Sherman-Morrison-Woodbury 公式

本文的閱讀等級:初級

考慮 n\times n 階矩陣 AB。在一般情況下,A+B 的逆矩陣並不存在有用的公式。但如果 A 是可逆矩陣,同時 B 具有某種特殊型態,則 (A+B)^{-1} 確實有簡易的運算公式。最簡單的例子是 I+\mathbf{u}\mathbf{v}^T,其中 \mathbf{u}\mathbf{v}n 維非零向量 (即 n\times 1 矩陣),\mathbf{u}\mathbf{v}^T 稱為秩-1矩陣。本文導出 I+\mathbf{u}\mathbf{v}^T 的逆矩陣,再利用此結果推演 (A+\mathbf{u}\mathbf{v}^T)^{-1} 的計算公式,最後舉一例說明其應用。

 
考慮線性方程

(I+\mathbf{u}\mathbf{v}^T)\mathbf{x}=\mathbf{b}

解出 \mathbf{x} 即可得到 (I+\mathbf{u}\mathbf{v}^T)^{-1} 的公式。令 k=\mathbf{v}^T\mathbf{x},乘開上式可得 \mathbf{x}+k\mathbf{u}=\mathbf{b}。等號兩邊左乘 \mathbf{v}^T,就有 k+k(\mathbf{v}^T\mathbf{u})=\mathbf{v}^T\mathbf{b},即得 k=(1+\mathbf{v}^T\mathbf{u})^{-1}\mathbf{v}^T\mathbf{b}。合併以上結果,

\displaystyle \mathbf{x}=\mathbf{b}-k\mathbf{u}=\mathbf{b}-\frac{\mathbf{v}^T\mathbf{b}}{1+\mathbf{v}^T\mathbf{u}}\mathbf{u}=\mathbf{b}-\frac{\mathbf{u}\mathbf{v}^T}{1+\mathbf{v}^T\mathbf{u}}\mathbf{b}=\left(I-\frac{\mathbf{u}\mathbf{v}^T}{1+\mathbf{v}^T\mathbf{u}}\right)\mathbf{b}

上式中,(\mathbf{v}^T\mathbf{b})\mathbf{u}=\mathbf{u}(\mathbf{v}^T\mathbf{b})=(\mathbf{u}\mathbf{v}^T)\mathbf{b} 係因 \mathbf{v}^T\mathbf{b} 是一個純量,並使用矩陣乘法結合律。若 1+\mathbf{v}^T\mathbf{u}\neq 0,則 I+\mathbf{u}\mathbf{v}^T 可逆,且

\displaystyle (I+\mathbf{u}\mathbf{v}^T)^{-1}=I-\frac{\mathbf{u}\mathbf{v}^T}{1+\mathbf{v}^T\mathbf{u}}

 
A 為一個 n\times n 階可逆矩陣,以 A 取代 I,利用 I+\mathbf{u}\mathbf{v}^T 的逆矩陣公式可導出 A+\mathbf{u}\mathbf{v}^T 的逆矩陣,過程如下:

\displaystyle  \begin{aligned}  (A+\mathbf{u}\mathbf{v}^T)^{-1}&=\left(A(I+A^{-1}\mathbf{u}\mathbf{v}^T)\right)^{-1}=(I+A^{-1}\mathbf{u}\mathbf{v}^T)^{-1}A^{-1}\\  &=\left(I-\frac{A^{-1}\mathbf{u}\mathbf{v}^T}{1+\mathbf{v}^TA^{-1}\mathbf{u}}\right)A^{-1}=A^{-1}-\frac{A^{-1}\mathbf{u}\mathbf{v}^TA^{-1}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}.  \end{aligned}

上式稱為 Sherman-Morrison 公式,(A+\mathbf{u}\mathbf{v}^T)^{-1} 存在的條件是 1+\mathbf{v}^TA^{-1}\mathbf{u}\neq 0。若 UVn\times m 階矩陣使得 I_m+V^TA^{-1}U 可逆,則 Sherman-Morrison 公式可以進一步推廣為

(A+UV^T)^{-1}=A^{-1}-A^{-1}U(I_m+V^TA^{-1}U)^{-1}V^TA^{-1}

稱為 Sherman-Morrison-Woodbury 公式 (證明見“兩矩陣和的逆矩陣”)。

 
因為 \mathbf{u}\mathbf{v} 都是非零向量,\mathrm{rank}(\mathbf{u}\mathbf{v}^T)=1,Sherman-Morrison 公式是一種「秩-1更新」(rank-one update) 公式。假設已知 A^{-1},若 A(i,j) 元改變,譬如加入一個擾動量 \delta,利用 Sherman-Morrison 公式可以免除重頭計算新矩陣的逆矩陣。令 \mathbf{u}=\delta\mathbf{e}_i\mathbf{v}=\mathbf{e}_j,其中 \mathbf{e}_i\mathbf{e}_j 分別是第 i 和第 j 個單位行向量。秩-1矩陣 \mathbf{u}\mathbf{v}^T(i,j) 元等於 \delta,其餘所有元都為零,因此加入擾動量的更新矩陣為

B=A+\mathbf{u}\mathbf{v}^T=A+\delta\mathbf{e}_i\mathbf{e}_j^T

根據 Sherman-Morrison 公式,

\displaystyle  B^{-1}=(A+\delta\mathbf{e}_i\mathbf{e}_j^T)^{-1}=A^{-1}-\delta\frac{(A^{-1}\mathbf{e}_i)(\mathbf{e}_j^TA^{-1})}{1+\delta(\mathbf{e}_j^TA^{-1}\mathbf{e}_i)}

上式中,A^{-1}\mathbf{e}_i\mathbf{e}_j^TA^{-1} 分別是 A^{-1} 的第 i 行和第 j 列,\mathbf{e}_j^TA^{-1}\mathbf{e}_iA^{-1}(j,i) 元。

 
下面舉一例說明「秩-1更新」演算。已知

A=\left[\!\!\begin{array}{rcr}  2&0&-1\\  2&1&-2\\  -1&0&1  \end{array}\!\!\right],~~A^{-1}=\begin{bmatrix}  1&0&1\\  0&1&2\\  1&0&2  \end{bmatrix}

A(2,1) 元加入擾動量 \delta=-1,則更新矩陣為

B=\left[\!\!\begin{array}{rcr}  2&0&-1\\  1&1&-2\\  -1&0&1  \end{array}\!\!\right]=A+(-1)\mathbf{e}_2\mathbf{e}_1^T

利用 Sherman-Morrison 公式,可得

\displaystyle\begin{aligned}  B^{-1}&=A^{-1}+\frac{(A^{-1}\mathbf{e}_2)(\mathbf{e}_1^TA^{-1})}{1-(\mathbf{e}_1^TA^{-1}\mathbf{e}_2)}\\  &=\begin{bmatrix}  1&0&1\\  0&1&2\\  1&0&2  \end{bmatrix}+\frac{\begin{bmatrix}  0\\  1\\  0  \end{bmatrix}\begin{bmatrix}  1&0&1  \end{bmatrix}}{1-0}\\  &=\begin{bmatrix}  1&0&1\\  0&1&2\\  1&0&2  \end{bmatrix}+\begin{bmatrix}  0&0&0\\  1&0&1\\  0&0&0  \end{bmatrix}=\begin{bmatrix}  1&0&1\\  1&1&3\\  1&0&2  \end{bmatrix}.\end{aligned}

This entry was posted in 線性方程, 線性代數專欄 and tagged , , , . Bookmark the permalink.

1 則回應給 Sherman-Morrison-Woodbury 公式

  1. Chenlogy 說:

    感覺似曾相識 (A+BCD)^-1

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s