Polynomial Function with Matching MaximaDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/