Early undergraduateComputationPlanned
Numerical methods
Floating-point arithmetic and rounding error, root finding by bisection and Newton's method, interpolation, numerical differentiation and integration, and error analysis and rates of convergence.
math.comp.numerical-methods
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: 38
You will learn to
- Explain floating-point representation, machine epsilon and catastrophic cancellation.
- Implement bisection and Newton's method and compare their rates of convergence.
- Implement the trapezoidal and Simpson's rules and estimate their errors.
Definition
- Machine epsilon is the gap between 1 and the next larger floating-point number.
- An iterative method converges with order p if its errors satisfy eₙ₊₁ ≈ C eₙᵖ for some constant C.
Theorem
- Newton's method converges quadratically to a simple root of a twice continuously differentiable function when started close enough to the root.
- Bisection halves the error bound at each step and always converges for a continuous function with a sign change.
- For smooth integrands, the composite trapezoidal rule has error O(h²) and the composite Simpson's rule O(h⁴).
Common misconceptions
- Assuming that printing more digits means more accuracy.
- Expecting Newton's method to converge from every starting point.
Leads to
Optional discoveries
- Optimisation Gradient descent and Newton's method for minimisation are close relatives of root-finding methods.
- ← Estimation and rounding
- ← Polynomials
- ← Introductory calculus
Learning pathways
Further reading
- Richard L. Burden and J. Douglas Faires, Numerical Analysis
- Endre Süli and David F. Mayers, An Introduction to Numerical Analysis (2003)
- Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms (1996)