Advanced undergraduateComputationPlanned
Numerical analysis
Numerical linear algebra (LU and QR factorisations, conditioning, least squares, eigenvalue algorithms), numerical solution of ODEs (Euler and Runge–Kutta methods, stiffness), and convergence and stability analysis.
math.comp.numerical-analysis
The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.
Builds on
Required prerequisites, all the way down: 41
You will learn to
- Solve linear systems by LU factorisation with partial pivoting and analyse their conditioning.
- Solve least-squares problems via QR factorisation and compute eigenvalues with the QR algorithm.
- Implement Euler and Runge–Kutta methods and analyse their order and stability, including for stiff problems.
Definition
- The condition number κ(A) = ‖A‖ ‖A⁻¹‖ measures how sensitive the solution of Ax = b is to perturbations of the data.
- An algorithm is backward stable if it computes the exact answer to a slightly perturbed problem.
- A one-step method for ODEs has order p if its global error is O(hᵖ) for step size h.
Theorem
- The relative error in the solution of Ax = b is bounded, to first order, by κ(A) times the relative error in the data.
- Gaussian elimination with partial pivoting is backward stable in practice, although its worst-case growth factor is 2ⁿ⁻¹.
- The classical Runge–Kutta method has order 4.
- Explicit methods applied to stiff problems need very small steps, whereas some implicit methods are A-stable.
Common misconceptions
- Computing A⁻¹ in order to solve Ax = b.
- Assuming a smaller step size always reduces the total error; rounding error eventually grows.
Optional discoveries
Learning pathways
Further reading
- Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra (1997)
- Endre Süli and David F. Mayers, An Introduction to Numerical Analysis (2003)