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}]]]
Length@FixedPointList[(# + 1)^(1/3) &, 1.]
withLength@FixedPointList[(2 #^3 + 1)/(3 #^2 - 1) &, 1.]
$\endgroup$ – Bob Hanlon Oct 1 '20 at 3:15