Метод LU-разложения онлайн

Решение СЛАУ методом 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

LU-разложение.

LUP-разложение

LU-разложение матрицы A — это представление матрицы A в виде произведения

A=LU,

где L-нижняя треугольная матрица, U — верхняя треугольная или ступенчатая матрица.

Процедура LU — разложения

Пусть A прямоугольная матрица порядка m×n любого ранга. С правой стороны матрицы А приписываем единичную матрицуE порядка n×n. Применяем к матрице A|Eметод исключения Гаусса. Если на каком то этапе Гауссово исключения ведущий элемент равен нулю, и существует ненулевой элемент, расположенный ниже ведущего элемента, то LU — разложение данной матрицы невозможно. Если же элементы ниже ведущего элемента нулевые, то выбираем новый ведущий элемент той же строки и следующего столбца.

Приводим матрицу A|E к треугольному или ступенчатому виду. Получим матрицу U|L0, где U— верхняя треугольная или ступенчатая матрица, а L0— нижняя треугольная матрица.

Заметим, что полученная матрица L0 приводит A к треугольному или ступенчатому виду:

Так как L0 квадратная невырожденная матрица, следовательно имеет обратную матрицу . Тогда

(2)

или

(3)

где .

Как мы отметили, не всегда можно проводить LU -разложение матрицы. Но LUP— разложение всегда возможно.

LUP-разложение матрицы A — это представление матрицы A в виде произведения

PA=LU,

где L-нижняя треугольная матрица, U — верхняя треугольная или ступенчатая матрица, P— матрица перестановок (матрица перестановок — эта матрица, полученная из единичной матрицы перестановкой некоторых строк или столбцов).

Процедура LUP — разложения

Пусть A прямоугольная матрица порядка m×n любого ранга. С правой стороны матрицы А приписываем единичную матрицу E порядка n×n. Применяем к матрице A|E матод исключения Гаусса c выбором наибольшего по модулю ведущего элемента. Если на каком то этапе исключения ведущий элемент равен нулю, то процедуру останавливаем. Получим матрицу U|L0. Тогда имеют место равенства (1) и (2). Но в общем случае L0 и, следовательно, не являются нижними треугольными матрицами, если при применении Гауссово исключения строки переставлялись.

Далее допустим, что мы знаем, как построить матрицу A1 из матрицы A переставляя строки так, что при применении Гауссово исключения c выбором максимального по модулю ведущего элемента относительно матрицы A1 не понадобилась переставление строк. Выбираем матрицу перестановок так, что

(4)

Строим матрицу A1|E и применяем Гауссово исключение. Получим матрицу U|L1. Тогда

(5)

где L1 и нижние треугольные матрицы т.к. при применении Гауссово исключения строки матрицы A1 не переставлялись.

Из (4) и (5) имеем:

(6)

Обозначим.

Наша задача найти L и U, без построения A1.

Из (2) и (4) имеем:

(7)

Тогда, учитывая второе равенство (5), получим:

(8)

Следовательно

(9)

Получили, что для LUP-разложения нужно применить Гауссово исключение c выбором максимального по модулю ведущего элемента относительно матрицы A|E. Получим матрицу . Вычисляем обратную матрицу . Вычисляем L из выражения (9).

Матрица перестановок Р строится во время Гауссово исключения, учитывая перестановки строк.

Пример LU — разложения (A=LU)

Пример LUP — разложения (PA=LU)

LU (LUP)-разложение онлайн

Для LU(LUP)-разложения онлайн пользуйтесь матричным онлайн калькулятором.

.

Добавить комментарий

Закрыть меню