3. Numerical Methods
3.1 Solution of Nonlinear Equations
Start with equations of the form
Numerical methods construct a sequence
Bolzano's theorem provides existence: if
A fixed-point formulation rewrites the problem as
Then the iteration is
A function
The Banach fixed-point theorem on
- There is exactly one fixed point
. - For every starting value
, the iteration converges to . - The error decreases at least geometrically:
Convergence order describes how fast iterates approach the limit. A sequence converging to
Newton's method is derived from tangent lines. At
The next iterate is the zero of this tangent, so
This is also a fixed-point iteration with
Two useful convergence theorems for Newton's method. A monotone convergence theorem uses
Additional related methods:
| Method | Formula / idea | Main point |
|---|---|---|
| Chord method | Use a line through two points with opposite signs and keep a bracketing interval. | Preserves a sign-change bracket. |
| Secant method | Avoids explicit derivative; superlinear order about | |
| Multivariate Newton | In practice solve |
What to Emphasize in an Oral Answer
- Frame the problem as solving
by constructing iterates . - Mention existence and uniqueness checks: Bolzano sign change gives a root, and strict monotonicity on the interval gives uniqueness.
- Explain fixed-point iteration
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
. - 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
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
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
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
The interpolation polynomial exists and is unique.
The Lagrange basis polynomials are
They satisfy
Error estimate: if
where
Divided differences build the Newton form. First-order divided differences are
Higher-order divided differences are recursive:
The divided-difference table is triangular:
| Node | Value | 1st divided difference | 2nd divided difference | ... |
|---|---|---|---|---|
The Newton interpolation polynomial is
where
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
distinct nodes, find the unique polynomial of degree at most matching the prescribed values. - Present the Lagrange basis idea:
, so automatically interpolates. - Give the error form and what controls it: the
st derivative bound and the node polynomial . - 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
The error depends on the next derivative of the original function and on the node polynomial
The Newton form uses divided differences. First divided differences are slopes between neighboring nodes, and higher ones are built recursively. The interpolation polynomial becomes
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
to minimize
The general polynomial fitting problem is: given
minimizing
This can be written as an overdetermined linear system
where
The least-squares solution minimizes
The Gaussian normal equations:
If
Normal equations are the basic least-squares technique. For numerical accuracy, it is also standard to solve least squares using QR factorization: write
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
. - For polynomial fitting, identify the coefficient vector
, observation vector , and rectangular Vandermonde matrix . - State the normal equations
and the full-column-rank condition for uniqueness. - Include the line-fitting case as ordinary linear regression when
. - 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
The normal equations are
3.4 Numerical Integration
Numerical integration approximates a definite integral
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:
where
An interpolation-type quadrature formula is built by interpolating
Thus the weights are
Newton-Cotes formulas are interpolation-type quadrature formulas where the nodes are equally spaced. They are:
| Type | Node choice |
|---|---|
| Closed Newton-Cotes | The endpoints |
| Open Newton-Cotes | The endpoints are not used as nodes. |
Named quadrature formulas:
| Formula | Nodes | Approximation | Degree of exactness | Local error order |
|---|---|---|---|---|
| Midpoint rule | exact for degree | |||
| Trapezoidal rule | exact for degree | |||
| Simpson rule | exact for degree |
Here
for suitable
Composite formulas improve accuracy by splitting
For composite trapezoidal rule, split
Then
with global error order
For composite midpoint rule, use midpoints
with global error order
For composite Simpson rule, split into
with global error order
Accuracy summary:
| Rule | Single-panel order | Composite global order | Practical note |
|---|---|---|---|
| Midpoint | One interior node; often better than trapezoid for similar cost. | ||
| Trapezoidal | Uses endpoints; simple and robust. | ||
| Simpson | More accurate for smooth functions; requires paired intervals or midpoints. |
What to Emphasize in an Oral Answer
- Define quadrature as approximating
by weighted function values . - 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
weights. - Mention degree of exactness/error behavior: midpoint and trapezoid are lower order; Simpson is exact through degree
and has higher smooth-function accuracy. - Explain composite rules: subdivide the interval, apply a simple rule on each part, and get global orders
for midpoint/trapezoid and 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:
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
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
and iterate
If
Main methods:
| Method | Iteration idea |
|---|---|
| Jacobi | Split |
| Damped Jacobi | Blend Jacobi with old values using a parameter |
| Gauss-Seidel | Use newly computed components immediately: |
| Relaxation / SOR | Damped Gauss-Seidel with parameter |
| Richardson |
Spline interpolation uses a spline of degree
is a piecewise polynomial of degree
B-splines are spline basis functions with minimal support, nonnegativity, and partition-of-unity behavior.
