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.
Theory guides
Explanations with definitions, theorems, derivations and worked examples, topic by topic.
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.
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.
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.
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.
ODEs
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.
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).
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.
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.