!!§!! Вспомогательный раздел к разделу
☞
((:algebra2:linearsystems#матричный_формализм СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ)).
Сложность --- повышенная. Предполагается понимание операции ((:algebra2#умножение_матриц умножения)) на ((:algebra2#элементарных_преобразований матрицы элементарных преобразований)).
----
~~TOC~~
== Матричный формализм метода Гаусса==
===Явное выражение коэффициентов преобразованной системы==
Выделим из полной системы уравнений
$$
\left\{
\begin{array}{lllll}
a_{11}x_1 &+a_{12}x_2&+ \ldots&+a_{1n}x_n &=b_1,\\
a_{21}x_1 &+a_{22}x_2&+ \ldots&+a_{2n}x_n &=b_2,\\
\dots & & & \dots & \\
a_{m1}x_1 &+a_{m2}x_2&+ \ldots&+a_{mn}x_n &=b_m.
\end{array} \right.
$$
ее подсистему, состоящую из первых $ k_{} $ уравнений
$$
\left\{
\begin{array}{lllll}
a_{11}x_1 &+a_{12}x_2&+ \ldots&+a_{1n}x_n &=b_1,\\
a_{21}x_1 &+a_{22}x_2&+ \ldots&+a_{2n}x_n &=b_2,\\
\dots & & & \dots & \\
a_{k1}x_1 &+a_{k2}x_2&+ \ldots&+a_{kn}x_n &=b_k.
\end{array} \right.
$$
Применим к этой подсистеме прямой ход метода Гаусса. Напомним, что он заключается в использовании
((:algebra2:linearsystems#исключение_переменных элементарных преобразований)), нацеленных на последовательное исключение неизвестных $ x_1,\dots,x_{k} $. Предположим, что в ходе этих элементарных преобразований удалось привести подсистему к трапециевидной форме
$$
\left\{
\begin{array}{llllllrl}
a_{11}x_1 +&a_{12}x_2&+ \ldots& +a_{1k}x_k&
+a_{1 ,k +1}x_{k+1}&+ \ldots + & a_{1n}x_n &=b_1,\\
&a_{22}^{[1]}x_2&+ \ldots& +a_{2k}^{[1]} x_k&
+a_{2 ,k+1}^{[1]} x_{k+1}&+ \ldots + & a_{2n}^{[1]} x_n &=b_2^{[1]},\\
& & \ddots & & & & & \dots \\
& & & a_{kk}^{[k-1]}x_{k} &
+ a_{k ,k +1}^{[k-1]}x_{k+1}& + \ldots + &
a_{k ,n}^{[k-1]}x_n &=b_{k}^{[k-1]},
\end{array} \right.
$$
т.е. по крайней мере, подсистема является совместной. Тогда совершенно очевидно, что и исходная система в ходе тех же элементарных преобразований преобразуется к виду, у которого первые $ k_{} $ уравнений будут совпадать с только что приведенными. Нас интересует последнее уравнение получившейся подсистемы, а именно
$$
a_{kk}^{[k-1]}x_{k}
+ a_{k ,k +1}^{[k-1]}x_{k+1} + \ldots + a_{k ,n}^{[k-1]}x_n =b_{k}^{[k-1]} \ .
$$
**Задача.** Найти явное выражение коэффициентов последнего уравнения в виде функций коэффициентов исходной системы.
Предположим сначала, что коэффициент при $ x_{k} $ отличен от нуля:
$$ a_{kk}^{[k-1]} \ne 0 \ , $$
тогда из последнего уравнения можно однозначно выразить $ x_{k} $ в виде функции
$ x_{k+1}, \dots, x_n $:
$$
x_{k} =- \frac{a_{k ,k +1}^{[k-1]}}{a_{kk}^{[k-1]}}x_{k+1} - \ldots - \frac{a_{k ,n}^{[k-1]}}{a_{kk}^{[k-1]}} x_n +\frac{b_{k}^{[k-1]}}{a_{kk}^{[k-1]}} \ .
$$
С другой стороны, переписав подсистему в виде:
$$
\left\{ \begin{array}{rrrr}
a_{11}x_1+\dots+a_{1k}x_{k}&=&b_1-&
(a_{1,k+1}x_{k+1}+
\dots +a_{1n}x_n), \\
\dots & & & \\
a_{k1}x_1+\dots+a_{kk}x_{k}
&=&b_k-&(a_{k,k+1}x_{k+1}+\dots +a_{kn}x_n).
\end{array}
\right.
$$
мы можем попытаться выразить неизвестные $ x_1,\dots,x_k $ через оставшиеся неизвестные $ x_{k+1},\dots,x_n $, воспользовавшись ((:algebra2:linearsystems#формулы_крамера формулами Крамера)).
Если определитель матрицы в левой части отличен от нуля:
$$
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1k}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{kk}
\end{array}
\right|\ne 0 \ ,
$$
то система однозначно разрешима относительно $ x_1,\dots,x_k $. Нас интересует выражение для $ x_k $:
$$
x_k
=\frac{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} &\left[ b_1-(a_{1,k+1}x_{k+1}+\dots +a_{1n}x_n) \right]
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & \left[ b_k-
(a_{k,k+1}x_{k+1}+\dots +a_{kn}x_n)
\right]
\end{array}
\right|
}{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1k}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{kk}
\end{array}
\right|
}
$$
Или, разложив последний столбец определителя в числителе в сумму столбцов, воспользуемся свойством
5
определителя (см.
☞
((:algebra2:dets#элементарные_свойства_определителя ЗДЕСЬ)) ):
$$
x_k=-
\frac{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1,k+1}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{k,k+1}
\end{array}
\right|
}{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1k}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{kk}
\end{array}
\right|
}x_{k+1} - \dots -
\frac{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1n}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{kn}
\end{array}
\right|
}{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1k}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{kk}
\end{array}
\right|
} x_n +
$$
$$
+
\frac{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & b_1
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & b_k
\end{array}
\right|
}{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1k}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{kk}
\end{array}
\right|
} \ .
$$
Итак, получено еще одно представление для $ x_{k} $ в виде функции $ x_{1},\dots,x_{k-1} $. Из единственности этого представления следует явное выражение коэффициентов уравнения из метода Гаусса:
$$
\frac{a_{k ,k +1}^{[k-1]}}{a_{kk}^{[k-1]}}=
\frac{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1,k+1}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{k,k+1}
\end{array}
\right|
}{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1k}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{kk}
\end{array}
\right|
},\dots, \frac{a_{k ,n}^{[k-1]}}{a_{kk}^{[k-1]}}=
\frac{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1n}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{kn}
\end{array}
\right|
}{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1k}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{kk}
\end{array}
\right|
},\
$$
$$
\frac{b_{k}^{[k-1]}}{a_{kk}^{[k-1]}} =
\frac{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & b_1
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & b_k
\end{array}
\right|
}{
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1k}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{kk}
\end{array}
\right|
} \ .
$$
Из последнего утверждения следует справедливость следующих равенств
$$
a_{kk}^{[k-1]}=L
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1k}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{kk}
\end{array}
\right|,\
a_{k ,k +1}^{[k-1]}=L
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1,k+1}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{k,k+1}
\end{array}
\right|,\ \dots,
$$
$$
a_{k ,n}^{[k-1]}=
L\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & a_{1n}
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & a_{kn}
\end{array}
\right|,\
b_{k}^{[k-1]}=L
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1} & b_1
\\
\dots &&&\dots \\
a_{k1} & \dots &a_{k,k-1} & b_k
\end{array}
\right| \ .
$$
при некотором множителе $ L_{} $. Утверждается, что
$$
L=1 \Bigg/
\left| \begin{array}{llll}
a_{11} & \dots &a_{1,k-1}
\\
\dots &&\dots \\
a_{k-1,1} & \dots &a_{k-1,k-1}
\end{array}
\right| \, .
$$
!!П!! **Пример.** Для системы л.у.
$$ \left\{
\begin{array}{rrrrr}
2\,x_1&+3\,x_2&+4\, x_3&-7\, x_4 =& 1, \\
3\,x_1&+2\,x_2&-3\,x_3&+x_4 =& 2, \\
-x_1&&+4\,x_3 &- x_4 =& -1, \\
7\,x_1&-x_2&+2\, x_3&+3\,x_4 =& 3.
\end{array}
\right.
$$
получить третье уравнение из прямого хода метода Гаусса.
**Решение.** Имеем:
$$
\frac{\left|
\begin{array}{rrr}
2&3&4 \\
3& 2&-3 \\
-1&0& 4
\end{array}
\right|}{\left|
\begin{array}{rr}
2&3 \\
3& 2&
\end{array}
\right|}x_3+
\frac{\left|
\begin{array}{rrr}
2&3&-7 \\
3& 2&1 \\
-1&0& -1
\end{array}
\right|}{\left|
\begin{array}{rr}
2&3 \\
3& 2&
\end{array}
\right|}
x_4
=
\frac{\left|
\begin{array}{rrr}
2&3&1 \\
3& 2&2 \\
-1&0& -1
\end{array}
\right|}{\left|
\begin{array}{rr}
2&3 \\
3& 2&
\end{array}
\right|}
\quad \iff \quad \frac{3}{5}\, x_3 +\frac{12}{5}\, x_4 =-\frac{1}{5} \, .
$$
!!Т!! **Теорема.** //Для того чтобы в прямом ходе метода Гаусса можно было последовательно (и без пропусков) исключить переменные//
$ x_1,x_2,\dots,x_k $ (//т.е.// $ j_{} $//-е уравнение имело коэффициент при// $ x_j $ //отличным от нуля//) //необходимо и достаточно чтобы все ((:algebra2:dets#миноры_и_алгебраические_дополнения главные миноры)) матрицы// $ A_{} $ //порядков от// $ 1_{} $ //до// $ k $ //были бы отличны от нуля//:
$$
a_{11} \ne 0,
\left|
\begin{array}{rr}
a_{11}&a_{12} \\
a_{21}&a_{22}
\end{array}
\right|\ne 0, \dots ,
\left| \begin{array}{llll}
a_{11} & a_{12} & \dots & a_{1k} \\
a_{21} & a_{22} & \dots & a_{2k} \\
\dots &&&\dots \\
a_{k1} & a_{k2} & \dots & a_{kk}
\end{array}
\right|\ne 0 \, .
$$
Материалы настоящего пункта имеют исключительно теоретическое значение --- никто не считает коэффициенты уравнений из метода Гаусса посредством определителей: накладно! Однако в следующем пункте полученные теоретические выводы будем постепенно превращать в конструктивные алгоритмы, которые востребованы в других задачах.
===Матричный формализм==
====LU-разложение матрицы==
Продолжим исследование метода Гаусса с точки зрения на систему линейных уравнений как на матричное уравнение
$$ AX= {\mathcal B} \ ; $$
снова ограничиваясь лишь случаем квадратной матрицы $ A_{} $. Напомним, что метод Гаусса состоит из двух стадий. Первая из них --- ((algebra2:linearsystems#исключение_переменных прямой ход)) --- фактически не задействовала сами неизвестные $ x_{1},\dots,x_n $: действия производились только над коэффициентами --- строками матрицы $ A_{} $ и элементами столбца правых частей $ {\mathcal B}_{} $.
!!П!! **Пример.** Решить систему л.у.
$$ \left\{
\begin{array}{rrrrr}
x_1&+2\,x_2&-11\, x_3&+2\, x_4 =&- 14, \\
3\,x_1 &+3\,x_2&+4\,x_3&-5\,x_4 =& 9, \\
5\,x_1&-7\,x_2 & +8\,x_3&+2\, x_4 =& 18, \\
7\,x_1&+8\,x_2&+3\, x_3&+4\,x_4 =& -2.
\end{array}
\right.
$$
**Решение.** Выпишем ((:algebra2:linearsystems#теорема_кронекера-капелли расширенную матрицу)) системы
$$
\left(
\begin{array}{rrrr|r}
1&2&-11&2 &- 14 \\
3&3&4&-5 & 9 \\
5&-7&8&2& 18 \\
7&8&3&4 & -2
\end{array}
\right)
$$
и будем выполнять ((:algebra2:rank#ранг_системы_строк_столбцов элементарные преобразования)) над ее строками:
$$
\rightarrow \quad
\left(
\begin{array}{rrrr|r}
1&2&-11&2 &- 14 \\
0&-3&37&-11 & 51 \\
0&-17&63&-8& 88 \\
0&-6&80&-10 & 96
\end{array}
\right) \quad
\rightarrow \quad
\left(
\begin{array}{rrrr|r}
1&2&-11&2 &- 14 \\
0&-3&37&-11 & 51 \\
0&0&-\frac{440}{3}&\frac{163}{3}& -201 \\
0&0&6&12 & -6
\end{array}
\right)
\quad
\rightarrow
$$
$$
\quad
\rightarrow \quad
\left(
\begin{array}{rrrr|r}
1&2&-11&2 &- 14 \\
0&-3&37&-11 & 51 \\
0&0&-\frac{440}{3}&\frac{163}{3}& -201 \\
0&0& 0 & \frac{3129}{220} & -\frac{3129}{220}
\end{array}
\right)
$$
Фактически мы просто переписали прямой ход метода Гаусса в терминах матрицы коэффициентов системы.
Последняя получившаяся матрица определит треугольный вид преобразованной системы. Очевидно, на этом этапе алгоритма, нет необходимости иметь дело именно с такими объектами как "линейное уравнение" и "неизвестная величина": пока что все действия производятся с объектом "строка матрицы". Попробуем записать эти действия в терминах операции ((:algebra2#умножение_матриц умножения матриц)). Для этой цели нам потребуются ((:algebra2#элементарных_преобразований матрицы элементарных преобразований)). Итак, на первом шаге метода Гаусса расширенная матрица системы
$$
\left(
\begin{array}{rrrr|r}
1&2&-11&2 &- 14 \\
3&3&4&-5 & 9 \\
5&-7&8&2& 18 \\
7&8&3&4 & -2
\end{array}
\right)
$$
преобразуется следующим образом: первая строка, домноженная на число $ 3_{} $ вычитается из второй строчки. Результатом этого действия будет матрица, которая совпадает с результатом умножения исходной матрицы слева на матрицу элементарных преобразований, а именно
$$
\underbrace{\left(
\begin{array}{rccc}
1 & 0 & 0 & 0\\
-3 & 1 & 0 & 0 \\
0 & 0& 1 & 0 \\
0 & 0 & 0& 1
\end{array}
\right)}_{=T_1}
\left(
\begin{array}{rrrr|r}
1&2&-11&2 &- 14 \\
3&3&4&-5 & 9 \\
5&-7&8&2& 18 \\
7&8&3&4 & -2
\end{array}
\right)=
\left(
\begin{array}{rrrr|r}
1&2&-11&2 &- 14 \\
0&-3&37&-11 & 51 \\
5&-7&8&2& 18 \\
7&8&3&4 & -2
\end{array}
\right)
\ .
$$
Следующий шаг заключается заключается в вычитании из третьей строки полученной матрицы первой, домноженной на $ 5_{} $. Это эквивалентно следующему умножению:
$$
\underbrace{\left(
\begin{array}{rccc}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 \\
-5 & 0& 1 & 0 \\
0 & 0 & 0& 1
\end{array}
\right)}_{=T_2}
\left(
\begin{array}{rrrr|r}
1&2&-11&2 &- 14 \\
0&-3&37&-11 & 51 \\
5&-7&8&2& 18 \\
7&8&3&4 & -2
\end{array}
\right)=
\left(
\begin{array}{rrrr|r}
1&2&-11&2 &- 14 \\
0&-3&37&-11 & 51 \\
0&-17&63&-8& 88 \\
7&8&3&4 & -2
\end{array}
\right) \ .
$$
Результат третьего шага достигается домножением полученной матрицы на матрицу элементарных преобразований
$$
T_3=
\left(
\begin{array}{rccc}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 \\
0 & 0& 1 & 0 \\
-7 & 0 & 0& 1
\end{array}
\right) \ .
$$
Понятно, что общий результат первых трех шагов получится если исходную матрицу системы умножить на произведение всех использованных матриц преобразований, т.е. на матрицу
$$T_{321}=T_3T_2T_1=
\left(
\begin{array}{rccc}
1 & 0 & 0 & 0\\
-3 & 1 & 0 & 0 \\
-5 & 0& 1 & 0 \\
-7 & 0 & 0& 1
\end{array}
\right) \ .
$$
Вообще говоря, при вычислении произведения матриц порядок следования сомножителей существен; однако для нашего конкретного случая матрицы в произведении можно переставлять --- они ((:algebra2#квадратные_матрицы коммутируют)).
Следующие преобразования из метода Гаусса описываются на матричном языке по аналогии:
$$
T_4=
\left(
\begin{array}{rccc}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 \\
0 & -\frac{17}{3}& 1 & 0 \\
0 & 0 & 0& 1
\end{array}
\right) \ , \ T_5
\left(
\begin{array}{rccc}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 \\
0 & 0& 1 & 0 \\
0 & -2 & 0& 1
\end{array}
\right) \quad \Rightarrow \quad T_{54}=
\left(
\begin{array}{rccc}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 \\
0 & -\frac{17}{3}& 1 & 0 \\
0 & -2 & 0& 1
\end{array}
\right) \ .
$$
И, наконец, последнее домножение производится на матрицу
$$
T_6=
\left(
\begin{array}{rccc}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 \\
0 & 0& 1 & 0 \\
0 & 0 & \frac{9}{220}& 1
\end{array}
\right) \ .
$$
Окончательный результат является итогом произведения всех участвующих матриц $ T_{j} $:
$$ T=T_6T_{54}T_{321}=
\left(
\begin{array}{rrrr}
1 & 0 & 0 & 0\\
-3 & 1 & 0 & 0 \\
12 & -\frac{17}{3}& 1 & 0 \\
-\frac{28}{55} & -\frac{491}{220} & \frac{9}{220}& 1
\end{array}
\right)
$$
на расширенную матрицу системы.
♦
А вот в последнем произведении переставлять сомножители нельзя!
Вместо того, чтобы домножать расширенную матрицу $ A \mid \mathcal B $ на матрицу $ T_{} $ мы могли бы иметь дело с исходной системой линейных уравнений:
$$ AX= {\mathcal B} \ . $$
Домножение ее (слева) на построенную матрицу $ T_{} $ приводит систему к новой
$$ (TA) X = T{\mathcal B} ; $$
в которой матрица
$$ U= TA $$
имеет ((:algebra2#треугольная верхнетреугольный вид)). Теперь рассмотрим повнимательней структуру матрицы $ T_{} $. Во-первых, она оказывается ((:algebra2#треугольная нижнетреугольной)). Во-вторых, на ее ((:algebra2#симметричная главной диагонали)) стоят единицы. Как следствие, $ \det T=1 $, т.е. матрица $ T_{} $ является ((:algebra2#обращение_матрицы неособенной)). Развиваем успех: из последнего матричного равенства можно
выразить матрицу $ A_{} $ в виде произведения:
$$ A=T^{-1}U \ . $$
Легко проверить, что обратная к нижнетреугольной матрице $ T_{} $ снова будет нижнетреугольной, и на главной диагонали снова будет иметь единицы. Обозначим $ L=T^{-1} $.
Представление произвольной квадратной матрицы $ A_{} $ в виде произведения нижнетреугольной матрицы $ L_{} $ и верхнетреугольной матрицы $ U_{} $ называется **LU-разложением** матрицы.
Это разложение не всегда существует.
!!П!! **Пример.** Попытка построить LU-разложение для матрицы
$$
A=\left(\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)
$$
по методу неопределенных матриц:
$$ L=
\left(\begin{array}{cc} 1 & 0 \\ \ell_{21} & 0 \end{array} \right) , \quad
U=
\left(\begin{array}{cc} u_{11} & u_{12} \\ 0 & u_{22} \end{array} \right)
$$
заканчивается фиаско...
!!Т!! **Теорема.** //Для того, чтобы матрица// $ A_{} $ //могла быть представлена в виде произведения//
$$ A=L \cdot U $$
//невырожденной нижнетреугольной матрицы// $ L_{} $ //с единицами на главной диагонали[[Такие матрицы называются **унитреугольными**.]] на верхнетреугольную матрицу// $ U_{} $ //необходимо и достаточно, чтобы все ((:algebra2:dets#миноры_и_алгебраические_дополнения главные миноры)) матрицы// $ A_{} $ //были отличны от нуля. При выполнении этого условия, указанное LU-разложение будет единственно.//
Появление в условии теоремы главных миноров матрицы $ A_{} $ кажется, на первый взгляд, неожиданным. Тем не менее, если вспомнить, что стартовой точкой рассуждений о возможности разложения матрицы в произведение явился метод Гаусса решения системы линейных уравнений, то эти миноры обнаруживаются в предыдущем
☞
((#явное_выражение_коэффициентов_преобразованной_системы ПУНКТЕ)), а также
☞
((:algebra2:linearsystems#матричный_формализм_метода_гаусса ЗДЕСЬ)). Условие необращения их в нуль означает, что в прямом ходе метода Гаусса не возникает исключительных случаев, требующих перестановки уравнений и/или переобозначения неизвестных.
====LDU-разложение матрицы==
Можно доказать, что существование LU-разложения для матрицы $ A_{} $ гарантирует, что и матрица $ U^{\top} $ допускает LU-разложение: главные миноры матриц $ A_{} $ и $ U_{} $ совпадают. Из разложения
$$ U^{\top} = L_1\cdot U_1 $$
при матрице $ L_1 $ нижнетреугольной и $ U_1 $ --- верхнетреугольной следует, что
$$ U_1=L_1^{-1} U^{\top} \ . $$
Поскольку обе матрицы в правой части являются нижнетреугольными, то и их произведение также будет нижнетреугольной матрицей. Таким образом, матрица $ U_1 $ должна быть одновременно верхне- и нижнетреугольной. Следовательно, она --- диагональная $ U_1 = D $ и
$$ U^{\top} = L_1\cdot D \quad \Rightarrow \quad U=D \cdot R $$
при $ R=L_1^{\top} $ --- верхнетреугольной с единицами на главной диагонали. Мы приходим к следующему
результату (в котором используем упрощение обозначений --- по-честному, нужно было бы у матриц $ L_{} $ и $ U_{} $ поставить новые индексы...):
!!Т!! **Теорема.** //Для того, чтобы неособенная матрица// $ A_{} $ //могла быть представлена в виде произведения//
$$ A= L \cdot D \cdot U $$
//диагональной матрицы// $ D_{} $, //а также нижней// $ L_{} $ //и верхней// $ U_{} $ //треугольных матриц с единицами на их главных диагоналях
необходимо и достаточно, чтобы все ((:algebra2:dets#миноры_и_алгебраические_дополнения главные миноры))// $ \det A_1,\dots,\det A_n=\det A $ //были ненулевыми. В этом случае представление матрицы в виде такого произведения единственно, при этом
матрица// $ D_{} $ //имеет следующую структуру//:
$$
D=\left(
\begin{array}{ccccc}
\det A_1 & 0 & 0 & \dots & 0 \\
0 & \det A_2/ \det A_1 & 0 & \dots & 0 \\
0 & 0 & \det A_3/ \det A_2 & \dots & 0 \\
\vdots & & & \ddots & \vdots \\
0 & 0 & 0 & \dots & \det A_n/ \det A_{n-1}
\end{array}
\right) \ .
$$
**Доказательство**
☞
((:algebra2:linearsystems:matrix_for:vspom1 ЗДЕСЬ)).
Представление произвольной квадратной матрицы $ A_{} $ в виде произведения нижнетреугольной матрицы $ L_{} $, диагональной матрицы $ D_{} $ и верхнетреугольной матрицы $ U_{} $ называется **LDU-разложением** матрицы $ A_{} $.
!!П!! **Пример.** Для матрицы системы из приведенного выше примера имеем:
$$
\left(
\begin{array}{rrrr}
1 & 0 & 0 & 0\\
-3 & 1 & 0 & 0 \\
12 & -\frac{17}{3}& 1 & 0 \\
& & & \\
-\frac{28}{55} & -\frac{491}{220} & \frac{9}{220}& 1
\end{array}
\right)
\underbrace{\left(
\begin{array}{rrrr}
1&2&-11&2 \\
3&3&4&-5 \\
5&-7&8&2 \\
7&8&3&4
\end{array}
\right)}_{A}=
\left(
\begin{array}{rrrr}
1&2&-11&2 \\
0&-3&37&-11 \\
0&0&-\frac{440}{3}&\frac{163}{3} \\
& & & \\
0&0& 0 & \frac{3129}{220}
\end{array}
\right) \ ;
$$
транспонировав матрицу в правой части равенства, приведем ее к нижнетреугольному ( = диагональному) виду:
$$
\left(
\begin{array}{rrrr}
1&0&0&0 \\
-2&1&0&0 \\
-\frac{41}{3}&\frac{37}{3}&1& 0 \\
& & & \\
\frac{119}{440} &\frac{397}{440}& \frac{163}{440} & 1
\end{array}
\right)
\left(
\begin{array}{rrrr}
1&0&0&0 \\
2&-3&0&0 \\
-11&37&-\frac{440}{3}& 0 \\
& & & \\
2&-11& \frac{163}{3} & \frac{3129}{220}
\end{array}
\right)=
\left(
\begin{array}{rrrr}
1&0&0&0 \\
0&-3&0&0 \\
0&0&-\frac{440}{3}& 0 \\
& & & \\
0&0& 0 & \frac{3129}{220}
\end{array}
\right) \ .
$$
Обращением треугольных матриц получаем LDU-представление матрицы $ A_{} $:
$$
A=
\left(
\begin{array}{rrrr}
1&0&0&0 \\
3&1&0&0 \\
5&\frac{17}{3}&1& 0 \\
& & & \\
7 &2& -\frac{9}{220} & 1
\end{array}
\right)
\left(
\begin{array}{rrrr}
1&0&0&0 \\
0&-3&0&0 \\
0&0&-\frac{440}{3}& 0 \\
& & & \\
0&0& 0 & \frac{3129}{220}
\end{array}
\right)
\left(
\begin{array}{rrrr}
1&2&-11&2 \\
0&1&-\frac{37}{3}&\frac{11}{3} \\
& & & \\
0&0& 1 & -\frac{163}{440} \\
& & & \\
0&0& 0 & 1
\end{array}
\right) \ .
$$
Для контроля приведем величины главных миноров матрицы $ A_{} $:
$$ A_1=1,\ A_2=
\left|
\begin{array}{rr}
1&2 \\
3&3
\end{array}
\right|=-3,\
A_3=
\left|
\begin{array}{rrrr}
1&2&-11 \\
3&3&4 \\
5&-7&8
\end{array}
\right|=440,\
A_4=\det A=6258 \ . $$
♦
!!=>!! //Для того, чтобы неособенная симметричная матрица// $ A_{} $ //могла быть представлена в виде произведения//
$$ A= U^{\top} \cdot D \cdot U $$
//где// $ D_{} $ // --- диагональная матрица//, //а// $ U_{} $ //--- верхнетреугольная матриц с единицами на главной диагонали,
необходимо и достаточно, чтобы все главные миноры// $ \det A_1,\dots,\det A_n=\det A $ //были ненулевыми. В этом случае представление матрицы в виде такого произведения единственно, при этом
матрица// $ D_{} $ //имеет структуру из предыдущей теоремы//.
**Доказательство** необходимости аналогично общему случаю. Обратно, при выполнении условия теоремы, существует единственное LDU-разложение матрицы $ A_{} $. При транспонировании оно должно сохраниться:
$$ LDU=A=A^{\top}=U^{\top} D L^{\top}\, . $$
В силу единственности разложения, имеем: $ L=U^{\top} $.
♦
== Источники ==
[1]. **Гантмахер Ф.Р.** //Теория матриц.// 4-е изд. М.Наука. 1988.
[2]. **Беклемишев Д.В.** //Дополнительные главы линейной алгебры.// М.Наука.1983
[3]. **Стренг Г.** //Линейная алгебра и ее применения//. М.Мир.1980