39. Оценки погрешности метода простой итерации для решения систем уравнений.

Теорема 2. (о погрешностях приближения в МПИ) Пусть Bq<1. Тогда справедливы оценки погрешности:

, (апостериорная оценка)

. (априорная оценка)

Доказательство: Рассмотрим два соседних приближения:

x^(k+1)=Bx^(k)+f,

x^(k)=Bx^(k-1)+f.

Возьмем разность между этими приближениями:

x^(k+1)- x^(k)=Bx^(k)- Bx^(k-1)= B(x^(k)- x^(k-1))

и про нормируем это выражение:

,

. (*)

Из последнего неравенства (*) видно в силу условия q<1, что элементы итерационной последовательности сближаются с ростом номера k. Оценим разность между (k+m)-ым и k-м членами последовательности при m>0:

Устремляя при фиксированном k , т.е.

.

Используя вновь соотношение (*), получим

откуда и получается априорная оценка погрешности:

.

Теорема 2 доказана.

40. Метод Зейделя для решения систем линейных алгебраических уравнений.

При вычислении очередного (k+1)-го приближения в МПИ в правую часть расчетной формулы (13) подставляется предыдущее, k-ое приближение, т.е. вектор x^(k), все компоненты которого имеют одинаковый итерационный индекс: (x₁^(k), x₂^(k),…, x_n^(k)). Однако элементы вектора вычисляются последовательно, поэтому , например, при вычислении x₂^(k+1) уже вычислен x₁^(k+1) в новом приближении. Метод, в котором для подсчета i-ой компоненты (k+1)-ого приближения используются уже найденные на этом, т.е. (k+1)-м шаге, новые значения первых i-1 компонент, называется методом Зейделя. Если приведение системы к итерационному виду сделано как это описано в предыдущем параграфе, то расчетная формула для элементов решения

, i=1,2,…, n. (15)

В развернутом виде метод Зейделя определяется системой равенств:

x₁^(k+1) = (b₁-a₁₂x₂^(k)-a₁₃x₃^(k)-…-a_1nx_n^(k))/a₁₁,

x₂^{(k+1 )}= (b₂-a₂₁x₁^(k+1)-a₂₃x₃^(k)-…-a_2nx_n^(k))/a₂₂,

…………………………………………… (16)

x_n^(k+1) = (b_n-a_n1x₁^(k+1)-a_n2x₂^(k+1)-…-a_n,n-1x_n-1^(k+21))/a_nn.

В сравнении с МПИ метод Зейделя сходится быстрее. Кроме того, при его реализации на компьютере не нужен отдельный массив для хранения нового приближения. Вычисленные компоненты нового вектора x^(k+1) заносятся на место соответствующих компонент старого вектора x^(k), в этой связи метод Зейделя называют методом последовательных смещений. В МПИ нужно целиком сохранять массив значений x^(k), подставляемый в правую часть расчетной формулы (13), до тех пор, пока не сформирован полностью новый массив x^(k+1) – результат текущего итерационного шага. Поэтому МПИ называют методом одновременных смещений.

Достаточные условия метода Зейделя такие же как и для МПИ.

Процесс итераций продолжаем до тех пор, пока значения x_i^(k+1) (i=1,2,…,n) не станут близким к значениям x_i^(k) с заданной погрешностью .