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 розкладі задля уникнення ділення на нуль. Оскільки представлення чисел з рухомою комою на цифровій машині має обмеження[1], ми також не хочемо ділити на надто маленьке число. Використовують два підходи для вибору опорного елементу на i-му кроці LUP розкладу. Перший — вибрати найбільший елемент в i-му рядку, що дає значний виграш у числовій стійкості. Другий — вибрати найбільший елемент у доповненні Щура на отриманому i-му кроці. Цей підхід дає дуже маленький приріст числової стабільності порівняно з попереднім підходом, натомість вимагає значних затрат часу.[2]

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

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

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

Примітки[ред.ред. код]

  1. Арифметика рухомої коми
  2. Lloyd N. Trefethen; David Bau, III. «21. Pivoting». Numerical Linear Algebra. SIAM. с. 160–161. ISBN 978-0-898713-61-9. 

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