## Defining Uniform B-Splines

In a previous post I spoke a little bit about B-Splines and in particular, Uniform B-Splines. I didn’t really go into much detail about how they are defined, how we decide what our b-spline is going to look like or even what an explicit expression for a spline would look like given our set of control points.

I decided to type up a LaTeX document which introduces the theory of b-splines. The document looks at b-splines from a practical perspective and so it doesn’t get too bogged down with the analysis side of things but concentrates on the tools required to find explicit expressions for b-splines.

The document contains expressions for piecing together a b-spline. I spent a good number of hours deriving these expressions and they got very messy to deal with but, eventually, persistence prevailed. It is likely that someone, somewhere has already derived these formulae but by doing the work myself I was able to learn so much about these splines that I wouldn’t have appreciated if I had just read someone else’s work.

This is one of the most important things about becoming better as a mathematician – being prepared to spend time with a problem and being willing to make a lot of mistakes until you get things right. Persistence is rarely a bad thing. I make no apology for the length of some of the expressions – I have not made any real attempt to simplify the expressions as I feel that it would be a glorious waste of time to try and do so. If anyone out there would like to have a go at tidying up the expressions then feel free to go right ahead.

## Finite Difference Methods in Two Dimensions

During my final year at Warwick University I did a project on Numerical Weather Forecasting and one of the methods that came up was the method of finite differences. I recently came across finite differences again over the last few weeks and how they can be used to solve some partial differential equations (PDEs). Here is an example that I found in one of my books that I decided to play around with

Solve, using the method of finite differences, the PDE $$x\dfrac{\partial{f}}{\partial{x}}+(y+1)\dfrac{\partial{f}}{\partial{y}}=0$$ for $0\leq x,y \leq 1$ with $$f(x,0)=x-1$$ $$f(x,1)=\dfrac{x-2}{2}$$ $$f(0,y)=-1$$ $$f(1,y)=-\dfrac{y}{y+1}$$

To solve this problem I used the central difference equations given by

$$\dfrac{\partial{f}}{\partial{x}}\approx \dfrac{f(x+h,y)-f(x-h,y)}{2h}$$

$$\dfrac{\partial{f}}{\partial{y}}\approx \dfrac{f(x,y+k)-f(x,y-k)}{2k}$$

with a step length in both the $x$ and $y$ directions of $\frac{1}{3}$. The domain can be overlaid with a grid as shown in the diagram

This makes the whole problem easier to deal with because now we can see visually what is happening rather than just dealing with everything purely algebraically – there’s no need to make things more difficult than they need to be after all.

The idea is to form a system of four simultaneous equations with $A$, $B$, $C$, and $D$ as the unknown quantities. When the system is solved then the values obtained correspond to the approximate values of $f$ at each of the grid points. Here is my full solution to this problem – PDE Solution Using Finite Differences. This fills in some of the gaps in our knowledge about the function $f$ but there is still a lot of information missing – in particular the points between the grid points.

To resolve this we can make the step-lengths smaller and create more interior grid points. This gives us more information but at a price – for example with a step length of $\frac{1}{5}$ in both directions we would have a system of $16$ simultaneous equations in $16$ unknowns – I don’t really fancy sorting that mess out without the help of a computer. And what’s more – as the step-length gets even smaller we get more and more complicated systems with more unknowns so eventually we would reach a point where even a computer would struggle to do anything with the information.

Nevertheless – finite difference methods are used and are useful for all kinds of problems and can provide a very visual way of numerically solving some otherwise very difficult equations.

## Uniform B-Splines

Over the last few days I have been getting interested in basis-splines (or B-Splines). B-Splines are functions $Q(u)$ that are piecewise polynomial of degree $n$, which means that they are made up of sections of polynomials of degree $n$ attached together, that approximate a polygon (called a control polygon).

The sections of polynomials are fitted together smoothly – how smoothly depends on the degree of the polynomials that make up the spline. For example a spline of degree $3$ is made up of sections of cubic polynomials such that the first and second derivatives of the spline $Q(u)$ are continuous at the attachment point but will usually fail to be three times differentiable at these points. More generally – for a spline $Q(u)$ of degree $n$, then $Q(u)$ will be $n-1$ times differentiable but will usually fail to be $n$ times differentiable.

For example, in the following diagram the control polygon is shown in red and the spline, shown in blue, is piecewise cubic

Cubic B-Spline

The attachment points for this spline are at the integer values along the $x$ axis –  I chose integer points because it makes the algebra considerably easier but in theory there is nothing restricting me to these points. Strictly speaking this is a uniform B-Spline which means that the attachment points are at regular intervals; if the attachment points occur on intervals of different lengths then it is a non-uniform spline which are also very commonly used.

The following graph is a graph of the first derivative of the above spline

Graph of the first derivative of a cubic B-Spline

Clearly this curve is continuous. I have fixed the spline so that the attachment points occur at integer values on the $x$-axis and importantly this curve is continuous at each of these points. We are not necessarily interested in what happens in between these points so it is a bit of a bonus that the derivative is continuous at all intermediate points. Now let’s look at the second derivative

Graph of the second derivative of a cubic B-Spline

Again the graph is continuous but we can see just by looking at the graph that it fails to be differentiable at the attachment points – but this is what we expect to happen. The only way that this spline could be more than twice differentiable would be if it was only made up of a single section – but this wouldn’t be a very interesting spline really…

Splines and spline interpolation are very useful in computer-aided design and particularly in computer games design. There is so much that I have learned and have yet to learn about splines that I can’t possible fit everything into a single post so I’m sure that I will be coming back to this topic again very soon.

## Polynomial Interpolation – Lagrange Representations

Interpolation is widely used in mathematics and in the sciences – mathematics tends to concentrate on the theoretical side of things and the methods are then used by scientists with the confidence that what they are using works.

What is interpolation? Well an example would be if you are measuring the temperature outside on a particular day then you would take the temperature at certain times and record the temperature – but what about the times in between? We can’t record everything but we might need to know what the temperature was at one of these intermediate times – this is where interpolation comes in. Interpolation is a way of “joining the dots” within (not outside) a dataset so that estimates can be made about the behaviour. This can be done in hundreds of different ways using different methods each with their pros and cons.

In a previous post I talked about the limitations of Euler’s method – well here I’m going to talk about the limitations of polynomial interpolation and specifically the Lagrange representation and one way that the problem can be partially resolved. Don’t misunderstand me – the Lagrange representation is very useful but it, as with almost any numerical technique, has its own problems.

Let’s look at the function $f(x)=\dfrac{1}{1+25x^{2}}$ on the interval $[-1,1]$. This is what it looks like

A graph of f(x) drawn using SAGE Math

Now given $n+1$ distinct points $x_{0}, x_{1}, \ldots , x_{n}$ in $[-1,1]$ and their corresponding $y$-values $y_{0}, y_{1}, \ldots , y_{n}$ then the Lagrange representation is defined as $$P_{n}=\sum_{j=0}^{n}y_{j}\ell_{j}$$ where $$\ell_{j}=\prod_{i=0,i\neq k}^{n}\dfrac{x-x_{i}}{x_{k}-x_{i}}$$

This representation can be proved to be unique and that $P(x_{i})=y_{i}$ but I don’t want to get sidetracked with this. So going back to the function $f(x)$ – first I’m going to choose $5$ equally-spaced points along the interval [-1,1]. The resulting interpolating polynomial looks as follows (I am not going to try to write an expression for the interpolating polynomials because they are very difficult to find explicitly and they don’t really tell us anything anyway)

Lagrange representation of f(x) with 5 equally spaced points

The interpolating curve is shown in red and $f(x)$ is shown in blue. This is not bad, after all we only have $5$ points to work with so we might expect that as the number of points increases we get a more accurate picture – right? Well…no. As the number of points increases we have to increase the degree of the interpolating polynomial and if we choose $10$ equally spaced points on the interval $[-1,1]$ we get this picture

Lagrange representation of f(x) with 10 equally spaced points

Things are starting to go a bit awry – maybe if we increase the number of points even further then things will start to settle down. Let’s look what happens when we have $16$ equally spaced points.

Lagrange representation of f(x) with 16 equally spaced points

Maybe that wasn’t such a good idea. Things are starting to get so out of control that as the number of interpolation points (and consequently the degree of the interpolating polynomial) increases, the interpolating polynomial oscillates wildly between both extremely large positive and extremely large negative values near the edges of the interval $[-1,1]$. This behaviour gets so bad $n$ increases that the interpolating polynomial grows without bound near the edges of the interval – this is known as Runge’s phenomenon and makes the interpolating polynomial practically useless.

One way around this is to choose a different set of interpolation points. One of the problems is the equal spacing of the points – to resolve this in part we can choose Chebyshev nodes. Using these Chebyshev nodes we get a very different picture – the following diagram shows what things look like when $10$ points are chosen

Lagrange representation of f(x) using 10 Chebyshev nodes

Now compare that to what we had before and we see something that is much better behaved. Has Runge’s phenomenon been eliminated? Mostly, yes – but in truth it can never be completely eliminated; the Chebyshev nodes, however, massively reduce the effects of Runge’s phenomenon. Runge’s phenomenon does not always occur but it is something that can go wrong from time-to-time, so as with all numerical methods you have to take care when applying the method to solve problems; there may be another more suitable method that needs to be applied.

## The Limitations of Euler’s Method

There are many examples of differential equations that cannot be solved analytically – in fact, it is very rare for a differential equation to have an explicit solution. Euler’s Method is a way of numerically solving differential equations that are difficult or that can’t be solved analytically. Euler’s method, however, still has its limitations.

For a differential equation $y^{\prime}=f(x,y(x))$ with initial condition $y(x_{0})=y_{0}$ we can choose a step-length $h$ and approximate the solution to the differential equation by defining $x_{n}=x_{0}+nh$ and then for each $x_{n}$ finding a corresponding $y_{n}$ where $y_{n}=x_{n-1}+hf(x_{n-1},y_{n-1})$. This method works quite well in many cases and gives good approxiamtions to the actual solution to a differential equation, but there are some differential equations that are very sensitive to the choice of step-length $h$ as the following demonstrates.

Let’s look at the differential equation $y^{\prime}+110y=100$ with initial condition $y(0)=2$.

This differential equation has an exact solution given by $y=1+\mathrm{e}^{-100t}$ but this example is a very good example which demonstrates that Euler’s method cannot be used blindly. Let’s look at what happens for a few different step-lengths.

For the step-length $h=0.019$ step-length we get the following behaviour

The red curve is the actual solution and the blue curve represents the behaviour of the numerical solution given by the Euler method – it is clear that the numerical solution converges to the actual solution so we should be very happy. However, look what happens when the step-length $h=0.021$ is chosen

Again the actual solution is represented by the red line which on this diagram looks like a flat line because the blue curve gets bigger and bigger as you move along the $x$-axis. So a change of just $0.002$ in the step-length has completely changed the behaviour of the numerical solution. For a step-length $h=0.03$ the graph would look as follows

The actual solution can barely be seen and the numerical solution gets out of control very quickly – this solution is completely useless – the scales on the $y$-axis are enormous and increasing the step-length only makes this worse. What has happened?

It can be shown by induction that for $n \in \mathbb{N}$ that $y_{n}=1+(1-100h)^{n}$. This converges only for $h<0.02$ and diverges for $h>0.02$. $h=0.02$ is a limiting case and gives an oscillating numerical solution that looks as follows

For this particular example for $h<0.02$ and as the step-length gets closer to $0$ the solution will converge faster and for $h>0.02$ as the step-length increases the solution will diverge more rapidly.

So even though we have Euler’s method at our disposal for differential equations this example shows that care must be taken when dealing with numerical solutions because they may not always behave as you want them to. This differential equation is an example of a stiff equation – in other words, one that is very sensitive to the choice of step length. In general as the step-length increases the accuracy of the solution decreases but not all differential equations will be as sensitive to the step-length as this differential equation – but they do exist.