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