Roots of the Cubic Equation: Solution 1 (Iteration)
- Author:
- Ryan Hirst
Reset returns the search to the starting guess/interval.
Press Go to hunt for the roots.
How's it work?
- Bounds: http://www.geogebratube.org/material/show/id/144224
- Number of roots: How many times does f(x) cross the x-axis? Let the local maximum (left) and minimum (right) fall at . If , there are three zeros, one each in the intervals . If , there is one zero. If the It falls in the range , otherwise, .
- Search method: Suppose I have two points on the curve C, D such that . Then the curve must cross the x-axis between c and d. It remains to find the root. I adopt two iterative procedures: 1. Midpoint: Find the y-value at the midpoint. Let . Then, unless one of the three points lies exactly on a zero, I have either , or . The interval containing the root has been cut in half. Repeat. 2. x-intercept (linear interpolation): let the segment CD cross the x-axis at . Then , in the same way, either or . . . . Search ends when one of the y-values is sufficiently small or zero. In general, the midpoint rule is slower, but the worse-case scenario for x-intercept --when one of the endpoints of the interval is close to a zero, and the drawn segment can't intersect the curve-- is very bad. Rather than test for this condition, I adopt a simple mixture of the two. The worst-case is always avoided, while the number of steps stays close to a good-case x-intercept search. Example: set , and try the search with the mix all the way to the right. Now give the slider a nudge to the left, and redo the search. More sophisticated interpolation methods are always possible. Take a parabola with vertex at the local min/max, and passing through the inflection point. The outside x-intercept of this curve is an excellent starting estimate to the true zero.
- Root search: I will search for only one root. If there is ONE real root, using the information above, I will take the endpoints of the interval containing the root. If there are THREE real roots, I will hunt for the central root. Call this first root r1. With r1 located, write The remaining pair of roots, real or imaginary, can then be found using the quadratic formula.