# Nth degree polynomial

1. Dec 9, 2013

### Panphobia

How would I go about solving an Nth degree polynomial function such that N>=5?

Ax$^{n}$+Bx$^{n-1}$+.........+Z = 0

2. Dec 9, 2013

### SteamKing

Staff Emeritus
Iteration, unless you stumble on some kind of factorization.

3. Dec 9, 2013

### Panphobia

That might take a while with this
u(k) = (900-3k)r$^{k-1}$
s(n) = Σ$_{k=1...n}$u(k)
find r for which s(5000) = -600,000,000,000

But ok no problem, I guess I will write a program to iterate through all possible values of r.

4. Dec 9, 2013

### Number Nine

You would use an algorithm like Newton's method to find the roots. Testing all possible values of r is both impossible and also not particularly efficient.

5. Dec 9, 2013

### Panphobia

I made some assumptions but I got the algorithm working and I got r

6. Dec 9, 2013

### Mandelbroth

The Galois group of a general complex polynomial of degree $n\geq 5$ is not solvable. Thus, you won't be able to come up with something like the quadratic formula for $n\geq 5$. You have to find other ways to find roots.

7. Dec 10, 2013

### jackmell

Given:

$$w(z)=a_0+a_1 z+a_2 z^2+\cdots+a_nz^n$$

by Laurent's Expansion Theorem applied to algebraic functions, we can always write down an explicit expression (just like the quadratic formula) for the roots in terms of complex-contour integrals:

$$w(z)=b\prod_{j=1}^N \left(z-\frac{1}{2k_j\pi i}\mathop{\oint} \frac{z_{j,k}(\zeta)}{\zeta}d\zeta\right)^{k}$$

However, the integral is in general not solvable in terms of elementary functions so must be evaluated numerically.

Last edited: Dec 10, 2013
8. Dec 10, 2013

### Mandelbroth

You know I meant "in terms of radicals, powers, addition, and subtraction," right? :tongue:

That's actually REALLY cool to me. I've never thought of that, so I've learned something new today.

9. Dec 10, 2013

### jackmell

We need to try one in case the reader is not sure how to do this. Let's take:

$$f(z,w)=z-w(w-1)^2(w-2)^3(w-(1+i))^4=0$$

And in order to extract the fourth-order root, we will integrate over the 4-cycle branch corresponding to this root, the $w_{4,1}$ branch, along an $8\pi$ circular path say midway the distance to the nearest singular point of $f(z,w)$ which in this case is about 0.026 so let's let $z=0.01 e^{it}$ Then we have:

$$\frac{dw}{dt}=-\frac{\frac{df}{dz}}{\frac{df}{dw}}\frac{dz}{dt}=g(z,w)$$

Then we solve the IVP:

$$\frac{dw}{dt}=g(z,w),\quad w(0)=w_{4,1}(0.01)$$

where $w_{4,1}(0.01)$ means we are starting the integration on one of the determinations of this 4-cycle branch..

We integrate that numerically and obtain the (numeric) function $w_{4,1}$.

Then we would integrate:

$$\frac{1}{8\pi i}\oint \frac{w_{4,1}(t)}{z(t)}z'(t) dt$$

and when I solve the IVP for each determination of that branch, and solve that integral numerically, I get four values very close to $1+i$.

Now, if I've explained that well, the reader can now write Mathematica code to extract the third-order root. It should only take about 10 lines of code. You would of course have to find which of the 10 determinations of the function correspond to the 3-cycle branch but you can just integrate over all of them; three results should be very close to 2.

Last edited: Dec 10, 2013
10. Dec 10, 2013

### DuncanM

There is a Master's Thesis (in PDF format) from Oxford University posted at the following link:

http://eprints.maths.ox.ac.uk/16/1/mekwi.pdf

I think it does a pretty good job providing a general overview (and easily readable) of the various iterative methods available for solving polynomial equations.

Forming a Companion Matrix for the polynomial and solving for its eigenvalues (which are the roots of the original equation) is a very robust technique. However, it is not computationally efficient; it is better to use a method specifically designed to solve for the roots of a polynomial equation.

The Jenkins-Traub and Laguerre methods are two algorithms popular for solving for the roots of polynomial equations. There are several more; a search should reveal them.

Do you need to write a program to do this task?
Or do you just need it done, regardless of the technique?

In addition to the commercial software that can do this (e.g. - MATLAB, Maple, Mathematica, etc), there are also several free tools available online that can perform this task. For example, the following Javascript program uses the Jenkins-Traub algorithm to solve for the roots of a polynomial up to degree 100:

http://www.akiti.ca/PolyRootRe.html [Broken]

Hope this helps.

Last edited by a moderator: May 6, 2017
11. Dec 10, 2013

### Panphobia

What I did was just figure out what r = 1 was, then r = 10 was. Then I found out the answer was between, so I binary searched through the decimals until I got to a precise enough r. I was hoping to come up with a true maths solution. But I guess that was good enough. r = 1.002322108633

12. Dec 10, 2013

### Office_Shredder

Staff Emeritus
That gets you one answer, but there is one for each degree (possibly complex). Depending on the context of the question you might need to do more work.