Problem-solving recipes

A step-by-step procedure for every problem type this course teaches — what to do first, what to do next, and how to tell which case you're in.

What are you being asked to do?

Start with what you're actually being asked to produce.

Given $f$ (or a bracket), need a root — the real cross-cutting choice in this course. Have a bracket $[a,b]$ with a sign change and need a guaranteed answer, no derivative required? Bisection. Have a formula for $f'$ and a starting guess already close to the root, and speed matters more than a guarantee? Newton's method — quadratic convergence, but it can fail from a bad start or with no derivative available at all.

Given $A\mathbf x=\mathbf b$ , need $\mathbf x$ — the other cross-cutting choice. A general dense system, or need an EXACT answer (up to round-off) in a predictable number of steps? Gaussian elimination with partial pivoting. A large, sparse, diagonally dominant system where an approximate answer to a stated tolerance is enough? Jacobi's method — cheaper per sweep, and guaranteed to converge under that same diagonal- dominance condition.

Given a table of $(x,y)$ points, need a polynomial through all of them — Newton's divided-difference form, especially if more points might get added later.

Given the same kind of table, need one SMOOTH piecewise curve instead of one high-degree polynomial — the natural cubic spline.

Given $f$ and a step size $h$ , need a more accurate derivative estimate — Richardson extrapolation on the central-difference formula.

Given $f$ , need $\int_a^b f(x)\,dx$ numerically — the composite Simpson's rule.

Given an overdetermined system $A\mathbf x\approx\mathbf b$ , need the best-fit $\hat{\mathbf x}$ without the numerical risk of the normal equations — least squares via $QR$ .

Given a matrix with a strictly dominant eigenvalue, need that eigenvalue and its eigenvector — power iteration with the Rayleigh quotient.

Given a system of nonlinear equations $F(\mathbf x)=\mathbf 0$ , need a solution — Newton's method for systems, which itself calls a linear solve (either recipe above) at every step.

Given an IVP $y'=f(t,y)$ , $y(t_0)=y_0$ , and a step size $h$ , need the next point — one RK4 step.

Given a LINEAR boundary-value problem, need the solution at every grid point — the linear shooting method, which itself calls the RK4 recipe above twice.

Finding a root

Run the bisection method

Use when: you have a bracket $[a,b]$ (f(a), f(b) of opposite sign) and need a root to a stated tolerance

Goal: an approximation within the required tolerance of a root, with a guaranteed error bound at every step

The Bisection Method

Guaranteed to work from any bracket -- slow, but never fails.

Run Newton's method

Use when: you have a formula for $f$ and $f'$ , and a starting guess $x_0$ reasonably close to a root

Goal: a sequence of guesses converging rapidly to a root, each one the x-intercept of the tangent line at the last

Newton's Method: derivation from the tangent line

Much faster when it works -- needs $f'$ and a starting guess already close to the root.

Solving a linear system

Solve a linear system by Gaussian elimination with partial pivoting

Use when: you're solving a linear system by hand and need the pivot order itself to control round-off growth, not just reach a correct answer

Goal: the numeric value of every unknown, reached by a pivot order that keeps every multiplier no larger than 1 in magnitude

Partial pivoting and why it's necessary

The general-purpose direct method -- an exact answer (up to round-off) in a predictable number of steps.

Run the Jacobi method to a stopping tolerance

Use when: you have a square system $A\mathbf{x}=\mathbf{b}$ with every diagonal entry $a_{ii}\ne0$ and a stated tolerance $\varepsilon$

Goal: an approximate solution vector whose change from the previous sweep is under $\varepsilon$ , built entirely from sweeps that each depend only on the sweep before it

The Jacobi method

The iterative alternative -- cheaper per sweep on a large, sparse, diagonally dominant system, only approximate.

Building an interpolating polynomial

Construct Newton's divided-difference interpolating polynomial

Use when: you have a table of (x, y) data points (or values of a known function at chosen nodes) and want a polynomial passing through all of them, especially if you might add more points later

Goal: the divided-difference table's top diagonal, assembled into Newton's nested form for P(x)

Newton's divided-difference form

Fitting a smooth curve through data

Construct a natural cubic spline

Use when: you have a table of (x, y) data points and want one smooth, piecewise-cubic curve through all of them, with no extra information available about the slope at either end

Goal: every coefficient $a_j,b_j,c_j,d_j$ of every piece, assembled into the full piecewise definition of $S(x)$

Natural boundary conditions

One polynomial per piece instead of one high-degree polynomial through every point.

Approximating a derivative

Richardson-extrapolate a difference approximation

Use when: you have an approximation $A(h)$ with a known, pure leading error order $h^p$ (for the central-difference formula, $p=2$ ), computed at a step size $h$ and at $h/2$

Goal: a new approximation, accurate to $O(h^{p+1})$ , with the shared leading error term of the two inputs canceled exactly

Richardson extrapolation

Combines two central-difference estimates to cancel the leading error term.

Approximating an integral

Apply the composite Simpson's rule

Use when: you need $\int_a^b f(x)\,dx$ to a specific accuracy and $f$ is smooth enough that a piecewise-parabola fit tracks it well

Goal: a single numerical approximation $S_n$ to the integral, built from $n+1$ evaluations of $f$

Simpson's rule and degree of precision

Solving a least-squares problem

Solve a least-squares problem via QR factorization

Use when: you have an overdetermined system $A\mathbf x\approx\mathbf b$ ( $A$ has more rows than columns, independent columns) and need a numerically trustworthy $\hat{\mathbf x}$ -- not just any correct one

Goal: the least-squares solution $\hat{\mathbf x}$ , reached without ever forming $A^{\mathsf T}\!A$

Least squares via QR factorization

The numerically trustworthy alternative to the normal equations.

Finding an eigenvalue

Estimate a dominant eigenvalue by power iteration and the Rayleigh quotient

Use when: you have a square matrix $A$ with (or assumed to have) a single strictly dominant eigenvalue, and want a numerical estimate of it and its eigenvector without forming the characteristic polynomial

Goal: a unit eigenvector for $A$ 's dominant eigenvalue $\lambda_1$ , plus a numerical estimate of $\lambda_1$ itself, both accurate to as many digits as needed

The Rayleigh quotient and accelerated convergence

Solving a system of nonlinear equations

Run Newton's method for a nonlinear system

Use when: you have formulas for every $F_i$ and every partial derivative $\partial F_i/\partial x_j$ , and a starting guess $\mathbf{x}_0$ reasonably close to a root of $F(\mathbf{x})=\mathbf{0}$

Goal: a sequence of vector guesses converging rapidly to a root of the system, each one built by solving one linear system

Newton's Method for Systems: the Jacobian

Calls a linear-system recipe above at every iteration.

Advancing an ODE's numerical solution

Take one RK4 step

Use when: you're given an IVP $y'=f(t,y)$ , $y(t_0)=y_0$ , a chosen step size $h$ , and asked to advance the numerical solution by one step with fourth-order accuracy

Goal: the next point $(t_{n+1},y_{n+1})$ on the numerical solution

RK4

Solving a boundary-value problem

Solve a linear BVP by shooting

Use when: you have a LINEAR second-order BVP $y''=p(x)y'+q(x)y+r(x)$ , $y(a)=\alpha$ , $y(b)=\beta$ , with $p,q,r$ continuous on $[a,b]$

Goal: the BVP's solution values at every grid point, accurate to whatever error RK4 itself carries -- reached by two ordinary IVP solves and one exact combination, no iteration

The Linear Shooting Method

Calls the RK4 recipe above twice per trial, for a LINEAR BVP specifically.