How can I determine the convergence rate of recurrence methods?

Question

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]

Answer 1

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}]]]