Оценка погрешности приближенного процесса методом итерации

Если задана допустимая погрешность вычислений  и Х_i – вектор точных значений неизвестных линейной системы, а Х_i^(k) – есть k приближение значений неизвестных, вычисленное методом итераций, то для оценки погрешности || Х_i - Х_i^(k)|| £  метода применяется формула

                                .                            (3.8)

где ||a|| – одна из трех норм матрицы a, ||b|| – та же норма вектора b,    а k – число итераций, необходимое для достижения заданной точности.

При этом предполагается, что последовательное приближение Х_i^(j) (где  j = 0, 1, 2, 3, …, k;  i = 1, 2, …, n) вычисляется точно, в нем отсутствуют погрешности округления.

Пример.  Методом последовательного приближения решить систему

1. Приведем данную систему к нормальному виду

;  .

2. Строим последовательные приближения.

Нулевое:

.                 

Первое:

.

Второе:

.

Третье:

.

С точностью 10^-1 получаем х₁ = 3, х₂ = 1, х₃ = 1.

Итерационный процесс сходится, т.к.

;

 .

        Процесс итераций заведомо сходится, если элементы матрицы a удовлетворяют неравенству |a_ij| < 1/n, где n - число неизвестных данной системы.

В нашем примере n = 3, |a_ji| < 1/3. Используя норму ,

||a||₂ = max (0,4; 0,325; 0,325)=0,421 .

Соответствующая матрица ||b||₂ = (3,25 + 1,4 + 1,4) = 6,05 .

Применяя формулу

при ε =10^-4 , получим

 .

или ,  значит    итераций.

ЛЕКЦИЯ 4. МЕТОД ЗЕЙДЕЛЯ

Условия сходимости процесса Зейделя

Метод Зейделя представляет собой некоторую модификацию метода последовательных приближений. В методе Зейделя при вычислении (k + 1) приближения неизвестного x_i учитываются уже найденные ранее (k+1) приближение неизвестных.

Пусть дана линейная система

                           (4.1)

Выбираем произвольно начальное приближение корней  и подставляем в первое уравнение системы (4.1)

 ,

полученное первое приближение подставляем во второе:

.

Полученные первые приближения х₁⁽¹⁾ и х₂⁽¹⁾ подставляем в третье уравнение системы (4.1)

и т. д.

.

Аналогично строим вторые и третьи итерации.

Таким образом, предполагая, что k приближение корней х^k_i  известно, по методу Зейделя строим (k + 1) приближение

где k = 0, 1, 2, …, n.

Пример. Методом Зейделя решим систему:

1. Приведем систему к нормальному виду:

2. За нулевые значения возьмем соответствующие значения свободных членов

.

3. Строим итерации по методу Зейделя

Второе приближение

И т.д.

№итерации
0	0,19	0,97	-0,14
1	0,2207	1,0703	-0,1915
2	0,2354	1,0988	-0,2118
3	0,2424	1,1088	-0,2196
4	0,2454	1,1124	-0,2226
5	0,2467	1,1138	-0,2237
6	0,2472	1,1143	-0,2241
7	0,2474	1,1145	-0,2243
8	0,2475	1,1145	-0,2243

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

;

Процесс Зейделя для линейной системы Х = b + aХ также, так и процесс последовательных приближений, сходится к единственному решению при любом выборе начального приближения, если какая-нибудь из норм матрицы a меньше единицы. То есть

либо

,

либо

.

Процесс Зейделя сходится к единственному решению быстрее процесса простой итерации.

Оценка погрешности процесса Зейделя

Пусть дана линейная система

x = b + aх ,

где x_i – точное значение корней линейной системы, x_i^(k) – k приближение, вычисленное по методу Зейделя. Тогда оценка погрешности этого метода делается по формуле

 ;  .

Пример. Подсчитать, сколько итераций по методу Зейделя необходимо выполнить, чтобы с точностью до 10^-4 найти корни системы.

Решение:

; ;

 .

Значит

Или

Имеем :

 ,

т.е.

 ,

по формуле (3.8) определяем

 ,

 ,

 .