Least Squares Data Fitting with Applications

11. Linear Least Squares Applications

Chapter 11 Linear Least Squares Applications We now present in detail two larger applications of linear least squares for fitting of temperature profiles and geological surface modeling. Both of them use splines, so for completeness, we start with a summary of their definitions and basic properties. 11.1 Splines in approximation This is a short summary of splines with an emphasis on univariate and bivariate cubic splines, their B-splines representation, and their use in least squares approximation. The topic of splines is important in many data fitting applications, especially where there is no pre-determined functional form. There is a distinct advantage in using splines for data representation, whether in interpolation or least squares approximation, because of their local support and consequent good quality of local approximation. We concentrate in detail on cubic splines because they are well suited to our type of applications. For an exhaustive discussion see some of the classical books, such as [7, 29, 69]. Univariate splines A spline is a function defined piecewise over its domain by polynomials of a certain degree that are joined together smoothly. Definition 101. A spline s(k) (x) of degree k, with domain [a, b] and nodes or knots (breakpoints) a = t0 ≤ t1 ≤ . . . ≤ tN = b has the following properties: 203 204 LEAST SQUARES DATA FITTING WITH APPLICATIONS Figure 11.1.1: Left: four consecutive cubic B-splines defined on the uniformly distributed knots tj = 0, 2, . . . , 7. Right: Cubic spline with coincident end knots at 0. • it is a polynomial of degree k in each subinterval [tj, tj+1], j = 0, . . . , N − 1; • at each interior knot t1, . . . , tN−1 that does not coincide with its neighbors, the function s(k) (x) and its derivatives up to order k − 1 are continuous. The class of such splines is a linear function space of dimension N + k, as one can verify from the number of conditions imposed for the continuity of the splines and its derivatives. There are various possible representations for a spline function, but the numerically most stable is in terms of a basis of B-splines. Definition 102. Given the non-decreasing sequence of knots {tj}j=0,...,N , the normalized jth B-spline of degree k is defined by B (k) j (x) = (tj+k+1 − tj) [tj, . . . , tj+k+1] (t − x)k +, where (t − x)k + ≡ max((t − x)k , 0) is the truncation function and [tj, . . . , tj+k+1](t−x)k + denotes the kth divided difference of the truncation function with x fixed. Each B (k) j (x) is in fact a specific k-degree spline with local support or “active” on [tj, tj+k+1], i.e., nonzero only in k + 1 consecutive subintervals. Vice versa, at any [tj, tj+1], only k + 1 nonzero B-splines overlap. Also, at any x ∈ [tj, tj+1], the sum  j B (k) j (x) = 1. If the knots are uniformly distributed, the maximum value of any B-spline B (k) j (x) occurs at the midpoint of its “definition” interval. See Figure 11.1.1 for an illustration with k = 3. Instead of deriving the B-splines from the definition, one can generate a B-spline of any degree recursively, starting from the piecewise constant LINEAR LEAST SQUARES APPLICATIONS 205 B-splines B (0) j , by using the de Boor-Cox formulas on the knot sequence {tj}j=0,...,m. For k = 1, 2, ... • B (0) j (x) =  1, tj ≤ t O(106 ), whereas with a nonuniform one it can be done with N ≈ 70 (see [202], p. 255). Some of the algorithms that use nonuniform knot sequences may require the addition of knots. It is of interest therefore to have a technique that, given a spline s(x) defined on a knot sequence {tj}j=0,...,m, computes the coefficients of the representation of the spline when some knots have been inserted, maybe for added accuracy. An efficient algorithm for this is the Oslo algorithm, described in [69], chapter 1. In the same reference, formulas for the derivative and integral of splines are given, as well as an algorithm for calculating the Fourier coefficients that is of interest in signal processing. Cubic splines least squares approximation Originally, splines were designed for interpolation, but this is not appropriate in the presence of noise. In this...