2.II.38C

Numerical Analysis
Part II, 2007

(a) State the Householder-John theorem and explain how it can be used to design iterative methods for solving a system of linear equations Ax=bA x=b.

(b) Let A=L+D+UA=L+D+U where DD is the diagonal part of AA, and LL and UU are, respectively, the strictly lower and strictly upper triangular parts of AA. Given a vector bb, consider the following iterative scheme:

(D+ωL)x(k+1)=(1ω)Dx(k)ωUx(k)+ωb(D+\omega L) x^{(k+1)}=(1-\omega) D x^{(k)}-\omega U x^{(k)}+\omega b

Prove that if AA is a symmetric positive definite matrix, and ω(0,2)\omega \in(0,2), then the above iteration converges to the solution of the system Ax=bA x=b.