Numerical methods

前置知识

38 项必需的前置知识（一直追溯到底）

你将学会

• 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.

定义

• 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.

定理

• 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⁴).

常见误解

• Assuming that printing more digits means more accuracy.
• Expecting Newton's method to converge from every starting point.

通向

可选发现

• Optimisation Gradient descent and Newton's method for minimisation are close relatives of root-finding methods.
• ← Estimation and rounding
• ← Polynomials
• ← Introductory calculus

学习路径

• Applied mathematics

延伸阅读

• 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)