Polynomial Function with Matching Maxima

Date: 11/17/2008 at 00:43:17
From: Chris
Subject: Finding a polynomial's "natural" Minimax curve

Let c(t) be a polynomial of degree 2n, n>=2 being a positive integer
for which all roots are unique, exist and are located between [0, 1].
I further specify that the first and last root are at t=0 and t=1.  As
such, the polynomial can be defined with the equation:

c(t) = t * (t - a_1) * ... * (t - a_(n-1)) * (1-t)

I would like to find every root of the polynomial that makes it such
that every maximum of the polynomial are equal.  

I cannot think of a way to get a system that I can compute the answer
to.  Maple also doesn't seem to be able to solve this one.  I found a
solution for a polygon of degree 4.  I did so by noticing the symmetry
that will arise at t=1/2 and thereby defining the equation as follows:
c(t) = t * (t-1) * (t-u) * (t-(1-u)).

I can then solve my equation by solving {dc(a)/dt = 0, c(a) =
-c(1/2)}, restricting my solution to those that fit {a < 1/2, a > 0, u
< 1/2}.  I can find that {a =0.1173165676, u =0.2928932188} and can
verify that this is indeed what was expected and that the properties 
are in fact respected.

I tried to tackle the same problem with a polynomial of degree 6 but
failed to get anywhere with that one.

Date: 11/17/2008 at 05:19:59
From: Doctor Jacques
Subject: Re: Finding a polynomial's 

Hi Chris,

The usual solution to these "equal ripple" problems makes use of the 
Chebyshev polynomials.

The idea behind this is that cos(n*u) is a rational function of 
cos(u).  We define the polynomials T_n(x) by:

  x = cos(u)     0 <= u <= pi
  T_n(x) = cos(n*u)

As the maxima and minima of cos(n*u) are all equal to 1 or -1, 
respectively, we get indeed the desired property.

Using basic trigonometric identities, it is possible to compute these 
polynomials by means of a recurrence formula.  You can see a plot of 
the first few polynomials, and read much more information about them, 
at:

  Wolfram Mathworld: Chebyshev Polynomial of the First Kind
    http://mathworld.wolfram.com/ChebyshevPolynomialoftheFirstKind.html 

Look in particular at the equations (9) and (26).

As we will see, we don't really need to compute the polynomials 
themselves.

For your particular problem, we cannot use these polynomials 
directly, because:

* The normal domain of the T_n(x) is the interval [-1,+1], and you
  want your polynomial defined over [0,1].  This can be easily taken
  care of by a linear transformation of the variable.

* The T_n(x) take values of 1 or -1 at the endpoints of the
  interval.  We can solve this problem by limiting the interval to
  the outermost two roots; this will only imply the need for other
  coefficients in the linear transformation above.

We can compute the roots of T_n(x) explicitly, because the 
corresponding values of u are the solutions of the equation:

  cos(n*u) = 0

and these values are given by:

  u = (2k+1)*pi/(2n)     k = 0, ..., n-1

If the corresponding values of x = cos(u) are x[1],...,x[n] in 
ascending order, we define the new variable t by:

  t = (x - x[1])/(x[n] - x[1])

and the desired polynomial c(t) = T_n(x) will have the desired 
properties.

If we don't care about the value of the maxima, we may write down 
the roots of c(t) directly, as:

  t[i] = (x[i] - x[1])/(x[n] - x[1])

and we have c(t) equal to the product of the factors (t - t[i]).

For example, for n = 4, the solutions of cos(4*u) = 0 are (2k+1)*pi/8.

We can make the following table:

  u[i]     x[i]      t[i]
  --------------------------
  7*pi/8 -0.923880  0.000000
  5*pi/8 -0.382683  0.292893
  3*pi/8  0.382683  0.707107
  1*pi/8  0.923880  1.000000

Notes:

* The u[i] are in descending order, since cos is a decreasing
  function on the interval considered, and we want the x[i] in
  ascending order.

* The second column is computed as x[i] = cos(u[i])

* The third column contains the roots of c(t) and is computed as:
   t[i] = (x[i] - x[1])/(x[4] - x[1])
        = (x[i] + 0.923880)/1.847759

The resulting polynomial is:

 c(t) =  t*(t-0.292893)*(t-0.707107)*(t-1)

which agrees with your calculation.

Note that this also works for polynomials of odd degree.

Please feel free to write back if you require further assistance.


- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/