Глава 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.