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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

\ A = LU,

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

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

\ A = LDU,

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

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

\ A = LUP,

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

Алгоритм[ред.ред. код]

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

Позначимо як lij, uij, aij елементи матриць L,U та A відповідно. З означення LU-розбиття lij=0 (j>i), uij=0 (j<i), uii=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:

\prod L_{i,i}

Дивись також[ред.ред. код]

Джерела[ред.ред. код]