Connect the Dots Like a Numerical Analyst

I have to say, teaching Numerical Analysis is one of the highlights of my job. Granted, my primary responsibility at Wayland is the Virtual Campus Director, and I will never teach Numerical Analysis online. Nevertheless, I LOVE it. In fact, the course banner that I use in Blackboard reinforces that fact to my students every time they log in:

Just as a for instance, I was able to get them to “solve” the age-old Connect-the-Dot problem. What is that, you ask? Well, simple: We all know, from the time we are toddlers, how to complete a Connect the Dot worksheet:

BUT, what is the mathematical solution? After all, math majors should look at the connect-the-dot worksheet and wonder, “What’s the equation of the solution?”

So today, as an introduction to using splines for interpolation, we derived the simple formulas for a piecewise linear interpolant:

Given a set of n+1 points with coordinates {(x_j, y_j)}_{j=0}^n, we can uniquely describe the piecewise linear function S(x) where S(x_i)=y_i for all i=0, 1, ldots, n, as follows:

S(x)=Big{ S_j(x),   xin[x_j,x_{j+1}]   , for j=0, 1, ldots, n-1

where S_j(x)=a_j x+b_j,

a_j = displaystyle frac{y_{j+1}-y_j}{x_{j+1}-x_j},

And b_j = y_j - a_j x_j for j=0, 1, ldots, n-1

At least, that’s the solution I told them in class today.  The truth is that’s not correct.  In fact, this will only “solve” the limited case where you always move left to right and never go back the other way.  What we really need is a parametric approach.  Given the initial data set above, we assign a parameter t in mathbb{R} to each point, say t=j for the point (x_j, y_j).  Then we have the following solution to the Connect-the-Dot problem:

Given a set of n+1 points with coordinates {(x_j, y_j)}_{j=0}^n, we can uniquely describe the piecewise linear parametric function bar{S}(t) where bar{S}(j)=(x_j,y_j) for all j=0, 1, ldots, n-1, as follows:

bar{S}(t) = Big{ biglangle S_{j,x}(t), S_{j,y}(t) bigrangle, for j=0, 1, ldots, n-1

where S_{j,x}(t)=a_{j,x} t+b_{j,x} and S_{j,y}(t)=a_{j,y} t+b_{j,y}

a_{j,x} = x_{j+1}-x_j and a_{j,y} = y_{j+1}-y_j

b_{j,x} = x_j - a_{j,x} t and b_{j,y} = y_j - a_{j,y} t for j=0, 1, ldots, n-1

That’s better, don’t you think?  From there we launched into a derivation of linear system approach to interpolation by natural cubic splines.  Then I ran out of time before finishing the derivation, which lead to the instagram post below…

That moment when class is over but you haven’t finished the proof… #mathteacherproblems

A photo posted by Scott Franklin (@splineguy) on

//platform.instagram.com/en_US/embeds.js

Advertisements

One thought on “Connect the Dots Like a Numerical Analyst

  1. Very nice! We did a splines project in Numerical Analysis in my undergrad where we had to find a picture of something (animal, lake, car, etc.), put it on a grid and build a cubic spline interpolation for it. Wish we’d thought of picking a connect-the-dots puzzle!.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s