Let's first list a few properties about polynomials. Given a polynomial \[ f(x) = \alpha_0 + \alpha_1 x + ... + \alpha_n x^n \]
the Fundamental Theorem of Algebra tells us that there are $n$ complex roots (counted with multiplicity). A root $r$ has multiplicity $k$ if $f(r) = f'(r) = ... = f^{(k)}(r) = 0 \neq f^{(k+1)}(r)$. A root is simple if it has multiplicity one and a polynomial is square-free if all of its roots are simple. The complex roots must come in conjugate pairs and any rational roots must be of the form (factor of $a_0$) / (factor of $a_n$). Also, the ratio $(-1)^k \alpha_{n-k}/\alpha_n$ gives the sum of the products of all $k$-combinations of roots. Lastly, a result of Cauchy is that the magnitude of any root is bounded by $M = 1 +\max \left| a_i/a_n \right|$.
These properties as well as Descartes' rule of signs (stated below) and synthetic division can all be used to find the roots of a polynomial. Other methods include Newton's, Bisection, Secant, Regula Falsi, etc. Below describes two subdivision methods for isolating all the real roots of a square-free polynomial with real coefficients. They work by determining whether an interval contains zero roots, one root, or multiple roots, and then respectively discarding, storing, or subdividing the interval. The methods can be generalized but not without some effort.
Box Method and code
These properties as well as Descartes' rule of signs (stated below) and synthetic division can all be used to find the roots of a polynomial. Other methods include Newton's, Bisection, Secant, Regula Falsi, etc. Below describes two subdivision methods for isolating all the real roots of a square-free polynomial with real coefficients. They work by determining whether an interval contains zero roots, one root, or multiple roots, and then respectively discarding, storing, or subdividing the interval. The methods can be generalized but not without some effort.
Box Method and code
No comments:
Post a Comment