A Math Challenge (kind of)



#2

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.


#3

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?


#4

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

Namir

#5

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.


#6

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.


#7

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

#8

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


#9

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


#10

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


#11

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


#12

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.

#13

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

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


#14

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

#15

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


#16

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

#17

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


#18

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

#19

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.


Possibly Related Threads...
Thread Author Replies Views Last Post
  Need help understanding math.... cyrille de Brébisson 9 1,224 12-13-2013, 02:23 AM
Last Post: Didier Lachieze
  OT: a math competition site Pier Aiello 0 325 09-16-2013, 06:03 AM
Last Post: Pier Aiello
  Simple Math Question Namir 2 477 08-09-2013, 06:13 PM
Last Post: Eddie W. Shore
  Elliptic integrals of 1st and 2nd kind calculated by complex agm Gjermund Skailand 3 521 06-29-2013, 03:39 PM
Last Post: Gjermund Skailand
  Cool math clock Bruce Bergman 28 2,331 04-10-2013, 03:13 AM
Last Post: Siegfried (Austria)
  Math Challenge I could not solve Meindert Kuipers 22 1,925 01-05-2013, 04:43 PM
Last Post: Thomas Klemm
  Math Question Namir 0 292 11-06-2012, 07:43 AM
Last Post: Namir
  Survey for Special Math Problem Namir 7 823 06-03-2012, 09:46 PM
Last Post: Namir
  HP41C: Factorial (kind of) in MCODE Frido Bohn 7 805 05-26-2012, 09:18 AM
Last Post: Frido Bohn
  math question Don Shepherd 22 1,734 04-25-2012, 11:38 PM
Last Post: Don Shepherd

Forum Jump: