Errors in numerical computing
Why every numerical solution is approximate, the two error families (round-off and truncation) and how to measure it: numerical, percentage and iterative error.
Syllabus
Complete numerical methods syllabus
Each topic groups its guides, derivations and exercises. Guides embed each method's full derivation; exercises are solved to the end.
Numerical foundations
Errors, significant figures, rounding, truncation, Taylor and order of approximation.
Interpolation
Newton, divided differences, Lagrange, Hermite, splines and error bounds.
Numerical differentiation
Forward, backward and central formulas, high accuracy and Richardson.
Numerical integration
Midpoint, trapezoid, Simpson, Newton-Cotes, Gauss-Legendre and multiple integration.
ODEs and initial value problems
Euler, Heun, Runge-Kutta, consistency, stability, convergence and first-order systems.
Multistep methods and stiffness
Adams-Bashforth, Adams-Moulton, predictor-corrector, implicit methods and stiff problems.
Linear systems
Residual, conditioning, Jacobi, Gauss-Seidel, spectral radius, convergence and SOR.
Nonlinear equations
Bisection, fixed point, Newton, secant, convergence order and high-order methods.
Nonlinear systems
Jacobian, Newton for systems, cost per iteration and high-order schemes.
Numerical foundations
Significant figures and round-off
How to count significant figures for numbers larger and smaller than 1 and in scientific notation, and where a machine's round-off errors come from.
Taylor and the truncation error
Taylor's theorem and its remainder, why the remainder is the truncation error, and how finite differences arise from it.
Derivation: finite differences from Taylor
How the truncated Taylor expansion yields the forward, backward and central finite differences of the first derivative.
Exercise: error of the sin x ≈ x approximation
Computing the numerical and percentage error when approximating by .
Exercise: iterative error with e^0.5
Approximating by its Taylor series, adding terms until the percentage iterative error drops below 0.05 %.
Exercise: Taylor of cos(x) up to order 3
Taylor series expansion of cos(x) around zero, taking terms up to order 3.
Interpolation
Interpolation: idea, existence and error
What interpolation is, why polynomials are used, the Weierstrass theorem, uniqueness of the interpolating polynomial and the error bound shared by Newton, Lagrange and Hermite.
Newton interpolation and divided differences
The Newton polynomial built in layers with divided differences: linear, quadratic and general form, the difference table, the error and a worked example with real data.
Lagrange interpolation
The Lagrange basis functions, the cardinal property that defines them, the polynomial as a direct combination of the data, its error and a worked example with the census data.
Hermite interpolation
Interpolation that imposes value and derivative at each node: the polynomial , its construction from the Lagrange bases, the error, the practical route via divided differences with repeated nodes and a Bessel-function example.
Cubic splines
Piecewise interpolation with one cubic per interval: the continuity conditions, the tridiagonal system that fixes the coefficients, natural splines and how to solve them.
Derivation: Newton coefficients via divided differences
Where and come from when forcing the polynomial through the points, and how the recursion generates every higher-order coefficient.
Derivation: Lagrange basis functions
How the requirement to equal 1 at one node and 0 at the others forces the product form of the functions.
Exercise: Hermite with the Bessel function
Full construction of the degree-5 Hermite polynomial with three nodes to approximate , step by step.
Exercise: Newton with population data
Full divided-difference table for the 1971–2011 census and estimate of the 2005 population with the degree-4 Newton polynomial.
Exercise: Lagrange with population data
Building the Lagrange basis functions for the 1971–2011 census and estimating the 2005 population, compared with Newton.
Numerical differentiation
Finite differences: the first derivative
Forward, backward and central formulas for the first derivative, their three- and five-point versions, the order of the error and a surprising numerical comparison.
Higher-order derivatives
Approximations of the second (and third) derivative by forward, backward and central finite differences, with their error order.
Richardson extrapolation
How to combine two approximations with steps and to cancel the dominant error term and raise the order, with the formulas for all terms and for even powers.
Derivation: three-point forward O(h²)
How to combine two Taylor expansions to eliminate the second derivative and get an order-2 forward difference for the first derivative.
Derivation: Richardson raises the order
From the error form to the extrapolation formula: why combining and removes the term.
Exercise: comparing derivative formulas
Computing for with the six finite-difference formulas and comparing their errors against the exact value .
Exercise: Richardson on ln(x)
Approximating for with forward differences and improving to via Richardson extrapolation.
Numerical integration
Numerical quadrature from Lagrange
The general idea of numerical integration: approximate an integral by a weighted sum of function values, obtained by integrating the Lagrange polynomial.
Closed Newton-Cotes: trapezoid, Simpson and more
Closed rules for equally spaced nodes that include the endpoints: trapezoid, Simpson 1/3, Simpson 3/8, Milne and their errors.
Open Newton-Cotes and midpoint
Open rules that avoid the endpoints of the interval, with special attention to the simple and composite midpoint rule.
Gaussian quadrature
How Gaussian quadrature chooses optimal nodes and weights using orthogonal polynomials: Legendre, Chebyshev, Laguerre and Hermite.
Numerical multiple integration
How trapezoid, Simpson and Gauss-Legendre extend to double integrals through product rules and changes of variables.
Derivation: trapezoid rule
Integrating the linear Lagrange interpolant on [a,b] to obtain the trapezoid rule and its geometric interpretation.
Derivation: composite trapezoid
From summing simple trapezoids on n subintervals to the weights 1,2,...,2,1 and the global error.
Derivation: simple midpoint
Replacing the function by a central height to obtain the centred rectangle rule and its error.
Derivation: composite midpoint
Generalising midpoint to n subintervals by using the centre of each block and summing local errors.
Derivation: Simpson 1/3
From three equally spaced nodes to Simpson's 1, 4, 1 weights by integrating the quadratic Lagrange polynomial.
Derivation: two-point Gauss-Legendre
How imposing exactness up to degree 3 gives the nodes and weights 1 on .
Exercise: trapezoid and Simpson on a smooth integral
Approximation of the integral of from 0 to with 4 and 8 subintervals, comparing errors.
Exercise: trapezoid and midpoint
Comparing composite trapezoid, simple midpoint and composite midpoint, with absolute and relative errors.
Exercise: work from tabulated data
Computing work by integrating F(x)cos(alpha(x)) from a table, using trapezoid, Simpson and midpoint.
Exercise: Gauss-Legendre on a general interval
Changing variables from [1,1.5] to [-1,1] and applying Gauss-Legendre with n=2 and n=3.
Exercise: Gauss-Chebyshev and an error bound
Determining how many nodes guarantee six decimals in an integral with Chebyshev weight.
Exercise: double integral with Gauss-Legendre
Transforming a rectangle to [-1,1]×[-1,1] and solving a double integral with n=m=3.
Exercise: double integral of a surface
Comparison between double Simpson and Gauss-Legendre for an integral derived from the hemisphere .
ODEs: initial value and multistep
Initial value problems
What an IVP is, when it has a unique solution (Lipschitz condition), how it is discretized, and how systems and higher-order equations reduce to the same scheme.
Euler's method
The simplest one-step method: advance with the slope at the current node. Full derivation along three routes (Taylor, incremental quotient and integration), order, a worked example and the implicit variant.
Heun's method
Averaging the initial slope and a predicted slope yields a second-order method. Full derivation via second-order Taylor and via the trapezoidal rule with an Euler prediction.
Runge-Kutta method (RK4)
The classical Runge-Kutta combines four slopes per step to reach order 4. Full derivation from Simpson's rule and direct extension to ODE systems.
Convergence, consistency and order
Local and global truncation errors, the definition of convergence and consistency, theoretical orders of the one-step methods and how to estimate the order numerically, with or without an exact solution.
Adams-Bashforth methods
Explicit multistep methods that integrate the ODE by approximating f with its interpolating polynomial over already-computed nodes: full derivation of AB2 with Lagrange, the AB3 and AB4 formulas, their order and how to start them.
Adams-Moulton methods
Implicit multistep methods that include the new node in the interpolation: full derivation of AM2 (implicit trapezoid), AM4, why they require solving a nonlinear equation and what they gain in exchange.
Predictor-corrector methods
Combining an explicit method (predictor) with an implicit one of the same order (corrector) to get the accuracy and stability of the implicit without solving equations: ABM2 and ABM4.
Stiff problems and stability
What makes an ODE stiff, why explicit methods become unstable with few points, and why implicit, low-order and adaptive-step methods are preferred.
Derivation: Euler's method and its order
Three independent routes lead to Euler's formula (Taylor, incremental quotient and integration), and the analysis of the Taylor remainder proves the method is first order.
Derivation: implicit Euler
Approximating the derivative at the new node with a backward difference produces the implicit Euler method and the nonlinear equation to solve at each step.
Derivation: Heun's method
Full derivation of Heun: via the Taylor expansion to second order combined with the two-variable Taylor of f, and via the trapezoidal rule with an Euler prediction.
Derivation: fourth-order Runge-Kutta
Applying Simpson's rule to the integral form of the IVP and approximating the unknown slopes with chained internal evaluations produces the classical RK4 and explains its 1, 2, 2, 1 weights.
Derivation: two-step Adams-Bashforth (AB2)
Full construction of AB2: integral form of the IVP, Lagrange interpolant of f at the two previous nodes, change of variable, integrals computed term by term, local error and generalization to AB3 and AB4.
Derivation: one-step Adams-Moulton (AM2)
Full construction of AM2: Lagrange interpolant including the new node, change of variable, computed 1/2-1/2 weights, connection with the trapezoidal rule and local error.
Exercise: Euler and RK4 by hand on a first-order ODE
Solve for y'=f(t,y) in an ODE given in implicit form and approximate y(3) with two Euler steps and one RK4 step, comparing both results.
Exercise: second-order ODE as a system, by hand
Reduce y''−sin y=0 to a first-order system and approximate y(3) with two Euler steps and one vector RK4 step.
Exercise: numerical order estimation (Euler, Heun, RK4)
On the same logistic IVP, Euler's order is estimated with the exact solution, Heun's by comparing successive meshes without an exact solution, and RK4's, confirming orders 1, 2 and 4.
Exercise: stability of explicit and implicit Euler
Full analysis of : the amplification factor of each method, the explicit method's stability condition , the unconditional stability of the implicit one and a numerical check with .
Exercise: the SIR model with Euler, Heun and RK4
Integration of the SIR epidemic system with the three one-step methods on the same mesh, comparing how the method's order visibly changes the results.
Exercise: AB2 and order estimation
Solving a logistic IVP (Verhulst) with AB2 started with Heun and estimating the order numerically by doubling the number of subintervals.
Exercise: explicit versus predictor-corrector
Comparing the maximum error of AB2, AB4 and the predictor-correctors ABM2 and ABM4 on the same Verhulst IVP.
Linear systems
Linear systems: error, residual and conditioning
Direct versus iterative methods for Ax=b, the difference between error and residual, the residual stopping criterion and why the condition number decides whether it is reliable.
Jacobi method
The splitting A=L+D+U, the choice M=D that defines Jacobi, its component-wise iterative scheme and a worked example.
Gauss-Seidel method
The choice M=D+L, which reuses each freshly computed component within the same iteration, and why it often converges faster than Jacobi.
Convergence and spectral radius
The condition that decides convergence, the sufficient strictly-diagonally-dominant criterion, and the convergence radius that measures speed.
Over-relaxation methods (SOR)
How a relaxation parameter ω speeds up the classical methods: relaxed Jacobi (JSOR) and SOR, which generalizes Gauss-Seidel (ω=1).
Derivation: Jacobi iteration matrix
From solving each unknown out of its equation to the matrix form x=−D⁻¹(L+U)x+D⁻¹b.
Exercise: Jacobi and Gauss-Seidel compared
Solving a 4×4 system with Jacobi and with Gauss-Seidel from x⁰=0, comparing how many iterations each needs for the same tolerance.
Exercise: convergence by spectral radius
A non-diagonally-dominant matrix where Jacobi diverges but Gauss-Seidel converges, decided by computing the spectral radius of each iteration matrix.
Nonlinear equations
Nonlinear equations: the problem and iterative methods
What solving means, why iterative methods are used, how they are classified (memory, points, derivatives) and which criteria stop the iteration.
Bisection method
The most robust method: halve the interval bracketing the root and keep the half where the sign changes. Explicit error bound and guaranteed convergence.
Fixed-point iteration
Rewrite as and iterate: when it converges (), how fast, and the theorem giving the method's order from which derivatives of vanish at the solution.
Newton-Raphson method
The reference iterative method: linearize f at the current iterate and jump to the tangent's root. Full derivation along three routes and proof of quadratic order with its error equation.
Derivative-free methods: secant and Steffensen
When is unavailable it is replaced by a divided difference: with two previous iterates (secant, order ) or with an auxiliary evaluation (Steffensen, order 2).
Convergence order and efficiency
Definition of convergence order and the error equation, their computational estimators COC and ACOC, the efficiency indices and the Kung-Traub conjecture defining optimal methods.
High-order methods: Halley, Traub, Ostrowski and Jarratt
Three techniques to design iterative methods faster than Newton: quadrature formulas, scheme composition (with frozen derivative) and weight functions, with the Chebyshev-Halley and King families.
Derivation: Newton-Raphson and its quadratic order
Newton's formula via the tangent line and via the Fundamental Theorem of Calculus, plus the complete Taylor proof that its error equation is quadratic.
Derivation: bisection error bound
Why the bisection error halves at every iteration, and how to predict in advance how many iterations a given tolerance requires.
Derivation: fixed-point convergence and order
Expanding by Taylor around the fixed point yields the method's error equation and proves both the criterion and the order theorem.
Exercise: bisection by hand
Six bisection iterations for cos²x−x=0 on [0,1], with the chain of intervals, the error bound at each step and the prediction of the required number of iterations.
Exercise: Newton on x=cos²x
Full application of Newton's method to x=cos²x from x0=0.3: table of iterates, residuals, increments and ACOC tending to the theoretical order 2.
Exercise: the secant by hand
The secant method applied to cos²x−x=0 from x0=0, x1=1: five iterations with explicit divided differences and superlinear convergence on display.
Exercise: numerical comparison of iterative methods
Newton, Halley, Ostrowski, Traub, midpoint, Jarratt and double Newton on test functions with tolerance 10⁻¹⁰⁰: iterations, residuals and ACOC confirming the theoretical orders.
Nonlinear systems
Systems of nonlinear equations
The problem in several variables: vector fixed-point methods, convergence order with norms, multidimensional ACOC and stopping criteria.
Newton for nonlinear systems
The vector version of Newton's method: the derivative becomes the Jacobian matrix, the quotient becomes one linear system per iteration, and the quadratic order is preserved.
Cost and efficiency in dimension n
Accounting of per-iteration cost in systems: evaluations per , per Jacobian, cost of the linear solves, efficiency indices and the multidimensional optimality conjecture.
High order in systems: Traub, Golden Ratio, NA, Jarratt and RN
Composition with Newton and frozen Jacobian: how to gain one order by composition without evaluating new Jacobians, and the Traub, Golden Ratio, NA, vector Jarratt and RN (order 5-6) families.
Derivation: Newton for systems by linearization
The first-order multivariate Taylor expansion linearizes F around the current iterate; setting that linearization to zero gives the Newton step, with the Jacobian in the role of the derivative.
Exercise: Newton for a system, by hand
Two Newton steps by hand on the system , : building the Jacobian, solving each step's linear system and visible quadratic convergence towards .
Exercise: Newton on a 2×2 system with iteration table
Full solution of , with Newton from : table of iterates, residual and increment norms, and ACOC settling at 2.
Exercise: numerical comparison on systems
Newton, Trapezoids, Golden Ratio, NA, Jarratt and RN on two test systems with tolerance 10⁻¹²: iterations, norms and ACOC, with RN (order 6) as the most effective method.