Numerical Analysis | Part IB, 2002

(a) Consider a system of linear equations Ax=bA x=b with a non-singular square n×nn \times n matrix AA. To determine its solution x=xx=x^{*} we apply the iterative method

xk+1=Hxk+v.x^{k+1}=H x^{k}+v .

Here vRnv \in \mathbb{R}^{n}, while the matrix HRn×nH \in \mathbb{R}^{n \times n} is such that x=Hx+vx^{*}=H x^{*}+v implies Ax=bA x^{*}=b. The initial vector x0Rnx^{0} \in \mathbb{R}^{n} is arbitrary. Prove that, if the matrix HH possesses nn linearly independent eigenvectors w1,,wnw_{1}, \ldots, w_{n} whose corresponding eigenvalues λ1,,λn\lambda_{1}, \ldots, \lambda_{n} satisfy maxiλi<1\max _{i}\left|\lambda_{i}\right|<1, then the method converges for any choice of x0x^{0}, i.e. xkxx^{k} \rightarrow x^{*} as kk \rightarrow \infty.

(b) Describe the Jacobi iteration method for solving Ax=bA x=b. Show directly from the definition of the method that, if the matrix AA is strictly diagonally dominant by rows, i.e.

aii1j=1,jinaijγ<1,i=1,,n,\left|a_{i i}\right|^{-1} \sum_{j=1, j \neq i}^{n}\left|a_{i j}\right| \leq \gamma<1, \quad i=1, \ldots, n,

then the method converges.

Typos? Please submit corrections to this page on GitHub.