2
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thank you! That's really interesting. $\endgroup$ Commented Dec 10, 2014 at 17:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .