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

Запишем исходную систему (3.4) в следующем виде:

(3.13)

или сокращенно

(3.14)

где .

Правая часть (3.14) определяет отображение F

, (3.15)

преобразующее точку n-мерного векторного пространства в точку того же пространства. Используя систему (3.4) и выбрав начальную точку , можно построить итерационную последовательность точек n-мерного пространства (аналогично методу простой итерации для скалярного уравнения ):

(3.16)

Оказывается, что при определенных условиях последовательность (3.16) сходится и ее предел является решением системы (3.13). Предваряя обсуждение данных условий, напомним необходимые сведения из математического анализа.

Определение 3.4. Функцию , определяющую расстояние между точками x и y множества X, называют метрикой, если выполнены следующие условия:

1) ³ 0,

2) = 0 тогда и только тогда, когда x = y,

3) =,

4) .

Определение 3.5. Множество с введенной в нем метрикой r становится метрическим пространством.

Определение 3.6. Последовательность точек метрического пространства называется фундаментальной, если для любого существует такое число , что для всех m,n > N выполняется неравенство .

Определение 3.7. Пространство называется полным, если в нем любая фундаментальная последовательность сходится.

Пусть F - отображение, действующее в метрическом пространстве Е с метрикой r, x и y - точки пространства Е, а Fx, Fy - образы этих точек.

Определение 3.8. Отображение F пространства E в себя называется сжимающим отображением, если существует такое число a, 0<a<1, что для любых двух точек x, y ÎE выполняется неравенство

. (3.17)

Определение 3.9. Точка x называется неподвижной точкой отображения F, если Fx=x.

Аналогично одномерному случаю можно доказать теорему о достаточном условии сходимости итерационного процесса в n-мерном пространстве. (Доказательство теоремы приводится практически во всех учебниках, посвященных численным методам (например, [1]))

Теорема. 3.1. Если F - сжимающее отображение, определенное в

полном метрическом пространстве, то существует единственная неподвижная точка x, такая, что x=Fx. При этом итерационная последовательность, построенная для отображения F с любым начальным членом , сходится к x.

В ходе доказательства данной теоремы показывается, что

. (3.18)

Из (3.18), приняв k-ое приближение за нулевое, получаем полезное для приложений неравенство:

. (3.19)

Рассмотрим условия, при которых отображение (3.15) будет сжимающим. Как следует из определения (3.17), решение данного вопроса зависит от способа метризации данного пространства. Обычно при решении систем линейных уравнений используют одну из следующих метрик:

, (3.20)

, (3.21)

. (3.22)

Для того чтобы отображение F, заданное в метрическом пространстве уравнениями (3.15), было сжимающим, достаточно выполнения одного из следующих условий:

1) в пространстве с метрикой :

, (3.23)

2) в пространстве с метрикой :

, (3.24)

3) в пространстве с метрикой :

. (3.25)

Для установления момента прекращения итераций при достижении заданной точности может быть использована, например, формула, следующая из (3.19):

. (3.26)

Алгоритм решения системы методом итераций реализуется следующей последовательностью действий:

1) Привести систему (3.4) к виду с преобладающими диагональными коэффициентами.