空军工程大学基础部，陕西 西安

收稿日期：2024年2月2日；录用日期：2024年3月1日；发布日期：2024年4月16日

摘要

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

关键词

Sherman-Morrison公式逆矩阵，BFGS算法，循环三对角线性方程组的求解

Sherman-Morrison Formula and Its Application

Guohong Liang, Junqing Feng, Xiuchao Song

Fundamentals Department, Air Force Engineering University, Xi’an Shaanxi

Received: Feb. 2^nd, 2024; accepted: Mar. 1^st, 2024; published: Apr. 16^th, 2024

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.

Keywords:Sherman-Morrison Formula Inverse Matrix, BFGS Algorithm, The Solution of Recurrent Tridiagonal Linear Equation System

Copyright © 2024 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

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算法和循环三对角线性方程组的求解等方面有着重要的应用。

文章引用

梁国宏,冯军庆,宋修朝. Sherman-Morrison公式及其应用
Sherman-Morrison Formula and Its Application[J]. 理论数学, 2024, 14(04): 53-57. https://doi.org/10.12677/pm.2024.144110

参考文献