Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 1 / 39B (Numerical Analysis)

Assume the diagonal entries of $A$ are nonzero. The relaxed Jacobi method simultaneously updates every component using the preceding iterate:In matrix form, with $D=\mathrm{diag}(A)$, this is $x^{(\nu +1)}=x^{(\nu )}+\omega D^{-1}(b-A{x}^{(\nu )})$. The ordinary Jacobi method has $\omega =1$.

Subtracting the fixed-point equation for the exact solution givesHere $D=2I$, so the supplied sine eigenvectors of $A$ are also eigenvectors of $H_{\omega }$. Explicitly,Their distinct eigenvalues for nonzero $\omega$ make them an eigenbasis; alternatively the discrete sine orthogonality gives a basis even when $\omega =0$.

For a fixed $n$, convergence for every initial error is equivalent to $|1-\omega t_k|<1$ for all $k$, where $t_k=1-\cos (k\pi /(n+1))>0$. ThusA single parameter works for every finite $n$ precisely when $\boxed{0<\omega \le 1}$: the largest $t_k$ tends to two as $n\to \infty$, so every $\omega >1$ eventually fails, whereas $\omega =1$ has all eigenvalues strictly between $-1$ and one for each finite grid.

For such $\omega$ the lowest-frequency eigenvalue satisfies, using $1-\cos x\le x^2/2$,An initial error proportional to $v_1$ retains exactly the factor ${\lambda }_1^{\nu }$. Hence the worst-case spectral radius cannot improve on a factor of the form $(1-c/n^2{)}^{\nu }$, with $c$ independent of grid size, and reducing a slow-mode error by a fixed fraction takes order $n^2$ iterations. This is a worst-case rate assertion, not a lower bound for every individual initial error: a vector containing only faster modes, or the zero vector, need not exhibit the slow mode.

Let $k_0=\lceil (n+1)/2\rceil$, $\theta =\pi /(n+1)$, and define the high-frequency endpoint parametersThey obey $1\le a\le b<2$ (with equality of endpoints for a single high mode). Since $|1-\omega t|$ is convex in $t$ and the endpoint modes are included, the exact high-frequency attenuation isThe minimax choice balances the endpoint values with opposite signs. If they were not balanced, moving $\omega$ toward their balancing point would lower the larger endpoint value. ThusFor odd $n$, $a=1$, giving ${\omega }_{\ast }=2/(2+\cos \theta )$ and ${\mu }_{\ast }=\cos \theta /(2+\cos \theta )$. For even $n$, $a=1+\sin (\theta /2)$, givingThese give the exact finite-grid high-frequency Jacobi smoothing optimum, including complete annihilation when there is only one high-frequency mode. Their grid-independent limits are $\boxed{{\omega }_{\ast }=2/3,{\mu }_{\ast }=1/3}$. Choosing $2/3$ damps every high mode by at most $1/3$ on every grid, while its low-mode factor remains $1-O(n^{-2})$. Thus high frequencies decay geometrically much faster. The familiar $2/3,1/3$ pair is the optimal uniform-in-grid smoother; it need not be the exact optimum on a particular finite sine-mode grid.