From: wolle@elsen-bahnhof.uni-paderborn.de (Wolfgang Reinelt) Newsgroups: sci.math Subject: Interpolation with polynomials (2nd service) Date: Thu, 26 Jan 1995 10:32:37 +0100 Hi there, a couple of days ago, I posted the following: WR> Given a real intervall [a,b] and points (x_i,y_i) with a = x_1 < x_2 < .. WR> < x_n = b.The y_i are strictly decreasing, y_i > y_i+1 . WR> Now we can find a polynomial (of order n-1) which interpolates these n WR> points. WR> The experience shows, that this polynomial is decreasing in [a,b], too. WR> How can I proove this? At first, thank you all for spending time on this: sending examples, Matlab code & so on! But I would like to specify the problem more clearly: If you fix the intervall [a,b] and take a *equidistant* decomposition of this: a = x_1 < x_2 < ... < x_n = b Now take the y_i, which are strictly decreasing: y_i > y_i+1. The polynomial (of order n-1) which interpolates these n points (x_i,y_i) can be computed by the Newton-scheme, for example. Now the (numerical) experience shows the following: If n is large enough (and the y_i are decreasing), the interpolation-polynomial is decreasing in [a,b], too. Ok, I know: if you interpolate in this way with a polynomial of order (n-1), you get maxima and minima and normally the polynomial oscillates between the single x_i and you get *not* the smooth curve you wanted to have. But in this special case (with large n, but not too large?) it seems to be different! You 'catch' a part of the polynomial, which is decreasing. Try it! I already know that interplolation by polynomials is the last thing to do (greetings to Chris Mueller 8-), better to use splines if you want to interplolate. But I got this problem by the followig way: A student of mine (el. engineering) tried to interpolate by polynomials in this case, saw that the polynomial was decreasing (in all of his trials) and asked me if this could be proved. So here's our task: =================== Compute n (and so the x_i) so that the polynomial (computed by Newton-scheme) is decreasing. Let a=0, b=1 and the decreasing y_i are given. Pay attention: if you increase n, you get other x_i, but let's say that it's possible to have y_i for each x_i in [0,1]. Enjoy it! Regards, Wolfgang. -- Wolfgang Reinelt (wolle@elsen-bahnhof.uni-paderborn.de) Dept. of Electrical Engineering University of Paderborn D-33095 Paderborn/Germany ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Interpolation with polynomials (2nd service) Date: 26 Jan 1995 17:46:12 GMT In article , Wolfgang Reinelt wrote: >If you fix the intervall [a,b] and take a *equidistant* decomposition of this: > a = x_1 < x_2 < ... < x_n = b >Now take the y_i, which are strictly decreasing: y_i > y_i+1. >The polynomial (of order n-1) which interpolates these n points (x_i,y_i) >can be computed by the Newton-scheme, for example. >Now the (numerical) experience shows the following: >If n is large enough (and the y_i are decreasing), the >interpolation-polynomial is decreasing in [a,b], too. The fact that this tends to be corroborated by numerical evidence suggests an interesting statistical problem: To show that, suitably interpreted, such-and-such _usually_ occurs. However, it need not _always_ occur. Suppose you have y_1>...>y_n and a polynomial f_1 of degree n-1 or less such that f(i)=y_i for all i. I will show you how to put in one more data point so as to mess up the monotonicity. Indeed, suppose you look for the curve that also passes thru (n+1, y_(n+1) ). This new function has to be f_2(x) = f_1(x) + a Prod_1^n (x-i) for some a, namely a=(y_(n+1) - f_1(n+1))/n!. Since you have insisted on monotonic data, there is an upper bound on a but anything less than that is consistent with the construction you request. Now consider f_2(n- 1/2). This is f_1(n-1/2) + a Prod_1^n(n-1/2-i). It is important to note that the coefficient of a is negative. Thus with sufficiently negative values of a, we can make f_2(n-1/2) be as large as we want, and in particular larger than f_2(n-1)=y_(n-1). It follows that for such a, the function f_2 is not decreasing. Possibly this construction relies on a rather larger drop from y_n to y_(n+1); thus if you wish to obtain the conclusion that f be decreasing, you probably need to add some conditions along the lines of: for each i, (y_(i+1)-y_i)/(y_i-y_(i-1)) is "close" to 1. But likely the labor needed to construct suitable hypotheses is much greater than the benefit to be gained. dave ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Interpolation with polynomials (2nd service) Date: 26 Jan 1995 18:29:17 GMT In article <3g8n54$f54@mp.cs.niu.edu>, I wrote: >Possibly this construction relies on a rather larger drop from >y_n to y_(n+1); thus if you wish to obtain the conclusion that f be >decreasing, you probably need to add some conditions along the lines of: >for each i, (y_(i+1)-y_i)/(y_i-y_(i-1)) is "close" to 1. But >likely the labor needed to construct suitable hypotheses is much >greater than the benefit to be gained. OK, maybe that was a bit hasty. You could analyze it this way with some success: Let L_i(x) = (x-1)(x-2)...(x-[i-1]) and set Y_i = Sum (-1)^j C(i-1, j)y_{i-j}, where C(a,b) is the binomial coeff. Then a formula for the interpolated curve is f(x) = Sum_1^n Y_i/(i-1)! L_i(x). If you want to have this be monotone decreasing, you need the derivative to be negative, that is, Y_2 + Sum_3^n Y_i/(i-1)! L_i'(x) < 0 for all x in [1,n] (or whatever the interval is on which you want f to be decreasing). I've written it in this way because Y_2 =y_2-y_1 is already negative, so you need only assure that no other term is too big. For each i and n there is an upper bound on L_i'(x) on [1,n] (which I don't have a formula for, sorry), so the above derivative is indeed negative as long as the Y_i are small, say as long as each Y_i < (1/n) |Y_2| (i-1)!/max L_i'(x). (Of course, the individual Y_i don't need to be small, this is just one way to get it.) As a rule of thumb, the coefficients Y_i do tend to be small if the data points are clustered along a curve of low degree. This probably accounts for the numerical evidence that led to the original conjecture. dave ============================================================================== [Reinelt later sent me the attached two TeX files -- djr] ============================================================================== \documentstyle[12pt]{article} \headheight 0pt \topmargin 0pt \footheight 0pt \textwidth 6.5in \textheight 9in \oddsidemargin 0pt \evensidemargin 0pt \parindent 0pt \begin{document} {\bf The problem:} Given a real intervall $[a,b]$ and points $(x_i,y_i)$ with $a = x_1 < x_2 < .. < x_n = b$. The $y_i$ are strictly decreasing, $y_i > y_{i+1}$. Now we can find a polynomial (of order $n-1$) which interpolates these $n$ points. The experience shows, that this polynomial is decreasing in [a,b], too. How can this be proved? \bigskip {\bf Counterexamples:} \bigskip {\em Thomas Dierkes (Email: dierkes@uni-muenster.de)\\ University of Muenster/Germany\\ Sertuerner Str. 21 Phone: +49 (251) 80248\\ 48149 Muenster, Germany} \bigskip Try out the points $(1, 15)$, $(2, 3)$, $(3, 2)$, $(4, -15)$ ! --- {\em Fred T.~Krogh (Email: fkrogh@math.jpl.nasa.gov)\\ Jet Propulsion Laboratory\\ Mail Stop 301-455\\ 4800 Oak Grove Drive\\ Pasadena, CA 91109\\ Phone: (818) 354-2663} \bigskip Consider the quadratic passing through the points $(0, 100)$, $(1, 1)$, $(10,0)$. I haven't checked, but am sure that this quadratic has a minimum in the interval $[0, 10]$ --- {\em Dan Grayson (Email: dan@symcom.math.uiuc.edu)\\ Moderator of sci.math.research} \bigskip Consider $x-x^3$ with $x$-values like -100, -99, 99, 100 --- {\em Dan Wevrick (Email: wevrick@hilda.mast.queensu.ca)} \bigskip Consider the three points $(0, 0)$, $(1, -3)$ and $(5, -15)$. These points satisfy your condition and the interpolating polynomial is $y = -x(x-2)(x-4)$, which is not decreasing on $[0,5]$. It is, in fact, increasing on $[1,3]$. --- {\em Zdislav V. Kovarik (Email: kovarik@mcmail.CIS.McMaster.CA)\\ McMaster University, Hamilton, Ontario, Canada} \bigskip Here is an infinite sequence of counterexamples: Define \[ f(x) = \frac{1}{1+25x^2} - 4 x, x \in [-1, 1] \] and interpolate it at $n$ equidistant points, starting with -1 and ending with +1. Example: for $n = 5$, the points are $\{-1, -0.5, 0, 0.5, 1\}$. Now starting with $n=7$, the interpolating polynomials fail to be all monotone, although $f$ is strictly decreasing. The more points you use, the worse the polynomial fit will be. This is a modification of the famous Runge example showing that interpolation may get worse if we increase the number of points of interpolation (carelessly). --- {\em Les Reid (Email: LFR942F\%SMSVMA.BITNET@vm.gmd.de)\\ Southwest Missouri State University\\ Springfield, MO, USA} \bigskip Unfortunately, the conjecture you posted on sci.math is false: The interpolating polynomial for the data points $(-3, 9)$, $(-2, 4)$ and $(1, 1)$ is $x^2$ which is not decreasing on $[-3, 1]$. --- {\em Vincent Broman (Email: broman@nosc.mil)\\ code 572 Bayside\\ Naval Command Control and Ocean Surveillance Center, RDT\&E Div.\\ Phone: +1 619 553 1641\\ San Diego, CA 92152-6147, USA} \bigskip Polynomial interpolation is not in general monotonic. Try fitting a cubic through $(0, 1)$, $(0.49, 0.99)$, $(0.51, 0.01)$, $(1, 0)$. --- {\em Bradley Brock (Email: brock@ccr-p.ida.org)\\ IDA - Center for Communications Research, Princeton} \bigskip This is certainly false. For example interpolate $(-1.1, 0.869)$, $(-0.1,0.199)$, $(0.1, -0.199)$, $(1.1,-0.869)$ --- {\em Alois Steindl (Email: asteindl@mch2ws2.tuwien.ac.at)\\ Tel.: +43 (1) 58801 / 5529, Fax.: +43 (1) 5875863\\ Inst. for Mechanics II, TU Vienna\\ A-1040 Wiedner Hauptstr. 8-10 } \bigskip Ich glaube nicht, dass diese Vermutung generell stimmt: Betrachtet man etwa die Funktion $y = x^2$ und wertet die Funktion an den Punkten $x_i = -2, -1, 0.5 $ aus, so ergibt sich $y_i = 4, 1, 0.25,$ also eine monoton fallende Folge.\\ Die interpolierende Funktion ist aber nicht monoton. --- {\em Fred Richman (Email: fred@noether.math.fau.edu)\\ Florida Atlantic University} \bigskip Try interpolating a quadratic through the points $(-1, 9)$, $(2, 6)$, and $(3, 1)$. You get $10 - x^2$, which is not decreasing in $[-1, 3]$. --- {\em Jan Cnops (Email: jc@cage.rug.ac.be)\\ University of Ghent, Belgium} \bigskip At first sight I would say: you can't prove it. To quote Newton more or less: "I'm at no leisure to work it out completely" (from the introduction to the Principia Mathematica), but I think this would give you a counterexample. Take the polynomial $ -(x-1)(x-2)\dots(x-n-1)-\epsilon x^{n-1}$ in the interval $[0, n+1]$, where $\epsilon$ is very small, but positive, and the interpolation points $x_i=i$. For $i=1,...,n-1$ I get $y_i=-\epsilon i^{n-1}$, and (maybe if you change a minus sign somewhere) you could fix the value in $x=n$ to be still smaller. --- {\em John D'Errico (Email: derrico@pixel.kodak.com)\\ Eastman Kodak Company} \bigskip As a simple counterexample, consider the $xy$ pairs $x = (0, 1, 2)$ $y = (2, 1, 0.99)$ --- {\em Harald Schumann (Email: Harald\_Schumann@ms3.maus.de)} \bigskip Beweisen laesst sich das leider nicht, aber widerlegen: Betrachte das Polynom \[ f(x) = -x^5 +5x^3 -4\] Es hat Nullstellen fuer $x = -2, -1, 0, 1, 2$. Im Intervall $-2 < x < 2$ liegen seine relativen Extrema: das Polynom ist somit dort nicht monoton, wohl aber fuer $x < -2$ bzw.\ $x > 2$. Waehlt man etwa $x_1 = -5$, $x_2 = -4$, $x_3 = 4$, $x_4 = 5$, $x_5 =6$, so bilden die $f(x_i)$ eine monoton fallende Folge, waehrend $f(x)$ im Intervall $[-5, 6]$ nicht monoton faellt. Unter den unendlich vielen Polynomen $n$-ten Grades, die durch $n$ vorgegebene Punkte gehen, sollten sich aber immer welche finden lassen, auf die Deine Annahme zutrifft. Interessante Frage uebrigens: wie findet man die? \end{document} ============================================================================== \documentstyle[12pt]{article} \headheight 0pt \topmargin 0pt \footheight 0pt \textwidth 6.5in \textheight 9in \oddsidemargin 0pt \evensidemargin 0pt \parindent 0pt \begin{document} {\bf The problem -- part II} \bigskip A couple of days ago, I posted the following: \bigskip {\em Given a real intervall $[a, b]$ and points $(x_i,y_i)$ with $a = x_1 < x_2 < \dots < x_n = b$.The $y_i$ are strictly decreasing, $y_i > y_{i+1}$. Now we can find a polynomial (of order $n-1$) which interpolates these $n$ points. The experience shows, that this polynomial is decreasing in $[a, b]$, too. How can this be proved?} \bigskip At first, thank you all for spending time on this: sending examples, Matlab code \& so on! \bigskip But I would like to specify the problem more clearly: \bigskip If you fix the intervall $[a, b]$ and take a {\em equidistant} decomposition of this: $a = x_1 < x_2 < ... < x_n = b$ Now take the $y_i$, which are strictly decreasing: $y_i > y_{i+1}$. The polynomial (of order $n-1$) which interpolates these $n$ points $(x_i,y_i)$ can be computed by the Newton-scheme, for example. Now the (numerical) experience shows the following: If $n$ is large enough (and the $y_i$ are decreasing), the interpolation-polynomial is decreasing in $[a, b]$, too. Ok, I know: if you interpolate in this way with a polynomial of order ($n-1$), you get maxima and minima and normally the polynomial oscillates between the single $x_i$ and you get {\em not} the smooth curve you wanted to have. But in this special case (with large $n$, but not too large?) it seems to be different! You "catch" a part of the polynomial, which is decreasing. Try it! I already know that interplolation by polynomials is the last thing to do (greetings to Chris Mueller {\tt 8-)}, better to use splines if you want to interplolate. \bigskip \underline{So here's our task:} Compute $n$ (and so the $x_i$) so that the polynomial (computed by Newton-scheme) is decreasing. Let $a=0$, $b=1$; the decreasing $y_i$ are given. Pay attention: if you increase $n$, you get other $x_i$, but let's say that it's possible to have $y_i$ for each $x_i$ in $[0, 1]$. Enjoy it! \bigskip {\bf Comments on this:} {\em John D'Errico (Email: derrico@pixel.kodak.com)\\ Eastman Kodak Company} \bigskip Regardless of how many points you choose to specify, if $n$ is greater than 2, I can give you a set of strictly decreasing function values, $y_i$, that will generate an interpolating polynomial that is not a decreasing function over the interval $[a, b]$. Period. This is provable. (It is immaterial what method you use to calculate the polynomial.) It turns out that the sets of data you are choosing to look at are ones which are well behaved enough that the polynomials you chose were indeed monotone. Many times this will happen. If you are interested, I will claim that you are asking the wrong question. A related, interesting question that might have an answer is: Given an equally spaced set of $n$ abscissae $x_i$ in the interval $[a, b]$, and a corresponding set of ordinates $y_i$, strictly decreasing, what can you say about the $n$-dimensional locus of the points $y_i$ which result in a monotone interpolating polynomial? First of all, this set is non-empty. If the points fall on a straight line, then the resulting interpolating polynomial will be the degenerate linear one, but for any $n$, there is at least one set of $y_i$ that generate a monotone polynomial. We can be arbitrary and scale the points always, so it is enough to consider $y_1=1$ and $y_n=0$. Next, is this $n$-dimensional locus a convex set? How large is this set? For example, what is the relative volume of this set compared to the set of all possible $y_i$ which are strictly monotone and also have $y_1=1$ and $y_n=0$? What is the behavior of this volume ratio as $n$ increases? Does this volume ratio approach unity as $n$ gets large, or does it go to zero? Well, I hope you get the idea. There are other interesting questions we might pose, none of which do I have the time to answer. \bigskip {\em Dave Rusin (Email: rusin@washington.math.niu.edu)\\ Northern Illinois University, Math} \bigskip The fact that this tends to be corroborated by numerical evidence suggests an interesting statistical problem: To show that, suitably interpreted, such-and-such {\em usually} occurs. However, it need not {\em always} occur. Suppose you have $y_1>...>y_n$ and a polynomial $f_1$ of degree $n-1$ or less such that $f(i)=y_i$ for all $i$. I will show you how to put in one more data point so as to mess up the monotonicity. Indeed, suppose you look for the curve that also passes thru $(n+1, y_{n+1} )$. This new function has to be $f_2(x) = f_1(x) + a \prod_{i=1}^n (x-i)$ for some $a$, namely $a=(y_{n+1} - f_1(n+1))/n!$. Since you have insisted on monotonic data, there is an upper bound on $a$ but anything less than that is consistent with the construction you request. Now consider $f_2(n-\frac{1}{2})$. This is $f_1(n-\frac{1}{2}) + a \prod_{i=1}^n (n-\frac{1}{2}-i)$. It is important to note that the coefficient of $a$ is negative. Thus with sufficiently negative values of $a$, we can make $f_2(n-\frac{1}{2})$ be as large as we want, and in particular larger than $f_2(n-1)=y_{n-1}$. It follows that for such $a$, the function $f_2$ is not decreasing. Possibly this construction relies on a rather larger drop from $y_n$ to $y_{n+1}$; thus if you wish to obtain the conclusion that $f$ be decreasing, you probably need to add some conditions along the lines of: for each $i$, $\frac{y_{i+1}-y_i}{y_i-y_{i-1}}$ is "close" to 1. But likely the labor needed to construct suitable hypotheses is much greater than the benefit to be gained. \bigskip \dots \bigskip OK, maybe that was a bit hasty. You could analyze it this way with some success: Let $L_i(x) = (x-1)(x-2)...(x-[i-1])$ and set $Y_i = \sum (-1)^j C(i-1, j)y_{i-j}$, where $C(a,b)$ is the binomial coeff. Then a formula for the interpolated curve is \[f(x) = \sum_1^n \frac{Y_i}{(i-1)!} L_i(x).\] If you want to have this be monotone decreasing, you need the derivative to be negative, that is, \[Y_2 + \sum_3^n \frac{Y_i}{(i-1)!} \dot{L}_i(x) < 0 \qquad \forall x \in [1, n] \] (or whatever the interval is on which you want $f$ to be decreasing). I've written it in this way because $Y_2 =y_2-y_1$ is already negative, so you need only assure that no other term is too big. For each $i$ and $n$ there is an upper bound on $\dot{L}_i(x)$ on $[1, n]$ (which I don't have a formula for, sorry), so the above derivative is indeed negative as long as the $Y_i$ are small, say as long as each $Y_i < \frac{1}{n} |Y_2| \frac{(i-1)!}{\max \dot{L}_i(x)}$. (Of course, the individual $Y_i$ don't need to be small, this is just one way to get it.) As a rule of thumb, the coefficients $Y_i$ do tend to be small if the data points are clustered along a curve of low degree. This probably accounts for the numerical evidence that led to the original conjecture. \end{document} ==============================================================================