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

• Floating-Point Numbers — IEEE 754 standard, normalized number representation
• IEEE 754 — Single and double precision details, special values (NaN, Inf)
• Machine Epsilon — Definition and computation of $\varepsilon_{\mathrm{mach}}$
• Significant Digits and Roundoff Error — How to count significant digits
• Absolute Error — Definition and properties of $|x - \hat{x}|$
• Relative Error — Definition and applications of $|x - \hat{x}|/|x|$
• Truncation Error — Errors from discretization and series truncation
• Roundoff Error — Errors arising from finite-precision representation

Computational Pitfalls

• Catastrophic Cancellation — Loss of significant digits when subtracting nearly equal values
• Loss of Significance — Small values ignored when added to large values
• Overflow and Underflow — Handling values beyond representable range
• Numerical Stability — Concepts of forward and backward stability

Root-Finding Methods for Nonlinear Equations

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

Interpolation and Approximation

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

Numerical Differentiation

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

Numerical Integration

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

Systems of Linear Equations

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

Norms

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

Numerical Methods for ODEs

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

Miscellaneous

• 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