Skip to content

3. Numerical Methods ​

3.1 Solution of Nonlinear Equations ​

Start with equations of the form

f(x)=0,f:R→R.

Numerical methods construct a sequence (xk) that should converge to a root x∗.

Bolzano's theorem provides existence: if f is continuous on [a,b] and f(a)f(b)<0, then there is a root x∗∈(a,b). If f is also strictly monotone on the interval, the root is unique.

A fixed-point formulation rewrites the problem as

x=g(x).

Then the iteration is

xk+1=g(xk).

A function g:[a,b]→[a,b] is a contraction if there is a number 0≤q<1 such that

|g(x)−g(y)|≤q|x−y|(x,y∈[a,b]).

The Banach fixed-point theorem on [a,b] says:

  1. There is exactly one fixed point x∗∈[a,b].
  2. For every starting value x0∈[a,b], the iteration xk+1=g(xk) converges to x∗.
  3. The error decreases at least geometrically:
|xk−x∗|≤qk|x0−x∗|≤qk(b−a).

Convergence order describes how fast iterates approach the limit. A sequence converging to x∗ has order p if

limk→∞|xk+1−x∗||xk−x∗|p=c>0.

p=1 is linear convergence, p=2 is quadratic convergence, and 1<p<2 is superlinear convergence.

Newton's method is derived from tangent lines. At xk, approximate f by its tangent:

y−f(xk)=f′(xk)(x−xk).

The next iterate is the zero of this tangent, so

xk+1=xk−f(xk)f′(xk).

This is also a fixed-point iteration with g(x)=x−f(x)/f′(x). It is not defined if f′(xk)=0, and it can be numerically unstable when f′(xk) is close to zero. Multiple roots are especially delicate because f′(x∗)=0.

Two useful convergence theorems for Newton's method. A monotone convergence theorem uses f∈C2[a,b], a root in the interval, constant signs of f′ and f″, and a starting point with f(x0) and f″(x0) of the same sign. Under those conditions Newton's method converges monotonically to the root. A local convergence theorem gives quadratic convergence when the start is close enough to a simple root and f′ stays bounded away from zero.

Additional related methods:

MethodFormula / ideaMain point
Chord methodUse a line through two points with opposite signs and keep a bracketing interval.Preserves a sign-change bracket.
Secant methodxk+1=xk−f(xk)(xk−xk−1)/(f(xk)−f(xk−1))Avoids explicit derivative; superlinear order about (1+5)/2.
Multivariate Newtonxk+1=xk−[F′(xk)]−1F(xk)In practice solve F′(xk)(xk+1−xk)=−F(xk).

What to Emphasize in an Oral Answer ​

  • Frame the problem as solving f(x)=0 by constructing iterates xk→x∗.
  • Mention existence and uniqueness checks: Bolzano sign change gives a root, and strict monotonicity on the interval gives uniqueness.
  • Explain fixed-point iteration xk+1=g(xk) and Banach's contraction condition, including uniqueness and geometric error decay.
  • Define convergence order and distinguish linear, superlinear, and quadratic convergence.
  • Derive Newton's method from the tangent line and state xk+1=xk−f(xk)/f′(xk).
  • State Newton's strengths and caveats: quadratic near a simple root, but sensitive to poor starts, zero/small derivatives, and multiple roots.
  • Compare related methods: bracketing/chord methods preserve sign intervals, secant avoids explicit derivatives, multivariate Newton solves a linearized system.
Suggested answer

For nonlinear equations we want to solve f(x)=0 numerically by constructing a sequence converging to a root. Bolzano's theorem gives a basic existence test: if f is continuous on [a,b] and changes sign, then there is a root in the interval, and strict monotonicity gives uniqueness. Another approach is to rewrite the problem as a fixed-point equation x=g(x) and iterate xk+1=g(xk). If g maps [a,b] into itself and is a contraction, meaning |g(x)−g(y)|≤q|x−y| with q<1, then the Banach fixed-point theorem guarantees a unique fixed point in [a,b], convergence from every starting point in the interval, and a geometric error bound.

Convergence order describes the speed of this approach to the root: linear convergence has order one, the secant method is superlinear, and Newton's method is often quadratic near a simple root. Newton's method is based on tangent approximation. At the current point xk, replace the function by its tangent line and take the root of that tangent as the next approximation. This gives xk+1=xk−f(xk)/f′(xk). Near a simple root and under smoothness assumptions, Newton's method has quadratic convergence, so the number of correct digits can grow very quickly. But the method is not defined when the derivative is zero and can behave badly when the derivative is very small, the root is multiple, or the starting point is poor.

Also include bracketing and derivative-free variants. The chord method keeps a sign-change interval and uses chords, while the secant method uses the last two iterates to approximate the derivative. The secant method avoids computing f′ and has superlinear convergence, though typically slower than Newton's quadratic convergence.

3.2 Polynomial Interpolation ​

Interpolation replaces an unknown or expensive function by a simpler function matching known values. It is motivated by function values measured at selected nodes and the desire to approximate values between nodes.

The polynomial interpolation problem is:

Given distinct nodes x0,…,xn and values f(x0),…,f(xn), find a polynomial pn of degree at most n such that

pn(xk)=f(xk)(k=0,…,n).

The interpolation polynomial exists and is unique.

The Lagrange basis polynomials are

lk(x)=∏j=0j≠knx−xjxk−xj.

They satisfy lk(xj)=1 if j=k and 0 otherwise. Therefore the interpolation polynomial is

Ln(x)=∑k=0nf(xk)lk(x).

Error estimate: if f∈Cn+1[a,b], then

|f(x)−Ln(x)|≤Mn+1(n+1)!|ωn(x)|,

where

ωn(x)=∏i=0n(x−xi),Mn+1=max[a,b]|f(n+1)(x)|.

Divided differences build the Newton form. First-order divided differences are

f[xi,xi+1]=f(xi+1)−f(xi)xi+1−xi.

Higher-order divided differences are recursive:

f[xi,…,xi+k]=f[xi+1,…,xi+k]−f[xi,…,xi+k−1]xi+k−xi.

The divided-difference table is triangular:

NodeValue1st divided difference2nd divided difference...
x0f(x0)
x1f(x1)f[x0,x1]
x2f(x2)f[x1,x2]f[x0,x1,x2]
⋯⋯⋯⋯⋯

The Newton interpolation polynomial is

Nn(x)=f(x0)+∑k=1nf[x0,x1,…,xk]ωk−1(x),

where

ωj(x)=(x−x0)(x−x1)⋯(x−xj).

The Lagrange and Newton forms represent the same unique interpolation polynomial. Lagrange form is direct and symmetric in the nodes. Newton form is computationally convenient because adding a new node only adds one more term.

Also include Hermite interpolation, where derivative values are prescribed in addition to function values. It generalizes Lagrange interpolation: if only function values are prescribed, it reduces to the ordinary Lagrange problem; if function and first derivative values are given at each node, it becomes a Hermite-Fejer-type problem.

What to Emphasize in an Oral Answer ​

  • State the interpolation problem: for n+1 distinct nodes, find the unique polynomial of degree at most n matching the prescribed values.
  • Present the Lagrange basis idea: lk(xj)=δkj, so Ln(x)=∑f(xk)lk(x) automatically interpolates.
  • Give the error form and what controls it: the (n+1)st derivative bound and the node polynomial ωn(x)=∏i=0n(x−xi).
  • Explain Newton form through divided differences and why it is computationally convenient when adding nodes.
  • Mention that Lagrange and Newton are two forms of the same unique polynomial.
  • Include Hermite interpolation as the extension where derivative values are also prescribed.
Suggested answer

Polynomial interpolation asks for a polynomial of degree at most n that matches given function values at n+1 distinct nodes. The interpolation problem has a unique solution. In Lagrange form, we build basis polynomials lk that are one at the k-th node and zero at all other nodes. Then the polynomial is Ln(x)=∑f(xk)lk(x), which automatically matches every prescribed value.

The error depends on the next derivative of the original function and on the node polynomial ωn(x)=∏(x−xi). If f is n+1 times continuously differentiable, the error is bounded by Mn+1|ωn(x)|/(n+1)!.

The Newton form uses divided differences. First divided differences are slopes between neighboring nodes, and higher ones are built recursively. The interpolation polynomial becomes f(x0)+∑f[x0,…,xk]ωk−1(x). It is the same polynomial as the Lagrange form, but it is often better for computation because if a new node is added, the existing terms can be kept and only a new divided-difference term is appended. Hermite interpolation extends the same idea by prescribing derivative data in addition to function values.

3.3 Least-Squares Method ​

Least squares is motivated by measurement errors: measured points usually do not lie exactly on one line or on one low-degree polynomial. Instead of enforcing exact interpolation, we choose a function that minimizes the sum of squared residuals.

For line fitting with points (xi,yi), choose

p1(x)=a+bx

to minimize

∑i=1m(yi−p1(xi))2.

The general polynomial fitting problem is: given m data points with m≫n, find

pn(x)=a0+a1x+⋯+anxn

minimizing

∑i=1m(yi−pn(xi))2.

This can be written as an overdetermined linear system

Az≈b,

where z=(a0,…,an)T, b=(y1,…,ym)T, and A is the rectangular Vandermonde matrix

A=[1x1x12⋯x1n1x2x22⋯x2n⋮⋮⋮⋱⋮1xmxm2⋯xmn].

The least-squares solution minimizes

∥Az−b∥22.

The Gaussian normal equations:

ATAz=ATb.

If A has full column rank, then ATA is invertible and the solution is unique. For n=1, this is ordinary linear regression. The normal-equation matrix and right-hand side are

ATA=[m∑xi∑xi∑xi2],ATb=[∑yi∑xiyi].

Normal equations are the basic least-squares technique. For numerical accuracy, it is also standard to solve least squares using QR factorization: write A=QR with orthonormal columns in Q, then solve

Rz=QTb.

QR avoids squaring the condition number, which is a weakness of normal equations. In rank-deficient or ill-conditioned cases, singular value decomposition is the most robust technique.

What to Emphasize in an Oral Answer ​

  • Contrast least squares with interpolation: it fits noisy or overdetermined data instead of forcing every point to match exactly.
  • State the objective: minimize the sum of squared residuals, equivalently ∥Az−b∥22.
  • For polynomial fitting, identify the coefficient vector z, observation vector b, and rectangular Vandermonde matrix A.
  • State the normal equations ATAz=ATb and the full-column-rank condition for uniqueness.
  • Include the line-fitting case as ordinary linear regression when n=1.
  • Mention numerical stability: normal equations are basic but can worsen conditioning; QR is preferred, and SVD is most robust for ill-conditioned or rank-deficient cases.
Suggested answer

Least squares is used when exact interpolation is inappropriate, usually because data contains measurement error or because there are more data points than parameters. Instead of requiring a polynomial to pass through every point, we choose coefficients that minimize the sum of squared residuals.

For polynomial fitting, write pn(x)=a0+a1x+⋯+anxn. Evaluating this polynomial at all measured xi gives an overdetermined linear system Az≈b, where A is a rectangular Vandermonde matrix and z is the vector of coefficients. The objective is to minimize ∥Az−b∥22.

The normal equations are ATAz=ATb. If A has full column rank, these equations have a unique solution and produce the least-squares polynomial; for n=1 this is ordinary linear regression. For numerical work, QR factorization is often preferred because it is more stable: with A=QR, one solves Rz=QTb. For very ill-conditioned or rank-deficient problems, SVD is the most robust method.

3.4 Numerical Integration ​

Numerical integration approximates a definite integral

∫abf(x)dx

when an antiderivative is not known or not convenient, but function values can be computed.

A quadrature formula approximates the integral by weighted function values:

Qn(f)=∑i=1nwif(xi),

where xi are the nodes and wi are the weights.

An interpolation-type quadrature formula is built by interpolating f at the chosen nodes, integrating the interpolation polynomial, and using that value as the approximation. If Li(x) are the Lagrange basis polynomials for the nodes, then

∫abf(x)dx≈∫ab∑i=1nf(xi)Li(x)dx=∑i=1nf(xi)∫abLi(x)dx.

Thus the weights are

wi=∫abLi(x)dx.

Newton-Cotes formulas are interpolation-type quadrature formulas where the nodes are equally spaced. They are:

TypeNode choice
Closed Newton-CotesThe endpoints a and b are included as nodes.
Open Newton-CotesThe endpoints are not used as nodes.

Named quadrature formulas:

FormulaNodesApproximationDegree of exactnessLocal error order
Midpoint rulem=(a+b)/2(b−a)f(m)exact for degree 1 polynomialsO(h3)
Trapezoidal rulea,b(b−a)(f(a)+f(b))/2exact for degree 1 polynomialsO(h3)
Simpson rulea,(a+b)/2,b(b−a)(f(a)+4f((a+b)/2)+f(b))/6exact for degree 3 polynomialsO(h5)

Here h=b−a for a single interval. The usual error forms, when the required derivatives exist, are:

EM=−(b−a)324f″(ξ),ET=−(b−a)312f″(ξ),ES=−(b−a)52880f(4)(ξ),

for suitable ξ in (a,b), up to sign conventions depending on whether error is written as exact minus approximate or approximate minus exact.

Composite formulas improve accuracy by splitting [a,b] into subintervals and applying a simple rule on each piece. This avoids using one high-degree interpolation polynomial over a large interval, which can oscillate badly.

For composite trapezoidal rule, split [a,b] into n equal parts with

h=b−an,xi=a+ih.

Then

Tn=h(f(x0)+f(xn)2+∑i=1n−1f(xi)),

with global error order O(h2).

For composite midpoint rule, use midpoints mi=(xi−1+xi)/2:

Mn=h∑i=1nf(mi),

with global error order O(h2).

For composite Simpson rule, split into n subintervals and apply Simpson on each subinterval, or equivalently use 2n+1 equally spaced nodes with half-step h/2. In the common form with an even number N of subintervals and h=(b−a)/N,

SN=h3(f(x0)+f(xN)+4∑i=1i oddN−1f(xi)+2∑i=2i evenN−2f(xi)),

with global error order O(h4).

Accuracy summary:

RuleSingle-panel orderComposite global orderPractical note
MidpointO(h3)O(h2)One interior node; often better than trapezoid for similar cost.
TrapezoidalO(h3)O(h2)Uses endpoints; simple and robust.
SimpsonO(h5)O(h4)More accurate for smooth functions; requires paired intervals or midpoints.

What to Emphasize in an Oral Answer ​

  • Define quadrature as approximating ∫abf(x)dx by weighted function values Qn(f)=∑wif(xi).
  • Explain interpolation-type quadrature: interpolate at chosen nodes and integrate the interpolation polynomial; weights are integrals of Lagrange basis functions.
  • Distinguish closed and open Newton-Cotes formulas by whether endpoints are used as nodes.
  • State the midpoint, trapezoidal, and Simpson formulas, especially Simpson's 1,4,1 weights.
  • Mention degree of exactness/error behavior: midpoint and trapezoid are lower order; Simpson is exact through degree 3 and has higher smooth-function accuracy.
  • Explain composite rules: subdivide the interval, apply a simple rule on each part, and get global orders O(h2) for midpoint/trapezoid and O(h4) for Simpson.
  • Note the practical reason for composite formulas: avoid one high-degree interpolant over a large interval.
Suggested answer

Numerical integration approximates a definite integral when an antiderivative is unavailable or inconvenient. A quadrature formula uses function values at selected nodes and weights them: Qn(f)=∑wif(xi).

Interpolation-type quadrature formulas choose nodes, interpolate the function at those nodes by a Lagrange polynomial, and integrate that polynomial exactly. This explains why the weights are integrals of the Lagrange basis polynomials. Newton-Cotes formulas are the interpolation quadrature formulas with equally spaced nodes. They are closed if the endpoints are included and open if the endpoints are omitted.

The main simple formulas are midpoint, trapezoidal, and Simpson. The midpoint rule uses the middle point and gives (b−a)f((a+b)/2). The trapezoidal rule uses the endpoints and gives (b−a)(f(a)+f(b))/2. Simpson's rule uses the endpoints and midpoint with weights 1,4,1, giving (b−a)(f(a)+4f((a+b)/2)+f(b))/6. Midpoint and trapezoidal rules have local error of order h3 and composite global error h2; Simpson has local error h5 and composite global error h4.

Composite formulas split the interval into smaller pieces and apply a simple formula on each piece. This improves accuracy without fitting one high-degree polynomial over the entire interval. Composite trapezoid and midpoint have second-order global accuracy, while composite Simpson has fourth-order global accuracy for sufficiently smooth functions.

Additional Material: Linear Systems and Splines ​

Iterative methods for linear systems and splines are included here as related numerical-methods material.

For linear systems Ax=b, iterative methods rewrite the system as

x=Bx+c

and iterate

x(k+1)=Bx(k)+c.

If B is a contraction, or more generally if the spectral radius ρ(B)<1, the iteration converges from every starting vector to the solution.

Main methods:

MethodIteration idea
JacobiSplit A=L+D+U; use old values on the right side: xk+1=−D−1(L+U)xk+D−1b.
Damped JacobiBlend Jacobi with old values using a parameter ω.
Gauss-SeidelUse newly computed components immediately: xk+1=−(L+D)−1Uxk+(L+D)−1b.
Relaxation / SORDamped Gauss-Seidel with parameter ω; convergence for symmetric positive definite A when 0<ω<2.
Richardsonxk+1=xk+p(b−Axk) using the residual.

Spline interpolation uses a spline of degree l on a partition

a=x0<x1<⋯<xn=b

is a piecewise polynomial of degree l on each subinterval, with global smoothness Cl−1. Spline interpolation asks for a spline matching the data values at the nodes. Extra boundary conditions are needed for uniqueness; cubic splines require two, such as natural boundary conditions s″(a)=s″(b)=0, Hermite endpoint slopes, or periodic endpoint conditions.

B-splines are spline basis functions with minimal support, nonnegativity, and partition-of-unity behavior.