Fixed point iteration for cube root

Question

I am trying to approximate the cube root of a number using fixed point iteration. I know how to do fixedpoint iteration but , I need help in figuring out the equation x = f(x). Take x as the root and n as the number for which cube root is to be figured out.

Answer 1

@Lutz Lehmann suggests using Newton's method for the equation $$f(x) = 0,$$ where $$f(x) = x^2 - \frac{a}{x}.$$ It is clear that if $a > 0$, then $r = a^{\frac{1}{3}}$ is the only positive solution of this equation. The iteration takes the form $$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} = g(x_k)$$ where $$g(x) = x - \frac{f(x)}{f'(x)} = x - \frac{x^2 - \frac{a}{x}}{2x + \frac{a}{x^2}} = x - x \left(\frac{x^3 - a}{2x^3 + a}\right).$$ In general, the convergence of a functional iteration is determined by the derivatives at the fixed point. Specifically, if $g(r) = r$ and $$g^{(j)}(r) = 0, \quad j=1,2,\dotsc,p-1$$ then by Taylor's formula $$|r - x_{k+1}| = O(|r-x_k|^p).$$ In the case of Newton's formula, i.e., $$g(x) = x - \frac{f(x)}{f'(x)}$$ and $f(r) = 0$ and $f(x) \not = 0$, we have $$g(r) = r $$ and $$ g'(x) = 1 - \frac{f'(x)^2 - f(x)f''(x)}{f'(x)^2} = \frac{f(x)f''(x)}{f'(x)^2} $$ and $$ g''(x) = \frac{(f'(x)f''(x)+f(x)f'''(x))f'(x)^2-2 f(x)f''(x)f'(x)f''(x)}{f'(x)^4}$$ In $f(r) = 0$, then $g'(r) = 0$ and $p \ge 2$ and if $f(r) = f''(r) = 0$, then $g'(r) = g''(r) = 0$ and $p \ge 3$. It is straight forward to verify that with $f(x) = x^2 - a x^{-1}$ we have $$f'(x) = 2x + ax^{-2}$$ and $$f''(x) = 2 - 2 ax^{-3}.$$ It follows that $$f(r) = f''(r) = 0$$ where $$r = a^{\frac{1}{3}}.$$

Answer 2

The starting equation is

$$x^3=n.$$

You can try many things,

$$x=\frac n{x^2},\\x=n+x-x^3,\\x=\alpha x+\beta\frac x{n^2}+\gamma(n+n-x^2),\\\cdots$$ with $\alpha+\beta+\gamma=1$ provided the function is contracting.

As said by others, Newton's iterations will be efficient:

$$x=x-\frac{x^3-n}{3x^2}=\frac{2x^3+n}{3x^2}.$$