Метод простых итераций для функциональных уравнений

Утверждение 1. Пусть (одномерный случай) и задана функция f(x), удовлетворяющая условию:

(9) (Условие Липшица с константой на отрезке [ a, b ].)

Тогда оператор f (x) - сжимающий и уравнение f(x)=х имеет единственную неподвижную точку, которую можно найти методом простых итераций: .

Действительно, определим . Следовательно, выполняется условие (8) теоремы 2, откуда и следует результат.

Утверждение 2. Пусть , причем (10)Тогда оператор f (x) является сжимающим.

Согласно теореме о среднем . Оценим это неравенство по модулю: . Это говорит о том, что выполняется условие (9) утверждения 1, значит, f (x) действительно сжимающий оператор.

Рассмотрим задачу поиска корней уравнения . Пусть известны границы для корня этого уравнения и мы хотим найти этот корень методом итераций. Если удастся привести уравнение к виду x=f(x), так чтобы выполнялось одно из условий утверждения 1 или утверждения 2, то в этом случае можно будет применить метод итераций. Такое преобразование, вообще говоря, не единственно, причем главная трудность заключается в определении того замкнутого ограниченного множества S (а в одномерном случае – отрезка [ a, b ]), для которого помимо условия сжатости, выполняется условие .

Утверждение 3. Определим множество - замкнутый r -“шар” с центром в точке х₀ (в одномерном случае – отрезок). Пусть оператор Т - сжимающий на S и выполняется следующее условие: (11)Тогда для любой точки выполняется: .

Достаточно доказать, что Имеем: {неравенство треугольника}

.

23 Метод Ньютона.

Пусть снова задано уравнение f(x)=0. Запишем его в виде , где и . Пусть х_к – некоторое приближение к корню х*. Для ускорения сходимости итераций желательно, чтобы был как можно меньше. Положим , то есть

Отсюда находим, что . Подставляя в исходное уравнение, получаем рекуррентную формулу: . Это и есть итерационная процедура Ньютона.

24.Численные методы линейной алгебры.

К численным методам линейной алгебры относятся: численные методы решения систем алгебраических уравнений (ЛАУ), обращение матриц, вычисление определителя матрицы, вычисление собственных значений и собственных векторов матриц. Численные методы решения систем ЛАУ можно разбить на две группы: прямые методы (метод исключения Гаусса и его модификации) и так называемые итерационные методы. Метод Гаусса подробно рассматривается в курсе линейной алгебры, где, в частности показывается, что число арифметических действий, затрачиваемых на приведение системы к треугольному виду пропорционально n³. При вычислении определителя методом Гаусса затрачивается арифметических действий. Несмотря на очевидные преимущества прямых методов (конечность действий), их применение не всегда возможно. Если матрица A линейной системы плохо обусловлена, то вследствие неизбежных ошибок округления на ЭВМ, полученное приближенное решение системы может оказаться сколь угодно далеким от точного решения. Чтобы разобраться в этом вопросе, нам понадобится понятие нормы матрицы, спектра матрицы и обсудить некоторые дополнительные свойства матриц, связанные с этими понятиями.

25.

Нормы матриц. Спектральные свойства матриц. Пусть , Обозначим M_n - множество квадратных матриц . Пусть каждой матрице поставлено в соответствие число .Это число называется нормой матрицы A, если выполняются следующие аксиомы:

1. . 2. . 3. (неравенство треугольника).

4. (кольцевое свойство).

Определение. Норма называется мультипликативной, если выполняются все четыре аксиомы, и аддитивной, если выполняются первые три аксиомы.

Следствие. Если норма матрицы A – мультипликативна, то согласно свойству 4: .Пусть . Определим норму матрицы следующим образом:

. (1) Таким образом, определенная норма матрицы называется подчиненной векторной норме .

Определение. Если матричная норма удовлетворяет условию , (2)то такая норма называется согласованной с нормой вектора.

Следствие 1. Любая подчиненная норма является также и согласованной (обратное вообще говоря, неверно).

Действительно, из (1) в силу определения супремума: , Тот факт, что обратное неверно, подтверждается конкретными примерами матричных норм, с которыми мы познакомимся далее.

Следствие 2. Пусть A = E и норма матрицы – подчиненная векторной норме. Тогда, поскольку Ex = x, то и из (1) немедленно следует что Полученное условие можно считать необходимым условием подчиненной нормы.Определим некоторые наиболее употребительные на практике матричные нормы.

- евклидова норма (норма Фробениуса: norm(a, ‘fro’)- в MATLAB),

- “столбцовая” норма (norm(a, 1)),

- “строчная” норма (norm(a, inf)),

- “спектральная” норма (norm(a)=norm(a, 2)), где - так называемые сингулярные числа матрицы А.

Замечание. Все приведенные выше нормы матриц согласованы с соответствующей нормой вектора. Спектральная норма является к тому же и подчиненной евклидовой норме вектора. Кроме того, среди всех возможных норм, согласованных с евклидовой нормой вектора, спектральная норма принимает минимальное значение.

Определение 1. Число (вообще говоря, комплексное) называется собственным значением матрицы А, соответствующим собственному вектору x, если выполняется условие: . (3)

Определение 2. Множество всех собственных чисел матрицы А , записанных с учетом их кратности, называется спектром матрицы А и обозначается S (A).

Определение 3. Спектральным радиусом квадратной матрицы А называется максимальный из модулей ее собственных значений.Заметим, что система (3) эквивалентна следующей однородной системе уравнений: . (4)

Как известно из курса линейной алгебры, система (4) имеет нетривиальные решения тогда и только тогда, когда . (5)Уравнение (5)- алгебраическое уравнение n -ой степени относительно .

Все его корни – собственные числа матрицы А. Имеет место следующая

Теорема 1. Для любой квадратной матрицы и любой согласованной матричной нормы имеет место неравенство:

Пусть - произвольное собственное значение матрицы A, и - соответствующий собственный вектор . Оценим по норме Определение 4. Сингулярным числом матрицы А называется собственное значение матрицы .

Определение 5. Матрица А называется положительно (неотрицательно) определенной (пишут: или ), если соответствующая квадратичная форма .