Итерационные методы решения СЛАУ: метод Якоби, Зейделя, простой итерации

В данной статье мы расскажем общие сведения об итерационных методах решения СЛАУ, познакомим с методом Зейделя и Якоби, а также приведем примеры решения систем линейных уравнений при помощи данных методов.

Общие сведения об итерационных методах или методе простой итерации

Определение 1

Метод итерации — это численный и приближенный метод решения СЛАУ.

Суть: нахождение по приближённому значению величины следующего приближения, которое является более точным. Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня $x_{0}$ .

Замечание 1

Рассмотрим систему $A x = b$ .

Чтобы применить итерационный метод, необходимо привести систему к эквивалентному виду $x = B x + d$ . Затем выбираем начальное приближение к решению СЛАУ $x^{(0)} = (x_{1}^{0}, x_{2}^{0}, . . . x_{m}^{0})$ и находим последовательность приближений к корню.

Для сходимости итерационного процесса является достаточным заданное условие $| | В | | < 1$ . Окончание итерации зависит от того, какой итерационный метод применили.

Метод Якоби

Определение 2

Метод Якоби — один из наиболее простых методов приведения системы матрицы к виду, удобному для итерации: из 1-го уравнения матрицы выражаем неизвестное $x_{1}$ , из 2-го выражаем неизвестное $x_{2}$ и т.д.

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

$b_{i j} = - a_{i j} / a_{i i}, i, j = 1, 2. . ., n$

Элементы (компоненты) вектора $d$ вычисляются по следующей формуле:

$d_{i} = b_{i} / a_{i i}, i = 1, 2, . . ., n$

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

$x^{(n + 1)} = B x^{(x)} + d$

Матричная запись (координатная):

$x_{i}^{(n + 1)} = b_{i 1} x_{1}^{n} + b_{i 2}^{@ 2} x_{2}^{(n)} + . . . + b$

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

$| | x^{(n + 1)} - x^{(n)} | | < ε_{1}$ , где $ε_{1} = \frac{1 - | | B | |}{| | B | |} ε$

В случае если $B < 1 / 2$ , то можно применить более простой критерий окончания итераций:

$| | x^{(n + 1)} - x^{(n)} | | < ε$

Пример 1

Решить СЛАУ методом Якоби:

${\begin{cases} 10 x_{1} + x_{2} - x_{3} = 11 \\ x_{1} + 10 x_{2} - x_{3} = 10 \\ - x_{1} + x_{2} + 10 x_{3} = 10 \end{cases}$

Решение

Необходимо решить систему с показателем точности $ε = 10^{- 3}$ .

Приводим СЛАУ к удобному виду для итерации:

${\begin{cases} x_{1} = - 0, 1 x_{2} + 0, 1 x_{3} + 1, 1 \\ x_{2} = - 0, 1 x_{1} + 0, 1 x_{3} + 1 \\ x_{3} = 0, 1 x_{1} - 0, 1 x_{2} + 1 \end{cases}$

Выбираем начальное приближение, например: $x^{(0)} = (\begin{array}{l} 1, 1 \\ 1 \\ 1 \end{array})$ — вектор правой части.

В таком случае, первая итерация имеет следующий внешний вид:

$x_{1}^{(1)} = - 0, 1 \times 1 + 0, 1 \times 1 + 1, 1 = 1, 1 x_{2}^{(1)} = - 0, 1 \times 1, 1 + 0, 1 + 1 = 0, 99 x_{3}^{(1)} = 0, 1 \times 1, 1 - 0, 1 \times 1 + 1 = 1, 01$

Аналогичным способом вычисляются приближения к решению:

$x^{(2)} = (\begin{array}{l} 1, 102 \\ 0, 991 \\ 1, 011 \end{array})$ , $x^{(3)} = (\begin{array}{l} 1, 102 \\ 0, 9909 \\ 1, 0111 \end{array})$ , $x^{(4)} = (\begin{array}{l} 1, 10202 \\ 0, 99091 \\ 1, 01111 \end{array})$

Находим норму матрицы $В$ , для этого используем норму $| | B | |_{\infty}$ .

Поскольку сумма модулей элементов в каждой строке равна 0,2, то $| | B | |_{\infty} = 0, 2 < 1 / 2$ , поэтому можно вычислить критерий окончания итерации:

$| | x^{(n + 1)} - x^{(n)} | | < ε$

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

$| | x^{(3)} - x^{(2)} | |_{\infty} = 0, 002$ , $| | x^{(4)} - x^{(3)} | |_{\infty} = 0, 00002$ .

Поскольку $| | x^{(4)} - x^{(3)} | |_{\infty} < ε$ , то можно считать, что мы достигли заданной точности на 4-ой итерации.

Ответ:

$x_{1} = 1, 102$ ; $x_{2} = 0, 991$ ; $x_{3} = 1, 011$ .

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

Определение 3

Метод Зейделя — метод является модификацией метода Якоби.

Суть: при вычислении очередного $(n + 1) - г о$ приближения к неизвестному $x i$ при $i > 1$ используют уже найденные $(n + 1) - е$ приближения к неизвестным $x 1, x 2, . . ., x i — 1,$ а не $n - о е$ приближение, как в методе Якоби.

Матричная запись:

$x_{i}^{(n + 1)} = b_{i 1} x_{1}^{(n + 1)} + b_{i 2} x_{2}^{(n + 1)} + . . . + b_{i, i - 1} x_{i - 2}^{(n + 1)} + b_{i, i + 1} x_{i + 1}^{(n)} +$

$+ . . . + b_{i m} x_{m}^{(n)} + d_{i}$

$i = 1, 2, . . . m . . .$

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

Пример 2

Решить СЛАУ методом Зейделя. Пусть матрица системы уравнений А — симметричная и положительно определенная. Следовательно, если выбрать начальное приближение, метод Зейделя сойдется. Дополнительных условий на малость нормы некоторой матрицы не накладывается.

Решение

Решим $3$ системы уравнений:

${\begin{cases} 2 x_{1} + x_{2} = 3 \\ x_{1} - 2 x_{2} = 1 \end{cases}$ , ${\begin{cases} x_{1} + 2 x_{2} = 3 \\ 2 x_{1} - x_{2} = 1 \end{cases}$ , ${\begin{cases} 2 x_{1} - 0, 5 x_{2} = 3 \\ 2 x_{1} + 0, 5 x_{2} = 1 \end{cases}$

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

${\begin{cases} x_{1}^{(n + 1)} = - 0, 5 x_{2}^{(n)} + 1, 5 \\ x_{2}^{(n + 1)} = 0, 5 x_{1}^{(n + 1)} + 0, 5 \end{cases}$ , ${\begin{cases} x_{1}^{(n + 1)} = - 2 x_{2}^{(n)} + 3 \\ x_{2}^{(n + 1)} = 2 x_{1}^{(n + 1)} - 1 \end{cases}$ , ${\begin{cases} 2 x_{1} - 0, 5 x_{2} = 3 \\ 2 x_{1} + 0, 5 x_{2} = 1 \end{cases}$ .

Отличительная особенность, условие сходимости выполнено только для первой системы:

$| | B | | < 1$

Вычисляем 3 первых приближения к каждому решению:

1-ая система: $x^{(0)} = (\begin{array}{l} 1, 5 \\ - 0, 5 \end{array})$ , $x^{(1)} = (\begin{array}{l} 1, 75 \\ 0, 375 \end{array})$ , $x^{(2)} = (\begin{array}{l} 1, 3125 \\ 0, 1563 \end{array})$ , $x^{(3)} = (\begin{array}{l} 1, 4219 \\ 0, 2109 \end{array})$

Решение: $x_{1} = 1, 4$ , $x_{2} = 0, 2$ . Итерационный процесс сходится.

2-ая система: $x^{(0)} = (\begin{array}{l} 3 \\ - 1 \end{array})$ , $x^{(1)} = (\begin{array}{l} 5 \\ 9 \end{array})$ , $x^{(2)} = (\begin{array}{l} - 15 \\ - 31 \end{array})$ , $x^{(3)} = (\begin{array}{l} 65 \\ 129 \end{array})$

Итерационный процесс разошелся.

Решение: $x_{1} = 1, x_{2} = 2$

3-я система: $x^{(0)} = (\begin{array}{l} 1, 5 \\ 2 \end{array})$ , $x^{(1)} = (\begin{array}{l} 2 \\ - 6 \end{array})$ , $x^{(2)} = (\begin{array}{l} 0 \\ 2 \end{array})$ , $x^{(3)} = (\begin{array}{l} 0 \\ 2 \end{array})$

Итерационный процесс зациклился.

Ответ: $x_{1} = 1, x_{1} = 2$

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

Если $А$ — симметричная и положительно определенная, то СЛАУ приводят к эквивалентному виду:

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

Расчетная формула имеет следующий внешний вид:

$x^{(n + 1)} = x^{(n)} - τ (A x^{n} - b) .$

Здесь $B = E - τ A$ и параметр $τ > 0$ выбирают таким образом, чтобы по возможности сделать максимальной величину $| | B | |_{2}$ .

Пусть $λ m i n$ и $λ m a x$ - максимальные и минимальные собственные значения матрицы $А$ .

$τ = 2 / (λ m i n + λ m a x)$ - оптимальный выбор параметра. В этом случае $| | B | |_{2}$ принимает минимальное значение, которое равняется $(λ m i n + λ m a x) / (λ m i n - λ m a x)$ .