Chapter 1.7 LU 分解

基本列運算：
  1. 將矩陣的某一列乘以一個非零數。
  2. 將矩陣中的某兩列互調位置。
  3. 將矩陣的某一列乘以某一非零數加入另一列。

基本列運算矩陣：

=

=

(M1 A) , M1=

(M2 A) , M2=
M3=
M3A : row i = row i + C row j

det(AB)=(det A) . (det B)

Exercise :

M2 M2=I     det(M2)det(M2)=det I Prove why is det ( M2 ) = -1

LU 分解:

Example :

A= b= G.E.
row 2 = row 2 - 1 row 1
row 3 = row 3 - 2 row 1
row 3 = row 3 - (-3) row 2
   

若 A=LU , 則 U= L=

不使用 Pivoting 的高斯消去法
[Thm]

若 A 的所有 principal submatrices Ak 皆為 nonsingular，則 A 分解為 A = LU 的方式只有一種。

Note:

A = LU , 則 L,U 為 nonsingular ( because det(L)= = 1 and pivot element of U are nonzero det(U) = )
U=L-1A

Example :

A = row 2 = row 2 - 1 row 1
row 3 = row 3 - 2 row 1
M1A= where M1= , M-11=
M2(M1A)= where M2= M-12=

M2 M1= , M-11 M-12=

A=

M1 A= (M2 M1) A=
A=(M2M1)-1.U = (M-11M-12) U = LU

 [Thm] ( LDV 分解 ) 若 A 可以做 LU 分解
， A=LU then A=LU=LDV uniquely ( the analysis way is singular )

A=LU=
=

if A=GGT :

  1. G(gij)
  2. A = LU LDV=(LD1/2)(D1/2V) =GGT
    若 A 為正定矩陣。
 <Proof> ( A=LDV , only analysis )
A = L1 D1 V2 = L2 D2 V2
= L1 U1 = L2 U2     where U1 = D1 V1  ,  U2 = D2 V2

because L1 = L2 and U1 = U2(LU 的分解方式為惟一 )

D1 V1 = D2 V2
= V2 V-11 = In
so D1 = D2 and V1 = V2

 [Cor] 若 A 為對稱矩陣，則 A=LU=LDLT

     ( =LD1/2D1/2LT= [LD1/2][(LD1/2)T]= GGT )

A=LDM 其中 L,M 為單位三角矩陣， D : diagonal matrix
若 A 為對稱矩陣， i.e. AT=A ,
then A=LDLT ( M=LT )

A=LDM AT = MT DT LT and A is symmetry

AT=A MT DT LT = LDM MT=L

( 因為 DT LT 與 DM 上三角矩陣，MT , L 為下三角矩陣 , 由 LU 分解之惟一性。 MT=L )

A 為正定矩陣 dii > 0 , 其中 D=(dii)

A=LDLT
L D1/2 D1/2 LT = [LD1/2][(D1/2)T LT] = [L D1/2][L D1/2]T =GGT

(另一方式來分解 , Chelosky Decomposition，先前之高斯消去法為 不使用 pivoting 的消去法。)

Example : 以 A= 來說，無法執行高斯消去法。
若經由列對調 ( 不影響其解 ) 產生新的 再做 LU 分解, 這樣稱為不使用 pivoting 的高斯消去法。

[Summary]

A = =
其中 =PA and P=

     Ax=b

PAx=Pb
LUx=Pb

  1. 令 y=Ux
  2. 先解 Ly=Pb
  3. y 解出之後，再解出 Ux=y

How to choice pivot element ?

假設現有下列系統： =
  1. (每列中最大者)。
  2. 取 max 當做 pivot element。
    因為:
    1. Si=4,S2=3, S3=2(即每列中最大的元素)
    2. 比較比值： 取最大者。
PA= G.E.

記錄下列交換運算的順序 (1,2,3) (3,2,1) (3,1,2),
so Pb=

於 中，S1= , S2=4

比較 , 所以選擇 4 為新的 picot element。
P2 P1 A G.E. ( P2 P1 A )
so P2 P1 A=LU 可得出 L= U=

且重排向量 (permutation vector) 為 (3.1.2)

A-1 的求法：

  1. A-1 =      n! 個步驟。
  2.     n3 個步驟。

A[] =[]
其中 e1=   ,  e2=
i.e. Ax=In ( x=A-1)
針對 A 做 LU 分解

解出 分別為 A-1 的行向量。

[Summary] 解 Ax=b 有兩種方法 :

  1. x=inv(A) * b, 複雜度：n!
  2. x=A, 複雜度：n3

Exercise

Pivot element : 找出相對極大值，而非絕對極大值

Example 1. :

= , If is small enough.

G.E. without poviting =
為錯誤答案，正確解為：

Example 2. :

= (This system is equivalent to Example 1.)

G.E. without poviting =


此亦為錯誤答案 !! 正確答案為： [Summary]