Iteration and Newton-Raphson

Iteration and Newton-Raphson

Spec I2 · AQA A-Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • An iteration xn+1=g(xn)x_{n+1}=g(x_n) that converges to α\alpha gives a root of x=g(x)x=g(x).
  • It converges if ∣g′(α)∣<1|g'(\alpha)|<1: a staircase if g′>0g'>0, a cobweb if g′<0g'<0. It diverges if ∣g′(α)∣>1|g'(\alpha)|>1.
  • Newton-Raphson: xn+1=xn−f(xn)f′(xn)x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.
  • Newton-Raphson fails if f′(xn)=0f'(x_n)=0, and can reach a different root.
  • Use the ANS key so each step keeps the full calculator value.

Iterative methods

Rearrange f(x)=0f(x)=0 into x=g(x)x=g(x) and feed each answer back in; if the terms settle, the limit is a root.

An iteration (recurrence relation) xn+1=g(xn)x_{n+1}=g(x_n) generates a sequence from a starting value. To solve f(x)=0f(x)=0, rearrange it into x=g(x)x=g(x). For x3+x−3=0x^3+x-3=0: x3=3−xx^3=3-x, so xn+1=3−xn3x_{n+1}=\sqrt[3]{3-x_n}.

If the sequence converges to α\alpha, then α=g(α)\alpha=g(\alpha), so α\alpha is a root of the original equation. Keep full calculator values (use ANS) and stop when successive terms agree to the required accuracy.

00.20.40.60.811.201234nx_n
Iterates of xn+1=3−xn3x_{n+1}=\sqrt[3]{3-x_n} from x0=1x_0=1: they alternate either side of the root and settle near 1.2131.213.

Worked example

Use xn+1=3−xn3x_{n+1}=\sqrt[3]{3-x_n} with x0=1x_0=1 to find a root of x3+x−3=0x^3+x-3=0.

Which is a correct rearrangement of x3+2x−5=0x^3+2x-5=0 into the form x=g(x)x=g(x)?

Staircase and cobweb diagrams

Draw y=xy=x and y=g(x)y=g(x); go vertically to the curve, then horizontally to the line, and repeat.

Draw y=xy=x and y=g(x)y=g(x). From x0x_0 go vertically to the curve, then horizontally to y=xy=x, and repeat. A staircase diagram converges from one side; a cobweb diagram spirals in with terms alternating either side of α\alpha.

For g(x)=3−x3g(x)=\sqrt[3]{3-x}, g′(x)=−13(3−x)−2/3≈−0.23g'(x)=-\frac13(3-x)^{-2/3}\approx-0.23 at α=1.213\alpha=1.213. Since −1<g′(α)<0-1<g'(\alpha)<0, it converges in a cobweb.

0.80.911.11.21.31.41.51.60.80.911.11.21.31.41.51.6xy(x₀, x₁)(x₁, x₂)αy = ∛(3 − x)y = x
Cobweb for xn+1=3−xn3x_{n+1}=\sqrt[3]{3-x_n} from x0=1x_0=1, closing in on α\alpha.

0 < g′(α) < 1

  • Staircase
  • Converges from one side

−1 < g′(α) < 0

  • Cobweb
  • Converges, alternating

|g′(α)| > 1

  • Moves away
  • Diverges

Near the root, g′(α)=−0.6g'(\alpha)=-0.6. What does the iteration do?

Newton-Raphson

The tangent at xnx_n meets the xx-axis at xn+1=xn−f(xn)f′(xn)x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.

The Newton-Raphson method uses a tangent to the curve. The tangent at xnx_n meets the xx-axis at xn+1=xn−f(xn)f′(xn)x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}. It usually converges very quickly when x0x_0 is close to the root.

Check your answer by evaluating ff just above and below it to confirm a sign change.

0.511.522.533.54−8−6−4−2246810xy(3, 2)x₁ = 8/3√7y = x² − 7tangent at x = 3
Tangent to y=x2−7y=x^2-7 at x=3x=3 meets the xx-axis at 83\frac83, near 7\sqrt7.
  • xn+1x_{n+1}xn−f(xn)f′(xn)x_n-\dfrac{f(x_n)}{f'(x_n)}

Worked example

Use Newton-Raphson on f(x)=x2−7f(x)=x^2-7 with x0=3x_0=3.

Worked example

Find the root of x3−2x−5=0x^3-2x-5=0 near 22, using x0=2x_0=2.

For f(x)=x2−5f(x)=x^2-5 and x0=2x_0=2, what is x1x_1?

How the methods can fail

An iteration diverges if ∣g′∣>1|g'|>1 near the root; Newton-Raphson fails if f′(xn)=0f'(x_n)=0.

Iteration: the sequence diverges if ∣g′∣>1|g'|>1 near the root. The rearrangement xn+1=xn3+13x_{n+1}=\frac{x_n^3+1}{3} for x3−3x+1=0x^3-3x+1=0 has g′(x)=x2g'(x)=x^2, greater than 11 at the root 1.5321.532. Starting at 1.61.6 gives 1.6991.699, 1.9671.967, moving away.

Newton-Raphson: it fails if f′(xn)=0f'(x_n)=0 because a horizontal tangent never meets the axis and the formula divides by zero. It can also converge to a different root, or oscillate, if x0x_0 is near a stationary point or far from the root.

−2.5−2−1.5−1−0.50.511.522.5−4−2246xy(1, −1)1.5320.347−1.879y = x³ − 3x + 1tangent at x = 1
f′(1)=0f'(1)=0: the tangent at x=1x=1 is horizontal, so x0=1x_0=1 fails.

Why does Newton-Raphson fail for x3−3x+1=0x^3-3x+1=0 with x0=1x_0=1?

Try an exam question

Use the Newton-Raphson method with x0=1x_0=1 to find x2x_2 for the equation x3+x−3=0x^3+x-3=0. Give your answer to 44 decimal places.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Find x1x_1, to 2 decimal places.

1 mark, marked against the mark scheme

Revision notes