Author |
Topic: Solving Polynonial equation (Read 1801 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
Solving Polynonial equation
« on: Nov 24th, 2010, 5:04am » |
 Quote  Modify
|
i have a polynomial P(x), such that 1<= degree of P(x) <=49.
how to find solution of P(x) = y upto 5 digit precision after decimal. 0 <= x <= 1.
|
| « Last Edit: Nov 24th, 2010, 5:05am by birbal » |
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Solving Polynonial equation
« Reply #1 on: Nov 24th, 2010, 5:12am » |
Quote Modify
|
You could try Newton's method.
The trouble is the (possibly) large number of local extrema. You may have to repeatedly try different random starting values.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Solving Polynonial equation
« Reply #2 on: Nov 24th, 2010, 8:50am » |
Quote Modify
|
on Nov 24th, 2010, 5:12am, towr wrote:You could try Newton's method.
The trouble is the (possibly) large number of local extrema. You may have to repeatedly try different random starting values. |
|
Yeah actually my purpose of asking this problem was to get an estimate how many local extrama would be there, or in other words, how sparse values of x should i try ?
|
| « Last Edit: Nov 24th, 2010, 8:51am by birbal » |
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Solving Polynonial equation
« Reply #3 on: Nov 24th, 2010, 9:38am » |
Quote Modify
|
We're trying to solve P(x)=y, right? Not maximizing or minimizing P(x). So I don't think we need to worry about local extrema.
Because polynomials are continuous, all we need are numbers 0 < a < b < 1 with P(a)<y and P(b)>y (or the other way around); we can then apply a form of binary search on [a,b] until the desired precision is reached. (Compute c = (a+b)/2, and continue searching in the interval [a,c] or [c,b], depending on the sign of P(c)-y.)
How do we find the initial a and b? My best guess is that we should first calculate P(0)-y and P(1)-y. If they are of different signs, start the binary search described above with a=0 and b=1. If not, we can successively try P(1/2)-y, P(1/4)-y, P(3/4)-y, P(1/8)-y, P(3/8)-y, P(5/8)-y, P(7/8)-y, ..., until we encounter a different sign. Let {a, b} be {the x value producing the different sign, the closest other x value tried} and start the binary search procedure.
[edit]This is probably somewhat slower than the root-finding version of Newton's method, but at least it's a lot more stable.[/edit]
|
| « Last Edit: Nov 24th, 2010, 9:39am by pex » |
IP Logged |
|
|
|
0.999...
Full Member
Gender:
Posts: 156
|
|
Re: Solving Polynonial equation
« Reply #4 on: Nov 24th, 2010, 10:15am » |
Quote Modify
|
This is just a hunch, but it appears that the sum of the (complex) roots, the product of the (complex) roots and a couple other products can guide us toward pex's initial values (if they exist of course):
Suppose our polynomial Q(x) = P(x)-y has order n.
1. The sum of the roots is the coefficient of x^(n-1).
2. The product of the roots is the coefficient of x^0.
3. The product of |1 - r_i| where {r_i} is the set of all n roots is the sum of the coefficients divided by the leading coefficient.
4. The product of |-1 - r_i| where {r_i} is the set of all n roots is the absolute value of the alternating sum of the coefficients divided by the leading coefficient.
|
| « Last Edit: Nov 24th, 2010, 10:31am by 0.999... » |
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Solving Polynonial equation
« Reply #5 on: Nov 25th, 2010, 10:49am » |
Quote Modify
|
A small note, pex's method is called the bisection method [1]. Ofcourse, there are several other approaches with Newton's being the fastest in terms of convergence (quadratic versus linear).
-- AI
[1] http://deadline.3x.ro/bisection_method.html
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Solving Polynonial equation
« Reply #6 on: Dec 8th, 2010, 2:09pm » |
Quote Modify
|
I assume you have a y, and you are searching for an x such that P(x)=z. That is, find the zeroes of Q(x)=P(x).
I'll assume there are many solutions and you want them all.
There is an interesting way to find out where to search for roots. As for any function, the roots are between local extrema. And local extrema are roots of Q'(x). So the roots of Q are separated by roots of Q'. If you first find the roots of Q', you have so many intervals where each has at most one root.
So the idea is to compute the derivatives of the polynomial until it reduces to degree 1. Compute the root.
The 2 roots of the previous derivative, with degree 2, are left and right of that root. These 2 roots split the reals in 3 regions where you have 3 roots of the previous derivative, with degree 3. You work up the degrees like that until you find where to search for the roots of Q.
You normally don't need to find the roots accurately, you just need to reach a value near the root where the next higher polynomial has the right sign (i.e. different from at the roots left and right). Sometimes, to prove that the local extrema is on the wrong side of zero you need to solve it accurately.
Well, this explanation is a bit messy, it would need a rework with proper notation of the derivatives. I hope you understand what I mean anyway.
PS: actually I remember another trick, it is to compute for a given x the values of Q, Q', Q", ... down to the constant term. The number of times that the value changes sign in the sequence is an indication of how many roots are left and right of that x.
|
| « Last Edit: Dec 8th, 2010, 2:17pm by Grimbal » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Solving Polynonial equation
« Reply #7 on: Dec 14th, 2010, 11:30pm » |
Quote Modify
|
on Nov 24th, 2010, 9:38am, pex wrote:We're trying to solve P(x)=y, right? Not maximizing or minimizing P(x). So I don't think we need to worry about local extrema.
Because polynomials are continuous, all we need are numbers 0 < a < b < 1 with P(a)<y and P(b)>y (or the other way around); we can then apply a form of binary search on [a,b] until the desired precision is reached. (Compute c = (a+b)/2, and continue searching in the interval [a,c] or [c,b], depending on the sign of P(c)-y.)
How do we find the initial a and b? My best guess is that we should first calculate P(0)-y and P(1)-y. If they are of different signs, start the binary search described above with a=0 and b=1. If not, we can successively try P(1/2)-y, P(1/4)-y, P(3/4)-y, P(1/8)-y, P(3/8)-y, P(5/8)-y, P(7/8)-y, ..., until we encounter a different sign. Let {a, b} be {the x value producing the different sign, the closest other x value tried} and start the binary search procedure.
[edit]This is probably somewhat slower than the root-finding version of Newton's method, but at least it's a lot more stable.[/edit] |
|
The problem is with binary search, it may happen that we are struck at a maxima(or minima) while doing binary search. We can never know that.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Solving Polynonial equation
« Reply #8 on: Dec 14th, 2010, 11:40pm » |
Quote Modify
|
on Dec 8th, 2010, 2:09pm, Grimbal wrote:I assume you have a y, and you are searching for an x such that P(x)=z. That is, find the zeroes of Q(x)=P(x).
I'll assume there are many solutions and you want them all.
There is an interesting way to find out where to search for roots. As for any function, the roots are between local extrema. And local extrema are roots of Q'(x). So the roots of Q are separated by roots of Q'. If you first find the roots of Q', you have so many intervals where each has at most one root.
So the idea is to compute the derivatives of the polynomial until it reduces to degree 1. Compute the root.
The 2 roots of the previous derivative, with degree 2, are left and right of that root. These 2 roots split the reals in 3 regions where you have 3 roots of the previous derivative, with degree 3. You work up the degrees like that until you find where to search for the roots of Q.
You normally don't need to find the roots accurately, you just need to reach a value near the root where the next higher polynomial has the right sign (i.e. different from at the roots left and right). Sometimes, to prove that the local extrema is on the wrong side of zero you need to solve it accurately.
Well, this explanation is a bit messy, it would need a rework with proper notation of the derivatives. I hope you understand what I mean anyway.
PS: actually I remember another trick, it is to compute for a given x the values of Q, Q', Q", ... down to the constant term. The number of times that the value changes sign in the sequence is an indication of how many roots are left and right of that x.
|
|
Nice method to find regions where the roots lie. But may be more time consuming, since we need to find the roots of all the derivates for Q(x).
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Solving Polynonial equation
« Reply #9 on: Dec 15th, 2010, 2:45am » |
Quote Modify
|
on Dec 14th, 2010, 11:30pm, birbal wrote:| The problem is with binary search, it may happen that we are struck at a maxima(or minima) while doing binary search. We can never know that. |
|
The question was to find a zero, not an extremum. So bisection will work fine (for any continuous function).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print