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

Содержание

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

ToDo:

  • LU-разложение — частный случай МетодГаусса?.
  • Через LU-разложение можно представить не любую матрицу, расширением метода для произвольной матрицы является РазложениеLUP (LU-разложение — частный случай LUP-разложения). LUP-разложение, a propos, тоже является частным случаем МетодГаусса?.
  • Сравнение алгоритмической сложности методов через roman O(n)-нотацию.
  • «наглядно представлена» — что я пишу вообще, переделать, это не по-русски, по крайней мере не в этом контектсе.

Определение

Для корректного определения понятия LU-разложения введем несколько дополнительных опредлений (затем перенести в статью АлгебраическиеМатрицы?, или в статью с другим названием, но отражающим суть явления)

Треугольная матрица (определение из учебника)
Квадратная матрица, все элементы которой строго выше или строго ниже главной диагонали равны нулю.
Треугольная матрица (с немаловожным уточнением)
Квадратная матрица, все элементы которой строго выше или строго ниже главной диагонали равны нулю, а среди остальных элементов найдётся хотя бы один ненулевой.

  • Кстати, вопрос к дипломированным математикам с дипломом не ниже НМУ с отличием (агагагагагагагага): а что с остальными элементами? Является ли нулевая матрица треугольной? И является ли второе определение более корректным? -- АтрашкевичАндрей
  • Кстати, практически уверен, что никто не будет отвергать, что диагональная ненулевая матрица с нулевым следом будет треугольной, причем и нежнетреугольной, и верхнетреугольной. Или разубедите меня. -- АтрашкевичАндрей

Нижнетреугольная матрица
треугольная матрица, все элементы которой строго ниже главной диагонали, равны нулю.

Нижнетреугольная матрица чаще всего обозначается L (от англ. lower) и может быть наглядно представлена в следующем виде: L =
left (
matrix {
ccol {a sub 11 above a sub 21 above a sub 31 above vdots above a sub n1}
ccol {0 above a sub 22 above a sub 32 above vdots above a sub n2}
ccol {0 above 0 above a sub 33 above vdots above a sub 3n}
ccol {dots above dots above dots above ddots above dots}
ccol {0 above 0 above 0 above vdots above a sub nn}
}
right )

, т. е. forall i < j ~ : ~ a sub ij = 0

Верхнетреугольная матрица
треугольная матрица, все элементы которой строго выше главной диагонали, равны нулю.

Верхнетреугольная матрица чаще всего обозначается U (от англ. upper) и может быть наглядно представлена в следующем виде: U =

left (
matrix {
ccol {a sub 11 above 0 above 0 above vdots above 0}
ccol {a sub 12 above a sub 22 above 0 above vdots above 0}
ccol {a sub 13 above a sub 23 above a sub 33 above vdots above 0}
ccol {dots above dots above dots above ddots above dots}
ccol {a sub 1n above a sub 2n above a sub 3n above vdots above a sub nn}
}
right )

, т. е. forall i > j ~ : ~ a sub ij = 0

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

Данное разложение помогает эффективно решать системы линайных алгебраических уравнений (СЛАУ), находить определитель матрицы (чтобы проверить разрешимость СЛАУ) и обращать матрицы.

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

Поток мыслей (или зачем это вообще нужно?)



«Король математики» Карл Гаусс мог не только ввести в ступор своего учителя по математике [1], но и придумал (вернее, переоткрыл, этот способ был известен еще в Китае эпохи раннего Тан, кажется) метод решения систем алгебраических уравнений. Этим методом можно решить (или прийти к выводу о неразрешимости) любую систему линейных алгебраических уравнений (в том числе и такую, в которой число переменных равно числу уравнений). Этот метод получил название МетодГаусса?. Затем идеи этого фундаментального математического метода легли в основу, например МетодНаименьшихКвадратов и многих других вычислительных методов, оперирующих аппаратом линейной алгебры.

Примерно тогда же появилось понятие ОпределительМатрицы?. Его основной целью было определить, имеется ли у СЛАУ решение.

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

При этом вычислительные мощности выросли на порядки. И нужны были красивые и простые (как в смысле алгоритма, так и в смысле реализации) методы решения СЛАУ (и, соответственно, вычисления определителей). Это и дало толчок к тому, чтобы развивать идеи разложений матриц. Потому что метод Гаусса прямым и обратным ходом позволяет совершенно элементарно решать СЛАУ.


  • Надо написать про сравнительную сложность алгоритмов: решать СЛАУ через разложение или через рукопашные методы. -- АтрашкевичАндрей


[1] Для незнающих, рекомендую ознакомиться с этим чудесным случаем: ни идиотская методика преподавания, строящаяся на палочной дисциплине и наказаниях не изменилась (а лишь ухудшилась), ни образ учителя математики как идиота и самодура не претерпел никаких измений.

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