High iteration Newton's Method

170 Views Asked by At

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?

3

There are 3 best solutions below

3
On BEST ANSWER

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?

0
On

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

2
On

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