Primeros años de universidadComputationPlanificado
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
La lección de este tema todavía no se ha escrito. El esquema siguiente forma parte del mapa del plan de estudios y no ha sido revisado.
Se basa en
Requisitos previos obligatorios, hasta el fondo: 38
Aprenderás a
- 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.
Definición
- 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.
Teorema
- 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⁴).
Errores frecuentes
- Assuming that printing more digits means more accuracy.
- Expecting Newton's method to converge from every starting point.
Conduce a
Descubrimientos opcionales
- Optimisation Gradient descent and Newton's method for minimisation are close relatives of root-finding methods.
- ← Estimation and rounding
- ← Polynomials
- ← Introductory calculus
Itinerarios de aprendizaje
Lecturas complementarias
- 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)