1
$\begingroup$

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]
$\endgroup$
2
  • 2
    $\begingroup$ Compare Length@FixedPointList[(# + 1)^(1/3) &, 1.] with Length@FixedPointList[(2 #^3 + 1)/(3 #^2 - 1) &, 1.] $\endgroup$ – Bob Hanlon Oct 1 '20 at 3:15
  • $\begingroup$ @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. $\endgroup$ – A little mouse on the pampas Oct 1 '20 at 9:02
3
$\begingroup$

Method 1:

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

enter image description here

φ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}]]]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.