Sherman-Morrison公式及其应用

Sherman-Morrison Formula and Its Application

摘要: Sherman-Morrison公式是求矩阵之和的逆矩阵的一种特殊方法，在最优化BFGS算法和循环三对角线性方程组的求解等方面有着重要的应用。

Abstract: The Sherman Morrison formula is a special method for finding the inverse matrix of the sum of matrices. It has important applications in optimizing the BFGS algorithm and solving cyclic tridiagonal linear systems of equations.

1. 引言

Sherman-Morrison公式是一种用于求解线性方程组描述的方法，以Jack Sherman和Winifred J. Morrison命名的，可用于计算机科学领域，特别是通信、网络和信号处理中。

由于矩阵之和的逆不一定可逆，即使可逆，也没有统一的公式，Sherman-Morrison公式 [1] [2] 在线性代数中用来求解逆矩阵的一种特殊方法，可逆矩阵与某个列乘行的矩阵之和是一定可逆的，并用公式直接得到逆矩阵。在最优化BFGS算法和循环三对角线性方程组的求解等方面有着重要的应用。

可以用于增量计算矩阵的逆，从而节省存储空间和计算时间。比如，当需要计算一个大型矩阵的逆时，对矩阵逐步添加向量，从而逐步计算出矩阵的逆。

设 $A\in R^{n\times n}$ 为可逆方阵， $u,v\in R^n$ 为列向量， $1+v^{\text{T}}{A}^{-1}u\ne 0$ ，需要求解线性方程 $\left(A+u{v}^{\text{T}}\right)x=b$ ，考虑求解两个方程： $Ay=b,Az=u$ ，有 $y=A^{-1}b,z=A^{-1}u$ ，得

$x+z{v}^{\text{T}}x=y$

注意到 $v^{\text{T}}x$ 是一个数，令 $\alpha =v^{\text{T}}x$ ，有 $x+z\alpha =y$ ，两端左乘 $v^{\text{T}}$ ，即 $v^{\text{T}}x+v^{\text{T}}z\alpha =v^{\text{T}}y$ ，故 $\alpha +v^{\text{T}}z\alpha =v^{\text{T}}y$ ，得

$\alpha =\frac{v^{\text{T}}y}{1+v^{\text{T}}z}=\frac{v^{\text{T}}{A}^{-1}b}{1+v^{\text{T}}{A}^{-1}u}$

有

$x=y-z\alpha =A^{-1}b-A^{-1}u\frac{v^{\text{T}}{A}^{-1}b}{1+v^{\text{T}}{A}^{-1}u}$

实际上，Sherman-Morrison公式在解线性方程有着重要的应用，即通过增加列向量来求解线性方程。

设 $A\in R^{n\times n}$ 为可逆方阵，B是一个n维列向量，考虑线性方程

$AX=B$

解为

$X=A^{-1}B$

令 $B^{\prime }=\left(B,u\right)$ ，即在B的右侧增加一个n维列向量u，则线性方程变为

$A{X}^{\prime }=B^{\prime }$

根据伴随矩阵，解为

$X^{\prime }=A^{-1}{B}^{\prime }=A^{-1}\left(B,u\right)={\left(A+u{v}^{\text{T}}\right)}^{-1}\left(B+u\alpha \right)$

其中 $\alpha =-\frac{v^{\text{T}}{A}^{-1}u}{1+v^{\text{T}}{A}^{-1}u}$ 。将解 $X^{\prime }$ 表示为

$X^{\prime }=A^{-1}B-\frac{A^{-1}u{v}^{\text{T}}{A}^{-1}}{1+v^{\text{T}}{A}^{-1}u}{A}^{-1}B$

于是

$X^{\prime }=\left(A^{-1}-\frac{A^{-1}u{v}^{\text{T}}{A}^{-1}}{1+v^{\text{T}}{A}^{-1}u}\right)B$

可见，通过增加列向量u来解线性方程的解法。

2. Sherman-Morrison公式

设 $A\in R^{n\times n}$ 为可逆方阵， $u,v\in R^n$ 为列向量，则 $A+u{v}^{\text{T}}$ 可逆充要条件为 $1+v^{\text{T}}{A}^{-1}u\ne 0$ ，且当 $A+u{v}^{\text{T}}$ 可逆时，有 [3] [4]

${\left(A+u{v}^{\text{T}}\right)}^{-1}=A^{-1}-\frac{A^{-1}u{v}^{\text{T}}{A}^{-1}}{1+v^{\text{T}}{A}^{-1}u}$

证明(充分性)当时，

$\begin{array}{c}\left(A+u{v}^{\text{T}}\right)\left(A^{-1}-\frac{A^{-1}u{v}^{\text{T}}{A}^{-1}}{1+v^{\text{T}}{A}^{-1}u}\right)=A{A}^{-1}+u{v}^{\text{T}}{A}^{-1}-\frac{A{A}^{-1}u{v}^{\text{T}}{A}^{-1}+u{v}^{\text{T}}{A}^{-1}u{v}^{\text{T}}{A}^{-1}}{1+v^{\text{T}}{A}^{-1}u}\\ =E+u{v}^{\text{T}}{A}^{-1}-\frac{u{v}^{\text{T}}{A}^{-1}+u{v}^{\text{T}}{A}^{-1}u{v}^{\text{T}}{A}^{-1}}{1+v^{\text{T}}{A}^{-1}u}\\ =E+u{v}^{\text{T}}{A}^{-1}-\frac{u\left(1+v^{\text{T}}{A}^{-1}u\right)v^{\text{T}}{A}^{-1}}{1+v^{\text{T}}{A}^{-1}u}\\ =E+u{v}^{\text{T}}{A}^{-1}-u{v}^{\text{T}}{A}^{-1}\\ =E\end{array}$

因此，当 $1+v^{\text{T}}{A}^{-1}u\ne 0$ 时，有

${\left(A+u{v}^{\text{T}}\right)}^{-1}=A^{-1}-\frac{A^{-1}u{v}^{\text{T}}{A}^{-1}}{1+v^{\text{T}}{A}^{-1}u}$

(必要性)当 $u=0$ 时，显然有 $1+v^{\text{T}}{A}^{-1}u=1\ne 0$ 。当 $u\ne 0$ 时，用反证法证明该命题成立。假设 $A+u{v}^{\text{T}}$ 可逆时，但 $1+v^{\text{T}}{A}^{-1}u=0$ 时，有

$\left(A+u{v}^{\text{T}}\right)A^{-1}u=u+u\left(v^{\text{T}}{A}^{-1}u\right)=u\left(1+v^{\text{T}}{A}^{-1}u\right)=0$

因为 $A+u{v}^{\text{T}}$ 可逆，故 $A^{-1}u=0$ ，又因为 $A^{-1}$ 可逆，故 $u=0$ ，此与假设 $u\ne 0$ 矛盾。因此，当 $A+u{v}^{\text{T}}$ 可逆时，但 $1+v^{\text{T}}{A}^{-1}u\ne 0$ 时，有 $1+v^{\text{T}}{A}^{-1}u\ne 0$ 。

3. Sherman-Morrison公式的应用

1) 当 $A=E_n$ 时的Sherman-Morrison公式

在Sherman-Morrison公式中，令 $A=E_n$ ，则有 $E+u{v}^{\text{T}}$ 可逆充要条件为 $1+v^{\text{T}}u\ne 0$ ，且当 $E+u{v}^{\text{T}}$ 可逆时，有

${\left(E+u{v}^{\text{T}}\right)}^{-1}=E-\frac{u{v}^{\text{T}}}{1+v^{\text{T}}u}$

再令 $v=u$ ，则 $1+u^{\text{T}}u>0$ ，因此， $E+u^{\text{T}}u$ 可逆，且

${\left(E+u{u}^{\text{T}}\right)}^{-1}=E-\frac{u{u}^{\text{T}}}{1+u^{\text{T}}u}$

2) Sherman-Morrison公式在BFGS算法中的应用

Sherman-Morrison公式在BFGS算法中的应用，可用来求解BFGS算法中近似Hessian矩阵的逆。

在BFGS算法中，得到递推公式

$B_{k+1}=B_k+\frac{q_k{q}_k^{\text{T}}}{q_k^{\text{T}}{p}_k}-\frac{B_k{p}_k{p}_k^{\text{T}}{B}_k}{p_k^{\text{T}}{B}_k{p}_k}$

其中， $p_k=x^{\left(k+1\right)}-x^{\left(k\right)}$ ， $q_k=\nabla f\left(x^{\left(k+1\right)}\right)-\nabla f\left(x^{\left(k\right)}\right)$ 。

令 $H=B_k+\frac{q_k{q}_k^{\text{T}}}{q_k^{\text{T}}{p}_k}$ ，注意到 $\frac{B_k{p}_k{p}_k^{\text{T}}{B}_k}{p_k^{\text{T}}{B}_k{p}_k}=\frac{1}{p_k^{\text{T}}{B}_k{p}_k}\left(B_k{p}_k\right){\left(B_k{p}_k\right)}^{\text{T}}$ ，其中 $p_k^{\text{T}}{B}_k{p}_k$ 为一个数，且 $B_k{p}_k\in R^n$ ，因此利用Sherman-Morrison公式，有

$\begin{array}{c}{B}_{k+1}^{-1}={\left(H-\frac{1}{p_k^{\text{T}}{B}_k{p}_k}\left(B_k{p}_k\right){\left(B_k{p}_k\right)}^{\text{T}}\right)}^{-1}\\ =H^{-1}-\frac{H^{-1}\left(-\frac{1}{p_k^{\text{T}}{B}_k{p}_k}\left(B_k{p}_k\right){\left(B_k{p}_k\right)}^{\text{T}}\right)H^{-1}}{1+\left(-\frac{1}{p_k^{\text{T}}{B}_k{p}_k}\right){\left(B_k{p}_k\right)}^{\text{T}}{H}^{-1}\left(B_k{p}_k\right)}\\ =H^{-1}+H^{-1}\frac{B_k{p}_k{p}_k^{\text{T}}{B}_k}{p_k^{\text{T}}{B}_k{p}_k-p_k^{\text{T}}{B}_k{H}^{-1}{B}_k{p}_k}{H}^{-1}\end{array}$

对于 $H^{-1}$ ，再次利用Sherman-Morrison公式，有

$\begin{array}{c}{H}^{-1}={\left(B_k+\frac{q_k{q}_k^{\text{T}}}{q_k^T{p}_k}\right)}^{-1}=B_k^{-1}-\frac{B_k^{-1}\frac{q_k{q}_k^{\text{T}}}{q_k^{\text{T}}{p}_k}{B}_k^{-1}}{1+\frac{1}{q_k^{\text{T}}{p}_k}{q}_k^{\text{T}}{B}_k^{-1}{q}_k}\\ =B_k^{-1}-\frac{B_k^{-1}\frac{q_k{q}_k^{\text{T}}}{q_k^T{p}_k}{B}_k^{-1}}{1+\frac{1}{q_k^{\text{T}}{p}_k}{q}_k^{\text{T}}{B}_k^{-1}{q}_k}=B_k^{-1}-\frac{B_k^{-1}{q}_k{q}_k^{\text{T}}{B}_k^{-1}}{q_k^{\text{T}}{p}_k+q_k^{\text{T}}{B}_k^{-1}{q}_k}\end{array}$

将 $H^{-1}$ 的表达式代回 $B_{k+1}^{-1}$ 中，得到

$B_{k+1}^{-1}=\left(I-\frac{p_k{q}_k^{\text{T}}}{p_k^{\text{T}}{q}_k}\right)B_k^{-1}\left(I-\frac{p_k{q}_k^{\text{T}}}{p_k^{\text{T}}{q}_k}\right)+\frac{p_k{p}_k^{\text{T}}}{p_k^{\text{T}}{q}_k}$

3) Sherman-Morrison公式在循环三对角线性方程组的求解中的应用

下面介绍循环三对角线性方程组的求解。所谓循环三对角线性方程组，指的是系数矩阵为如下形式：

$A=\left[\begin{array}{cccccc}{b}_1& c_1& 0& \cdots & 0& a_1\\ a_2& b_2& c_2& 0& ⋮& 0\\ 0& \ddots & \ddots & \ddots & 0& ⋮\\ ⋮& ⋮& a_{n-2}& b_{n-2}& c_{n-2}& 0\\ 0& \cdots & \cdots & a_{n-1}& b_{n-1}& c_{n-1}\\ c_n& 0& \cdots & 0& a_n& b_n\end{array}\right]$

循环三对角线性方程组可写成 $Ax=d$ ，其中 $d={\left(d_1,d_2,\cdots ,d_n\right)}^{\text{T}}$ 。

令 $u={\left(\lambda ,0,0,\cdots ,c_n\right)}^{\text{T}}$ ， $v={\left(1,0,0,\cdots ,\frac{a_1}{\lambda }\right)}^{\text{T}}$ ，且 $A=A^{\prime }+u{v}^{\text{T}}$ ，其中

$A^{\prime }=\left[\begin{array}{cccccc}{b}_1-\lambda & c_1& 0& \cdots & 0& 0\\ a_2& b_2& c_2& 0& ⋮& 0\\ 0& \ddots & \ddots & \ddots & 0& ⋮\\ ⋮& ⋮& a_{n-2}& b_{n-2}& c_{n-2}& 0\\ 0& \cdots & \cdots & a_{n-1}& b_{n-1}& c_{n-1}\\ c_n& 0& \cdots & 0& a_n& b_n-\frac{a_1{c}_n}{\lambda }\end{array}\right]$

$A^{\prime }$ 为三对角矩阵。根据以上的理论知识，只需求解以下两个方程

$A^{\prime }y=d,A^{\prime }z=u$

这样就能根据 $y,z$ 求出x。

总之，Sherman-Morrison公式给出了求矩阵之和的逆矩阵的一种特殊方法，在矩阵论中有着重要的应用，除此之外，在最优化BFGS算法和循环三对角线性方程组的求解等方面有着重要的应用。