Метод простой итерации решения СЛАУ

Покажем как применяется принцип сжатых изображений к исследованию скорости сходимости и самой сходимости итерационных процессов решения систем уравнений.
Пусть дана система вида:
Х=Вх+b (1) где
B= X= b=
Правую часть уравнения (1) обозначим через Ф(х), тогда Ф(х) можно уже рассматривать как отображение пространства Rⁿ Rⁿ, где ; ; ; ; (2 – координаты ).
Решение уравнения (1) таким образом сведется к отысканию неподвижной точки отображения Ф. Для того чтобы отображение Ф имело неподвижную точку – нужно чтобы Ф было сжатием. Если покажем, что Ф – сжатие, тогда имеет в пространстве единственную неподвижную точку х^* и к ней будет сходится итерационный процесс: x_n+1=Ф(x_n), x_n ; x⁽ⁿ⁺¹⁾=Bx⁽ⁿ⁾+b (3).
В координатной форме метод (3) запишется: x_i⁽ⁿ⁺¹⁾ =⁽ⁿ⁾ + b_i, (4).
Определим при каких же условиях Ф будет сжатием. Убедимся, что ответ зависит не только от Ф, но и от выбора метрики.
Рассмотрим первую метрику пространства - кубическую.
1) , где х=(x_1, x_2,…, x_n), х=(x_{1 ,} x_{2 ,…,} x_n ).
;
- следовательно, чтобы Ф было сжатие
; ₁ = (5)
2)Рассмотрим метрику октаэдрическую:
аналогично случаю 1) мы можем показать, что Ф будет сжатием, если: ₂ = (6)
3)Для сферической метрики:
² ; ₃ = ² (7)
Таким образомесли выполняется одно из условий(5)-(7)то Ф – сжатие. И по принципу Банаха для отображения Ф в пространство существует единственная неподвижная точка х^* (х^*, …,х_n^*) к которым сходится итерационный процесс (3)/(4). -> Доказали Теорему.
Теорема: если для матрицы В из уравнения (1) выполняется одно из условий _{l ,} l=1,3 то система линейных алгебраических уравнений (1) имеет единственное решение х^*, которое может быть получено по формуле (3) как предел последовательности, начиная с некоторого х₀. Причем скорость сходимости процесса (3) определяется следующим соотношением: .
Пусть дана система Ах=b. Домножим на - обе части:
х - Ах=- +x; x= Ах - +x; x⁽ⁿ⁺¹⁾=( A)xⁿ - (*)
Чтобы процесс (*) сходился -> = <1.
Очевидно, что в итерационный процесс до конца выполнения просчета шага n+1 должны сохранятся и значения n-шага. Этим недостатком не владеет метод Зейделя, который является модификацией метода простой итерации.
Метод Зейделя:
+ ;

Предлагаемый метод позволяет сразу же использовать при вычислении координат вектора х⁽ⁿ⁺¹⁾ уже найденные его предыдущие координаты.
Условие сходимости и метода Зейделя и метода простой итерации одинаковы. Области сходимости у этих методов не всегда совпадают, а если совпадают то скорость Зейделя > скорости итерации.

17. Систему нелинейных уравнений можно кратко записать в векторном виде f(x)=0 или в коор. виде: f_k(x₁,x, … x_m)=0, . Такие системы решаются только итер. Методами. Для такой сис-мы исп м-д простой итерации. Для этого приводят сис-му к виду:

…… (15.1)

 

Для ее записи в m - мерном числовом пространстве R_m введем два вектора: один из них х для изображения совокупности неизвестных (х₁,х₂,...х_m), второй будет обозначать совокупность значений функций (, ,... ). Система запишется в краткой векторной форме х = (х). Пусть как-то выбрано начальное приближение к решению х⁰ =() Все следующие приближения будут находиться по правилу итераций xⁿ⁺¹ = . Для выяснения условий, достаточных для сходимости последовательности приближений хⁿ (n = 0,1,...,) применим теорему Банаха о сжимающих отображениях. Для этого нужно в R_m ввести метрику.

1. Случай кубической метрики

В шаре возьмем две произвольные точки х(х₁,х₂,...х_m) и y(y₁, y₂, … y_m) оценим изменение функции :

Звездочкой у скобок отмечено то, что значение функции, стоящей в скоб­ках, должно быть взято в некоторой точке отрезка прямой, соединяющего х и у. Чтобы найти оценку изменения, не зависящую от i и положения точек х и у, заменим последнюю из скобок ее максимальным значе­нием по х и i. Тогда получим

 

Отсюда видно, что в качестве числа q может быть взята величина

q=

Все это позволяет сформировать теорему о сходимости итерационной последовательности в случае кубической метрики.

Теорема 15.1

Пусть

1) функции определены и непрерывно дифференцируемы в области

области

2) в этой области

3) начальные приближения неизвестных удовлетворяют неравенствам

4) для чисел , q и М выполняется условие

Тогда система (15.1) в области имеет решение (x₁^*, x₂^*… x_m^*) и к нему сходиться итер. посл-ть приближений (x₁ⁿ, x₂ⁿ… x_mⁿ)

2) Скорость сходимости м.б. охарактеризована нерав-м:

, (i= )

2. Случай октаэдрической метрики

Аналогично теореме 15.1. в R^m для октаэдрической метрик м.б. доказана сл.теорема

Теорема 15.2. Пусть

1) ф-ция определены и непрерывны в области

2) удовлетв. в этой обл-сти усл-ю

3)для нач. приближений неизв. вып-ся нер-во

4)) для чисел , q и М выполняется условие

Тогда:

1) система (15.1) в области имеет решение (x₁^*, x₂^*… x_m^*) и к нему сходиться итер. посл-ть приближений (x₁ⁿ, x₂ⁿ… x_mⁿ)

2) скорость сходимости хар-ся нерав-ом

3. Случай сферической метрики

Теорема 15.3

Пусть:

1) ф-ции определены в области

2) удовлетв. в этой обл-сти усл-ю

3)для нач. приближений неизв. вып-ся нер-во

4)) для чисел , q и М выполняется условие

Тогда:

3) система (15.1) в области имеет решение (x₁^*, x₂^*… x_m^*) и к нему сходиться итер. посл-ть приближений (x₁ⁿ, x₂ⁿ… x_mⁿ)

4) скорость сходимости хар-ся нерав-ом

Сходимость метода линейная. Сами вычисления просты, но сложно найти такую систему х= , которая была бы эквивалентна исх.сис-ме f(x)=0 и одновременно обеспечивала бы сходимость

18. Надо решить сис-му Нелин. Ур-ний

……….. (16.1)

Рассмотрим n - мерное векторное пространство R_m, x=(x₁,…x_m). Введем вектор - функцию f(x)=(f₁(x), f₂(x),… f_m(x)), тогда система (16.1) запишется в виде f(x)=0 (16.2)

Пусть известно некоторое исходное приближение х° = {х₁°,х₂°,..., х_n°} к решению системы х^* = (х₁^*,... х_m^*). Для выделения главной линей­ной части из системы (16.2) удобно рассмотреть не точное решение х*, а вектор-погрешность х* - х° = (х₁* - х₁⁰, … х_m* -х_m°)= = (,..., ). Уравнение для получится, если в равенстве f(х*)=0 заменить х* на х° + , т.е. f(х° + )= 0. Предполагая все составляющие вектора малыми величинами, выделим в системе (16.1) главную линейную часть. Для этого рассмотрим уравнение любого номера f_i(х° + )=0 и разложим f_i в ряд Тейлора по степеням погрешности и сохраним в разложении линейную часть, отбросив все члены более высокого порядка. После этого получится линейная система уравнений относительно погрешностей, приближенно заменяющая систему (16.1).

 

Решая ее относительно , например, методом Гаусса, мы получим приближенные значения для например, , Мы улучшим исходные значения неизвестных x_i⁰,если к ним прибавим , т.е.

Новые значения х¹_m аналогичными вычислениями могут быть тоже улучшены и т.д. В результате для каждого значения х_i* получится последовательность приближений х_iⁿ такая, что каждое следующее приближение х_iⁿ⁺¹ будет находиться из линейной системы по предыдущему приближению х_iⁿ:

Рассмотрим матрицу Якоби системы функций f_i, i=1,m

(16.4)

Значение ее при х = хⁿ есть матрица системы (16.4). Система будет иметь единственное решение, если ее определитель отличен от нуля . Итак, метод Ньютона сходится, если в достаточно малой окрестности

корня , причем сходимость квадратичная. Вычисления по

методу Ньютона несколько сложнее, чем при простых итерациях, ибо на каждом шаге надо находить матрицу производных и решать систему линейных уравнений. Поэтому в некоторых учебниках рекомендуют вычислить матрицу производных только на начальной итерации и использовать ее во всех остальных итерациях.