3.1. Треугольные системы
Прежде всего рассмотрим решение треугольной системы.
Рассмотрим частный случай для системы \(\mathbf{L}\mathbf{x}=\mathbf{b}\), где \(\mathbf{L}\) – нижнетреугольная матрица размера 4
\[\begin{split}\begin{bmatrix}
L_{11} & 0 & 0 & 0 \\
L_{21} & L_{22} & 0 & 0 \\
L_{31} & L_{32} & L_{33} & 0 \\
L_{41} & L_{42} & L_{43} & L_{44}
\end{bmatrix}
\begin{bmatrix}
x_1 \\ x_2 \\ x_3 \\ x_4
\end{bmatrix}
=
\begin{bmatrix}
b_1 \\ b_2 \\ b_3 \\ b_4
\end{bmatrix}\end{split}\]
Эта система может быть решена итерационно, начиная с \(x_1\)
\[\begin{split}\begin{split}
x_1 &= \frac{b_1}{L_{11}}\\
x_2 &= \frac{b_2 - L_{21}x_1}{L_{22}}\\
x_3 &= \frac{b_3 - (L_{31}x_1 + L_{32}x_2)}{L_{33}}\\
x_4 &= \frac{b_4 - (L_{41}x_1 + L_{42}x_2 + L_{43}x_3)}{L_{44}}
\end{split}\end{split}\]
Алгоритм, который здесь применён называют прямой подстановкой (forward substitution).
Аналогично, система \(\mathbf{U}\mathbf{x}=\mathbf{b}\), где \(\mathbf{U}\) – верхнетреугольная матрица, может быть решена алгоритмом обратной подстановки (backward substitution). Например, для случая \(\mathbf{U}\) размера 4
\[\begin{split}\begin{bmatrix}
U_{11} & U_{12} & U_{13} & U_{14} \\
0 & U_{22} & U_{23} & U_{24} \\
0 & 0 & U_{33} & U_{34} \\
0 & 0 & 0 & U_{44}
\end{bmatrix}
\begin{bmatrix}
x_1 \\ x_2 \\ x_3 \\ x_4
\end{bmatrix}
=
\begin{bmatrix}
b_1 \\ b_2 \\ b_3 \\ b_4
\end{bmatrix}\end{split}\]
алгоритм обратной подстановки начинается с \(x_4\) и включает следующие шаги
\[\begin{split}\begin{split}
x_4 &= \frac{b_4}{U_{44}}\\
x_3 &= \frac{b_3 - U_{34}x_4}{U_{33}}\\
x_2 &= \frac{b_2 - (U_{23}x_3 + U_{24}x_4)}{U_{22}}\\
x_1 &= \frac{b_1 - (U_{12} x_2 + U_{13}x_3 + U_{14}x_4)}{U_{11}}.
\end{split}\end{split}\]
Алгоритм постановки показывает следующее утверждение.
Утверждение 3.1
Треугольная матрица вырождена тогда и только тогда, когда хотя бы один ёё диагональнй элемент нулевой.