檢視 LU分解的原始碼

佇線性的代數佮數值分析中，'''LU 分解'''是矩陣分解的一種，將一个矩陣分解做一个下三角矩陣佮一个上三角矩陣的乘積，有當時仔需要閣乘頂一个置換矩陣。LU 分解會當予人看做是高斯消去法的矩陣的形式。佇咧數值計算上，LU 分解按呢經常予人用來解線性方程組、而且要求逆矩陣佮計算行列式中攏是一个關鍵的流程。

==定義==

對著方陣 $ A $，$ A $ 的'''LU 分解'''是將伊分解做一个下三角矩陣 L 佮上三角矩陣 U 的乘積，也就是講


: $ A=LU $

若適當的改變 $ A $ 行的順序抑是列的順序，就會當共 $ A $ 做 LU 分解。

比如講一个 $ 三 \ times 三 $ 矩陣 A，其實 LU 彼分解會去寫做下跤的形式：


: $ A={ \ begin { bmatrix } a _ { 十一 } & a _ { 十二 } & a _ { 十三 } \ \ a _ { 二十一 } & a _ { 二十二 } & a _ { 二十三 } \ \ a _ { 三十一 } & a _ { 三十二 } & a _ { 三十三 } \ \ \ end { bmatrix } }={ \ begin { bmatrix } l _ { 十一 } & 零 & 零 \ \ l _ { 二十一 } & l _ { 二十二 } & 零 \ \ l _ { 三十一 } & l _ { 三十二 } & l _ { 三十三 } \ \ \ end { bmatrix } } { \ begin { bmatrix } u _ { 十一 } & u _ { 十二 } & u _ { 十三 } \ \ 零 & u _ { 二十二 } & u _ { 二十三 } \ \ 零 & 零 & u _ { 三十三 } \ \ \ end { bmatrix } } $。

事實上，毋是每一个矩陣攏有 LU 分解。比如講，對上式會當知影講 $ a _ { 十一 }=l _ { 十一 } u _ { 十一 } $，若是 $ a _ { 十一 }=零 $，著 $ l _ { 十一 } $ 抑是 $ u _ { 十一 } $ 等於零，故 L 抑是 U 是可逆矩陣，A 著愛嘛是可逆矩陣。毋過，有可逆矩陣欲起來 A 滿足 $ a _ { 十一 }=零 $，這是 A 就是講無 LU 分解的例。該問題會當藉著改換 A 的各列順序來解決，終其尾會得著一个 A 的 PLU 分解。

===PLU 分解===

方陣 A 的'''PLU 分解'''是是共分解做一个置換矩陣 P、一个下三角矩陣 L 佮上三角矩陣 U 的乘積，即


: $ A=PLU $

事實上，所有的方陣攏會當寫做 PLU 分解的形式，因為倒乘置換矩陣 $ P ^ { 影一 } $ 是佇交換行的順序，所以由 $ P ^ { 影一 } A=LU $ 捒了適當的交換 A 走的順序，即可將 A 做 LU 分解。事實上，PLU 分解有誠懸的數值穩定性，所以實用的物件是足好用的。

有時為著計算上的方便，會仝時間換行佮列的順序，這个時陣會將 A 分解做


: $ A=PLUQ $

其中 P、L、U 同上，Q 是一个置換矩陣。

===LDU 分解===

方陣 A 的'''LDU 分解'''是是共分解做一个單位下三角矩陣 L、斜對角矩陣 D 佮單位上三角矩陣 U 的乘積，即


: $ A=LDU $

其中單位頂懸、下三角矩陣是講對角線頂懸攏是一的頂懸、下三角矩陣。

事實上，LDU 分解會當推廣到 A 是一般的矩陣，毋是方陣。現此時，L 和 D 是方陣，並且佮 A 有仝款的列，U 著愛和 A 仝款的長闊。注意到這馬 U 是頂三角的定義改做主對角線的下跤攏是零，啊若主對角線是收集所有 $ U _ { ij } $ 滿足 i=j。

==存在性佮唯一性==

一个可逆矩陣會當進行 _ LU _ 分解若而且唯若伊的所有的子式攏非常無。若是欲求其中的 _ L _ 矩陣（抑是 _ U _ 矩陣）為單位三角矩陣，是按呢分解唯一的。同理通知，矩陣的 _ LDU _ 會當分解條件嘛相仝，並且總是唯一的。

著算矩陣袂使顛倒，_ LU _ 猶閣有可能存在的。實際上，若一个秩為 _ k _ 矩陣的前 _ k _ 個順序主子式不為零，伊就會當進行 _ LU _ 分解，但反途抑無。

目前，佇咧任意域頂頭一个方塊矩陣會當進行 _ LU _ 分解充的條件已經予人發現講，遮的充要條件會當用某一寡特定子矩陣的秩表示。用高斯消去法來得著 _ LU _ 分解的算法嘛會當擴張到任域上。

任意矩陣 _ A _（毋但是方塊矩陣）攏會當進行 _ LUP _ 分解。內底的 _ L _ 和 _ U _ 矩陣是方陣，_ P _ 矩陣是佮 _ A _ 形仝款。

==正定矩陣==

如果矩陣 _ A _ 是埃爾米特矩陣，而且是正定矩陣，遐爾仔會使得，_ U _ 是 _ L _ 的共擔轉置。也就是講，_ A _ 會當寫做


: $ A=LL ^ { * } \ $

這个分解予人叫做 Cholesky 分解。著每一个正定矩陣，Cholesky 分解攏唯一存在。此外，比起一般的彼號 _ LU _ 分解，計算 Cholesky 分解閣較緊，並且有閣較懸的數值穩定性。

==具體的表達式==

因為 _ LDU _ 分解唯一存在，著予定的矩陣，會當予出相應三个矩陣 _ L _、_ D _ 和 _ U _ 的具體的表達式。表達式由 _ A _ 的主子式之比構成（所以要求𪜶無為零）。 設 $ d _ { 一 } , d _ { 二 } , \ cdots d _ { n } $ 為矩陣 _ D _ 的對角線係數，則有 $ d _ { 一 }=\ mathbf { A } _ { 一 , 一 } $。著 $ i=二 , \ ldots , n $，$ d _ { i } $ 的值等於 _ A _ 的第 $ i $ 順序主子式佮第 $ i 影一 $ 個順序主子式之比，其中約定 $ d _ { 零 } $=一。

==算法==

_ LU _ 分解佇本質上是高斯消去法的一種表達形式。實質上是將 _ A _ 通過初等行轉換變做一个上三角矩陣，其轉換矩陣就是一个單位下三角矩陣。這正正是咱所講的杜爾里特算法（Doolittle algorithm）： 對下至上地對矩陣 _ A _ 初等欲轉換，共對角線倒下跤的元素變做零，然後閣證明遮的行轉換的效果等仝款佇倒乘一系列單位下三角矩陣，伊這系列單位下三角矩陣的乘積的逆就是 L 矩陣，伊嘛是一个單位下三角矩陣。

這類算法的複雜度一般咧 $ { \ frac { 二 n ^ { 三 } } { 三 } } $ 左右，對充分消去的分解是無。

===杜爾里特算法===

著予定的 _ N _ × _ N _ 矩陣


: $ A=( a _ { n , n } ) $

有


: $ A ^ { ( 零 ) } :=A $

然後定義對 _ n _=一 , . . . , _ N 影一 _ 的狀況如下：

佇咧第 _ n _ 步，消去矩陣 _ A _ ( _ n 影一 _ ) 的第 _ n _ 列主對角線下跤的元素：將 _ A _ ( _ n 影一 _ ) 的第 _ n _ 行乘以 $ l _ { i , n } :=-{ \ frac { a _ { i , n } ^ { ( n 影一 ) } } { a _ { n , n } ^ { ( n 影一 ) } } } $ 了後加到第 _ i _ 行起去。其中 $ i=n + 一 , \ ldots , N $。

這相當於在 _ A _ ( _ n 影一 _ ) 的倒爿乘一个單位下三角矩陣：


: $ L _ { n }={ \ begin { bmatrix } 一 & & & & & 零 \ \ & \ ddots & & & & \ \ & & 一 & & & \ \ & & l _ { n + 一 , n } & \ ddots & & \ \ & & \ vdots & & \ ddots & \ \ 零 & & l _ { N , n } & & & 一 \ \ \ end { bmatrix } } $

所以，定義做：設


: $ A ^ { ( n ) } :=L _ { n } A ^ { ( n 影一 ) } $

經過 _ N 影一 _ 輪操作了後，所有咧主對角線下跤的係數攏為零矣，所以咱得著一个上三角矩陣：_ A _ ( _ N 影一 _ )，這陣就有：


: $ A=L _ { 一 } ^ { 影一 } L _ { 一 } A ^ { ( 零 ) }=L _ { 一 } ^ { 影一 } A ^ { ( 一 ) }=L _ { 一 } ^ { 影一 } L _ { 二 } ^ { 影一 } L _ { 二 } A ^ { ( 一 ) }=L _ { 一 } ^ { 影一 } L _ { 二 } ^ { 影一 } A ^ { ( 二 ) }=\ ldots=L _ { 一 } ^ { 影一 } \ ldots L _ { N 影一 } ^ { 影一 } A ^ { ( N 影一 ) } $

這陣，矩陣 _ A _ ( _ N 影一 _ ) 就是講 _ U _，$ L=L _ { 一 } ^ { 影一 } \ ldots L _ { N 影一 } ^ { 影一 } $。
下三角矩陣 $ L _ { k } $ 的逆猶原是下三角矩陣，而且下三角矩陣的乘積猶原是下三角矩陣，所以乎 $ L $ 是下三角矩陣。
所以咱得著分解：$ A=LU $。

顯然，彼款的成立，每一步咧操作的時陣必須愛有 $ a _ { n , n } ^ { ( n 影一 ) } \ neq 零 $。若是這條件無成立，就愛將第 _ n _ 行佮另外一逝交換，由此就會出現一个置換矩陣 _ P _。這就是為啥物一般來講 _ LU _ 分解里會帶閣有一个對換矩陣的原因。

==例==

共一个簡單的三 × 三矩陣 _ A _ 進行 LU 分解：


: $ A={ \ begin { bmatrix } 一 & 二 & 三 \ \ 二 & 五 & 七 \ \ 三 & 五 & 三 \ \ \ end { bmatrix } } $

先將矩陣第一列元素內底 a 十一以下的所有的元素變做零，即


: $ L _ { 一 } A={ \ begin { bmatrix } 一 & 零 & 零 \ \ 鋪二 & 一 & 零 \ \ ma三 & 零 & 一 \ \ \ end { bmatrix } } \ times { \ begin { bmatrix } 一 & 二 & 三 \ \ 二 & 五 & 七 \ \ 三 & 五 & 三 \ \ \ end { bmatrix } }={ \ begin { bmatrix } 一 & 二 & 三 \ \ 零 & 一 & 一 \ \ 零 & 影一 & ma六 \ \ \ end { bmatrix } } $

閣將矩陣第二列元素內底 a 二十二以下的所有的元素變做零，即


: $ L _ { 二 } ( L _ { 一 } A )={ \ begin { bmatrix } 一 & 零 & 零 \ \ 零 & 一 & 零 \ \ 零 & 一 & 一 \ \ \ end { bmatrix } } \ times { \ begin { bmatrix } 一 & 二 & 三 \ \ 零 & 一 & 一 \ \ 零 & 影一 & ma六 \ \ \ end { bmatrix } }={ \ begin { bmatrix } 一 & 二 & 三 \ \ 零 & 一 & 一 \ \ 零 & 零 & 鋪五 \ \ \ end { bmatrix } }=U $


: $ L=L _ { 一 } ^ { 影一 } L _ { 二 } ^ { 影一 }={ \ begin { bmatrix } 一 & 零 & 零 \ \ 二 & 一 & 零 \ \ 三 & 零 & 一 \ \ \ end { bmatrix } } \ times { \ begin { bmatrix } 一 & 零 & 零 \ \ 零 & 一 & 零 \ \ 零 & 影一 & 一 \ \ \ end { bmatrix } }={ \ begin { bmatrix } 一 & 零 & 零 \ \ 二 & 一 & 零 \ \ 三 & 影一 & 一 \ \ \ end { bmatrix } } $

猶閣有一種方法是通過方程式求解，如下所示，將以下矩陣進行 _ LU _ 分解：


: $ { \ begin { bmatrix } 四 & 三 \ \ 六 & 三 \ \ \ end { bmatrix } }={ \ begin { bmatrix } l _ { 十一 } & 零 \ \ l _ { 二十一 } & l _ { 二十二 } \ \ \ end { bmatrix } } { \ begin { bmatrix } u _ { 十一 } & u _ { 十二 } \ \ 零 & u _ { 二十二 } \ \ \ end { bmatrix } } $

因為矩陣的陣數只是二，會當直接列方程式解：


: $ l _ { 十一 } * u _ { 十一 } + 零 * 零=四 $


: $ l _ { 十一 } * u _ { 十二 } + 零 * u _ { 二十二 }=三 $


: $ l _ { 二十一 } * u _ { 十一 } + l _ { 二十二 } * 零=六 $


: $ l _ { 二十一 } * u _ { 十二 } + l _ { 二十二 } * u _ { 二十二 }=三 $

這個線性方程組有無數多組解。所以，會當假使其中一个是單位三角矩陣，譬論講 _ L _，也就是講其對角線頂懸的兩个係數攏是一。這个時陣會使解出講：


: $ l _ { 二十一 }=一垺五 $


: $ u _ { 十一 }=四 $


: $ u _ { 十二 }=三 $


: $ u _ { 二十二 }=抹一爿五 $。

也就是講


: $ { \ begin { bmatrix } 四 & 三 \ \ 六 & 三 \ \ \ end { bmatrix } }={ \ begin { bmatrix } 一 & 零 \ \ 一垺五 & 一 \ \ \ end { bmatrix } } { \ begin { bmatrix } 四 & 三 \ \ 零 & 抹一爿五 \ \ \ end { bmatrix } } $

==疏疏矩陣分解==

對階數真大的稀疏矩陣，有特別的簡便算法來得著其他 _ LU _ 分解：這陣的 _ L _ 和 _ U _ 原仔稀疏矩陣。理論起來講，算法的複雜度差不多等於非零係數的個數，毋是矩陣的大細階數。遮的算法通過運用行佮列的交換，予過程中零係數因為操作變做非零係數的次數減到上少。

一般的將零係數因為操作變做非零係數的次數減到上少的方法是運用圖論。

==應用==

===求解線性方程式===

著予定的線性方程組


: $ Ax=LUx=b \ , $

愛解出 _ x _，會當進行以下步：

一 . 首先，解方程式 $ Ly=b $ 得著 $ y $；
二 . 然後解方面程式 $ Ux=y $ 得著 $ x $。

佇兩改的求解中，咱拄著的攏三角矩陣，按呢運用向前（向後爿）替代法就會當簡潔地求解（參見三角矩陣）， 毋免用著高斯消去法。毋過，咧將 _ A _ 進行 _ LU _ 分解的時陣，猶閣愛用到高斯消去法。所以，這个方法適合佇咧愛對濟濟个無仝款的 b 求解的時陣用。

===求逆矩陣===

求矩陣 _ A _ 的逆時，會當直接共求講 _ L _ 和 _ U _ 的逆矩陣，然後代入：$ A ^ { 影一 }=U ^ { 影一 } L ^ { 影一 } $。嘛會當共單位矩陣分解做 _ n _ 一个列的向量，紲落用面頂求解線性方程式的方法解出逆矩陣的列向量，然後鬥起來。後者的複雜度佇咧 _ n _ 二級別，比較高斯法為優。

===計算行列式===

矩陣 $ L $ 和 $ U $ 會當用來快速地計算矩陣 $ A $ 的行列式，因為乎 det ( _ A _ )=det ( _ L _ ) det ( _ U _ )，啊若三角矩陣的行列式就是對角線元素的乘積。若是要求 _ L _ 是單位三角矩陣，遐爾 $ \ det ( A )=\ det ( L ) \ det ( U )=\ prod _ { i=一 } ^ { n } u _ { ii } $

仝款的方法嘛會當應用 _ LUP _ 分解，只需要有乘上 _ P _ 的行列式，即相應置換的符號差。

==參見==

* 分箍 LU 分解
* Cholesky 分解
* 矩陣分解
* LU 大約簡

==參考來源==

* Trefethen , Lloyd ; Bau , David , Numerical Linear Algebra
* Cormen , T . H . ; Leisserson , C . E ; Rivest , R . L . , Introduction to Algorithms
* Golub , Gene H . ; Van Loan , Charles F . , Matrix Computations 三 rd , Baltimore : Johns Hopkins , 九百九十六 , ISBN  九百七十八追空九八千空一十八追五千四百一十四追九   .
* Horn , Roger A . ; Johnson , Charles R . , Matrix Analysis , Cambridge University Press , 一千九百八十五 , ISBN  空九五百二十一孵三鋪八千六百三十二孵二   . See Section 三人五 .
* Okunev , Pavel ; Johnson , Charles , Necessary And Sufficient Conditions For Existence of the LU Factorization of an Arbitrary Matrix , 一千九百九十七 , arXiv : math . NA / 五十八空六千三百八十二   .
* Householder , Alston , The Theory of Matrices in Numerical Analysis , 一千九百七十五   .
* LU decomposition on _ MathWorld _ .
* LU decomposition on _ Math-Linux _ .
* LU decomposition

==外部連結==

* LAPACK is a collection of FORTRAN subroutines for solving dense linear algebra problems
* ALGLIB includes a partial port of the LAPACK to C + + , C # , Delphi , etc .
* Online Matrix Calculator performs LU decomposition
* LU decomposition at _ Holistic Numerical Methods Institute _
* Module for LU Factorization with Pivoting
* LU Decomposition by Ed Pegg , Jr .，The Wolfram Demonstrations Project，兩千空七 .

[[分類: 待校正]]