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

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

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

${\displaystyle \ A=LU,}$

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

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

${\displaystyle \ A=LDU,}$

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

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

${\displaystyle \ A=LUP,}$

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

Опис

${\displaystyle 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}$

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

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

Алгоритм

Є модифікованим методом Гауса і потребує 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. Очевидно, що

${\displaystyle 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}}$

${\displaystyle 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:

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

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

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

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

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

${\displaystyle Ax=LUx=b\,}$

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

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

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

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

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

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

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

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

Дивись також

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