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.
Wiki
Search Numerical Methods
Type a method, property or formula. Search spans articles, exercises, derivations, comparisons and glossary terms.
129 results
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: 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.
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.
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.
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: 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: 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.
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: finite differences from Taylor
How the truncated Taylor expansion yields the forward, backward and central finite differences of the first derivative.
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.
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.
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 .
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.
Derivation: Jacobi iteration matrix
From solving each unknown out of its equation to the matrix form x=−D⁻¹(L+U)x+D⁻¹b.
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.
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: 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.
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.
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.
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 .
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.
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.
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.
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.
Consistency
A method is consistent if its local error tends to zero as the step size shrinks.
Stability
Control over how small errors are amplified during the computation.
Convergence
The property that approximations approach the target value.
Order
The asymptotic rate at which the error decreases.
Conditioning
Sensitivity of the exact problem to perturbations in the data.
Residual
The defect left after substituting an approximation into the original equation.
Truncation error
Error introduced by cutting off an expansion or replacing a continuous object with a discrete one.
Absolute and relative error
The two basic measures of the distance between an exact value and its approximation.
Rounding error
Error caused by representing and operating on numbers with finite precision.
Machine epsilon
The rounding unit of the floating-point system: the maximum relative error of representing a number.
Significant figures
The digits of an approximation that carry reliable information about the exact value.
Taylor polynomial
The local polynomial approximation of a function built from its derivatives at a point.
Nodes
The points of the domain where the function is known or evaluated.
Divided differences
The recursive coefficients that build the interpolating polynomial in Newton form.
Spline
A piecewise-polynomial interpolant with smoothness conditions at the joints.
Runge phenomenon
Growing oscillations near the endpoints when interpolating with high degree at equispaced nodes.
Quadrature
Approximating a definite integral by a weighted sum of function values.
Degree of precision
The highest polynomial degree that a quadrature formula integrates exactly.
Richardson extrapolation
Combining two approximations with different steps to cancel the leading error term.
Step size ($h$)
The distance between consecutive points of the discretization.
Explicit and implicit methods
The distinction between computing the new step directly or by solving an equation that contains it.
Stiffness
A property of an ODE that forces explicit methods to take tiny steps for stability.
Region of absolute stability
The set of values for which a method damps the test equation.
Fixed point
A value the iteration function leaves unchanged: .
Stopping criterion
The rule that decides when an iteration has reached sufficient accuracy.
Diagonally dominant matrix
A matrix in which each diagonal element dominates the sum of the rest of its row.
Spectral radius
The largest absolute value of a matrix's eigenvalues; it decides the convergence of linear iterations.
Jacobian matrix
The matrix of partial derivatives that generalizes to systems of several variables.
Vector and matrix norms
The size measures used to quantify errors and convergence in several dimensions.
Newton vs secant vs bisection
Three scalar root-finding strategies: global safety, local speed and per-iteration cost.
Euler vs Heun vs RK4
One-step IVP methods: accuracy, evaluations of and practical use.
Jacobi vs Gauss-Seidel vs SOR
Linear iterative methods viewed as splittings and through their iteration matrix.
Lagrange vs Newton vs Hermite vs splines
Four ways to interpolate the same data: what information they use, what they cost to build and when each one pays off.
Trapezoid vs Simpson vs midpoint vs Gauss
The everyday quadratures compared by nodes, composite error order and the situation where each wins.
AB2 vs AM2 vs predictor-corrector
The order-2 multistep methods head to head: cost per step, error constant and the price of implicit stability.
No results for that search. Try terms such as order, convergence, Jacobi or truncation.