Решение СЛАУ методом LU-разложения по Алгоритму Краута
Одним из лучших методов решения систем линейных алгебраических уравнений общего вида является метод, основанный на разложении исходной матрицы на произведение треугольных, или метод LU-факторизации. Алгоритмы этого метода близки к алгоритмам метода Гаусса, хотя вычисления могут производиться в различной последовательности. Главным преимуществом метода LU-факторизации в сравнении с методом Гаусса является возможность более быстрого получения решений для различных векторов свободных членов, а также для транспонированной системы уравнений.
По числу операций, необходимых для решения конкретной системы, методы Гаусса и LU-факторизации практически неразличимы. Однако из всех операций решения в методе LU-разложения почти половина приходится на этап факторизации и следующая половина - на собственно решение двух треугольных систем. В силу этого факта при необходимости решения системы, отличающейся лишь вектором свободных членов, получаем экономию на операциях разложения. Аналогично, когда необходимо решать транспонированную систему после исходной, можно воспользоваться предыдущей факторизацией и лишь сменить порядок решения треугольных систем в силу операции транспонирования.
Понятие LU-разложение
Представление матрицы A в виде произведения двух матриц, A = L * U, где L — нижняя треугольная матрица, а U — верхняя треугольная матрица.
$L=\left[\begin{matrix}{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{matrix}\right]$ $U=\left[\begin{matrix}1&{u}_{12}&{u}_{13}&{u}_{14}\\0&1&{u}_{23}&{u}_{24}\\0&0&1&{u}_{34}\\0&0&0&1\end{matrix}\right]$Матрица - математический объект, записываемый в виде прямоугольной таблицы элементов кольца или поля (например, целых, действительных или комплексных чисел), которая представляет собой совокупность строк и столбцов, на пересечении которых находятся её элементы.
В методе решения систем линейных уравнений, основанном на факторизации, предполагается, что исходная система может быть представлена в виде
$$L * U * x = y$$т.е.
$$A = L * U$$Причем для определенности полагается, что матрица L является нижнетреугольной, а U–верхнетреугольной, причем с единичной диагональю.
Забегая несколько вперед, сразу отметим, что определитель треугольной матрицы равен произведению диагональных элементов, а определитель произведения матриц равен произведению их определителей. Откуда следует, что определитель матрицы A равен произведению диагональных элементов нижнетреугольной матрицы L:
\begin{equation*} {\Delta}=\prod _{i=1}^{n}{{l}_{11}} \end{equation*} Ограничившись для наглядности порядком n = 4, запишем L- и U-матрицы:Применения
Решение систем алгебраических линейных уравнений
Полученное LU-разложение матрицы A (матрица коэффициентов системы) может быть использовано для решения семейства систем линейных уравнений с различными векторами b в правой части:
$$A * x = b$$Если известно LU-разложение матрицы A, $$A = L*U$$, исходная система может быть записана как
$$L * U * x = b,$$Эта система может быть решена в два шага. На первом шаге решается система
$$L * U = b,$$ Поскольку I - нижняя треугольная матрица, эта система решается непосредственно прямой подстановкой. На втором шаге решается система $$U * x = y,$$Поскольку U - верхняя треугольная матрица, эта система решается непосредственно обратной подстановкой.
Обращение матриц
Обращение матрицы A эквивалентно решению линейной системы
$$A * X = I$$где X - неизвестная матрица, I - единичная матрица. Решение X этой системы является обратной матрицей ${A}^{-1}$. Систему можно решить описанным выше методом LU-разложения.
Вычисление определителя матрицы
Определитель (или детерминант) – это многочлен, комбинирующий элементы квадратной матрицы таким образом, что его значение сохраняется при транспонировании и линейных комбинациях строк или столбцов. То есть, определитель характеризует содержание матрицы. В частности, если в матрице есть линейно-зависимые строки или столбцы, — определитель равен нулю. Определитель играет ключевую роль в решении в общем виде систем линейных уравнений, на его основе вводятся базовые понятия. Имея LU-разложение матрицы A,
$$A=L*U,$$ можно непосредственно вычислить её определитель, \begin{equation*} \mathit{det}\left(A\right)=\mathit{det}\left(\mathit{LU}\right)=\mathit{det}\left(L\right)\mathit{det}\left(U\right)=\left(\prod _{i=1}^{n}{\mathit{Lii}}\right)\left(\prod _{i=1}^{n}{\mathit{Uii}}\right) \end{equation*} где n — размер матрицы A, $l_{ii}$ и $u_{ii}$ - диагональные элементы матриц L и U.Алгоритм Краута
Суть алгоритма Краута. Предполагая, что разложение A = L * U существует, запишем произведение L * U:
A = \begin{bmatrix}l_{11} & l_{11} u_{12} & l_{11} u_{12} & l_{11} u_{14} \\ l_{21} & l_{21} u_{12} + l_{22} & l_{21} u_{13} + l_{22} u_{23} & l_{21} u_{14} + l_{22} u_{24} \\ l_{31} & l_{31} u_{12} + l_{32} & l_{31} u_{13} + l_{32} u_{23} + l_{33} & l_{31} u_{14} + l_{32} u_{24} + l_{33} u_{34} \\ l_{41} & l_{41} u_{12} + l_{42} & l_{41} u_{13} + l_{42} u_{23} + l_{43} & l_{41} u_{14} + l_{42} u_{24} + l_{34} u_{34} + l_{44}\end{bmatrix}Сравнивая компоненты этого произведения с компонентами матрицы A, видим, что первый столбец произведения L * U равен первому столбцу матрицы A, т.е. , при i = 1,…,4. Первая строка произведения может быть использована для определения первой строки матрицы U.
Действительно, т.к.
$$l_{11}*u_{1j}=a_{1j},$$при j=2,..4, получаем $$u_{1j}=a_{1j}/a_{11}.$$ Поскольку во втором столбце элементы $u_{12}$ и $l_{i3}$ известны, можем определить второй столбец матрицы L: \begin{equation*} {l}_{\mathit{i2}}={a}_{12}-{l}_{\mathit{i1}}\ast {u}_{12} \end{equation*}
где $i=2,...,4$. Теперь, т.к. известны $l_{21}$ , $l_{22}$ и $u_{1j}$, можно по второй строке произведения определить вторую строку матрицы U:
\begin{equation*} {u}_{2j}=\left({a}_{2j}-{l}_{21}\ast {u}_{1j}\right)/{{l}_{22}} \end{equation*}при $j=3,...,4$. Далее, чередуя строки и столбцы, можно аналогичным образом найти остальные элементы матриц L и U. Чтобы получить общие соотношения, запишем произвольный элемент произведения L * U:
Чтобы получить общие соотношения, запишем произвольный элемент произведения L * U:
\begin{equation*} {a}_{\mathit{ij}}=\sum _{m=1}^{n}{{l}_{\Im }\ast {u}_{\mathit{mj}}=\sum _{m=1}^{\mathit{min}\text(i,j)}{{l}_{\Im }\ast {u}_{\mathit{mj}}}} \end{equation*}где верхний предел суммы учитывает наличие нулевых элементов в матрицах L и U. Рассмотрим произвольный элемент на или под главной диагональю матрицы A, для которого , и заменим индекс на . Учитывая при этом, что $u_{kk} = 1$, получим
\begin{equation*} {a}_{\mathit{ik}}=\sum _{m=1}^{k}{{l}_{\Im }\ast {u}_{\mathit{mk}}}={l}_{\mathit{ik}}+\sum _{m=1}^{k-1}{{l}_{\Im }\ast {u}_{\mathit{mk}}} \end{equation*}откуда
\begin{equation*} {l}_{\mathit{ik}}={a}_{\mathit{ik}}-\sum _{m=1}^{k-1}{{l}_{\Im }\ast {u}_{\mathit{mk}}},(1.1) \end{equation*}при $j>=k$ и $k=1,..,n$. Аналогичным образом, рассматривая произвольный элемент над главной диагональю, для которого , и используя k вместо i, находим
\begin{equation*} {a}_{\mathit{kj}}=\sum _{m=1}^{k}{{l}_{\mathit{mk}}\ast {u}_{\mathit{mj}}}={l}_{\mathit{ik}}\ast {u}_{\mathit{kj}}+\sum _{m=1}^{k-1}{{l}_{\mathit{km}}\ast {u}_{\mathit{mj}}} \end{equation*}откуда
\begin{equation*} {u}_{\mathit{kj}}=\left({a}_{\mathit{kj}}-\sum _{m=1}^{k-1}{{l}_{\mathit{km}}}\ast {u}_{\mathit{mj}}\right)/{{l}_{\mathit{kk},(1.2)}} \end{equation*}при и j > k, и k = 1,...,n.
Эти соотношения для $l_{ik}$ и $u_{kj}$ есть алгоритм разложения на треугольные матрицы – алгоритм Краута.
Заметим, что текущие элементы матриц L и U определяются текущим элементом матрицы A и предыдущими элементами матриц L и U.
Отсюда, т.к. нулевые элементы и единичную диагональ матрицы U запоминать не нужно, в процессе вычислений матрицы L и U могут быть записаны на месте матрицы A, причем L расположена в нижнем треугольнике $(i>=j)$, а U – соответственно в верхнем треугольнике $(i
Коротко алгоритм Краута как вариант чередования столбцов и строк можно представить следующей последовательностью действий: