Finding the function when the Newton-Rapson formula is give.

Question

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.

Answer 1

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.

Answer 2

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.