I have some trouble solving a problem in my textbook:
Given the following function: $$f(x) = x^{-1} – R$$
Assume $R > 0$. Write a short algorithm to find $1/R$ by Newton's method applied to $f$. Do not use division or exponentiation in the algorithm. For positive $R$, what starting points are suitable?
OK, so I've managed to solve the first part of the problem. Using Newton's method and rearranging terms I have gotten:
$$x_{n+1} = x_{n}(2 – Rx_{n})$$
This is correct according to the book, and I can just use my standard algorithm for Newton's method with this expression. So far so good.
The problem is the second part, where I am supposed to find suitable starting points. I figured that if $x_{1} = -x_{0}$, then the iterations cycle. So then I get:
$$\begin{align*}
-x_{0} &= x_{0}(2 – Rx_{0})\\
-3x_{0} &= – Rx_{0}^2\\
-3 &= -Rx_{0}\\
x_{0} &= 3/R
\end{align*}$$
Thus my answer would be that we must have $x_{0} < 3/R$. My book, however, says:
If $R > 1$ then the starting point $x_{0}$ should be close to $0$ but smaller than $1/R$.
So what is wrong with my reasoning here? If anyone can help me out, I would really appreciate it!
Best Answer
I presume the restriction on division applies to choosing a starting point as well?
The function $f$ is strictly decreasing on the domain $(0,\infty)$, $\lim_{x \downarrow 0} f(x) = \infty$, $\lim_{x\to \infty} f(x) = -R$, hence there exists a unique $x^*$ such that $f(x^*) = 0$. The picture below shows the behavior for $R=10$.
Furthermore, $f$ is strictly convex on its domain, which means, in this case, if an iteration $x_n$ satisfies $x_n < x^*$, then it is easy to show that $x_n < x_{n+1} \leq x^*$. Furthermore, if $x_n>x^*$, and if $x_{n+1}$ lies in the domain of $f$, then $x_{n+1} \leq x^*$.
So, the only real restriction on a starting point is to ensure that $x_1 \in (0, \infty)$ so that subsequent iterations are well defined. In this case, you have $x_1 = x_0(2-R x_0)$, giving $x_1>0$ iff $x_0 < \frac{2}{R}$.
So the answer is that Newton's method will converge iff you start with $0 < x_0 < \frac{2}{R}$, or, since you are not allowed division, choose $x_0>0$ such that $R x_0 < 2$.
It is instructive to look at the Newton iteration itself. In this case, $\phi(x) = x(2-Rx)$ defines the iteration scheme (ie, $\phi_{n+1} = \phi(x_n)$). We know the solution is a fixed point of $\phi$, that is $\phi(\frac{1}{R}) = \frac{1}{R}$, which gives $\phi(x) - \phi(\frac{1}{R}) = - R (x-\frac{1}{R})^2$. So we have $|\phi(x) - \phi(\frac{1}{R})| = (R |x-\frac{1}{R}|) |x-\frac{1}{R}|$. This is a contraction whenever $x \in (0, \frac{2}{R})$. However, as $x$ gets closer to $\frac{1}{R}$, the 'error' term (ie, distance between $x_n$ and the solution $\frac{1}{R}$) drops with the square of the previous error (ignoring the $R$ for simplicity), which gives Newton's method its so called quadratic convergence rate.