next up previous [pdf]

Next: Bibliography Up: Liu and Li: - Previous: Acknowledgments

Appendix A: Direct derivation of the Sherman-Morrison Formula

The Sherman-Morrison formula can be derived directly by solving the linear problem as

$\displaystyle (\mathbf{A}-\mathbf{u}\mathbf{v})\mathbf{x}=\mathbf{b},$ (22)

where $ \mathbf{u}$ is a column vector and $ \mathbf{v}$ is a row vector. Assuming $ \mathbf{A}^{-1}$ is already known, we pre-multiply equation A-1 by $ \mathbf{A}^{-1}$ and denote $ \mathbf{A}^{-1}\mathbf{u}=\mathbf{z}$ and $ \mathbf{A}^{-1}\mathbf{b}=\mathbf{y}$ to give

$\displaystyle \mathbf{x}-\mathbf{z}\mathbf{v}\mathbf{x}=\mathbf{y}.$ (23)

Because $ \mathbf{v}\mathbf{x}$ is a scalar quantity, we can denote it as $ \alpha$ . To find $ \alpha$ , we pre-multiply the equation A-2 by $ \mathbf{v}$ to give

$\displaystyle \alpha-\mathbf{v}\mathbf{z}\alpha=\mathbf{v}\mathbf{y}.$ (24)

Since $ \mathbf{v}\mathbf{z}$ and $ \mathbf{v}\mathbf{y}$ in the equation A-3 are scalars, one can easily solve for $ \alpha$ to get

$\displaystyle \alpha=\frac{\mathbf{v}\mathbf{y}}{1-\mathbf{v}\mathbf{z}}.$ (25)

Thus the solution can be written as
$\displaystyle \mathbf{x}$ $\displaystyle =$ $\displaystyle \mathbf{y}+\alpha\mathbf{z}$ (26)
  $\displaystyle =$ $\displaystyle \mathbf{A}^{-1}\mathbf{b}+\mathbf{A}^{-1}\mathbf{u}
(1-\mathbf{v}\mathbf{A}^{-1}\mathbf{u})^{-1}
\mathbf{v}\mathbf{A}^{-1}\mathbf{b}$ (27)
  $\displaystyle =$ $\displaystyle [\mathbf{A}^{-1}+\mathbf{A}^{-1}\mathbf{u}
(1-\mathbf{v}\mathbf{A}^{-1}\mathbf{u})^{-1}
\mathbf{v}\mathbf{A}^{-1}]\mathbf{b}.$ (28)

We then obtain the Sherman-Morrison formula

$\displaystyle (\mathbf{A}-\mathbf{u}\mathbf{v})^{-1}=\mathbf{A}^{-1}+ \mathbf{A...
...athbf{u}(1- \mathbf{v}\mathbf{A}^{-1}\mathbf{u})^{-1}\mathbf{v}\mathbf{A}^{-1}.$ (29)


next up previous [pdf]

Next: Bibliography Up: Liu and Li: - Previous: Acknowledgments

2019-05-06