Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 3 / 40A (Numerical Analysis)

Writing the error as $e_k=x_k-x^{\ast }$ givesprovided the fixed-point consistency conditionholds. Convergence for every starting vector is therefore equivalent to $H^k\to 0$, which in finite dimensions is equivalent toThese two conditions are necessary and sufficient.

Let $D=\mathrm{diag}(A)$. The Jacobi method isso $H=I-D^{-1}A$ and $v=D^{-1}b$. If $A$ is strictly diagonally dominant, every Gershgorin disc of $H$ is centered at zero and has radiusEvery eigenvalue therefore has modulus below one, so $\rho (H)<1$ and part (i) proves convergence.

The gradient is $\nabla f(x)=Ax-b=A(x-x^{\ast })$. Completing the square givesfor $x\ne x^{\ast }$, so $x^{\ast }$ is the unique global minimizer. Since $x-x^{\ast }=A^{-1}\nabla f(x)$,

Since $\nabla f(x_k)=-r_k$, exact line search minimizes $f(x_k+t{r}_k)$. Differentiation givesso

The exact line search for a positive-definite quadratic givesUsingproduces the stated ratio formula. If $l$ and $L$ are the extreme eigenvalues,Hence the fraction in the ratio is at least $l/L$, and iteration yieldsWhen $n=1$, $l=L$, so the right side is zero after one iteration: exact line search reaches the solution in a single step.