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.