Re: [理工] [線代]矩陣
※ 引述《bill750121 (Q)》之銘言：
: 關於這類型的題目如何求解
: a,b皆為已知實數，u為已知矩陣
: ( aI + buu^T )^-1
: 該知都已知 硬試求解也是算的出來
: 但是計算滿繁雜(因為只是題目的片斷) 是否有版友有其他有效率的算法?
---
可以查一個 formula 叫做 Woodbury identity
也就是假設 有四個 matrix:
A : m by m
B : n by n
U : m by n
V : n by m
假設 A 、 B 、 (A+UBV) 皆可 invertible
則:
-1 -1 -1 -1 -1 -1 -1
( A + UBV ) = A - A U( B + VA U ) VA
pf:
因為 (A+UBV)^(-1) 存在， 則存在一反矩陣 X
使得 (A+UBV)X = I_m , "I_m" means the m by m identity matrix
令 Y = BVX，則可寫得一聯立方程組:
┌ AX + UY = I_m ____(1)
└ Y = BVX ____(2)
-1
由 (1) 可知 X = A ( I_m - UY ) ____(3)
帶入 (2) 式:
-1
Y = BVA ( I_m - UY )
-1 -1
→ ( I_m + BVA U )Y = BVA
根據 Sylvester's determinant theorem (可用 LUL 概念下去證明)
-1 -1
det( I_m + BVA U ) = det( I_n + A UBV )
-1
= det(A ) * det( A + UBV )
≠ 0
-1 -1
可知 ( I_m + BVA U ) 存在
-1 -1 -1
因此 Y = ( I_m + BVA U ) BVA
-1 -1 -1 -1
= ( B + VA U ) VA
再把 Y 的結果帶回 (3) 式即可解得:
-1 -1 -1 -1 -1 -1
X = A - A U( B + VA U ) VA Q.E.D.
-----
Note:
若 B = [1]
U = u , u: m by 1 matrix
V = v^T , v: m by 1 matrix
則 Woodbury identity 會退化成:
-1 -1 1 -1 T -1
( A + uv^T ) = A - ────────── A uv A
1 + [v^(T)][A^(-1)]u
上式又稱做 Sherman–Morrison formula
以原 po 問的問題來說
把 A = a*I_m
U = bu
V = u
帶入，即可得:
T 1 b T
( a*I_m + b*uu ) = (1/a)*I_m - ───────── * ──uu
1 + (b/a)[u^(T)]u a^2
1 b T
= ──[ I_m - ─────── uu ]
a a + b[u^(T)]u
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.47.130
→
10/09 18:39, , 1F
10/09 18:39, 1F
討論串 (同標題文章)