mscroggs.co.uk
mscroggs.co.uk
Click here to win prizes by solving the mscroggs.co.uk puzzle Advent calendar.
Click here to win prizes by solving the mscroggs.co.uk puzzle Advent calendar.

subscribe

Blog

 2018-09-13 
This is a post I wrote for round 2 of The Aperiodical's Big Internet Math-Off 2018. As I went out in round 1 of the Big Math-Off, you got to read about the real projective plane instead of this.
Polynomials are very nice functions: they're easy to integrate and differentiate, it's quick to calculate their value at points, and they're generally friendly to deal with. Because of this, it can often be useful to find a polynomial that closely approximates a more complicated function.
Imagine a function defined for \(x\) between -1 and 1. Pick \(n-1\) points that lie on the function. There is a unique degree \(n\) polynomial (a polynomial whose highest power of \(x\) is \(x^n\)) that passes through these points. This polynomial is called an interpolating polynomial, and it sounds like it ought to be a pretty good approximation of the function.
So let's try taking points on a function at equally spaced values of \(x\), and try to approximate the function:
$$f(x)=\frac1{1+25x^2}$$
Polynomial interpolations of \(\displaystyle f(x)=\frac1{1+25x^2}\) using equally spaced points
I'm sure you'll agree that these approximations are pretty terrible, and they get worse as more points are added. The high error towards 1 and -1 is called Runge's phenomenon, and was discovered in 1901 by Carl David Tolmé Runge.
All hope of finding a good polynomial approximation is not lost, however: by choosing the points more carefully, it's possible to avoid Runge's phenomenon. Chebyshev points (named after Pafnuty Chebyshev) are defined by taking the \(x\) co-ordinate of equally spaced points on a circle.
Eight Chebyshev points
The following GIF shows interpolating polynomials of the same function as before using Chebyshev points.
Nice, we've found a polynomial that closely approximates the function... But I guess you're now wondering how well the Chebyshev interpolation will approximate other functions. To find out, let's try it out on the votes over time of my first round Big Internet Math-Off match.
Scroggs vs Parker, 6-8 July 2018
The graphs below show the results of the match over time interpolated using 16 uniform points (left) and 16 Chebyshev points (right). You can see that the uniform interpolation is all over the place, but the Chebyshev interpolation is very close the the actual results.
Scroggs vs Parker, 6-8 July 2018, approximated using uniform points (left) and Chebyshev points (right)
But maybe you still want to see how good Chebyshev interpolation is for a function of your choice... To help you find out, I've written @RungeBot, a Twitter bot that can compare interpolations with equispaced and Chebyshev points. Just tweet it a function, and it'll show you how bad Runge's phenomenon is for that function, and how much better Chebysheb points are.
A list of constants and functions that RungeBot understands can be found here.

Similar posts

A surprising fact about quadrilaterals
Interesting tautologies
Big Internet Math-Off stickers 2019
Mathsteroids

Comments

Comments in green were written by me. Comments in blue were not written by me.
 Add a Comment 


I will only use your email address to reply to your comment (if a reply is needed).

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li>
To prove you are not a spam bot, please type "vector" in the box below (case sensitive):

Archive

Show me a random blog post
 2020 

Nov 2020

Christmas (2020) is coming!

Jul 2020

Happy √3+1 Approximation Day!

May 2020

A surprising fact about quadrilaterals
Interesting tautologies

Mar 2020

Log-scaled axes

Feb 2020

PhD thesis, chapter ∞
PhD thesis, chapter 5
PhD thesis, chapter 4
PhD thesis, chapter 3
Inverting a matrix
PhD thesis, chapter 2

Jan 2020

PhD thesis, chapter 1
Gaussian elimination
Matrix multiplication
Christmas (2019) is over
 2019 
▼ show ▼
 2018 
▼ show ▼
 2017 
▼ show ▼
 2016 
▼ show ▼
 2015 
▼ show ▼
 2014 
▼ show ▼
 2013 
▼ show ▼
 2012 
▼ show ▼

Tags

christmas tennis data visualisation sport javascript football palindromes captain scarlet finite element method pi approximation day harriss spiral mathsteroids triangles folding tube maps dates speed estimation craft european cup matrix of minors pi cambridge misleading statistics logic go frobel flexagons probability chess simultaneous equations preconditioning trigonometry hexapawn nine men's morris game of life twitter curvature pythagoras dragon curves mathslogicbot signorini conditions martin gardner cross stitch bodmas bubble bobble video games weather station the aperiodical interpolation electromagnetic field talking maths in public advent calendar gerry anderson matt parker matrices bempp latex inline code chebyshev world cup coins exponential growth puzzles python menace folding paper boundary element methods countdown rhombicuboctahedron sorting matrix of cofactors realhats statistics geometry braiding london underground reuleaux polygons manchester science festival london ternary computational complexity big internet math-off platonic solids stickers wave scattering mathsjam logs gaussian elimination weak imposition christmas card reddit game show probability arithmetic pizza cutting numerical analysis propositional calculus hannah fry php quadrilaterals graph theory accuracy pac-man people maths royal institution fractals golden ratio books noughts and crosses polynomials approximation manchester oeis binary rugby radio 4 graphs light draughts phd inverse matrices tmip a gamut of games dataset national lottery plastic ratio convergence wool determinants machine learning map projections news sobolev spaces geogebra asteroids hats royal baby matrix multiplication programming data sound games chalkdust magazine error bars ucl golden spiral raspberry pi final fantasy squares

Archive

Show me a random blog post
▼ show ▼
© Matthew Scroggs 2012–2020