Метод простой итерации Якоби

 

Метод Гаусса обладает довольно сложной вычислительной схемой. Кроме того, при вычислениях накапливается ошибка округления, что может привести к недостаточно точному результату. Рассмотрим метод простой итерации Якоби, свободный от этих недостатков, хотя требующий приведения исходной системы уравнений к специальному виду.

Для того, чтобы применить метод простой итерации, необходимо систему уравнений

 

Ax = b                                                                                          (3.22)

 

с квадратной невырожденной матрицей A привести к виду

 

x = Bx + c,                                                                                   (3.23)

 

где B – квадратная невырожденная матрица с элементами b_ij, i, j = 1, 2, …, n, x – вектор-столбец неизвестных x_i, c – вектор-столбец с элементами c_i, i = 1, 2, …, n.

Существуют различные способы приведения системы (3.22) к виду (3.23). Рассмотрим самый простой. Представим систему (3.22) в развернутом виде:

 

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_1nx_n = b₁

a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + … + a_2nx_n = b₂

a₃₁x₁ + a₃₂x₂ + a₃₃x₃ + … + a_3nx_n = b₃                                       (3.24)

a_n1x₁ + a_n2x₂ + a_n3x₃ + … + a_nnx_n = b_n

 

Из первого уравнения системы (3.24) выразим неизвестную x₁:

x₁ = a (b₁ – a₁₂x₂ – a₁₃x₃ – … – a_1nx_n),

 

из второго уравнения – неизвестную x₂:

x₂ = a (b₂ – a₂₁x₁ – a₂₃x₃ – … – a_2nx_n),

 

и т. д. В результате получим систему:

 

x₁=           b₁₂x₂ + b₁₃x₃ + … + b_{1, n-1}x_n-1 + b_1nx_n + c₁

x₂= b₂₁x₁                    + b₂₃x₃ + … + b_{2, n-1}x_n-1+ b_2nx_n + c₂

x₃= b₃₁x₁ + b₃₂x₂+ …           + b_{3, n-1}x_n-1+ b_3nx_n  + c₃                   (3.25)

.

x_n=  b_n1x₁ + b_n2x₂ + b_n3x₃          + b_{n, n-1}x_n-1                  + c_n

 

Матричная запись системы (3.25) имеет вид (3.23). На главной диагонали матрицы B находятся нулевые элементы, а остальные элементы вычисляются по формулам:

 

b_ij = , c_i = , i, j = 1, 2, …n, i j.                                      (3.26)

 

Очевидно, что диагональные элементы матрицы A должны быть отличны от нуля.

Выберем произвольно начальное приближение Обычно в качестве первого приближения берут x = c_i или x = 0. Подставим начальное приближение в правую часть (3.25). Вычисляя левые части, получим значения x , x , …, x . Продолжая этот процесс дальше, получим последовательность приближений, причем (k + 1)-е приближение строится следующим образом:

x =           b₁₂x + b₁₃ x  + … + b_{1, n-1} x + b_1n x  + c₁

x  = b₂₁x ₁                    + b₂₃ x + … + b_{2, n-1} x  + b_2n x  + c₂

x = b₃₁x  + b₃₂ x + …      + b_{3, n-1} x  + b_3n x    + c₃ … (3.27)

x =  b_n1x  + b_n2x + b_n3 x          + b_{n, n-1} x                            + c._n

 

Система (3.27) представляет собой расчетные формулы метода простой итерации Якоби.

Сходимость метода простой итерации. Известно следующее достаточное условие сходимости метода простой итерации Якоби.

Если элементы матрицы A удовлетворяют условию:

 

|a_ii| > , i = 1, 2, …, n.                                                       (3.28)

 

то итерационная последовательность x^k сходится к точному решению x^*.

Условие (3.28) называют условием преобладания диагональных элементов матрицы A, так как оно означает, что модуль диагонального элемента i-ой строки больше суммы модулей остальных элементов этой строки, i = 1, 2, …, n.

Необходимо помнить, что условие сходимости (3.28) является лишь достаточным. Его выполнение гарантирует сходимость метода простых итераций, но его невыполнение, вообще говоря, не означает, что метод расходится.

Справедлива следующая апостериорная оценка погрешности:

 

max|x  - x | £ max|x – x |, i = 1, 2, …, n,                        (3.29)

 

где b = max |b_ij| i, j = 1, 2, …, n.

Правую часть оценки (3.29) легко вычислить после нахождения очередного приближения.

Критерий окончания. Если требуется найти решение с точностью e, то в силу (3.29) итерационный процесс следует закончить как только на (k+1)-ом шаге выполнится неравенство:

 

max|x – x | < e,  i = 1, 2, …, n.                                         (3.30)

 

Поэтому в качестве критерия окончания итерационного процесса можно использовать неравенство

 

max|x – x | < e₁,  i = 1, 2, …, n.                                                  (3.31)

где e_{1 =} e _.

Если выполняется условие b £ , то можно пользоваться более простым критерием окончания:

 

max|x – x | < e,  i = 1, 2, …, n.                                                    (3.32)

 

В других случаях использование критерия (3.32) неправомерно и может привести к преждевременному окончанию итерационного процесса.

Пример 3.5.

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

20.9x₁ + 1.2 x₂ + 2.1x₃ + 0.9x₄= 21.70

1.2x₁ + 21.2 x₂ +  1.5x₃ +   2.5x₄= 27.46

2.1x₁ + 1.5 x₂ + 19.8x₃ +  1.3x₄= 28.76                                    (3.33)

0.9x₁ + 2.5 x₂ + 1.3x₃ + 32.1x₄= 49.72

Заметим, что метод простой итерации сходится, т. к. выполняется условие преобладания диагональных элементов (3.28):

 

|20.9| > |1.2 + 2.1 + 0.9|,

|21.2| > |1.2| + |1.5| + |2.5|,

|19.8| > |2.1| + |1.5| + |1.3|,

|32.1| > |0.9| + |2.5| + |1.3|.

 

Пусть требуемая точность e = 10^-3. Вычисления будем проводить с четырьмя знаками после десятичной точки.

Приведем систему к виду (3.25):

 

x₁  =              – 0.0574 x₂ – 0.1005x₃ – 0.0431x₄+ 1.0383

x₂ = –0.0566x₁                 – 0.0708x₃ –  0.1179x₄+ 1.2953

x₃ = –0.1061x₁ – 0.0758 x₂                            –  0.0657x₄+ 1.4525   (3.34)

x₄ = –0.0280x₁ – 0.0779 x₂ – 0.0405x₃                + 1.5489

 

Величина b = max |b_ij|, i, j = 1, 2, 3, 4 равна 0.1179, т. е. выполняется условие b £ , и можно пользоваться критерием окончания итерационного процесса (3.32).

В качестве начального приближения возьмем элементы столбца свободных членов:

 

x  = 1.0383, x  = 1.2953, x  = 1.4525, x  = 1.5489.                 (3.35)

 

Вычисления будем вести до тех пор, пока все величины |x – x |, i = 1, 2, 3, 4, а следовательно, и max|x – x | не станут меньше e = 10^-3.

Последовательно вычисляем:

при k = 1

x    =               – 0.0574x   – 0.1005x – 0.0431x  + 1.0383 = 0.7512

x   = –0.0566x                   – 0.0708x  –  0.1179x  + 1.2953 = 0.9511

x   = –0.1061x  – 0.0758 x                              –  0.0657x  + 1.4525 = 1.1423

x  = –0.0280x  – 0.0779x – 0.0405x                    + 1.5489 = 1.3601

 

при k = 2

x = 0.8106,   x = 1.0118,   x = 1.2117, x = 1.4077.

 

при k = 3

x = 0.7978, x = 0.9977, x = 1.1975, x = 1.3983.

 

при k = 4

x = 0.8004, x = 1.0005, x = 1.2005, x  = 1.4003.

 

Вычисляем модули разностей значений x при k = 3 и k = 4:

| x – x | = 0.026,  | x – x | = 0.028, | x – x | = 0.0030,  | x – x | = 0.0020.

 

Так как все они больше заданной точности e = 10^-3, продолжаем итерации.

 

При k = 5

x = 0.7999, x = 0.9999, x = 1.1999, x  = 1.3999.

 

Вычисляем модули разностей значений x при k = 4 и k = 5:

| x – x | = 0.0005, | x – x | = 0.0006, | x  – x | = 0.0006, | x – x | = 0.0004.

Все они меньше заданной точности e = 10^-3, поэтому итерации заканчиваем. Приближенным решением системы являются следующие значения:

x₁  0.7999, x₂  0.9999, x₃  1.1999, x₄  1.3999.

 

Для сравнения приведем точные значения переменных:

x₁= 0.8, x₂= 1.0, x₃= 1.2, x₄= 1.4.

Метод Зейделя

 

Модификацией метода простых итераций Якоби можно считать метод Зейделя.

В методе Якоби на (k+1)-ой итерации значения x , i = 1, 2, …, n. вычисляются подстановкой в правую часть (3.27) вычисленных на предыдущей итерации значений x . В методе Зейделя при вычислении x используются значения x , x , x , уже найденные на (k+1)-ой итерации, а не  x , x , …, x , как в методе Якоби, т.е. (k + 1)-е приближение строится следующим образом:

 x =                   b₁₂x     + b₁₃ x + … + b_{1, n-1} x + b_1n x + c₁

x  = b₂₁x                                   + b₂₃ x + … + b_{2, n-1} x + b_2n x  + c₂

x = b₃₁x  + b₃₂ x                    + … + b_{3, n-1} x   + b_3n x    + c₃(3.36)

x = b_n1 x  + b_n2x x + b_n3 x x + … + b_{n, n-1} x                         + c._n

 

Формулы (3.36) являются расчетными формулами метода Зейделя.

Введем нижнюю и верхнюю треугольные матрицы:

 

      0 0 0 … 0                                0 b₁₂   b₁₃ … b_1n

     b₂₁0      0 … 0                                 0  0      b₂₃ … b_2n

B ₁= b₃₁ b₃₂    0 … 0    и   B ₂= 0  0     0 … b_3n.

     b_n1 b_n2 b_n3 …0                                 0  0  0 … 0

 

Матричная запись расчетных формул (3.36) имеет вид:

 

x ^k+1 = B ₁ x ^k+1 + B ₂ x ^k + c.                                                                     (3.37)

 

Так как B = B ₁ + B ₂, точное решение x ^* исходной системы удовлетворяет равенству:

x ^* = B ₁ x ^* + B ₂ x ^* + c.                                                                         (3.38)

Сходимость метода Зейделя. Достаточным условием сходимости метода Зейделя является выполнение неравенства:

b = max |b_ij|, < 1,  i, j = 1, 2, …, n.                                                (3.39)

 

Неравенство (3.39) означает, что для сходимости метода Зейделя достаточно, чтобы максимальный по модулю элемент матрицы B был меньше единицы.

Если выполнено условие (3.39), то справедлива следующая апостериорная оценка погрешности:

 

max|x  - x | £ max|x – x | i = 1, 2, …, n,                       (3.40)

где b – максимальный элемент матрицы B, b₂– максимальный элемент матрицы B ₂.

Правую часть оценки (3.40) легко вычислить после нахождения очередного приближения.

Критерий окончания. Если требуется найти решение с точностью e, то в силу (3.37) итерационный процесс следует закончить как только на (k+1)-ом шаге выполнится неравенство:

 

max|x – x | < e,  i = 1, 2, …, n.                                      (3.41)

 

Поэтому в качестве критерия окончания итерационного процесса можно использовать неравенство

 

max|x – x | < e₁,  i = 1, 2, …, n.                                             (3.42)

где e_{1 =} e _.

 

Если выполняется условие b £ , то можно пользоваться более простым критерием окончания:

 

max|x – x | < e,  i = 1, 2, …, n.                                                 (3.43)

 

Метод Зейделя как правило сходится быстрее, чем метод Якоби. Однако возможны ситуации, когда метод Якоби сходится, а метод Зейделя сходится медленнее или вообще расходится.

Пример 3.6.

Применим метод Зейделя для решения системы уравнений (3.33) из примера 3.5. Первые шаги полностью совпадают с процедурой решения по методу Якоби, а именно: система приводится к виду (3.34), затем в качестве начального приближения выбираются элементы столбца свободных членов (3.35). Проведем теперь итерации методом Зейделя.

 

При k = 1

x    = – 0.0574x   – 0.1005x – 0.0431x  + 1.0383 = 0.7512

 

При вычислении x используем уже полученное значение x :

x   = –0.0566 x    – 0.0708x  –  0.1179x  + 1.2953 = 0.9674

 

При вычислении x  используем уже полученные значения x  и x :

 

x   = –0.1061 x  – 0.0758 x  –  0.0657x  + 1.4525 = 1.1977

При вычислении x  используем уже полученные значения x , x , x :

 

x  = –0.0280 x  – 0.0779 x   – 0.0405x x   + 1.5489 = 1.4037

 

Аналогичным образом проведем вычисления при k = 2 и k = 3. Получим:

 

при k = 2

x = 0.8019,   x = 0.9996,   x = 1.9996, x = 1.4000.

 

при k = 3

x = 0.80006, x = 1.00002, x = 1.19999, x = 1.40000.

 

Известны точные значения переменных:

x₁= 0.8, x₂= 1.0, x₃= 1.2, x₄= 1.4.

 

Сравнение с примером 3.5 показывает, что метод Зейделя сходится быстрее и дает более точный результат.

Тема 4. Приближение функций

Постановка задачи

 

Задача приближения (аппроксимации) функций заключается в том, чтобы для данной функции построить другую, отличную от нее функцию, значения которой достаточно близки к значениям данной функции. Такая задача возникает на практике достаточно часто. Укажем наиболее типичные случаи.

1. Функция задана таблицей в конечном множестве точек, а вычисления нужно произвести в других точках.

2. Функция задана аналитически, но ее вычисление по формуле затруднительно.

При решении задачи поиска приближенной функции возникают следующие проблемы.

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

2. Необходимо выбрать критерий близости исходной и приближенной функции. Это может быть требование совпадения обеих функций в узловых точках (задача интерполяции), минимизация среднеквадратического уклонения (метод наименьших квадратов) и др.

3. Необходимо указать правило (алгоритм), позволяющее с заданной точностью найти приближение функции.

⇐ Предыдущая12345678Следующая ⇒

Поделиться: