## Friday, February 21, 2014

### Example: Sherman-Morrison Formula

Consider the following equation $Ax=b$,$\begin{bmatrix} 1 & 2 & 3 \\ 1 & 4 & 9 \\ 4 & 5 & 7 \\ \end{bmatrix}x = \begin{bmatrix} 2 \\ 4 \\ 6 \\ \end{bmatrix}.$ The solution of this equation is,$x = \begin{bmatrix} 0.75 \\ 0.25 \\ 0.25 \\ \end{bmatrix}.$ Now let us suppose we wanted to solve a similar problem ( $A'x' = b$ )with a slightly perturbed matrix,$A' = \begin{bmatrix} 1 & 2 & 3 \\ 1 & 6 & 9 \\ 4 & 5 & 7 \\ \end{bmatrix}.$ Notice that this matrix differs from $A$ in the (2,2) element (6 instead of 4).

The Sherman-Morrison formula tells us to form $u = [0~1~0]^T, v = [0~~2~~0]^T$, so that $A' = A + u v^T.$ Hence $y = x = A^{-1}b = \begin{bmatrix} 0.75 \\ 0.25 \\ 0.25 \\ \end{bmatrix},\text{ and } z = A^{-1} u = \begin{bmatrix} 0.125 \\ -0.625 \\ 0.375 \\ \end{bmatrix}.$ Thus,$x' = y - \left({v^T y \over 1 + v^T z}\right) z$  This implies $x' = \begin{bmatrix} 0.75 \\ 0.25 \\ 0.25 \\ \end{bmatrix} \frac{0.25}{1-0.625} \begin{bmatrix} 0.125 \\ -0.625 \\ 0.375 \\ \end{bmatrix} =\begin{bmatrix} 1 \\ -1 \\ 1 \\ \end{bmatrix},$ which is indeed the correct solution.