Chapter 3, Problem 4E

(Rank−1 Updates of Linear Systems)
(a) Set
$A=\text{round}\left(10\ast \text{rand}\left(8\right)\right)$
$\text{b}=\text{round}\left(10\ast \text{rand}\left(8,1\right)\right)$
$M=\text{inv}\left(A\right)$
Use the matrix M to solve the system $A\text{y}=\text{b}$ for y.
(b) Consider now a new system $C\text{x}=\text{b}$ , where C is constructed as follows:
$\text{u}=\text{round}\left(10\ast \text{rand}\left(8,1\right)\right)$
$\text{v}=\text{round}\left(10\ast \text{rand}\left(8,1\right)\right)$

$C=A+E$
The matrices C and A differ by the rank−1 matrix E. Use MATLAB to verify that the rank of E is 1. Use MATLABS’s “\” operation to solve the system $C\text{x}=\text{b}$ and then compute the residual vector $\text{r}=\text{b}-A\text{x}$ .
(c) Let us now solve $C\text{x}=\text{b}$ by a new method that takes advantage of the fact that A and C differ by a rank−1 matrix. This new procedure is called a rank−1 update method. Set


and then compute the solution x by
$\text{x}=\text{y}-e\ast \text{z}$
Compute the residual vector $\text{b}-C\text{x}$ and compare it with the residual vector in part (b). This new method may seem more complicated, but it actually is much more computationally efficient.
(d) To see why the rank−1 update method works, use MATLAB to compute and compare
Cy and $\text{b}+c\text{u}$
Prove that if all computations had been carried out in exact arithmetic, these two vectors would be equal. Also, compute
Cz and $\left(1+d\right)\text{u}$
Prove that if all computations had been carried out in exact arithmetic, these two vectors would be equal. Use these identities to prove that $C\text{x}=\text{b}$ . Assuming that A is nonsingular, will the rank−1 update method always work? Under what conditions could it fail? Explain.