Numerical Analysis Intermediate

Numerical Linear Algebra, Interpolation, Approximation, Quadrature, ODEs, Optimization, and Fourier Transforms (Upper Undergraduate Level — 68 Chapters)

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.

Learning Objectives

Understand and implement LU, Cholesky, QR, and SVD decompositions
Use iterative solvers (Jacobi, Gauss-Seidel, SOR, ILU) with preconditioning
Compute eigenvalues using the power method, inverse iteration, Jacobi rotation, and Wilkinson shifts
Apply Aitken, Neville, Hermite, spline, and Chebyshev interpolation
Distinguish Padé approximation, minimax (Remez), and least squares fitting
Use high-order quadrature methods such as Romberg, Richardson extrapolation, and Gauss-Legendre
Solve ODEs with Runge-Kutta, multistep, and implicit methods
Understand stiff ODEs and A-stability
Apply polynomial root finders, multivariate Newton, and Broyden's method
Use core optimization techniques (conjugate gradient, BFGS, L-BFGS)
Understand the discrete Fourier transform and circular convolution

Table of Contents (68 Chapters)

Part I — Computational Foundations

1. Kahan Summation — Compensated summation, Neumaier correction, error suppression

Part II — Linear Systems: Direct Methods

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

Part III — Linear Systems: Iterative Methods

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

Part IV — Eigenvalue Problems

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

Part V — Interpolation

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

Part VI — Function Approximation

32. Approximation Theory — Best approximation, $L^2$/$L^\infty$ norms, Remez exchange theorem
33. Chebyshev Approximation — DCT, power series economization, Clenshaw
34. Padé Approximation — Rational approximation, continued fractions
35. Minimax Approximation — Remez exchange theorem, optimal polynomials
36. Least Squares — Normal equations, QR-based solver
37. Total Least Squares — Errors-in-variables model, SVD-based solution

Part VII — Numerical Integration

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

Part VIII — Ordinary Differential Equations

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

Part IX — Nonlinear Equations

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

Part X — Optimization

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

Part XI — Fourier Transforms

67. Discrete Fourier Transform (DFT) — Definition, inverse, Parseval's theorem, twiddle factors
68. 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)