Solving High-Degree Polynomial Functions: A Scientific Approach

[Panphobia]

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

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

 

[SteamKing]

Iteration, unless you stumble on some kind of factorization.

 

[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.

 

[Number Nine]

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.

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.

 

[Panphobia]

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

 

[Mandelbroth]

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

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

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.

 

[jackmell]

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

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.

 

[Mandelbroth]

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.

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.

 

[jackmell]

I've never thought of that, so I've learned something new today.

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.

 

[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

Hope this helps.

 

[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

 

[Office_Shredder]

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.