Rearrange f(x)=0 as x=g(x) and repeat xn+1=g(xn)
about 30 min1 simulation2 practice questions1 Python program5 questions to check yourself
This lesson is free to read. Enroll free to keep your place and take the tests.
Lesson 2 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
rearrange an equation as x=g(x) and carry out the iteration;
draw and read staircase and cobweb diagrams;
use g′(α) to decide whether an iteration converges, and how fast.
Press the cos key again and again
Set a calculator to radians. Type any number and press cos, again and again. The display settles on 0.739085… and stays there. What has happened? You have solved x=cosx. Each press works out xn+1=cosxn, and the values close in on the one number that cos leaves unchanged.
Fixed points
A fixed point of g is a number α with g(α)=α. On a graph, it is where y=g(x) meets y=x. To solve f(x)=0, we rearrange it as x=g(x). Then a root of f is a fixed point of g, and we iterate:
xn+1=g(xn).
If the sequence converges, its limit is a fixed point, as long as g is continuous.
One equation, three rearrangements
Take x3+2x−5=0 again, with its root α≈1.3283. Start each time at x0=1.5.
x=21(5−x3). The values run 0.8125, 2.2318, −3.0583, and then grow without bound.
x=35−2x. The values run 1.2599, 1.3536, 1.3186, 1.3319, and close in on α.
x=x2+25. The values run 1.1765, 1.4775, 1.1953, 1.4583, and close in very slowly.
Why such different behaviour? Look at the slope of each g at the root: about −2.65, −0.38 and −0.94.
The rule for convergence
Let en=xn−α be the error. By the mean value theorem,
en+1=g(xn)−g(α)=g′(c)en,
for some c between xn and α. Near the root, g′(c)≈g′(α). So each step multiplies the error by about g′(α).
If ∣g′(α)∣<1, the errors shrink and the iteration converges from a start close enough to α.
If ∣g′(α)∣>1, the errors grow and the iteration moves away from α.
The smaller ∣g′(α)∣ is, the faster it converges. This is linear convergence: the error falls by a fixed factor each step.
The sign tells the shape of the path:
0<g′(α)<1: a staircase, coming in from one side;
−1<g′(α)<0: a cobweb, jumping from side to side.
For x=cosx, g′(α)=−sinα≈−0.67. That is why the calculator values jump above and below 0.739.
Two panels, each with the line y = x and a curve y = g(x) crossing it at a fixed point. On the left the curve has a positive slope less than 1, and the path of the iteration is a staircase climbing towards the fixed point from one side. On the right the curve has a negative slope, and the path is a cobweb spiralling in, the values jumping from one side of the fixed point to the other.
Reading the error ratio
You can estimate g′(α) from the iterates alone. The ratio of successive differences, xn−xn−1xn+1−xn, tends to g′(α). For the cube root rearrangement, the differences are about 0.094, −0.035 and 0.0133, and their ratios are close to −0.38.
Practise with new numbers
Try it in Python
The program runs the three rearrangements of x3+2x−5=0 side by side, and stops one when its values grow too large.
Common mistakes
Testing g′ at the wrong place. The slope that matters is g′(α), at the root, not at x0.
Thinking every rearrangement works. Each has its own g′(α).
Mixing up the shapes. A positive slope gives a staircase, a negative one a cobweb.
Stopping when two values agree to two places. With a slope near 1 the iterates creep, and the root may still be far.
Remember these
Root of f is a fixed point of g: g(α)=α.
en+1≈g′(α)en.
Converges when ∣g′(α)∣<1, runs away when ∣g′(α)∣>1.
Staircase for g′>0, cobweb for g′<0.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Show that x2−3x+1=0 can be written as x=3−x1.
For g(x)=3−x1, find g′(x). Does the iteration converge to the root near 2.618?
An iteration has g′(α)=−0.5. Describe its diagram.
Will xn+1=xn2 converge to the fixed point 1 from x0=1.1?
Why does pressing cos many times give the same number whatever you start with?
References
R. L. Burden and J. D. Faires, Numerical Analysis, Chapter 2, Fixed-Point Iteration.
Enroll free in Numerical Solution of Equations
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.