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

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

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

х^(k)= +х^(k-1) (k=1,2,…)

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

Доказательство.

При заданном произвольном векторе х^(о) , имеем последовательность приближений

х⁽¹⁾= +х^(о),

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

……………

х^(k)= +х^(k-1).

Откуда

х^(k)=(Е++²+…+^k-1)+^kх^(o). (3.11)

Так как , то и

(Е++²+…+^k-1)= ,

которое следует из [3] (см. теорема 5, стр. 250).

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

х= =(Е-)^-1. Теорема доказана.

Следствие 3.1. Процесс итерации для системы (3.9) сходится, если:

а) ,

б) ,

в) .

Следствие 3.2. Для системы уравнений

процесс итерации сходится, если выполнены условия теоремы Адамара.

3.1.2. Оценки погрешности метода простой итерации

Теорема 3.2 [3]. Пусть , тогда выполняется

, (3.12)

где х^(k) – к-ое приближение, х – точное решение.

Доказательство.

Пусть х^(о)=(0, 0,…, 0), тогда из (3.11) имеем

х^(k)=(Е++²+…+^k-1).

Точное решение

х=(Е++²+…+^k-1)+(^k+^k+1+…).

Тогда, вычитая из первого равенства второе и оценивая нормы, получим

,

где . Тогда имеем

что и требовалось доказать.

Оценка (3.12) называется априорной оценкой погрешности и позволяет оценить погрешность к-го приближения, не проведя вычислений, используя, нормы и . Также при заданной точности вычисления  можно определить необходимое число итераций из формулы .

Теорема 3.3 [3]. Пусть , тогда имеет место неравенство

.

Доказательство.

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

х=+х. (3.13)

Тогда для к-го приближения имеем

х^(к)=+х^(к-1). (3.14)

Из (3.13) и (3.14) получим

х^(к)-х=(х^(к-1)-х). (3.15)

Прибавим к левой и правой части этого равенства х^(к-1) и тогда имеем

х^(к-1)-х= х^(к-1)-х^(к)+(х^(к-1)-х). Откуда

. (3.16)

Из (3.15) получим

, (3.17)

тогда из (3.16) и (3.17) имеем

, (3.18)

что и требовалось доказать.

Оценка (3.18) называется апостериорной оценкой погрешности, так как её получают по известной и вычисленным приближениям х^(к-1) и х^(к).

3.2. Метод Зейделя

Метод Зейделя [3,4,9,11]представляет собой некоторую модификацию метода простой итерации. Основная идея метода заключается в том, что при вычислении (к+1)-го приближения неизвестной x_i учитываются уже вычисленные ранее (к+1)-ые приближения неизвестных x_1, x₂, …, x_n.

Пусть имеется приведенная линейная система

x_i=_i+ , (i=1, 2, …, n).

Выберем произвольно начальные приближения

.

Далее, предполагая, что к-ые приближения неизвестных вычислены, построим формулы для (к+1)-го приближения:

,

,

………………………………….

,

………………………………….

, (k=0, 1, 2,…).

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

,

_ii=0, k=0, 1, 2, …

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

для всех ;

где 0<<1.

Отметим, что теорема 3.1 и следствия 3.1 и 3.2 верны и для метода Зейделя.

Формулы для оценки погрешности метода Зейделя следующие [3]:

а) по m – норме

где

,

б) по l – норме

,

где

.