Overview: Root Finding and Quadrature - COMP 521: Introduction to Scientific Computing and Data Science

The Big Picture: Learning Equilibrium Through Mathematics¶

A motivating physical problem¶

Lagrange’s 1772 analysis identified five equilibrium configurations in the restricted three-body problem. A spacecraft near $L_2$ follows an orbit around that configuration rather than remaining at a static point; the calculation uses a model, a coordinate convention, and numerical solution procedures.

That example separates two tasks that recur in computational physics:

solve $f(x)=0$ for an equilibrium or event location;
approximate $\int_a^b f(x)\,dx$ for an accumulated quantity.

They use some shared ideas—contracts, convergence evidence, and sensitivity—but they are different numerical problems.

What this module provides¶

You’re about to discover that the cosmos is filled with equilibrium points and measurable quantities:

Where does a stellar model reach its surface? Root finding locates the boundary of a pressure-supported model
How much energy does a galaxy radiate? Integration across the spectrum
Where can spacecraft orbit with minimal fuel? Finding Lagrange points
What’s the total mass of a dark matter halo? Integrating density profiles

Root finding and quadrature recur in many models. Correct use depends on the regularity of the function, available information, required error measure, and the cost of evaluating the model.

Why the distinction matters¶

Examples include integrating a luminosity density, evaluating a transit flux, and solving an equilibrium condition. A library call does not remove the need to define a method’s inputs, assumptions, and verification test.

Choose your learning path¶

🏃 Fast Track¶

Essential concepts only

🚶 Standard Path¶

Full conceptual understanding

Everything in Fast Track, plus:

🧗 Complete Path¶

Deep dive with all details

Complete module including:

All mathematical derivations
Optional Monte Carlo integration
Gaussian quadrature
Richardson extrapolation
Root-finding investigation for Block 3
An integral inside a root problem, after both topics
All worked examples

Quick Jump to What You Need by Project

For Project 2 (numerical integration):

Reusable function contract and pytest
Composite rules and their orders
Adaptive Simpson’s rule
Substitution and endpoint behavior
Optional conceptual enrichment: Monte Carlo RMS error

For Project 3 (root finding and classes):

Method-selection rule

Do not choose a numerical method by its name or nominal order. State the quantity, the function contract or data model, the error measure, and a test. A result needs investigation when:

Their root finder diverges on a “simple” equation
Integration gives wildly different answers with different methods
Monte Carlo takes forever to converge

A bracket gives bisection a convergence guarantee for a continuous function with a sign change. Newton’s method uses a local linear model; it is not gradient descent. Monte Carlo has a root-mean-square rate proportional to $N^{-1/2}$ under independent, finite-variance sampling, but whether it is the best method depends on variance, dimension, structure, and cost.

Mathematical Foundations¶

📖 Core Notation and Concepts

Before diving in, let’s establish the mathematical language for static problems:

Root Finding Notation¶

Symbol	Meaning	Physical Example
$f(x) = 0$	Residual equation to solve	A discretized equilibrium or boundary condition
$x^*$ or $r$	Root/zero of function	Stellar radius
$[a,b]$	Bracketing interval	Search region
$\epsilon$	Tolerance	Desired accuracy
$e_n = x_n - r$	Error at iteration n	Distance from true root

Integration Notation¶

Symbol	Meaning	Physical Example
$\int_a^b f(x)dx$	Definite integral	Total luminosity
$w_i$	Quadrature weights	Sample contributions
$x_i$	Quadrature points	Where to evaluate
$h$	Step size	Wavelength spacing
$O(h^p)$	Error order	Convergence rate

Key Relationships¶

Root Finding Convergence Rates:

Bisection: bracket half-width $B_{n+1}=B_n/2$ ; actual midpoint error need not halve.
Secant near a smooth simple root: $|e_{n+1}|\approx C|e_n|^{1.618}$ .
Newton near a smooth simple root: $|e_{n+1}|\approx C|e_n|^2$ when the quadratic term is nonzero.

Integration Error Scaling:

Trapezoidal: $E \propto h^2$
Simpson: $E \propto h^4$
Monte Carlo: RMS error $\propto N^{-1/2}$ for independent finite-variance samples

These patterns recur in scientific computing, but each application still needs an explicit model and a convergence check.

Module Contents¶

Part 1: Root Finding¶

Learn three fundamental approaches to finding zeros: bracketing (bisection), tangent following (Newton), and interpolation (secant). Discover why different methods excel in different situations and how to combine them for robustness. Apply these to Kepler’s equation, Lagrange points, and stellar structure.

Part 2: Quadrature — Discrete Sums, Error, and Adaptation¶

Build composite rules from panels, measure their convergence, and implement a tested module. Compare deterministic and Monte Carlo estimators using their actual assumptions and cost.

Part 3: Synthesis and Method Selection¶

Separate root-finding and integration contracts, then compare their convergence claims and failure modes.

For Block 2, begin with Part 2. Return to Part 1 when Block 3 introduces root finding.