Это старая версия (1.158) РазложениеLU.

Содержание

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

  • точное указание ограничений на применимость LU-разложения: какой должны быть матрица A, чтобы невозможно было её разложить (и нужно было бы переходить к РазложениеLUP)?

Определение

LU-разложением матрицы roman A называется её представление в виде произведения матриц roman LU: roman A = left ( matrix { ccol {a sub 11 above vdots above a sub n1} ccol {dots above ddots above dots} ccol {a sub 1n above vdots above a sub nn} } right ) = roman LU = left ( matrix { ccol {l sub 11 above vdots above l sub n1} ccol {dots above ddots above dots} ccol {0 above vdots above l sub nn} } right ) ~ left ( matrix { ccol {u sub 11 above vdots above 0} ccol {dots above ddots above dots} ccol {u sub 1n above vdots above u sub 22} } right )

Матрица roman L (от англ. «lower» — «нижний») — нижняя треугольная матрица: все элементы, находящиеся строго выше главной диагонали, являются нулями.

Матрица roman U (от англ. «upper» — «верхний») — верхняя треугольная матрица: все элементы, находящиеся строго ниже главной диагонали, являются нулями.

Например, для некоторой матрицы roman B sub {(3 times 3)}: roman B sub {(3 times 3)} = left ( matrix { ccol {b sub 11 above b sub 21 above b sub 31} ccol {b sub 12 above b sub 22 above b sub 32} ccol {b sub 13 above b sub 23 above b sub 33} } right ) = roman LU = left ( matrix { ccol {l sub 11 above l sub 21 above l sub 31} ccol {0 above l sub 22 above l sub 32} ccol {0 above 0 above l sub 33} } right ) ~ left ( matrix { ccol {u sub 11 above 0 above 0} ccol {u sub 12 above u sub 22 above 0} ccol {u sub 13 above u sub 23 above u sub 33} } right )

Нужно отметить, что в данном примере матрица roman B sub {(3 times 3)} должна быть невырожденной.

Использование LU-разложения

LU-разложение позволяет эффективно выполнять следующие действия:

  1. Решение матричных уравнений вида roman A bold x = bold b.
  2. Вычисление определителя матрицы roman A : det( roman A).
  3. Обращение матрицы roman A : roman A \\(-> roman A sup -1.

Решение матричных уравнений

Решение матричных уравнений вида roman A bold x = bold b.

После LU-разложения матрицы roman A можем записать исходное матричное уравнение roman A bold x = bold b в виде: roman LU bold x = bold b

Заменив bold y = roman U bold x получим систему, которую просто можно решить прямым ходом (прямой подстановкой): roman L bold y = bold b

Затем, получив решение предыдущего уравнения (bold y) можем разрешить систему обратным ходом (обратной подстановкой): roman U bold x = bold y

В итоге получив искомый вектор bold x.

Вычисление определителя

Вычисление определителя матрицы roman A : det( roman A).

Если roman A = roman LU, то det( roman A) = det( roman LU ) = det( roman L) ~ det( roman U).

Определителем любой треугольной матрицы будет произведение ее диагональных элементов, поэтому det( roman L) ~ det( roman U) = ( size +4 Pi from i=1 to n l sub ii ) ~ ( size +4 Pi from i=1 to n u sub ii )

Получение обратной матрицы

Обращение матрицы roman A : roman A \\(-> roman A sup -1.

По основному свойству обратной матрицы roman A roman A sup -1 = roman I ~ , где roman I — единичная матрица.

Разложив матрицу roman A, можем записать: roman {L U A} sup -1 = roman I

и решить эту матричное уравнение тем же способом, что и описанный выше способ решения матричных уравнений через LU-разложение.

Реализация метода

Алгоритмическая реализация метода

  • Дописать.

Программная реализация метода

  • Дописать.

Эффективность метода

Данное разложение является более вычислительно эффективным: как в аспекте алгоритмической сложности, так и в вопросе программной реализации, — чем стандартные методы решения матричных уравнений (метод Крамера), вычисления определителей (разложением по строке или по столбцу или рекурсивное вычисление) и обращения матриц (через МетодГаусса? или матрицу алгебраических дополнений).

Необходимо отметить, что LU-разложение может применяться не к любой невырожденной матрице roman A. Если LU-разложение неприменимо, то необходимо использовать РазложениеLUP.

Ограниченность метода

Не всякая невырожденная квадратная матрица может быть разложена с помощью LU-разложения.

  • Дописать.

Важные частные случаи

Если матрица roman A является симметрической (т. е. её элементы симметричны относительно главной диагонали) и положительно определенной, то этот частный случай LU-разложения называют РазложениеХолецкого.

Запись LU-разложения будет в этом случае следующей: roman A = roman {L L sup T} = roman {U sup T U}

, причем $$roman L = roman {U sup T$}$$.

КатегорияЛинейнаяАлгебра | КатегорияПрикладнаяМатематика