Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2009 / A / 2 / Solution

The Gauss-Seidel method updates coordinates successively using the newest available entries:It is well-defined for every initial vector exactly when every $a_{ii}\ne 0$, equivalently when the triangular matrix $D+L$ is invertible. Nonsingularity of $A$ alone does not ensure this. The matrix form isIf the iterates converge to $z$, passing to the limit gives $(D+L)z=b-Uz$, hence $Az=b$. Nonsingularity identifies $z$ as the unique solution $x$.

Now assume $A$ is a symmetric positive-definite matrix. Testing with the coordinate vector gives $a_{ii}=e_i^{T}A{e}_i>0$, so $D$ is positive definite. The form $⟨v,w{⟩}_A=v^{T}Aw$ is an inner product: bilinearity and symmetry are immediate and positivity is the hypothesis. Its Cauchy-Schwarz inequality givesproving the triangle inequality; definiteness and absolute homogeneity are immediate. Thus $\Vert v{\Vert }_A=\sqrt{v^{T}Av}$ is the energy norm.

Subtract the iteration from the exact equation to obtain $(D+L)e_{k+1}=-L^T{e}_k$. HenceUsing the preceding iteration also gives $(D+L)e_k=-L^T{e}_{k-1}$ and therefore $A{e}_k=L^T(e_k-e_{k-1})$ for $k\ge 1$, as required.

Put $d=e_k-e_{k+1}$. Expanding the two quadratic forms and using the first identity gives the exact Gauss-Seidel energy decrease identity:Here $2d^{T}Ld=d^T(L+L^T)d$. If $d=0$, then $A{e}_k=0$, so $e_k=0$. Otherwise $d^{T}Dd>0$. Thus $\boxed{\Vert e_k{\Vert }_A>\Vert e_{k+1}{\Vert }_A}$ unless the exact solution has already been reached.