Computer Science › Algorithms & Software
Where numerical error comes from: truncating an infinite process, rounding to finite precision, and how both propagate through a computation, with absolute and relative error and loss of significance.
The conditioning of a problem versus the stability of an algorithm, forward and backward error, and why a well-conditioned problem can still be ruined by an unstable formula.
Bisection as a numerical method: the bracketing guarantee from the Intermediate Value Theorem, linear convergence, the exact iteration count for a tolerance, and stopping criteria.
Fixed-point iteration, the contraction condition on the derivative that decides convergence, and how rewriting the same equation changes the outcome.
Newton's method derived from the tangent line, quadratic convergence near a simple root, and how it fails: poor starting points, vanishing derivatives, and multiple roots.
The secant method as Newton without a derivative, the formal definition of order of convergence, and how the secant method's order is derived.
LU decomposition as Gaussian elimination with its multipliers recorded, why partial pivoting is required for stability, PA = LU, and reusing the factors across right-hand sides. This pivoting is not the simplex pivot, and the lesson says so.
Jacobi and Gauss-Seidel iterations for large sparse systems, the diagonal dominance and spectral radius conditions for convergence, and when iteration beats factorization.
The condition number of a matrix, how it bounds the amplification of relative error in Ax = b, and the Hilbert matrix as the classic ill-conditioned case.
The Lagrange and Newton forms of the same interpolating polynomial, divided differences, the interpolation error formula, and Runge's phenomenon.
Piecewise interpolation with linear and cubic splines, the continuity conditions, natural and clamped boundaries, and why splines avoid Runge's oscillation.
Fitting curves by least squares from the numerical side: normal equations versus QR, conditioning, and the choice of basis, building on the linear algebra lesson instead of repeating it.
The composite trapezoid and Simpson rules derived from interpolation, with their error terms worked on integrals that have known exact values.
The order of a quadrature rule, Richardson extrapolation, and adaptive quadrature that refines only where the error estimate demands it.
Euler's method for initial-value problems, local truncation error versus global error, the effect of step size, and a first look at stability.
Second-order and classical fourth-order Runge-Kutta methods, how they gain order without derivatives of the right-hand side, and adaptive step size.
A decision guide for the whole discipline: given a problem's size, smoothness, and conditioning, choose a method and diagnose why it failed.
Part of the Computer Science curriculum.
Where numerical error comes from: truncating an infinite process, rounding to finite precision, and how both propagate through a computation, with absolute and relative error and loss of significance.
The conditioning of a problem versus the stability of an algorithm, forward and backward error, and why a well-conditioned problem can still be ruined by an unstable formula.
Bisection as a numerical method: the bracketing guarantee from the Intermediate Value Theorem, linear convergence, the exact iteration count for a tolerance, and stopping criteria.
Fixed-point iteration, the contraction condition on the derivative that decides convergence, and how rewriting the same equation changes the outcome.
Newton's method derived from the tangent line, quadratic convergence near a simple root, and how it fails: poor starting points, vanishing derivatives, and multiple roots.
The secant method as Newton without a derivative, the formal definition of order of convergence, and how the secant method's order is derived.
LU decomposition as Gaussian elimination with its multipliers recorded, why partial pivoting is required for stability, PA = LU, and reusing the factors across right-hand sides. This pivoting is not the simplex pivot, and the lesson says so.
Jacobi and Gauss-Seidel iterations for large sparse systems, the diagonal dominance and spectral radius conditions for convergence, and when iteration beats factorization.
The condition number of a matrix, how it bounds the amplification of relative error in Ax = b, and the Hilbert matrix as the classic ill-conditioned case.
The Lagrange and Newton forms of the same interpolating polynomial, divided differences, the interpolation error formula, and Runge's phenomenon.
Piecewise interpolation with linear and cubic splines, the continuity conditions, natural and clamped boundaries, and why splines avoid Runge's oscillation.
Fitting curves by least squares from the numerical side: normal equations versus QR, conditioning, and the choice of basis, building on the linear algebra lesson instead of repeating it.
The composite trapezoid and Simpson rules derived from interpolation, with their error terms worked on integrals that have known exact values.
The order of a quadrature rule, Richardson extrapolation, and adaptive quadrature that refines only where the error estimate demands it.
Euler's method for initial-value problems, local truncation error versus global error, the effect of step size, and a first look at stability.
Second-order and classical fourth-order Runge-Kutta methods, how they gain order without derivatives of the right-hand side, and adaptive step size.
A decision guide for the whole discipline: given a problem's size, smoothness, and conditioning, choose a method and diagnose why it failed.