Метод последовательных приближений (метод итерации)

Пусть дана система линейных уравнений

(1)

 

Запишем систему (1) в матричном виде:

AX=B,

где

А= , X= , B= . (2)

Предполагая, что диагональные элементы a_ii 0 (i =1, 2,…, n),выразим x ₁ через первое уравнение системы, x ₂- через второе уравнение и т.д. В результате получим систему, эквивалентную системе (1):

 

(3)

 

 

Обозначим , где i =1, 2,…, n; j =1, 2,…, n. Тогда система (3) запишется таким образом:

 

(3')

Система (3') называется системой, приведенной к нормальному виду. Введя обозначения.

, ,

Запишем систему (3’) в матричной форме:

или

= + ∙ . (4)

Решим систему (4) методом последовательных приближений. За нулевое приближение примем столбец свободных членов:

= - нулевое приближение,

далее, построим матрицы-столбцы

= + ∙ - первое приближение;

= + ∙ - второе приближение.

и т.д.

Вообще, любое (k +1)-e приближение вычисляют по формуле

 

X^(k+1)= + X^(k) (k=0, 1,…, n). (5)

 

Если последовательность приближений X ⁽⁰⁾, X ⁽¹⁾,…, X ^(k) имеет предел , то этот предел является решением системы (3), поскольку по свойству предела , т.е. .

 

 

Пример 1. Методом последовательных приближений решить систему

 

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

, .

 

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

.

Первое приближение.

+ ∙ =

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

+ ∙ =

 

Третье приближение.

+ ∙ =

Таким образом, x ₁=2,9935; x ₂=1,0068; x ₃=1,0068 и с точностью до 10^-1 поучаем x ₁=3; x ₂=1; x ₃=1.

 

Пример 2. Методом итерации решить следующую систему с точностью до 10^-3.

 

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

или

 

 

Заметим, что линейную систему можно привести к нормальному виду также следующим образом: записать коэффициенты при x ₁, x ₂, x ₃ в соответствующих уравнениях системы (*) в виде kx, где k - число, близкое к коэффициенту при соответствующем неизвестном и на которое легко разделить коэффициенты при неизвестных и свободные члены.

Например:

Перепишем систему (*) таким образом:

Матрица и вектор принимают вид

 

2) Последовательно находим

,

+ ∙ = ,

 

+ ∙ = .

 

Таким образом, с точностью до 10^-3 получаем

x ₁=0,236; x ₂=1,103; x ₃= -0,214.

 

 

УСЛОВИЯ СХОДИМОСТИ ИТЕРАЦИОННОГО ПРОЦЕССА

Пусть дана приведённая к нормальному виду система линейных уравнений Х = + Х. Итерационный процесс и его сходимость зависят от величины элементов матрицы следующим образом: если сумма модулей элементов строк или сумма модулей элементов столбцов меньше единицы, то процесс итерации для данной системы сходится к единственному решению независимо от выбора начального вектора.

Следовательно, условия сходимости можно записать так:

<1 (i=1, 2, …,n) или <1 (j=1, 2, …,n)

Пример 1. Для системы

или

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

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

Процесс итерации заведомо сходится, если элементы матрицы удовлетворяют неравенству , где n- число неизвестных данной системы. В нашем примере n =3 и все элементы _.

Сходимость итерационного процесса связана нормами матрицы следующими соотношениями. Если выполняется одно из условий:

либо

либо

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

 

 

Так, в рассмотренном выше примере норма

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

 

 

ОЦЕНКА ПОГРЕШНОСТИ ПРИБЛИЖЕННОГО ПРОЦЕССА МЕТОДА ИТЕРАЦИИ

Если задана допустимая погрешность вычислений и - вектор точных значений неизвестных линейной системы, а есть k - e приближение значений неизвестных, вычисленное методом итерации, то для оценки погрешности метода применяется формула

(1)

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

 

Пример 1. Показать, что для системы

 

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

 

 

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

или

 

2) Матрица системы

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

3) Имеем

4) Применяем формулу (1), находим

Теоретическая оценка числа итерации, необходимых для обеспечения заданной точности, практически оказывается завышенной.