The question is, "Show that the Newton-Raphson method of the form $$x_{n+1}= \frac{12x_n-5x_n^3}{8}$$ can be used to estimate $\sqrt{0.8}$. Show that this method will converge if the initial estimate $x_1$ satisfies $\sqrt{4/15}\lt x_1\lt\sqrt{4/3}$."

I tried to write the given equation in the form of Newton Raphson equation and find the function $f(x)$ and then show that when $f(x)=0$, $x=\sqrt{4/5}$. But I couldn't find the $f(x)$. Is there any specific method to find the $f(x)$ in such cases? Please help.

up vote 3 down vote accepted

We concentrate on a part of your question, the choice of $f$. Instead of pulling an answer out of a hat, we wander around systematically for a while. Your recurrence is, I believe (edit: verified in a comment), $$x_{n+1}=\frac{12x_n -5x_n^3}{8}.\tag{1}$$ The general Newton-Raphson recurrence is $$x_{n+1}=x_n - \frac{f(x_n)}{f'(x_n)}.\tag{2}$$ Note that (1) can be rewritten as $$x_{n+1}=x_n- \frac{5x_n^3-4x_n}{8}.\tag{3}$$ Comparing (2) and (3), and changing $x_n$ to $x$, and taking the reciprocal, we get $$\frac{f'(x)}{f(x)}=\frac{8}{5x^3-4x}.$$ This is a separable differential equation, which we can solve.

Thie above in some sense answers the question of how we obtain $f(x)$ from the recurrence. So much for generalities. Solving the DE, or by inspection, we see that $$f(x)=\frac{5x^2-4}{x^2}=5-\frac{4}{x^2}$$ does the job.

Remark: More generally, let us solve $x^2-a=0$, using the function $f(x)=1-\frac{a}{x^2}$. Then $f'(x)=\frac{2a}{x^3}$, and the Newton-Raphson iteration is $$x_{n+1}=x_n -\frac{1-a/x_n^2}{2a/x_n^3}=\frac{3x_n}{2}-\frac{x_n^3}{2a}.$$ The nice thing here is that division need not be part of the algorithm, for we can precompute $\frac{1}{2a}$ and just use multiplication.

By way of contrast, the usual Newton Method choice $f(x)=x^2-a$ involves division by varyign quantities. That could be significant in certain hardware limited settings.

  • Thank you. This is exactly what I wanted to learn. – user46044 Dec 3 '14 at 17:54
  • You are welcome. You asked an interesting question. You may have seen the related "trick" of using the Newton Method for calculating the reciprocal, in a setting where we have hardware addition/subtraction and multiplication, but not division. – André Nicolas Dec 3 '14 at 17:59

What is the fixed point?

Let $$ g\left(x\right)\equiv\frac{12x-5x^{3}}{8}. $$ Then, the scheme can be written $$ x_{n+1}=g\left(x_{n}\right). $$ Suppose there exists a positive ($x^{\star}>0$) fixed point (i.e. $x^{\star}=g\left(x^{\star}\right)$). Then, $$ x^{\star}=\frac{12x^{\star}-5\left(x^{\star}\right)^{3}}{8}. $$ Dividing this equation by $x^{\star}$, $$ 1=\frac{12}{8}-\frac{5}{8}\left(x^{\star}\right)^{2}. $$ Simplifying yields $x^{\star}=\sqrt{4/5}=\sqrt{0.8}$ (remember, $x^{\star}$ was chosen to be positive).

Note: Your question asked for $f\left(x^\star\right)=0$. Just define $f$ by $f\left(x\right)\equiv g\left(x\right)-x$.

Proving the fixed point exists (and is unique)

Now, consider the interval $$X\equiv\left[\sqrt{4/15},\sqrt{4/5}\right].$$ We want to show that $$ g\left(X\right)\subset X $$ and $$ \forall x\in X\colon\left|g^{\prime}\left(x\right)\right|<1. $$ These two facts allow us to show (see Banach fixed point theorem) that $x_{n}\rightarrow x^{\star}$ if the initial guess is chosen in $X$.

First, note that $$ g^{\prime}\left(x\right)=\frac{12-15x^{2}}{8}. $$ It can be shown that $g^{\prime}\geq 0$ on $X$ (exercise!). Since $g\left(\sqrt{4/15}\right)\in X$ (exercise!) and $g\left(\sqrt{4/5}\right)=\sqrt{4/5}$ (we already proved this in the above section), we conclude that $g\left(X\right)\subset X$.

Second, note that $g^{\prime\prime}<0$ on $X$ and $g^{\prime}\geq0$ on $X$. Since $$ g^{\prime}\left(\sqrt{4/5}\right)<g^{\prime}\left(\sqrt{4/15}\right)<1, $$ we are done.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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