7: Метод розкладання LU для розв'язання одночасних лінійних рівнянь
- Page ID
- 105566
Після успішного завершення цього розділу, ви повинні мати можливість
- розв'язувати множину одночасних лінійних рівнянь методом розкладання LU
- розкласти несингулярну матрицю на форму LU.
- розв'язувати множину одночасних лінійних рівнянь методом розкладання LU
- розкласти несингулярну матрицю на форму LU.
- знайти зворотну матрицю за допомогою методу розкладання LU.
- обґрунтувати, чому використання методу розкладання LU є більш ефективним, ніж гаусова елімінація в деяких випадках.
Я чую про розкладання LU, який використовується як метод розв'язання безлічі одночасних лінійних рівнянь. Що це таке?
Ми вже вивчали два чисельні методи пошуку розв'язку одночасних лінійних рівнянь — елімінація Наївного Гауса та Гауссова елімінація з частковим поворотом. Тоді навіщо нам вивчати інший метод? Щоб оцінити, чому розкладання LU може бути кращим вибором, ніж методи усунення Гаусса в деяких випадках, давайте спочатку обговоримо, що таке розкладання LU.
Для несингулярної матриці,\(\left\lbrack A \right\rbrack\) на якій можна успішно проводити кроки ліквідації Наївного Гауса, завжди можна записати її як
\[\left\lbrack A \right\rbrack = \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack \nonumber \]
де
\[\left\lbrack L \right\rbrack = \text{Lower triangular matrix} \nonumber \]
\[\left\lbrack U \right\rbrack = \text{Upper triangular matrix} \nonumber \]
Тоді, якщо один вирішує набір рівнянь
\[\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack, \nonumber \]
потім
\[\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack\ \text{as }\left( \lbrack A\rbrack = \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack \right) \nonumber \]
Множимо обидві сторони на\(\left\lbrack L \right\rbrack^{- 1}\),
\[\left\lbrack L \right\rbrack^{- 1}\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack L \right\rbrack^{- 1}\left\lbrack C \right\rbrack \nonumber \]
\[\left\lbrack I \right\rbrack \left\lbrack U \right\rbrack \left\lbrack X \right\rbrack = \left\lbrack L \right\rbrack^{- 1}\left\lbrack C \right\rbrack\ \text{as }\left( \left\lbrack L \right\rbrack^{- 1}\left\lbrack L \right\rbrack = \lbrack I\rbrack \right) \nonumber \]
\[\left\lbrack U \right\rbrack \left\lbrack X \right\rbrack = \left\lbrack L \right\rbrack^{- 1}\left\lbrack C \right\rbrack\ \text{as }\left( \left\lbrack I \right\rbrack\ \left\lbrack U \right\rbrack = \lbrack U\rbrack \right) \nonumber \]
Нехай
\[\left\lbrack L \right\rbrack^{- 1}\left\lbrack C \right\rbrack = \left\lbrack Z \right\rbrack \nonumber \]
потім
\[\left\lbrack L \right\rbrack\left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack\ \ \ (1) \nonumber \]
і
\[\left\lbrack U \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack Z \right\rbrack\ \ \ (2) \nonumber \]
Таким чином, ми можемо вирішити Equation (1) спочатку за\(\lbrack Z\rbrack\) допомогою прямої підстановки, а потім використовувати Equation (2) для обчислення вектора рішення\(\left\lbrack X \right\rbrack\) шляхом зворотної підстановки.
Як розкласти несингулярну матрицю [A], тобто як знайти [A] = [L] [U]?
Якщо на несингулярній матриці можуть бути застосовані кроки ліквідації наївного Гаусса, то\(\left\lbrack A \right\rbrack\) їх можна розкласти на LU як
\[\begin{split} \lbrack A\rbrack &= \begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \cdots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{bmatrix}\\ &= \begin{bmatrix} 1 & 0 & \ldots & 0 \\ {l}_{21} & 1 & \cdots & 0 \\ \vdots & \vdots & \cdots & \vdots \\ {l}_{n1} & {l}_{n2} & \cdots & 1 \\ \end{bmatrix}\ \ \begin{bmatrix} u_{11} & u_{12} & \ldots & u_{1n} \\ 0 & u_{22} & \cdots & u_{2n} \\ \vdots & \vdots & \cdots & \vdots \\ 0 & 0 & \cdots & u_{nn} \\ \end{bmatrix} \end{split} \nonumber \]
Елементи\(\left\lbrack U \right\rbrack\) матриці точно такі ж, як і матриця коефіцієнтів, яку отримують наприкінці кроків ліквідації вперед в ліквідації Наївного Гауса.
Нижня трикутна матриця\(\left\lbrack L \right\rbrack\) має\(1\) в своїй діагоналі записи. Ненульові елементи на недіагональних елементах в\(\left\lbrack L \right\rbrack\) є множниками, які зробили відповідні записи нулем у верхній трикутній матриці\(\left\lbrack U\right\rbrack\) при прямому усуненні.
Давайте розглянемо це на тому ж прикладі, який використовується в наївній гауссівській елімінації.
Знайти LU розкладання матриці
\[\left\lbrack A \right\rbrack = \begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix} \nonumber \]
Рішення
\[\begin{split} \left\lbrack A \right\rbrack &= \left\lbrack L \right\rbrack \left\lbrack U \right\rbrack\\ &= \begin{bmatrix} 1 & 0 & 0 \\ {l}_{21} & 1 & 0 \\ {l}_{31} & {l}_{32} & 1 \\ \end{bmatrix}\begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \\ \end{bmatrix} \end{split} \nonumber \]
\(\left\lbrack U \right\rbrack\)Матриця така ж, як і в кінці прямої ліквідації методу ліквідації Наївного Гауса, тобто
\[\left\lbrack U \right\rbrack = \begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix} \nonumber \]
Знайти\({l}_{21}\) і\({l}_{31}\), знайти множник, який був використаний для того, щоб зробити\(a_{21}\) і\(a_{31}\) елементи нуль на першому кроці вперед ліквідації методу наївного Гаусса. Це було
\[\begin{split} {l}_{21} &= \frac{64}{25}\\ &= 2.56 \end{split} \nonumber \]
\[\begin{split} {l}_{31} &= \frac{144}{25}\\ &= 5.76 \end{split} \nonumber \]
Щоб знайти\({l}_{32}\), який множник був використаний, щоб зробити\(a_{32}\) елемент нуль? Пам'ятайте\(a_{32}\) елемент був зроблений нулем на другому кроці ліквідації вперед. \(\left\lbrack A \right\rbrack\)Матриця на початку другого кроку ліквідації вперед була
\[\begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & - 16.8 & - 4.76 \\ \end{bmatrix} \nonumber \]
Так
\[\begin{split} {l}_{32} &= \frac{- 16.8}{- 4.8}\\ &= 3.5 \end{split} \nonumber \]
Звідси
\[\left\lbrack L \right\rbrack = \begin{bmatrix} 1 & 0 & 0 \\ 2.56 & 1 & 0 \\ 5.76 & 3.5 & 1 \\ \end{bmatrix} \nonumber \]
Підтвердити\(\left\lbrack L \right\rbrack \left\lbrack U \right\rbrack = \left\lbrack A \right\rbrack\).
\[\begin{split} \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack &= \begin{bmatrix} 1 & 0 & 0 \\ 2.56 & 1 & 0 \\ 5.76 & 3.5 & 1 \\ \end{bmatrix}\begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix}\\ &= \begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix} \end{split} \nonumber \]
Використовуйте метод розкладання LU для вирішення наступних одночасних лінійних рівнянь.
\[\begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix}\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 106.8 \\ 177.2 \\ 279.2 \\ \end{bmatrix} \nonumber \]
Рішення
Нагадаємо, що
\[\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack \nonumber \]
і якщо
\[\left\lbrack A \right\rbrack = \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack \nonumber \]
потім спочатку розв'язуючи
\[\left\lbrack L \right\rbrack\left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack \nonumber \]
а потім
\[\left\lbrack U \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack Z \right\rbrack \nonumber \]
дає вектор розв'язку\(\left\lbrack X \right\rbrack\).
Тепер в попередньому прикладі ми показали
\[\begin{split} \left\lbrack A \right\rbrack &= \left\lbrack L \right\rbrack \left\lbrack U \right\rbrack\\ &=\begin{bmatrix} 1 & 0 & 0 \\ 2.56 & 1 & 0 \\ 5.76 & 3.5 & 1 \\ \end{bmatrix}\begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix} \end{split} \nonumber \]
Спочатку вирішуйте
\[\left\lbrack L \right\rbrack\ \left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack \nonumber \]
\[\begin{bmatrix} 1 & 0 & 0 \\ 2.56 & 1 & 0 \\ 5.76 & 3.5 & 1 \\ \end{bmatrix}\begin{bmatrix} z_{1} \\ z_{2} \\ z_{3} \\ \end{bmatrix} = \begin{bmatrix} 106.8 \\ 177.2 \\ 279.2 \\ \end{bmatrix} \nonumber \]
подарувати
\[z_{1} = 106.8 \nonumber \]
\[2.56z_{1} + z_{2} = 177.2 \nonumber \]
\[5.76z_{1} + 3.5z_{2} + z_{3} = 279.2 \nonumber \]
Заміна вперед, починаючи з першого рівняння, дає
\[z_{1} = 106.8 \nonumber \]
\[\begin{split} z_{2} &= 177.2 - 2.56z_{1}\\ &= 177.2 - 2.56 \times 106.8\\ &= - 96.208 \end{split} \nonumber \]
\[\begin{split} z_{3} &= 279.2 - 5.76z_{1} - 3.5z_{2}\\ &= 279.2 - 5.76 \times 106.8 - 3.5 \times \left( - 96.208 \right)\\ &= 0.76 \end{split} \nonumber \]
Звідси
\[\begin{split} \left\lbrack Z \right\rbrack &= \begin{bmatrix} z_{1} \\ z_{2} \\ z_{3} \\ \end{bmatrix}\\ &= \begin{bmatrix} 106.8 \\ - 96.208 \\ 0.76 \\ \end{bmatrix} \end{split} \nonumber \]
Ця матриця така ж, як і права сторона, отримана в кінці поступових етапів ліквідації методу наївного Гаусса. Це збіг обставин?
Тепер вирішуйте
\[\left\lbrack U \right\rbrack \left\lbrack X \right\rbrack = \left\lbrack Z \right\rbrack \nonumber \]
\[\begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix}\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 106.8 \\ - 96.208 \\ 0.76 \\ \end{bmatrix} \nonumber \]
\[25a_{1} + 5a_{2} + a_{3} = 106.8 \nonumber \]
\[- 4.8a_{2} - 1.56a_{3} = - 96.208 \nonumber \]
\[0.7a_{3} = 0.76 \nonumber \]
З третього рівняння
\[0.7a_{3} = 0.76 \nonumber \]
\[\begin{split} a_{3} &= \frac{0.76}{0.7}\\ &= 1.0857\end{split} \nonumber \]
Підставивши значення\(a_{3}\) в другому рівнянні,
\[- 4.8a_{2} - 1.56a_{3} = - 96.208 \nonumber \]
\[\begin{split} a_{2} &= \frac{- 96.208 + 1.56a_{3}}{- 4.8}\\ &= \frac{- 96.208 + 1.56 \times 1.0857}{- 4.8}\\ &= 19.691 \end{split} \nonumber \]
Підставляючи значення\(a_{2}\) і\(a_{3}\) в першому рівнянні,
\[25a_{1} + 5a_{2} + a_{3} = 106.8 \nonumber \]
\[\begin{split} a_{1} &= \frac{106.8 - 5a_{2} - a_{3}}{25}\\ &= \frac{106.8 - 5 \times 19.691 - 1.0857}{25}\\ &= 0.29048 \end{split} \nonumber \]
Звідси вектор розв'язку
\[\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 0.29048 \\ 19.691 \\ 1.0857 \\ \end{bmatrix} \nonumber \]
Як знайти зворотну квадратну матрицю за допомогою розкладання LU?
Матриця\(\left\lbrack B \right\rbrack\) є оберненою\(\left\lbrack A \right\rbrack\) if
\[\left\lbrack A \right\rbrack\left\lbrack B \right\rbrack = \left\lbrack I \right\rbrack = \left\lbrack B \right\rbrack\left\lbrack A \right\rbrack \nonumber \]
Як ми можемо використовувати розкладання LU, щоб знайти зворотну матрицю? Припустимо, що перший стовпець\(\left\lbrack B \right\rbrack\) (обернений\(\left\lbrack A \right\rbrack\)) є
\[\lbrack b_{11}\ b_{12}\ldots\ \ldots b_{n1}\rbrack^{T} \nonumber \]
Потім з наведеного вище визначення зворотного і визначення множення матриці
\[\left\lbrack A \right\rbrack\begin{bmatrix} b_{11} \\ b_{21} \\ \vdots \\ b_{n1} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \\ \end{bmatrix} \nonumber \]
Аналогічно, другий стовпець\(\left\lbrack B \right\rbrack\) задається
\[\left\lbrack A \right\rbrack\begin{bmatrix} b_{12} \\ b_{22} \\ \vdots \\ b_{n2} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ \vdots \\ 0 \\ \end{bmatrix} \nonumber \]
Аналогічно, всі стовпці\(\left\lbrack B \right\rbrack\) можна знайти, вирішуючи\(n\) різні набори рівнянь, причому стовпчик правого боку є\(n\) стовпцями матриці ідентичності.
Використовуйте розкладання LU, щоб знайти зворотне
\[\left\lbrack A \right\rbrack = \begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix} \nonumber \]
Рішення
Знаючи, що
\[\begin{split} \left\lbrack A \right\rbrack &= \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\\ &= \begin{bmatrix} 1 & 0 & 0 \\ 2.56 & 1 & 0 \\ 5.76 & 3.5 & 1 \\ \end{bmatrix}\begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix} \end{split} \nonumber \]
Ми можемо вирішити для першого стовпця,\(\lbrack B\rbrack = \left\lbrack A \right\rbrack^{- 1}\) вирішивши для
\[\begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix}\begin{bmatrix} b_{11} \\ b_{21} \\ b_{31} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ \end{bmatrix} \nonumber \]
Спочатку вирішуйте
\[\left\lbrack L \right\rbrack\left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack, \nonumber \]
тобто
\[\begin{bmatrix} 1 & 0 & 0 \\ 2.56 & 1 & 0 \\ 5.76 & 3.5 & 1 \\ \end{bmatrix}\begin{bmatrix} z_{1} \\ z_{2} \\ z_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ \end{bmatrix} \nonumber \]
подарувати
\[z_{1} = 1 \nonumber \]
\[2.56z_{1} + z_{2} = 0 \nonumber \]
\[5.76z_{1} + 3.5z_{2} + z_{3} = 0 \nonumber \]
Заміна вперед, починаючи з першого рівняння, дає
\[z_{1} = 1 \nonumber \]
\[\begin{split} z_{2} &= 0 - 2.56z_{1}\\ &= 0 - 2.56\left( 1 \right)\\ &= - 2.56 \end{split} \nonumber \]
\[\begin{split} z_{3} &= 0 - 5.76z_{1} - 3.5z_{2}\\ &= 0 - 5.76\left( 1 \right) - 3.5\left( - 2.56 \right)\\ &= 3.2 \end{split} \nonumber \]
Звідси
\[\begin{split} \left\lbrack Z \right\rbrack &= \begin{bmatrix} z_{1} \\ z_{2} \\ z_{3} \\ \end{bmatrix}\\ &= \begin{bmatrix} 1 \\ - 2.56 \\ 3.2 \\ \end{bmatrix} \end{split} \nonumber \]
Тепер вирішуйте
\[\left\lbrack U \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack Z \right\rbrack \nonumber \]
тобто
\[\begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix}\begin{bmatrix} b_{11} \\ b_{21} \\ b_{31} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ - 2.56 \\ 3.2 \\ \end{bmatrix} \nonumber \]
\[25b_{11} + 5b_{21} + b_{31} = 1 \nonumber \]
\[- 4.8b_{21} - 1.56b_{31} = - 2.56 \nonumber \]
\[0.7b_{31} = 3.2 \nonumber \]
Зворотна заміна, починаючи з третього рівняння, дає
\[\begin{split} b_{31} &= \frac{3.2}{0.7}\\ &= 4.571 \end{split} \nonumber \]
\[\begin{split} b_{21} &= \frac{- 2.56 + 1.56b_{31}}{- 4.8}\\ &= \frac{- 2.56 + 1.56(4.571)}{- 4.8}\\ &= - 0.9524 \end{split} \nonumber \]
\[\begin{split} b_{11} &= \frac{1 - 5b_{21} - b_{31}}{25}\\ &= \frac{1 - 5( - 0.9524) - 4.571}{25}\\ &= 0.04762 \end{split} \nonumber \]
Звідси перший стовпець зворотного\(\left\lbrack A \right\rbrack\) є
\[\begin{bmatrix} b_{11} \\ b_{21} \\ b_{31} \\ \end{bmatrix} = \begin{bmatrix} 0.04762 \\ - 0.9524 \\ 4.571 \\ \end{bmatrix} \nonumber \]
Аналогічно, рішення
\[\begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix}\begin{bmatrix} b_{12} \\ b_{22} \\ b_{32} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ \end{bmatrix}\ \text{gives }\begin{bmatrix} b_{12} \\ b_{22} \\ b_{32} \\ \end{bmatrix} = \begin{bmatrix} - 0.08333 \\ 1.417 \\ - 5.000 \\ \end{bmatrix} \nonumber \]
і рішення
\[\begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix}\begin{bmatrix} b_{13} \\ b_{23} \\ b_{33} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \\ \end{bmatrix}\ \text{gives }\begin{bmatrix} b_{13} \\ b_{23} \\ b_{33} \\ \end{bmatrix} = \begin{bmatrix} 0.03571 \\ - 0.4643 \\ 1.429 \\ \end{bmatrix} \nonumber \]
Звідси
\[\left\lbrack A \right\rbrack^{- 1} = \begin{bmatrix} 0.04762 & - 0.08333 & 0.03571 \\ - 0.9524 & 1.417 & - 0.4643 \\ 4.571 & - 5.000 & 1.429 \\ \end{bmatrix} \nonumber \]
Чи можете ви підтвердити наступне для наведеного вище прикладу?
\[\left\lbrack A \right\rbrack\ \left\lbrack A \right\rbrack^{- 1} = \left\lbrack I \right\rbrack = \left\lbrack A \right\rbrack^{- 1}\left\lbrack A \right\rbrack \nonumber \]
Розпад ЛУ виглядає складніше, ніж гаусова елімінація. Чи використовуємо ми розкладання LU, оскільки вона обчислювально-більш ефективна, ніж гаусова елімінація, щоб вирішити набір n рівнянь, заданих\(\mathbf{[A][X]=[C]}\)?
Для\(\lbrack A\rbrack\) квадратної матриці\(n \times n\) розміру обчислювальний час [^1]\(CT|_{DE}\) для розкладання\(\lbrack A\rbrack\) матриці до\(\lbrack L\rbrack\lbrack U\rbrack\) форми задається
\[CT|_{DE} = T\left( \frac{8n^{3}}{3} + 4n^{2} - \frac{20n}{3} \right), \nonumber \]
де
\[T = \text{clock cycle time}^{2} \nonumber \]
Обчислювальний час\(CT|_{FS}\) для вирішення шляхом прямої підстановки\(\left\lbrack L \right\rbrack\left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack\) задається
\[CT|_{FS} = T\left( 4n^{2} - 4n \right) \nonumber \]
Обчислювальний час\(CT|_{BS}\) для вирішення шляхом зворотної заміщення\(\left\lbrack U \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack Z \right\rbrack\) задається
\[CT|_{BS} = T\left( 4n^{2} + 12n \right) \nonumber \]
Отже, сумарний обчислювальний час для вирішення множини рівнянь шляхом розкладання LU дорівнює
\[\begin{split} {CT|}_{LU} &= {CT|}_{DE} + {CT|}_{FS} + {CT|}_{BS}\\ &= T\left( \frac{8n^{3}}{3} + 4n^{2} - \frac{20n}{3} \right) + T\left( 4n^{2} - 4n \right) + T\left( 4n^{2} + 12n \right)\\ &= T\left( \frac{8n^{3}}{3} + 12n^{2} + \frac{4n}{3} \right) \end{split} \nonumber \]
Тепер давайте подивимося на обчислювальний час, який займає гауссова елімінація. Обчислювальний час\(CT|_{FE}\) для прямої частини ліквідації,
\[{CT|}_{FE} = T\left( \frac{8n^{3}}{3} + 8n^{2} - \frac{32n}{3} \right), \nonumber \]
і обчислювальний час\(CT|_{BS}\) для задньої частини заміщення
\[{CT|}_{BS} = T\left( 4n^{2} + 12n \right) \nonumber \]
Отже, сумарний обчислювальний час\(CT|_{GE}\) для вирішення множини рівнянь методом гаусової елімінації дорівнює
\[\begin{split} {CT|}_{GE} &= {CT|}_{FE} + {CT|}_{BS}\\ &= T\left( \frac{8n^{3}}{3} + 8n^{2} - \frac{32n}{3} \right) + T\left( 4n^{2} + 12n \right)\\ &= T\left( \frac{8n^{3}}{3} + 12n^{2} + \frac{4n}{3} \right) \end{split} \nonumber \]
Розрахунковий час гаусової елімінації та розкладання LU ідентичний.
Це мене заплутало далі! Чому я повинен вивчати метод розкладання LU, коли він займає той же обчислювальний час, що і гаусова елімінація, і це теж, коли два методи тісно пов'язані? Будь ласка, переконайте мене, що розкладання LU має своє місце у вирішенні лінійних рівнянь!
Тепер ми маємо знання, щоб переконати вас, що метод розкладання LU має своє місце у вирішенні одночасних лінійних рівнянь. Давайте розглянемо приклад, де метод розкладання LU обчислювально-ефективніший, ніж гаусова елімінація. Пам'ятайте, намагаючись знайти зворотну матрицю\(\lbrack A\rbrack\) в розділі 04.01, задача зводиться до розв'язання\(n\) множин рівнянь зі\(n\) стовпцями матриці ідентичності як вектора RHS. Для розрахунків кожного стовпця зворотної матриці коефіцієнт\(\lbrack A\rbrack\) матриці\(\lbrack A\rbrack\) матриці в множині рівняння\(\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack\) не змінюється. Отже, якщо ми використовуємо метод розкладання LU,\(\left\lbrack A \right\rbrack = \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) розкладання потрібно зробити лише один раз, пряму підстановку (Equation 1)\(n\) раз та зворотну підстановку (Equation 2)\(n\) раз.
Отже, загальний обчислювальний час,\(CT|_{inverse\ {LU}}\) необхідний для знаходження зворотної матриці за допомогою розкладання LU, становить
\[\begin{split} {CT|}_{inverse\ {LU}} &= 1 \times {CT|}_{DE} + n \times {CT|}_{FS} + n \times {CT|}_{BS}\\ &= 1 \times T\left( \frac{8n^{3}}{3} + 4n^{2} - \frac{20n}{3} \right) + n \times T\left( 4n^{2} - 4n \right) + n \times T\left( 4n^{2} + 12n \right)\\ &= T\left( \frac{32n^{3}}{3} + 12n^{2} - \frac{20n}{3} \right) \end{split} \nonumber \]
Для порівняння, якщо метод гаусової елімінації використовувався для пошуку зворотної матриці, то ліквідацію вперед, а також зворотну заміну доведеться виконати n разів. Загальний обчислювальний час,\({CT|}_{inverse\ {GE}}\) необхідний для пошуку зворотної матриці за допомогою гаусової елімінації, тоді дорівнює
\[\begin{split} {CT|}_{inverse\ {GE}} &= n \times {CT|}_{FE} + n \times {CT|}_{BS}\\ &= n \times T\left( \frac{8n^{3}}{3} + 8n^{2} - \frac{32n}{3} \right) + n \times T\left( 4n^{2} + 12n \right)\\ &= T\left( \frac{8n^{4}}{3} + 12n^{3} + \frac{4n^{2}}{3} \right) \end{split} \nonumber \]
Очевидно\(n\), що для великих,\({CT|}_{inverse\ {GE}} >>{CT|}_{inverse\ {LU}}\) як\({CT|}_{inverse\ {GE}}\) і домінуючі умови\(n^{4}\) і\({CT|}_{inverse\ {LU}}\) має домінуючі умови\(n^{3}\). Для великих значень\(n\), метод гаусової елімінації займе більше обчислювального часу (приблизно в\(n/4\) рази — довести це), ніж метод розкладання LU. Типові значення відношення обчислювального часу для різних значень\(n\) наведені в таблиці 1.
| \(n\) | \(10\) | \(100\) | \(1000\) | \(10000\) |
|---|---|---|---|---|
| \ (n\) ">\({CT|}_{inverse\ {GE}}/{CT|}_{inverse\ {LU}}\) | \ (10\) ">\(3.28\) | \ (100\) ">\(25.83\) | \ (1000\) ">\(250.8\) | \ (10000\) ">\(2501\) |
Чи переконані ви зараз, що розкладання LU має своє місце у вирішенні систем рівнянь, коли нам доводиться вирішувати декілька векторів правого боку, тоді як матриця коефіцієнтів залишається незмінною?
Час обчислюється спочатку окремо обчисленням кількості додавань, віднімань, множень та поділів у такій процедурі, як зворотна заміна тощо Потім ми припускаємо 4 тактових циклів кожен для операції додавання, віднімання або множення та 16 тактових циклів для операції ділення, як це відбувається для типовий чіп AMD® -K7.
http://www.isi.edu/~draper/papers/mwscas07_kwon.pdf
Метод розкладання LU для розв'язання одночасних лінійних рівнянь
Метод\(\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) розкладання обчислювально-ефективніший, ніж ліквідація Наївного Гауса для розв'язання
(А). єдиний набір одночасних лінійних рівнянь.
(B). множинні набори одночасних лінійних рівнянь з різними матрицями коефіцієнтів і однаковими правими векторами.
(C). множинні набори одночасних лінійних рівнянь з однаковою матрицею коефіцієнтів та різними правими векторами.
(D). менше десяти одночасних лінійних рівнянь.
Нижня трикутна матриця\(\left\lbrack L \right\rbrack\) в\(\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) розкладанні матриці наведено нижче
\[\begin{bmatrix} 25 & 5 & 4 \\ 10 & 8 & 16 \\ 8 & 12 & 22 \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ \mathcal{l}_{21} & 1 & 0 \\ \mathcal{l}_{31} & \mathcal{l}_{32} & 1 \\ \end{bmatrix}\begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \\ \end{bmatrix} \nonumber \]є
(А)\(\begin{bmatrix} 1 & 0 & 0 \\ 0.40000 & 1 & 0 \\ 0.32000 & 1.7333 & 1 \\ \end{bmatrix}\)
(Б)\(\begin{bmatrix} 25 & 5 & 4 \\ 0 & 6 & 14.400 \\ 0 & 0 & - 4.2400 \\ \end{bmatrix}\)
(С)\(\begin{bmatrix} 1 & 0 & 0 \\ 10 & 1 & 0 \\ 8 & 12 & 0 \\ \end{bmatrix}\)
(D)\(\begin{bmatrix} 1 & 0 & 0 \\ 0.40000 & 1 & 0 \\ 0.32000 & 1.5000 & 1 \\ \end{bmatrix}\)
Верхня трикутна матриця\(\left\lbrack U \right\rbrack\) в\(\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) розкладанні матриці наведено нижче
\[\begin{bmatrix} 25 & 5 & 4 \\ 0 & 8 & 16 \\ 0 & 12 & 22 \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ \mathcal{l}_{21} & 1 & 0 \\ \mathcal{l}_{31} & \mathcal{l}_{32} & 1 \\ \end{bmatrix}\begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \\ \end{bmatrix} \nonumber \]
є
(А)\(\begin{bmatrix} 1 & 0 & 0 \\ 0.40000 & 1 & 0 \\ 0.32000 & 1.7333 & 1 \\ \end{bmatrix}\)
(Б)\(\begin{bmatrix} 25 & 5 & 4 \\ 0 & 6 & 14.400 \\ 0 & 0 & - 4.2400 \\ \end{bmatrix}\)
(С)\(\begin{bmatrix} 25 & 5 & 4 \\ 0 & 8 & 16 \\ 0 & 0 & - 2 \\ \end{bmatrix}\)
(D)\(\begin{bmatrix} 1 & 0.2000 & 0.16000 \\ 0 & 1 & 2.4000 \\ 0 & 0 & - 4.240 \\ > \end{bmatrix}\)
Для заданої матриці\(\times\) 2000 2000\(\left\lbrack A \right\rbrack\), припустимо, що потрібно близько 15 секунд, щоб знайти зворотне\(\left\lbrack A \right\rbrack\) за допомогою методу\(\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) розкладання, тобто знайти\(\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) один раз, а потім зробити пряму підстановку і зворотний\(2000\) час підстановки, використовуючи\(2000\) стовпці матриці ідентичності як вектор правого боку. Приблизний час, у секундах, який знадобиться, щоб знайти зворотний, якщо він знайдений шляхом багаторазового використання методу усунення Наївного Гауса, тобто виконання\(2000\) часу ліквідації вперед та зворотного підстановки, використовуючи\(2000\) стовпці матриці ідентичності як правої руки бічний вектор є найбільш майже
(А)\(300\)
(Б)\(1500\)
(С)\(7500\)
(D)\(30000\)
Алгоритм розв'язання множини\(n\) рівнянь\(\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack\), де\(\left\lbrack A \right\rbrack = \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) передбачає розв'язування\(\left\lbrack L \right\rbrack\left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack\) шляхом прямої підстановки. Алгоритм\(\left\lbrack L \right\rbrack\left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack\) розв'язання задається
(А)\(z_{1} = c_{1}/l_{11}\)
для\(i\) від 2\(n\) робити
сума = 0
для\(j\) від 1\(i\) робити
сума = сума +\(l_{\text{ij}}*z_{j}\)
кінець робити
\(z_{i} = (c_{i} - \text{sum})/l_{\text{ii}}\)
кінець робити
(Б)\(z_{1} = c_{1}/l_{11}\)
для\(i\) від 2\(n\) робити
сума = 0
для\(j\) від 1\((i - 1)\) робити
сума = сума +\(l_{\text{ij}}*z_{j}\)
кінець робити
\(z_{i} = (c_{i} - \text{sum})/l_{\text{ii}}\)
кінець робити
(С)\(z_{1} = c_{1}/l_{11}\)
для\(i\) від 2\(n\) робити
для\(j\) від 1\((i - 1)\) робити
сума = сума +\(l_{\text{ij}}*z_{j}\)
кінець робити
\(z_{i} = (c_{i} - \text{sum})/l_{\text{ii}}\)
кінець робити
(D) для\(i\) від 2\(n\) робити
сума = 0
для\(j\) від 1\((i - 1)\) робити
сума = сума +\(l_{\text{ij}}*z_{j}\)
кінець робити
\(z_{i} = (c_{i} - \text{sum})/l_{\text{ii}}\)
кінець робити
Для розв'язання крайових задач використовується числовий метод, заснований на методі скінченних різниць. Це призводить до одночасних лінійних рівнянь з тридіагональними матрицями коефіцієнтів. Вони вирішуються за допомогою спеціалізованого методу\(\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) розкладання.
Виберіть набір рівнянь, який приблизно вирішує крайову задачу
\[\frac{d^{2}y}{dx^{2}} = 6x - 0.5x^{2},\ \ y\left( 0 \right) = 0,\ \ y\left( 12 \right) = 0,\ \ 0 \leq x \leq 12 \nonumber \]
Друга похідна у вищевказаному рівнянні апроксимується точним центральним поділеним різницевим наближенням другого порядку, як це вивчено в модулі диференціювання (Глава 02.02). \(h = 4\)Використовується розмір кроку, і, отже, значення y можна знайти приблизно на рівновіддалених 4 вузлах між\(x = 0\) і\(x = 12\).
(А)\(\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0.0625 & 0.125 & 0.0625 & 0 \\ 0 & 0.0625 & 0.125 & 0.0625 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}\begin{bmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 16.0 \\ 16.0 \\ 0 \\ \end{bmatrix}\)
(Б)\(\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0.0625 & - 0.125 & 0.0625 & 0 \\ 0 & 0.0625 & - 0.125 & 0.0625 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}\begin{bmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 16.0 \\ 16.0 \\ 0 \\ \end{bmatrix}\)
(С)\(\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0.0625 & - 0.125 & 0.0625 & 0 \\ 0 & 0.0625 & - 0.125 & 0.0625 \\ \end{bmatrix}\begin{bmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 16.0 \\ 16.0 \\ 0 \\ \end{bmatrix}\)
(D)\(\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0.0625 & 0.125 & 0.0625 & 0 \\ 0 & 0.0625 & 0.125 & 0.0625 \\ \end{bmatrix}\begin{bmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 16.0 \\ 16.0 \\ \end{bmatrix}\)
Метод розкладання LU для розв'язання одночасних лінійних рівнянь
Показати, що розкладання LU є більш ефективним способом знаходження зворотної квадратної матриці, ніж використання гаусової елімінації.
Використовуйте розкладання LU, щоб знайти [L] та [U]
\[4x_{1} + x_{2} - x_{3} = - 2 \nonumber \]\[5x_{1} + x_{2} + 2x_{3} = 4 \nonumber \]\[6x_{1} + x_{2} + x_{3} = 6 \nonumber \]
Знайти зворотне
\[\lbrack A\rbrack = \begin{bmatrix} 3 & 4 & 1 \\ 2 & - 7 & - 1 \\ 8 & 1 & 5 \\ \end{bmatrix} \nonumber \]
за допомогою розкладання LU.
Заповніть пропуски для невідомих у розкладанні LU матриці, наведеної нижче
\[\begin{bmatrix} 25 & 5 & 4 \\ 75 & 7 & 16 \\ 12.5 & 12 & 22 \\ \end{bmatrix} = \begin{bmatrix} \mathcal{l}_{11} & 0 & 0 \\ \mathcal{l}_{21} & \mathcal{l}_{22} & 0 \\ \mathcal{l}_{31} & \mathcal{l}_{32} & \mathcal{l}_{33} \\ \end{bmatrix}\begin{bmatrix} 25 & 5 & 4 \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \\ \end{bmatrix} \nonumber \]
Показати, що несингулярна матриця
\[\left\lbrack A \right\rbrack = \begin{bmatrix} 0 & 2 \\ 2 & 0 \\ \end{bmatrix} \nonumber \]
не можна розкласти на форму LU.
Розпад LU
\[\lbrack A\rbrack = \begin{bmatrix} 4 & 1 & - 1 \\ 5 & 1 & 2 \\ 6 & 1 & 1 \\ \end{bmatrix} \nonumber \]
дається
\[\begin{bmatrix} 4 & 1 & - 1 \\ 5 & 1 & 2 \\ 6 & 1 & 1 \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 1.25 & 1 & 0 \\ 1.5 & 2 & 1 \\ \end{bmatrix}\begin{bmatrix} ?? & ?? & ?? \\ 0 & ?? & ?? \\ 0 & 0 & ?? \\ \end{bmatrix} \nonumber \]
Знайти верхню трикутну матрицю в наведеному вище розкладанні?