Provide a fixed-iteration method for computing $a^{\frac{1}{n}}$ such that the order of convergence is $2$

Question

We can approximate $a^\frac{1}{n}$ by fixed-iteration method. This method says, instead of finding a function $f$ such that $f(a^\frac{1}{n})=0$, find another function $g$ such that $g(a^\frac{1}{n})=a^\frac{1}{n}$.

If the domain of this $g$ is a subset of its range, and $|g(x)|<1$, for all $x$ in the domain of $g$, then we can be sure that no matter what $x_0$ we choose, the sequence made by fixed-point iteration will definitely converge to $a^\frac{1}{n}$.

The definition of convergence of order $p$ to $\alpha$ is that $\operatorname{lim}_{n\to\infty}\frac{|x_{n+1}-\alpha|}{|x_n-\alpha|^p}=\lambda$ such that $\lambda$ and $p$ are two positive constants.

The question asks for a $g$ such that $g(a^\frac{1}{n})=a^\frac{1}{n}$ and the order of the convergence should be $2$.

Note: $a$ is a positive number. ($a\gt 0$)

My problem is not finding a $g$ such that $g(a^\frac{1}{n})=a^\frac{1}{n}$, but holding the condition that the order of convergence should be $2$ is a bit of mystery to me. Also, I want a method which works for any value of $x_0$.

Any idea?

Answer 1

Two of many possibilities are:

• Use the Newton method on any variation of $f(x)=x^n-a$.

• Find any contractive method, usually of the form $x_+=x-q(x)f(x)$, and apply the Aitken delta-squared process on it.

Answer 2

Newton's Method for solving $x^n=a$: $$ x_{k+1}=\frac{n-1}nx_k+\frac a{nx_k^{n-1}} $$ gives $$ \begin{align} x_{k+1}-a^{1/n} &=\frac{n-1}nx_k+\frac a{nx_k^{n-1}}-a^{1/n}\\ &=\left(x_k-a^{1/n}\right)-\frac{x_k^n-a}{nx_k^{n-1}}\\ &=\left(x_k-a^{1/n}\right)-\frac{x_k}n\left(1-\frac a{x_k^n}\right)\\ &=\left(x_k-a^{1/n}\right)-\left(x_k-a^{1/n}\right)\frac1n\sum_{j=0}^{n-1}\frac{a^{j/n}}{x_k^j}\\ &=\left(x_k-a^{1/n}\right)\frac1n\sum_{j=0}^{n-1}\left(1-\frac{a^{j/n}}{x_k^j}\right)\\ &=\left(x_k-a^{1/n}\right)^2\frac1{nx_k}\sum_{j=0}^{n-1}\sum_{i=0}^{j-1}\frac{a^{i/n}}{x_k^i}\\ &=\left(x_k-a^{1/n}\right)^2\frac1{nx_k}\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}\frac{a^{i/n}}{x_k^i}\\ &=\left(x_k-a^{1/n}\right)^2\frac1{nx_k}\sum_{i=0}^{n-2}(n-i-1)\frac{a^{i/n}}{x_k^i}\\ &\sim\left(x_k-a^{1/n}\right)^2\frac1{na^{1/n}}\sum_{i=0}^{n-2}(n-i-1)\\[6pt] &=\frac{n-1}{2a^{1/n}}\left(x_k-a^{1/n}\right)^2 \end{align} $$ where the $\sim$ means we have approximated $x_k$ by $a^{1/n}$.

Thus, if we can get within $\frac{2a^{1/n}}{n-1}$ of the root, the convergence will be of order $2$ and $\lambda=\frac{n-1}{2a^{1/n}}$.