Chapter 5 · Introduction

Chapter 5 — Numerical Analysis

How to compute what cannot be written down: roots of equations, solutions of large linear systems, interpolating polynomials, integrals and solutions of differential equations — and how to know how accurate, how fast and how reliable each method is.

A clay tablet from Babylon, nearly four thousand years old, gives $\sqrt2$ as $1;24,51,10$ in base sixty — accurate to about one part in two million — a value that can be reached by repeatedly averaging a guess $x$ with $2/x$. In 1669 Newton improved approximate roots of $x^3-2x-5=0$ by linearising the equation at each guess; Raphson streamlined the procedure in 1690. Around 1810 Gauss computed the orbit of the asteroid Pallas by eliminating unknowns from a system of linear equations, and in the 1820s he was solving such systems by an iteration that Seidel described in print in 1874. Newton and Gauss also left us interpolation formulas and quadrature rules that are still taught under their names. None of these ideas was new mathematics in the sense of new theorems about numbers; all of them were new answers to a practical question: when an exact formula is unavailable, how do we compute an answer we can trust?

Numerical analysis is the mathematics of that question. Every method in this chapter replaces an exact problem by a computable one — a curve by its tangent, a matrix by its triangular factors, a function by a polynomial, an integral by a weighted sum, a differential equation by a step-by-step recursion — and then asks three things. Does it converge (and under which hypotheses)? How fast — what is the order of convergence or of the truncation error? How reliable is it when the data are slightly wrong or the arithmetic is rounded? The answers are theorems, with proofs that use nothing more than the mean value theorem, Taylor's theorem and a little linear algebra. Today the same questions sit inside every weather forecast, every crash simulation and every satellite navigation receiver.

f(x) = 0→Bisection · regula falsi→x = g(x), |g′(α)| < 1→Newton: order 2 · secant: 1.618→Ax = b: PA = LU→Jacobi · Gauss–Seidel: ρ(T) < 1→Δ, ∇, E · interpolation→Trapezoidal · Simpson · Gauss→Euler · Heun · RK4
🎯 By the end of this chapter you can…
  • locate roots and solve $f(x)=0$ by bisection, regula falsi, fixed-point iteration, Newton–Raphson and the secant method; decide convergence from $|g'(\alpha)|$, find the order of convergence (including Newton at multiple roots and the secant order $\tfrac{1+\sqrt5}{2}$), and count the bisection steps for a given accuracy;
  • solve linear systems by Gauss elimination with partial pivoting, compute Doolittle, Crout and Cholesky factorisations and operation counts, decide whether the Jacobi and Gauss–Seidel iterations converge (diagonal dominance, spectral radius), and estimate errors with the condition number;
  • use the operators $\Delta,\nabla,E$, Newton's forward and backward formulas, Lagrange and divided-difference interpolation with the error term, Hermite interpolation and natural cubic splines, and explain Runge's phenomenon;
  • derive difference formulas for derivatives and the trapezoidal, Simpson and Gauss–Legendre rules with their error terms and degree of precision, and accelerate them by Richardson extrapolation and Romberg integration;
  • solve initial value problems by Picard's method, Taylor series, Euler, modified Euler and Runge–Kutta methods, and relate local and global truncation error, order and absolute stability.
Teaser — The Root-Finding Race: Digits Added versus Digits Multiplied

Four methods hunt the same root. The graph shows the number of correct decimal digits, $-\log_{10}|x_n-\alpha|$, after $n$ steps. Bisection and fixed-point iteration add a roughly constant number of digits per step (straight lines: linear convergence); the secant method and Newton's method multiply the number of digits (curves that shoot up: order $1.618$ and $2$). Then pick the double root and watch Newton lose its advantage. Section 5.1 explains every curve.

6
steps n—
bisection—
fixed point—
secant—
Newton—

How this is examined

Numerical analysis is one of the most predictable parts of the CSIR NET Unit 3 syllabus, and its Part B questions are largely computational. Expect to be asked for the number of bisection steps that guarantees a given accuracy; for the value of a Newton or secant iterate after one or two steps; for the order of convergence of a given iteration or of Newton's method at a double root; for a condition on $g$ that makes $x=g(x)$ converge; for an entry of an LU factor, a pivot or a determinant obtained by elimination; for the spectral radius of a Jacobi or Gauss–Seidel iteration matrix of a $2\times2$ or $3\times3$ matrix; for a forward difference, an interpolating polynomial or a divided difference; for the value of a trapezoidal, Simpson or Gauss–Legendre approximation, or the degree of precision of a quadrature rule; and for one step of Euler, modified Euler or Runge–Kutta. Part C, where several options may be correct, tests the theorems behind the recipes: whether an iteration converges for every starting value, whether Jacobi convergence implies Gauss–Seidel convergence, which quadrature rules are exact for cubics, how the error of a composite rule scales with $h$, which methods are stable for a given step. The wrong options are nearly always one of the counterexamples collected in the ⚠️ boxes of the five sections. GATE MA asks very similar questions, often with numerical answers.

Sections in this chapter

5.1

Roots of Equations and Rates of Convergence

Bisection and regula falsi, fixed-point iteration and contractions, Newton–Raphson (quadratic at simple roots, linear at multiple roots, the modified method), the secant method, order of convergence and efficiency, failures, and Newton's method for systems.

$e_{n+1}\approx\dfrac{f''(\alpha)}{2f'(\alpha)}\,e_n^2$
Open section →
5.2

Linear Systems: Gauss Elimination and Gauss–Seidel

Gauss elimination with partial pivoting and its operation count, LU (Doolittle, Crout) and Cholesky factorisations, Jacobi and Gauss–Seidel iterations, diagonal dominance and the spectral radius, SOR, and the condition number.

$x^{(k+1)}=Tx^{(k)}+c$ converges $\iff\rho(T)\lt1$
Open section →
5.3

Finite Differences and Interpolation

Forward, backward and central differences, the shift operator, Newton's interpolation formulas, Lagrange interpolation and its error, divided differences, Hermite interpolation, cubic splines and Runge's phenomenon.

$\Delta=E-1,\quad \Delta^n x^n=n!\,h^n$
Open section →
5.4

Numerical Differentiation and Integration

Difference formulas for derivatives, the trapezoidal and Simpson rules with their error terms, degree of precision, Newton–Cotes and Gauss–Legendre quadrature, Richardson extrapolation and Romberg integration.

$\int_a^b f\approx\tfrac h3\left(y_0+4y_1+y_2\right)$
Open section →
5.5

Numerical Solution of ODEs

Picard's successive approximations, the Taylor series method, Euler, modified Euler and Runge–Kutta methods, local and global truncation error, order, absolute stability, and systems of equations.

$y_{n+1}=y_n+\tfrac h6(k_1+2k_2+2k_3+k_4)$
Open section →
✅ Before you start

From the CSIR NET Unit 1 course you need: the intermediate value theorem, the mean value theorem and Taylor's theorem with the Lagrange form of the remainder (they drive every error estimate in this chapter); sequences, Cauchy sequences and the contraction mapping principle; and, from linear algebra, determinants, eigenvalues and the Jordan form, positive definite matrices and Sylvester's criterion, and vector and matrix norms. From this course, the Lipschitz condition and Picard's successive approximations of §1.1 (fixed-point iteration is their one-dimensional cousin, and Picard's method returns in §5.5), and systems of first-order equations from §1.3 for the numerical solution of systems. Linear constant-coefficient difference equations, which describe the error of many iterations, behave exactly like the linear ODEs of §2.1 with characteristic roots replaced by powers. If this is your first visit, the welcome page explains how each section is organised.