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

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

Условие сходимости итерационного процесса. Метод Якоби. Метод Зейделя

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

Рассматривается система линейных алгебраических уравнений

Ax = b

Для применения итерационных методов система должна быть приведена к эквивалентному виду

x=Bx+d.

Затем выбирается начальное приближение к решению системы уравнений и находится последовательность приближений к корню.

Для сходимости итерационного процесса достаточно, чтобы было выполнено условие (норма матрицы). Критерий окончания итераций зависит от применяемого итерационного метода.

Метод Якоби.

Самый простой способ приведения системы к виду, удобному для итерации, состоит в следующем:

Из первого уравнения системы выразим неизвестное x₁, из второго уравнения системы выразим x₂, и т. д.

В результате получим систему уравнений с матрицей B, в которой на главной диагонали стоят нулевые элементы, а остальные элементы вычисляются по формулам:

Компоненты вектора d вычисляются по формулам:

Расчетная формула метода простой итерации имеет вид:

или в покоординатной форме записи выглядит так:

Критерий окончания итераций в методе Якоби имеет вид:

Если , то можно применять более простой критерий окончания итераций

Пример 1.Решение системы линейных уравнений методом Якоби.

Пусть дана система уравнений:

Требуется найти решение системы с точностью

Приведем систему к виду удобному для итерации:

Выберем начальное приближение, например,

- вектор правой части.

Тогда первая итерация получается так:

Аналогично получаются следующие приближения к решению.

Найдем норму матрицы B.

Будем использовать норму

Так как сумма модулей элементов в каждой строке равна 0.2, то , поэтому критерий окончания итераций в этой задаче

Вычислим нормы разностей векторов:

Так как заданная точность достигнута на четвертой итерации.

Ответ: x₁ = 1.102, x₂ = 0.991, x₃ = 1.011

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

Метод можно рассматривать как модификацию метода Якоби. Основная идея состоит в том, что при вычислении очередного (n+1)-го приближения к неизвестному x_i при
i >1 используют уже найденные (n+1)-е приближения к неизвестным x₁, x₂, ..., x_{i - 1}, а не n-ое приближение, как в методе Якоби.

Расчетная формула метода в покоординатной форме записи выглядит так:

Условия сходимости и критерий окончания итераций можно взять такими же, как в методе Якоби.

Пример 2. Решение систем линейных уравнений методом Зейделя.

Рассмотрим параллельно решение 3-х систем уравнений:

Приведем системы к виду удобному для итераций:

Заметим, что условие сходимости выполнено только для первой системы. Вычислим 3 первых приближения к решению в каждом случае.

1-ая система:

Точным решением будут значения: x₁ = 1.4, x₂ = 0.2. Итерационный процесс сходится.

2-ая система:

Видно, что итерационный процесс расходится.

Точное решение x ₁ = 1, x ₂ = 0.2.

3-я система:

Видно, что итерационный процесс зациклился.

Точное решение x ₁ = 1, x ₂ = 2.

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

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

Если A – симметричная и положительно определенная матрица, то систему уравнений часто приводят к эквивалентному виду:

x = x -τ (Ax - b), τ – итерационный параметр.

Расчетная формула метода простой итерации в этом случае имеет вид:

x ⁽ⁿ⁺¹⁾ = x ⁿ - τ (Ax ⁽ⁿ⁾ - b).

Здесь

B = E - τ A

и параметр τ > 0 выбирают так, чтобы по возможности сделать минимальной величину

Пусть λ_min и λ_max – минимальное и максимальное собственные значения матрицы A. Оптимальным является выбор параметра

В этом случае принимает минимальное значение равное:

Пример 3. Решение систем линейных уравнений методом простой итерации. (в MathCAD)

Пусть дана система уравнений Ax = b

1. Для построения итерационного процесса найдем собственные числа матрицы A:

- используется встроенная функция для нахождения собственных чисел.

2. Вычислим итерационный параметр и проверим условие сходимости

- условие сходимости выполнено.

3. Возьмем начальное приближение - вектор x0, зададим точность 0.001 и найдем начальные приближения по приведенной ниже программе:

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

Замечание. Если в программе возвращать матрицу rez, то можно просмотреть все найденные итерации.