How to solve an nth degree polynomial equation

The typical approach of solving a quadratic equation is to solve for the roots

$$x=\frac{-b\pm\sqrt{b^{2}-4ac}}{2a}$$

Here, the degree of x is given to be 2

However, I was wondering on how to solve an equation if the degree of x is given to be n.

For example, consider this equation:

$$a_0 x^{n} + a_1 x^{n-1} + \dots + a_n = 0$$

-
@Johannes thanks for editing – Ayush Khemka Sep 22 '12 at 8:39
We live in the 21st century. Yet, we still can't simply solve a quintic by hand. We are just not that smart yet. – Nick Sep 25 '14 at 10:00
Calculate the eigenvalues of the companion matrix. Just kidding... – Dirk Dec 4 '14 at 16:42
Hilbert's 13th problem was to solve a degree-7 polynomial using functions of two variables. Vladimir Arnold solved it in 1957. – Michael Dec 6 '14 at 11:10
@Nick Of course, we can approximate the roots of polynomials of arbitrary degree to arbitrary degree of accuracy, and efficiently, too. I'd say that makes us pretty smart, our inability to write down those roots using a quite arbitrary class of "elementary" functions notwithstanding. – user7530 Dec 21 '14 at 17:24

There is no perfect answer to this question. For polynomials up to degree 4, there are explicit solution formulas similar to that for the quadratic equation (the Cardano formulas for third-degree equations, see here, and the Ferrari formula for degree 4, see here).

For higher degrees, no general formula exists (or more precisely, no formula in terms of addition, subtraction, multiplication, division, arbitrary constants and $n$-th roots). This result is proved in Galois theory and is known as the Abel-Ruffini theorem. Edit: Note that for some special cases (e.g., $x^n - a$), solution formulas exist, but they do not generalize to all polynomials. In fact, it is known that only a very small part of polynomials of degree $\ge 5$ admit a solution formula using the operations listed above.

Nevertheless, finding solutions to polynomial formulas is quite easy using numerical methods, e.g., Newton's method. These methods are independent of the degree of the polynomial.

-
The OP's question is not clear enough. The equation may be concretely given like $x^5 + x^4 + x^3 + x^2 + x + 1 = 0$. If the Galois group of the equation is solvable, it can be solved using repeatedly the roots of equations of the form $x^k - a = 0$. – Makoto Kato Sep 22 '12 at 9:27
That is certainly true, but he states a general polynomial without any assumptions on the coefficients. Therefore, I will assume he is looking for a general solution formula. Of course, say, $x^n - 1=0$ is very easy to solve in terms of radicals, but this is not the issue here. – Johannes Kloos Sep 22 '12 at 9:29
It is not clear to me if the OP asks a solution of a general polynomial. – Makoto Kato Sep 22 '12 at 9:32
@MakotoKato: Let me break it down. My assumption: Ayush is talking about a general method to solve polynomial equations in $\mathbb R[x]$ (or maybe $\mathbb C[x]$). Rationale: He or she does not mention any ground field, but mentions square roots, so I assume a school background. He/she is interested in a generalization of the solution formula for quadratic equations with given but arbitrary coefficients (as in his answer above). Therefore, my statement is: given an arbitrary polynomial, there are/aren't any solution methods in terms of radicals, as explained. For a given polynomials (cont.) – Johannes Kloos Sep 22 '12 at 9:53
numerical methods will usually apply, without regard to the degree. Of course, if we consider different settings (polynomials in a ground field with indeterminates, finite fields, whatever), the situation may change, but: If the OP had meant that, I believe there would have been an indication that he actually meant it and knew about it (why? Because these situations are quite rare in non-university level math). Thus, I permitted myself to make the assumptions mentioned above. – Johannes Kloos Sep 22 '12 at 9:56

Not very long time ago (2015) the paper Analytical Method for Finding Polynomial Roots has been appeared. This paper describes solving of ploynomial equations with analytical infinite power series.

-

The best general, understandable description of how to handle polynomials in general is the relevant chapter of Wilf's "Mathematics for the Physical Sciences" (Dover, 2006). The text is somewhat dated, as it is a reprint of a book from before computers being ubiquous, and there are further developments.

The first thing is to look for rational zeros, if any are found, divide their factors out.

For some special forms of polynomials, you can get the zeros by reducing them to lower degree ones, or with known zeros. Up to degree 4, there are formulas in terms of algebraic operations (addition, multiplication, roots), for degree 5 and above there aren't. Also, if there are multiple zeros, they are common to the polynomial and its derivative, so computing the greatest common divisor of the polynomial and its derivative is a first step.

Even when there are explicit formulas, for degrees 3 and 4 they are unwildely, it is often more useful to get a numerical approximation.

-

An approach that immediately comes to mind is to first establish the relationship (non-linear, typically) between each root of the polynomial (assumed, complex) and the coefficients of the power series, and then solve the resulting set of $n$ equations for the $n$ variables i.e, the roots, using an iterative numerical algorithm (say, Newton-Raphson extended to $n$ equations in $n$ variables) computed in the complex domain (to ensure convergence).
A pretty good approach to get the power series coefficients is by using discrete convolution for polynomial multiplication (see here ).

However, I was wondering on how to solve an equation if the degree of $x$ is given to be $n$.

The only thing that's now between you and your solutions (all $n$ of them) is a computer program.

-

Abel's impossibility theorem states that there is no algebraic solution to polynomial equations of degree five or higher

But Jordan has shown that any algebraic equation can be solved using modular functions. There are explicit formulas without the need to use Tschirnhausen or other transformations. However, application of this theorem in practice is very difficult because of the complexity of the relevant hyperelliptic integrals and higher genus theta functions. (General formulas see here)

There are general formulas for the general equations $$x^n-x+t=0$$ and $$ax^{2\mu}+bx^\mu-x^\nu+c=0$$ (see here and here)

-

I'd like to show you this flowchart which summarizes all methods of solving up to quartic polynomials 'by hand':

-
That is pretty awesome. But I think there is a typo in the reduction from quartic to cubic (look at the degrees of $u$). Did you make this? – DanielV Dec 23 '14 at 9:55
No I just found it once on reddit, but never found the original source =/ reddit.com/r/math/comments/2679hf/… I think I have to check everything and rewrite it one day. – flawr Dec 23 '14 at 9:56

consider a equation $x^5+x=3$ to solve this fifth order equation the equation can be written as $x=3-x^5$. Now you get the value of x. Substituting the value of x in the equation gives $x=3-(3-x^5)^5$. Now again substituting the x in this equation gives $x=3-(3-(3-x^5)^5)^5$. Proceeding this way to infinite series we obtain value of $x=3-(3-(3-(3-\dots)^5)^5)^5)^5\dots)^5$.

-
This "infinite series" of yours (though it looks more like an infinite tower of 5th powers to me) ... how would you go about finding its decimal-number value to five decimal places? – David K Oct 15 '14 at 7:15
Unfortunately, those $\ldots$ omit an important bit of information. There is a root-finding method called fixed-point iteration which basically does this, but it's a bit more careful about not having ill-defined infinite series pop up (or infinite series which are clearly divergent) – Milo Brandt Dec 21 '14 at 16:28
I believe that this method is not stable near the real root since $5x^4\gt1$. A better recursion would be $x_{n+1}=(3-x_n)^{1/5}$. – robjohn Dec 23 '14 at 7:33

If the equation's all roots are real and negative, The range bound answer for one of a root is between $\displaystyle -\frac{k}{z}$ and $\displaystyle -n \frac{k}{z}$, where $k$ is constant, $z$ is coefficient of $x$ and $n$ is the highest power of $x$. And the coefficient of $x^n$ must be $1$.

-

However, I was wondering on how to solve an equation if the degree of x is given to be n.

It depends on the information you want. For many applications, the fact "$\alpha$ is a solution to that equation" is all the information you need, and so solving the equation is trivial.

Maybe you'll also want to know how many real solutions there are. Descartes' rule of signs is good for that. Also, see Sturm's theorem.

Sometimes, you need some information on the numeric value. You usually don't need much: "$\alpha$ is the only solution to that equation that lies between 3 and 4", for example. It's pretty easy to get rough information through ad-hoc means. Newton's method can be used to improve estimates, and determining how many solutions there are can help ensure you've found everything.

-

If I understand the question correctly: there is no general expression for finding roots of polynomials of degree 5 or more. See here

For degrees 3 and 4 the Wikipedia entries are quite good.

-
The Abel-Ruffini theorem statest that there is no solution using radicals, not that there is no expression or method in general. – Calle Sep 22 '12 at 8:42
@Calle Given he/she mentioned the quadratic formula I assumed he/she meant a similar expression for higher degrees. But I take your point. – user39572 Sep 22 '12 at 8:48
The OP's question is not clear enough. The equation may be concretely given like $x^5 + x^4 + x^3 + x^2 + x + 1 = 0$. – Makoto Kato Sep 22 '12 at 9:20