0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How are u sure that the convergence is of order $2$ with the Newton method? In fact, How are u sure that it even converges? $\endgroup$ – Season Four Oct 28 '17 at 12:50
  • $\begingroup$ Newton's method locally converges. For this function, which is increasing and convex, Newton's method will converge for any initial value right from the root, and one can confirm that any point left to the root will in the first iteration move to right of the root. Look up the Babylonian method, this is similar. $\endgroup$ – LutzL Oct 28 '17 at 12:53
  • $\begingroup$ Assuming I agree that it converges, I still don't know why the order is $2$. Can you prove it? $\endgroup$ – Season Four Oct 28 '17 at 15:59
  • $\begingroup$ Because the Newton method for any simple root of any twice differentiable function has convergence order 2. And as Aitken is related to Newton, it also has order 2. $\endgroup$ – LutzL Oct 28 '17 at 17:21
0
$\begingroup$

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}}$.

$\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.