Numerical Analysis and Scientific Computing

Algorithms, approximation error and when to trust a computed answer

About this course

Numerical algorithms and their error — root finding, linear systems and least squares, interpolation and splines, differentiation and quadrature, differential equations, eigenvalues and optimization, ending with a reproducible computation.

What you will be able to do

  • Apply bisection, Newton and secant methods and compare their convergence
  • Solve linear systems with pivoting and assess conditioning and least-squares fits
  • Build polynomial and spline interpolants and explain their limits
  • Control error in numerical differentiation and quadrature
  • Choose a stable ODE solver and step size for stiff and boundary-value problems

What this course covers

  • Gaussian elimination as reversible row operations
  • Partial pivoting and multiplier magnitude control
  • PA = LU factorization and reusable solver
  • Forward and back substitution as dependency traversal
  • Element growth: bounded multipliers do not cap U entries
  • Operation count: cubic factorization, quadratic solves
  • Verification checklist and limits of each check
  • Existence and Uniqueness of Interpolating Polynomial
  • Runge Phenomenon and Limits of Node-Fit as Accuracy Proof
  • Lagrange Cardinal Basis and Partition of Unity
  • Newton Divided Differences and Incremental Construction
  • Lebesgue Function and Data Amplification
  • Interpolation Remainder Formula
  • Finite Representation and Rounding
  • Failure of Associativity in Finite Arithmetic
  • The Four-Layer Trust Certificate
  • Conditioning: Problem Sensitivity to Input Perturbations
  • Catastrophic Cancellation and Stable Reformulation
  • Residuals vs. Forward Error in Linear Systems
  • Full Trust Certificate and Provenance
  • Power Iteration and Spectral Amplification
  • Rayleigh Quotient and Residual as Eigenpair Certificate
  • Shifting and Inverse Iteration for Targeted Eigenvalues
  • Orthogonalization for Multiple Eigenvectors
  • Convergence Factors and Operation Counts
  • Reliable Spectral Workflow and Stopping Criteria
  • Compact Spectral Certificate as the Capstone Result
  • Initial Value Problems and One-Step Methods
  • Euler's Method: Derivation and Geometric Meaning
  • Local Truncation Error vs. Global Error
  • Runge-Kutta Stage Construction
  • Butcher Tableau and Stage Auditing
  • Order of Accuracy via Refinement Ratios
  • Embedded Comparison and Accuracy Estimation
  • IVP Accuracy Certificate and Common Misconceptions
  • Roots, brackets, and iterates as distinct objects
  • A bracket as a theorem with data (IVT foundation)
  • Bisection invariant and correctness argument
  • A priori iteration budget via width halving
  • Stopping rules and their distinct certificates
  • Finite arithmetic stagnation of the midpoint
  • Complete bisection certificate and closing synthesis
  • Descent direction and curvature-safe step length
  • Derivative verification as a prerequisite
  • Exact steepest descent and successive gradient orthogonality
  • Conditioning, preconditioning, and zigzag geometry
  • Sufficient decrease and Armijo backtracking
  • Stopping evidence and false-stop diagnosis
  • Complete descent certificate and reproducibility record
  • Residual vs. forward error distinction
  • Same residual, different forward error: worked contrast
  • Condition number as worst-case relative amplification
  • Attaining the condition bound in a chosen direction
  • Estimating conditioning through probe solves
  • Iterative refinement using stored factorization
  • Complete conditioning and refinement audit
  • Stability functions and amplification factors
  • Separating consistency, stability, and accuracy
  • Absolute stability regions and step-size constraints
  • Stiffness as a timescale mismatch
  • A-stability vs L-stability: the stiff damping limit
  • Step-selection certificate for stiff systems
  • Correcting common stability misconceptions
  • Piecewise polynomials and the continuity ledger
  • Constraint counting and the two boundary freedoms
  • Moment parameterization and the tridiagonal system
  • Boundary sensitivity: natural vs. clamped splines on X³ data
  • Least squares as orthogonal projection
  • Derivation of the normal equations
  • Verification in original coordinates
  • Numerical danger of forming A^T A
  • QR factorization via Householder reflections
  • Rank deficiency: fitted vector vs. coefficient uniqueness
  • Reliable least squares workflow and certificate
  • Stopping Certificates and the Algorithm-vs-Solver Distinction
  • Newton's Method: Derivation and Quadratic Convergence
  • Newton's Method Failure: Two-Cycle on a Smooth Polynomial
  • The Secant Method: Derivation and Super-Linear Convergence
  • Safeguarding: Combining a Bracket with Fast Proposals
  • Residual, Error, and Sensitivity: Converting Evidence to Bounds
  • Hierarchy of Failure Modes and Solver Design Principles
  • Anatomy of a Precise Scientific Claim
  • Constructed BVP and Its Exact Solution
  • Source Identity via Canonical Specification and Fingerprinting
  • Four-Stage Verification Pipeline and Its Failure Modes
  • Boundary value problems vs. initial value marching
  • Finite difference discretization of the BVP
  • Distinguishing truncation, algebraic residual, and nodal error
  • Second-order convergence under mesh refinement
  • Discrete maximum principle and matrix sign structure
  • Five-point stencil and sparsity in two dimensions
  • Layered validation workflow and evidence hierarchy
  • Sources of error in numerical differentiation
  • Stencil design via Taylor moment cancellation
  • Optimal step size and the error bowl
  • Absolute weight norm and value-error propagation
  • Richardson extrapolation
  • Non-smoothness and the absolute-value counterexample
  • Differentiation certificate and corrected misconceptions
  • Degree of exactness and its boundary
  • Quadrature rules as exactness contracts
  • Composite rules and fourth-order convergence
  • Richardson extrapolation and the divide-by-fifteen estimator
  • Adaptive quadrature and the partition tree
  • Cancellation and local versus global error control
  • Reliable quadrature workflow and verification habits

Syllabus

  1. Error and Root Finding

    1. L1 · What Makes a Numerical Answer Trustworthy
    2. L2 · Bisection and the Logic of Bracketing
    3. L3 · Newton and Secant Methods

  2. Linear Systems and Least Squares

    1. L4 · Elimination, Pivoting and Linear Systems
    2. L5 · Conditioning and Iterative Refinement
    3. L6 · Least Squares and Orthogonal Factorization

  3. Interpolation, Differentiation and Quadrature

    1. L7 · Polynomial Interpolation and Its Limits
    2. L8 · Piecewise Polynomials and Splines
    3. L9 · Numerical Differentiation and Noise
    4. L10 · Quadrature and Error Control

  4. Differential Equations

    1. L11 · Initial-Value Problems and Runge–Kutta Methods
    2. L12 · Stability, Stiffness and Step Size
    3. L13 · Boundary-Value Problems and Finite Differences

  5. Eigenvalues, Optimization and Reproducibility

    1. L14 · Computing Eigenvalues and Eigenvectors
    2. L15 · Numerical Optimization and Descent
    3. L16 · A Reproducible Scientific Computation