One problem with GPS datasets is that there are often gaps in the data, which may skew data results and prevent transformation into the frequency domain. Another problem is that the time scales in GPS data sets are often non-linear. Interpolation solves these problems by filling the gaps in the data. A large number of interpolation methods exists, all having their advantages and disadvantages for different applications. As a result, the GDMS offers six different interpolation methods:- Nearest Neighbour Linear Cubic Spline Natural Spline Newton Divided Difference Least Squares Theoretically, each of the datasets that we analyse are sampled once a day at exactly 12:00. This is, however, not always possible for reasons such as such as equipment failure, extreme weather and in some case local politics. The Fourier transform algorithms available to us require that the dataset be regular. This means that if a dataset is missing a point or has an irregular sample rate then it can not be transferred to the frequency domain. The dataset therefore, must be made regular either by removing points or interpolating new points. This irregular sampling rate has been compounded by having the datasets stored on a non-linear time scale. The data that we have been provided has been sampled once a day at noon as timed by an atomic clock, thereby allowing an accurate sample rate. The sample date/time, however, has then been stored in decimal year format to eight significant figures, and this creates a problem. During a regular year one day is 0.00273972, except one in every four years is a leap year and the length of a day then becomes 0.00273224. Also at the start of each year a rounding occurs so that the first reading of the year occurs at XXXX.0014. This rounding creates the illusion of a different time distance between the last day of one year and the first day of the next. Due to the nature of this problem, it is necessary to transform the data scale to be independent of calender years before carrying out interpolation. The new time scale that we convert to is what is known as a truncated Julian day. The Julian day system uses an integer day count since the first of January 4714 BC. This, however, produces extremely large numbers which could potentially cause loss of accuracy due to machine limitations. To prevent this we have used the first of January 1901 as our start date. The existing decimal dates then converted to truncated Julian day and rounded to the nearest whole number. Once the timescale is linear, interpolation can be carried out on the data without fear of loss of data or returning inaccurately interpolated points. Different interpolation methods have different strengths and weaknesses. On an arbitrary dataset it is impossible to tell which interpolation method will be the most accurate, and as such six different interpolation methods have been provided. Each will be outlined below, including details on its operation, strengths and weaknesses. Nearest neighbour interpolation is the simplest method provided. This method sets the value of any new point to the value of the nearest point on the original dataset. The advantage of this is that any added points will be of the same approximate value as nearby points. There are a number of disadvantages with nearest neighbour approximation. Firstly, any new points will not follow any linear or frequency trends in the data, which could lead to inaccuracy of models both in the time and frequency domains. In addition, if new points lie close to outliers then the points generated can be very inaccurate. Linear interpolation is widely used as it is simple, yet generally produces better results than nearest neighbour. In this interpolation method, each new point is placed on a line between the two adjacent points. The Equation for adding a new point is: eqimginterp_linear.bmp Linear interpolation has several advantages. Firstly, each added point has a value that is approximately the same as nearby value thus obtaining values significantly out of range are very rare. Secondly, the added point will follow any local linear trends between the two points. The disadvantages of linear interpolation stem from the interpolation method only working with the two adjacent points. If the line between these two points does not follow the overall trend of the data then loss of accuracy occurs. The GDMS includes one of the many implementations of cubic spline interpolation. This specific implementation, has no particular name and is given the generic title of cubic spline interpolation. The only difference between this method and a natural spline is the choice of second derivatives used at the end points. With this implementation the values of the second derivative for the end points are set the same as the second derivatives of the second to end points. To produce a spine for a dataset of n+1 points you have to produce n separate cubics. Each of these cubic should have each end match up exactly with the points to either side. And on the same point the two adjacent cubic should have shared first and second derivatives. Each of these cubics can be described by the equation: eqimginterp_cubic.bmp Because each of these cubics begins at a any existing point we can say: di = yi where hi=(xi+1 - xi), is the width of the the interval. Also if we make S the set of second derivatives; then through algebraic simplification we can get: eqimginterp_spline_abc.bmp With cubic splines, solving for S is achieved by solving: eqimginterp_S_cubic.bmp The two end values, S0 and Sn, are then set to equal S1 and Sn respectively. A full mathematical derivation can be found in Gerald & Wheatley (1999), page 238. Splines can provide extremely accurate results when the original sample rate is notable greater than the frequency of fluctuation in the data. However if the sample rate is less than half the frequency of change (including signal noise) in the data then the results can be erratic. Splines also have a problem when it comes to large gaps in the dataset. Because the gap between two points is represented by a cubic, large gaps result in peaks or troughs in the dataset. The final problem with spline is that the end sections are inaccurate due to arbitrary methods used to assign the derivative of the end points. In the case of cubic splines, the end points tend to be too curved and it is for this reason that two cubic spline methods have been provided for this application. Natural splines are a type of cubic spline, originating in ancient times, that is before the birth of Christ, when drafts-men and builders would create a smooth curve by pegging a flexible piece of wood between a number of points. As with all cubic spline implementations, the interpolation is achieved by inserting a cubic between each two adjacent points. Equalising the derivatives has the effect of making the resulting interpolation appear smooth and visually pleasing. For this reason splines are often used in graphics. In the mathematical process of building splines it is impossible to infer the derivatives of the two end points of a dataset. It is the values assigned to these end points that determine the type of spine. In a natural spline the end points are set to 0. This gives a result similar to the ancient wooden splines used by builders. Mathematically this produces a result where the end segments can be too straight. To produce a spine for a dataset of n+1 points you have to produce n separate cubics. Each of these cubic should have each end match up exactly with the points to either side. And on the same point the two adjacent cubic should have shared first and second derivatives. Each of these cubics can be described by the equation: eqimginterp_cubic.bmp Because each of these cubics begins at a point we can say: di = yi Where hi=(xi+1 - xi) , is the width of the the interval. Also if we make S the set of second derivatives; then through algebraic simplification we can get: eqimginterp_spline_abc.bmp With natural splines solving for S is done by solving: eqimginterp_S_natural.bmp The two end values, S0 and Sn, are then set to zero. A full mathematical derivation can be found in Gerald & Wheatley (1999), page 238. Mathematicians have long know that a nth order difference table can be used to accurately recreate a polynomial of degree n. Newton divided differences uses a similar method to approximate new points within an tributary dataset. The Newton divided differences method is based on building a table of divided differences. The divided difference between two points in a dataset is defined as: eqimginterp_DD1.bmp Likewise higher order divided differences can be defined as: eqimginterp_DD2.bmp These divided differences are built into a table as follows: eqimginterp_DD3.bmp This table can then be used to generate an equation: eqimginterp_DD4.bmp A full mathematical derivation can be found in Gerald & Wheatley (1999), page 229. Because divided differences estimates a curve by using polynomial, using a polynomial of too low or high a degree can result in errors. The accuracy available by using the double precision floating point format also creates a limit. To detect and limit the errors caused by these factors the error estimates can be calculated. As the divided difference table grows it calculates the rough error for a table of size one less. If the error estimate has shrunk then the program continues building the table to a higher order. If the error has grown then the program stops building the table. The error for a divided difference of a given order is approximately equal to the change that will be incurred by increasing the order of the divided difference table by one. So for an order n newton divided difference interpolation the mathematical definition of the error is: A full mathematical derivation can be found in Gerald & Wheatley (1999), page 229. Interpolation methods provide a useful toolkit that can be used to remove defects within the dataset. They can be used to fill holes in the time series, allowing the general trend of these missing points to be seen as well Fourier transforms to be applied to the given data system. No one interpolation method, however, is guaranteed to correctly estimate the missing data points for every data set, due to the nature of the individual characteristics of the gaps. It is for this reason that six different interpolation methods have been provided.