Difference between revisions of "Root (polynomial)"

m
 
(4 intermediate revisions by 3 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}}
Line 5: Line 59:
 
[[Category:Algebra]]
 
[[Category:Algebra]]
 
[[Category:Polynomials]]
 
[[Category:Polynomials]]
[[Category:Definitions]]
+
[[Category:Definition]]

Latest revision as of 20:37, 13 March 2022

A root of a function (often a polynomial) $f(x)$ whose range is the real, the complex numbers or any abstract field is a value $a$ in the domain of the function such that $f(a) = (x-a) = 0$.

Finding roots

Let \[P(x) = c_nx^n + c_{n-1}x^{n-1} + \dots + c_1x + c_0 = \sum_{j=0}^{n} c_jx^j\] with all $c_j \in \mathbb C$ and $c_n \neq 0$, a general degree-$n$ polynomial. The degree of $P(x)$ is $n$, so $P(x)$ has at most $n$ complex roots. In fact, the sum of the multiplicities of all distinct complex roots is exactly $n$; that is, counting any double roots twice, triple roots three times, and so on, there are in fact exactly $n$ complex roots of $P(x)$.

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 $Q(x)$ with degree $n$ having the same roots as $P(x)$, given by \[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}.\]

Once a root $a$ of $P(x)$ is found, the Factor Theorem gives that $x - a$ is a factor of $P(x)$. Therefore, $x - a$ can be divided out of $P(x)$ using synthetic division, and the roots of the resulting quotient will be the remaining roots of $P(x)$. Once another root is found, the process can be repeated. Dividing through by $x - a$ is most practical when the root $a$ and all the coefficients $c_j$ of $P(x)$ are rational.

Rational roots

The three simplest values to test are $-1, 0,$ and $1$.

  • $0$ is a root of $P(x)$ if and only if the constant term $c_0$ is $0$.
  • $1$ is a root of $P(x)$ if and only if the sum of the coefficients is $0$.
  • $-1$ is a root of $P(x)$ if and only if the alternating sum of the coefficients is $0$.

If all of the coefficients $c_j$ of $P(x)$ are integers, then the Rational Root Theorem applies; namely, if $\frac{p}{q}$ is a root of $P(x)$, with $p$ and $q$ relatively prime, then $p$ is a (positive or negative) divisor of $c_0$ and $q$ is a divisor of $c_n$.

If all of the $c_j$ 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 $P(x)$ and integer coefficients. The Rational Root Theorem can then be applied to the new polynomial to search for rational roots of $P(x)$.

In some cases the search may be simplified by substituting $P(x) = M(L(x))$, where $L(x)$ is a nonconstant linear polynomial with rational coefficients. If $a$ is a rational root of $P(x)$, then $L(a)$ is a rational root of $M(x)$. Conversely, if $a$ is a rational root of $M(x)$, then the inverse $L^{-1}(a)$ of $L(x)$ at $a$ must be a rational root of $P(x)$.

Real roots

Evaluating $P(x)$ at chosen values can point to the location of roots. If $P(a)$ and $P(b)$ have opposite signs, then the Intermediate Value Theorem states that $P(x)$ has at least one root in $(a,b)$.

For single roots and other roots of odd multiplicity (triple roots, quintuple roots, etc.), $P(x)$ will always change sign on opposite sides of the root, but for roots of even multiplicity (such as double roots), the sign of $P(x)$ 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 $P(x)$. Writing the coefficients of $P(x)$ in descending order of degree and excluding any that equal $0$, the number of positive real roots of $P(x)$ is equal to the number of sign changes between adjacent coefficients, minus some even nonnegative integer. The number of negative real roots of $P(x)$ 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 $n$. Specifically, if $n$ is odd then $P(x)$ must have at least one real root.

Rolle's Theorem guarantees that if $P(x)$ has two roots $r$ and $s$, then its derivative $P'(x)$ has at least one root in the interval $(r,s)$. In particular, if $P'(x)$ has no roots in an interval $(a,b)$, then $P(x)$ has at most one root in $[a,b]$.

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 $x_0$ and compute the approximations recursively: \[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}}.\]

Complex roots

Complex roots of polynomials with real coefficients always exist in conjugate pairs. That is, if $a$, $b$, and all coefficients of $P(x)$ are real and $a + bi$ is a root of $P(x),$ then $a - bi$ is also a root of $P(x)$. In particular, $P(x)$ 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 $a + bi$ and $a - bi$ is \[(x - (a + bi))(x - (a - bi)) = x^2 - 2ax + (a^2 + b^2),\] 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 $a + bi$ and $a - bi$.

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 $4$.

For a quadratic equation $ax^2 + bx + c$, the roots are given by the quadratic formula \[\frac{ -b \pm \sqrt{b^2 - 4ac}}{2a}.\]

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.