A logarithmic fixed-point iteration

Supplied graph with axes x and y, vertical asymptote x=1 and roots α and β.y = ln(x−1) − x + 4. Native mathematical paths and source labels.xy1αβ
Question diagram 1
Supplied graph with axes x and y, vertical asymptote x=1 and roots α and β.y = ln(x−1) − x + 4. Native mathematical paths and source labels.xy1αβ

Supplied graph with axes x and y, vertical asymptote x=1 and roots α and β.

The diagram shows y=ln⁡(x−1)−x+4y=\ln(x-1)-x+4. Its roots are α,β\alpha,\beta, with α<β\alpha<\beta.

(i) Find α,β\alpha,\beta correct to 3 decimal places. marks

A sequence of real numbers satisfies xn+1=ln⁡(xn−1)+4x_{n+1}=\ln(x_n-1)+4, n≥1n\ge1.

(ii) Prove algebraically that if the sequence converges, it converges to either α\alpha or β\beta. marks

(iii) By considering the maximum point of y=ln⁡(x−1)−x+4y=\ln(x-1)-x+4, show xn+1≤xn+2x_{n+1}\le x_n+2. marks

[2012/MI/Prelim/10]

Total marks: 8

Solution

(i)

Find the two roots

The diagram shows y=ln⁡(x−1)−x+4y=\ln(x-1)-x+4, with roots α<β\alpha<\beta. Find α\alpha and β\beta correct to 3 decimal places.

Explore this idea

Hint

  1. Remember the domain: x>1x>1.

  2. Use a graphing calculator's intersection or root finder for each crossing.

Answer · (i)

α=1.052,β=5.505\alpha=1.052,\beta=5.505 (3 d.p.).

Explore the idea

The roots are where the curve meets the diagonal

Start at the chosen value on the horizontal axis, go up to the curve, across to the diagonal, and repeat. Each corner of the web is the next term.

Starting valueu₁ = 3
Iterations drawn4
Try an example
u(n = 5)
5.49518
u(n = 1)
3
Distance to β ≈ 5.505
0.01007
Key idea

Solving x=ln⁡(x−1)+4x=\ln(x-1)+4 is the same as solving ln⁡(x−1)−x+4=0\ln(x-1)-x+4=0: a root of the graph is a fixed point of the iteration.

Ideas to try
  1. Find the two points where the teal curve crosses the red diagonal. Their xx-coordinates are α\alpha and β\beta.
  2. Start at 33 and add iterations: the web is drawn toward β\beta but pushed away from α\alpha.
(ii)

Algebraic limit argument

For xn+1=ln⁡(xn−1)+4x_{n+1}=\ln(x_n-1)+4, prove algebraically that if the sequence converges, it converges to either α\alpha or β\beta.

Explore this idea

Hint

  1. Assume the limit LL exists and is finite.

  2. Rule out the boundary L=1L=1.

  3. Take limits in the recurrence and recognise the equation from part (i).

Answer · (ii)

Any finite limit is α\alpha or β\beta.

Every recurrence step must be defined; limit 1 is impossible.

Explore the idea

Which fixed point attracts?

Start at the chosen value on the horizontal axis, go up to the curve, across to the diagonal, and repeat. Each corner of the web is the next term.

Starting valueu₁ = 2
Iterations drawn8
Try an example
u(n = 9)
5.50519
u(n = 1)
2
Distance to β
0.00005
Key idea

A fixed point is necessary for convergence, not sufficient. Here only β\beta attracts: the curve is steep at α\alpha and flatter than the diagonal at β\beta.

Ideas to try
  1. Try several starting values above 1.21.2. Where do they all end up?
  2. A fixed point only says where a limit could be. Check the distance readout to see which one the terms actually approach.
(iii)

Bound the increment

By considering the maximum point of y=ln⁡(x−1)−x+4y=\ln(x-1)-x+4, show that xn+1≤xn+2x_{n+1}\le x_n+2.

Explore this idea

Hint

  1. Identify the graph's height with the step xn+1−xnx_{n+1}-x_n.

  2. Find the graph's maximum.

Answer · (iii)

h(x)≤h(2)=2h(x)\le h(2)=2, so xn+1≤xn+2x_{n+1}\le x_n+2.

xn>1x_n>1.

Explore the idea

The increment never exceeds 2

Switch to the increment plot. Its height at the current term is the step to the next term.

Starting valueu₁ = 2
Iterations drawn0
Try an example
u(n = 1)
2
u(n = 1)
2
Distance to α
0.94753
Key idea

The increment curve is the picture of xn+1−xnx_{n+1}-x_n. Its maximum value 22 at x=2x=2 is the most any step can add.

Ideas to try
  1. Open the increment plot and move the start. The dot rides the curve and never rises above 22.
  2. Where the curve is above the axis the term increases; where it is below, the term decreases.
Takeaway

One graph, two readings

Where h(x)=0h(x)=0 the iteration stands still; the height of hh elsewhere is the size and direction of each step.