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.