Find all roots of a quintic polynomial given 1?

Question

Let's say I have solved for one of the roots $a$ of a quintic equation using Newton's method. I read somewhere that you can "simply" divide the equation by $x - a$ to get a quartic and solve from there.

How would I get this quartic equation from my quintic euqation (using a formula), and after doing this, how would I go about solving it numerically?

Answer 1

If $p(x)=x^5+Ax^4+Bx^3+Cx^2+Dx+E$ has root $a$, then

$$p(x)=(x-a)(x^4+A'x^3+B'x^2+C'x+D')$$

where

$$\begin{align} A&=A'-a\\ B&=B'-aA'\\ C&=C'-aB'\\ D&=D'-aC'\\ E&=-aD' \end{align}$$

We can easily unwind the first two equations to

$$\begin{align} A'&=A+a\\ B'&=B+aA'=B+aA+a^2 \end{align}$$

and the last two (provided $a\not=0$) to

$$\begin{align} D'&=-E/a\\ C'&=(D'-D)/a=-(E/a^2+D/a) \end{align}$$

Alternatively you could keep going in the "forward" direction with

$$\begin{align} C'&=C+aB'=C+aB+a^2A+a^3\\ D'&=D+aC'=D+aC+a^2B+a^3A+a^4 \end{align}$$

Either way, if you have a (good) numerical approximation to $a$, you can compute (approximately) the coefficients $A'$, $B'$, $C'$, and $D'$ of a quartic and then apply your favorite root-finding algorithm to that polynomial. If you succeed in getting a second root, you can repeat the basic idea outlined here, to factor that root out of the quartic leaving a cubic, etc. (Once you get things down to a quadratic, the quadratic formula will finish things off.)

Note, however, that a quintic may have only one real root, so some caution is called for if you're trying to make this mindless and mechanical; in particular, Newton-Raphson is not going to help with a quartic that has no real roots.

Answer 2

You can use polynomial long division to find the quotient.

An example of numerical package that does this is Python's numpy package. The following example shows that the quotient of $x^5-1$ by $x-1$ is $x^4 + x^3 + x^2 + x + 1$ and that the remainder is $0$

>>> import numpy as np
>>> q, r = np.polydiv([1, 0, 0, 0, 0, -1], [1, -1])
>>> q
array([1., 1., 1., 1., 1.])
>>> r
array([0.])

The source code is available in the numpy source tree, see the lines after def polydiv.

You don't need to divide the polynomials to find the roots. Efficient algorithms exist that find simultaneously all the complex roots of the polynomial. With numpy you can simply write this to get all the complex roots

>>> np.poly1d([1, 0, 0, 0, 0, -1]).r
array([-0.80901699+0.58778525j, -0.80901699-0.58778525j,
    0.30901699+0.95105652j,  0.30901699-0.95105652j,
    1.        +0.j        ])

Answer 3

Expanding on Gribouillis' answer, you don't need to factor to find more roots. The Durand-Kerner method allows for simultaneously finding all polynomial roots without this, and it allows you to include known roots if you wish as well. As it goes, it will also further polish the root you initially estimated, so if your known root isn't completely accurate then that is fine too.

Let $r_{i,n}$ be the $n$th estimate of the $i$th root for $i\in\{1,...,5\}$, with $r_{1,1}$ known and $r_{i,1}$ picked for $i\ne1$. One may then estimate

$$r_{i,n}=r_{i,n-1}-\frac{f(r_{i,n-1})}{P_{i,n}Q_{i,n}}$$

where

$$P_{i,n}=\prod_{j<i}(r_{i,n-1}-r_{j,n})=(r_{i,n-1}-r_{1,n})\cdots(r_{i,n-1}-r_{i-1,n})$$ $$Q_{i,n}=\prod_{j>i}(r_{i,n-1}-r_{j,n-1})=(r_{i,n-1}-r_{i+1,n-1})\cdots(r_{i,n-1}-r_{5,n-1})$$

or alternatively, one may use the simpler but slightly slower

$$r_{i,n}=r_{i,n-1}-\frac{f(r_{i,n-1})}{R_{i,n}}$$

where

$$R_{i,n}=\prod_{j\ne i}(r_{i,n-1}-r_{j,n-1})=(r_{i,n-1}-r_{1,n-1})\cdots(r_{i,n-1}-r_{5,n-1})$$

and the expanded RHS does not include the term $(r_{i,n-1}-r_{i,n-1})$.

The downside to this method is you will likely want to deal with complex arithmetic even if you only want real roots. There are also several similar algorithms on Wikipedia.