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

 

Теорема 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 доказана.

 

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

 

При вычислении очередного (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) с заданной погрешностью g.

 

Алгоритм метода Зейделя.

Исходные данные:

А – квадратная матрица коэффициентов порядка n,

b – столбец свободных членов,

х⁽⁰⁾- столбец начальных значений,

n – порядок системы,

k_max- предельное число итераций (страховка от зацикливания),

e - требуемая точность.

Результаты:

х – вектор решений,

 

 

begin

 

i=1,n

 

x_i←x_i⁽⁰⁾

p_i←1/a_ii

 

 

 

k=1,k_max

 

k_end←k

 

i=1,n

 

t←b_i

 

j=1,n

 

 

i¹j

 

t=t-a_ijx

 

 

 

x_new←t*p_i

 

 

_½x_new-x_i½>g

 

k_end=0

 

 

x_i← x_new

 

 

k_end¹0

 

exit

 

 

 

end

 

 

k_end – фактическое количество итераций (если достигнута точность e), если точность не достигнута за. k_max итераций, то k_end= 0.

Вспомогательные переменные:

t – переменная суммирования для накопления очередной компоненты,

x_new – переменная для временного хранения очередной компоненты решения в новом приближении.

Тело алгоритма состоит из двух последовательных циклов: первый играет вспомогательную роль (назначает начальные значения элементам столбца из неизвестных, вычисляет обратные величины диагональных элементов), второй – он троекратный, реализует процесс Зейделя. Во внешнем цикле (цикл «по ε») меняется значение счётчика k от единицы с шагом, равным единице, до заданного предельного числа итераций k_max. В конце его при истинном неравенстве |x_i^(k+1)-x^(k)_i|≤ε (тогда k_end=0) выполняется возврат к точке вызова данного алгоритма. В цикле «по строкам» (цикл «по i») вычисляются компоненты очередного приближения x_i^(k+1) (которые предварительно записываются в переменной x_new) и анализируется условие |x_i^(k+1)-x_i^(k)|≤. Если хотя бы для одной компоненты оно не выполняется, то переменной k_end присваивается нуль. Самый внутренний цикл (цикл «по j») служит для для реализации вычислений по формуле (15); в нем из правых частей уравнений системы (16) вычитаются левые части, содержащие все неизвестные кроме i- го.