▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
Hi All,
I am interested in the algorithm that allows me to determine the coefficients (A) and order of a polynomial (N) that:
1. Passes through a specified set of roots (n1 roots).
2. Passes through a specified set of minima (n2 minima).
3. Passes through a specified set of maxima (n3 maximum).
Doing just #1 is easy as pie!! Doing 1 and 2, 1 and 3, or 1, 2, and 3 is hard. Any ideas?
Namir
Edited: 16 Aug 2011, 3:22 p.m.
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
Namir,
is n1 the exact number of roots or the minimum number of roots?
for #1 alone, this is simple, it's just the product (xxi) where xi are the roots. To put #2 or #3 into the equation, you may or may not need to multiply in more factors so that f'(x) has roots at the specified minima or maxima and f"(x) is positive for #2 and negative for #3.
Can you give a concrete example of values so that we can experiment with the problem?
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
n1 is the number of roots that you choose (and specify the values of the roots).
Namir
Posts: 2,247
Threads: 200
Joined: Jun 2005
Here is an example:
1. Roots at 1, 0.125, and 1.
2. Maximum at 0.
3. Minimum at 0.5.
Edited: 16 Aug 2011, 5:33 p.m.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
Namir,
I have to repeat the question of [u][b]Marcus[/u][/b] which is of primary importance. If the three roots you give are the only one of the polymer, there is no solution to your problem.
If 1, 1/8 and 1 are the only and simple roots of the polymer P(x), then P(x) is exactly of degree 3.
We have to found the four coefficients a, b, c, and d of P(x):
P(x) = a.x^{3} + b.x^{2} + c.x + d.
P’(x) = 3a.x^{2} + 2b.x + c
P"(x) = 6a.x + 2b
For the three roots x_{1}= 1, x_{2} = 1/8 and x_{3} = 1;
P( 1 ) = 0 a + b – c + d == 0 (eq.1)
P( 1/8 ) = 0 a/512 + b/64 + c/8 + d == 0 (eq.2)
P( +1 ) = 0 a + b + c + d == 0 (eq.3)
From (eq.1) and (eq.3) we have 2b + 2d == 0, thus d = b.
As explain by [u][b]Marcus[/u][/b] at the extremum (minimum and maximum), the first derivate P’(x) is zero, thus :
P’( 0 ) = 0 c == 0 (eq.4)
P’( 1/2 ) = 0 3a/4 + b + c == 0 (eq.5)
From (eq.4) and (eq.5) b = 3a/4
The point 0 is a maximum if P"(0) negative.
P"( 0 ) < 0 b < 0 (eq.6)
The point ½ is a minimum if P"(1/2) is positive.
P"( 1/2 ) > 0 3a + 2b > 0 (eq.6)
3a  3a/2 > 0
3a/2 > 0
At this point , we have to found a set of coefficients :
a > 0, b= 3a/4, c=0 and d=b=3a/4.
From (eq.2) :
a/512  3a/128  3a/4 == 0
a == 0
Thus, no such a polymer exist ! It may only be a solution if the polymer is of a greater degree.
OK, I found no evident solution, but my approch clearly show that an appropriate algorithm may be lead by linear algebra, system of equations and inequations.
Edited: 16 Aug 2011, 7:59 p.m.
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
A polynomial with a higher degree is fine. This means it will have additional roots (real or complex) and that's fine. As long as the resulting example polynomial has the properties I gave.
Thanks for your efforts!!
Namir
Posts: 1,216
Threads: 75
Joined: Jun 2011
Quote:
Here is an example:
1. Roots at 1, 0.125, and 1.
2. Maximum at 0.
3. Minimum at 0.5.
The solution (i.e. the lowest degree polynomial) to this problem is:
f(x) = k*(88*x^5 + 75*x^4 + 88*x^3  76*x^2 + 1)
where k can be any positive number.
Franz
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
Thank you!!
The whole idea about getting a "custom" polynomial arose when I was trying to select simple polynomials to study the calculations of their roots. Using the form of p(x)=product(x  root(i)) was intuitive but yielded a few polynomials that did not have much rise in values between two roots that I was interested in. So I began to ask about getting custom polynomials where I cans specify not only the roots but also certain maxima and minima between these roots.
Namir
▼
Posts: 1,216
Threads: 75
Joined: Jun 2011
Well, if your requirements (given in your first post)
1. Passes through a specified set of roots (n1 roots).
2. Passes through a specified set of minima (n2 minima).
3. Passes through a specified set of maxima (n3 maximum).
fulfill the condition that all your given extrema are between 2 roots and maxima and minima are alternating (i.e. root,min,root,max,root,min,root, etc), then the algorithm is quite simple (and has been mentioned already in parts):
1) Choose a polynomial of degree n=n1+n2+n3: (highest coeff can be 1)
f(x) = x^n + c[n1]*x^(n1) + c[n2]*x^(n2) + ... + c[1]*x + c[0]
2) build its derivative f'(x)
3) substituting the zeros in f(x)=0 and the extrema in f'(x)=0 gives you a linear equation system of n equations and variables with a unique solution for all n coeffs c[0]...c[n1]
4) finally substitute any of your extrema in f''(x) to check the sign, and if this sign is wrong then multiply the function with 1.
I did even use a bit shorter way:
one part of the polynomial you can build directly from the zeros (as you already mentioned), so you just need another part for the extrema, and that's now a polynomial withe degree n=n2+n3 only!
Looks like this: (for your given example)
f(x)=(x+1)(x1/8)(x1)*(x^2+a*x+b)
Now do the same as above, but you only need to substitute the extrema, and you have only a 2x2 system for a and b.
One problem still remains:
If your extrema don't fulfill the conditions I wrote above (e.g. if you want both 0 and 1/2 to be maxima (or minima)), then such a n=n1+n2+n3 polynomial doesn't work  you always get one as maxima and the other as minima (or vice versa, depending on multiplying it with 1 or not).
So far I don't know how this problem could be solved too  I've tried an even higher polynomial, but this also didn't work.
BTW: if you don't only give the arguments (xvalue) for the extrema but also the function value (y), then of course you'll have to increase the polynomialdegree by 1 for each additional condition.
Franz
Edited: 17 Aug 2011, 9:22 a.m.
▼
Posts: 59
Threads: 5
Joined: Jul 2011
It seems that the roots for minima and maxima should be alternated. If there is a minimum at x1 then the derivative will have its sign being negative on the left of x1 and positive on the right ( +), conversely for a maximum (+ ). Then lets assume that two minima are consecutive we shall have a sequence of (+)(+) for the sign of the derivative, but then we also have a sequence (+) which shows that there is local maximum between the two minima, which is contradictory with the initial hypothesis.
Then if the derivative is continuous (should be for a polynomial) minima and maxima are interleaved. In other words there is no polynomial solution if this condition is not satisfied.
Regards
▼
Posts: 325
Threads: 18
Joined: Jul 2006
I don't believe the original requirements stated that all of the maxima (or minima) are given. It's possible for a polynomial to have more than one minima and maxima between two roots.
Posts: 3,283
Threads: 104
Joined: Jul 2005
Franz, you caught me on the finish line, I was just verifying my results with Derive. :)
My normalized result (pasted from Derive):
5 4 3 2
 88·x + 75·x + 88·x  76·x + 1
The idea:
P(x)=A(x)*B(x) where B(x) is the product of (xx0_{i}) and A(x) is a yet to determine polynomial. I tried with:
B(x)=u*x^{2}+v*x+w.
After some pencil and paper computations I arrived at:
v=8, u=11/8*v=11 and w=v/8=1
It has all the requested properties, especially the derivative is 0 at 0 and 1/2 and the second derivative is negative for 0 and positive for 1/2. I let Derive do the dirty work of computing the coefficients of A(x)B(x) and did the normalization by hand.
▼
Posts: 1,216
Threads: 75
Joined: Jun 2011
Quote:
Franz, you caught me on the finish line, I was just verifying my results with Derive. :)
Well Marcus, we both seem to be quite similar and come from the same 'good old school'! ;)
I also did it almost exactly the same way as you, and I also did use Derive (for such simple tasks I even use the old DOS Derive 3!)  really funny! :)
Posts: 274
Threads: 23
Joined: Sep 2007
hi Marcus,
Are you sure about the polynomial of degree 5 ?
I agree that I did not play with polynomials since a very long time. But as far as I remember, a polynomial of degree 3 can have 3 roots and 1 minima and 1 maxima.
Patrice
▼
Posts: 1,216
Threads: 75
Joined: Jun 2011
Quote:
Are you sure about the polynomial of degree 5 ?
I agree that I did not play with polynomials since a very long time. But as far as I remember, a polynomial of degree 3 can have 3 roots and 1 minima and 1 maxima.
I'm not Marcus, but nevertheless ... ;)
If you construct a 3degree polynomial with the 3 given roots, then its maximum and minimum are NOT at the given xvalues (unless it's by chance). So you have to choose a higher degree to fulfill also these extrema conditions.
Franz
Posts: 274
Threads: 23
Joined: Sep 2007
Hi Namir,
Just to be precise, how should I understand the values ?
1)
1. Roots at (1,0), (0.125,0), and (1,0).
2. Maximum at (0,Mx1).
3. Minimum at (0.5,Mn1).
or
2)
1. Roots at (1,0), (0.125,0), and (1,0).
2. Maximum at (Mx1, 0).
3. Minimum at (Mn1, 0.5).
Patrice
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
The solutions presented so far deal with you option (1).
Posts: 468
Threads: 17
Joined: May 2011
Hi,
here is an HP50G program based on the analyses of Marcus and Franz. It would be easy to generalise it and input the roots, minima and maxima as parameters. I don't verify here the sign of extremums (mini maxi)but it's easy to change ( by example in exploring the TABVAR result, and the Up / Down variation around the extremum ( Down Up) give a minimum and ( Up Down) a maximum).
I got :
Eq : '(144*X^5116*X^4144*X^3+121*X^25)/144'
Roots : { 1 '1/4' 1 '((5+sqrt70)/18)' '(5+sqrt70)/18' }
Extremum : { '1/2' '((13+Sqrt(21949))/180)' '(13+Sqrt(21949))/180' 0 }
TABVAR : {'inf' + '((13+sqrt(21949))/180)'  0 + '1/2'  '(13+sqrt21949)/180' + '+inf' } @ Extract of TABVAR
The prog (must be in 'exact mode', and no numeric of course):
[ 1 1 '1/4' 1 1 1 ] FCOEF @ Generate the first part of f(x). The even parameters are for single or multiple roots. Here we suppose single roots so 1
'X^2+a*X+b' * @ here we have got f(x) with 2 unknows a and b
DUP @ Garde le résultat au chaud (in french in the text)
DERVX 0 = @ f'(x)=0
{'X=0' 'X=1/2' } SUBST @ { f'(0)=0 f'(1/2)=0 }
AXL ['a' 'b'] SOLVE @ To solve the system of 2 equations
EVAL AXL
1 « SUBST » DOSUBS @ replace a and b by their values in f(x)
EXPAND @ simplify the equation
@..............................
@ And now verify if all is OK
@..............................
DUP 'X' ZEROS
OVER DERVX 'X' ZEROS
For generalisation, could be something like :
{ Root1 Multiplicity Root2 Multiplicity etc. }
{ Extremum1 '!' Extremum2 '!' etc....} @ ! is Up or Down arrow char like do the TABVAR command
POLY
and change dynamically the number of a b c d... parameters depending of the number of extrema
... and manage the errors and "no solution" issue ( mini / maxi inconsistency like 2 max that follow without min ?)
Gilles
PS : generic version :
@ INPUT
@ Level 2 : Array of roots ex : [ 1 '1/4' 1]
@ Level 1 : Array of extrema ex : [0 '1/2' ]
@ OUTPUT
@ Level 1: a polynomial solution ex : '(144*X^5116*X^4144*X^3+121*X^25)/144'
«
DUP AXL
1 « DROP NSUB 96 + CHR STR> » DOSUBS @ { 'a' 'b' 'c' ...}
> abc
«
« 'X' SWAP = » MAP @ [ X=Extr1 X=Extr2 ... ]
SWAP
AXL 1 « 1 » DOSUBS AXL FCOEF @ Gener fisrt part of f(x)
OVER AXL 1 « DROP 'X' NSUB ^ » DOSUBS @ Gener second part
1 SWAP + @ 'a+bX+cX^2+...+X^n'
abc 1 + * SigmaLIST @
* @ Gener f(x) is Part1 * Part2
DUP
DERVX 0 = @ f'(X)=0
ROT SUBST AXL
abc DUP SIZE 1 >
{ AXL SOLVE EVAL AXL } @ Find a,b,c etc.
{ EVAL ISOL 1 >LIST }
IFTE @ because SOLVE don't work with a single equation/single unknow
1 « SUBST » DOSUBS @ Replace value of a,b,c ... in f(X)
EXPAND
»
Edited: 18 Aug 2011, 1:51 p.m.
