Numerical Analysis Intermediate

Overview

This intermediate section covers numerical linear algebra (matrix decompositions, iterative solvers, eigenvalue problems), interpolation and function approximation, numerical integration, methods for ordinary differential equations, nonlinear equation solving, numerical optimization, and the discrete Fourier transform. The level corresponds to typical upper-undergraduate (junior/senior) numerical analysis courses and entry-level graduate study.

Table of Contents

Part I — Computational Foundations

• Kahan Summation — Compensated summation, Neumaier correction, error suppression

Part II — Linear Systems: Direct Methods

• LU Decomposition — $A = LU$ factorization, solving triangular systems
• Cholesky Decomposition — Symmetric positive-definite factorization, numerical stability
• LDL Decomposition — Square-root-free symmetric factorization, Bunch-Kaufman pivoting
• Householder Transformation — Reflections, QR construction, tridiagonalization
• Givens Rotation — Plane rotations for element zeroing, sparse QR
• QR Decomposition — Gram-Schmidt, Householder QR, Givens QR
• Singular Value Decomposition (SVD) — Low-rank approximation, PCA, image compression
• Thomas Algorithm — $O(n)$ solver for tridiagonal systems
• Band Matrix Solver — LU for bandwidth $p$, complexity $O(np^2)$
• Sparse Matrices — CSR/CSC storage formats, efficient operations
• Condition Number and Error Analysis — $\kappa(A)$, ill-conditioning, error propagation

Part III — Linear Systems: Iterative Methods

• Iterative Methods Overview — Convergence conditions, spectral radius, stopping criteria
• Jacobi Method — Diagonal dominance, parallelization, convergence analysis
• Gauss-Seidel Method — Sequential updates, faster convergence than Jacobi
• SOR Method — Successive over-relaxation, optimal $\omega$
• Incomplete LU Factorization (ILU) — Preconditioning, ILU(0)/ILUT, accelerating Krylov methods

Part IV — Eigenvalue Problems

• Eigenvalue Problems — Canonical forms, similarity transformations, sensitivity
• Power Method — Largest absolute eigenvalue, Rayleigh quotient
• Inverse Iteration — Shifted iteration, Rayleigh quotient iteration, cubic convergence
• Jacobi Rotation — Symmetric eigenvalues, quadratic convergence, all eigenpairs
• Wilkinson Shift — Optimal shift strategy for symmetric QR, cubic convergence

Part V — Interpolation

• Aitken Interpolation — Δ² process, convergence acceleration
• Neville's Algorithm — Recursive interpolation, tableau form
• Hermite Interpolation — Osculating polynomials, repeated nodes, derivative data
• Spline Interpolation Overview — Piecewise polynomials, smoothness, knots
• Cubic Spline — Natural, clamped, and not-a-knot boundary conditions
• B-Spline — Cox-de Boor recursion, knot vectors, NURBS
• Bernstein Polynomials — Weierstrass theorem, Bézier curves
• Chebyshev Interpolation — Avoiding the Runge phenomenon, barycentric form
• Clenshaw Recurrence — Backward recurrence, stable evaluation of orthogonal expansions

Part VI — Function Approximation

• Approximation Theory — Best approximation, $L^2$/$L^\infty$ norms, Remez exchange theorem
• Chebyshev Approximation — DCT, power series economization, Clenshaw
• Padé Approximation — Rational approximation, continued fractions
• Minimax Approximation — Remez exchange theorem, optimal polynomials
• Least Squares — Normal equations, QR-based solver
• Total Least Squares — Errors-in-variables model, SVD-based solution
• Savitzky-Golay Filter — Smoothing and derivative estimation via local polynomial least squares
• Zernike Polynomials — Orthogonal polynomials on the unit disk, optical wavefront decomposition

Part VII — Numerical Integration

• Boole's Rule — 5-point Newton-Cotes formula, degree-6 exactness
• Richardson Extrapolation — Error acceleration, $h \to 0$ asymptotic expansion
• Romberg Integration — Trapezoidal rule plus Richardson acceleration
• Legendre-Gauss Quadrature — Finite interval, exact to degree $2n - 1$
• Chebyshev Quadrature — Equal weights, Chebyshev nodes
• Hermite-Gauss Quadrature — Infinite interval, weight $e^{-x^2}$
• Gauss-Laguerre Quadrature — Semi-infinite interval, weight $e^{-x}$
• Radau Quadrature — Includes one endpoint
• Lobatto Quadrature — Includes both endpoints, Clenshaw-Curtis family

Part VIII — Ordinary Differential Equations

• Numerical Methods for ODEs — Improved Euler method, local truncation error
• Runge-Kutta Methods — RK4, Butcher tableau, embedded formulas, step-size control
• Linear Multistep Methods — Linear multistep, BDF, zero-stability
• Adams Methods — Adams-Bashforth, Adams-Moulton
• Predictor-Corrector Methods — PECE, Milne's method
• Implicit Euler Method — A-stable, L-stable, Newton iteration
• Trapezoidal Method (ODE) — Second-order accuracy, A-stable, Crank-Nicolson
• Stability Analysis and Stiff Equations — Absolute stability, A-stability, stiffness ratio, Dahlquist barrier

Part IX — Nonlinear Equations

• Polynomial Roots — Aberth-Ehrlich method, simultaneous iteration
• Sturm Sequences and Real-Root Counting — Sturm's theorem, sign changes
• Brent's Method — Hybrid of bisection and inverse quadratic interpolation
• Müller's Method — Quadratic interpolation, complex roots, quadratic convergence
• Halley's Method — Cubic convergence, Householder's higher-order iterations
• Multivariate Newton's Method — Jacobian matrix, quadratic convergence, globalization
• Broyden's Method — Quasi-Newton approximation, rank-1 update

Part X — Optimization (→ moved to the Optimization series)

Numerical optimization topics are consolidated in the dedicated "Optimization" series. To avoid duplication, this chapter links directly to those pages.

• Numerical Optimization Basics — Optimality conditions, steepest descent, rates of convergence
• Line Search — Golden-section, Armijo, Wolfe conditions
• Conjugate Gradient Method — Fletcher-Reeves, Polak-Ribière
• Quasi-Newton Methods — BFGS, DFP, L-BFGS
• Nonlinear Least Squares — Gauss-Newton, Levenberg-Marquardt

Part XI — Fourier Transforms

• Discrete Fourier Transform (DFT) — Definition, inverse, Parseval's theorem, twiddle factors
• Circular Convolution — Convolution theorem, overlap-add and overlap-save

Prerequisites

• Content from Numerical Analysis Basics
• Linear algebra (matrices, eigenvalues, vector spaces)
• Calculus and Taylor series
• Fundamentals of differential equations
• Complex numbers (DFT chapters only)

Related Sections and Next Steps

• Numerical Analysis Advanced — In-depth PDE/FEM/FFT, Krylov methods, Monte Carlo, inverse problems
• Numerical Analysis Basics — Review of foundational concepts
• Ordinary Differential Equations — Theoretical background for ODE chapters