Ne1, Ne2 - Fixed point iteration and Newton-Raphson | OCR A-Level Further Mathematics B (MEI)

Generate root approximations by repeated substitution or tangent intercepts. You will draw staircase and cobweb paths, implement the correct iteration, choose meaningful starting values, and use the accuracy checks from the previous lesson.

A rearrangement chooses an iteration

The positive root of $x^2-x-1=0$ can be written as $x=\sqrt{x+1}$ or $x=1+1/x$ . If both start at $1$ , must they take the same route to the root?

They do not. The first approaches from below; the second jumps between sides. An algebraic rearrangement preserves the relevant fixed point but changes the function repeatedly applied.

You already know

A recurrence needs a starting value and a precise update. Keep stored precision between evaluations. A continuous sign change inside a proposed answer's rounding interval can justify its decimal places when the intended root is isolated.

A fixed point is a number $\alpha$ with $g(\alpha)=\alpha$ , represented by an intersection of $y=g(x)$ and $y=x$ .

Fixed point iteration

Rearrange the equation as $x=g(x)$ , and generate

x_{n+1}=g(x_n),\qquad n=0,1,2,\ldots

If the iterates converge to $\alpha$ and $g$ is continuous there, the limit satisfies $\alpha=g(\alpha)$ . The rearrangement must remain valid for the root sought.

Not in the formula booklet: learn it.

For a graphical trace, start at $(x_0,0)$ , move vertically to $y=g(x)$ , then horizontally to $y=x$ . Repeat vertical-to-curve and horizontal-to-line. A monotone approach often produces a staircase; an alternating approach produces a cobweb.

[DIAGRAM: asset_name: Staircase and cobweb for the same positive root; asset_slug: fixed_point_paths; caption: Different rearrangements produce different graphical journeys to the same fixed point; description: Two equal-scale panels plot y=x with y=square root of x plus 1 and y=1 plus 1/x over positive x. From x0=1 the first four vertical and horizontal iteration moves form an increasing staircase in the first panel and an alternating cobweb in the second. The common intersection is alpha approximately 1.618.]
Different rearrangements produce different graphical journeys to the same fixed point

Worked example 1: the staircase rearrangement

Question. Use $x_{n+1}=\sqrt{x_n+1}$ , $x_0=1$ , to find the positive root of $x^2-x-1=0$ to four decimal places.

Plan. Repeat the square-root update, inspect the later output and certify the proposed rounding.

\begin{aligned} x_1&=\sqrt2=1.41421356\ldots && \text{first substitution}\\ x_2&=\sqrt{x_1+1}=1.55377397\ldots && \text{retain stored }x_1\\ x_3&=\sqrt{x_2+1}=1.59805318\ldots && \text{same update}\\ x_4&=\sqrt{x_3+1}=1.61184775\ldots && \text{staircase continues} \end{aligned}

Continuing without intermediate rounding gives this output.

$n$	$x_n$ , displayed to eight decimal places
$8$	$1.61797753$
$9$	$1.61801654$
$10$	$1.61802860$

For $f(x)=x^2-x-1$ , test the proposed four-decimal answer's boundaries:

f(1.61795)=-0.0001877975<0,\qquad f(1.61805)=0.0000358025>0

Why this step? The iterates suggest $1.6180$ ; continuity and strict increase of $f$ on $[1,2]$ put its unique root inside that rounding cell.

Answer. $\alpha=1.6180$ to four decimal places.

Check. All displayed early iterates rise towards the intersection, matching the staircase; the sign test supplies the accuracy justification.

Change only the rearrangement, keeping the equation, seed and required precision fixed.

Worked example 2: the cobweb rearrangement

Question. Find the same positive root using $x_{n+1}=1+1/x_n$ , $x_0=1$ .

Plan. Use the reciprocal update, retaining full precision through its alternating values.

\begin{aligned} x_1&=1+1/1=2 && \text{new update}\\ x_2&=1+1/2=\frac32 && \text{cross back}\\ x_3&=1+1/(3/2)=\frac53 && \text{cross again}\\ x_4&=1+1/(5/3)=\frac85 && \text{same recurrence} \end{aligned}

The later output is:

$n$	$x_n$ , displayed to eight decimal places
$12$	$1.61802575$
$13$	$1.61803714$
$14$	$1.61803279$

Why this step? Here values alternate across the fixed point; a trace that increases every time would not represent this update.

Answer. Again $\alpha=1.6180$ to four decimal places, certified by the same $f(1.61795)<0<f(1.61805)$ test.

Check. The early fractions are $2/1,3/2,5/3,8/5$ : each new numerator is the sum of the previous numerator and denominator, which also explains the next fraction $13/8$ .

The opening equation therefore has the same positive answer but different routes. In a spreadsheet with iterates in column $\text{B}$ , the updates are $=\operatorname{SQRT}(\text{B2}+1)$ or $=1+1/\text{B2}$ , copied down from $\text{B3}$ .

Watch out

Wrong: a successful rearrangement guarantees every rearrangement will converge from every start. Right: it defines a different iteration; inspect the graph, domains and output for the one actually used.

Use a new square-root update.

Newton-Raphson follows a tangent to the axis

Newton-Raphson replaces the curve locally by its tangent. At $x_n$ , the tangent has equation

y=f(x_n)+f'(x_n)(x-x_n)

Its horizontal-axis intercept is the next approximation.

Newton-Raphson

x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}

The function and derivative must be defined, with $f'(x_n)\ne0$ . An intercept can leave the initial neighbourhood, so check that later steps remain meaningful.

In the formula booklet.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

Ne1, Ne2 - Fixed point iteration and Newton-Raphson

A rearrangement chooses an iteration

Newton-Raphson follows a tangent to the axis

Continue this lesson.

Learn faster with Nova