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

22 августа 2023
6 минут
9 648

Преподаватель математики и информатики. Кафедра бизнес-информатики Российского университета транспорта

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

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

Определение 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^{n}}_{1} + {b^{}}_{i 2} {x^{(n)}}_{2} + . . . + b$

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

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

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

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

Пример 2

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

$\{\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{matrix} 1, 1 \\ 1 \\ 1 \end{matrix})$ — вектор правой части.

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

${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{matrix} 1, 102 \\ 0, 991 \\ 1, 011 \end{matrix})$ , $x^{(3)} = (\begin{matrix} 1, 102 \\ 0, 9909 \\ 1, 0111 \end{matrix})$ , $x^{(4)} = (\begin{matrix} 1, 10202 \\ 0, 99091 \\ 1, 01111 \end{matrix})$

Находим норму матрицы $В$ , для этого используем норму ${||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,01 1$ .

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

Определение 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 . . .$

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

Пример 3

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

Как решать?

Решим $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{matrix} 1, 5 \\ - 0, 5 \end{matrix})$ , $x^{(1)} = (\begin{matrix} 1, 75 \\ 0, 375 \end{matrix})$ , $x^{(2)} = (\begin{matrix} 1, 3125 \\ 0, 1563 \end{matrix})$ , $x^{(3)} = (\begin{matrix} 1, 4219 \\ 0, 2109 \end{matrix})$

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

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

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

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

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

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

Решение: $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)$ .