Difference between revisions of "Root (polynomial)"
Etmetalakret (talk | contribs) |
m |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
− | A '''root''' of a [[function]] (often a [[polynomial]]) <math>f(x)</math> whose range is the [[real number | real]], the [[complex number]]s or any abstract [[field]] is a value <math>a</math> in the [[domain]] of the function such that <math>f(a) = 0</math>. | + | A '''root''' of a [[function]] (often a [[polynomial]]) <math>f(x)</math> whose range is the [[real number | real]], the [[complex number]]s or any abstract [[field]] is a value <math>a</math> in the [[domain]] of the function such that <math>f(a) = (x-a) = 0</math>. |
+ | |||
+ | ==Finding roots== | ||
+ | |||
+ | Let <cmath>P(x) = c_nx^n + c_{n-1}x^{n-1} + \dots + c_1x + c_0 = \sum_{j=0}^{n} c_jx^j</cmath> with all <math>c_j \in \mathbb C</math> and <math>c_n \neq 0</math>, a general degree-<math>n</math> polynomial. The degree of <math>P(x)</math> is <math>n</math>, so <math>P(x)</math> has at most <math>n</math> complex roots. In fact, the sum of the multiplicities of all distinct complex roots is exactly <math>n</math>; that is, counting any double roots twice, triple roots three times, and so on, there are in fact exactly <math>n</math> complex roots of <math>P(x)</math>. | ||
+ | |||
+ | ===General techniques=== | ||
+ | |||
+ | Multiplying or dividing all of the coefficients of a polynomial by a nonzero constant does not change its roots. Thus, there will always be a [[Monic polynomial|monic polynomial]] <math>Q(x)</math> with degree <math>n</math> having the same roots as <math>P(x)</math>, given by <cmath>Q(x) = x^n + \frac{c_{n-1}x^{n-1}}{c_n} + \dots + \frac{c_1x}{c_n} + \frac{c_0}{c_n} = \sum_{j=0}^{n} \frac{c_jx^j}{c_n}.</cmath> | ||
+ | |||
+ | Once a root <math>a</math> of <math>P(x)</math> is found, the [[Factor Theorem]] gives that <math>x - a</math> is a factor of <math>P(x)</math>. Therefore, <math>x - a</math> can be divided out of <math>P(x)</math> using [[Synthetic division|synthetic division]], and the roots of the resulting quotient will be the remaining roots of <math>P(x)</math>. Once another root is found, the process can be repeated. Dividing through by <math>x - a</math> is most practical when the root <math>a</math> and all the coefficients <math>c_j</math> of <math>P(x)</math> are rational. | ||
+ | |||
+ | ===Rational roots=== | ||
+ | |||
+ | The three simplest values to test are <math>-1, 0,</math> and <math>1</math>. | ||
+ | <ul> <li> <math>0</math> is a root of <math>P(x)</math> if and only if the constant term <math>c_0</math> is <math>0</math>. | ||
+ | <li> <math>1</math> is a root of <math>P(x)</math> if and only if the sum of the coefficients is <math>0</math>. | ||
+ | <li> <math>-1</math> is a root of <math>P(x)</math> if and only if the [[Alternating sum|alternating sum]] of the coefficients is <math>0</math>. | ||
+ | </ul> | ||
+ | |||
+ | If all of the coefficients <math>c_j</math> of <math>P(x)</math> are integers, then the [[Rational Root Theorem]] applies; namely, if <math>\frac{p}{q}</math> is a root of <math>P(x)</math>, with <math>p</math> and <math>q</math> [[Relatively prime|relatively prime]], then <math>p</math> is a (positive or negative) divisor of <math>c_0</math> and <math>q</math> is a divisor of <math>c_n</math>. | ||
+ | |||
+ | If all of the <math>c_j</math> are rational, but not necessarily integers, then multiplying through by the [[Least common multiple|least common multiple]] of the denominators yields a polynomial with the same roots as <math>P(x)</math> and integer coefficients. The Rational Root Theorem can then be applied to the new polynomial to search for rational roots of <math>P(x)</math>. | ||
+ | |||
+ | In some cases the search may be simplified by substituting <math>P(x) = M(L(x))</math>, where <math>L(x)</math> is a nonconstant linear polynomial with rational coefficients. If <math>a</math> is a rational root of <math>P(x)</math>, then <math>L(a)</math> is a rational root of <math>M(x)</math>. Conversely, if <math>a</math> is a rational root of <math>M(x)</math>, then the [[Inverse of a function|inverse]] <math>L^{-1}(a)</math> of <math>L(x)</math> at <math>a</math> must be a rational root of <math>P(x)</math>. | ||
+ | |||
+ | ===Real roots=== | ||
+ | |||
+ | Evaluating <math>P(x)</math> at chosen values can point to the location of roots. If <math>P(a)</math> and <math>P(b)</math> have opposite signs, then the [[Intermediate Value Theorem]] states that <math>P(x)</math> has at least one root in <math>(a,b)</math>. | ||
+ | |||
+ | For single roots and other roots of odd multiplicity (triple roots, quintuple roots, etc.), <math>P(x)</math> will always change sign on opposite sides of the root, but for roots of even multiplicity (such as double roots), the sign of <math>P(x)</math> will be the same on either side of the root, so the Intermediate Value Theorem will not detect even-multiplicity roots. | ||
+ | |||
+ | [[Descartes Rule of Signs]] yields information on the number of positive real roots and negative real roots of <math>P(x)</math>. Writing the coefficients of <math>P(x)</math> in descending order of degree and excluding any that equal <math>0</math>, the number of positive real roots of <math>P(x)</math> is equal to the number of sign changes between adjacent coefficients, minus some even nonnegative integer. The number of negative real roots of <math>P(x)</math> is equal to the number of such sign changes after reversing the sign of every odd-degree coefficient, again minus some even nonnegative integer. Here roots are counted according to multiplicity, so double roots are counted twice, triple roots three times, and so on. | ||
+ | |||
+ | More broadly, counting roots according to their multiplicity as before the number of real roots always has the same [[Parity|parity]] as the degree <math>n</math>. Specifically, if <math>n</math> is odd then <math>P(x)</math> must have at least one real root. | ||
+ | |||
+ | [[Rolle's Theorem]] guarantees that if <math>P(x)</math> has two roots <math>r</math> and <math>s</math>, then its derivative <math>P'(x)</math> has at least one root in the interval <math>(r,s)</math>. In particular, if <math>P'(x)</math> has no roots in an interval <math>(a,b)</math>, then <math>P(x)</math> has at most one root in <math>[a,b]</math>. | ||
+ | |||
+ | [[Newton's method]] generates arbitrarily close approximations of the value of a real root of a polynomial. Use of Newton's method generally requires an educated guess for the location of the root based on the above criteria. We let the guess equal <math>x_0</math> and compute the approximations recursively: <cmath>x_{k+1} = x_k - \frac{P(x_k)}{P'(x_k)} = x_k - \frac{\sum_{j=0}^{n} c_jx_k^j}{\sum_{j=1}^{n} jc_jx_k^{j-1}}.</cmath> | ||
+ | |||
+ | ===Complex roots=== | ||
+ | |||
+ | Complex roots of polynomials with real coefficients always exist in [[Complex conjugate|conjugate pairs]]. That is, if <math>a</math>, <math>b</math>, and all coefficients of <math>P(x)</math> are real and <math>a + bi</math> is a root of <math>P(x),</math> then <math>a - bi</math> is also a root of <math>P(x)</math>. In particular, <math>P(x)</math> must both have an even number of distinct nonreal roots and an even sum of the multiplicities of all distinct nonreal roots. | ||
+ | |||
+ | The product of the factors corresponding to <math>a + bi</math> and <math>a - bi</math> is <cmath>(x - (a + bi))(x - (a - bi)) = x^2 - 2ax + (a^2 + b^2),</cmath> a quadratic polynomial with real coefficients. As such, dividing through by the product leaves a polynomial which still has real coefficients and all roots of the original except <math>a + bi</math> and <math>a - bi</math>. | ||
+ | |||
+ | ===In algebraic form=== | ||
+ | |||
+ | A root of a polynomial with integer coefficients will always be an algebraic number. General formulas give the algebraic form of the roots of polynomials with degree at most <math>4</math>. | ||
+ | |||
+ | For a quadratic equation <math>ax^2 + bx + c</math>, the roots are given by the [[Quadratic formula|quadratic formula]] <cmath>\frac{ -b \pm \sqrt{b^2 - 4ac}}{2a}. </cmath> | ||
+ | |||
+ | The [[Cubic Equation#The Cubic Formula|cubic formula]] and [[Quartic Equation#The Quartic Formula|quartic formula]] also exist, but they are quite lengthy and not very practical for computation by hand. | ||
+ | |||
+ | No similar formula exists for quintics or polynomials of any higher degree. Although the roots of such polynomials are algebraic numbers, they cannot be expressed in terms of the coefficients using only addition, subtraction, multiplication, division, powers, and radicals. | ||
{{stub}} | {{stub}} |
Latest revision as of 20:37, 13 March 2022
A root of a function (often a polynomial) whose range is the real, the complex numbers or any abstract field is a value in the domain of the function such that .
Contents
[hide]Finding roots
Let with all and , a general degree- polynomial. The degree of is , so has at most complex roots. In fact, the sum of the multiplicities of all distinct complex roots is exactly ; that is, counting any double roots twice, triple roots three times, and so on, there are in fact exactly complex roots of .
General techniques
Multiplying or dividing all of the coefficients of a polynomial by a nonzero constant does not change its roots. Thus, there will always be a monic polynomial with degree having the same roots as , given by
Once a root of is found, the Factor Theorem gives that is a factor of . Therefore, can be divided out of using synthetic division, and the roots of the resulting quotient will be the remaining roots of . Once another root is found, the process can be repeated. Dividing through by is most practical when the root and all the coefficients of are rational.
Rational roots
The three simplest values to test are and .
- is a root of if and only if the constant term is .
- is a root of if and only if the sum of the coefficients is .
- is a root of if and only if the alternating sum of the coefficients is .
If all of the coefficients of are integers, then the Rational Root Theorem applies; namely, if is a root of , with and relatively prime, then is a (positive or negative) divisor of and is a divisor of .
If all of the are rational, but not necessarily integers, then multiplying through by the least common multiple of the denominators yields a polynomial with the same roots as and integer coefficients. The Rational Root Theorem can then be applied to the new polynomial to search for rational roots of .
In some cases the search may be simplified by substituting , where is a nonconstant linear polynomial with rational coefficients. If is a rational root of , then is a rational root of . Conversely, if is a rational root of , then the inverse of at must be a rational root of .
Real roots
Evaluating at chosen values can point to the location of roots. If and have opposite signs, then the Intermediate Value Theorem states that has at least one root in .
For single roots and other roots of odd multiplicity (triple roots, quintuple roots, etc.), will always change sign on opposite sides of the root, but for roots of even multiplicity (such as double roots), the sign of will be the same on either side of the root, so the Intermediate Value Theorem will not detect even-multiplicity roots.
Descartes Rule of Signs yields information on the number of positive real roots and negative real roots of . Writing the coefficients of in descending order of degree and excluding any that equal , the number of positive real roots of is equal to the number of sign changes between adjacent coefficients, minus some even nonnegative integer. The number of negative real roots of is equal to the number of such sign changes after reversing the sign of every odd-degree coefficient, again minus some even nonnegative integer. Here roots are counted according to multiplicity, so double roots are counted twice, triple roots three times, and so on.
More broadly, counting roots according to their multiplicity as before the number of real roots always has the same parity as the degree . Specifically, if is odd then must have at least one real root.
Rolle's Theorem guarantees that if has two roots and , then its derivative has at least one root in the interval . In particular, if has no roots in an interval , then has at most one root in .
Newton's method generates arbitrarily close approximations of the value of a real root of a polynomial. Use of Newton's method generally requires an educated guess for the location of the root based on the above criteria. We let the guess equal and compute the approximations recursively:
Complex roots
Complex roots of polynomials with real coefficients always exist in conjugate pairs. That is, if , , and all coefficients of are real and is a root of then is also a root of . In particular, must both have an even number of distinct nonreal roots and an even sum of the multiplicities of all distinct nonreal roots.
The product of the factors corresponding to and is a quadratic polynomial with real coefficients. As such, dividing through by the product leaves a polynomial which still has real coefficients and all roots of the original except and .
In algebraic form
A root of a polynomial with integer coefficients will always be an algebraic number. General formulas give the algebraic form of the roots of polynomials with degree at most .
For a quadratic equation , the roots are given by the quadratic formula
The cubic formula and quartic formula also exist, but they are quite lengthy and not very practical for computation by hand.
No similar formula exists for quintics or polynomials of any higher degree. Although the roots of such polynomials are algebraic numbers, they cannot be expressed in terms of the coefficients using only addition, subtraction, multiplication, division, powers, and radicals.
This article is a stub. Help us out by expanding it.