MATLAB Function Reference

luinc

不完全的 LU 矩陣分解

Syntax

luinc(X,'0')
[L,U] = luinc(X,'0')
[L,U,P] = luinc(X,'0') 
luinc(X,droptol)
luinc(X,options)
[L,U] = luinc(X,options)
[L,U] = luinc(X,droptol)
[L,U,P] = luinc(X,options)
[L,U,P] = luinc(X,droptol) 

Description

luinc 產生一上三角矩陣，一下三角矩陣，及一個排列矩陣。

luinc(X,'0') 計算一層級為 0 之方正稀疏矩陣的不完全 LU 分解。分解出來的三角矩陣有和原本的稀疏矩陣 X 相同的稀疏矩陣結構，而它們的乘積等於 X。luinc(X,'0') 回傳準確的下三角矩陣及上三角矩陣並將其放置於同一個矩陣中。排列的訊息雖然遺失了，但 nnz(luinc(X,'0')) = nnz(X)，對於可能相同的零會進行相消的動作。

[L,U] = luinc(X,'0') 回傳排列矩陣的乘積，一下三角矩陣 L，及一上三角矩陣 U。L, U, 和 X 的稀疏結構並不能比較，但非零的個數將維持一樣，因為在 L 和 U 中相同的零可經由約分：

  nnz(L)+nnz(U) = nnz(X)+n, where X is n-by-n.

L*U 的乘積和 X 有相同的稀疏結構。(L*U).*spones(X)-X 有 eps 的順序項目（entries of the order）。

[L,U,P] = luinc(X,'0') 回傳一元下三角矩陣 L，一上三角矩陣 U 及一排列矩陣 P。L 和排列矩陣 X 的下三角矩陣有相同的稀疏結構。

  spones(L) = spones(tril(P*X))

 L 的對角線有可能出現 1 且 P*X 也可能為零，若 L 有零則經約分後 P*X 可能不為零。U 和 P*X 的上三角矩陣有相同的稀疏結構。

  spones(U) = spones(triu(P*X))

 U 出現的零可經約分使 P*X 不為零。L*U 的乘積可能針對排列矩陣 P*X 的稀疏結構有進位的誤差。(L*U).*spones(P*X)-P*X 有 eps 的順序項目（entries of the order）。

luinc(X,droptol) 對任何稀疏矩陣使用一微量的誤差計算不完全的 LU 分解。droptol 必須是一非負數的數值。luinc(X,droptol) 產生一近似於完全 LU 分解，即 lu(X) 的值。對於微量誤差值的增加，近似值將隨著增加，直到微量誤差值變為 0，在此時即為完全 LU 分解，也就是 lu(X)。

當三角不完全分解因子的每行 j 計算時，強度的項目會小於局部的微量誤差（微量誤差和 X 相關行基準的乘積）

  droptol*norm(X(:,j))

從對應的因子中變弱。

對此漸弱法則的例外為上三角矩陣的對角線元素，其保留來避免單一的因子。

luinc(X,options) 定義一用來做結合結構，其含有四個欄位，分別為：droptol, milu, udiag, thresh。options 額外的欄位將被忽略。

droptol 為不完全分解的微量誤差。

若 milu 為 1，luinc 產生一修改的不完全 LU 分解，其減去上三角矩陣中對角線上的每一欄的漸弱元素。預設值為 0。

若 udiag 為 1，任何對上三角矩陣中對角線為零的位置將被局部微量誤差所取代。預設值為 ０。

thresh 為在 0 和 1 之間的軸心臨界點。預設值總是選擇每一欄中最大強度的元素並將其視為軸心。thresh 在函式 lu 中有更詳細的敘述。

luinc(X,options) 等同於 luinc(X,droptol) 若 options 僅有 droptol 這個欄位。

[L,U] = luinc(X,options) 回傳一元下三角矩陣 L 和一上三角矩陣 U。L*U 近似於 X。luinc(X,options) 回傳一嚴謹的上、下三角因子的部份並放置於同一矩陣。而排列的資訊將遺失。

[L,U] = luinc(X,options) 等同於 luinc(X,droptol) 當 options 僅有 droptol 這一項欄位。

[L,U,P] = luinc(X,options) 回傳一元下三角矩陣 L，一上三角矩陣 U，及一排列矩陣 P。U 中非零的元素滿足

  abs(U(i,j)) >= droptol*norm((X:,j)),

對於對角元素的例外雖然不滿足標準，但會其將保留。L 的元素在依軸心放大時將被比照局部微量誤差來測試，故對 L 的非零元素而言

abs(L(i,j)) >= droptol*norm(X(:,j))/U(j,j).

 L*U 將會近似於 P*X。

[L,U,P] = luinc(X,options) 等同於 [L,U,P] = luinc(X,droptol) 若 options 只有 droptol 這一個欄位。

Remarks

不完全分解當用來解大型的線性代數稀疏結構是相當有用的。下三角因數延著主對角線有 1 的分布而上三角因數則在其對角線為 0。若上三角因數在對角線上有零，則有微量誤差的不完全分解將印出一警告訊息。相同地，使用選項 udiag 取代對角線上的零僅能顯出問題的徵兆但卻沒辦法解出它。preconditioner 也許不會是單一的，但其可能沒用而此時也將印出錯誤訊息。

Limitations

luinc(X,'0') 僅作用於正方矩陣。

Examples

開啟一稀疏矩陣並計算其 LU 分解。

load west0479;
S = west0479;
LU = lu(S);

計算層級為 0 的不完全 LU 分解。

[L,U,P] = luinc(S,'0');
D = (L*U).*spones(P*S)-P*S;

spones(U) 和 spones(triu(P*S)) 為完全相同的。

spones(L) 和 spones(tril(P*S)) 有對角線有 73 處不一致，即 L 為 1 而 P*S 為 0，而在位置 (206,113) 處，L 經由約分而變為 0， P*S 則為 -1。D 有 eps 的順序項目（entries of the order）。

[IL0,IU0,IP0] = luinc(S,0);
[IL1,IU1,IP1] = luinc(S,1e-10);
                .
                .
                .

若微量誤差是 0，則造成完全 LU 分解。增加微量誤差也會使因數的稀疏結構增加（即降低非零元素的數目），但也會增加因數的錯誤，可藉由微量誤差對比於 norm(L*U-P*S,1)/norm(S,1) 的平面圖來確認。

Algorithm

luinc(X,'0') 是根據 LU 分解中的局部軸心的 "KJI" 變數。更新僅用於確定 X 中非零元素的位置。

luinc(X,droptol) 和 luinc(X,options) 是根據行導向 lu 來對稀疏矩陣作用。

See Also

lu, cholinc, bicg

References

Saad, Yousef, Iterative Methods for Sparse Linear Systems, PWS Publishing Company, 1996, Chapter 10 - Preconditioning Techniques.

lu

magic