### newton´s method

LaTeX4Web 1.4 OUTPUT Newton¢s method is used to find the roots of a given polynomial. That is, we want to find x so that f(x)=0. We first need to determine a x0 which is close to the actual root x. If we take the tangent line to x0 and we determine when does it cross the x-axis we will then obtain a x1 which is much closer to the root that we are looking for. The following picture illustrates the method:
LaTeX4Web 1.4 OUTPUT y = f(x0) + f¢(x0)(x-x0). We take the example y=x2 -2. We know that the root is approximately 1.5, and we begin with this x0. Then the image at this point is
y = (1.5)2 - 2 = 0.25.
Then we compute the tangent line at this point. The derivative of x2 -2 i 2x and then substituting x by 1.5 we obtain that the slope of the tangent line equals 3. Hence, the equation of the tangent line is
y = 3(x-1.5) + 0.25
y = 3x - 4.25.
If we solve for x when y equals 0 (crosses the x-axis) we obtain that x equals 1.4166. Then we repeat this process until we obtain enough exact decimals. Then in general the Newton Method uses the recursion
xn+1 = xn - (f(xn))/(f¢(xn)).
However, this method presents two problems: firstly, the last equation cannot be computed if f¢(xn) equals 0. Secondly, it does not distinguish between simple and multiple roots. On the other hand, in general all the roots of a polynomial can be found in one interval that can be determined.

We also provide the code for Newton's Method. We use five iterations for the decimals.

 newton.txt Size : 2.981 Kb Type : txt
LaTeX4Web 1.4 OUTPUT Here you can see an example of the code. We use the polynomial x2 -2. Its roots are -Ö2 and Ö2. You can see that with five decimals the result is very close to the square root of 2.
LaTeX4Web 1.4 OUTPUT For the code it is necessary to know the interval in which all the roots of the polynomial lie. We use the fact that if we sum in absolute value all the coefficients of a polynomial we obtain a value a. Then, all the roots of the polynomial lie between -a and a. We now prove this claim. Let p(x) be a polynomial of integer coefficients
p(x) = xn + an-1xn-1 + ... + a2x2 + a1x + a0.
Let a be a root of p(x). This means that p(a)=0. Knowing that
|x|+ |y| ³ |x+y|,
we evaluate p(a)=0. Then,
an = -an-1an-1 - ... -a2a2 - a1a - a0.
Using the absolute value we obtain
|a|n = |an-1an-1 + ... + a1a + a0| £ |an-1||a|n-1 + ... + |a1||a| + |a0|.
If a is bigger than 1 it follows that the previous expression is smaller or equal than
|an-1||a|n-1 + ... + |a1||a|n-1 + |a0||a|n-1 = |a|n-1 (|an-1| + ... + |a1| + |a0|).
If we then divide we obtain that
|a| £ an-1 + ... + |a1| + |a0| < M
where M is defined as 1 + |a0| + ... + |an-1|. Since |a| £ M we know that a Î [-M, M] and the proof is complete.