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 x_{0} which is close to the actual root x. If we take the tangent line to x_{0} and we determine when does it cross the x-axis we will then obtain a x_{1} which is much closer to the root that we are looking for. The following picture illustrates the method:
LaTeX4Web 1.4 OUTPUT
y = f(x_{0}) + f¢(x_{0})(x-x_{0}). We take the example y=x^{2}
-2. We know that the root is approximately 1.5, and we begin with this x_{0}. 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 x^{2}
-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 x_{n+1} = x_{n} - (f(x_{n}))/(f¢(x_{n})). However, this method presents two problems: firstly, the last equation cannot be computed if f¢(x_{n}) 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
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) = x^{n}
+ a_{n-1}x^{n-1}
+ ... + a_{2}x^{2}
+ a_{1}x + a_{0}. 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, a^{n}
= -a_{n-1}a^{n-1}
- ... -a_{2}a^{2}
- a_{1}a - a_{0}. Using the absolute value we obtain |a|^{n}
= |a_{n-1}a^{n-1}
+ ... + a_{1}a + a_{0}| £ |a_{n-1}||a|^{n-1}
+ ... + |a_{1}||a| + |a_{0}|. If a is bigger than 1 it follows that the previous expression is smaller or equal than |a_{n-1}||a|^{n-1}
+ ... + |a_{1}||a|^{n-1}
+ |a_{0}||a|^{n-1}
= |a|^{n-1}
(|a_{n-1}| + ... + |a_{1}| + |a_{0}|). If we then divide we obtain that |a| £ a_{n-1} + ... + |a_{1}| + |a_{0}| < M where M is defined as 1 + |a_{0}| + ... + |a_{n-1}|. Since |a| £ M we know that a Î [-M, M] and the proof is complete.