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

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

Приведем систему (1) к равносильной ей системе вида:

(7)

или в сокращенной записи , (8)

О системе (7) говорят, что она «приведена к нормальному виду».

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

F: , , (9)

преобразующее точку (x₁, x₂, …, x_n) п -мерного векторного пространства в точку (у ₁, у₂, …,у_n) того же пространства. Используя отображение (9) и выбрав начальную точку , можно построить итерационную последовательность точек п -мерного пространства (аналогично методу простой итерации для уравнения x = f (x)):

(10)

Если отображение F является сжимающим, то эта последовательность сходится и ее предел является решением системы (7), и тем самым исходной системы.

Рассмотрим условия, при которых отображение (9) является сжимающим. Решение этого вопроса зависит от способа метризации пространства.

Пусть (x₁, x₂, …, x_n) и (у ₁, у₂, …,у_n) – две точки п -мерного пространства. Для применения метода итераций систему линейных уравнений удобно «погрузить» в пространство с одной из следующих метрик:

1) ρ₁( , ) =

2) ρ₂( , ) =

3) ρ₃( , ) =

Отображение (9) будет сжимающим, если выполняется хотя бы одно из условий:

а) в пространстве с метрикой ρ₁: (11)

б)в пространстве с метрикой ρ₂: (12)

в) в пространстве с метрикой ρ₃: (13)

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

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

1. Привести исходную систему к системе с преобладающими диагональными коэффициентами и разделить каждое уравнение на соответствующий диагональный коэффициент.

2. Проверить выполнение условий сходимости.

3. Выбрать метрику, для которой выполняется условие сходимости итерационного процесса.

4. Реализовать итерационный процесс (за начальное приближение обычно берется столбец свободных членов)

Для применения метода итераций система (1) сначала должна быть переписана в виде (7). При этом гарантией сходимости итерационного процесса может служить выполнение хотя бы одного из достаточных условий (11) – (13) при погружении системы в пространство с одной из трех рассмотренных выше метрик.

Для обеспечения условий сходимости нужно получить систему (7) так, чтобы коэффициенты при неизвестных в правой части системы были существенно меньше единицы. Этого можно достичь, если исходную систему (1) с помощью равносильных преобразований привести к системе, у которой абсолютные величины коэффициентов, стоящие на главной диагонали, больше абсолютных величин каждого из других коэффициентов при неизвестных в соответствующих уравнениях (такую систему называют системой с преобладающими диагональными коэффициентами). Если теперь разделить все уравнения на соответствующие диагональные коэффициенты и выразить из каждого уравнения неизвестное с коэффициентом, равным единице, будет получена система вида (7), у которой все < 1.

Выполнение этого условия необходимо, но недостаточно для удовлетворения условий сжимаемости. Если после указанных действий ни одно из условий не выполняется, следует возвратиться к исходной системе и попытаться выполнить преобразования так, чтобы добиться лучшего эффекта.

Результатом установления одного из условий является получение значения q, которое затем применяется в формуле оценки точности k -го приближения. После того как сходимость установлена, можно приступать к выполнению вычислений. Схема алгоритма метода итераций для систем уравнений аналогична схеме метода итераций для одного уравнения. За начальное приближение берется обычно столбец свободных членов системы (7). Итерационный процесс прекращается при достижении заданной точности результата ε:

(14)

где ρ – метрика, по которой была установлена сходимость и получено соответствующее значение q.