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

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

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

$A=LU,$

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

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

$A=LDU,$

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

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

$A=LUP,$

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

Опис

$A=\left(\begin{array}{ccccc}{a}_{11}& a_{12}& \dots & a_{1n}& \\ a_{21}& a_{22}& \dots & a_{2n}& \\ ⋮& ⋮& \ddots & ⋮& \\ a_{n1}& a_{n2}& \dots & a_{nn}& \end{array}\right)=\left(\begin{array}{ccc}{a}_{11}& w^t& \\ v& A^{\prime }& \end{array}\right)=\left(\begin{array}{ccc}1& 0& \\ v/a_{11}& I_{n-1}& \end{array}\right)\left(\begin{array}{ccc}{a}_{11}& w^T& \\ 0& A^{\prime }-\frac{v\times w^t}{a_{11}}& \end{array}\right)=\left(\begin{array}{ccc}1& 0& \\ v/a_{11}& I_{n-1}& \end{array}\right)\left(\begin{array}{ccc}{a}_{11}& w^T& \\ 0& L^{\prime }{U}^{\prime }& \end{array}\right)=\left(\begin{array}{ccc}1& 0& \\ v/a_{11}& L^{\prime }& \end{array}\right)\left(\begin{array}{ccc}{a}_{11}& w^T& \\ 0& U^{\prime }& \end{array}\right)=LU$

Матриця $A^{\prime }-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\ge j)$

$u_{ij}=\frac{1}{l_{ii}}[a_{ij}-\sum _{k=0}^{i-1}{l}_{ik}{u}_{kj}](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})$

Дивись також

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

Джерела

• Шаблон:Гантмахер.Теорія матриць