# How can I determine the convergence rate of recurrence methods?

I want to solve the equation $$x^{3}-x-1=0$$ by iterating recurrence equations.

I have two different recurrence relations for solving this equation:

1. $$x_{k+1}=\sqrt[3]{x_{k}+1} \quad(k=0,1, \cdots)$$

2. $$x_{k+1}=\frac{2 x_{k}^{3}+1}{3 x_{k}^{2}-1} \quad(k=0,1, \cdots)$$

I have known that the first recurrence relation has linear convergence and the second has at least second order convergence.

How can I use Mathematica to verify this conclusion?

This is code I use to iterate my recurrence relations:

NestList[Power[# + 1, (3)^-1] &, 1., 5]
NestList[(2 #^3 + 1)/(3 #^2 - 1) &, 1., 5]

• Compare Length@FixedPointList[(# + 1)^(1/3) &, 1.] with Length@FixedPointList[(2 #^3 + 1)/(3 #^2 - 1) &, 1.] Commented Oct 1, 2020 at 3:15
• @BobHanlon Thank you very much for your comments. I have written an answer. If you can, I'd like to get more ingenious methods from you. Commented Oct 1, 2020 at 9:02

Method 1:

By using theorem 4 on page 219 of this book, we can easily obtain the convergence rates of these two iterative methods:

φ1[x_] := Power[x + 1, (3)^-1]
(D[φ1[x], x] /. x -> SuperStar[x]) //
FullSimplify[#, (SuperStar[x])^3 - (SuperStar[x]) - 1 == 0] &

φ2[x_] := (2 (x)^3 + 1)/(3 (x)^2 - 1)

(D[φ2[x], x] /. x -> SuperStar[x]) //
FullSimplify[#, (SuperStar[x])^3 - (SuperStar[x]) - 1 == 0] &
(D[φ2[x], x, x] /. x -> SuperStar[x]) //
FullSimplify[#, (SuperStar[x])^3 - (SuperStar[x]) - 1 == 0] &


So the first recurrence relation has linear convergence and the second has second order convergence.

Method 2:

Let a root of equation $$x^{3}-x-1=0$$ be $${x}^{*}$$, then $${({x}^{*})}^{3}-{x}^{*}-1=0$$.

Let $$x_{k}=x^{*}+\varepsilon$$, where $$\varepsilon$$ is the iteration error, then there is the following relationship:

$$\begin{array}{l} {x}_{{k}+1}-{x}^{*}=\sqrt[3]{{x}_{{k}}+1}-\sqrt[3]{{x}^{*}+1}=\sqrt[3]{{x}^{*}+\varepsilon+1}-\sqrt[3]{{x}^{*}+1} \\ {x}_{{k}+1}-{x}^{*}=\frac{2 {x}_{{k}}^{3}+1}{3 {x}_{{k}}^{2}-1}-\frac{2\left({x}^{*}\right)^{3}+1}{3\left({x}^{*}\right)^{2}-1}=\frac{2\left({x}^{*}+\varepsilon\right)^{3}+1}{3\left({x}^{*}+\varepsilon\right)^{2}-1}-\frac{2\left({x}^{*}\right)^{3}+1}{3\left({x}^{\star}\right)^{2}-1} \end{array}$$

The above expressions are expanded into Taylor series at $$\varepsilon=0$$:

Series[Power[SuperStar[x] + ε + 1, (3)^-1] - Power[
SuperStar[x] + 1, (3)^-1], {ε, 0, 3}] // FullSimplify
Series[(2 (SuperStar[x] + ε)^3 + 1)/(
3 (SuperStar[x] + ε)^2 - 1) - (
2 (SuperStar[x])^3 + 1)/(3 (SuperStar[x])^2 - 1), {ε,
0, 3}] //
FullSimplify[#, (SuperStar[x])^3 - (SuperStar[x]) - 1 == 0] &


Then we can get the same conclusion.

Method 3:

With the help of Michael E2, I draw the error scatter diagram of two iterative methods:

ListPlot@Block[{$$MinPrecision = 50,$$MaxPrecision = 50},
Log[Table[
Abs[Nest[Power[# + 1, (3)^-1] &, 1., i] -
Root[#^3 - # - 1 &, 1]], {i, 1, 10, 1}]]]
ListPlot@Block[{$$MinPrecision = 1000,$$MaxPrecision = 1000},
Log[Table[
Abs[Nest[(2 #^3 + 1)/(3 #^2 - 1) &, 1.1000, i] -
Root[#^3 - # - 1 &, 1]], {i, 1, 10, 1}]]]
`