A Math Challenge (kind of) « Next Oldest | Next Newest »

 ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 08-16-2011, 03:20 PM 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. ▼ Marcus von Cube, Germany Posting Freak Posts: 3,283 Threads: 104 Joined: Jul 2005 08-16-2011, 04:20 PM 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? ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 08-16-2011, 04:40 PM n1 is the number of roots that you choose (and specify the values of the roots). Namir Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 08-16-2011, 05:33 PM 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. ▼ C.Ret Senior Member Posts: 260 Threads: 0 Joined: Oct 2008 08-16-2011, 07:39 PM 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. ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 08-16-2011, 10:06 PM 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 fhub Posting Freak Posts: 1,216 Threads: 75 Joined: Jun 2011 08-17-2011, 06:08 AM 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 ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 08-17-2011, 08:32 AM 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 ▼ fhub Posting Freak Posts: 1,216 Threads: 75 Joined: Jun 2011 08-17-2011, 09:19 AM 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*x + c 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...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. ▼ Bunuel66 Member Posts: 59 Threads: 5 Joined: Jul 2011 08-17-2011, 03:48 PM 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 ▼ Kiyoshi Akima Senior Member Posts: 325 Threads: 18 Joined: Jul 2006 08-17-2011, 06:07 PM 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. Marcus von Cube, Germany Posting Freak Posts: 3,283 Threads: 104 Joined: Jul 2005 08-17-2011, 09:14 AM 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. ▼ fhub Posting Freak Posts: 1,216 Threads: 75 Joined: Jun 2011 08-17-2011, 09:27 AM 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! :-) Patrice Senior Member Posts: 274 Threads: 23 Joined: Sep 2007 08-17-2011, 01:31 PM 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 ▼ fhub Posting Freak Posts: 1,216 Threads: 75 Joined: Jun 2011 08-17-2011, 01:42 PM 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 Patrice Senior Member Posts: 274 Threads: 23 Joined: Sep 2007 08-17-2011, 01:16 PM 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 ▼ Marcus von Cube, Germany Posting Freak Posts: 3,283 Threads: 104 Joined: Jul 2005 08-17-2011, 03:48 PM The solutions presented so far deal with you option (1). Gilles Carpentier Senior Member Posts: 468 Threads: 17 Joined: May 2011 08-17-2011, 08:58 PM 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 2,817 12-13-2013, 02:23 AM Last Post: Didier Lachieze OT: a math competition site Pier Aiello 0 846 09-16-2013, 06:03 AM Last Post: Pier Aiello Simple Math Question Namir 2 1,118 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 1,184 06-29-2013, 03:39 PM Last Post: Gjermund Skailand Cool math clock Bruce Bergman 28 5,618 04-10-2013, 03:13 AM Last Post: Siegfried (Austria) Math Challenge I could not solve Meindert Kuipers 22 4,489 01-05-2013, 04:43 PM Last Post: Thomas Klemm Math Question Namir 0 754 11-06-2012, 07:43 AM Last Post: Namir Survey for Special Math Problem Namir 7 1,878 06-03-2012, 09:46 PM Last Post: Namir HP41C: Factorial (kind of) in MCODE Frido Bohn 7 1,979 05-26-2012, 09:18 AM Last Post: Frido Bohn math question Don Shepherd 22 4,249 04-25-2012, 11:38 PM Last Post: Don Shepherd

Forum Jump: 