Numerical Methods

------- | ------- | ------------------------------------------------------ | | AQA | Paper 2 | Sign change, iteration,” date: 2025-06-02T16:25:28.480Z tags:

• Maths
• ALevel categories:
• Maths

Theorem. If $f$ is continuous on $[a,b]$ and $f(a)$ and $f(b)$ have opposite signs, then there Exists at least one root $\alpha \in (a,b)$ such that $f(\alpha) = 0$.

The sign change theorem tells us a root exists but says nothing about:

• How many roots are in the interval (there could be 1, 3, 5, …).
• The exact location of the root.

Intuition. The sign change theorem is the Intermediate Value Theorem applied to the special case Of crossing zero. If you walk from a point below sea level to one above sea level, you must cross Sea level at some point, provided the ground is continuous (no teleporting).

To solve $f(x) = 0$ Rewrite as $x = g(x)$ and iterate:

Starting from an initial guess $x_0$. If the sequence converges to $\alpha$ Then $f(\alpha) = 0$.

Theorem. If $g$ is continuously differentiable near a fixed point $\alpha$ and $|g'(\alpha)| \lt 1$ Then the iteration $x_{n+1} = g(x_n)$ converges to $\alpha$ for all starting Values sufficiently close to $\alpha$.

If $|g'(\alpha)| \gt 1$ The iteration diverges.

Proof (linear convergence). Near $\alpha$ By Taylor’s theorem:

Since $g(\alpha) = \alpha$:

For $x_n$ close to $\alpha$:

If $|g'(\alpha)| \lt 1$ Then $|x_{n+1} - \alpha| \lt |x_n - \alpha|$: the error shrinks, so the Iteration converges. If $|g'(\alpha)| \gt 1$ The error grows and the iteration diverges. $\blacksquare$

Different rearrangements of $f(x) = 0$ give different $g(x)$ And some converge while others Diverge.

Example. Solve $x^3 + x - 1 = 0$.

• $g(x) = 1 - x^3$: $g'(x) = -3x^2$. Near the root $\alpha \approx 0.68$: $|g'(\alpha)| \approx 1.39 \gt 1$. Diverges.
• $g(x) = \sqrt[3]{1-x}$: $g'(x) = \dfrac{-1}{3(1-x)^{2/3}}$. Near $\alpha$: $|g'(\alpha)| \approx 0.72 \lt 1$. Converges.

The fixed-point iteration $x_{n+1} = g(x_n)$ can be visualised using the cobweb diagram. Plot $y = g(x)$ and $y = x$. Starting from $x_0$ on the $x$-axis, go vertically to $y = g(x_0) = x_1$ then horizontally to $y = x$ Then vertically to $y = g(x_1) = x_2$ And so on.

• If $0 \lt g'(\alpha) \lt 1$: the cobweb spirals inward (monotone convergence).
• If $-1 \lt g'(\alpha) \lt 0$: the cobweb zigzags inward (oscillatory convergence).
• If $|g'(\alpha)| \gt 1$: the cobweb spirals or zigzags outward (divergence).

The closer $|g'(\alpha)|$ is to zero, the faster the convergence. When $g'(\alpha) = 0$ The Iteration achieves quadratic convergence (similar to Newton-Raphson), since the leading error term In the Taylor expansion vanishes.

To solve $f(x) = 0$ Start from $x_0$ and draw the tangent to $y = f(x)$ at $x_0$. The tangent line is:

Setting $y = 0$ (where the tangent crosses the $x$-axis):

This is the Newton-Raphson formula.

Theorem. If $f$ is twice continuously differentiable, $f(\alpha) = 0$, $f'(\alpha) \neq 0$ And $x_0$ is sufficiently close to $\alpha$ Then Newton-Raphson converges quadratically: $|x_{n+1} - \alpha| \leq C|x_n - \alpha|^2$.

Proof (sketch). By Taylor’s theorem about $x_n$:

For some $\xi$ between $\alpha$ and $x_n$. Rearranging:

Taking absolute values: $|x_{n+1} - \alpha| = \dfrac{|f''(\xi)|}{2|f'(x_n)|}|x_n - \alpha|^2 \leq C|x_n - \alpha|^2$. $\blacksquare$

Intuition. Quadratic convergence means the number of correct decimal places roughly doubles With each iteration. If you have 2 correct digits, the next iteration gives about 4, then 8, Then 16. This is dramatically faster than the linear convergence of fixed-point iteration (which Adds roughly a fixed number of correct digits per step).

Newton-Raphson fails when:

• $f'(x_n) = 0$ (the tangent is horizontal, division by zero).
• $f'(x_n)$ is close to zero (the next iterate jumps far away).
• The starting point is not close enough to the root.

Caution: Warning A different starting point.

When $f'(x_n) = 0$ at some iterate, the Newton-Raphson formula requires division by zero and the Method breaks down entirely. Even when $f'(x_n)$ is merely small, the step $x_{n+1} = x_n - f(x_n)/f'(x_n)$ becomes very large, sending the iterate far from the root.

Example. Let $f(x) = x^3 - 3x + 3$. Then $f'(x) = 3x^2 - 3$ So $f'(1) = 0$. Starting at $x_0 = 1$:

The formula gives $x_1 = 1 - f(1)/f'(1) = 1 - 1/0$ Which is undefined.

Even starting at $x_0 = 0.9$: $f(0.9) = 0.729 - 2.7 + 3 = 1.029$, $f'(0.9) = 2.43 - 3 = -0.57$. $x_1 = 0.9 - 1.029/(-0.57) = 0.9 + 1.805 = 2.705$.

The root is near $\alpha \approx -2.10$ So the iterate has been sent in the wrong direction. The Next iterate $x_2$ will be pulled back, but convergence is erratic compared to a well-chosen Starting point.

Caution: Warning Tangent is not close to horizontal near your starting point.

The quadratic convergence proof in Section 3.2 requires $f'(\alpha) \neq 0$. When the root coincides with an inflection point, so that $f'(\alpha) = 0$ Convergence degrades from quadratic to linear.

Theorem. If f(\alpha) = 0$$f'(\alpha) = 0$$f''(\alpha) \neq 0 And $x_0$ is sufficiently Close to $\alpha$ Then Newton-Raphson converges linearly with rate $1/2$:

Proof sketch. Expanding by Taylor’s theorem to third order about $\alpha$:

Therefore:

So $|x_{n+1} - \alpha| \to \frac{1}{2}|x_n - \alpha|$ as $x_n \to \alpha$: the error is halved each Step (linear convergence with rate $1/2$), not squared. $\blacksquare$

Example. $f(x) = (x-1)^3$ has a root at $x = 1$ where $f'(1) = 0$. The Newton-Raphson iteration Becomes:

Starting at $x_0 = 4$: x_1 = 3$$x_2 = 7/3 \approx 2.333$$x_3 = 17/9 \approx 1.889 x_4 = 37/27 \approx 1.370$$x_5 = 75/81 \approx 1.210…

The error is multiplied by $2/3$ each step (linear, not quadratic). Compare: standard Newton-Raphson with $f'(\alpha) \neq 0$ would give roughly 1, then 2, then 4, then 8 correct digits. Here each step only adds a fixed fraction of a digit.

Where $h = (b-a)/n$ and $y_i = f(a+ih)$.

Theorem. The error in the composite trapezium rule is:

For some $\eta \in (a, b)$ Provided $f$ is twice continuously differentiable on $[a, b]$.

Derivation. Consider a single strip $[x_i, x_{i+1}]$ of width $h$. The trapezium rule Approximates $\int_{x_i}^{x_{i+1}} f(x)\,dx$ by the area of a trapezium:

To find the error, expand $f$ about the midpoint $m_i = x_i + h/2$. Let $\delta = h/2$:

Adding these:

The trapezium approximation for this strip is:

The exact integral over this strip is (by Taylor expansion of the integral):

Therefore the error on a single strip is:

Summing over all $n$ strips and applying the Intermediate Value Theorem to $f''$ (which is Continuous), there exists $\eta \in (a, b)$ such that:

Since $\sum_{i=0}^{n-1} f''(m_i) \cdot h \approx \int_a^b f''(x)\,dx$ and $nh = b - a$:

(The negative sign arises from the exact derivation via the Euler-Maclaurin formula; the key point is the $h^2$ scaling.) $\blacksquare$

Key consequence. The error is proportional to $h^2 = (b-a)^2/n^2$. Doubling the number of strips ($n \to 2n$) reduces the error by a factor of 4, since $h \to h/2$ and $h^2 \to h^2/4$.

From the error formula, since $|f''(\eta)| \leq M$ for all $\eta \in [a,b]$:

This gives a guaranteed upper bound on the absolute error. If we require the error to satisfy $|E_T| \lt \varepsilon$ We need:

Example. Approximate $\displaystyle\int_0^1 e^{-x^2}\,dx$ with the trapezium rule. Here $f(x) = e^{-x^2}$ So $f'(x) = -2x\,e^{-x^2}$ and $f''(x) = (4x^2 - 2)e^{-x^2}$. On $[0,1]$: $|f''(x)| \leq 2$ (achieved at $x = 0$ Where $f''(0) = -2$).

For error $\lt 10^{-4}$:

So $n = 42$ strips suffice (rounding up to the nearest even number, which is convenient if one later Wishes to compare with Simpson’s rule).

For an even number $n$ of strips:

The coefficients follow the pattern: $1, 4, 2, 4, 2, \ldots, 4, 1$.

Simpson’s rule approximates $f$ by quadratic arcs over pairs of strips. Over $[x_{2k}, x_{2k+2}]$ A Unique quadratic passes through (x_{2k}, y_{2k})$$(x_{2k+1}, y_{2k+1})$$(x_{2k+2}, y_{2k+2}). Integrating this quadratic gives the area $\dfrac{h}{3}(y_{2k} + 4y_{2k+1} + y_{2k+2})$.

Where $|f^{(4)}(x)| \leq M$ on $[a,b]$.

Intuition. Simpson’s rule has error $O(1/n^4)$ compared to $O(1/n^2)$ for the trapezium rule. Doubling the number of strips reduces the error by a factor of 16 for Simpson’s rule vs. 4 for the Trapezium rule. This is because quadratic approximations match the curvature of the function much Better than linear ones.

Sign change (bisection): Use when you need a guaranteed, robust result and have a sign change. Always converges but slowly (halving the interval each step). No derivative needed. Excellent for Initial bracketing before switching to a faster method.

Fixed-point iteration: Use when the equation is rearranged into $x = g(x)$ and $|g'(\alpha)| \lt 1$ can be verified. Simple to implement but may converge slowly or diverge Entirely depending on the rearrangement. Different rearrangements of the same equation can give Radically different convergence behaviour.

Newton-Raphson: Use when $f'(x)$ is easy to compute and a good starting estimate is available. Extremely fast (quadratic convergence) when it works, but can fail catastrophically if $f'(x_n)$ is Small, if the starting point is poor, or if the root is at an inflection point.

In practice, numerical software often combines methods:

1. Bracket the root using sign change to find an interval $[a, b]$ containing the root.
2. Refine using Newton-Raphson or fixed-point iteration starting from the midpoint or a favourable endpoint.
3. Verify the result by checking $f(x_n)$ is sufficiently close to zero.

Newton-Raphson requires both $f$ and $f'$ per step (two evaluations), but its quadratic convergence Means it needs far fewer steps in total. For high accuracy requirements, Newton-Raphson is Overwhelmingly more efficient despite the higher per-step cost.

• Differentiation — Newton-Raphson requires the derivative, and convergence analysis relies on Taylor’s theorem from differentiation.
• Integration — The trapezium rule and Simpson’s rule are numerical approximations of definite integrals.
• Exponentials and Logarithms — Many root-finding problems involve exponential equations solved iteratively.
• Proof — Convergence proofs use logical deduction techniques such as contradiction and induction.

1. Forgetting to check that solutions satisfy the original equation (especially with squaring both sides or dividing by variables).

2. Rounding too early in multi-step calculations. Carry full precision through and round only the final answer.

3. Losing marks by not showing sufficient working. Always write out each step, especially in proof questions.

4. Misreading the question, particularly with ‘hence’ vs ‘hence or otherwise’. The former requires using previous work.

flowchart TD
    A[14 Numerical Methods] --> B[Key Concepts]
    A --> C[Core Principles]
    A --> D[Practical Applications]
    B --> E[Fundamental definitions]
    C --> F[Design patterns]
    D --> G[Real-world usage]

The key principles covered in this topic are linked in the sub-pages above. Focus on understanding the definitions, applying the formulas or frameworks, and evaluating strengths and limitations of each approach.

Worked examples demonstrating the application of key concepts are covered in the detailed sub-pages linked above.