LU-розклад матриці

LU-розклад матриці — представлення матриці у вигляді добутку нижньої трикутної матриці та верхньої трикутної матриці.

Квадратна матриця A розміру n може бути представлена у вигляді

$\ A=LU,$

де L та U — нижня та верхня трикутна матриця того ж розміру відповідно.

LDU-розклад матриці — це представлення у вигляді

$\ A=LDU,$

де D — діагональна матриця, а L та U є одиничними трикутними матрицями, тобто, всі їх діагональні елементи рівні одиниці.

LUP-розклад матриці — це представлення в формі

$\ A=LUP,$

де L та U — нижня та верхня трикутна матриця того ж розміру, а P — матриця перестановки.

Опис

$A={\begin{pmatrix}a_{11}&a_{12}&\dots &a_{1n}&\\a_{21}&a_{22}&\dots &a_{2n}&\\\vdots &\vdots &\ddots &\vdots &\\a_{n1}&a_{n2}&\dots &a_{nn}&\\\end{pmatrix}}={\begin{pmatrix}a_{11}&w^{t}&\\v&A'&\\\end{pmatrix}}={\begin{pmatrix}1&0&\\v/a_{11}&I_{n-1}&\\\end{pmatrix}}{\begin{pmatrix}a_{11}&w^{T}&\\0&A'-{\frac {v\times w^{t}}{a_{11}}}&\\\end{pmatrix}}={\begin{pmatrix}1&0&\\v/a_{11}&I_{n-1}&\\\end{pmatrix}}{\begin{pmatrix}a_{11}&w^{T}&\\0&L'U'&\\\end{pmatrix}}={\begin{pmatrix}1&0&\\v/a_{11}&L'&\\\end{pmatrix}}{\begin{pmatrix}a_{11}&w^{T}&\\0&U'&\\\end{pmatrix}}=LU$

Матриця $A'-v\times w^{t}/a_{11}$ називається доповненням Шура для $A$ щодо $a_{11}.$

Метод не працює якщо один з $a_{ii}=0,$ тому що відбувається ділення на нуль. Елементи, на які ми ділимо впродовж $LU$-розкладу, називаються опорними і перебувають на головній діагоналі матриці $U.$ Ми використовуємо матрицю перестановки $P$ у $LUP$-розкладі задля уникнення ділення на нуль. Оскільки представлення чисел з рухомою комою на цифровій машині має обмеження, ми також не хочемо ділити на надто маленьке число. Використовують два підходи для вибору опорного елементу на $i$-му кроці $LUP$-розкладу. Перший — вибрати найбільший елемент в $i$-му рядку, що дає значний виграш у числовій стійкості. Другий — вибрати найбільший елемент у доповненні Щура на отриманому $i$-му кроці. Цей підхід дає дуже маленький приріст числової стабільності порівняно з попереднім підходом, натомість вимагає значних затрат часу.

Алгоритм

Є модифікованим методом Гауса і потребує 2n³ / 3 арифметичних операцій.

Позначимо як l_ij, u_ij, a_ij елементи матриць L,U та A відповідно. З означення LU-розбиття l_ij=0 (j>i), u_ij=0 (j<i), u_ii=1. Очевидно, що

$a_{ij}=\sum _{k=0}^{n-1}l_{ik}u_{kj}=\sum _{k=0}^{i-1}l_{ik}u_{kj}+l_{ii}u_{ij}+\sum _{k=i+1}^{n-1}l_{ik}u_{kj}=\sum _{k=0}^{i-1}l_{ik}u_{kj}+l_{ii}u_{ij}$

$a_{ij}=\sum _{k=0}^{n-1}l_{ik}u_{kj}=\sum _{k=0}^{j-1}l_{ik}u_{kj}+l_{ij}u_{jj}+\sum _{k=j+1}^{n-1}l_{ik}u_{kj}=\sum _{k=0}^{j-1}l_{ik}u_{kj}+l_{ij}u_{jj}$,

(тут n — розмір матриці А)

Звідки легко в явній формі отримати вирази для елементів матриць L та U:

$l_{ij}=a_{ij}-\sum _{k=0}^{j-1}l_{ik}u_{kj}\ (i\geq \ j)$

$u_{ij}={1 \over l_{ii}}\left[a_{ij}-\sum _{k=0}^{i-1}l_{ik}u_{kj}\right]\ (i<j)$

Застосування

Розв'язок СЛАР

Якщо в рівнянні

$Ax=LUx=b\,$

задано A та b. Тоді розв'язок отримується в два кроки:

1. Розв'язуємо рівняння $Ly=b$ і знаходимо y
2. Розв'язуємо рівняння $Ux=y$ і знаходимо x.

Обернена матриця

Матриці L та U можуть використовуватись для обчислення оберненої матриці:

$\ A^{-1}=U^{-1}L^{-1}.$

Обчислення детермінанта

Після застосування LU-розкладу детермінант може бути обчислений через добуток детермінантів матриць L та U. А детермінанти цих матриць рівні добутку діагональних елементів:

det(A)=det(LU)=det(L)det(U)=$(\prod L_{i,i})$$(\prod U_{i,i})$

Дивись також

• Теорія матриць

Джерела

• Гантмахер Ф. Р. Теория матриц. — 5-е. — М: : Физматлит, 2010. — 559 с. — ISBN 5-9221-0524-8.(рос.)