Описание метода простых итераций.

Вернемся теперь к решению системы линейных уравнений, преобразованной к виду (9.1).

Решить систему - значит найти неподвижную точку Х такую, что если подставить ее координаты в правые части уравнений (9.1), то получим ту же точку Х. Для поиска неподвижной точки сжимающего отображения мы, как обычно, построим рекуррентную последовательность векторов по следующему правилу:

Х₀-произвольный, Х_k+1 = А Х_k + В (9.2)

После построения последовательности векторов посмотрим, сходится ли построенная последовательность. Если да, то она сходится обязательно к решению системы (9.1).

Упражнение 9.3. Докажите.

Сходится последовательность или нет – зависит от матрицы А и начального вектора Х₀.

ТЕОРЕМА. Пусть задана система линейных уравнений (9.1) и построена рекуррентная последовательность векторов по правилу (9.2). Если для матрицы А хотя бы одно из чисел q₁,q₂,q_¥ меньше 1, то мы можем утверждать, что последовательность векторов, которую мы построили, обязательно сходится к решению со скоростью геометрической прогрессии со знаменателем q.

Доказательство опирается на принцип сжимающих отображений и аналогично доказательству в одномерном случае, изложенному в самом начале работы.

Упражнение 9.4. Проведите самостоятельно доказательство теоремы.

Из теоремы вытекает соответствующий метод решения системы. Заметим, что при выполнении ограничений на элементы матрицы А последовательность построенных по правилу (9.2) векторов сходится к решению независимо от выбора вектора Х₀, но обычно в качестве Х₀ выбирают вектор В. Это можно объяснить тем, что если взять Х₀=0, то на следующем шаге получится вектор В, т.е. он как бы лежит на пути от 0 к решению системы. Повторим, что у метода итераций есть преимущество перед всеми другими методами: это устойчивый метод.

Условие окончания вычислений.

Замечание. Если ответ надо получить с заданной точностью e, то вычисления прекращают на том этапе вычислений, когда начнет выполняться неравенство:

, причем в качестве величины q берут наименьшую величину из трех вычисленных норм матрицы A, а в качестве нормы пространства Rⁿ- соответствующую норму.

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

Приведение исходной системы к нужному виду.

Из различных вариантов приведения системы к виду, пригодному для применения метода простых итераций, мы отметим два простых случая, которые нередко встречаются на практике.

Случай диагонального преобладания.

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

Пример1:

5x₁-x₂+2x₃=13 x₁=0.2x₂-0.4x₃ +2.6

2x₁-10x₂+4x₃=0 ó x₂=0.2x₁+0.4x₃ +0

x₁+2x₂+20x₃=100 x₃=-0.05x₁-0.1x₂ +5

Аналогичным образом поступают и тогда, когда диагонального преобладания можно добиться перестановкой уравнений.