Chapter 5 · Numerical Analysis

5.2 Linear Systems: Gauss Elimination and Gauss–Seidel

Direct and iterative solution of $Ax=b$: Gauss elimination with partial pivoting and its $\tfrac{n^3}{3}$ cost, LU (Doolittle, Crout) and Cholesky factorisations, the Jacobi and Gauss–Seidel iterations and their convergence through diagonal dominance and the spectral radius, SOR, and the condition number.

Almost every computation in applied mathematics ends in a linear system. Newton's method for a system of equations (§5.1) solves one at every step; cubic splines (§5.3) and implicit methods for differential equations lead to tridiagonal systems; a finite-difference model of the temperature in a turbine blade, the stresses in a bridge or the pressure in an oil reservoir produces systems with millions of unknowns. Cramer's rule, which you learned first, is useless here: it needs about $(n+1)!$ operations, so for $n=25$ unknowns it would keep the fastest computer on Earth busy for longer than the age of the universe. Gauss elimination needs about $\tfrac23n^3$ operations — a fraction of a second for $n=1000$.

There are two families of methods. Direct methods — Gauss elimination and its matrix form, the LU factorisation — give the exact answer (up to rounding) after a fixed number of operations; their enemies are zero or tiny pivots and rounding errors, controlled by pivoting and measured by the condition number. Iterative methods — Jacobi, Gauss–Seidel and SOR — start from a guess and improve it, touching only the nonzero entries of $A$, which is what makes them attractive for large sparse systems; whether they converge is decided by a single number, the spectral radius of the iteration matrix. CSIR NET asks for exactly these: an entry of an LU factor, the number of operations, whether Jacobi or Gauss–Seidel converges for a given matrix, the spectral radius of an iteration matrix, and the condition number of a small matrix.

Gauss Elimination and Its Cost

Throughout, $A=(a_{ij})$ is a real $n\times n$ matrix, $b\in\mathbb{R}^n$, and we solve $Ax=b$. The idea of elimination is two thousand years old (it appears in the Chinese Nine Chapters on the Mathematical Art); Gauss used it around 1810 to compute the orbit of the asteroid Pallas.

📘 Definition 5.8 — Gauss elimination, pivots, multipliers

Put $A^{(1)}=A$, $b^{(1)}=b$. For $k=1,\dots,n-1$, if the pivot $a^{(k)}_{kk}\ne0$, compute the multipliers $m_{ik}=a^{(k)}_{ik}/a^{(k)}_{kk}$ and subtract $m_{ik}$ times row $k$ from row $i$, for $i=k+1,\dots,n$:

$$a^{(k+1)}_{ij}=a^{(k)}_{ij}-m_{ik}\,a^{(k)}_{kj},\qquad b^{(k+1)}_i=b^{(k)}_i-m_{ik}\,b^{(k)}_k .$$

This forward elimination produces an upper triangular system $Ux=c$ with $u_{ij}=a^{(i)}_{ij}$, $c_i=b^{(i)}_i$, which is solved by back substitution:

$$x_n=\frac{c_n}{u_{nn}},\qquad x_i=\frac{1}{u_{ii}}\Big(c_i-\sum_{j=i+1}^{n}u_{ij}x_j\Big),\quad i=n-1,\dots,1.$$

The elimination breaks down if some pivot $a^{(k)}_{kk}$ is $0$.

📐 Theorem 5.11 — When elimination without row exchanges works

Let $\Delta_k=\det\big(a_{ij}\big)_{i,j\le k}$ be the leading principal minors of $A$ and $\Delta_0=1$. Gauss elimination without row interchanges produces nonzero pivots $u_{11},\dots,u_{kk}$ if and only if $\Delta_1,\dots,\Delta_k$ are all nonzero, and then

$$u_{kk}=\frac{\Delta_k}{\Delta_{k-1}},\qquad \Delta_k=u_{11}u_{22}\cdots u_{kk}.$$

In particular, for nonsingular $A$ the elimination runs to the end without interchanges iff $\Delta_1,\dots,\Delta_{n-1}\ne0$, and $\det A=u_{11}u_{22}\cdots u_{nn}$.

Proof. Adding a multiple of row $k$ to a row $i\gt k$ does not change any leading principal minor $\Delta_j$: for $j\lt i$ the submatrix is untouched, and for $j\ge i$ both rows lie in the $j\times j$ block, where adding a multiple of one row to another keeps the determinant. Suppose the first $k-1$ pivots are nonzero, so $A^{(k)}$ is defined. Its leading $k\times k$ block is upper triangular with diagonal $u_{11},\dots,u_{k-1,k-1},a^{(k)}_{kk}$, hence $\Delta_k=u_{11}\cdots u_{k-1,k-1}\,a^{(k)}_{kk}$. By induction $\Delta_{k-1}=u_{11}\cdots u_{k-1,k-1}\ne0$, so the $k$-th pivot $a^{(k)}_{kk}=\Delta_k/\Delta_{k-1}$ is nonzero exactly when $\Delta_k\ne0$. ∎

📐 Theorem 5.12 — Operation count

Solving $Ax=b$ by Gauss elimination and back substitution takes

$$\frac{n^3}{3}+n^2-\frac n3\ \text{ multiplications/divisions},$$ $$\frac{n^3}{3}+\frac{n^2}{2}-\frac{5n}{6}\ \text{ additions/subtractions}.$$

So the cost is about $\tfrac{n^3}{3}$ multiplications, i.e. $\tfrac23n^3$ floating-point operations, almost all of it in the elimination of $A$. Each further right-hand side costs only $n^2$ multiplications.

Proof. At step $k$ there are $n-k$ rows below the pivot. Each needs one division (the multiplier), $n-k$ multiplications and subtractions to update its entries in columns $k+1,\dots,n$, and one multiplication and subtraction for $b$. Summing over $k=1,\dots,n-1$ with $s=n-k$: $$\sum_{s=1}^{n-1}\big(s+s^2+s\big)=\frac{(n-1)n(2n-1)}{6}+(n-1)n\quad\text{mult./div.},$$ $$\sum_{s=1}^{n-1}\big(s^2+s\big)=\frac{(n-1)n(2n-1)}{6}+\frac{(n-1)n}{2}\quad\text{add./sub.}$$ Back substitution needs $\sum_{i=1}^{n}(n-i+1)=\tfrac{n(n+1)}2$ multiplications/divisions and $\tfrac{n(n-1)}2$ subtractions. Adding up and simplifying gives the stated polynomials (for $n=3$: $17$ and $11$). ∎

By contrast, Gauss–Jordan elimination (clearing above the pivots as well) costs about $\tfrac{n^3}{2}$ multiplications, and Cramer's rule with determinants expanded by cofactors about $(n+1)!$. For $n=3$ the counts $17$ (elimination) and $11$ are a favourite exam question.

A zero pivot stops elimination; a small pivot is worse, because it silently produces garbage. The cure is to choose the largest available pivot.

📘 Definition 5.9 — Partial pivoting
At step $k$ of the elimination, choose a row $p\ge k$ with $|a^{(k)}_{pk}|=\max_{i\ge k}|a^{(k)}_{ik}|$ and interchange rows $p$ and $k$ (of $A^{(k)}$ and $b^{(k)}$) before eliminating. Then every multiplier satisfies $|m_{ik}|\le1$. (Complete pivoting searches the whole remaining submatrix and also interchanges columns; it is rarely needed.)
📐 Theorem 5.13 — $PA=LU$
If $A$ is nonsingular, Gauss elimination with partial pivoting never meets a zero pivot. Recording the interchanges in a permutation matrix $P$ and the multipliers in a unit lower triangular $L$ (with $|l_{ij}|\le1$), one has $PA=LU$, where $U$ is the final upper triangular matrix. Moreover $\det A=(-1)^s\,u_{11}\cdots u_{nn}$, where $s$ is the number of interchanges.

Proof. After $k-1$ steps, $A^{(k)}=M\,A$ for an invertible matrix $M$ (a product of elimination and interchange matrices), so $A^{(k)}$ is nonsingular. Its first $k-1$ columns are zero below the diagonal; if the entries $a^{(k)}_{ik}$, $i\ge k$, were all zero, the first $k$ columns would lie in a $(k-1)$-dimensional space and $A^{(k)}$ would be singular. So a nonzero pivot exists, and the largest one gives $|m_{ik}|\le1$. That the interchanges can all be moved to the front, giving $PA=LU$ with the multipliers permuted accordingly, follows from the identity $P_{k}E_j=\tilde E_jP_k$ ($j\lt k$), where $\tilde E_j$ is the elimination matrix $E_j$ with two multipliers swapped. Finally $\det P=(-1)^s$, $\det L=1$. ∎

✏️ Example 1 — Gauss elimination with partial pivoting
Solve $x_1+2x_2+3x_3=5$, $2x_1+2x_2+x_3=2$, $4x_1+x_2+2x_3=7$ by Gauss elimination with partial pivoting, and read off $\det A$.
Step 1 The largest entry of column 1 is $4$ (row 3): interchange rows 1 and 3. Multipliers $m_{21}=\tfrac24=\tfrac12$, $m_{31}=\tfrac14$: $$\left[\begin{array}{ccc|c}4&1&2&7\\0&\tfrac32&0&-\tfrac32\\0&\tfrac74&\tfrac52&\tfrac{13}4\end{array}\right]$$
Step 2 In column 2 below the diagonal, $\tfrac74\gt\tfrac32$: interchange rows 2 and 3. Multiplier $m_{32}=\tfrac{3/2}{7/4}=\tfrac67$: $$\left[\begin{array}{ccc|c}4&1&2&7\\0&\tfrac74&\tfrac52&\tfrac{13}4\\0&0&-\tfrac{15}7&-\tfrac{30}7\end{array}\right]$$
Back substitution $x_3=2$; $\ \tfrac74x_2+5=\tfrac{13}4$ gives $x_2=-1$; $\ 4x_1-1+4=7$ gives $x_1=1$. Check in the first equation: $1-2+6=5$ ✓.
Determinant Two interchanges, so $\det A=(+1)\cdot4\cdot\tfrac74\cdot\left(-\tfrac{15}7\right)=-15$. All multipliers $\tfrac12,\tfrac14,\tfrac67$ are at most $1$ in size.
✏️ Example 2 — Why pivoting matters: a tiny pivot in 3-digit arithmetic
Solve $0.0001\,x+y=1$, $x+y=2$ in floating-point arithmetic that keeps three significant digits, (a) without pivoting, (b) with partial pivoting. The exact solution is $x=1.00010\ldots$, $y=0.99990\ldots$
(a) $m_{21}=1/0.0001=10^4$. The second row becomes $(1-10^4)\,y=2-10^4$, i.e. $-9999\,y=-9998$; rounded to three digits both sides are $-1.00\times10^4$, so $y=1.00$. Back substitution: $0.0001\,x=1-1.00=0$, so $x=0$ — completely wrong.
(b) Interchange the rows (pivot $1\gt0.0001$): $m_{21}=0.0001$, and the new second row is $(1-0.0001)\,y=1-0.0002$, i.e. $1.00\,y=1.00$ after rounding. Then $y=1.00$ and $x=2-1.00=1.00$ — correct to three digits.
Diagnosis In (a) the huge multiplier $10^4$ swamps the information in row 2: the rounding error in $y$ is tiny, but back substitution divides it by the tiny pivot $0.0001$. The problem itself is well conditioned (the lines meet at a large angle); the algorithm without pivoting is unstable.

LU Factorisation: Doolittle, Crout and Cholesky

Gauss elimination secretly factorises the matrix. Keeping the factors is useful: a system with a new right-hand side then costs only $n^2$ operations, and the factors give the determinant for free.

📘 Definition 5.10 — LU factorisations

An LU factorisation of $A$ is $A=LU$ with $L$ lower triangular and $U$ upper triangular. It is the Doolittle factorisation if $L$ has unit diagonal ($l_{ii}=1$) and the Crout factorisation if $U$ has unit diagonal ($u_{ii}=1$). Once $A=LU$ is known, $Ax=b$ is solved by

$$Ly=b\ \ (\text{forward substitution}),\qquad Ux=y\ \ (\text{back substitution}).$$

Comparing entries of $A=LU$ row by row gives the Doolittle formulas (for $k=1,\dots,n$): $\ u_{kj}=a_{kj}-\sum_{s\lt k}l_{ks}u_{sj}$ ($j\ge k$) and $\ l_{ik}=\big(a_{ik}-\sum_{s\lt k}l_{is}u_{sk}\big)/u_{kk}$ ($i\gt k$).

📐 Theorem 5.14 — Existence and uniqueness of LU
A nonsingular matrix $A$ has a Doolittle factorisation $A=LU$ if and only if $\Delta_1,\dots,\Delta_{n-1}\ne0$; it is then unique, $L$ consists of the multipliers of Gauss elimination ($l_{ik}=m_{ik}$), $U$ is the eliminated matrix, and $\det A=u_{11}\cdots u_{nn}$. The Crout factorisation exists under the same condition and is $A=(LD)(D^{-1}U)$ with $D=\operatorname{diag}(u_{11},\dots,u_{nn})$.

Proof. Existence. By Theorem 5.11 elimination runs without interchanges. Step $k$ multiplies $A^{(k)}$ on the left by $E_k=I-\mathbf{m}_k\mathbf{e}_k^{\mathsf T}$, where $\mathbf{m}_k=(0,\dots,0,m_{k+1,k},\dots,m_{nk})^{\mathsf T}$. So $E_{n-1}\cdots E_1A=U$ and $A=E_1^{-1}\cdots E_{n-1}^{-1}U$. Since $E_k^{-1}=I+\mathbf{m}_k\mathbf{e}_k^{\mathsf T}$ and $\mathbf{e}_k^{\mathsf T}\mathbf{m}_j=0$ for $j\ge k$, the product $E_1^{-1}\cdots E_{n-1}^{-1}=I+\sum_k\mathbf{m}_k\mathbf{e}_k^{\mathsf T}=L$, the unit lower triangular matrix of multipliers. Necessity. If $A=LU$ with $L$ unit lower triangular, the leading $k\times k$ block of $A$ is $L_kU_k$ (the leading blocks of $L$ and $U$), so $\Delta_k=u_{11}\cdots u_{kk}$, and these are nonzero because $\det A=u_{11}\cdots u_{nn}\ne0$. Uniqueness. If $L_1U_1=L_2U_2$, then $L_2^{-1}L_1=U_2U_1^{-1}$ is both unit lower triangular and upper triangular, hence equal to $I$. ∎

For symmetric positive definite matrices — stiffness matrices, normal equations, covariance matrices — there is a symmetric factorisation at half the cost, and it needs no pivoting.

📐 Theorem 5.15 — Cholesky factorisation

A real symmetric matrix $A$ is positive definite if and only if $A=LL^{\mathsf T}$ for a lower triangular $L$ with positive diagonal entries; this $L$ is unique and is computed column by column from

$$l_{kk}=\sqrt{a_{kk}-\sum_{s\lt k}l_{ks}^2},\qquad l_{ik}=\frac{1}{l_{kk}}\Big(a_{ik}-\sum_{s\lt k}l_{is}l_{ks}\Big)\ \ (i\gt k).$$

The cost is about $\tfrac{n^3}{6}$ multiplications and $n$ square roots. If $A$ is symmetric but not positive definite, the algorithm meets a non-positive number under a square root.

Proof. ($\Leftarrow$) $x^{\mathsf T}Ax=\|L^{\mathsf T}x\|^2\gt0$ for $x\ne0$, because $L^{\mathsf T}$ is invertible. ($\Rightarrow$) Induction on $n$; $n=1$ is $a_{11}=l_{11}^2$ with $a_{11}\gt0$. Write $A=\begin{pmatrix}a&\mathbf{w}^{\mathsf T}\\ \mathbf{w}&B\end{pmatrix}$ with $a=a_{11}=\mathbf{e}_1^{\mathsf T}A\mathbf{e}_1\gt0$. Then $$A=\begin{pmatrix}\sqrt a&0\\ \mathbf{w}/\sqrt a&I\end{pmatrix}\begin{pmatrix}1&0\\0&S\end{pmatrix}\begin{pmatrix}\sqrt a&\mathbf{w}^{\mathsf T}/\sqrt a\\0&I\end{pmatrix},\qquad S=B-\frac{\mathbf{w}\mathbf{w}^{\mathsf T}}{a}.$$ The Schur complement $S$ is symmetric positive definite: for $\mathbf{y}\ne0$ put $x=(-\mathbf{w}^{\mathsf T}\mathbf{y}/a,\ \mathbf{y})$; then $x^{\mathsf T}Ax=\mathbf{y}^{\mathsf T}S\mathbf{y}\gt0$. By induction $S=L_SL_S^{\mathsf T}$, and $L=\begin{pmatrix}\sqrt a&0\\ \mathbf{w}/\sqrt a&L_S\end{pmatrix}$ works. Uniqueness: as in Theorem 5.14, $L_2^{-1}L_1=L_2^{\mathsf T}L_1^{-\mathsf T}$ is lower and upper triangular, hence diagonal, $D$ say, with $D=D^{-1}$ and positive entries, so $D=I$. The formulas are the entries of $A=LL^{\mathsf T}$ read in the order $(k,k)$, then $(i,k)$ for $i\gt k$. ∎

A third special structure is worth knowing: for a tridiagonal matrix (as in splines and in finite-difference boundary value problems) elimination without pivoting touches only three diagonals and costs $O(n)$ operations instead of $O(n^3)$ — the Thomas algorithm (Exercise II.7). It is safe when $A$ is diagonally dominant.

✏️ Example 3 — Doolittle and Crout factorisations; two right-hand sides
Let $A=\begin{pmatrix}1&2&1\\3&8&7\\2&7&9\end{pmatrix}$. Find its Doolittle and Crout factorisations and $\det A$, and use them to solve $Ax=b$ for $b=(4,18,18)^{\mathsf T}$ and for $b=(0,2,4)^{\mathsf T}$.
Row 1 $u_{11}=1$, $u_{12}=2$, $u_{13}=1$; $\ l_{21}=3$, $l_{31}=2$.
Row 2 $u_{22}=8-3\cdot2=2$, $u_{23}=7-3\cdot1=4$; $\ l_{32}=(7-2\cdot2)/2=\tfrac32$.
Row 3 $u_{33}=9-2\cdot1-\tfrac32\cdot4=1$. So $$L=\begin{pmatrix}1&0&0\\3&1&0\\2&\tfrac32&1\end{pmatrix},\quad U=\begin{pmatrix}1&2&1\\0&2&4\\0&0&1\end{pmatrix},$$ and $\det A=1\cdot2\cdot1=2$.
Crout With $D=\operatorname{diag}(1,2,1)$: $$LD=\begin{pmatrix}1&0&0\\3&2&0\\2&3&1\end{pmatrix},\quad D^{-1}U=\begin{pmatrix}1&2&1\\0&1&2\\0&0&1\end{pmatrix}.$$
Solve For $b=(4,18,18)$: $Ly=b$ gives $y=(4,\ 18-12,\ 18-8-9)=(4,6,1)$; $Ux=y$ gives $x_3=1$, $x_2=(6-4)/2=1$, $x_1=4-2-1=1$. For $b=(0,2,4)$: $y=(0,2,4-3)=(0,2,1)$, so $x_3=1$, $x_2=(2-4)/2=-1$, $x_1=0+2-1=1$: $x=(1,-1,1)$. Each new right-hand side cost only two triangular solves.
✏️ Example 4 — Cholesky: success and failure
(a) Find the Cholesky factor of $A=\begin{pmatrix}4&2&-2\\2&10&2\\-2&2&6\end{pmatrix}$ and solve $Ax=(2,4,4)^{\mathsf T}$. (b) Show that the algorithm fails for $B=\begin{pmatrix}1&2\\2&1\end{pmatrix}$ and explain why.
Column 1 $l_{11}=\sqrt4=2$, $l_{21}=2/2=1$, $l_{31}=-2/2=-1$.
Column 2 $l_{22}=\sqrt{10-1}=3$, $l_{32}=\big(2-(-1)(1)\big)/3=1$.
Column 3 $l_{33}=\sqrt{6-1-1}=2$. So $L=\begin{pmatrix}2&0&0\\1&3&0\\-1&1&2\end{pmatrix}$; all square roots were of positive numbers, which confirms that $A$ is positive definite (and $\det A=(2\cdot3\cdot2)^2=144$).
Solve $Ly=(2,4,4)$: $y_1=1$, $y_2=(4-1)/3=1$, $y_3=(4+1-1)/2=2$. $L^{\mathsf T}x=y$: $x_3=1$, $x_2=(1-1)/3=0$, $x_1=(1-0+1)/2=1$. So $x=(1,0,1)$.
(b) $l_{11}=1$, $l_{21}=2$, and then $l_{22}^2=1-4=-3\lt0$. $B$ is symmetric with positive diagonal but not positive definite ($\det B=-3$, eigenvalues $3$ and $-1$): positive diagonal entries are necessary, not sufficient.

Iterative Methods: Jacobi and Gauss–Seidel

For a large sparse matrix (a few nonzeros per row), elimination fills in the zeros and its $n^3$ cost is prohibitive. An iterative method instead rewrites $Ax=b$ as a fixed-point problem $x=Tx+c$ — the vector analogue of §5.1 — and each step costs only one pass over the nonzero entries.

📘 Definition 5.11 — Jacobi and Gauss–Seidel iterations

Assume $a_{ii}\ne0$ for all $i$ and split $A=L+D+U$, with $D$ the diagonal part, $L$ the strictly lower and $U$ the strictly upper triangular part. From $x^{(0)}$:

  • Jacobi iteration (all components from the old vector): $$x^{(k+1)}_i=\frac{1}{a_{ii}}\Big(b_i-\sum_{j\ne i}a_{ij}x^{(k)}_j\Big),$$ i.e. $x^{(k+1)}=T_Jx^{(k)}+D^{-1}b$ with $T_J=-D^{-1}(L+U)$;
  • Gauss–Seidel iteration (new components are used as soon as they are known): $$x^{(k+1)}_i=\frac{1}{a_{ii}}\Big(b_i-\sum_{j\lt i}a_{ij}x^{(k+1)}_j-\sum_{j\gt i}a_{ij}x^{(k)}_j\Big),$$ i.e. $x^{(k+1)}=T_{GS}\,x^{(k)}+(D+L)^{-1}b$ with $T_{GS}=-(D+L)^{-1}U$.

$T_J$ and $T_{GS}$ are the iteration matrices. In both cases the exact solution satisfies $x=Tx+c$, so the error $e^{(k)}=x^{(k)}-x$ obeys $e^{(k+1)}=Te^{(k)}$, i.e. $e^{(k)}=T^ke^{(0)}$.

📘 Definition 5.12 — Spectral radius; diagonal dominance
The spectral radius of a square matrix $T$ is $\rho(T)=\max\{|\lambda|:\lambda\text{ an eigenvalue of }T\}$ (complex eigenvalues included). $A$ is strictly (row) diagonally dominant if $|a_{ii}|\gt\sum_{j\ne i}|a_{ij}|$ for every $i$, and strictly column diagonally dominant if $A^{\mathsf T}$ is. For any induced matrix norm (see the CSIR NET Unit 1 course), $\rho(T)\le\|T\|$, since $Tv=\lambda v$ gives $|\lambda|\,\|v\|\le\|T\|\,\|v\|$; recall $\|T\|_\infty=\max_i\sum_j|t_{ij}|$ (maximum row sum) and $\|T\|_1$ = maximum column sum.
📐 Theorem 5.16 — Convergence of stationary iterations

Let $x=Tx+c$ have the solution $x$. The iteration $x^{(k+1)}=Tx^{(k)}+c$ converges to $x$ for every starting vector $x^{(0)}$ if and only if $\rho(T)\lt1$. A sufficient condition is $\|T\|\lt1$ for some induced norm, and then

$$\|x^{(k)}-x\|\le\|T\|^k\|x^{(0)}-x\|,\qquad \|x^{(k)}-x\|\le\frac{\|T\|}{1-\|T\|}\,\|x^{(k)}-x^{(k-1)}\|.$$

Asymptotically the error shrinks by the factor $\rho(T)$ per step, so about $-\log_{10}\rho(T)$ correct digits are gained per iteration.

Proof. Since $e^{(k)}=T^ke^{(0)}$ and $e^{(0)}$ is arbitrary, convergence for every start means $T^k\to0$. ($\Rightarrow$) Let $Tv=\lambda v$ with $|\lambda|=\rho(T)\ge1$, $v\ne0$ (possibly complex). Then $T^kv=\lambda^kv\not\to0$. Write $v=v_1+iv_2$ with real $v_1,v_2$; as $T$ is real, $T^kv=T^kv_1+iT^kv_2$, so $T^kv_1$ or $T^kv_2$ does not tend to $0$ — a real starting error that is not damped. ($\Leftarrow$) Use the Jordan form $T=SJS^{-1}$. A Jordan block $\lambda I+N$ of size $m$ ($N^m=0$) has $$(\lambda I+N)^k=\sum_{j=0}^{m-1}\binom kj\lambda^{k-j}N^j,$$ and $\binom kj|\lambda|^{k-j}\le k^j|\lambda|^{k-j}\to0$ when $|\lambda|\lt1$. Hence $J^k\to0$ and $T^k=SJ^kS^{-1}\to0$. The bounds: $\|e^{(k)}\|\le\|T\|^k\|e^{(0)}\|$ is submultiplicativity; and $x^{(k)}-x=T(x^{(k-1)}-x)$ gives $\|x^{(k)}-x\|$ $\le\|T\|\big(\|x^{(k)}-x^{(k-1)}\|+\|x^{(k)}-x\|\big)$, which rearranges to the a posteriori bound. Finally, Gelfand's formula $\|T^k\|^{1/k}\to\rho(T)$ (also a consequence of the Jordan form) shows that $\rho(T)$ is the asymptotic factor. ∎

📐 Theorem 5.17 — Diagonal dominance implies convergence

If $A$ is strictly row diagonally dominant, the Jacobi and Gauss–Seidel iterations converge for every $x^{(0)}$. With $\alpha_i=\sum_{j\lt i}|a_{ij}|/|a_{ii}|$ and $\beta_i=\sum_{j\gt i}|a_{ij}|/|a_{ii}|$,

$$\|T_J\|_\infty=\max_i(\alpha_i+\beta_i)\lt1,\qquad \|T_{GS}\|_\infty\le\max_i\frac{\beta_i}{1-\alpha_i}\le\|T_J\|_\infty .$$

Proof. The $i$-th row of $T_J=-D^{-1}(L+U)$ has entries $-a_{ij}/a_{ii}$ ($j\ne i$) and $0$, so its absolute row sum is $\alpha_i+\beta_i\lt1$ by diagonal dominance; apply Theorem 5.16. For Gauss–Seidel let $y=T_{GS}x$, i.e. $(D+L)y=-Ux$, so $$y_i=-\frac1{a_{ii}}\Big(\sum_{j\lt i}a_{ij}y_j+\sum_{j\gt i}a_{ij}x_j\Big).$$ Choose $i$ with $|y_i|=\|y\|_\infty$. Then $\|y\|_\infty\le\alpha_i\|y\|_\infty+\beta_i\|x\|_\infty$, so $\|y\|_\infty\le\frac{\beta_i}{1-\alpha_i}\|x\|_\infty$ (note $\alpha_i\lt1$). Finally $\frac{\beta_i}{1-\alpha_i}\le\alpha_i+\beta_i$ because $(\alpha_i+\beta_i)(1-\alpha_i)-\beta_i=\alpha_i(1-\alpha_i-\beta_i)\ge0$. ∎

Diagonal dominance is sufficient, not necessary. Two further results are used constantly in examinations.

📐 Theorem 5.18 — Symmetric positive definite and tridiagonal matrices
  1. If $A$ is symmetric positive definite, the Gauss–Seidel iteration converges for every $x^{(0)}$. (The Jacobi iteration need not: it converges for all such $A$ only if $2D-A$ is also positive definite.)
  2. If $A$ is tridiagonal with nonzero diagonal (in particular, if $n=2$), then $\mu$ is an eigenvalue of $T_J$ iff $-\mu$ is, and the nonzero eigenvalues of $T_{GS}$ are exactly the squares $\mu^2$ of the eigenvalues of $T_J$. Hence $$\rho(T_{GS})=\rho(T_J)^2:$$ the two methods converge or diverge together, and Gauss–Seidel gains twice as many digits per step.

Proof. (2) $\lambda$ is an eigenvalue of $T_{GS}$ iff $-Uv=\lambda(D+L)v$ for some $v\ne0$, i.e. $\det(\lambda D+\lambda L+U)=0$; similarly $\mu$ is an eigenvalue of $T_J$ iff $\det(\mu D+L+U)=0$. For a tridiagonal matrix, conjugating by $S=\operatorname{diag}(1,\gamma,\gamma^2,\dots)$ multiplies the subdiagonal by $\gamma$ and the superdiagonal by $\gamma^{-1}$, so $\det(\mu D+\gamma L+\gamma^{-1}U)=\det(\mu D+L+U)$ for every $\gamma\ne0$. With $\gamma=-1$ this shows that $-\mu$ is an eigenvalue of $T_J$ whenever $\mu$ is. With $\lambda=\mu^2$, $\mu\ne0$, $$\det(\mu^2D+\mu^2L+U)=\mu^n\det(\mu D+\mu L+\mu^{-1}U)=\mu^n\det(\mu D+L+U),$$ so $\mu^2$ is an eigenvalue of $T_{GS}$ iff $\mu$ is one of $T_J$. (1) (Sketch.) Let $T_{GS}v=\lambda v$, $v\ne0$, and normalise $v^*Dv=1$; with $U=L^{\mathsf T}$ and $a=v^*Lv$, the relation $-L^{\mathsf T}v=\lambda(D+L)v$ gives $-\bar a=\lambda(1+a)$, and $v^*Av=1+a+\bar a\gt0$. A short computation gives $1-|\lambda|^2=\dfrac{v^*Av}{|1+a|^2}\gt0$. ∎

For a $2\times2$ matrix everything is explicit: if $A=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ with $ad\ne0$, then $T_J=\begin{pmatrix}0&-b/a\\-c/d&0\end{pmatrix}$ has eigenvalues $\pm\sqrt{bc/(ad)}$, and $T_{GS}=\begin{pmatrix}0&-b/a\\0&bc/(ad)\end{pmatrix}$ has eigenvalues $0$ and $bc/(ad)$. Both converge iff $|bc|\lt|ad|$.

Interactive 1 — Jacobi versus Gauss–Seidel in the Plane

A $2\times2$ system is a pair of lines; the solution is where they cross. Gauss–Seidel moves horizontally onto line 1 (solving equation 1 for $x$) and then vertically onto line 2 — a staircase between the lines. Jacobi does both updates from the old point at once, so it jumps diagonally and needs two steps for each Gauss–Seidel step. Compare $\rho(T_J)$ and $\rho(T_{GS})=\rho(T_J)^2$, and try the last two systems: the same equations in a different order.

iteration k—
Jacobi error—
Gauss–Seidel error—
ρ(T_J)—
ρ(T_GS)—
✏️ Example 5 — Jacobi and Gauss–Seidel for a diagonally dominant system
Solve $10x-y+2z=6$, $-x+11y-z=22$, $2x-y+10z=-10$ by both methods from $x^{(0)}=0$ (exact solution $(1,2,-1)$). Bound $\|T_J\|_\infty$ and $\|T_{GS}\|_\infty$ and compare with the observed errors.
Formulas $x\leftarrow\tfrac{1}{10}(6+y-2z)$, $\ y\leftarrow\tfrac1{11}(22+x+z)$, $\ z\leftarrow\tfrac1{10}(-10-2x+y)$ — Jacobi uses old values on the right, Gauss–Seidel the newest available.
Jacobi $x^{(1)}=(0.6,\ 2,\ -1)$, $x^{(2)}=(1,\ 1.963\,64,\ -0.92)$, $x^{(3)}=(0.980\,36,\ 2.007\,27,\ -1.003\,64)$. Max errors $0.4,\ 0.08,\ 0.0196,\ 0.0047,\ 0.0011$: a factor of about $4$ per step.
Gauss–Seidel $x_1=0.6$, then $y_1=\tfrac{22+0.6}{11}=2.054\,55$, then $z_1=\tfrac{-10-1.2+2.054\,55}{10}=-0.914\,55$. Next $x^{(2)}=(0.988\,36,\ 2.006\,71,\ -0.997\,00)$, $x^{(3)}=(1.000\,07,\ 2.000\,28,\ -0.999\,99)$. Max errors $0.4,\ 0.0116,\ 0.000\,28,\ 0.000\,025$: much faster.
Theory The row sums $\alpha_i+\beta_i$ are $0.3,\ 0.18,\ 0.3$, so $\|T_J\|_\infty=0.3$; for Gauss–Seidel $\max\beta_i/(1-\alpha_i)=\max(0.3$, $0.0909/0.909$, $0)=0.3$ as well. The actual spectral radii are smaller, $\rho(T_J)\approx0.268$ and $\rho(T_{GS})\approx0.043$, which matches the observed error ratios — the norm is only an upper bound.
✏️ Example 6 — Prove or disprove
(a) If the Jacobi iteration converges for $A$, so does Gauss–Seidel. (b) If Gauss–Seidel converges for $A$, so does Jacobi. (c) If Gauss–Seidel converges for $A$, then $A$ is diagonally dominant. (d) For every $2\times2$ matrix with nonzero diagonal, Jacobi converges iff Gauss–Seidel converges.
(a) False Let $A=\begin{pmatrix}1&1&-1\\2&1&-2\\-2&2&1\end{pmatrix}$. Then $T_J=I-A$ has characteristic polynomial $\lambda^3$, so $T_J^3=0$, $\rho(T_J)=0$, and Jacobi reaches the exact solution in at most three steps from any start. But $$T_{GS}=\begin{pmatrix}0&-1&1\\0&2&0\\0&-6&2\end{pmatrix},$$ with eigenvalues $0,2,2$: $\rho(T_{GS})=2$ and Gauss–Seidel diverges.
(b) False $A=\begin{pmatrix}1&\tfrac34&\tfrac34\\ \tfrac34&1&\tfrac34\\ \tfrac34&\tfrac34&1\end{pmatrix}$ is symmetric positive definite (eigenvalues $\tfrac52,\tfrac14,\tfrac14$), so Gauss–Seidel converges (Theorem 5.18(1)); in fact $\rho(T_{GS})=\sqrt{27/64}\approx0.65$. But $T_J=-\tfrac34\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}$ has eigenvalues $-\tfrac32,\tfrac34,\tfrac34$, so $\rho(T_J)=1.5$ and Jacobi diverges. (Here $2D-A$ has eigenvalue $2-\tfrac52\lt0$.)
(c) False The same matrix: $1\lt\tfrac34+\tfrac34$ in every row, yet Gauss–Seidel converges.
(d) True By the computation after Theorem 5.18, $\rho(T_J)=\sqrt{|bc/(ad)|}$ and $\rho(T_{GS})=|bc/(ad)|$; one is less than $1$ iff the other is.

Successive Over-Relaxation and the Condition Number

Gauss–Seidel moves each component to the value that satisfies its equation. If the iterates creep monotonically towards the solution, it pays to overshoot a little.

📘 Definition 5.13 — Successive over-relaxation (SOR)

For a relaxation parameter $\omega$, compute the Gauss–Seidel value $\tilde x_i$ and take a weighted average with the old value:

$$x^{(k+1)}_i=(1-\omega)\,x^{(k)}_i+\omega\,\tilde x_i .$$

In matrix form $x^{(k+1)}=T_\omega x^{(k)}+\omega(D+\omega L)^{-1}b$ with $T_\omega=(D+\omega L)^{-1}\big((1-\omega)D-\omega U\big)$. $\omega=1$ is Gauss–Seidel; $\omega\gt1$ is over-relaxation, $\omega\lt1$ under-relaxation.

📐 Theorem 5.19 — Kahan's bound; facts about SOR
  1. (Kahan) For every $A$ with nonzero diagonal, $\rho(T_\omega)\ge|\omega-1|$. Hence SOR can converge for every start only if $0\lt\omega\lt2$.
  2. (Ostrowski–Reich, statement) If $A$ is symmetric positive definite, SOR converges for every $\omega\in(0,2)$.
  3. (Young, statement) If $A$ is tridiagonal with $T_J$ having real eigenvalues and $\rho_J=\rho(T_J)\lt1$, the optimal parameter and the resulting spectral radius are $$\omega_{\rm opt}=\frac{2}{1+\sqrt{1-\rho_J^2}},\qquad \rho(T_{\omega_{\rm opt}})=\omega_{\rm opt}-1 .$$

Proof of (1). $\det T_\omega$ $=\dfrac{\det\big((1-\omega)D-\omega U\big)}{\det(D+\omega L)}$ $=\dfrac{(1-\omega)^n\det D}{\det D}=(1-\omega)^n$, because both matrices are triangular with diagonals $(1-\omega)D$ and $D$. The determinant is the product of the $n$ eigenvalues, so at least one of them has $|\lambda|\ge|1-\omega|$. If $\omega\le0$ or $\omega\ge2$, then $\rho(T_\omega)\ge1$ and Theorem 5.16 rules out convergence for every start. ∎

The gain from (3) is spectacular when $\rho_J$ is close to $1$, as it is for fine discretisations of Laplace's equation (see the Research–Teaching Nexus below): with $\rho_J=0.99$, Gauss–Seidel has $\rho=0.98$, but SOR with $\omega_{\rm opt}\approx1.75$ has $\rho\approx0.75$.

Finally, how accurate can any computed solution be? Small changes in the data — measurement errors in $b$, rounding in $A$ — can produce large changes in $x$. The amplification factor is a property of the matrix, not of the algorithm.

📘 Definition 5.14 — Condition number
For a nonsingular $A$ and an induced matrix norm, the condition number of $A$ is $$\kappa(A)=\|A\|\,\|A^{-1}\|.$$ Always $\kappa(A)\ge\|AA^{-1}\|=\|I\|=1$, and $\kappa(cA)=\kappa(A)$ for $c\ne0$. For symmetric $A$ and the Euclidean norm, $\kappa_2(A)=|\lambda|_{\max}/|\lambda|_{\min}$. A matrix with large $\kappa$ is called ill-conditioned.
📐 Theorem 5.20 — Perturbation bounds

Let $Ax=b$ with $A$ nonsingular and $b\ne0$.

  1. If $A(x+\delta x)=b+\delta b$, then $\dfrac{\|\delta x\|}{\|x\|}\le\kappa(A)\,\dfrac{\|\delta b\|}{\|b\|}$.
  2. If $(A+\delta A)(x+\delta x)=b$, then $\dfrac{\|\delta x\|}{\|x+\delta x\|}\le\kappa(A)\,\dfrac{\|\delta A\|}{\|A\|}$.
  3. For any approximation $\hat x$ with residual $r=b-A\hat x$: $\ \dfrac{\|x-\hat x\|}{\|x\|}\le\kappa(A)\,\dfrac{\|r\|}{\|b\|}$.

The bounds are attained for suitable $b$ and $\delta b$, so $\kappa(A)$ is exactly the worst-case amplification of relative errors.

Proof. (1) Subtracting, $A\,\delta x=\delta b$, so $\|\delta x\|\le\|A^{-1}\|\,\|\delta b\|$; and $\|b\|=\|Ax\|\le\|A\|\,\|x\|$ gives $1/\|x\|\le\|A\|/\|b\|$. Multiply. (2) Expanding, $A\,\delta x=-\delta A\,(x+\delta x)$, so $\|\delta x\|\le\|A^{-1}\|\,\|\delta A\|\,\|x+\delta x\|$ $=\kappa(A)\frac{\|\delta A\|}{\|A\|}\|x+\delta x\|$. (3) is (1) with $\hat x=x+\delta x$, $\delta b=-r$. Sharpness: choose $x$ with $\|Ax\|=\|A\|\,\|x\|$ and $\delta b$ with $\|A^{-1}\delta b\|=\|A^{-1}\|\,\|\delta b\|$ (possible because induced norms are maxima). ∎

Rule of thumb: with data accurate to $t$ digits and $\kappa(A)\approx10^q$, expect only about $t-q$ correct digits in $x$, whatever method is used. A small residual certifies a small error only when $\kappa(A)$ is modest.

✏️ Example 7 — Nearly parallel lines
Let $A=\begin{pmatrix}1&1\\1&1.01\end{pmatrix}$ and $b=(2,\ 2.01)^{\mathsf T}$, so $x=(1,1)^{\mathsf T}$. Compute $\kappa_\infty(A)$. Solve again with $b'=(2,\ 2.02)^{\mathsf T}$, and compute the residual of the guess $\hat x=(2,0)^{\mathsf T}$. Compare with Theorem 5.20.
Inverse $\det A=0.01$ and $A^{-1}=100\begin{pmatrix}1.01&-1\\-1&1\end{pmatrix}$ $=\begin{pmatrix}101&-100\\-100&100\end{pmatrix}$. So $\|A\|_\infty=2.01$, $\|A^{-1}\|_\infty=201$ and $\kappa_\infty(A)=404.01$.
Perturb $b$ $x'=A^{-1}b'=(202-202$, $-200+202)=(0$, $2)$. A change of $0.01$ in one entry of $b$ — a relative change $\tfrac{0.01}{2.01}\approx0.5\%$ — moved the solution by $\|\delta x\|_\infty=1$, a relative change of $100\%$: amplification $201\le\kappa_\infty=404$.
Residual $A\hat x=(2,\ 2)$, so $r=(0,\ 0.01)$: tiny, yet $\hat x$ is completely wrong ($\|x-\hat x\|_\infty=1$). Theorem 5.20(3) allows exactly this: $\kappa\,\|r\|/\|b\|=404\cdot0.005=2$.
Geometry The two equations are lines with slopes $-1$ and $-1/1.01$, almost parallel; sliding one of them slightly moves their intersection far along both. Explore this in Interactive 2.
Interactive 2 — Ill-Conditioning: Nearly Parallel Lines

The system $x+y=2$, $x+(1+\delta)y=2+\delta+\eta$ has the solution $(1,1)$ when $\eta=0$. The slider $\delta$ controls the angle between the lines; $\eta$ is a small error in the right-hand side. Watch the perturbed solution run away from the true solution as the lines become parallel, and compare the actual amplification of relative error with the bound $\kappa_\infty(A)$ of Theorem 5.20. Press Play to let $\eta$ oscillate.

——
κ∞(A)—
rel. change in b—
rel. change in x—
amplification—
perturbed solution—
🧭 Problem-solving strategy — linear systems in the examination hall
  1. Entries of $L$ and $U$. Doolittle: the first row of $U$ is the first row of $A$; the first column of $L$ is the first column of $A$ divided by $a_{11}$; continue row by row. Check: $\det A=\prod u_{kk}$ and $\Delta_k=u_{11}\cdots u_{kk}$.
  2. Does LU (without pivoting) exist? Check the leading principal minors $\Delta_1,\dots,\Delta_{n-1}$.
  3. Cholesky? Symmetric, and all leading principal minors positive (Sylvester's criterion).
  4. Jacobi/Gauss–Seidel convergence. First look for strict diagonal dominance (rows or columns) — possibly after reordering the equations. For symmetric positive definite $A$, Gauss–Seidel converges. For $2\times2$ and tridiagonal matrices use $\rho(T_{GS})=\rho(T_J)^2$. Otherwise compute the characteristic polynomial of the iteration matrix.
  5. Operation counts. Elimination $\approx\tfrac{n^3}{3}$ multiplications; exactly $\tfrac{n^3}{3}+n^2-\tfrac n3$ with back substitution; triangular solve $\approx\tfrac{n^2}{2}$; Cholesky $\approx\tfrac{n^3}{6}$; tridiagonal $O(n)$.
  6. Conditioning. $\kappa=\|A\|\,\|A^{-1}\|\ge1$; for $2\times2$ matrices write down $A^{-1}$ and take maximum absolute row sums.
⚠️ Counterexamples and pitfalls
  1. A nonsingular matrix need not have an LU factorisation. $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ has $\Delta_1=0$; it needs a row interchange ($PA=LU$ always exists).
  2. Nonzero pivots are not enough. A tiny pivot gives huge multipliers and wrong answers (Example 2); use partial pivoting.
  3. Positive diagonal does not mean positive definite. $\begin{pmatrix}1&2\\2&1\end{pmatrix}$ breaks the Cholesky algorithm.
  4. Jacobi and Gauss–Seidel are independent. Jacobi can converge while Gauss–Seidel diverges, and conversely (Example 6); only for $2\times2$ and tridiagonal (more generally, consistently ordered) matrices do they behave alike.
  5. Diagonal dominance is sufficient, not necessary (Example 6(c)); and weak dominance ($\ge$) is not sufficient: $\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$ is singular.
  6. The order of the equations matters. $x+4y=5$, $3x+y=4$: Jacobi has $\rho(T_J)=\sqrt{12}$ and diverges; written as $3x+y=4$, $x+4y=5$ it has $\rho(T_J)=1/\sqrt{12}$ and converges.
  7. $\|T\|\ge1$ does not imply divergence. $T=\begin{pmatrix}0.5&10\\0&0.5\end{pmatrix}$ has $\|T\|_\infty=10.5$ but $\rho(T)=0.5$: the iteration converges — after the error first grows for several steps.
  8. A small residual does not mean a small error for ill-conditioned systems (Example 7).
  9. A small determinant does not mean ill-conditioning, and vice versa. $10^{-3}I_{10}$ has determinant $10^{-30}$ and $\kappa=1$; $\begin{pmatrix}1&1000\\0&1\end{pmatrix}$ has determinant $1$ and $\kappa_\infty=1001^2\approx10^6$.
  10. Over-relaxation is not automatically better. For $\begin{pmatrix}4&-1\\-1&4\end{pmatrix}$, $\rho(T_{GS})=\tfrac1{16}$ but $\rho(T_{1.25})=0.25$; and SOR with $\omega\notin(0,2)$ never converges for every start (Theorem 5.19).
  11. Cramer's rule and explicit inverses are for theory. Computing $A^{-1}$ costs about three times as much as an LU solve and is less accurate.

Exercises

I
Gauss elimination and pivoting.
  • 1 Solve $x+y+z=6$, $2x+3y+5z=23$, $4x+5z=19$ by Gauss elimination without pivoting, listing the multipliers.
  • 2 Solve $2y+z=0$, $x+y+z=2$, $2x+y+3z=7$ by Gauss elimination with partial pivoting, and obtain $\det A$ from the result.
  • 3 How many multiplications/divisions and additions/subtractions does Gauss elimination with back substitution need for $n=4$? Roughly how many multiplications for $n=1000$?
  • 4 Show that Gauss–Jordan elimination (making $A$ into $I$) needs about $\tfrac{n^3}{2}$ multiplications.
  • 5 For $A_k=\begin{pmatrix}1&2&3\\2&k&5\\3&5&8\end{pmatrix}$ find the pivots of elimination without interchanges. For which $k$ does it break down, and for which $k$ is $A_k$ singular?
  • 6 Solve $10^{-5}x+y=1$, $x+y=2$ in 4-significant-digit arithmetic, without and with partial pivoting.
  • 7 Find $P$, $L$, $U$ with $PA=LU$ by partial pivoting for $A=\begin{pmatrix}1&2&1\\2&2&3\\4&1&2\end{pmatrix}$, and $\det A$.
  • 8 Prove that if $A$ is strictly diagonally dominant by columns, then partial pivoting never interchanges rows. (Show that one elimination step preserves column dominance.)
1 $m_{21}=2$, $m_{31}=4$: rows become $(0,1,3\,|\,11)$ and $(0,-4,1\,|\,-5)$. $m_{32}=-4$: $(0,0,13\,|\,39)$. Back substitution: $z=3$, $y=11-9=2$, $x=6-2-3=1$.
2 Column 1: largest $|a_{i1}|$ is $2$ (row 3): swap rows 1, 3. $m_{21}=\tfrac12$, $m_{31}=0$: rows $(0,\tfrac12,-\tfrac12\,|\,-\tfrac32)$, $(0,2,1\,|\,0)$. Column 2: $2\gt\tfrac12$, swap; $m_{32}=\tfrac14$: $(0,0,-\tfrac34\,|\,-\tfrac32)$. So $z=2$, $y=(0-2)/2=-1$, $x=(7+1-6)/2=1$. Two swaps: $\det A=(+1)\cdot2\cdot2\cdot(-\tfrac34)=-3$.
3 $\tfrac{64}{3}+16-\tfrac43=36$ multiplications/divisions and $\tfrac{64}3+8-\tfrac{10}3=26$ additions/subtractions. For $n=1000$: about $\tfrac13\cdot10^9\approx3.3\times10^8$ multiplications — well under a second on a laptop.
4 At step $k$ every one of the other $n-1$ rows is updated in columns $k+1,\dots,n$ and in $b$: $(n-1)(n-k+1)$ multiplications, plus $n-k+1$ divisions to normalise the pivot row. Summing over $k$, the updates give $(n-1)\sum_{k=1}^n(n-k+1)$ $=(n-1)\tfrac{n(n+1)}2$ multiplications, and the divisions only $O(n^2)$: in total $\tfrac{n^3}2+O(n^2)$ — 50% more than elimination plus back substitution.
5 $\Delta_1=1$, $\Delta_2=k-4$, $\Delta_3=\det A_k=3-k$. By Theorem 5.11 the pivots are $1,\ k-4,\ \dfrac{3-k}{k-4}$. Elimination breaks down (second pivot $0$) iff $k=4$, although $A_4$ is nonsingular ($\det=-1$); $A_k$ is singular iff $k=3$, in which case elimination runs but the last pivot is $0$.
6 Without pivoting: $m=10^5$, $(1-10^5)y=2-10^5$; both $-99999$ and $-99998$ round to $-1.000\times10^5$, so $y=1.000$ and $x=(1-1.000)/10^{-5}=0$. With pivoting: $m=10^{-5}$, $(1-10^{-5})y=1-2\times10^{-5}$ rounds to $1.000\,y=1.000$; $y=1.000$, $x=2-1.000=1.000$. True solution $x=1.00001\ldots$, $y=0.99999\ldots$
7 Swap rows 1, 3 (pivot $4$); $m_{21}=\tfrac24=\tfrac12$, $m_{31}=\tfrac14$ (for the rows now in positions 2, 3: original rows 2 and 1). Remaining rows: $(0,\tfrac32,2)$ and $(0,\tfrac74,\tfrac12)$; swap (pivot $\tfrac74$), $m=\tfrac{3/2}{7/4}=\tfrac67$, last pivot $2-\tfrac67\cdot\tfrac12=\tfrac{11}7$. With the multipliers permuted along with the rows: $$P=\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix},\ L=\begin{pmatrix}1&0&0\\ \tfrac14&1&0\\ \tfrac12&\tfrac67&1\end{pmatrix},\ U=\begin{pmatrix}4&1&2\\0&\tfrac74&\tfrac12\\0&0&\tfrac{11}7\end{pmatrix}.$$ $P$ is a 3-cycle (two swaps), so $\det A=4\cdot\tfrac74\cdot\tfrac{11}7=11$.
8 Column dominance $|a_{11}|\gt\sum_{i\gt1}|a_{i1}|$ makes $a_{11}$ the largest entry of column 1, so no swap at step 1. After the step, $a'_{ij}=a_{ij}-a_{i1}a_{1j}/a_{11}$ ($i,j\ge2$). For a column $j\ge2$: $$\sum_{i\ge2,\,i\ne j}|a'_{ij}|\le\sum_{i\ge2,\,i\ne j}|a_{ij}|+\frac{|a_{1j}|}{|a_{11}|}\sum_{i\ge2,\,i\ne j}|a_{i1}|\lt\big(|a_{jj}|-|a_{1j}|\big)+\frac{|a_{1j}|}{|a_{11}|}\big(|a_{11}|-|a_{j1}|\big),$$ which equals $|a_{jj}|-\frac{|a_{1j}a_{j1}|}{|a_{11}|}\le|a'_{jj}|$. So the reduced matrix is again column dominant; induct.
II
LU and Cholesky factorisations.
  • 1 Find the Doolittle factorisation of $A=\begin{pmatrix}2&1&3\\4&3&5\\-2&2&-2\end{pmatrix}$ and $\det A$.
  • 2 Find the Crout factorisation of the same matrix.
  • 3 Use the factorisation to solve $Ax=b$ for $b=(6,12,-2)^{\mathsf T}$ and $b=(-1,-1,0)^{\mathsf T}$.
  • 4 Find the Cholesky factor of $\begin{pmatrix}9&-3&6\\-3&5&0\\6&0&6\end{pmatrix}$.
  • 5 For which real $\alpha$ does $\begin{pmatrix}1&\alpha&0\\ \alpha&1&\alpha\\0&\alpha&1\end{pmatrix}$ have a Cholesky factorisation? Find the factor.
  • 6 Let $A$ be symmetric with $\Delta_1,\dots,\Delta_n\ne0$. Show that $A=LDL^{\mathsf T}$ with $L$ unit lower triangular and $D$ diagonal, and that $A$ is positive definite iff all entries of $D$ are positive.
  • 7 Solve $\begin{pmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{pmatrix}x=\begin{pmatrix}1\\0\\1\end{pmatrix}$ by elimination for tridiagonal systems (Thomas algorithm) and estimate its cost for $n$ unknowns.
  • 8 Compute $A^{-1}$ for the matrix of Exercise 1 by solving $Ax=e_j$, $j=1,2,3$, with its LU factors. Why do numerical analysts solve $Ax=b$ rather than compute $A^{-1}b$?
1 $u_{1j}=(2,1,3)$; $l_{21}=2$, $l_{31}=-1$. $u_{22}=3-2=1$, $u_{23}=5-6=-1$; $l_{32}=(2-(-1)(1))/1=3$. $u_{33}=-2-(-1)(3)-3(-1)=4$. $$L=\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix},\ U=\begin{pmatrix}2&1&3\\0&1&-1\\0&0&4\end{pmatrix},$$ $\det A=2\cdot1\cdot4=8$.
2 $A=(LD)(D^{-1}U)$, $D=\operatorname{diag}(2,1,4)$: $$L_C=\begin{pmatrix}2&0&0\\4&1&0\\-2&3&4\end{pmatrix},\ U_C=\begin{pmatrix}1&\tfrac12&\tfrac32\\0&1&-1\\0&0&1\end{pmatrix}.$$
3 $b=(6,12,-2)$: $y=(6,\ 0,\ -2+6-0)=(6,0,4)$, then $x_3=1$, $x_2=0+1=1$, $x_1=(6-1-3)/2=1$: $x=(1,1,1)$. $b=(-1,-1,0)$: $y=(-1,\ 1,\ 0-1-3)=(-1,1,-4)$, so $x_3=-1$, $x_2=1-1=0$, $x_1=(-1+3)/2=1$: $x=(1,0,-1)$.
4 $l_{11}=3$, $l_{21}=-1$, $l_{31}=2$; $l_{22}=\sqrt{5-1}=2$, $l_{32}=(0-(2)(-1))/2=1$; $l_{33}=\sqrt{6-4-1}=1$. $L=\begin{pmatrix}3&0&0\\-1&2&0\\2&1&1\end{pmatrix}$.
5 Leading minors $1$, $1-\alpha^2$, $1-2\alpha^2$: positive definite iff $|\alpha|\lt\tfrac1{\sqrt2}$ (Sylvester). Then $l_{11}=1$, $l_{21}=\alpha$, $l_{22}=\sqrt{1-\alpha^2}$, $l_{32}=\dfrac{\alpha}{\sqrt{1-\alpha^2}}$, $l_{33}=\sqrt{\dfrac{1-2\alpha^2}{1-\alpha^2}}$ (and $l_{31}=0$).
6 By Theorem 5.14, $A=LU$ uniquely; write $U=DM$ with $D=\operatorname{diag}(u_{kk})$ and $M$ unit upper triangular. Then $A=A^{\mathsf T}=M^{\mathsf T}(DL^{\mathsf T})$ is another Doolittle factorisation, so by uniqueness $M^{\mathsf T}=L$: $A=LDL^{\mathsf T}$. Since $x\mapsto L^{\mathsf T}x$ is a bijection, $x^{\mathsf T}Ax=y^{\mathsf T}Dy$ with $y=L^{\mathsf T}x$, which is positive for all $y\ne0$ iff every $d_{kk}\gt0$. (Then $L\sqrt D$ is the Cholesky factor.)
7 $m_{21}=-\tfrac12$: row 2 becomes $(0,\tfrac32,-1\,|\,\tfrac12)$. $m_{32}=-\tfrac23$: row 3 becomes $(0,0,\tfrac43\,|\,\tfrac43)$. So $x_3=1$, $x_2=(\tfrac12+1)/\tfrac32=1$, $x_1=(1+1)/2=1$. Only one multiplier and one update per row: about $3n$ multiplications/divisions for the elimination and $2n$ for back substitution — $O(n)$ instead of $O(n^3)$.
8 Solving with $e_1,e_2,e_3$ gives the columns of $$A^{-1}=\begin{pmatrix}-2&1&-\tfrac12\\-\tfrac14&\tfrac14&\tfrac14\\ \tfrac74&-\tfrac34&\tfrac14\end{pmatrix}$$ (check: $A\,A^{-1}=I$; the first column solves $Ax=e_1$ with $y=(1,-2,7)$). Forming $A^{-1}$ costs about $n^3$ multiplications against $\tfrac{n^3}{3}$ for one LU solve, and multiplying $A^{-1}b$ adds rounding errors without adding accuracy.
III
Jacobi and Gauss–Seidel.
  • 1 Perform two Jacobi iterations from $x^{(0)}=0$ for $5x-y+z=5$, $2x+8y-z=9$, $-x+y+4z=4$ (exact solution $(1,1,1)$).
  • 2 Perform two Gauss–Seidel iterations for the same system and compare.
  • 3 For $A=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ with $ad\ne0$, compute $T_J$, $T_{GS}$ and their spectral radii.
  • 4 Show that Jacobi diverges for $x+4y=5$, $3x+y=4$, and that it converges after the equations are interchanged.
  • 5 For $A=\begin{pmatrix}1&\alpha&0\\ \alpha&1&\alpha\\0&\alpha&1\end{pmatrix}$ find $\rho(T_J)$ and $\rho(T_{GS})$. For which $\alpha$ do the methods converge? For which $\alpha$ is $A$ strictly diagonally dominant?
  • 6 Find $\rho(T_J)$ and $\rho(T_{GS})$ for $\begin{pmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{pmatrix}$. About how many digits does each method gain per iteration?
  • 7 Prove that the Jacobi iteration converges if $A$ is strictly diagonally dominant by columns.
  • 8 An iteration has $\|T\|_\infty=\tfrac12$ and $\|x^{(1)}-x^{(0)}\|_\infty=1$. How many iterations guarantee an error at most $10^{-6}$?
1 $x\leftarrow(5+y-z)/5$, $y\leftarrow(9-2x+z)/8$, $z\leftarrow(4+x-y)/4$. $x^{(1)}=(1,\ 1.125,\ 1)$; $x^{(2)}=(1.025,\ 1,\ 0.96875)$. Errors (max norm) $0.125$, $0.031$.
2 $x^{(1)}$: $x=1$, $y=(9-2)/8=0.875$, $z=(4+1-0.875)/4=1.031\,25$. $x^{(2)}$: $x=0.968\,75$, $y=1.011\,72$, $z=0.989\,26$. Errors $0.125$, $0.031$, then $0.0045$ at the third step against Jacobi's $0.010$; $\rho(T_J)\approx0.365$, $\rho(T_{GS})\approx0.179$.
3 $T_J=\begin{pmatrix}0&-\tfrac ba\\-\tfrac cd&0\end{pmatrix}$, eigenvalues $\pm\sqrt{\tfrac{bc}{ad}}$; $T_{GS}=-\begin{pmatrix}a&0\\c&d\end{pmatrix}^{-1}\begin{pmatrix}0&b\\0&0\end{pmatrix}$ $=\begin{pmatrix}0&-\tfrac ba\\0&\tfrac{bc}{ad}\end{pmatrix}$, eigenvalues $0,\ \tfrac{bc}{ad}$. So $\rho(T_J)=\sqrt{|bc/(ad)|}$ and $\rho(T_{GS})=|bc/(ad)|=\rho(T_J)^2$.
4 As written, $bc/(ad)=4\cdot3/1=12$: $\rho(T_J)=\sqrt{12}\gt1$, divergence. Interchanged, $A=\begin{pmatrix}3&1\\1&4\end{pmatrix}$ is strictly diagonally dominant, $\rho(T_J)=1/\sqrt{12}\approx0.29$, convergence to $(1,1)$.
5 $T_J=-\alpha\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}$ has eigenvalues $0,\pm\sqrt2\,\alpha$, so $\rho(T_J)=\sqrt2|\alpha|$, and by Theorem 5.18(2) $\rho(T_{GS})=2\alpha^2$. Both converge iff $|\alpha|\lt\tfrac1{\sqrt2}$ — exactly when $A$ is positive definite (Exercise II.5). Strict dominance needs $2|\alpha|\lt1$; for $\tfrac12\le|\alpha|\lt\tfrac1{\sqrt2}$ the methods converge without it.
6 Dividing by $2$ gives Exercise 5 with $\alpha=-\tfrac12$ (the iteration matrices are the same): $\rho(T_J)=\tfrac{\sqrt2}2\approx0.707$, $\rho(T_{GS})=\tfrac12$. Digits per step: $-\log_{10}0.707\approx0.15$ and $\log_{10}2\approx0.30$.
7 $T_J=-D^{-1}(L+U)$ is similar to $DT_JD^{-1}=-(L+U)D^{-1}$, whose $j$-th column has entries $-a_{ij}/a_{jj}$ ($i\ne j$). Its maximum column sum $\max_j\sum_{i\ne j}|a_{ij}|/|a_{jj}|$ is $\lt1$, so $\rho(T_J)=\rho\big((L+U)D^{-1}\big)$ $\le\|(L+U)D^{-1}\|_1\lt1$.
8 $\|x^{(k)}-x\|$ $\le\dfrac{\|T\|^k}{1-\|T\|}\|x^{(1)}-x^{(0)}\|$ $=2^{1-k}$. Need $2^{1-k}\le10^{-6}$, i.e. $k\ge1+6\log_210=20.93$: $k=21$.
IV
SOR, conditioning and applications.
  • 1 Perform two SOR iterations with $\omega=1.25$ from $0$ for $4x-y=3$, $-x+4y=3$. Compute $\rho(T_{GS})$ and $\rho(T_{1.25})$. Was over-relaxation a good idea here?
  • 2 For $A=\begin{pmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{pmatrix}$ find $\omega_{\rm opt}$ and $\rho(T_{\omega_{\rm opt}})$, and compare with Gauss–Seidel.
  • 3 Show that SOR with $\omega=2.5$ cannot converge for every starting vector, whatever $A$ is.
  • 4 Compute $\kappa_\infty$ and $\kappa_1$ of $\begin{pmatrix}3&1\\2&1\end{pmatrix}$.
  • 5 Compute $\kappa_2$ of $\begin{pmatrix}2&1\\1&2\end{pmatrix}$ and of $\begin{pmatrix}1&0.99\\0.99&1\end{pmatrix}$.
  • 6 The Hilbert matrix $H_3=\big(\tfrac1{i+j-1}\big)$ has $H_3^{-1}=\begin{pmatrix}9&-36&30\\-36&192&-180\\30&-180&180\end{pmatrix}$. Find $\kappa_\infty(H_3)$. How many decimal digits may be lost in solving $H_3x=b$?
  • 7 Prove that $\kappa(AB)\le\kappa(A)\kappa(B)$ and $\kappa(A^{-1})=\kappa(A)$ for any induced norm.
  • 8 (Heat in a rod.) The steady temperatures $T_1,T_2,T_3$ (in °C) at three interior points of a heated rod with end temperatures $T_0=0$ °C and $T_4=100$ °C satisfy $-T_{i-1}+2T_i-T_{i+1}=10$, $i=1,2,3$. Find the exact solution, perform two Gauss–Seidel sweeps from $T=0$, and estimate the number of sweeps for an accuracy of $0.01$ °C.
1 Sweep 1: $\tilde x=3/4$, $x=1.25\cdot0.75=0.9375$; $\tilde y=(3+0.9375)/4=0.984\,38$, $y=1.25\cdot0.984\,38=1.230\,47$. Sweep 2: $x=-0.25\cdot0.9375$ $+1.25\cdot\tfrac{3+1.230\,47}4$ $=1.087\,65$; $y=-0.25\cdot1.230\,47$ $+1.25\cdot\tfrac{3+1.087\,65}{4}$ $=0.969\,77$. Here $\rho(T_J)=\tfrac14$, $\rho(T_{GS})=\tfrac1{16}$, $\omega_{\rm opt}=\tfrac{2}{1+\sqrt{15/16}}\approx1.016$, and for $\omega\gt\omega_{\rm opt}$, $\rho(T_\omega)=\omega-1=0.25$: worse than Gauss–Seidel. Over-relaxation pays only when $\rho_J$ is close to $1$.
2 $\rho_J=\tfrac{\sqrt2}2$, so $\omega_{\rm opt}=\dfrac{2}{1+\sqrt{1/2}}$ $=\dfrac{2}{1+0.7071}\approx1.1716$ and $\rho=\omega_{\rm opt}-1\approx0.1716$, against $\rho(T_{GS})=0.5$: $0.77$ digits per sweep instead of $0.30$.
3 By Theorem 5.19(1), $\rho(T_{2.5})\ge|2.5-1|=1.5\gt1$, so some starting error is not damped (Theorem 5.16).
4 $\det=1$, $A^{-1}=\begin{pmatrix}1&-1\\-2&3\end{pmatrix}$. $\|A\|_\infty=4$, $\|A^{-1}\|_\infty=5$: $\kappa_\infty=20$. $\|A\|_1=5$, $\|A^{-1}\|_1=4$: $\kappa_1=20$.
5 Symmetric, so $\kappa_2=\lambda_{\max}/\lambda_{\min}$: eigenvalues $3,1$ give $\kappa_2=3$; eigenvalues $1.99,\ 0.01$ give $\kappa_2=199$.
6 $\|H_3\|_\infty=1+\tfrac12+\tfrac13=\tfrac{11}6$, $\|H_3^{-1}\|_\infty=36+192+180=408$, so $\kappa_\infty(H_3)=748$: up to about $\log_{10}748\approx2.9$ digits can be lost. (For $H_4$, $\kappa_\infty=28\,375$; the Hilbert matrices are the classical ill-conditioned family.)
7 $\kappa(AB)=\|AB\|\,\|B^{-1}A^{-1}\|$ $\le\|A\|\,\|B\|\,\|B^{-1}\|\,\|A^{-1}\|$ $=\kappa(A)\kappa(B)$. And $\kappa(A^{-1})=\|A^{-1}\|\,\|A\|=\kappa(A)$.
8 The system $2T_1-T_2=10$, $-T_1+2T_2-T_3=10$, $-T_2+2T_3=110$ has the solution $(40,70,90)$ °C. Gauss–Seidel: sweep 1 gives $(5,\ 7.5,\ 58.75)$, sweep 2 gives $(8.75,\ 38.75,\ 74.375)$. Since $\rho(T_{GS})=\tfrac12$ (Exercise III.6), the initial error of about $90$ °C must be halved about $\log_2(90/0.01)\approx13$ times; in fact $14$ sweeps reach $0.01$ °C.
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

E1. CSIR Part B GATE MA For $A=\begin{pmatrix}4&1\\2&5\end{pmatrix}$, the spectral radius of the Gauss–Seidel iteration matrix is (A) $0.1$; (B) $\sqrt{0.1}$; (C) $0.5$; (D) $0$.

Idea For $2\times2$ matrices $T_{GS}$ has eigenvalues $0$ and $\tfrac{bc}{ad}$.
Compute $\tfrac{1\cdot2}{4\cdot5}=0.1$. (B) is $\rho(T_J)$.
Answer (A).

E2. CSIR Part B Let $A=\begin{pmatrix}2&1&1\\4&3&3\\8&7&9\end{pmatrix}=LU$ with $L$ unit lower triangular and $U$ upper triangular. Then $l_{32}+u_{33}$ equals (A) $3$; (B) $4$; (C) $5$; (D) $6$.

Elimination $l_{21}=2$, $l_{31}=4$; the rows become $(0,1,1)$ and $(0,3,5)$; $l_{32}=3$; $u_{33}=5-3=2$.
Check $\det A=2\cdot1\cdot2=4$; directly, $2(27-21)-1(36-24)$ $+1(28-24)=4$ ✓.
Answer (C) $3+2=5$.

E3. CSIR Part B The number of multiplications and divisions needed to solve a general $3\times3$ system by Gauss elimination (without pivoting) followed by back substitution is (A) $9$; (B) $11$; (C) $17$; (D) $27$.

Count Theorem 5.12: $\tfrac{27}3+9-1=17$. In detail: step 1: $2$ multipliers, $2\times2$ updates, $2$ for $b$ ($8$); step 2: $1+1+1=3$; back substitution $1+2+3=6$. Total $17$.
Answer (C). ((B) $11$ is the number of additions/subtractions.)

E4. CSIR Part C Let $A=\begin{pmatrix}1&-1&1\\-2&1&-2\\2&2&1\end{pmatrix}$. Which of the following are true? (One or more options may be correct.) (A) For every right-hand side and every starting vector, the Jacobi iteration reaches the exact solution after at most three iterations. (B) The Gauss–Seidel iteration converges for every starting vector. (C) $A$ is strictly diagonally dominant. (D) $\det A=1$.

(A) True Here $D=I$, so $T_J=I-A=\begin{pmatrix}0&1&-1\\2&0&2\\-2&-2&0\end{pmatrix}$. Then $T_J^2=\begin{pmatrix}4&2&2\\-4&-2&-2\\-4&-2&-2\end{pmatrix}$ and $T_J^3=T_J\,T_J^2=0$. Hence $e^{(3)}=T_J^3e^{(0)}=0$ for every start: $\rho(T_J)=0$.
(B) False $T_{GS}=\begin{pmatrix}0&1&-1\\0&2&0\\0&-6&2\end{pmatrix}$ has eigenvalues $0,2,2$, so $\rho(T_{GS})=2$.
(C) False Row 1: $1\lt1+1$.
(D) True $1(1+4)+1(-2+4)$ $+1(-4-2)=1$.
Answer (A) and (D).

E5. CSIR Part C Which of the following are true for real $n\times n$ matrices? (A) Every nonsingular matrix has an LU factorisation with $L$ unit lower triangular (no row interchanges). (B) Every symmetric matrix with positive diagonal entries has a Cholesky factorisation. (C) If $A$ is symmetric positive definite, Gauss elimination without pivoting never meets a zero pivot. (D) For every nonsingular $A$ there are a permutation matrix $P$ and triangular $L$, $U$ with $PA=LU$ and $|l_{ij}|\le1$.

(A) False $\begin{pmatrix}0&1\\1&0\end{pmatrix}$: $\Delta_1=0$ (Theorem 5.14).
(B) False $\begin{pmatrix}1&2\\2&1\end{pmatrix}$ is not positive definite (Example 4(b)).
(C) True All $\Delta_k\gt0$ (Sylvester), so all pivots $\Delta_k/\Delta_{k-1}\gt0$ (Theorem 5.11).
(D) True Partial pivoting (Theorem 5.13).
Answer (C) and (D).

E6. CSIR Part C Let $\kappa(A)=\|A\|_\infty\|A^{-1}\|_\infty$ for nonsingular $A$. Which of the following are true? (A) $\kappa(A)\ge1$ for every nonsingular $A$. (B) $\kappa(A+B)\le\kappa(A)+\kappa(B)$ whenever $A$, $B$, $A+B$ are nonsingular. (C) If $|\det A|\lt10^{-6}$ then $\kappa(A)\gt10^{3}$. (D) For $A=\begin{pmatrix}1&1\\1&1.01\end{pmatrix}$, $\kappa(A)=404.01$.

(A) True $1=\|I\|=\|AA^{-1}\|\le\|A\|\,\|A^{-1}\|$.
(B) False $A=I$, $B=\operatorname{diag}(-0.9,1)$: $\kappa(A)=1$, $\kappa(B)=\tfrac1{0.9}\approx1.11$, but $A+B=\operatorname{diag}(0.1,2)$ has $\kappa=2\cdot10=20$.
(C) False $A=0.001\,I_3$ has $\det A=10^{-9}$, yet $\kappa(A)=1$. The determinant scales, the condition number does not.
(D) True Example 7: $2.01\times201=404.01$.
Answer (A) and (D).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Elimination. Definition 5.8 and Theorem 5.11 (the pivots are ratios of leading minors — a five-line proof students remember); Example 1 on the board; the operation count (Theorem 5.12) with the $n=3$ numbers $17$ and $11$; Example 2 in three-digit arithmetic, done slowly; partial pivoting and $PA=LU$.
  2. Factorisations. Theorem 5.14 (existence, uniqueness, $L$ = multipliers), Example 3 with two right-hand sides, Cholesky (Theorem 5.15) with the Schur-complement proof, Example 4 and the failure case. Five minutes on tridiagonal systems (Exercise II.7) as a preview of splines in §5.3.
  3. Iterations and conditioning. Definition 5.11, Theorem 5.16 (with the Jordan-form proof), Theorem 5.17; project Interactive 1 (start with system 1, then 2 to show slow zigzags, then 3 and 4 to show that reordering matters); Theorem 5.18 and Example 6; Kahan's bound; Definition 5.14, Theorem 5.20, Example 7 and Interactive 2. Finish with Exam corner E1 and E4.

Discussion questions. (1) Gauss–Seidel uses newer information than Jacobi; why can it nevertheless be slower, or even diverge when Jacobi converges? (2) Is an ill-conditioned system a defect of the algorithm or of the problem? What would you tell an engineer whose computed solution has a tiny residual but is physically absurd? (3) Why is elimination preferred for a dense $500\times500$ system but iteration for a sparse system with $10^7$ unknowns?

Misconceptions to watch for. "A nonsingular matrix always has an LU factorisation"; "partial pivoting is only needed for zero pivots"; "$\|T\|\gt1$ means divergence"; "diagonal dominance is necessary for convergence"; "if Jacobi converges, Gauss–Seidel converges faster"; "a small determinant means ill-conditioned"; "a small residual means an accurate solution"; confusing the counts of multiplications ($17$) and additions ($11$) for $n=3$.

Suggested homework. I(1, 2, 5, 6), II(1, 3, 4, 5, 7), III(1, 2, 4, 5, 8), IV(2, 4, 6, 8); Exam corner E2, E5, E6.

🔬 Research–Teaching NexusResearch-tutored · optional, about 60 minutes

Research question. A thin square metal plate — think of the heat spreader on top of a computer processor — is held at $100$ °C along one edge and $0$ °C along the other three. Its steady temperature solves Laplace's equation, which on an $N\times N$ grid of interior points becomes the linear system "each temperature is the average of its four neighbours". How does the number of Jacobi, Gauss–Seidel and SOR iterations needed for a fixed accuracy grow as the grid is refined, and how much does the optimal relaxation parameter save?

Why it matters. Thermal design of electronics, groundwater and oil-reservoir simulation, electrostatics and image processing (Poisson image editing) all lead to exactly this kind of large, sparse, diagonally dominant system. Iteration counts that grow with the grid are why modern codes use multigrid and conjugate-gradient methods — and SOR was the workhorse that came before them.

What to do.

  1. Write the five-point equations $4u_{i,j}-u_{i-1,j}-u_{i+1,j}$ $-u_{i,j-1}-u_{i,j+1}=0$ with the boundary values moved to the right-hand side. Check that the matrix is weakly diagonally dominant and symmetric positive definite.
  2. Implement Jacobi, Gauss–Seidel and SOR (sweeping row by row) and count the sweeps needed to reduce the maximum change per sweep below $10^{-6}$, for $N=10,20,40$.
  3. Compare your counts with the predictions $k\approx\ln(10^6)/(-\ln\rho)$, using $\rho_J=\cos\frac{\pi}{N+1}$, $\rho_{GS}=\rho_J^2$ and, for SOR, $\rho=\omega_{\rm opt}-1$ with $\omega_{\rm opt}$ from Theorem 5.19(3).
  4. Try $\omega$ slightly above and below $\omega_{\rm opt}$ and plot iterations against $\omega$; explain the asymmetry of the curve.

Tools: Python with NumPy (loops are fine for $N\le40$) or a spreadsheet for $N=10$; Interactive 1 for intuition.

Hand in: A table of iteration counts against $N$ for the three methods, the plot of iterations against $\omega$, and a short paragraph explaining how the counts scale with $N$ (equivalently with the grid size $h=\frac1{N+1}$).

Going further. Read about the conjugate gradient method and about multigrid, whose iteration counts do not grow with $N$; investigate red–black ordering, which makes the five-point matrix consistently ordered so that Young's theory applies.

Instructor note: the asymptotic predictions for a $10^{-6}$ reduction are — $N=10$: $\rho_J\approx0.9595$, Jacobi $\approx334$, Gauss–Seidel $\approx167$, SOR ($\omega_{\rm opt}\approx1.560$) $\approx24$; $N=20$: $\approx1230$, $615$, $46$ ($\omega_{\rm opt}\approx1.741$); $N=40$: $\approx4702$, $2351$, $90$ ($\omega_{\rm opt}\approx1.858$). Jacobi and Gauss–Seidel counts grow like $N^2$ (since $1-\rho_J\approx\frac{\pi^2}{2(N+1)^2}$), SOR only like $N$. Measured counts with a "maximum change" stopping rule are somewhat different (the rule is not the error), which is itself a useful discussion point. The iterations-versus-$\omega$ curve is steep to the left of $\omega_{\rm opt}$ and has slope $1$ in $\rho$ to the right, so overestimating $\omega_{\rm opt}$ is the safer mistake.

🧪 Self-check quiz

0/5 correct

Q1. For large $n$, the number of multiplications needed to solve a dense $n\times n$ system by Gauss elimination is about

Q2. If $A$ is strictly diagonally dominant by rows, then

Q3. The iteration $x^{(k+1)}=Tx^{(k)}+c$ converges for every starting vector if and only if

Q4. The Cholesky factorisation $A=LL^{\mathsf T}$ (with positive diagonal in $L$) exists exactly when $A$ is

Q5. For a tridiagonal matrix the Jacobi iteration matrix has spectral radius $0.6$. The Gauss–Seidel iteration matrix has spectral radius