# Newton method why the error is proportional to the square for the error of the last one?

We have learned that the Newton method is used to solve different equations. As I know, this method is iterative, which means that using an estimate point and using a loop, we can get closer and closer to the exact solution, until the tolerance hit the zero.

It is bit hard for me to understand this concept. Basically I saw somewhere that this method is approximately proportional to the square of the previous one.

|xi+1 −y|≈q*|xi −y|^2


Where q is a constant and y is the exact solution.

Can you explain me why this is true for this algorithm?

Consider the Taylor series of a function about some point $x_n$ truncated at the linear term:

$$f(x) = f(x_n) + f'(x_n)(x-x_n) + R(x)$$

where $R$ is the remainder. You should know that $R \sim \mathcal{O}\left( (x-x_n)^2\right)$ (there are a few ways to write the remainder, but this is sufficient).

Let's set $x=a$, where $a$ is a root of the polynomial. Then we get

$$f(a) = 0 = f(x_n) + f'(x_n)(a-x_n) + R(a).$$

Re-arranging, we find

$$-\frac{f(x_n)}{f'(x_n)} + x_n = a + \frac{R(a)}{f'(x_n)}.$$

Note that the left-hand side looks a whole lot like Newton's method.

Set $x_{n+1}$ equal to this left hand side, and we get

$$\underbrace{x_{n+1}-a}_{\epsilon} = \frac{R(a)}{f'(x_n)}.$$

Noting that $f'(x_n)$ is just a number, we can say that $|\epsilon| \propto (x_n-a)^2,$ this right-hand side coming from the definition of the remainder.

• thank you! That's really interesting. Commented Dec 10, 2014 at 17:42