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.

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 (x-xi) 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?

n1 is the number of roots that you choose (and specify the values of the roots).

Namir

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.

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.x3 + b.x2 + c.x + d.

P’(x) = 3a.x2 + 2b.x + c

P"(x) = 6a.x + 2b

For the three roots x1= -1, x2 = 1/8 and x3 = 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.

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

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

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

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 (x-x0_i) and A(x) is a yet to determine polynomial. I tried with:

B(x)=u*x²+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.

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

1) Choose a polynomial of degree n=n1+n2+n3: (highest coeff can be 1)

f(x) = x^n + c[n-1]*x^(n-1) + c[n-2]*x^(n-2) + ... + 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[n-1]

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)(x-1/8)(x-1)*(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 (x-value) for the extrema but also the function value (y), then of course you'll have to increase the polynomial-degree by 1 for each additional condition.

Franz

Edited: 17 Aug 2011, 9:22 a.m.

Quote:

---

Franz, you caught me on the finish line, I was just verifying my results with Derive. :-)

---

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! :-)

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

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

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.

---

If you construct a 3-degree polynomial with the 3 given roots, then its maximum and minimum are NOT at the given x-values (unless it's by chance). So you have to choose a higher degree to fulfill also these extrema conditions.

Franz

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

The solutions presented so far deal with you option (1).

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.

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^5-116*X^4-144*X^3+121*X^2-5)/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^5-116*X^4-144*X^3+121*X^2-5)/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.