Paper 1, Section II, A

Numerical Analysis
Part II, 2017

State the Householder-John theorem and explain how it can be used in designing iterative methods for solving a system of linear equations Ax=bA \mathbf{x}=\mathbf{b}. [You may quote other relevant theorems if needed.]

Consider the following iterative scheme for solving Ax=bA \mathbf{x}=\mathbf{b}. Let A=L+D+UA=L+D+U, where DD is the diagonal part of AA, and LL and UU are the strictly lower and upper triangular parts of AA, respectively. Then, with some starting vector x(0)\mathbf{x}^{(0)}, the scheme is as follows:

(D+ωL)x(k+1)=[(1ω)DωU]x(k)+ωb.(D+\omega L) \mathbf{x}^{(k+1)}=[(1-\omega) D-\omega U] \mathbf{x}^{(k)}+\omega \mathbf{b} .

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

Which method corresponds to the case ω=1?\omega=1 ?