Ссылка на описание курса

🔷 Тема семинара LU разложение матрицы, условия его существования, алгоритмы нахождения.

🔷 LU разложение используется для решения линейных систем с плотной матрицей.

$$ A x = b\qquad\Leftrightarrow \qquad LUx = b $$

Далее в два этапа отдельное решаются системы в верхней и нижней треугольными матрицами:

$$ Ly = b\qquad\quad Ux = y $$

Заметим, что если однажды было найдено LU разложение, то можно решать линейную систему быстро для многих правых частей b.

<aside> 💡 В качестве литературы можно порекомендовать учебник (Методы численного анализа), смотрите соответствующую главу.

</aside>

<aside> 💡 Также можно посмотреть Matrix Analysis (Horn, Johnson), глава 3.5 (Triangular factorizations and canonical forms). Там разобраны случаи, которые не требуют строгой регулярности матрицы, однако один из факторов может быть вырожден.

</aside>

<aside> 💡 Алгоритм LU разложения хорошо описан в Matrix Computations (Golub, Van Loan), смотрите 3-ю главу (General Linear Systems).

</aside>

В качестве определения LU разложения можно выбрать один из двух подходов:

$$ A, L, U\in\mathbb{C}^{n\times n}\qquad A = LU $$

1. L — нижняя унитреугольная (единицы на диагонали), U — невырожденная верхняя треугольная.
2. L — нижняя треугольная, U — верхняя треугольная.

• В первом случае можно доказать критерий, что такое разложение существует тогда и только тогда, когда A имеет свойство строгой регулярности.
• Во втором случае для невырожденности отдельно фактора L или U нужны более слабые условия, смотрите Matrix Analysis (Horn, Johnson). Данные условия обсуждались и доказывались на семинаре.

Практические алгоритмы строят не LU разложение, а PLU или LUP разложение, где P это некоторая матрица перестановки. Данный процесс называется выбором ведущего элемента и оказывает сильное влияние на оценки точности и устойчивости в арифметике float или double.