The Problem with Polynomials

To view this worksheet actively, first download it to your computer using the link above.  Then, create an account for yourself at https://cloud.sagemath.com/ .  Upload this worksheet into that site and enjoy!

"The Problem with Polynomials"

John Travis

Mississippi College

January, 2015

Presented at Tougaloo College Forum...January 23, 2015

Ever done one of those Facebook IQ tests?  

from http://www.themarysue.com/iq-tests-how-do-they-work/ 

A typical question in these exams is something on the order of:

Determine the next term in the sequence given by

1, 4, 7, 11, 15, ...

So, what's the answer?

Choice 1:

1 + 3 = 4

4 + 3 = 7

7 + 4 = 11

11 + 4 = 15

15 + 5 = 20

20 + 5 = 25

26 + 6 = 32

...

Choice 2:

1 = one, the first integer with three letters

4 = four, is the first integer after 1 with four letters

7 = seven, is the first integer after 4 with five letters

11 = eleven, is the first integer after 7 with six letters

15 = fifteen, is the first integer after 11 with seven letters

18 = eighteen, is the first integer after 15 with eight letters

21 = twentyone, is the first integer after 21 with nine letters

24 = twentyfour, ...

So, which is the correct answer?

It can be anything you want...

How does one determine what comes next?  Is there a "formula" to determine things.

Ever since a student is first introduced to the idea of functions, most examples have centered around "nice" functions and especially polynomials.  For example, consider the homework set from Stewart's Calculus 7th edition:

Polynomials are often used since they are relatively easy to evaluate and use.  

Are they helpful though as mathematical models for making predictions and estimations?

From http://www.epa.gov/climatechange/science/future.html , observed and projected changes in global average temperature

The process of determining exact values for past dates is actually not exact but it is even more reasonable to question the projections made for dates in the future.  

What about world population?  

Consider the following data representing world population (in millions) collected from http://www.ecology.com/population-estimates-year-2050/ .  Notice the projections indicated for 2020, 2030, 2040, and 2050.

For now, let's presume that the population values for 1910-2010 are reasonably close.  If so, then we can look back and estimate the population for years between the data points using a process known as interpolation.  

Interpolation presumes that the user can utilize some (continuous) function which meets all of the given data values precisely but which can be evaluated at any time to give an estimate between the data values.  That is, $f(x)$ interpolates the data points

$(x_0,y_0), (x_1,y_1), (x_2,y_2),  ... (x_n,y_n) $

provided

$\forall k \in \left \{  0, 1, ... , n  \right \}, f(x_k) = y_k  $.

On the other hand, once a successful interpolating function $f(x)$ has been generated, one often utilizes the formula which was designed to estimate values between data points to estimate values beyond the given data points.  This process is known as extrapolation.  This is similar to using a formula for the IQ sequence to predict the next terms in the sequence.

Notice, each of these do interpolate the single given data point $(1,3)$:

$f_1(1) = 3$

$f_2(1) = - \frac{5}{8}(1)^2 + (1) + \frac{21}{8} = 3$

$f_3(1) = \frac{9}{(1)+2} = 3$

$f_4(1) = \frac{18 sin^{-1}((1)-\frac{1}{2})}{\pi} = \frac{18*\pi/6}{\pi} = 3$

What about more than one data point?  For our population data above we are given 11 population data points from 1910-2010 so finding a formula in general which passes through them all in a reasonable fashion can be somewhat messy if we proceed as above.  To make this easier, we will look for the foumula to be as simple as possible.  Our experience in the past has been that polynomials are the easiest functions to deal with so let's look for a polynomial of smallest degree possible.  Such a polynomial $p(x)$ is called the Lagrange Polynomial.

For the interactive cell below, type in a list of data points.  Since we want a function to interpolate these points then all of the x-values must be distinct.

General basis formula for Lagrange:

p(x) = $\sum_{k=0}^{n} \prod_{k \ne j} {\frac{x-x_j}{x_k-x_j}}$

For example, to interpolate the data points originally given above (1, 3), (2, 1), (4, 0), simply write:

$p(x) = 3 \frac{(x-2)(x-4)}{(1-2)(1-4)}+1\frac{(x-1)(x-4)}{(2-1)(2-4)}+0\frac{(x-1)(x-2)}{(4-1)(4-2)}$

Student look up:

• Vandermonde Matrix Interpolation
• Newton's Divided Differences

Notice, as the number of data points increases so does the degree of the resulting polynomial and therefore so does the number of changes of inflection.  In general, the Lagrange polynomial interpolating n+1 data points with distinct x-values will be of degree n (or less.)

So, let's use the Lagrange Interpolating Polynomial to address the world population data.  We get different formulas dependent upon how many years we want to take into account.

Notice that as we interpolate more points not only does the degree of the resulting polynomial increase but also the coefficients become increasingly large and alternating in sign.  This yields a corresponding decrease in computational accuracy due to round-off issues and ultimately yields a formula which, while technically precise, is practically useless.  

Student look up:  What are the benefits of "Horner's Method"?

So, can we expect these formulas to be useful at all for extrapolation as well?  Using the cell above we get the following interpolants:

1920-1940:  

$ p_1(x) = \frac{1}{10}x^2 - 364x +332100 $ 

1950-2010:  

$p_2(x) = \frac{33}{40000000}x^6 - \frac{117613}{12000000}x^5 + \frac{11643529}{240000}x^4 - \frac{3073782307}{24000}x^3 + \frac{570538028629}{3000}x^2 - \frac{7530504229893}{50}x + 49696300029814$

1970-2010:  

$p_3(x) = \frac{23}{40000}x^4 - \frac{367}{80}x^3 + \frac{5489919}{400}x^2 - \frac{91245562}{5}x + 9099040894$

How well do these work for predicting the future (forecasting)?  Or recreating the past (hindcasting)?

Notice how bad these Lagrange polynomials are for extrapolation.  

The problem is even worse actually in that polynomials are VERY sensitive to the values of their higher order coefficients.  Indeed, the basis approach takes "factored" terms such as described below:

Consider the following polynomial which has easy to determine roots at $1, 2, ..., 20$:

$p(x) = (x-1)(x-2)(x-3) ... (x-20)$ 

Below, we look at variants of this and note how just determining the roots works out when we change of value of the (n-1)st order term's coefficient by 0.000001.

Certainly there is some function which will precisely measure the world population for any time in the future...if we only knew it then it would be of great interest! 

We see that the use of Lagrange polynomials is possible for interplolation and extrapolation but they might not be actually helpful in practice since drastic changes occur when in the presence of roundoff or when the data might be imprecise.

What if we remove the restriction that we precisely interpolate data points but only require us to be close.

Weierstrass Approximation Theorem

If $f$ is a continuous real-valued function on $[a,b]$, then $\forall \epsilon > 0, \exists $ a polynomial $p$ on $[a,b]$ such that

$|f(x) - p(x)| < \epsilon, \forall x \in [a,b]$  

This means, in other words, that there is a polynomial of perhaps high degree which approximates the actual world population to within any desired degree of accuracy.  

The problem is that this result is an existence result and not a constructive one so we have no idea how to obtain what is guaranteed.

Rather than interpolating at a large collection of data points, why not just interpolate "really well" at just one.  Indeed, this might work well if you have more information...such as slope and curvature...at a point or collection of points.  

Taylor Polynomials - satisfying positional data as well a given number of derivative values at one point

Let's apply this single point approach to the population data...

It turns out that even interpolation is sometimes messy.  For example, let's use a Lagrange Polynomial to approximate the rational function

$f(x) = \frac{1}{1+x^2}$

on $[-4,4]$.

Ok then.  If interpolation doesn't yield a good model for extrapolation, let's try to get something "close" to the data points (ala Weierstrass Theorem).   

Least Squares

Best Fit

Regression

The next best thing might be to break up the data into pieces and approximate using several low degree polynomials.  This will help with interpolation but not with extrapolation.

The next best thing might be to break up the data into pieces and approximate using several low degree polynomials.  This will help with interpolation but not with extrapolation.

What about using piecewise cubics...with slopes (i.e. derivatives) provided at each data point as well. 

Hermite Interpolation

So, we can use polynomials to interpolate so long as they don't get of too high degree or provided the numerical coefficients are too large.  But neither regular polynomials or piecewise versions are very helpful for extrapolation.

What to do?

Rather than trying to predict the future population data using the past only, perhaps it would be better to model the underlying dynamics to obtain a formula for extrapolation.

Model 1:  Population growth is proportional to the size of the existing population.

In mathematical terms, if P(t) is the population at time t:

$P'(t) = k P(t)$

for some parameter k, which has solution

$P(t) = P_0 e^{kt}$

Conclusion:  We love polynomials because they are easy to evaluate and manipulate.  However, using them in practical situations must be done with great care and especially so if we are using them for making predication that matter.