Chapter 9 — Numerical Analysis
When a problem has no formula for its answer — a large linear system, a transcendental equation, an integral without an elementary antiderivative, a differential equation — we compute: by elimination, by iteration, by replacing a function with a polynomial, by taking small steps. This chapter is about how those computations work and how fast their errors shrink.
A weather forecast, the trajectory of a spacecraft, the stress in a bridge, the price of an option, the dose curve of a new drug: behind each of them is a computer solving mathematical problems that have no closed-form answer. The equations are familiar — a linear system $Ax=b$ with a million unknowns, an equation such as $x=\cos x$, an integral such as $\int_0^1e^{-x^2}dx$, a differential equation $y'=f(x,y)$ — but no formula produces the answer. Numerical analysis is the mathematics of producing it anyway: designing algorithms that turn such problems into finitely many arithmetic operations, and, just as importantly, proving how accurate the result is and how fast the error shrinks as we work harder.
Almost every method in this chapter rests on one of two ideas. The first is iteration: start with a guess and improve it repeatedly — Jacobi and Gauss–Seidel sweeps for linear systems, bisection, fixed-point iteration, Newton's and the secant method for equations. Here the key questions are does it converge (a spectral radius below $1$, a derivative of modulus below $1$) and with what order (does each step add a fixed number of correct digits, or double them?). The second idea is local replacement by a polynomial: replace $f$ by the line or parabola through a few of its values, and differentiate or integrate that instead. This gives interpolation formulas, difference quotients, the trapezoidal and Simpson rules — and, applied step by step along a solution curve, Euler's and the Runge–Kutta methods. Here the key result is always an error formula with a power of the step $h$ and a derivative of $f$: halve the step and the error falls by $2^p$, where $p$ is the order of the method.
- solve linear systems by Gaussian elimination with partial pivoting, compute LU and Cholesky factorisations, and count their cost;
- carry out Jacobi and Gauss–Seidel iterations, and decide their convergence from diagonal dominance, positive definiteness or the spectral radius of the iteration matrix;
- apply bisection, fixed-point iteration, Newton–Raphson and the secant method, find the order of convergence of an iteration, and recognise what changes at a multiple root;
- construct interpolating polynomials in Lagrange and Newton form, use divided and finite differences, and bound the interpolation error;
- derive difference formulas for derivatives with their error terms, and apply the trapezoidal, Simpson 1/3 and 3/8 rules, simple and composite, with error bounds and degree of precision;
- solve initial value problems by Euler's method, the modified Euler method and second-order Runge–Kutta methods, and compare their local and global errors and their stability.
How this is examined
Numerical analysis is one of the most computation-heavy chapters of GATE MA, and it is well suited to the on-screen calculator. MCQs typically ask for an entry of an LU or Cholesky factor, an iterate of Jacobi or Gauss–Seidel, the order of convergence of a given iteration, the formula Newton's method produces for a square root or a reciprocal, the degree of precision of a quadrature rule, or the form of a Runge–Kutta step. MSQs test judgement about convergence and accuracy: whether Jacobi or Gauss–Seidel converges for a matrix with a parameter, which statements about Newton's method at simple and multiple roots are true, which rules are exact for which polynomials, how the error of a composite rule changes when the step is halved, or which step sizes keep Euler's method stable. NATs ask for a number to two or three decimal places: a Newton or secant iterate, a bisection count, an interpolated value from a table, a trapezoidal or Simpson estimate, the number of subintervals needed for a given accuracy, or one or two Euler or Runge–Kutta steps. The same material appears in IIT JAM and, with more emphasis on proofs of convergence, in CSIR NET Part C.
Sections in this chapter
Linear Systems and Nonlinear Equations
Gaussian elimination with partial pivoting, LU and Cholesky factorisations, the Jacobi and Gauss–Seidel iterations and their convergence; bisection, fixed-point iteration, Newton–Raphson and the secant method, with their orders of convergence.
Interpolation, Numerical Differentiation and Integration
Lagrange and Newton interpolation with the error formula, divided and finite differences, difference quotients for derivatives, and the trapezoidal, Simpson and Newton–Cotes rules with composite error terms and degree of precision.
Numerical Solution of Initial Value Problems
Euler's method, the modified Euler method and the second-order Runge–Kutta family, local and global truncation error, order of a method, and stability on the test equation $y'=\lambda y$.
The error analysis in this chapter uses one-variable calculus throughout: the intermediate value theorem, Rolle's theorem, the mean value theorem and Taylor's theorem with the Lagrange remainder. For linear systems you need matrix algebra, determinants and leading principal minors from §3.1, eigenvalues and the spectral radius from §3.2, and positive definite matrices from §3.3. Fixed-point iteration is the one-dimensional case of the contraction mapping principle of §4.1. Section 9.3 assumes the basic theory of first-order initial value problems from §6.1. If this is your first visit, the welcome page explains how each section and its 🎯 GATE corner are organised.