Итерационные методы решения СЛАУ

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

Особенность прямых методов состоит в том, что вычисления в них всегда проводятся точно, например, с использованием целых чисел, но при этом эти методы трудно применимы для вычисления решений для больших систем. К прямому методу относится, например, метод Крамера.

Ниже подробно рассмотрены итерационные методы решения СЛАУ.

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

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

Процесс вычисления одного столбца называется итерацией.

Различают несколько основных способов итерационного решения СЛАУ:

• Метод Гаусса-Зейделя;
• Метод Якоби.

Метод Якоби (метод простых итераций СЛАУ)

Рассмотрим систему уравнений, с коэффициентами, которые можно записать в виде матрицы:

$A=\left(\begin{array}{cccc} a_{11} & a_{12} & … & a_{1n} \\ a_{21} & a_{22} & … & a_{2n} \\ … & … & … & … \\ a_{n1} & a_{n2} & … & a_{nn} \\ \end{array}\right)$

Саму же систему уравнений можно записать в виде равенства $A \cdot X = F$, где $X$ — вектор-столбец собственных значений системы, а $F$ — вектор-столбец свободных членов.

Метод состоит в том, чтобы в каждом уравнении системы выразить соответственно $x_1, x_2,…, x_n$ и затем получить новую матрицу $B$, у которой элементы главной диагонали принимают нулевые значения.

В общем виде формула для вычисления корней уравнений записывается так: $\overrightarrow{x}= B\overrightarrow{x} + \overrightarrow{g}$

Добиться такого вида от системы можно следующими способами:

$B= E – D^{-1}A=D^{-1}(D-A), \overrightarrow{g} = D^{-1}\overrightarrow{b};$

$B=-D^{-1}(L+U)=-D^{-1}(A-D), \overrightarrow{g} = D^{-1}\overrightarrow{b};$

$D^{-1}_{ii}=\frac{1}{D_{ii}}, D_{ii}≠0, i=1,2,…, n$.

Здесь $D$ — матрица, у которой нулевые все элементы, кроме элементов на главной диагонали, а на главной диагонали находятся соответствующие элементы матрицы $A$. Матрицы $U$ и $L$ означают верхнетреугольную матрицу и нижнетреугольную соответственно; их значимые элементы соответствуют частям матрицы $A$. Буквой $Е$ же обозначается единичная матрица соответствующей размерности.

Процедура нахождения корней тогда запишется так:

$\overrightarrow{x}^{(k+1)}= B\overrightarrow{x}^{(k)} + \overrightarrow{g}$

Для конкретного элемента она будет выглядеть так:

$x_{i}^{k+1}=\frac{1}{a_ii}(b_i - \sum\limits_{i≠j} a_ij\cdot x_j^(k)\left(1\right)$, где $i=1,2,…, n$

буквой $(k)$ во всех формулах выше обозначается номер итерации, сама же формула $(1)$ называется рекуррентной.

Окончание вычисления происходит в том случае, если разница между вычислениями в двух соседних итераций составляет не более чем $ε_1$:

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

В упрощённой форме условие окончания итераций выглядит как $||x^{(n+1)}-x^{(n)}||$

Порядок решения СЛАУ методом Якоби такой:

1. Приведение системы уравнений к виду, в котором на каждой строчке выражено какое-либо неизвестное значение системы.
2. Произвольный выбор нулевого решения, в качестве него можно взять вектор-столбец свободных членов.
3. Производим подстановку произвольного нулевого решения в систему уравнений, полученную под пунктом 1.
4. Осуществление дополнительных итераций, для каждой из которых используется решение, полученное на предыдущем этапе.

Метод Гаусса-Зейделя

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

$(L + D) \cdot \overrightarrow{x} = -U\overrightarrow{x} + \overrightarrow{b}$

Сами итерации в методе Гаусса-Зейделя производятся по формуле:

$(L +D)\overrightarrow{x}^{(k+1)}=-U\overrightarrow{x}^{(k)} + \overrightarrow{b}$

Метод Гаусса-Зейделя похож на метод Якоби, но здесь полученные значения переменных используются не исключительно для следующей итерации, а сразу для следующего вычисления значения $x$.