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

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

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

$\ A = LU,$

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

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

$\ A = LDU,$

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

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

$\ A = LUP,$

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

Алгоритм

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

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

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

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

$A x = L U x = b \,$

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

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

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

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

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

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

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

$\sum U_{i,j}$

Дивись також

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

Джерела

• Гантмахер Ф. Р. (1967). Теория матриц (вид. друге). Москва: Наука. с. 576.