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.$