Глава 3. Итерационные методы решения систем

⇐ ПредыдущаяСтр 5 из 13Следующая ⇒

Линейных алгебраических уравнений

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

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<e<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) является не вполне корректным.

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

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

(3.7)

Полагая, что коэффициенты a_ii¹0 (i=1, 2,…, n) разрешим первое уравнение из (3.7) относительно х₁ , второе относительно х₂ и т.д. Тогда получим

(3.8)

где b_i=b_i/a_ii , a_ij=-a_ij/a_ii при i¹j, a_ij=0 при i=j,

(i,j=1, 2,…,n).

Вводя обозначения

, ,

перепишем систему уравнений (3.8) в матричной форме

х=b+aх . (3.9)

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

х⁽⁰⁾=b ,

где индекс (0) – номер нулевого приближения.

Дальше строим последовательность

х⁽¹⁾= b+aх⁽⁰⁾ ,

х⁽²⁾= b+aх⁽¹⁾ ,

………….. (3.10)

х⁽^k+1)= b+aх^(k) .

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

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

Итерация заканчивается при выполнении условия

, где 0<e<1.

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

Теория сходимости итерационных процессов для решения СЛАУ разработана достаточно хорошо. Здесь ограничимся рассмотрением нескольких достаточных условий сходимости.

Теорема 3.1 [3]. Процесс итерации для приведенной линейной системы (3.9) сходится к единственному ее решению, если какая-нибудь каноническая норма матрицы a меньше единицы, т.е. для итерационного процесса

х⁽^k)= b+aх^(k-1) (k=1,2,…)

достаточное условие сходимости есть