2.10: Факторизація LU

\(LU\)Факторизація матриці передбачає запис даної матриці у вигляді добутку нижньої трикутної матриці,\(L\) яка має основну діагональ, що складається повністю з них, і верхньої трикутної матриці\(U\) у вказаному порядку. Це версія обговорюється тут, але іноді буває, що\(L\) має номери, відмінні від 1 вниз по головній діагоналі. Це все ще корисна концепція. \(L\)Йде з «нижнім», а\(U\) з «верхнім».

Виявляється, багато матриць можна записати таким чином, і коли це можливо, люди захоплюються гладкими способами вирішення системи рівнянь,\(AX=B\). Саме з цієї причини потрібно вивчити\(LU\) факторизацію. Вона дозволяє працювати тільки з трикутними матрицями. Виявляється, для отримання\(LU\) факторизації потрібно приблизно вдвічі менше операцій, ніж для пошуку рядка зменшеної форми ешелону.

Спочатку слід зазначити, що не всі матриці мають\(LU\) факторизацію і тому ми підкреслимо прийоми її досягнення, а не формальні докази.

Приклад\(\PageIndex{1}\): A Matrix with NO \(LU\) factorization

Чи можете ви написати\(\left[ \begin{array}{rr} 0 & 1 \\ 1 & 0 \end{array} \right]\) у формі,\(LU\) як тільки що описано?

Рішення

Для цього вам знадобиться\[\left[ \begin{array}{rr} 1 & 0 \\ x & 1 \end{array} \right] \left[ \begin{array}{rr} a & b \\ 0 & c \end{array} \right] = \ \left[ \begin{array}{cc} a & b \\ xa & xb+c \end{array} \right] =\left[ \begin{array}{rr} 0 & 1 \\ 1 & 0 \end{array} \right] .\nonumber \]

Тому,\(b=1\) а\(a=0.\) також, з нижніх рядків,\(xa=1\) що не може статися і мати\(a=0.\) Тому ви не можете записати цю матрицю у вигляді\(% LU.\) Вона не має\(LU\) факторизації. Це те, що ми маємо на увазі вище, кажучи, що метод не вистачає загальності.

Тим не менш, метод часто надзвичайно корисний, і ми опишемо нижче багато методів, які використовуються для створення\(LU\) факторизації, коли це можливо.

Пошук\(LU\) факторизації шляхом інспекції

Які матриці мають\(LU\) факторизацію? Виявляється це ті, чиї рядно-ешелонові форми можна домогтися без перемикання рядів. Іншими словами, матриці, які передбачають використання рядкових операцій типу 2 або 3 для отримання форми рядка-ешелону.

Приклад\(\PageIndex{2}\): An \(LU\) factorization

Знайдіть\(LU\) факторизацію\(A=\left[ \begin{array}{cccc} 1 & 2 & 0 & 2 \\ 1 & 3 & 2 & 1 \\ 2 & 3 & 4 & 0 \end{array} \right] .\)

Рішення

Один із способів знайти\(LU\) факторизацію - просто шукати її безпосередньо. Вам потрібно

\[\left[ \begin{array}{cccc} 1 & 2 & 0 & 2 \\ 1 & 3 & 2 & 1 \\ 2 & 3 & 4 & 0 \end{array} \right] =\left[ \begin{array}{ccc} 1 & 0 & 0 \\ x & 1 & 0 \\ y & z & 1 \end{array} \right] \left[ \begin{array}{cccc} a & d & h & j \\ 0 & b & e & i \\ 0 & 0 & c & f \end{array} \right] .\nonumber \]

Потім множивши їх, ви отримаєте,\[ \ \left[ \begin{array}{cccc} a & d & h & j \\ xa & xd+b & xh+e & xj+i \\ ya & yd+zb & yh+ze+c & yj+iz+f \end{array} \right]\nonumber \] і так ви можете тепер сказати, що різні величини рівні. З першого стовпця потрібно\(a=1,x=1,y=2.\) Тепер перейти до другого стовпця. Вам\(d=2,xd+b=3\)\(b=1,yd+zb=3\) так потрібно\(z=-1.\) з третього стовпця,\(h=0,e=2,c=6.\) Тепер з четвертого стовпця,\(j=2,i=-1,f=-5.\) Таким чином,\(LU\) факторизація є\[\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 2 & -1 & 1 \end{array} \right] \left[ \begin{array}{rrrr} 1 & 2 & 0 & 2 \\ 0 & 1 & 2 & -1 \\ 0 & 0 & 6 & -5 \end{array} \right] \nonumber .\] Ви можете перевірити, чи правильно ви отримали це просто множивши ці два.

\(LU\)Факторизація, Метод множника

Пам'ятайте, що для того,\(A\) щоб матриця була записана у формі\(A=LU\), ви повинні вміти зводити її до своєї рядково-ешелонової форми без зміни рядків. Наступний метод дає процес обчислення\(LU\) факторизації такої матриці\(A\).

Приклад\(\PageIndex{3}\): \(LU\) factorization

Знайдіть\(LU\) факторизацію для\[\left[ \begin{array}{rrr} 1 & 2 & 3 \\ 2 & 3 & 1 \\ -2 & 3 & -2 \end{array} \right]\nonumber \]

Рішення

Запишіть матрицю як наступний твір. \[\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{rrr} 1 & 2 & 3 \\ 2 & 3 & 1 \\ -2 & 3 & -2 \end{array} \right]\nonumber \]

У матриці праворуч почніть з лівого рядка і обнуліть записи нижче верхньої частини, використовуючи операцію рядка, яка передбачає додавання кратного рядка до іншого рядка. Ви робите це і також оновлюєте матрицю зліва, щоб товар був незмінним. Ось перший крок. Візьміть\(-2\) раз верхній ряд і додайте до другого. Потім візьміть\(2\) раз верхній ряд і додайте до другого в матрицю зліва. \[\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{rrr} 1 & 2 & 3 \\ 0 & -1 & -5 \\ -2 & 3 & -2 \end{array} \right]\nonumber \]Наступний крок - зайняти\(2\) раз верхній ряд і додати до нижнього в матриці праворуч. Для того, щоб товар був незмінним, ви розміщуєте\(% -2\) в лівому нижньому кутку в матриці зліва. Таким чином, наступний крок дає\[\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -2 & 0 & 1 \end{array} \right] \left[ \begin{array}{rrr} 1 & 2 & 3 \\ 0 & -1 & -5 \\ 0 & 7 & 4 \end{array} \right]\nonumber \] Далі зайняти\(7\) раз середній ряд праворуч і додати до нижнього ряду. Оновлення матриці зліва аналогічно тому, що було зроблено раніше,\[\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -2 & -7 & 1 \end{array} \right] \left[ \begin{array}{rrr} 1 & 2 & 3 \\ 0 & -1 & -5 \\ 0 & 0 & -31 \end{array} \right]\nonumber \] на цьому етапі зупиніться. Ви закінчили.

Щойно описаний метод називається методом множника.

Розв'язування систем за допомогою\(LU\) факторизації

Одна з причин, чому люди піклуються про\(LU\) факторизацію, це дозволяє швидко вирішувати системи рівнянь. Ось приклад.

Приклад\(\PageIndex{4}\): \(LU\) factorization to Solve Equations

Припустимо, ви хочете знайти рішення для\[\left[ \begin{array}{rrrr} 1 & 2 & 3 & 2 \\ 4 & 3 & 1 & 1 \\ 1 & 2 & 3 & 0 \end{array} \right] \left[ \begin{array}{c} x \\ y \\ z \\ w \end{array} \right] =\left[ \begin{array}{c} 1 \\ 2 \\ 3 \end{array} \right] .\nonumber \]

Рішення

Звичайно, один із способів - написати доповнену матрицю і відшліфувати. Однак це передбачає більше операцій рядків, ніж обчислення\(LU\) факторизації, і виявляється, що\(LU\) факторизація може дати рішення швидко. Ось як. Далі наведено\(LU\) факторизацію матриці. \[\left[ \begin{array}{rrrr} 1 & 2 & 3 & 2 \\ 4 & 3 & 1 & 1 \\ 1 & 2 & 3 & 0 \end{array} \right] \ = \ \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 4 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right] \left[ \begin{array}{rrrr} 1 & 2 & 3 & 2 \\ 0 & -5 & -11 & -7 \\ 0 & 0 & 0 & -2 \end{array} \right] .\nonumber\]

Давайте\(UX=Y\) і розглянемо\(LY=B\), де в даному випадку,\(B=\left[ 1,2,3\right] ^{T}\). Таким чином\[ \ \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 4 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right] \left[ \begin{array}{c} y_{1} \\ y_{2} \\ y_{3} \end{array} \right] =\left[ \begin{array}{c} 1 \\ 2 \\ 3 \end{array} \right]\nonumber \], що дає дуже швидко, що\(Y=\left[ \begin{array}{r} 1 \\ -2 \\ 2 \end{array} \right] \ .\)

Тепер можна знайти,\(X\) вирішивши\(UX=Y\). Таким чином, в даному випадку,\[\left[ \begin{array}{rrrr} 1 & 2 & 3 & 2 \\ 0 & -5 & -11 & -7 \\ 0 & 0 & 0 & -2 \end{array} \right] \left[ \begin{array}{c} x \\ y \\ z \\ w \end{array} \right] =\left[ \begin{array}{r} 1 \\ -2 \\ 2 \end{array} \right]\nonumber \] який дає\[X=\left[ \begin{array}{c} - \frac{3}{5}+\frac{7}{5}t \\ \frac{9}{5}-\frac{11}{5}t \\ t \\ -1 \end{array} \right] ,\enspace t\in \mathbb{R}\text{.}\nonumber \]

Обґрунтування методу мультиплікатора

Чому метод множника працює для знаходження\(LU\) факторизації? Припустимо,\(A\) це матриця, яка має властивість, для якої форма рядка-ешелон\(A\) може бути досягнута без перемикання рядків. Таким чином, кожен рядок, який замінюється за допомогою цієї операції рядка при отриманні форми рядка-ешелону, може бути змінений за допомогою рядка, який знаходиться над ним.

Лемма\(\PageIndex{1}\): Multiplier Method and Triangular Matrices

\(L\)Дозволяти нижню (верхню) трикутну матрицю\(m\times m\), яка має ті, що знаходяться вниз по головній діагоналі. Потім\(L^{-1}\) також є нижня (верхня) трикутна матриця, яка має ті, що знаходяться вниз по головній діагоналі. У випадку,\(L\) який має форму,\[L=\left[ \begin{array}{cccc} 1 & & & \\ a_{1} & 1 & & \\ \vdots & & \ddots & \\ a_{n} & & & 1 \end{array} \right] \label{4nove1h}\] де всі записи дорівнюють нулю, за винятком лівого стовпця та основної діагоналі, це також випадок, який\(L^{-1}\) отримується простим\(L\) множенням кожного запису нижче основної діагоналі в \(L\)с\(-1\). Те саме вірно, якщо один ненульовий стовпчик знаходиться в іншій позиції.

Доказ

Розглянемо звичайну настройку для знаходження зворотного\(\left[ \begin{array}{cc} L & I \end{array} \right] .\) Потім кожна операція рядка робиться для зменшення\(L\) до рядка зменшеної форми ешелону призводить до зміни лише записів\(I\) нижче основної діагоналі. В особливому випадку\(L\) заданого в\(\eqref{4nove1h}\) або єдиному ненульовому стовпчику знаходиться в іншій позиції, множення на,\(-1\) як описано в лемі, явно призводить до\(L^{-1}\).

Для простої ілюстрації останньої заяви,\[\left[ \begin{array}{cccccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & a & 1 & 0 & 0 & 1 \end{array} \right] \rightarrow \left[ \begin{array}{cccccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & -a & 1 \end{array} \right]\nonumber \]

Тепер нехай\(A\) буде\(m\times n\) матриця, скажімо\[A=\left[ \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{array} \right]\nonumber \] і припустимо,\(A\) може бути рядок зменшена до верхньої трикутної форми, використовуючи тільки рядок операції 3. Таким чином, зокрема,\(a_{11}\neq 0\). Помножити ліворуч на\(E_{1}=\)\[\left[ \begin{array}{cccc} 1 & 0 & \cdots & 0 \\ - \frac{a_{21}}{a_{11}} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ -\frac{a_{m1}}{a_{11}} & 0 & \cdots & 1 \end{array} \right]\nonumber \] Це добуток елементарних матриць, які вносять зміни лише в першому стовпчику. Це рівнозначно\(-a_{21}/a_{11}\) зняттю разів першого ряду і додаванню до другого. Потім\(-a_{31}/a_{11}\) беремо раз перший ряд і додаємо до третього і так далі. Коефіцієнти в першому стовпці наведеної вище матриці є множниками. Таким чином, результат має вигляд\[E_{1}A=\left[ \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n}^{\prime } \\ 0 & a_{22}^{\prime } & \cdots & a_{2n}^{\prime } \\ \vdots & \vdots & & \vdots \\ 0 & a_{m2}^{\prime } & \cdots & a_{mn}^{\prime } \end{array} \right]\nonumber \] За припущенням,\(a_{22}^{\prime }\neq 0\) і тому можна використовувати цей запис для обнулення всіх записів під ним в матриці праворуч шляхом множення на матрицю виду,\(E_{2}=\left[ \begin{array}{cc} 1 & \mathbf{0} \\ \mathbf{0} & E \end{array} \right]\) де\(E\) \(\left[ m-1\right] \times \left[ m-1\right]\)матриця форми\[E=\left[ \begin{array}{cccc} 1 & 0 & \cdots & 0 \\ -\frac{a_{32}^{\prime }}{a_{22}^{\prime }} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ -\frac{a_{m2}^{\prime }}{a_{22}^{\prime }} & 0 & \cdots & 1 \end{array} \right]\nonumber \] Знову ж таки, записи в першому стовпці під 1 є множниками. Продовжуючи цей шлях, обнулення записів нижче діагональних записів, нарешті, призводить до того,\[E_{m-1}E_{n-2}\cdots E_{1}A=U\nonumber \] де\(U\) знаходиться верхній трикутний. Кожен\(E_{j}\) має всі вниз по основній діагоналі і нижче трикутної. Тепер помножте обидві сторони на зворотні\(E_{j}\) у зворотному порядку.\(.\) Це дає\[A=E_{1}^{-1}E_{2}^{-1}\cdots E_{m-1}^{-1}U\nonumber \] Лемма\(\PageIndex{1}\), це означає, що добуток тих\(E_{j}^{-1}\) є нижчою трикутною матрицею, що має всі вниз по головній діагоналі. .

Наведене вище обговорення і лема дає обґрунтування методу мультиплікатора. Вирази,\[\frac{-a_{21}}{a_{11}},\frac{-a_{31}}{a_{11}},\cdots, \frac{-a_{m1}}{a_{11}}\nonumber \] позначені відповідно\(M_{21},\cdots ,M_{m1}\) для збереження позначення, які були отримані при побудові\(E_{1}\), є множниками. Тоді відповідно до леми, знайти\(E_{1}^{-1}\) вас просто пишіть\[\left[ \begin{array}{cccc} 1 & 0 & \cdots & 0 \\ -M_{21} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ -M_{m1} & 0 & \cdots & 1 \end{array} \right]\nonumber \] Подібні міркування застосовуються до іншого.\(E_{j}^{-1}.\) Таким чином,\(L\) є добутком форми\[\left[ \begin{array}{cccc} 1 & 0 & \cdots & 0 \\ -M_{21} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ -M_{m1} & 0 & \cdots & 1 \end{array} \right] \cdots \left[ \begin{array}{cccc} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & 0 & \ddots & \vdots \\ 0 & \cdots & -M_{m\left[ m-1\right] } & 1 \end{array} \right]\nonumber \] кожен фактор, що має максимум один ненульовий стовпець, положення якого рухається зліва на праворуч при скануванні вищевказаного добутку матриць зліва направо. З того, що ми знаємо про ефект множення зліва на елементарну матрицю, випливає, що вищевказаний твір має вигляд.\[\left[ \begin{array}{ccccc} 1 & 0 & \cdots & 0 & 0 \\ -M_{21} & 1 & \cdots & 0 & 0 \\ \vdots & -M_{32} & \ddots & \vdots & \vdots \\ -M_{\left[ m-1\right] 1} & \vdots & \cdots & 1 & 0 \\ -M_{m1} & -M_{m2} & \cdots & -M_{m\left[m-1\right]} & 1 \end{array} \right]\nonumber \]

У словах, починаючи з лівого стовпця і рухаючись до правого, ви просто вставляєте, у відповідне положення в матриці ідентичності,\(-1\) раз множник, який був використаний для обнулення запису в цьому положенні нижче основної діагоналі,\(A,\) зберігаючи при цьому основна діагональ, яка повністю складається з них. Це\(L.\)