Rank-1 Updates of Linear Systems (a) Set A = round(10 ∗ rand(8)), b...

Rank-1 Updates of Linear Systems

(a) Set

A = round(10 ∗ rand(8)),

b = round(10 ∗ rand(8, 1)),

and M = inv(A). Use the matrix M to solve the system Ay = b for y.

(b) Consider now a new system Cx = b, where C is constructed as follows:

u = round(10 ∗ rand(8, 1)),

v = round(10 ∗ rand(8, 1))

E = u ∗ v’ ,

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 MATLAB’s “\” operation to solve the system Cx = b, and then compute the residual vector r = b − Ax.

(c) Let us now solve Cx = 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

z = M ∗ u,

c = v’ ∗ y,

d = v’ ∗ z,

e = c/(1 + d)

and then compute the solution

x by x = y − e ∗ z

Compute the residual vector b − Cx 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

C y and b + cu

Prove that if all computations had been carried out in exact arithmetic, these two vectors would be equal. Also, compute

C z and (1 + d)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 Cx = b. Assuming that A is nonsingular, will the rank-1 update method always work? Under what conditions could it fail? Explain.