Итерационные методы решения систем линейных уравнений

Рассмотрим систему из 3-х уравнений с тремя неизвестными:

 

а₁₁х₁ + а₁₂х₂ + а₁₃х₃ = b₁; (2.1)

а₂₁х₁ + а₂₂х₂ + а₂₃х₃ = b₂; (2.2)

а₃₁х₁ + а₃₂х₂ + а₃₃х₃ = b₃. (2.3)

 

Предположим, что а₁₁¹0, а₂₂¹0, а₃₃¹0, и перепишем систему в виде:

 

(2.4)

(2.5)

(2.6)

 

В методе Якоби некоторое исходное приближение к решению этой системы, обозначенное как х₁⁽⁰⁾, х₂⁽⁰⁾, х₃⁽⁰⁾, одновременно используется с помощью выражений (2.4) – (2.6) для вычисления первого приближения х₁⁽¹⁾, х₂⁽¹⁾, х₃⁽¹⁾ .Эти значения используются для вычисления второго приближения, и т.д. Процесс прекращается, когда достигается требуемая точность решения. В этом методе замена значений всех приближений производится одновременно (метод одновременных смещений).

В методе Гаусса-Зейделя также берется исходное приближение к решению системы (2.1) – (2.3), обозначенное как х₁⁽⁰⁾, х₂⁽⁰⁾, х₃⁽⁰⁾.

Подставим это решение в (2.4) и вычислим новое значение х₁:

.

Используя полученное значение х₁⁽¹⁾ и начальное значение х₃⁽⁰⁾, вычислим из (2.5) новое значение х₂:

.

Используя значение х₁⁽¹⁾ и х₂⁽¹⁾, вычислим из (2.6) новое значение х₃:

.

Этим заканчивается первая итерация. Теперь можно заменить исходные значения х₁⁽⁰⁾, х₂⁽⁰⁾, х₃⁽⁰⁾ на х₁⁽¹⁾, х₂⁽¹⁾, х₃⁽¹⁾ и вычислить следующее приближение.

В общем случае k-ое приближение определяется формулами:

(2.7)

Видно, что текущее значение неизвестных сразу же используется для последующих вычислений. Например, нельзя вычислить х₂^(k), пока не получено х₁^(k). Аналогично, для вычисления х₃^(k) необходимо сначала определить х₁^(k) и х₂^(k).

Метод Гаусса-Зейделя очень удобен для использования на ЭВМ.

Рассмотрим теперь систему из n уравнений с n неизвестными:

(2.8)

Мы по-прежнему предполагаем, что диагональные коэффициенты а_ii отличны от 0 для всех i. Тогда k-ое приближение к решению будет задаваться формулой:

.

Итерационный процесс продолжается до тех пор, пока все х_i^(k) не станут достаточно близкими к х_i^(k-1). Критерий близости можно задать в виде:

,

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

Обратимся к вопросу сходимости метода. Перед обобщением на случай n уравнений рассмотрим более простой пример – систему из 2-х уравнений. При этом возьмем систему, в которой диагональные коэффициенты по абсолютному значению будут больше недиагональных.

 

(2.9)

 

Точное решение системы:

х = 2/5, у = 6/5.

Из (2.9) запишем:

 

Результаты последовательных итераций составляют:

 

Итерация	х	у
		3/2
	1/4	9/8
	7/16	39/32

 

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

 

 

Рисунок 1.5 – Итерационный процесс решения системы (2.9)

 

 

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