Numerical Analysis Basics

Overview

This section covers the fundamentals of numerical analysis typically taught in early undergraduate courses. Topics include how computers represent numbers (floating-point arithmetic), standard algorithms for solving equations, interpolation, and numerical integration.

Table of Contents

Error and Number Representation

• 1. Floating-Point Numbers — IEEE 754 standard, normalized number representation
• 2. IEEE 754 — Single and double precision details, special values (NaN, Inf)
• 3. Machine Epsilon — Definition and computation of $\varepsilon_{\mathrm{mach}}$
• 4. Overflow and Underflow — Handling values beyond representable range
• 5. Significant Digits and Roundoff Error — How to count significant digits
• 6. Absolute Error — Definition and properties of $|x - \hat{x}|$
• 7. Relative Error — Definition and applications of $|x - \hat{x}|/|x|$
• 8. Roundoff Error — Errors arising from finite-precision representation
• 9. Truncation Error — Errors from discretization and series truncation

Computational Pitfalls

• 10. Loss of Significance — Small values ignored when added to large values
• 11. Catastrophic Cancellation — Loss of significant digits when subtracting nearly equal values
• 12. Numerical Stability — Concepts of forward and backward stability

Root-Finding Methods for Nonlinear Equations

• 13. Bisection Method — The most basic root-finding method: reliable but slow
• 14. Regula Falsi (False Position Method) — Improving bisection with linear interpolation
• 15. Fixed-Point Iteration — Iteration of $x = g(x)$, contraction mapping theorem
• 16. Newton's Method — $x_{n+1} = x_n - f(x_n)/f'(x_n)$, quadratic convergence
• 17. Secant Method — Superlinear convergence without derivatives

Interpolation and Approximation

• 18. Horner's Method — Efficient polynomial evaluation algorithm
• 27. Interpolation (Overview) — Lagrange interpolation, Newton divided differences, interpolation error
• 28. Lagrange Interpolating Polynomial — Construction using basis polynomials
• 29. Divided Differences — Definition, properties, and recursive computation
• 30. Newton's Divided Difference Interpolation — Efficient computation via divided difference tables
• 31. Spline Interpolation — Piecewise polynomials, cubic splines

Numerical Differentiation

• 32. Forward Difference — $f'(x) \approx (f(x+h) - f(x))/h$
• 33. Backward Difference — $f'(x) \approx (f(x) - f(x-h))/h$
• 34. Central Difference — $f'(x) \approx (f(x+h) - f(x-h))/(2h)$, second-order accuracy

Numerical Integration

• 35. Numerical Integration (Overview) — Trapezoidal rule, Simpson's rule, composite formulas
• 36. Trapezoidal Rule — The most basic numerical integration method, $O(h^2)$
• 37. Simpson's Rule — $O(h^4)$ accuracy via quadratic interpolation
• 38. Newton-Cotes Formulas — General theory of quadrature formulas based on equally spaced nodes
• 39. Gaussian Quadrature — Optimal choice of quadrature points and weights

Systems of Linear Equations

• 21. Gaussian Elimination — Forward elimination and back substitution, with animated examples
• 22. Pivot Selection — Partial, complete, and rational pivoting
• 23. Forward Substitution — Solving lower triangular systems
• 24. Back Substitution — Solving upper triangular systems
• 25. Gauss-Jordan Elimination — Reduction to reduced row echelon form
• 26. Cramer's Rule — Solving linear systems using determinants

Norms

• 19. Vector Norms — 1-norm, 2-norm, $\infty$-norm
• 20. Matrix Norms — Frobenius norm, spectral norm

Numerical Methods for ODEs

• 40. Euler Method — Forward, backward, and improved Euler methods; stability analysis

Miscellaneous

• 41. Algorithm Complexity — Big-$O$ notation, time complexity, and space complexity

Visualizing Newton's Method

Newton's method rapidly approaches a root by following tangent lines.

Visualizing Spline Interpolation

Prerequisites

• Content from Numerical Analysis Introduction
• Fundamentals of calculus
• Knowledge of Taylor series

Reading

• Newton's Method: The Art of Clever Guessing [Reading] — Let yourself be fooled by the tangent line on purpose to build a better next guess. A relaxed look at why it is so blazingly fast, its intuition, and its pitfalls.
• Slow but Never Wrong: The Quiet Certainty of Bisection [Reading] — It is not the fastest. But once you know a root lies inside an interval, it corners the answer, halving with certainty at every step. A relaxed take on choosing sureness over speed, with a surprising link to number-guessing games.
• Why 0.1 + 0.2 Isn't 0.3: How Computers Stumble on Decimals [Reading] — Why can't a computer hold a simple decimal exactly? From the nature of binary to cancellation, and all the way to the Patriot missile and Ariane 5 failures, a casual tour through the mysteries of rounding error.