5.4: Розкладання LU

Last updated
Save as PDF

Page ID: 79629

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Варіант алгоритму гаусової елімінації може бути використаний для обчислення розкладання LU матриці. Цю процедуру придумав Алан Тьюринг, британський математик вважав «батьком інформатики». Розкладання LU квадратної матриці\(\mathbf{A}\) складається з нижньотрикутної матриці\(\mathbf{L}\) і верхньо-трикутної матриці\(\mathbf{U}\), така, що

\[\mathbf{A} = \mathbf{L}\, \mathbf{U}.\]

За певних особливих обставин розклади LU забезпечують дуже ефективний метод розв'язання лінійних рівнянь. Припустимо, що ми повинні вирішити набір лінійних рівнянь\(\mathbf{A} \vec{x} = \vec{b}\) багато разів, використовуючи те ж,\(\mathbf{A}\) але\(\vec{b}\) невизначене число з, які можуть бути невідомі заздалегідь. Наприклад, вони можуть представляти нескінченну серію результатів вимірювань,\(\mathbf{A}\) представляючи певну фіксовану експериментальну конфігурацію.\(\vec{b}\) Ми хотіли б ефективно розрахувати\(\vec{x}\) для кожного\(\vec{b}\), що надходить. Якщо це буде зроблено за допомогою гаусової елімінації, кожен розрахунок потребує\(O(N^{3})\) часу.

Однак якщо ми зможемо виконати розкладання LU завчасно, то розрахунки можна виконати набагато швидше. Лінійні рівняння є

\[\mathbf{L}\, \mathbf{U} \vec{x} = \vec{b}.\]

Це можна розбити на два окремих рівняння:

\[\mathbf{L}\, \vec{y} = \vec{b}, \quad \mathrm{and}\;\;\; \mathbf{U} \vec{x} = \vec{y}.\]

Оскільки\(\mathbf{L}\) нижньо-трикутне, ми можемо вирішити перше рівняння шляхом прямої підстановки (подібно до зворотної заміни, за винятком того, що воно йде від першого рядка до останнього), щоб знайти\(\vec{y}\). Тоді ми можемо вирішити друге рівняння шляхом зворотної підстановки, щоб знайти\(\vec{x}\). Весь процес вимагає\(O(N^{2})\) часу, що є величезним поліпшенням у порівнянні з виконанням оптової гаусової елімінації.

Однак пошук розкладання LU вимагає\(O(N^{3})\) часу (ми не будемо вдаватися в деталі тут, але це в основному варіант фази скорочення рядків алгоритму гаусової елімінації). Тому, якщо ми зацікавлені у вирішенні лінійних рівнянь лише один раз або кілька разів, метод розкладання LU не покращує продуктивність. Це корисно в ситуаціях, коли розкладання LU виконується достроково. Ви можете думати про розкладання LU як спосіб переупорядкування алгоритму гаусової елімінації, так що нам не потрібно знати\(\vec{b}\) під час першої, дорогої\(O(N^{3})\) фази.

У Python ви можете виконати розкладання LU за допомогою функції scipy.linalg.lu. Кроки підстановки вперед та зворотної заміни можуть бути виконані за допомогою scipy.linalg.solve_triangular.