Numerical Analysis Basics

Fundamental Numerical Algorithms (Undergraduate Level)

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.

Learning Objectives

Understand the IEEE 754 floating-point number system
Solve equations using Newton's method and the secant method
Apply Lagrange interpolation and Newton interpolation
Compute numerical integrals using the trapezoidal rule and Simpson's rule
Understand the order of convergence of algorithms

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.

Visualization of Newton's Method — Figure 1: Newton's method applied to $f(x) = x^3 - 2x - 5$. Starting from $x_0 = 3.5$, tangent lines are drawn and their x-intercepts $x_1, x_2, \ldots$ converge rapidly to the root $x^*$.

Visualizing Spline Interpolation

Visualization of Spline Interpolation — Figure 2: Comparison of cubic spline interpolation (blue solid line) and linear interpolation (gray dashed line) through 6 data points (red circles). Spline interpolation connects cubic polynomials across each interval, producing a smooth curve.

Prerequisites

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