Numerical Analysis

Units

1. 1

   Floating point and error

   2 lessons

   1. Floating-point numbersSay how a computer stores a real number as a sign, a significand and an exponent, find the gap between neighbouring floats, and explain why 0.1 + 0.2 ≠ 0.3.
   2. Error, cancellation and conditioningMeasure error as absolute and relative, explain catastrophic cancellation, and separate a problem's condition number from an algorithm's stability.
2. 2

   Solving nonlinear equations

   4 lessons

   1. BisectionFind a root of a continuous function by halving a bracketing interval, and use the bound (b − a)/2ⁿ to say how many steps a tolerance needs.
   2. Newton's methodFollow tangent lines to a root with xₙ₊₁ = xₙ − f(xₙ)/f′(xₙ), see the number of correct digits double each step, and say when the method fails.
   3. Fixed-point iterationRewrite f(x) = 0 as x = g(x), iterate xₙ₊₁ = g(xₙ), read the iteration as a cobweb, and say when it converges and how fast.
   4. The secant method and order of convergenceRun the secant method, which replaces f′ in Newton's step by a slope through the last two iterates, and estimate the order of convergence p of a method from a table of errors.
3. 3

   Interpolation

   4 lessons

   1. Polynomial interpolationExactly one polynomial of degree at most n passes through n + 1 points; the Lagrange form built from basis polynomials, and the Vandermonde system.
   2. Newton's divided differencesThe Newton form and its divided-difference table, adding a point without starting over, worked on four data points.
   3. Interpolation error and Runge's phenomenonThe error formula with the product of (x − xᵢ), the wild swings of equally spaced interpolation of 1/(1 + 25x²), and Chebyshev nodes that tame them.
   4. Cubic splinesPiecewise cubics matching values, slopes and curvature at the knots, natural end conditions, and the smooth curve compared with one high-degree polynomial.
4. 4

   Numerical differentiation and integration

   3 lessons

   1. Finite differencesForward and central difference quotients, truncation error O(h) and O(h²) from Taylor's theorem, and the step size that balances truncation against rounding on a log-log error plot.
   2. Trapezoid and Simpson's rulesComposite trapezoid and Simpson's rules, their error orders h² and h⁴, and Richardson extrapolation, with the panels drawn under the curve.
   3. Gaussian quadratureChoosing nodes as well as weights: the two-point Gauss rule at ±1/√3 is exact for cubics, compared with Simpson's rule on the same integrand.
5. 5

   Solving linear systems

   4 lessons

   1. Gaussian elimination with pivotingOperation count of about 2n³/3, the small-pivot disaster on a 2 × 2 system in limited precision, and partial pivoting that fixes it.
   2. LU and Cholesky factorizationsPA = LU from elimination, solving by forward and back substitution for many right-hand sides, and Cholesky A = LLᵀ for symmetric positive definite matrices.
   3. Norms and condition numbersVector and matrix norms, κ(A) = ‖A‖‖A⁻¹‖, and the bound on relative error in x from relative error in b, with a nearly singular system whose solution jumps.
   4. Iterative methodsJacobi and Gauss-Seidel iterations, convergence for diagonally dominant matrices, and the spectral radius of the iteration matrix, with error falling on a log plot.
6. 6

   Least squares computation

   2 lessons

   1. Least squares by QRWhy forming AᵀA squares the condition number, and solving Rx = Qᵀb from a QR factorization instead, worked on a line fit.
   2. Orthogonalization: Gram-Schmidt and HouseholderClassical and modified Gram-Schmidt lose orthogonality differently; a Householder reflection zeros a column below the diagonal, drawn as a mirror in the plane.
7. 7

   Computing eigenvalues

   3 lessons

   1. The power methodRepeated multiplication turns any start toward the dominant eigenvector at rate |λ₂/λ₁|, the Rayleigh quotient, and inverse iteration with a shift for other eigenvalues.
   2. The QR algorithmFactor A = QR, form RQ, repeat, and read the eigenvalues of a symmetric 2 × 2 matrix off the diagonal as the iterates become triangular.
   3. The singular value decomposition in practiceCompute the singular values of a small matrix, read the numerical rank from them, and build the best low-rank approximation with the Eckart-Young error.
8. 8

   Solving differential equations numerically

   2 lessons

   1. Euler and Runge-Kutta methodsStep y' = f(t, y) forward with Euler's method and the fourth-order Runge-Kutta method, and read their global errors O(h) and O(h⁴) from a step-size study on y' = y.
   2. Stability and stiff equationsFind the step sizes for which Euler's method is stable on y' = λy, recognise a stiff equation such as y' = −50(y − cos t), and use implicit Euler to take large stable steps.