High iteration Newton's Method

Question

Suppose newton's iteration method is applied to $f(x)=1/x$ with $x_{0}=1$. Find $x_{50}$.

So for me it seems like that newton's method is trying to approximate the root of the function.

From Newton's Method

$x_{i+1}=x_{i}-\frac{f(x_{i})}{f'(x_{i})}$

So

\begin{align*} x_{i+1}=x_{i}-\frac{\frac{1}{x_{i}}}{-\frac{1}{x^2_{i}}}=x_{i}+x_{i} \end{align*} From the above relation, we can compute the first values \begin{align*} x_{1}&=x_{0}+x_{0}=2\\ x_{2}&=x_{1}+x_{1}=4\\ x_{3}&=x_{2}+x_{2}=8\\ x_{4}&=x_{3}+x_{3}=16\\ x_{5}&=x_{4}+x_{4}=32 \end{align*} So \begin{align*} x_{0}&=1\\ x_{1}&=x_{0} \cdot 2\\ x_{2}&=x_{0} \cdot 2^2\\ x_{3}&=x_{0} \cdot 2^3\\ x_{n}&=x_{0} \cdot 2^n \end{align*}

Therefore

$x_{50}=2^{50}$ I just think my result looks strange, does it just mean what we can see intuitively that the function has no roots?

Answer 1

Your result is correct, $x_n = 2^n x_0$.

The case of $f(x) = \frac{1}{x}$ if a good example of what can go wrong. There is no root to find as $f(x) \not = 0$ for all $x \not =0$. The absolute value of the residual, i.e., $|f(x_n)|$, converges to zero, while $|x_n| \rightarrow \infty$. If the residual is used to terminate the iteration, then the user will be given the wrong impression, i.e., a root has been found. The morale is two-fold 1) do not feed your software a problem which cannot be solved, 2) always look at the intermediate results.

A good implementation of Newton's method will not rely on Newton's method alone. It will accept a bracket, i.e. an interval $[a,b]$ such that $f(a)$ and $f(b)$ have opposite signs and $f : [a,b] \rightarrow \mathbb{R}$ is continuous. It will systematically shrink the bracket using a combination of Newton's method and bisection.

---

EDIT: In response to OP's comment.

A formal proof of the fact that $x_n = 2^n x_0$ can be done as follows. Let $V \subseteq \mathbb{N}$ be given by $$ V = \{ n \in \mathbb{N} \: : x_n = 2^n x_0\}.$$ We must show that $1 \in V$ and if $k \in V$, then $k+1 \in V$.

It has already been established that $$x_{n+1} = 2 x_n, \quad n=0,1,2\dotsc.$$ In particular, $$x_1 = 2 x_0 = 2^1 x_0,$$ or equivalently, $1 \in V$.

Now suppose that $k \in V$. We must show that $k+1 \in V$, i.e., $x_{k+1} = 2^{k+1} x_0$. By assumption, $x_k = 2^{k} x_0$. Therefore, $$x_{k+1} = 2 x_k = 2 (2^k x_0) = 2^{k+1} x_0.$$ We conclude that $k+1 \in V$.

By the principle of mathematical induction, we can now conclude that $V = \mathbb{N}$.

Comment: Depending on the situation, such formalism is overkill. However, it is good practice to write clearly about simple matters. How else can one learn to write clearly about complicated matters?

Answer 2

Consider the point at which the function $f(x)=0$. It's impossible for this to be true. In fact: $$\lim_{x\to 0^+}{\frac{1}{x}}=\infty$$ In short, what you are attempting to do is find some $x$ such that $f(x)=0$, and each time you perform the iterative again you will get closer to the root, which you can see as your $$\lim_{i\to \infty}{x_i}=\infty$$

Answer 3

It is correct as root of 1/x is infinity Sometimes the newtons method gives weird results when the root is a complex number but it gives correct answer in most of the cases