How do I calculate the roots of a polynomial? Don't tell me to factor. I mean how would a calculator or a computer find them? I need to be able to find roots of polynomials of up to about the fifth degree.
Newton found a very smple way to calculate roots of a polynomial very accurately. He did this without aid of a calculator or a computer. (This is especially helpful if the roots are irrational) The process is very simple. Pick a number. This can be any number, what you are doing is trying to verify a possible root. (plugging in each number draws in a tangent on the graph. Each tangent gets more and more accuarate.) Now, this is Xn Plug your Xn into here Xn+1=Xn- f(Xn)/f'(Xn) now your Xn+1 is the value obtained from plugging this in. To get to varying degrees of accuracy, try it a few times, each time replacing Xn+1 into Xn. Eventually you will come up with an extremely accurate root. For every degree, there will be another root. If you have a graphing calculator, you can usually input your equation into the graphing features, then zoom in to find the x-intercepts. Some, such as the TI-83, allow for a trace feature to find the zero by inputting a left and rght bound. It just depends on how accurate you need. Hope that helps. Please Register or Log in to view the hidden image!
another method I did not post for you would be synthetic division. this will help narrow down the gap for the roots let's take the polynomial y=x^3+2x-1 To narrow down where a root may be locate, we can use a little guesswork to its' location. (note, some polynomials will have several roots, but only one REAL root..the rest will be complex numbers) pick a number, any number... a good bet to start with is usually zero. Synthetic division works much like long division, but yields us with very useful information about the polynomiaL let's represent the equation y=x^3+2x-1 (so for later we'll need the derivative which is of course 3x^2+2) x^3 x^2 x 0l 1 0 2 -1 l_____ 0___0___0_____ 1 0 2 l_-1___ the last number, if zero, is the root... if not it simply represents the y value of the equation when the number being divided by is put into it. since our last number was a -1, we know thatit is not a root, so we can move on to another number... let's try 1 1l 1 0 2 -1 l____1__1___3___ 1 1 3 l_2__ now this tells us something. using the principles of algebra, we know that the root must be between 0 and 1 becae the function crossed from negative to positive. Now we can make a guess as to our first root now if we want to find a root, we can take a guess. umm, how about 1. seems easy enough if Xn=1 then w are left with Xn+1=1- (1^3+2(1)-1)/(3(1)^2+2) so our Xn+1=3/5 now we substitute Xn once more with 3/5 so we get the expression Xn+1=3/5-((3/5)^3+2(3/5)-1)/(3(3/5)^2+2) Xn+1=175/385,which is a very close approximation to the irrational root. the process can be repeated over and over, with the value getting more andmore exact. to find the complex roots you can use synthetic division with numbers such as i, -i, i+1, or i-1. some of my algebra may be sloppy. really quick napkin calculations, but this should help you out. . if you are at all confused about synthetic division, you can visit THIS SITE good luck Please Register or Log in to view the hidden image!
Calculators make a table of values, when Y=0 in the table, it's a root. HP calculators have a root option, as opposed to the left and right boundary for TI's. A positive 100% sure answer to this, I don't know, but I would tend to think that calculators would factor before they went through the process Upquark explained, factoring is quicker.
An example of the Newton method was requested. As posted: Newton method is Next = Last - Polynomial(Last) / Derivative(Last) Polynomial(x) = x<sup>3</sup> + 5x<sup>2</sup> + 4x - 9 There is a real root at .939 465 058 586 Derivative(x) = 3x<sup>2</sup> + 10x + 4 If you started with a guess of x = 1, the Newton method would be as follows. Polynomial(1) = 1 Derivative(1) = 17 NextGuess = 1 - 1 / 17 NextGuess = .941 176 470 588 P(.941 176 470 588) = .027 478 119 270 D(.941 176 470 588) = 16.069 204 152 NextGuess = .941 176 470 588 - .027 478 119 270 / 16.069 204 152 NextGuess = .939 466 484 266 The next iteration should result in about 8-10 digits of precision. There are various ways to find additional roots. You can use synthetic division to reduce the order of the polynomial. There are various problems with the method. If there are two or more roots that are equal, the method starts dividing nearly zero by nearly zero, resulting in overflow or failure to converge. If this happens, the multiple root is also a root of the derivative. You must find and test roots of the derivative. If there is a triple root, it is a double root of the derivative: You must find and check roots of the second derivative. If there are complex roots, the method can jump and not converge to any real root. This problem can be solved by starting over with a different initial guess. An even order polynomial might not have any real roots. See below. Synthetic division can result in loss of precision. This can be overcome by using the root of the reduced polynomial as an initial guess for the Newton method applied to the original polynomial. If you want to find complex roots, you can use the method starting with a complex first guess and using complex arithmetic. Starting with a complex initial guess can result in finding a real root, but not vice versa. I wrote a VB application to find polynomial roots. It works for bigger polynomials than anybody cares about. It uses complex arithmetic and starts with a random complex initial guess. It reduces the order of the polynomial using synthetic division, and improves precision of roots found by Newton method using original polynomial. When a complex root is found, the order is reduced by two (Synthetic division by a quadratic factor). I have a HP calculator, but have no idea how it finds roots. I find it hard to imagine that it uses anything but the Newton method, which is easy to program and very efficient. I cannot believe that any type of table is involved, other than one for storing the roots found while the next is being determined. For real roots, I suppose some systematic binary search algorithm could be used, but this is very inefficient compared to Newton, and prohibitively slow for finding complex roots, which the HP can find. BTW: In fooling around with my VB program, I found a polynomial which had a very large derivative near a root. If graphed, the polynomial would be almost a vertical line near the root. A very precise value of the root resulted in the polynomial evaluation being orders of magnitude greater than zero.
I think that the TI's (at least the 82,83,85) use a high/low method. Basically they go along the line and check when: 1) the value goes from positive to negative 2) the slope goes from positive to negative I don't think they actually do any manipulations of the equation because they have fairly low processor power. More importantly though, I've had it not catch roots sometimes depending on the way the graph is scaled. Now programs like Maple/Matlab, I'd be almost positive that they do a much more advanced method.
Persol: MY HP 48GX finds both real and complex roots of polynomials to about 12 digits of precision. It found all roots of 8th order polynomial in a few seconds. I do not think it is any faster than the high end TI calculators. The above suggests to me that it uses the Newton method. I do not know of any other method which would get that precision for complex roots in a few seconds using another method. Will the TI calculators find complex roots? If so, I would expect that they also use Newton. How precise are the roots found by the TI? Checking for positive and negative is painfully slow if you try for 12 digits of precision. BTW: If the TI checks the slope, it has to compute the derivative, and might as well do the Newton method. Do you know of any other methods as good as Newton?
It only finds the real roots within the range specified (or the range of the current graph). It gives the answer to about 9 decimal places I think... but it is not accurate to 9 places. As for calculating the slope, it seems to just be a rough calculation using dx as the pixel width and dy as the y change between the current and next pixel. I say this because I can have the same exact equation, but sometime it won't find the root depending on the graph settings. Also, if I ask it to calculate the slope it will give an incorect answer if I am zoomed out too far. I'm not saying that this is a good method for accuracy, but that this is how the TIs do it.
The post about finding roots by factoring is erroneous. If r is a root, then (x - r) is a factor. You cannot factor without knowing a root. Factoring is only done by students when the instructor provides a polynomial with integer (or at worst rational) roots. I am also a bit skeptical about a calculator building a table, although perhaps it might do so to graph a polynomial. It is possible that a table might be built in order to approximate roots via interpolation, but this is a lousy way to find roots if you care about precision. I would not believe that a table is built unless the manufacturer's handbook told me so.
There are many ways to find roots numerically. Newton's method is just one. I think that calculators probably use a combination of Newton's method and a "half-interval" method (I forget the proper name for the algorithm).
James R: A search for "half interval" found a web site that described the method. You did not forget the name. It is a binary search for a real root in a given interval. The reference says that the time is proportional to the log of Length/Precision. Length is length of interval and precision is desired precision. It seems to me that the above suggests that for 12 digit precision you would use the following formula. 2<sup>n</sup> = Length * 10<sup>-12</sup>, where n is the number of iterations. The method looks easier to program than Newton, but cannot find complex roots. For real roots, it is certainly feasible on a modern PC and might be okay for a calculator. I suspect that my HP calculator uses Newton because it can find real and complex roots of a 12th order polynomial in about 10 seconds. I cannot imagine any other method being able to that on a relatively slow engine.
