Chapter 9 · Numerical Analysis

9.1 Linear Systems and Nonlinear Equations

Gaussian elimination with partial pivoting, LU and Cholesky factorisations and their operation counts; the Jacobi and Gauss–Seidel iterations and why diagonal dominance makes them converge; and the root-finders GATE asks about — bisection, fixed-point iteration, Newton–Raphson and the secant method — with their orders of convergence.

Two problems sit underneath almost every scientific computation. The first is a linear system $Ax=b$: a finite-element model of a bridge, a least-squares fit, a discretised heat equation, a Markov chain's stationary distribution, each step of Newton's method for several unknowns — all of them end with "now solve these $n$ linear equations". The second is a nonlinear equation $f(x)=0$: the interest rate hidden in a loan repayment, the angle in Kepler's equation that places a satellite on its orbit, the depth at which a floating log balances, the eigenvalue of a vibrating beam. Neither problem is solved in practice by Cramer's rule or by a formula. Linear systems are solved by elimination (a finite recipe that would be exact in exact arithmetic) or by iteration (a sequence of cheap approximations that converges to the solution); nonlinear equations are solved by iteration only, and the central question becomes how fast the iterates converge.

GATE MA examines this section in a very predictable way. MCQs and NATs ask you to carry out one or two steps of a method by hand — an LU or Cholesky entry, a Jacobi or Gauss–Seidel iterate, a Newton or secant iterate, the number of bisection steps for a given accuracy — or to identify the order of an iteration. MSQs list statements about convergence ("Gauss–Seidel converges whenever Jacobi does", "Newton's method is always quadratic", "diagonal dominance is necessary") and expect you to know which are theorems and which have counterexamples. The tools are the eigenvalue and norm facts of Chapter 3 (especially §3.2 and §3.3), the mean value theorem and Taylor's theorem, and the contraction idea of §4.1.

Direct Methods: Gaussian Elimination, LU and Cholesky

Throughout, $A=[a_{ij}]$ is a real $n\times n$ matrix, $b\in\mathbb{R}^n$, and $\Delta_k$ denotes the $k$-th leading principal minor of $A$, the determinant of its top-left $k\times k$ block.

📘 Definition 9.1 — Gaussian elimination; pivots, multipliers, partial pivoting

Gaussian elimination reduces $[A\mid b]$ to an upper triangular system $[U\mid c]$ in $n-1$ stages. At stage $k$ the current entry $a^{(k)}_{kk}$ is the $k$-th pivot; for each row $i\gt k$ the multiplier $m_{ik}=a^{(k)}_{ik}/a^{(k)}_{kk}$ is formed and $m_{ik}$ times row $k$ is subtracted from row $i$, which creates zeros below the pivot. The triangular system $Ux=c$ is then 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),\ \ i=n-1,\dots,1.$$

Partial pivoting: at stage $k$, before eliminating, interchange row $k$ with a row $p\ge k$ for which $|a^{(k)}_{pk}|$ is largest. Then every multiplier satisfies $|m_{ik}|\le1$.

📐 Theorem 9.1 — When elimination without row exchanges works; pivots and the determinant
Let $A$ be an $n\times n$ matrix. Gaussian elimination can be carried out without row interchanges (all pivots $a^{(k)}_{kk}\ne0$ for $k=1,\dots,n$) if and only if $\Delta_1,\dots,\Delta_n$ are all nonzero. In that case the pivots are $$a^{(1)}_{11}=\Delta_1,\qquad a^{(k)}_{kk}=\frac{\Delta_k}{\Delta_{k-1}}\ \ (k\ge2),$$ and $\det A=a^{(1)}_{11}a^{(2)}_{22}\cdots a^{(n)}_{nn}$. With row interchanges (as in partial pivoting), $\det A=(-1)^s\times(\text{product of the pivots})$, where $s$ is the number of interchanges; and every nonsingular $A$ can be eliminated with partial pivoting.

Proof. Subtracting a multiple of one row from a later row does not change any leading principal minor: the top-left $k\times k$ block of the new matrix is obtained from the old block by the same row operation restricted to its first $k$ rows (or is unchanged, if the row being changed is below row $k$). After $k-1$ stages without interchanges, the top-left $k\times k$ block is upper triangular with diagonal $a^{(1)}_{11},\dots,a^{(k)}_{kk}$, so $\Delta_k=a^{(1)}_{11}\cdots a^{(k)}_{kk}$. By induction on $k$: if $\Delta_1,\dots,\Delta_{k-1}\ne0$, the first $k-1$ pivots are nonzero, stage $k$ can be reached, and $a^{(k)}_{kk}=\Delta_k/\Delta_{k-1}$ is nonzero exactly when $\Delta_k\ne0$. This proves the equivalence and the pivot formula; $k=n$ gives $\det A=\Delta_n=$ the product of the pivots. A row interchange multiplies the determinant by $-1$, which gives the general formula. Finally, if $A$ is nonsingular, at stage $k$ the current matrix is nonsingular and its first $k-1$ columns are already reduced, so some entry $a^{(k)}_{pk}$ with $p\ge k$ is nonzero (otherwise the first $k$ columns would be dependent); partial pivoting picks the largest of them, which is nonzero. ∎

📐 Theorem 9.2 — Operation counts

To solve $Ax=b$ ($n\times n$) by Gaussian elimination followed by back substitution, the numbers of multiplications/divisions and of additions/subtractions are

$$\frac{n^3}{3}+n^2-\frac n3\qquad\text{and}\qquad\frac{n^3}{3}+\frac{n^2}{2}-\frac{5n}{6},$$

so the cost is about $\tfrac23n^3$ arithmetic operations, dominated by the elimination; back substitution alone takes $\tfrac{n(n+1)}{2}$ multiplications/divisions, i.e. $O(n^2)$. Once $A=LU$ is known, each further right-hand side costs only $O(n^2)$ (two triangular solves, about $n^2$ multiplications in all). Cramer's rule with determinants expanded by cofactors costs more than $n!$ operations.

Proof. At stage $k$ there are $n-k$ rows to change. For each of them we compute one multiplier (one division), update $n-k$ entries of $A$ and one entry of $b$ (one multiplication and one subtraction each). Stage $k$ therefore costs $(n-k)(n-k+2)$ multiplications/divisions and $(n-k)(n-k+1)$ subtractions. Summing over $k=1,\dots,n-1$ with $j=n-k$: $\sum_{j=1}^{n-1}j(j+2)=\tfrac{(n-1)n(2n-1)}{6}+(n-1)n$ and $\sum_{j=1}^{n-1}j(j+1)=\tfrac{(n-1)n(2n-1)}{6}+\tfrac{(n-1)n}{2}$. Back substitution computes $x_i$ with $n-i$ multiplications, $n-i$ subtractions and one division: $\tfrac{n(n+1)}{2}$ multiplications/divisions and $\tfrac{n(n-1)}{2}$ subtractions. Adding and simplifying gives the two polynomials (check: for $n=3$ they give $17$ and $11$). ∎

✏️ Example 1 — A zero pivot, and elimination with partial pivoting
Solve $\ y+z=1,\ \ 4x+3y-3z=-5,\ \ 4x+3z=10\ $ by Gaussian elimination with partial pivoting, and find $\det A$ from the pivots.
Why pivot $a_{11}=0$, so elimination without interchanges cannot even start ($\Delta_1=0$, Theorem 9.1). The largest $|a_{i1}|$ is $4$ (rows 2 and 3); take row 2 and interchange rows 1 and 2.
Stage 1 $\left[\begin{array}{ccc|c}4&3&-3&-5\\0&1&1&1\\4&0&3&10\end{array}\right]$, multipliers $m_{21}=0$, $m_{31}=1$: $R_3\leftarrow R_3-R_1$ gives the third row $(0,\,-3,\,6\mid15)$.
Stage 2 In column 2 the candidates are $1$ and $-3$; $|-3|$ is larger, so interchange rows 2 and 3. Then $m_{32}=\tfrac{1}{-3}=-\tfrac13$ and $R_3\leftarrow R_3+\tfrac13R_2$: $$\left[\begin{array}{ccc|c}4&3&-3&-5\\0&-3&6&15\\0&0&3&6\end{array}\right].$$
Back substitution $z=2$; $-3y+12=15$ gives $y=-1$; $4x-3-6=-5$ gives $x=1$.
Determinant Two interchanges, pivots $4,-3,3$: $\det A=(-1)^2\cdot4\cdot(-3)\cdot3=-36$. Check by cofactors along the first row of the original matrix: $0-1\cdot(12-(-12))$ $+\,1\cdot(0-12)=-24-12=-36$. ✓

Elimination without interchanges records itself as a factorisation. If no interchanges are needed, the multipliers fill a unit lower triangular matrix $L=[m_{ik}]$ (ones on the diagonal), the final upper triangular matrix is $U$, and $A=LU$. Solving $Ax=b$ then splits into two triangular solves.

📘 Definition 9.2 — LU factorisations: Doolittle, Crout, Cholesky

An LU factorisation of $A$ is $A=LU$ with $L$ lower triangular and $U$ upper triangular. It is the Doolittle factorisation if $l_{ii}=1$ for all $i$, and the Crout factorisation if $u_{ii}=1$ for all $i$. For a real symmetric $A$, a Cholesky factorisation is $A=LL^{\mathsf T}$ with $L$ lower triangular and $l_{ii}\gt0$. Given $A=LU$, solve $Ly=b$ by forward substitution, then $Ux=y$ by back substitution.

Comparing entries of $A=LU$ (Doolittle), for $k=1,\dots,n$: $\ u_{kj}=a_{kj}-\sum_{s\lt k}l_{ks}u_{sj}$ for $j\ge k$, and $l_{ik}=\big(a_{ik}-\sum_{s\lt k}l_{is}u_{sk}\big)/u_{kk}$ for $i\gt k$. Comparing entries of $A=LL^{\mathsf T}$ (Cholesky): $\ l_{kk}=\big(a_{kk}-\sum_{s\lt k}l_{ks}^2\big)^{1/2}$ and $l_{ik}=\big(a_{ik}-\sum_{s\lt k}l_{is}l_{ks}\big)/l_{kk}$ for $i\gt k$.

📐 Theorem 9.3 — Existence and uniqueness of LU; $PA=LU$
(a) A nonsingular matrix $A$ has a Doolittle factorisation if and only if $\Delta_1,\dots,\Delta_{n-1}$ are all nonzero; it is then unique, $L$ holds the multipliers of Gaussian elimination, $U$ is the eliminated matrix, and $\det A=u_{11}u_{22}\cdots u_{nn}$. The Crout factorisation exists under the same condition and equals $A=(LD)(D^{-1}U)$ with $D=\operatorname{diag}(u_{11},\dots,u_{nn})$.
(b) For every nonsingular $A$ there is a permutation matrix $P$ (the row interchanges of partial pivoting) with $PA=LU$ of Doolittle type.

Proof. (a) Existence. By Theorem 9.1 elimination runs without interchanges when $\Delta_1,\dots,\Delta_{n-1}\ne0$ (the last pivot is $\Delta_n/\Delta_{n-1}\ne0$ because $A$ is nonsingular). Stage $k$ multiplies the current matrix on the left by $E_k=I-m_ke_k^{\mathsf T}$, where $m_k=(0,\dots,0,m_{k+1,k},\dots,m_{nk})^{\mathsf T}$. Hence $E_{n-1}\cdots E_1A=U$ and $A=E_1^{-1}\cdots E_{n-1}^{-1}U$. Since $E_k^{-1}=I+m_ke_k^{\mathsf T}$ and $e_k^{\mathsf T}m_j=0$ for $j\gt k$, the product $E_1^{-1}\cdots E_{n-1}^{-1}$ equals $I+\sum_km_ke_k^{\mathsf T}$, the unit lower triangular matrix of multipliers. Necessity. If $A=LU$ with $l_{ii}=1$, the top-left $k\times k$ blocks satisfy $A_k=L_kU_k$, so $\Delta_k=u_{11}\cdots u_{kk}$; since $\det A=\Delta_n\ne0$, every $u_{ii}\ne0$ and every $\Delta_k\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 $I$. The Crout form follows by moving the diagonal of $U$ into $L$. (b) Partial pivoting succeeds for nonsingular $A$ (Theorem 9.1); performing all its interchanges first gives a matrix $PA$ that is eliminated without interchanges, and (a) applies to it. ∎

📐 Theorem 9.4 — Cholesky factorisation
A real symmetric matrix $A$ has a Cholesky factorisation $A=LL^{\mathsf T}$ ($L$ lower triangular with positive diagonal) if and only if $A$ is positive definite; the factorisation is then unique. In the Cholesky recursion of Definition 9.2, $A$ is positive definite exactly when every quantity $a_{kk}-\sum_{s\lt k}l_{ks}^2$ under a square root is positive — so running the recursion is itself a test for positive definiteness.

Proof. ($\Leftarrow$) If $A$ is positive definite, every leading block $A_k$ is positive definite (restrict $x^{\mathsf T}Ax$ to vectors supported on the first $k$ coordinates), so $\Delta_k=\det A_k\gt0$. By Theorem 9.3, $A=LU$ with $L$ unit lower triangular and $u_{kk}=\Delta_k/\Delta_{k-1}\gt0$. Write $U=DV$ with $D=\operatorname{diag}(u_{kk})$ and $V$ unit upper triangular. Then $A=LDV$, and $A=A^{\mathsf T}=V^{\mathsf T}DL^{\mathsf T}$ is another factorisation of the same type, so uniqueness in Theorem 9.3 gives $V=L^{\mathsf T}$. Thus $A=LDL^{\mathsf T}=(LD^{1/2})(LD^{1/2})^{\mathsf T}$, a Cholesky factorisation. ($\Rightarrow$) If $A=LL^{\mathsf T}$ with $l_{ii}\gt0$, then $L$ is invertible and $x^{\mathsf T}Ax=\|L^{\mathsf T}x\|^2\gt0$ for $x\ne0$. Uniqueness: the recursion of Definition 9.2 determines each entry of $L$ from earlier ones once the sign of $l_{kk}$ is fixed positive. The square-root test follows because the recursion computes $l_{kk}^2=u_{kk}=\Delta_k/\Delta_{k-1}$, and $A$ is positive definite iff all $\Delta_k\gt0$ (Sylvester's criterion, §3.3). ∎

✏️ Example 2 — Doolittle and Crout factorisations, and a solve
Find the Doolittle and Crout factorisations of $A=\begin{pmatrix}2&-1&1\\4&1&3\\-2&7&4\end{pmatrix}$ and use the first to solve $Ax=(-1,3,8)^{\mathsf T}$.
Row 1 of $U$, column 1 of $L$ $u_{11}=2$, $u_{12}=-1$, $u_{13}=1$; $l_{21}=4/2=2$, $l_{31}=-2/2=-1$.
Row 2, column 2 $u_{22}=1-2(-1)=3$, $u_{23}=3-2\cdot1=1$; $l_{32}=\big(7-(-1)(-1)\big)/3=2$.
Last pivot $u_{33}=4-(-1)(1)-2\cdot1=3$. So $$L=\begin{pmatrix}1&0&0\\2&1&0\\-1&2&1\end{pmatrix},\quad U=\begin{pmatrix}2&-1&1\\0&3&1\\0&0&3\end{pmatrix},$$ and $\det A=2\cdot3\cdot3=18$.
Crout Move $D=\operatorname{diag}(2,3,3)$ into $L$: $L_C=LD=\begin{pmatrix}2&0&0\\4&3&0\\-2&6&3\end{pmatrix}$, $U_C=D^{-1}U=\begin{pmatrix}1&-\frac12&\frac12\\0&1&\frac13\\0&0&1\end{pmatrix}$.
Forward $Ly=b$: $y_1=-1$, $y_2=3-2(-1)=5$, $y_3=8-(-1)(-1)-2\cdot5=-3$.
Back $Ux=y$: $3x_3=-3$ gives $x_3=-1$; $3x_2+x_3=5$ gives $x_2=2$; $2x_1-x_2+x_3=-1$ gives $x_1=1$. Solution $(1,2,-1)$; substituting into the three original equations gives $-1,3,8$. ✓
✏️ Example 3 — Cholesky: success, and failure as a test
(a) Find the Cholesky factor of $A=\begin{pmatrix}4&2&-2\\2&10&2\\-2&2&6\end{pmatrix}$. (b) Run the recursion on $B=\begin{pmatrix}1&2&0\\2&3&1\\0&1&2\end{pmatrix}$ and conclude.
(a) Column 1 $l_{11}=\sqrt4=2$, $l_{21}=2/2=1$, $l_{31}=-2/2=-1$.
(a) Column 2 $l_{22}=\sqrt{10-1^2}=3$, $l_{32}=\big(2-(-1)(1)\big)/3=1$.
(a) Column 3 $l_{33}=\sqrt{6-(-1)^2-1^2}=2$. Hence $L=\begin{pmatrix}2&0&0\\1&3&0\\-1&1&2\end{pmatrix}$; multiplying out, the third row of $LL^{\mathsf T}$ is $(-2,\,2,\,6)$. ✓ Since the recursion succeeded, $A$ is positive definite, and $\det A=(2\cdot3\cdot2)^2=144$.
(b) $l_{11}=1$, $l_{21}=2$, then $l_{22}^2=3-2^2=-1\lt0$: the recursion breaks down. By Theorem 9.4, $B$ is not positive definite (indeed $\Delta_2=3-4=-1$, and $x=(2,-1,0)$ gives $x^{\mathsf T}Bx=4-8+3=-1$). $B$ still has a Doolittle factorisation, since $\Delta_1=1$ and $\Delta_2=-1$ are nonzero.

Iterative Methods: Jacobi and Gauss–Seidel

For large sparse systems — a million unknowns with five nonzeros per row, as in a discretised Laplace equation — elimination fills in the zeros and costs far too much. Iterative methods only multiply by $A$, keep its sparsity, and can be stopped as soon as the answer is good enough. Split $A=L+D+U$, where $D$ is the diagonal of $A$ and $L$, $U$ are its strictly lower and upper triangular parts (these $L,U$ are not the LU factors).

📘 Definition 9.3 — Jacobi and Gauss–Seidel iterations; iteration matrices

Assume $a_{ii}\ne0$ for all $i$. Starting from any $x^{(0)}$:

  • Jacobi (every component 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)}+c_J$ with $T_J=-D^{-1}(L+U)$, $c_J=D^{-1}b$.
  • Gauss–Seidel (each new component is used as soon as it is computed): $$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)}+c_{GS}$ with $T_{GS}=-(D+L)^{-1}U$, $c_{GS}=(D+L)^{-1}b$.

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

📘 Definition 9.4 — Diagonal dominance; spectral radius
$A$ is strictly diagonally dominant (by rows) if $|a_{ii}|\gt\sum_{j\ne i}|a_{ij}|$ for every $i$; strictly diagonally dominant by columns if $A^{\mathsf T}$ is. The spectral radius of a square matrix $T$ is $\rho(T)=\max\{|\lambda|:\lambda\text{ an eigenvalue of }T\}$, complex eigenvalues included. For every induced matrix norm $\rho(T)\le\|T\|$ (if $Tv=\lambda v$, $v\ne0$, then $|\lambda|\|v\|=\|Tv\|\le\|T\|\|v\|$); we use $\|T\|_\infty=\max_i\sum_j|t_{ij}|$ (largest absolute row sum) and $\|T\|_1$ (largest absolute column sum).
📐 Theorem 9.5 — Convergence of a stationary iteration

Let $x^*=Tx^*+c$. The iteration $x^{(k+1)}=Tx^{(k)}+c$ converges to $x^*$ for every starting vector if and only if $\rho(T)\lt1$. If $\|T\|\lt1$ for some induced norm, then

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

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

Proof. Since $e^{(k)}=T^ke^{(0)}$ with $e^{(0)}$ arbitrary, convergence for every start means $T^k\to0$. ($\Rightarrow$) If $Tv=\lambda v$ with $v\ne0$ and $|\lambda|\ge1$, then $T^kv=\lambda^kv\not\to0$. (If $\lambda$ and $v$ are complex, $T^k$ applied to $\operatorname{Re}v$ or to $\operatorname{Im}v$ fails to tend to $0$, since $T^kv=T^k\operatorname{Re}v+iT^k\operatorname{Im}v$.) ($\Leftarrow$) Write $T=SJS^{-1}$ in Jordan form (§3.2). A Jordan block $J_m(\lambda)=\lambda I+N$ with $N^m=0$ has $J_m(\lambda)^k=\sum_{j=0}^{m-1}\binom kj\lambda^{k-j}N^j$, and each $\binom kj|\lambda|^{k-j}\to0$ as $k\to\infty$ when $|\lambda|\lt1$ (a polynomial in $k$ times a decaying exponential). So $J^k\to0$ and $T^k=SJ^kS^{-1}\to0$. For the bounds: $\|e^{(k)}\|\le\|T\|^k\|e^{(0)}\|$ by submultiplicativity; and $x^{(0)}-x^*=(x^{(0)}-x^{(1)})+(x^{(1)}-x^*)$ gives $\|e^{(0)}\|\le\|x^{(1)}-x^{(0)}\|+\|T\|\|e^{(0)}\|$, i.e. $\|e^{(0)}\|\le\|x^{(1)}-x^{(0)}\|/(1-\|T\|)$. ∎

📐 Theorem 9.6 — Strict diagonal dominance implies convergence
If $A$ is strictly diagonally dominant by rows, then $A$ is nonsingular, and both the Jacobi and the Gauss–Seidel iterations converge to the solution of $Ax=b$ for every $b$ and every $x^{(0)}$. Moreover $\rho(T_{GS})\le\|T_J\|_\infty=\max_i\dfrac{\sum_{j\ne i}|a_{ij}|}{|a_{ii}|}\lt1$. (The same conclusions hold for strict diagonal dominance by columns.)

Proof. Jacobi. $T_J$ has entries $-a_{ij}/a_{ii}$ off the diagonal and $0$ on it, so $\|T_J\|_\infty=\max_i\sum_{j\ne i}|a_{ij}|/|a_{ii}|=:q\lt1$. By Theorem 9.5, $\rho(T_J)\le q\lt1$ and Jacobi converges. Gauss–Seidel. Let $\mu$ be an eigenvalue of $T_{GS}$ with eigenvector $v$, scaled so that $\max_j|v_j|=1$, and choose $i$ with $|v_i|=1$. From $-Uv=\mu(D+L)v$, row $i$ reads $\mu a_{ii}v_i=-\sum_{j\gt i}a_{ij}v_j-\mu\sum_{j\lt i}a_{ij}v_j$, so $$|\mu|\Big(|a_{ii}|-\sum_{j\lt i}|a_{ij}|\Big)\le\sum_{j\gt i}|a_{ij}|.$$ Write $r=\sum_{j\lt i}|a_{ij}|$ and $s=\sum_{j\gt i}|a_{ij}|$; dominance says $|a_{ii}|\gt r+s$, so $|a_{ii}|-r\gt s\ge0$ and $|\mu|\le s/(|a_{ii}|-r)$. Since $s/(|a_{ii}|-r)\le(r+s)/|a_{ii}|$ (cross-multiply: $s|a_{ii}|\le(r+s)(|a_{ii}|-r)$ iff $r(r+s)\le r|a_{ii}|$, true), we get $|\mu|\le q\lt1$. Nonsingularity. If $Ax=0$, then $Dx=-(L+U)x$, i.e. $x=T_Jx$, so $x=T_J^kx\to0$ and $x=0$. Column dominance. A strictly dominant matrix (by rows or by columns) is nonsingular, by the previous sentence applied to $A$ or $A^{\mathsf T}$. If $|\lambda|\ge1$, then $\lambda D+L+U=\lambda\big(D+\lambda^{-1}(L+U)\big)$ and $\mu(D+L)+U=\mu\big(D+L+\mu^{-1}U\big)$ (with $\mu=\lambda$) are multiples of matrices that are still strictly dominant, because shrinking off-diagonal entries preserves dominance; so neither determinant vanishes, and no eigenvalue of $T_J$ or $T_{GS}$ has modulus $\ge1$. ∎

📐 Theorem 9.7 — Symmetric positive definite and tridiagonal matrices
  1. (Ostrowski–Reich) If $A$ is real symmetric with positive diagonal entries, Gauss–Seidel converges for every $x^{(0)}$ if and only if $A$ is positive definite.
  2. If $A$ is symmetric positive definite, Jacobi converges for every $x^{(0)}$ if and only if $2D-A$ is also positive definite. (So positive definiteness alone does not make Jacobi converge.)
  3. If $A$ is tridiagonal with nonzero diagonal entries, the nonzero eigenvalues of $T_{GS}$ are exactly the squares of the eigenvalues of $T_J$; hence $\rho(T_{GS})=\rho(T_J)^2$. Jacobi and Gauss–Seidel then converge or diverge together, and when they converge Gauss–Seidel needs about half as many iterations.

Proof of (3). For $\alpha\ne0$ let $S=\operatorname{diag}(1,\alpha,\alpha^2,\dots,\alpha^{n-1})$. Conjugating multiplies the entry in position $(i,j)$ by $\alpha^{i-j}$; for a tridiagonal matrix the only off-diagonal entries are at $i-j=\pm1$, so $S(\beta D+L+U)S^{-1}=\beta D+\alpha L+\alpha^{-1}U$ for every $\beta$. Hence $\det(\beta D+\alpha L+\alpha^{-1}U)=\det(\beta D+L+U)$ for all $\alpha\ne0$. Now $\mu\ne0$ is an eigenvalue of $T_{GS}=-(D+L)^{-1}U$ iff $\det\big(\mu(D+L)+U\big)=0$. Write $\mu=\lambda^2$. Then $\mu D+\mu L+U=\lambda\left(\lambda D+\lambda L+\lambda^{-1}U\right)$, so $$\det\big(\mu(D+L)+U\big)=\lambda^n\det(\lambda D+L+U),$$ and $\det(\lambda D+L+U)=\det D\cdot\det\big(\lambda I-T_J\big)$. So $\mu=\lambda^2\ne0$ is an eigenvalue of $T_{GS}$ iff $\lambda$ is an eigenvalue of $T_J$. ∎ Parts (1) and (2) are proved with the energy norm $\|x\|_A=\sqrt{x^{\mathsf T}Ax}$ — see the Go deeper box.

✏️ Example 4 — Jacobi and Gauss–Seidel side by side
For the system $5x-y+z=2$, $\ x+4y-z=10$, $\ 2x-y+6z=-6$ (exact solution $(1,2,-1)$), explain why both methods converge, and compute two iterations of each from $x^{(0)}=0$.
Convergence Row sums: $5\gt1+1$, $4\gt1+1$, $6\gt2+1$. Strictly diagonally dominant, so both converge (Theorem 9.6), with $\|T_J\|_\infty=\max\left(\tfrac25,\tfrac24,\tfrac36\right)=\tfrac12$.
Formulas $x=\tfrac15(2+y-z)$, $\ y=\tfrac14(10-x+z)$, $\ z=\tfrac16(-6-2x+y)$.
Jacobi $x^{(1)}=\left(\tfrac25,\ \tfrac{10}{4},\ -1\right)=(0.4,\ 2.5,\ -1)$. Then $x^{(2)}=\left(\tfrac{2+2.5+1}{5},\ \tfrac{10-0.4-1}{4},\ \tfrac{-6-0.8+2.5}{6}\right)$ $=(1.1,\ 2.15,\ -0.7167)$.
Gauss–Seidel Sweep 1: $x=0.4$; $y=\tfrac{10-0.4+0}{4}=2.4$; $z=\tfrac{-6-0.8+2.4}{6}=-0.7333$. Sweep 2: $x=\tfrac{2+2.4+0.7333}{5}=1.0267$; $y=\tfrac{10-1.0267-0.7333}{4}=2.06$; $z=\tfrac{-6-2.0533+2.06}{6}=-0.9989$.
Compare Errors in the max norm after two steps: Jacobi $0.283$, Gauss–Seidel $0.060$. The spectral radii are $\rho(T_J)\approx0.294$ and $\rho(T_{GS})\approx0.129$, so here Gauss–Seidel gains about $0.89$ digits per sweep against $0.53$ for Jacobi.
✏️ Example 5 — Prove or disprove: the two methods are not comparable in general
Decide each statement. (a) If Jacobi converges for every start, so does Gauss–Seidel. (b) If Gauss–Seidel converges for every start, so does Jacobi. (c) Diagonal dominance is necessary for convergence.
(a) False $A=\begin{pmatrix}1&2&-2\\1&1&1\\2&2&1\end{pmatrix}$. Here $T_J=-\begin{pmatrix}0&2&-2\\1&0&1\\2&2&0\end{pmatrix}$ has characteristic polynomial $\lambda^3$ (trace $0$, sum of principal $2\times2$ minors $-2+4-2=0$, determinant $0$), so $\rho(T_J)=0$: $T_J^3=0$ and Jacobi reaches the exact solution in at most $3$ steps. But $T_{GS}=\begin{pmatrix}0&-2&2\\0&2&-3\\0&0&2\end{pmatrix}$ is triangular with eigenvalues $0,2,2$: $\rho(T_{GS})=2$, and Gauss–Seidel diverges.
(b) False $A=\begin{pmatrix}1&0.6&0.6\\0.6&1&0.6\\0.6&0.6&1\end{pmatrix}$ is symmetric with eigenvalues $2.2,\ 0.4,\ 0.4$, hence positive definite: Gauss–Seidel converges (Theorem 9.7(1); numerically $\rho(T_{GS})\approx0.465$). But $T_J=-(A-I)$ has eigenvalues $-1.2,\ 0.6,\ 0.6$, so $\rho(T_J)=1.2\gt1$ and Jacobi diverges. (Consistently with Theorem 9.7(2), $2D-A$ has the eigenvalue $1-1.2=-0.2$.)
(c) False The matrix in (b) is not diagonally dominant ($1\lt0.6+0.6$), yet Gauss–Seidel converges; and $\begin{pmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{pmatrix}$ is only weakly dominant in its middle row ($2=1+1$), yet $\rho(T_J)=\tfrac{\sqrt2}{2}$ and $\rho(T_{GS})=\tfrac12$. Dominance is sufficient, not necessary; the spectral radius is the real criterion (Theorem 9.5).
🧭 Linear systems in GATE time
  1. LU / Cholesky entries: do not run full elimination — compute the needed entry from the Doolittle or Cholesky recursion. The $k$-th pivot is $\Delta_k/\Delta_{k-1}$; $\det A=\prod u_{kk}=\big(\prod l_{kk}\big)^2$ (Cholesky).
  2. Iterates: write each equation solved for its diagonal unknown first; in Gauss–Seidel overwrite as you go. Keep fractions for one or two steps.
  3. Convergence: check dominance by rows and by columns (either suffices); if it fails, compute $\rho(T)$. For a $2\times2$ matrix $\begin{pmatrix}a&b\\c&d\end{pmatrix}$: $\rho(T_J)=\sqrt{|bc/(ad)|}$ and $\rho(T_{GS})=|bc/(ad)|$. For tridiagonal matrices use $\rho(T_{GS})=\rho(T_J)^2$; for symmetric matrices with positive diagonal, Gauss–Seidel converges iff the matrix is positive definite.
  4. Reordering the equations can create dominance (and with it convergence) — but it changes $T_J$ and $T_{GS}$.

Nonlinear Equations: Bisection and Fixed-Point Iteration

Now $f$ is a real function and $\alpha$ a root, $f(\alpha)=0$. Every method below produces a sequence $x_0,x_1,x_2,\dots$; we write $e_n=x_n-\alpha$ for the error and measure speed as follows.

📘 Definition 9.5 — Order of convergence
Let $x_n\to\alpha$ with $x_n\ne\alpha$. The convergence has order $p\ge1$ and asymptotic error constant $C$ if $$\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_n|^p}=C,\qquad0\lt C\lt\infty,$$ with the extra requirement $C\lt1$ when $p=1$. Order $1$ is linear convergence (with rate $C$), order $2$ quadratic, order $3$ cubic; superlinear means $|e_{n+1}|/|e_n|\to0$. Roughly, linear convergence adds a fixed number $-\log_{10}C$ of correct digits per step, while order $p$ multiplies the number of correct digits by $p$.
📘 Definition 9.6 — The bisection method
Let $f$ be continuous on $[a,b]$ with $f(a)f(b)\lt0$. Put $[a_0,b_0]=[a,b]$ and, for $n=0,1,2,\dots$, let $c_n=\tfrac12(a_n+b_n)$; if $f(c_n)=0$ stop, otherwise let $[a_{n+1},b_{n+1}]$ be whichever of $[a_n,c_n]$, $[c_n,b_n]$ has endpoint values of opposite signs.
📐 Theorem 9.8 — Convergence of bisection
Under the hypotheses of Definition 9.6, each bracket $[a_n,b_n]$ contains a root $\alpha$ of $f$, has length $(b-a)/2^n$, and $$|c_n-\alpha|\le\frac{b-a}{2^{n+1}}.$$ Hence $|c_n-\alpha|\le\varepsilon$ is guaranteed as soon as $n\ge\log_2\frac{b-a}{\varepsilon}-1$, and the bracket length is $\le\varepsilon$ as soon as $n\ge\log_2\frac{b-a}{\varepsilon}$. The error bound halves at every step: bisection behaves like a linear method with rate $\tfrac12$ (about $0.3$ digits per step), whatever $f$ is.

Proof. By construction $f(a_n)f(b_n)\lt0$, so by the intermediate value theorem $[a_n,b_n]$ contains a root; the nested brackets have lengths $(b-a)/2^n\to0$, so they shrink to a single root $\alpha$ lying in all of them. The midpoint of an interval of length $\ell$ containing $\alpha$ is within $\ell/2$ of $\alpha$, which gives the bound; solving $(b-a)/2^{n+1}\le\varepsilon$ for $n$ gives the step count. ∎

(The sequence $|e_n|$ itself need not decrease monotonically, so bisection does not have an order in the strict sense of Definition 9.5; it is its error bound that converges linearly. GATE questions on bisection ask for iterates or for step counts — read carefully whether they bound the bracket length or the distance from the midpoint.)

📘 Definition 9.7 — Fixed-point iteration
Rewrite $f(x)=0$ in the equivalent form $x=g(x)$; a solution is a fixed point of $g$. Fixed-point iteration is $x_{n+1}=g(x_n)$ from a starting value $x_0$. The same equation has many such forms — for $x^3+x-1=0$, for instance, $g(x)=1-x^3$, $g(x)=(1-x)^{1/3}$ and $g(x)=1/(1+x^2)$ — and they behave very differently.
📐 Theorem 9.9 — Fixed-point theorem on an interval

(a) If $g$ is continuous on $[a,b]$ and $g([a,b])\subseteq[a,b]$, then $g$ has a fixed point in $[a,b]$.

(b) If moreover $g$ is differentiable on $(a,b)$ with $|g'(x)|\le k\lt1$ there, the fixed point $\alpha$ is unique, and for every $x_0\in[a,b]$ the iterates stay in $[a,b]$, converge to $\alpha$, and satisfy $$|x_n-\alpha|\le k^n|x_0-\alpha|,\qquad|x_n-\alpha|\le\frac{k^n}{1-k}|x_1-x_0|,\qquad|x_n-\alpha|\le\frac{k}{1-k}|x_n-x_{n-1}|.$$

Proof. (a) $h(x)=g(x)-x$ is continuous with $h(a)=g(a)-a\ge0$ and $h(b)=g(b)-b\le0$; by the intermediate value theorem $h$ vanishes somewhere in $[a,b]$. (b) By the mean value theorem $|g(x)-g(y)|\le k|x-y|$ for $x,y\in[a,b]$. If $\alpha,\beta$ were two fixed points, $|\alpha-\beta|=|g(\alpha)-g(\beta)|\le k|\alpha-\beta|$ forces $\alpha=\beta$. The iterates stay in $[a,b]$ because $g$ maps it into itself, and $|x_{n}-\alpha|=|g(x_{n-1})-g(\alpha)|\le k|x_{n-1}-\alpha|$, which by induction gives the first bound and convergence. For the second, $|x_0-\alpha|\le|x_0-x_1|+|x_1-\alpha|$ $\le|x_1-x_0|+k|x_0-\alpha|$, so $|x_0-\alpha|\le|x_1-x_0|/(1-k)$; combine with the first. The third is the second applied with $x_{n-1}$ as the starting point. ∎ (This is the contraction mapping principle of §4.1 on the complete space $[a,b]$.)

📐 Theorem 9.10 — Local convergence and order of fixed-point iteration
Let $g(\alpha)=\alpha$ and let $g$ be $C^1$ near $\alpha$.
  1. If $|g'(\alpha)|\lt1$, the iteration converges to $\alpha$ for every $x_0$ close enough to $\alpha$; if $0\lt|g'(\alpha)|\lt1$ the convergence is linear with rate $|g'(\alpha)|$ — monotone if $g'(\alpha)\gt0$, oscillating about $\alpha$ if $g'(\alpha)\lt0$.
  2. If $|g'(\alpha)|\gt1$, no sequence of iterates converges to $\alpha$ (unless some $x_n$ equals $\alpha$ exactly).
  3. If $g\in C^p$ near $\alpha$ ($p\ge2$) with $g'(\alpha)=\cdots=g^{(p-1)}(\alpha)=0$ and $g^{(p)}(\alpha)\ne0$, the convergence (for $x_0$ near $\alpha$) has order exactly $p$, with $\displaystyle\lim\frac{e_{n+1}}{e_n^p}=\frac{g^{(p)}(\alpha)}{p!}$.

Proof. (1) Choose $k$ with $|g'(\alpha)|\lt k\lt1$; by continuity $|g'|\le k$ on some interval $I=[\alpha-\delta,\alpha+\delta]$, and then $|g(x)-\alpha|=|g(x)-g(\alpha)|\le k|x-\alpha|\le\delta$, so $g(I)\subseteq I$ and Theorem 9.9 applies. By the mean value theorem $e_{n+1}=g(x_n)-g(\alpha)=g'(\xi_n)e_n$ with $\xi_n$ between $x_n$ and $\alpha$; as $x_n\to\alpha$, $e_{n+1}/e_n=g'(\xi_n)\to g'(\alpha)$, which gives the rate and the sign behaviour. (2) Near $\alpha$, $|g'|\ge K\gt1$, so $|e_{n+1}|\ge K|e_n|$ as long as $x_n$ stays near $\alpha$: the error grows, and the iterates cannot settle at $\alpha$. (3) Taylor's theorem with the Lagrange remainder: $e_{n+1}=g(x_n)-g(\alpha)=\dfrac{g^{(p)}(\eta_n)}{p!}e_n^p$ with $\eta_n$ between $x_n$ and $\alpha$; convergence follows from (1) since $g'(\alpha)=0$, and then $e_{n+1}/e_n^p\to g^{(p)}(\alpha)/p!\ne0$. ∎

✏️ Example 6 — Four ways to write $x=e^{-x}$
The equation $x=e^{-x}$ has a unique root $\alpha\approx0.567143$. Predict, and then check, what fixed-point iteration from $x_0=0.5$ does for (a) $g_1(x)=e^{-x}$; (b) $g_2(x)=-\log x$; (c) $g_3(x)=\tfrac12\left(x+e^{-x}\right)$; (d) $g_4(x)=x-\dfrac{x-e^{-x}}{1+e^{-x}}$.
(a) linear, oscillating $g_1'(\alpha)=-e^{-\alpha}=-\alpha\approx-0.567$. Linear convergence with rate $0.567$, alternating sides: $0.6065,\ 0.5452,\ 0.5797,\ 0.5601,\ 0.5712,\dots$ About $0.25$ digits per step.
(b) diverges $g_2'(\alpha)=-1/\alpha\approx-1.763$, so $|g_2'(\alpha)|\gt1$ (Theorem 9.10(2)): $0.6931,\ 0.3665,\ 1.0037,\ -0.0037$, and then $\log$ of a negative number is undefined. ($g_2$ is the inverse function of $g_1$, which is why its derivative at $\alpha$ is the reciprocal.)
(c) faster linear $g_3'(\alpha)=\tfrac12(1-e^{-\alpha})=\tfrac12(1-\alpha)\approx0.216$: monotone linear convergence, $0.5533,\ 0.5642,\ 0.5665,\ 0.5670,\ 0.56711,\dots$ — about $0.66$ digits per step.
(d) quadratic $g_4$ is Newton's iteration for $f(x)=x-e^{-x}$ (next subsection), so $g_4'(\alpha)=0$: $0.566311,\ 0.56714317,\ 0.56714329$ — the number of correct digits roughly doubles each step ($3$, then $7$, then $14$).
Lesson Among the family $g_\lambda(x)=(1-\lambda)x+\lambda e^{-x}$, the derivative $g_\lambda'(\alpha)=1-\lambda(1+\alpha)$ vanishes for $\lambda=1/(1+\alpha)\approx0.638$: choosing the rearrangement to make $g'(\alpha)=0$ is exactly how Newton's method arises.

Newton–Raphson and the Secant Method

Replace the graph of $f$ near the current point by its tangent line, and take the tangent's root as the next approximation. That is Newton's method; replacing the tangent by the chord through the last two points gives the secant method, which needs no derivative.

📘 Definition 9.8 — Newton–Raphson method; multiplicity of a root
For differentiable $f$ and a starting value $x_0$, the Newton–Raphson method is $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\qquad(f'(x_n)\ne0),$$ the fixed-point iteration of $g(x)=x-f(x)/f'(x)$. A root $\alpha$ has multiplicity $m$ if $f(\alpha)=f'(\alpha)=\cdots=f^{(m-1)}(\alpha)=0\ne f^{(m)}(\alpha)$; it is simple if $m=1$, i.e. $f'(\alpha)\ne0$.
📐 Theorem 9.11 — Local quadratic convergence of Newton's method
Let $f\in C^2$ near a simple root $\alpha$. Then there is $\delta\gt0$ such that for every $x_0\in[\alpha-\delta,\alpha+\delta]$ Newton's iterates stay in this interval, converge to $\alpha$, and $$\lim_{n\to\infty}\frac{e_{n+1}}{e_n^2}=\frac{f''(\alpha)}{2f'(\alpha)}.$$ So the convergence is at least quadratic, and exactly quadratic when $f''(\alpha)\ne0$ (cubic or better when $f''(\alpha)=0$ and $f\in C^3$).

Proof. Taylor's theorem about $x_n$, evaluated at $\alpha$: $0=f(\alpha)=f(x_n)+f'(x_n)(\alpha-x_n)$ $+\,\tfrac12f''(\eta_n)(\alpha-x_n)^2$ with $\eta_n$ between $x_n$ and $\alpha$. Divide by $f'(x_n)$ and use $x_n-f(x_n)/f'(x_n)=x_{n+1}$: $$e_{n+1}=x_{n+1}-\alpha=\frac{f''(\eta_n)}{2f'(x_n)}\,e_n^2.$$ Since $f'(\alpha)\ne0$, pick an interval $I=[\alpha-\delta_0,\alpha+\delta_0]$ on which $|f'|\ge m\gt0$ and $|f''|\le M$, and put $K=M/(2m)$ and $\delta=\min(\delta_0,\tfrac1{2K})$. For $x_n\in[\alpha-\delta,\alpha+\delta]$ we get $|e_{n+1}|\le K|e_n|^2\le\tfrac12|e_n|$, so the iterates stay in the interval and $e_n\to0$. Finally $\eta_n\to\alpha$ and $x_n\to\alpha$, so $e_{n+1}/e_n^2\to f''(\alpha)/(2f'(\alpha))$. ∎

📐 Theorem 9.12 — Monotone convergence of Newton's method (Fourier's condition)
Let $f\in C^2[a,b]$ with $f(a)f(b)\lt0$, and suppose $f'$ and $f''$ are each nonzero and of constant sign on $[a,b]$. If $x_0\in[a,b]$ satisfies $f(x_0)f''(x_0)\gt0$, Newton's iterates converge monotonically to the unique root $\alpha$ of $f$ in $[a,b]$.

Proof (case $f'\gt0$, $f''\gt0$). Then $f$ is increasing and convex with a unique root $\alpha$, and $f(x_0)\gt0$ means $x_0\gt\alpha$. A convex graph lies above each tangent line, so the tangent at $x_n\gt\alpha$ is $\le f$ and vanishes at a point $x_{n+1}\ge\alpha$; and $x_{n+1}=x_n-f(x_n)/f'(x_n)\lt x_n$. So $(x_n)$ decreases and is bounded below by $\alpha$; its limit $L$ satisfies $L=L-f(L)/f'(L)$, i.e. $f(L)=0$, so $L=\alpha$. The other three sign cases follow by replacing $f(x)$ with $-f(x)$, $f(-x)$ or $-f(-x)$. ∎

📐 Theorem 9.13 — Newton's method at a multiple root
Let $f(x)=(x-\alpha)^mh(x)$ with $m\ge2$, $h$ of class $C^2$ near $\alpha$ and $h(\alpha)\ne0$. Then Newton's method converges to $\alpha$ for $x_0$ near $\alpha$, but only linearly, with rate $\dfrac{m-1}{m}$. The modified Newton method $x_{n+1}=x_n-m\,\dfrac{f(x_n)}{f'(x_n)}$ restores (at least) quadratic convergence; so does Newton's method applied to $u=f/f'$, which has a simple root at $\alpha$.

Proof. $f'(x)=(x-\alpha)^{m-1}\big(mh(x)+(x-\alpha)h'(x)\big)$, so for $x\ne\alpha$ near $\alpha$ $$\frac{f(x)}{f'(x)}=(x-\alpha)\,\varphi(x),\qquad\varphi(x)=\frac{h(x)}{mh(x)+(x-\alpha)h'(x)},\qquad\varphi(\alpha)=\frac1m.$$ Newton's function is $g(x)=x-(x-\alpha)\varphi(x)$, with $g(\alpha)=\alpha$ and $g'(\alpha)=1-\varphi(\alpha)=1-\tfrac1m\in(0,1)$; Theorem 9.10(1) gives linear convergence with rate $\tfrac{m-1}{m}$. For the modified method, $g_m(x)=x-m(x-\alpha)\varphi(x)$ has $g_m'(\alpha)=1-m\varphi(\alpha)=0$, so the convergence is superlinear, and quadratic by the Taylor argument of Theorem 9.10(3). Finally $u=f/f'=(x-\alpha)\varphi$ with $\varphi(\alpha)\ne0$ has a simple root at $\alpha$. ∎

📘 Definition 9.9 — Secant method and regula falsi
From two starting values $x_0\ne x_1$, the secant method is $$x_{n+1}=x_n-f(x_n)\,\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}=\frac{x_{n-1}f(x_n)-x_nf(x_{n-1})}{f(x_n)-f(x_{n-1})},$$ the root of the chord through the last two points. Regula falsi (false position) uses the same formula but, like bisection, keeps a bracket: it replaces whichever endpoint of the current bracket $[a_n,b_n]$ has $f$ of the same sign as $f(x_{n+1})$.
📐 Theorem 9.14 — Orders of the secant method and of regula falsi
(a) Let $f\in C^2$ near a simple root $\alpha$ with $f''(\alpha)\ne0$. For $x_0,x_1$ close enough to $\alpha$ the secant iterates converge with order $$p=\frac{1+\sqrt5}{2}\approx1.618,\qquad\text{and}\qquad e_{n+1}\approx\frac{f''(\alpha)}{2f'(\alpha)}\,e_ne_{n-1}.$$ (b) If $f''$ has constant sign on the bracket, one endpoint of regula falsi stays fixed from some step on, and its convergence is only linear.
(c) Per evaluation of $f$ or $f'$, Newton's method (two evaluations per step, order $2$) multiplies the correct digits by $\sqrt2\approx1.41$, the secant method (one evaluation per step) by $1.618$: the efficiency index $p^{1/w}$ favours the secant method when $f'$ is as costly as $f$.

Proof (sketch of (a)). With divided differences $f[u,v]=\frac{f(u)-f(v)}{u-v}$ and $f[u,v,w]=\frac{f[u,v]-f[v,w]}{u-w}$ (developed in §9.2), a short computation from the secant formula gives the exact identity $e_{n+1}=\dfrac{f[x_{n-1},x_n,\alpha]}{f[x_{n-1},x_n]}\,e_ne_{n-1}$. The mean value theorem for divided differences turns the fraction into $\dfrac{f''(\zeta_n)/2}{f'(\theta_n)}\to\dfrac{f''(\alpha)}{2f'(\alpha)}=:c$. If $|e_{n+1}|$ is about $K|e_n|^p$, then $|e_n|\approx(|e_{n+1}|/K)^{1/p}$ shifted by one index gives $K|e_n|^p\approx|c|\,|e_n|\,(|e_n|/K)^{1/p}$; matching powers of $|e_n|$ forces $p=1+1/p$, i.e. $p^2=p+1$, whose positive root is $\tfrac{1+\sqrt5}{2}$. (b) and (c) are discussed in the Go deeper box. ∎

✏️ Example 7 — Newton's method: a reciprocal without division, a cube root, and a double root
(a) Show that Newton's method for $f(x)=\tfrac1x-a$ ($a\gt0$) needs no division, and find for which $x_0$ it converges to $1/a$. Run it for $a=7$, $x_0=0.1$. (b) Two Newton steps for $x^3=2$ from $x_0=1$. (c) Newton's method for $f(x)=(x-1)^2(x+2)$ from $x_0=2$, and the modified method.
(a) Formula $f'(x)=-1/x^2$, so $x_{n+1}=x_n+x_n^2\left(\tfrac1{x_n}-a\right)=x_n(2-ax_n)$ — only multiplications. With $r_n=1-ax_n$ we get $r_{n+1}=1-ax_n(2-ax_n)=(1-ax_n)^2=r_n^2$, so $r_n=r_0^{2^n}$: convergence iff $|r_0|\lt1$, i.e. $0\lt x_0\lt\tfrac2a$, and then quadratic. For $a=7$, $x_0=0.1$ ($r_0=0.3$): $0.13$, $0.1417$, $0.14284777$, $0.142857142,\dots$ $\to\tfrac17=0.142857\ldots$
(b) Cube root $x_{n+1}=x_n-\frac{x_n^3-2}{3x_n^2}=\frac{2x_n^3+2}{3x_n^2}$. $x_1=\tfrac43\approx1.3333$, $x_2=\tfrac{2(64/27)+2}{3(16/9)}=\tfrac{91}{72}\approx1.26389$; errors $0.073$, $0.0040$, and $x_3\approx1.259933$ has error $1.2\times10^{-5}$ — quadratic, as $c=\frac{f''}{2f'}=\frac1{\sqrt[3]2}\approx0.79$ predicts ($0.79\cdot0.0040^2\approx1.3\times10^{-5}$).
(c) Double root $f=(x-1)^2(x+2)$ has a double root at $1$ ($m=2$). Newton from $2$: $1.5556,\ 1.2979,\ 1.1554,\ 1.0796,\ 1.0403$ — errors $0.556,0.298,0.155,0.080,0.040$, ratios tending to $\tfrac12=\tfrac{m-1}{m}$ (Theorem 9.13): linear.
(c) Modified $x_{n+1}=x_n-2f(x_n)/f'(x_n)$: $1.1111,\ 1.0019493,\ 1.00000063$ — errors $0.11$, $1.9\times10^{-3}$, $6.3\times10^{-7}$: quadratic again.
🧭 Root-finding in GATE time
  1. Order of a given iteration $x_{n+1}=g(x_n)$: find the fixed point, differentiate $g$ there; the first non-vanishing derivative $g^{(p)}(\alpha)$ gives order $p$ (Theorem 9.10). Rational iterations such as Halley's $x\,\frac{x^2+3a}{3x^2+a}$ for $\sqrt a$ often have $g'(\alpha)=g''(\alpha)=0$: order $3$.
  2. Standard Newton formulas to know by heart: $\sqrt N$: $x_{n+1}=\tfrac12\left(x_n+\tfrac N{x_n}\right)$; $\sqrt[k]N$: $x_{n+1}=\tfrac1k\left((k-1)x_n+\tfrac N{x_n^{k-1}}\right)$; $\tfrac1N$: $x_{n+1}=x_n(2-Nx_n)$; $\tfrac1{\sqrt N}$: $x_{n+1}=\tfrac{x_n}{2}\left(3-Nx_n^2\right)$.
  3. Multiple root suspected (Newton creeping, $f'$ small): the ratio $e_{n+1}/e_n\approx\tfrac{m-1}{m}$ reveals $m$; use the modified method.
  4. Bisection step counts: $n\ge\log_2\frac{b-a}{\varepsilon}$ (bracket length) or $n\ge\log_2\frac{b-a}{\varepsilon}-1$ (midpoint error); compute $\log_2$ as $\log_{10}/0.30103$.
  5. Orders to remember: bisection and regula falsi $1$, fixed point $1$ (if $g'(\alpha)\ne0$), secant $1.618$, Newton $2$ at simple roots and $1$ at multiple roots.
⚠️ Counterexamples and pitfalls
  1. A nonsingular matrix need not have an LU factorisation. $\begin{pmatrix}0&1\\1&0\end{pmatrix}$: $\Delta_1=0$. It does have $PA=LU$ with $P$ the interchange (Theorem 9.3(b)).
  2. Exact arithmetic is not enough: pivot. In $4$-digit arithmetic, $0.0001x+y=1$, $x+y=2$ without pivoting gives $y=1.000$, $x=0.000$; with partial pivoting it gives $x=1.000$, $y=0.9999$ (true solution $x=1.0001\ldots$, $y=0.9998\ldots$, rounded to $1.000$ and $0.9999$). A tiny pivot creates a huge multiplier that swamps the data.
  3. Positive diagonal and symmetry do not give Cholesky. $\begin{pmatrix}1&2\\2&1\end{pmatrix}$ is symmetric with positive diagonal but indefinite ($\Delta_2=-3$); the recursion needs $\sqrt{-3}$.
  4. Diagonal dominance is sufficient, not necessary. $\begin{pmatrix}1&0.6&0.6\\0.6&1&0.6\\0.6&0.6&1\end{pmatrix}$ is not dominant, yet Gauss–Seidel converges.
  5. Neither of Jacobi and Gauss–Seidel dominates the other. Example 5: Jacobi converges and Gauss–Seidel diverges for $\begin{pmatrix}1&2&-2\\1&1&1\\2&2&1\end{pmatrix}$; the reverse happens for the matrix above.
  6. Positive definite does not make Jacobi converge (same matrix: $\rho(T_J)=1.2$). It does make Gauss–Seidel converge.
  7. $\|T\|\ge1$ does not mean divergence. $T=\begin{pmatrix}0.5&2\\0&0.5\end{pmatrix}$ has $\|T\|_\infty=2.5$ but $\rho(T)=0.5$: the iteration converges (after an initial growth of the error).
  8. A self-map of $[a,b]$ need not give a convergent iteration. $g(x)=1-x$ on $[0,1]$ has the fixed point $\tfrac12$, but from $x_0=0$ the iterates are $0,1,0,1,\dots$ ($|g'|=1$, not $\lt1$).
  9. Newton's method can diverge or cycle at a simple root. For $\arctan x$ it diverges from $|x_0|\gt1.3917$; for $f(x)=x^{1/3}$ the iteration is $x_{n+1}=-2x_n$ (here $f'$ is unbounded at the root, so Theorem 9.11 does not apply); for $x^3-2x+2$ from $x_0=0$ it cycles $0,1,0,1,\dots$
  10. Newton is not always quadratic. At a double root it is linear with rate $\tfrac12$; at a simple root with $f''(\alpha)=0$ it is cubic.
  11. Regula falsi is not superlinear despite using the secant formula: for convex $f$ one endpoint sticks and the convergence is linear — sometimes slower than bisection.
  12. Small residual $\ne$ small error. $f(x)=(x-1)^{10}$ has $|f(1.1)|=10^{-10}$ although $x=1.1$ is $0.1$ from the root; near a multiple root $|f|$ is a poor stopping test.
📚 Go deeper — full proofs in the CSIR NET course

Two Labs

Interactive 1 — Tangents, Chords and Brackets: Four Root-Finders on the Graph

Left: the graph of $f$ with the construction of the latest step — Newton's tangent, the secant's or regula falsi's chord, or bisection's shaded bracket — and the iterates marked on the axis. Right: the number of correct digits $-\log_{10}|x_n-\alpha|$ after each step. Press Play (or Step); change the method, the function and the start $x_0$. Watch the bars: do they grow by a fixed amount (linear) or double (quadratic)?

step n—
xₙ—
|xₙ − α|—
measured order—
Interactive 2 — Jacobi versus Gauss–Seidel: Spectral Radius Decides

We solve $Ax=b$ with exact solution $(1,1,1)$ from $x^{(0)}=0$. Left: $\log_{10}$ of the error $\|x^{(k)}-x^*\|_\infty$ for Jacobi and Gauss–Seidel; a straight line of slope $\log_{10}\rho(T)$ is what Theorem 9.5 predicts. Right: the matrix, each row marked dominant or not, and both spectral radii against the critical value $1$. Move the diagonal $d$; Play steps $d$ upwards and redraws.

d—
ρ(T_J)—
ρ(T_GS)—
strictly dominant? positive definite?—

Exercises

I
Direct methods.
  • 1 Solve $2x+y-z=1$, $4x+5y-3z=3$, $-2x+5y-2z=-1$ by Gaussian elimination without interchanges. Give the multipliers, $U$ and $\det A$.
  • 2 Solve $0.0001x+y=1$, $x+y=2$ in $4$-significant-digit arithmetic, without and with partial pivoting, and compare with the true solution.
  • 3 Find the Doolittle factorisation of $A=\begin{pmatrix}1&2&3\\2&5&8\\3&8&14\end{pmatrix}$, and deduce its Cholesky factorisation.
  • 4 Find the Crout factorisation of $\begin{pmatrix}3&6\\2&7\end{pmatrix}$.
  • 5 Show that $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ has no LU factorisation, and give $P,L,U$ with $PA=LU$.
  • 6 For which real $k$ does $\begin{pmatrix}4&2&0\\2&k&1\\0&1&1\end{pmatrix}$ have a Cholesky factorisation? Find it for $k=3$.
  • 7 How many multiplications/divisions does Gaussian elimination with back substitution need for $n=10$? Roughly how much longer does $n=1000$ take than $n=100$?
  • 8 The pivots of elimination without interchanges on a $4\times4$ matrix are $2,-1,3,\tfrac12$. Find $\Delta_1,\dots,\Delta_4$.
1 $m_{21}=2$, $m_{31}=-1$: rows become $(0,3,-1\mid1)$ and $(0,6,-3\mid0)$; $m_{32}=2$: $(0,0,-1\mid-2)$. $U=\begin{pmatrix}2&1&-1\\0&3&-1\\0&0&-1\end{pmatrix}$, $z=2$, $y=1$, $x=1$; $\det A=2\cdot3\cdot(-1)=-6$.
2 Without pivoting: $m=10^4$, $(1-10^4)y=2-10^4$ rounds to $-1.000\times10^4y=-1.000\times10^4$, $y=1.000$, $x=(1-y)/0.0001=0$. With pivoting (swap): $m=0.0001$, $0.9999y=0.9998$, $y=0.9999$, $x=2-0.9999=1.000$. True: $x=\tfrac{10000}{9999}=1.0001\ldots$, $y=\tfrac{9998}{9999}=0.9998\ldots$ Pivoting is right to $4$ digits; no pivoting loses $x$ completely.
3 $L=\begin{pmatrix}1&0&0\\2&1&0\\3&2&1\end{pmatrix}$, $U=\begin{pmatrix}1&2&3\\0&1&2\\0&0&1\end{pmatrix}=L^{\mathsf T}$. Since the pivots are all $1\gt0$, $A$ is positive definite and its Cholesky factor is $L$ itself; $\det A=1$.
4 Doolittle: $L=\begin{pmatrix}1&0\\\tfrac23&1\end{pmatrix}$, $U=\begin{pmatrix}3&6\\0&3\end{pmatrix}$. Crout: $\begin{pmatrix}3&0\\2&3\end{pmatrix}\begin{pmatrix}1&2\\0&1\end{pmatrix}$ (check: $2\cdot2+3=7$).
5 $LU$ with $l_{11}=1$ would give $a_{11}=u_{11}=0$ and then $a_{21}=l_{21}u_{11}=0\ne1$. With $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$: $PA=I=I\cdot I$.
6 $\Delta_1=4$, $\Delta_2=4k-4$, $\Delta_3=4k-8$: positive definite iff $k\gt2$. For $k=3$: $l_{11}=2$, $l_{21}=1$, $l_{31}=0$, $l_{22}=\sqrt{3-1}=\sqrt2$, $l_{32}=\tfrac1{\sqrt2}$, $l_{33}=\sqrt{1-\tfrac12}=\tfrac1{\sqrt2}$.
7 $\tfrac{1000}{3}+100-\tfrac{10}{3}=430$. The cost grows like $n^3$, so $n=1000$ takes about $10^3=1000$ times as long as $n=100$.
8 $\Delta_k=$ product of the first $k$ pivots: $2,\ -2,\ -6,\ -3$.
II
Iterative methods.
  • 1 For $4x+y=9$, $x+3y=5$ compute two Jacobi iterations from $(0,0)$.
  • 2 Same system: two Gauss–Seidel iterations from $(0,0)$. Compare with the solution $(2,1)$.
  • 3 For $A=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ with $ad\ne0$, show $\rho(T_J)=\sqrt{|bc/(ad)|}$ and $\rho(T_{GS})=|bc/(ad)|$.
  • 4 Show that both methods diverge for $x+2y=3$, $3x+y=4$, and that both converge after interchanging the two equations.
  • 5 For $A=\begin{pmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{pmatrix}$ find $\rho(T_J)$ and $\rho(T_{GS})$. About how many Gauss–Seidel iterations reduce the error by a factor $10^{-6}$?
  • 6 An iteration has $\|T\|_\infty=\tfrac12$ and $\|x^{(1)}-x^{(0)}\|_\infty=1$. How many iterations guarantee $\|x^{(k)}-x^*\|_\infty\le10^{-4}$?
  • 7 For which real $a$ does Jacobi converge for $A=\begin{pmatrix}1&a&a\\a&1&a\\a&a&1\end{pmatrix}$? For which $a$ does Gauss–Seidel converge?
  • 8 Show that if $A$ is strictly diagonally dominant by columns, Jacobi converges. (Hint: $\|\cdot\|_1$ and $DT_JD^{-1}$.)
1 $x=\tfrac{9-y}{4}$, $y=\tfrac{5-x}{3}$. $x^{(1)}=(2.25,\ 1.6667)$, $x^{(2)}=\left(\tfrac{11}{6},\ \tfrac{11}{12}\right)\approx(1.8333,\ 0.9167)$.
2 $x^{(1)}=\left(2.25,\ \tfrac{11}{12}\right)$, $x^{(2)}=\left(\tfrac{97}{48},\ \tfrac{143}{144}\right)\approx(2.0208,\ 0.9931)$. Errors after two steps: Jacobi $0.167$, Gauss–Seidel $0.021$; here $\rho(T_{GS})=\tfrac1{12}=\rho(T_J)^2$.
3 $T_J=\begin{pmatrix}0&-b/a\\-c/d&0\end{pmatrix}$ has $\lambda^2=\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&-b/a\\0&bc/(ad)\end{pmatrix}$, eigenvalues $0$ and $\tfrac{bc}{ad}$.
4 $\tfrac{bc}{ad}=6$: $\rho(T_J)=\sqrt6$, $\rho(T_{GS})=6$, both $\gt1$. Interchanged: $3x+y=4$, $x+2y=3$ is dominant, $\tfrac{bc}{ad}=\tfrac16$: both converge (to $(1,1)$).
5 $T_J$ has eigenvalues $0,\pm\tfrac{\sqrt2}{2}$, so $\rho(T_J)=\tfrac{\sqrt2}2\approx0.707$ and, the matrix being tridiagonal, $\rho(T_{GS})=\tfrac12$ (Theorem 9.7(3)). Need $2^{-k}\le10^{-6}$: $k\ge6/\log_{10}2\approx19.9$, about $20$ iterations (Jacobi needs about $40$).
6 $\tfrac{(1/2)^k}{1/2}\cdot1\le10^{-4}$, i.e. $2^{k}\ge2\times10^4$, $k\ge\log_2(2\times10^4)\approx14.3$: $k=15$.
7 $T_J=-a(J-I)$ with $J$ the all-ones matrix (eigenvalues $3,0,0$), so $T_J$ has eigenvalues $-2a,\ a,\ a$: Jacobi converges iff $|a|\lt\tfrac12$. $A$ is symmetric with unit diagonal and eigenvalues $1+2a,\ 1-a,\ 1-a$, positive iff $-\tfrac12\lt a\lt1$; by Ostrowski–Reich, Gauss–Seidel converges iff $-\tfrac12\lt a\lt1$.
8 $DT_JD^{-1}=-(L+U)D^{-1}$ has off-diagonal entries $-a_{ij}/a_{jj}$; its column sums in absolute value are $\sum_{i\ne j}|a_{ij}|/|a_{jj}|\lt1$. So $\|DT_JD^{-1}\|_1\lt1$, hence $\rho(T_J)=\rho(DT_JD^{-1})\lt1$ (similar matrices have the same eigenvalues) and Theorem 9.5 applies.
III
Root-finding.
  • 1 Perform four steps of bisection for $x^3+x-1=0$ on $[0,1]$ and give the final bracket.
  • 2 How many bisection steps on $[1,2]$ guarantee a bracket of length at most $10^{-6}$?
  • 3 Show that $x_{n+1}=1+\tfrac1{x_n}$ converges to the golden ratio $\varphi=\tfrac{1+\sqrt5}{2}$ from every $x_0\ge1$, and find its rate.
  • 4 For which $\lambda$ does $x_{n+1}=x_n+\lambda(x_n^2-3)$ converge to $\sqrt3$ from nearby starts? Which $\lambda$ gives quadratic convergence?
  • 5 Two Newton steps for $\sqrt{10}$ from $x_0=3$.
  • 6 Show that Newton's method for $f(x)=x^{1/3}$ diverges from every $x_0\ne0$. Which hypothesis of Theorem 9.11 fails?
  • 7 What is the rate of linear convergence of Newton's method for $f(x)=x^3$? For $f(x)=x^2\sin x$ at $0$?
  • 8 Three secant steps for $x^3-2x-5=0$ from $x_0=2$, $x_1=3$.
  • 9 Find the order of $x_{n+1}=\dfrac{x_n(x_n^2+3a)}{3x_n^2+a}$ ($a\gt0$) as an iteration for $\sqrt a$.
1 $f(0)=-1$, $f(1)=1$. $c_0=0.5$: $f=-0.375$, bracket $[0.5,1]$. $c_1=0.75$: $f=0.172$, $[0.5,0.75]$. $c_2=0.625$: $f=-0.131$, $[0.625,0.75]$. $c_3=0.6875$: $f=0.0125$, $[0.625,0.6875]$. (Root $0.68233$.)
2 $2^{-n}\le10^{-6}$: $n\ge6/\log_{10}2\approx19.93$, so $n=20$.
3 $g(x)=1+\tfrac1x$ maps $[1,2]$ into $[1.5,2]\subseteq[1,2]$, and for $x_0\ge1$ already $x_1\in(1,2]$. On $[1.5,2]$, $|g'(x)|=\tfrac1{x^2}\le\tfrac49\lt1$, so Theorem 9.9 applies from $x_2\in[1.5,2]$ on. Rate $|g'(\varphi)|=\tfrac1{\varphi^2}\approx0.382$, oscillating ($2,\,1.5,\,1.667,\,1.6,\,1.625,\dots$).
4 $g'(\sqrt3)=1+2\sqrt3\lambda$; need $|1+2\sqrt3\lambda|\lt1$, i.e. $-\tfrac1{\sqrt3}\lt\lambda\lt0$. Quadratic for $\lambda=-\tfrac1{2\sqrt3}$ (then $g''(\sqrt3)=2\lambda\ne0$, order exactly $2$).
5 $x_1=\tfrac12\left(3+\tfrac{10}3\right)=\tfrac{19}{6}\approx3.166667$; $x_2=\tfrac12\left(\tfrac{19}6+\tfrac{60}{19}\right)=\tfrac{721}{228}\approx3.162281$ (true $3.162278$).
6 $f'(x)=\tfrac13x^{-2/3}$, so $x-\tfrac{f}{f'}=x-3x=-2x$: $|x_n|=2^n|x_0|\to\infty$. $f$ is not differentiable at the root (no $f\in C^2$ near $\alpha$, and $f'(\alpha)$ does not exist).
7 $x^3$: triple root, $x_{n+1}=\tfrac23x_n$, rate $\tfrac23$. $x^2\sin x=x^3\cdot\tfrac{\sin x}{x}$: also a triple root at $0$, rate $\tfrac23$.
8 $x_2=2.058824$, $x_3=2.081264$, $x_4=2.094824$ (root $2.094551$).
9 $g(\sqrt a)=\sqrt a$, and $g'(\sqrt a)=g''(\sqrt a)=0$, $g'''(\sqrt a)=\tfrac{3}{2a}\ne0$ (Halley's method). Order $3$, with $e_{n+1}\approx\tfrac{1}{4a}e_n^3$.
IV
Prove or disprove, and one model.
  • 1 A strictly diagonally dominant matrix is nonsingular.
  • 2 If $A$ is real symmetric with positive diagonal entries, $A$ has a Cholesky factorisation.
  • 3 If $g$ is continuous and maps $[a,b]$ into itself, fixed-point iteration converges from every $x_0\in[a,b]$.
  • 4 If Newton's method converges to a root, the convergence is quadratic.
  • 5 If $\rho(T)\lt1$, then $x^{(k+1)}=Tx^{(k)}+c$ converges even when $\|T\|_\infty\gt1$.
  • 6 Orbits. Kepler's equation $E-e\sin E=M$ gives the eccentric anomaly $E$ of a satellite with eccentricity $e$ at mean anomaly $M$. For $e=0.5$, $M=1$ (radians) perform three Newton steps from $E_0=M$, and explain why the fixed-point iteration $E_{n+1}=M+e\sin E_n$ also converges, and how fast.
1 True. If $Ax=0$, $x\ne0$, pick $i$ with $|x_i|=\|x\|_\infty$; then $|a_{ii}||x_i|=\big|\sum_{j\ne i}a_{ij}x_j\big|\le\sum_{j\ne i}|a_{ij}||x_i|$, contradicting dominance (Lévy–Desplanques; also Theorem 9.6).
2 False. $\begin{pmatrix}1&2\\2&1\end{pmatrix}$ is indefinite; Theorem 9.4 needs positive definiteness.
3 False. $g(x)=1-x$ on $[0,1]$: $0,1,0,1,\dots$ A fixed point exists (Theorem 9.9(a)), but convergence needs a contraction condition such as $|g'|\le k\lt1$.
4 False. At a root of multiplicity $m\ge2$ it is linear with rate $\tfrac{m-1}{m}$ (Theorem 9.13), e.g. $x^2$ from $x_0=1$: $x_n=2^{-n}$.
5 True (Theorem 9.5). $T=\begin{pmatrix}0.5&2\\0&0.5\end{pmatrix}$: $\|T\|_\infty=2.5$, $\rho(T)=0.5$, and $T^k=\begin{pmatrix}0.5^k&4k\,0.5^k\\0&0.5^k\end{pmatrix}\to0$.
6 $f(E)=E-0.5\sin E-1$, $f'(E)=1-0.5\cos E$. $E_1=1.576469$, $E_2=1.500208$, $E_3=1.498702$ (root $1.4987011$; the first step overshoots, then quadratic convergence). For $g(E)=1+0.5\sin E$: $|g'|=0.5|\cos E|\le0.5$ everywhere, so it converges from any start (Theorem 9.9 on a suitable interval), linearly with rate $0.5|\cos E^*|\approx0.036$ — fast because $E^*$ is close to $\tfrac\pi2$.
🎯 GATE corner GATE MA · MCQGATE MA · MSQGATE MA · NAT

E1. GATE MA · MCQ Let $A=\begin{pmatrix}4&2&2\\2&5&3\\2&3&6\end{pmatrix}=LL^{\mathsf T}$ be the Cholesky factorisation, $L$ lower triangular with positive diagonal. Then $l_{33}$ equals (A) $1$; (B) $\sqrt2$; (C) $2$; (D) $\sqrt3$.

Recursion $l_{11}=2$, $l_{21}=1$, $l_{31}=1$; $l_{22}=\sqrt{5-1}=2$, $l_{32}=\tfrac{3-1\cdot1}{2}=1$; $l_{33}=\sqrt{6-1-1}=2$.
Check $\det A=(2\cdot2\cdot2)^2=64$; directly $4(30-9)-2(12-6)+2(6-10)$ $=84-12-8=64$. ✓
Answer (C).

E2. GATE MA · MCQ For $a\gt0$, the iteration $x_{n+1}=\dfrac{x_n(x_n^2+3a)}{3x_n^2+a}$ converges to $\sqrt a$ for $x_0$ near $\sqrt a$. Its order of convergence is (A) $1$; (B) $2$; (C) $3$; (D) $4$.

Error identity With $s=\sqrt a$: $g(x)-s=\dfrac{x^3+3ax-3sx^2-as}{3x^2+a}$ $=\dfrac{(x-s)^3}{3x^2+a}$ (expand $(x-s)^3=x^3-3sx^2+3ax-as$).
Order So $e_{n+1}=e_n^3/(3x_n^2+a)$ and $e_{n+1}/e_n^3\to\tfrac1{4a}\ne0$: order exactly $3$ (equivalently $g'(s)=g''(s)=0\ne g'''(s)$).
Answer (C).

E3. GATE MA · MSQ For a real number $a$ let $A_a=\begin{pmatrix}1&a&a\\a&1&a\\a&a&1\end{pmatrix}$, and consider the Jacobi and Gauss–Seidel iterations for $A_ax=b$. Which of the following is/are true? (One or more options may be correct.) (A) For $a=0.4$ both iterations converge for every initial vector. (B) For $a=0.7$ the Jacobi iteration converges for every initial vector. (C) For $a=0.7$ the Gauss–Seidel iteration converges for every initial vector. (D) For $a=-0.6$ the Gauss–Seidel iteration converges for every initial vector.

Facts $T_J=-a(J-I)$ has eigenvalues $-2a,a,a$, so $\rho(T_J)=2|a|$. $A_a$ is symmetric with unit diagonal and eigenvalues $1+2a$, $1-a$, $1-a$; it is positive definite iff $-\tfrac12\lt a\lt1$, and by Ostrowski–Reich (Theorem 9.7(1)) Gauss–Seidel converges iff $-\tfrac12\lt a\lt1$.
(A) True $a=0.4$: strictly diagonally dominant ($1\gt0.8$), so both converge (Theorem 9.6); $\rho(T_J)=0.8$, $\rho(T_{GS})\approx0.253$.
(B) False, (C) True $a=0.7$: $\rho(T_J)=1.4\gt1$, Jacobi diverges; $A_{0.7}$ is positive definite (eigenvalues $2.4,0.3,0.3$), Gauss–Seidel converges ($\rho(T_{GS})\approx0.586$).
(D) False $a=-0.6$: $1+2a=-0.2\lt0$, not positive definite, so Gauss–Seidel does not converge for every start (numerically $\rho(T_{GS})\approx1.445$).
Answer (A) and (C).

E4. GATE MA · MSQ Which of the following statements is/are true? (One or more options may be correct.) (A) If $f\in C^2$ and $\alpha$ is a simple root of $f$, Newton's method converges to $\alpha$ at least quadratically for every $x_0$ sufficiently close to $\alpha$. (B) Newton's method for $f(x)=x^2(x-1)$, started close to $0$, converges to $0$ linearly with rate $\tfrac12$. (C) The regula falsi method has order of convergence $\tfrac{1+\sqrt5}{2}$ for every $C^2$ function with a simple root. (D) Fixed-point iteration $x_{n+1}=g(x_n)$ with $g\in C^1$, $g(\alpha)=\alpha$ and $|g'(\alpha)|\gt1$ converges to $\alpha$ for no $x_0$ near $\alpha$, other than $x_0=\alpha$ and points whose iterates land exactly on $\alpha$.

(A) True Theorem 9.11: $e_{n+1}/e_n^2\to f''(\alpha)/(2f'(\alpha))$ — order $2$, or higher if $f''(\alpha)=0$.
(B) True $0$ is a double root ($m=2$, $h(x)=x-1$, $h(0)\ne0$), so Theorem 9.13 gives linear convergence with rate $\tfrac12$. (Directly: $g(x)=x-\frac{x^2(x-1)}{3x^2-2x}=\frac{2x^2-x}{3x-2}$, $g'(0)=\tfrac12$.)
(C) False Regula falsi keeps a bracket; for $f$ with $f''$ of constant sign an endpoint stays fixed and the convergence is only linear (Theorem 9.14(b)). The order $1.618$ belongs to the secant method.
(D) True Theorem 9.10(2): near $\alpha$, $|e_{n+1}|\ge K|e_n|$ with $K\gt1$, so the error grows while the iterates remain near $\alpha$.
Answer (A), (B) and (D).

E5. GATE MA · NAT The secant method is applied to $x^2-2=0$ with $x_0=1$ and $x_1=2$. The value of $x_3$ is ______ (correct to two decimal places).

Step 1 $f(1)=-1$, $f(2)=2$: $x_2=2-2\cdot\frac{2-1}{2-(-1)}=\tfrac43$.
Step 2 $f\left(\tfrac43\right)=\tfrac{16}9-2=-\tfrac29$: $x_3=\tfrac43-\left(-\tfrac29\right)\frac{\tfrac43-2}{-\tfrac29-2}$ $=\tfrac43-\frac{4/27}{-20/9}$ $=\tfrac43+\tfrac1{15}=\tfrac{21}{15}=1.4$.
Answer $1.40$ (accept $1.39$ to $1.41$).

E6. GATE MA · NAT For $A=\begin{pmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{pmatrix}$, the spectral radius of the Gauss–Seidel iteration matrix is ______ (correct to two decimal places).

Jacobi first $T_J=\tfrac12\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}$, characteristic polynomial $\lambda^3-\tfrac12\lambda$: eigenvalues $0,\pm\tfrac1{\sqrt2}$.
Tridiagonal By Theorem 9.7(3), $\rho(T_{GS})=\rho(T_J)^2=\tfrac12$. (Directly: $T_{GS}=\begin{pmatrix}0&\frac12&0\\0&\frac14&\frac12\\0&\frac18&\frac14\end{pmatrix}$, eigenvalues $0,0,\tfrac12$.)
Answer $0.50$ (accept $0.49$ to $0.51$).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Direct methods. Definition 9.1 and Example 1 on the board (let the class discover that $a_{11}=0$ blocks naive elimination). Theorem 9.1 via "leading minors do not change"; Theorem 9.2 with the $n=3$ check. Definition 9.2, Theorem 9.3 (multipliers become $L$), Example 2; Theorem 9.4 and Example 3 as a positive-definiteness test. Pitfall 2 (the $4$-digit system) as a two-minute demonstration.
  2. Iterative methods. Definition 9.3, Example 4 (students compute in pairs: one Jacobi, one Gauss–Seidel). Theorem 9.5 with the eigenvector argument; Theorem 9.6 with the max-component proof. Project Interactive 2: tridiagonal family from $d=1$ to $d=4$ (both cross $\rho=1$ at $d=\sqrt2$; Gauss–Seidel's line is twice as steep), then the second family between $d=1$ and $d=2$, then the "Jacobi wins" matrix. Example 5, Theorem 9.7(3) proof, GATE corner E3 and E6 live.
  3. Nonlinear equations. Definition 9.5 (digits added versus multiplied), bisection and Theorem 9.8, Theorems 9.9–9.10, Example 6 (ask the class to predict each $g$ before computing). Newton: Theorem 9.11 proof, Theorems 9.12–9.13, Example 7; secant and Theorem 9.14. Interactive 1: Newton on $\cos x-x$, then the double root, then $\arctan$ with $x_0$ beyond $1.39$. E2 and E4 live.

Discussion questions. (1) Elimination costs $\tfrac23n^3$; an iterative method costs one multiplication by $A$ per step. For a $10^6\times10^6$ matrix with five nonzeros per row, roughly how many iterations could you afford for the price of elimination? (2) Why does the Gauss–Seidel proof of Theorem 9.6 need the component of largest modulus? (3) Bisection always works but is slow; Newton is fast but can fail. Design a hybrid that keeps a bracket and takes Newton steps when they stay inside it.

Misconceptions to watch for. Treating diagonal dominance as necessary; believing Gauss–Seidel always beats Jacobi; confusing the splitting $L+D+U$ with the LU factors; thinking a symmetric matrix with positive diagonal is positive definite; mixing up bracket length and midpoint error in bisection counts; claiming Newton is quadratic at every root; calling regula falsi superlinear; stopping on a small residual near a multiple root.

Suggested homework. I(1, 2, 3, 6), II(2, 3, 5, 7), III(1, 3, 4, 6, 8, 9), IV(1, 3, 5, 6); GATE corner E1, E3, E5.

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

Research question. How many iterations do Jacobi, Gauss–Seidel and over-relaxation need to compute the steady temperature in a heated metal plate, and how does that number grow as the grid is refined?

Why it matters. Steady heat flow, electrostatic potentials, groundwater pressure and the pressure step of weather and ocean models all reduce to Laplace's or Poisson's equation, discretised on a grid into a huge sparse linear system — the classic home of iterative methods. On a square with $N\times N$ interior grid points and spacing $h=\tfrac1{N+1}$, the five-point scheme gives a matrix for which $\rho(T_J)=\cos(\pi h)$ and, the matrix being consistently ordered, $\rho(T_{GS})=\cos^2(\pi h)$ — the analogue of Theorem 9.7(3).

What to do.

  1. Set up the plate: the unknown $u_{ij}$ at interior points satisfies $4u_{ij}-u_{i-1,j}-u_{i+1,j}-u_{i,j-1}-u_{i,j+1}=0$, with boundary values $100$ on the top edge and $0$ on the other three (a plate held at $100^\circ\mathrm{C}$ along one side).
  2. Write Jacobi and Gauss–Seidel sweeps that update the grid in place (no matrix needs to be stored). For $N=10$, $20$, $40$ count the sweeps needed to reduce the maximum change per sweep below $10^{-6}$.
  3. Compare your counts with the prediction $k\approx\dfrac{6\ln10}{-\ln\rho}$, and verify that the counts grow roughly like $N^2$.
  4. Add over-relaxation: $u\leftarrow u+\omega(u_{GS}-u)$ with $\omega=\dfrac{2}{1+\sin(\pi h)}$. How do the counts grow now?

Tools: Python with numpy (a double loop is enough), or a spreadsheet for $N=10$.

Hand in: a table of iteration counts for the three methods and three grids, a contour plot of the temperature, and a paragraph explaining why refining the grid makes plain Jacobi and Gauss–Seidel slow.

Going further. Read about multigrid methods, which reduce the error at a rate independent of $h$ by working on a hierarchy of grids, and about the conjugate gradient method for symmetric positive definite systems.

Instructor note: the predicted counts for an error reduction of $10^{-6}$ are, for $N=10$: Jacobi about $334$, Gauss–Seidel about $167$, optimal SOR ($\omega\approx1.560$, $\rho=\omega-1\approx0.560$) about $24$; for $N=20$: about $1230$, $615$ and $46$ ($\omega\approx1.741$); for $N=40$: about $4700$, $2350$ and $90$ ($\omega\approx1.858$). Counts measured with a stopping test on the change per sweep come out somewhat smaller than these error-based predictions, but the growth — like $N^2$ for Jacobi and Gauss–Seidel and like $N$ for SOR — is clearly visible.

🧪 Self-check quiz

0/5 correct

Q1. Near a simple root $\alpha$ of a $C^2$ function with $f''(\alpha)\ne0$, Newton's method converges with order

Q2. If $A$ is strictly diagonally dominant by rows, then for every $b$ and every starting vector

Q3. A real symmetric matrix has a Cholesky factorisation $LL^{\mathsf T}$ (positive diagonal) if and only if it is

Q4. The least number of bisection steps on $[0,1]$ that guarantees a bracket of length at most $10^{-3}$ is

Q5. Newton's method applied to $f(x)=(x-2)^3$ from $x_0=3$ gives