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.
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$.
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. ∎
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$). ∎
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.
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$.
(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. ∎
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). ∎
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).
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)}$.
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\|)$. ∎
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$. ∎
- (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.
- 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.)
- 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.
- 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).
- Iterates: write each equation solved for its diagonal unknown first; in Gauss–Seidel overwrite as you go. Keep fractions for one or two steps.
- 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.
- 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.
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.)
(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]$.)
- 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$.
- If $|g'(\alpha)|\gt1$, no sequence of iterates converges to $\alpha$ (unless some $x_n$ equals $\alpha$ exactly).
- 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$. ∎
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.
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))$. ∎
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)$. ∎
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$. ∎
(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. ∎
- 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$.
- 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)$.
- 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.
- 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$.
- 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.
- 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)).
- 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.
- 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}$.
- 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.
- 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.
- Positive definite does not make Jacobi converge (same matrix: $\rho(T_J)=1.2$). It does make Gauss–Seidel converge.
- $\|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).
- 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$).
- 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$
- 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.
- 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.
- 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.
- CSIR Unit 3 · §5.1 Roots of Equations and Rates of Convergence — uniqueness of the order and the digits-per-step law, regula falsi for convex functions with the sticking endpoint, the full proof that the secant method has order $\tfrac{1+\sqrt5}2$ with its asymptotic constant, efficiency indices, and Newton's method for systems of equations.
- CSIR Unit 3 · §5.2 Linear Systems: Gauss Elimination and Gauss–Seidel — the elementary-matrix proof of $PA=LU$, the full proofs of the Ostrowski–Reich theorem and of the Jacobi criterion for positive definite matrices, successive over-relaxation (SOR) and Kahan's bound, and the condition number with perturbation bounds.
Two Labs
Exercises
- 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 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 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 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.
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$.
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$.
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.
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$.
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).
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).
Suggested plan — 3 lectures × 60 min.
- 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.
- 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.
- 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 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.
- 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).
- 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}$.
- Compare your counts with the prediction $k\approx\dfrac{6\ln10}{-\ln\rho}$, and verify that the counts grow roughly like $N^2$.
- 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.
🧪 Self-check quiz
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