Численные методы линейной алгебры

Глава 3. Итерационные методы решения систем
линейных алгебраических уравнений

В главе будут описаны итерационные методы решения систем линейных алгебраических уравнений

Ax=b. (3.1)
При решении системы уравнений (3.1) итерационным методом отыскивается последовательность векторов x^(k) такая, что
(3.2)
Введем понятие вектора погрешности
z^(k) =x^(k)-x (3.3)
и вектора невязок
R^(k)=Ax^(k)-b . (3.4)
Из формулы (3.2) следуют, что

Отметим, что в отличие от вектора погрешности z^(k) вектор невязок R^(k) может быть вычислен. Поэтому очень часто в качестве условия окончания итераций выбирают
, где 0<<1. (3.5)
Условие (3.5) является не вполне корректным, покажем это. Действительно, из (3.3) имеем
Az^(k)=Ax^(k)-b= R^(k) ,
z^(k)=A^-1 R^(k) ,

С другой стороны

Следовательно,

или
, (3.6)
где – число обусловленности матрицы А. Из (3.6) следует, что лишь для хорошо обусловленных систем (3.1) относительная малость векторов невязок R^(k) влечет за собой относительную малость векторов погрешности z^(k). Для таких задач условие (3.5) является корректным.
Для плохо обусловленной системы (3.1) относительная малость векторов невязок R^(k) не влечет относительную малость векторов погрешности z^(k). Для таких задач условие (3.5) является не вполне корректным.


3.1. Метод простой итерации

Для описания метода простой итерации [2-4, 6, 11] распишем систему (3.1)

(3.7)
Полагая, что коэффициенты a_ii0 (i=1, 2,…, n) разрешим первое уравнение из (3.7) относительно х₁ , второе относительно х₂ и т.д. Тогда получим
(3.8)
где _i=b_i/a_ii , _ij=-a_ij/a_ii при ij, _ij=0 при i=j,
(i,j=1, 2,…,n).
Вводя обозначения

, ,
перепишем систему уравнений (3.8) в матричной форме
х=+х . (3.9)
Систему уравнений (3.9) будем решать методом последовательных приближений. За нулевое приближение примем столбец свободных членов
х⁽⁰⁾= ,
где индекс (0) – номер нулевого приближения.
Дальше строим последовательность

х⁽¹⁾= +х⁽⁰⁾ ,

х⁽²⁾= +х⁽¹⁾ ,
………….. (3.10)
х^(k+1)= +х^(k) .

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

Таким образом, алгоритм метода простой итерации для решения СЛАУ будет следующим

Итерация заканчивается при выполнении условия
, где 0<<1.