正定系統的 Chelosky 分解

Chapter 1.5 正定系統的 Chelosky 分解

(Positive Definite System Chelosky Decomposition)

[Def] 若實方陣 A 為對稱，且對所有 x 滿足 x^TAx > 0 , 則 A 稱為正定矩陣(positive definite matrix)。

[Thm] 若 A 為正定，則 A 為 nonsingular。

[Cor] 若 A 為正定，則 Ax = b 有唯一解。

<Proof>

若 A 為 singular 則

x

0

Ax = 0

x^T( Ax ) = x^T 0 = 0

A 不為正定矩陣。

[Thm] 如果 M 為實矩陣且 nonsingular , 則 A=MM^T 為正定矩陣。

<Proof>

real OK !
symmetric (A^T=A)
because A^T = (MM^T ) ^T = (M^T ) ^TM^T = MM^T= A
for all x 0 (x^TAx > 0)
because x^TAx = x^T(MM ^T)x = y^Ty > 0 ( Let y=M^Tx )
If y = (y₁, ... ,y_n)^T
y^Ty = y²₁+y²₂+ ... +y²_n

<PS>

若 A 為正定，則 A 的所有特徵值皆為正實數。
正定矩陣並非所有項皆為正數。

[Thm] Cholesky Decomposition

若 A 為正定，則 A 可以被分解為如 A=GG^T 的形式，其中 G 為下三角矩陣且其主對角線上的項皆為正數（且分解的方式為唯一的）。

Example :

(1)
M= M^T=

則 A = MM^T = 為正定矩陣。

以 3 × 3 的矩陣為例：
A = LU =

=

=

Example :

M =

and A=MM^T=

The LU Decomposition of A = =
=

= =GG^T

Cholesky 分解

A 為正定 A可以以唯一的方法分解為 A=GG^T，
其中 G 為對角項為時數的下三角矩陣。
若 A = ( a_ij )
= =
首先，找出 G 的第一行：
STEP 1.
a₁₁ = g₁₁^.g₁₁
g₁₁ = (a_i1=g_i1 ^. g₁₁)
STEP 2.
再求第二行：
a₂₂ = g₂₁^.g₂₁ + g₂₂^.g₂₂ g₂₂ =
In general , For j = 1 ...n , g_ii =
g_ij = ,i = j + 1 ^... n
以行的方式來找出 g_ij， ( 先找 g_ii, 再找 g_ij )

Example : A=

=

Phase 1. 先從第一行著手
4 = g²₁₁

g₁₁=

= 2 , g₂₁ =

= -1 , g₃₁ =

= 2 , g₄₁=

= 1

Phase 2. 求第二行之元素： g₂₂ = = 3 g₃₂ = = 0 g₄₂ = -2

Note :

若 A 為正定 a_ii > 0 for all i
a_ij not necessary 0

演算法 ( Cholesky Decomposition )

for j=1 ...n for n=1 ...j-1 a_jj

a_jj-a²_jk a_jj

for i=j+1 ...n for k=1 ...j-1 a_ij

a_ij-a_ik a_jk
a_ij