Surface Fitting¶
Linear Equations¶
A linear equation is one whose coefficients appear linearly in the expression. For example, the following equation is linear in its coefficients:
The coefficients a, b, c, d, and e all linearly multiply a basis function of x, y, or both x and y. Such linear equations can be solved in a single step matrix solution.
Note that linear equations refer to the relationship between the coefficients and basis functions, not to the graphical appearance of the surface. A surface may have a wildly non-linear or non-planar appearance, but yet be formed by a linear equation.
Non-Linear Equations¶
A non-linear equation, on the other hand, is one where the coefficients appear in a non-linear or nested fashion. The following equation is linear only in the a and b coefficients, and non-linear in c, d, e, and f:
A non-linear equation cannot be solved in a single step. Estimates must be made for each coefficient, and some form of iterative convergence must follow.
Minimization of Least Squares¶
In TableCurve 3D, both linear and non-linear equations minimize the sum of squares of the residuals. A residual is simply the difference between the z value of a given x,y,z triplet and the z value computed from the surface-fit equation at this same x and y value.
A residual is thus the vertical z-distance between the surface and a data point. It can be either positive or negative in value. The square of a residual is always positive, and thus reflects the magnitude of the residual, although it does so in a second order rather than a linear fashion.
Least-squares minimization thus assumes that x and y are accurately determined, and that an error exists only in the dependent variable z, and that errors are normally distributed. It is this minimization of the sum of the squared residuals with this assumption of normally distributed errors in only the z-variable that makes it possible to fit linear equations in a single matrix solution.
Design Matrix¶
In a linear equation it is possible to construct a design matrix based upon the sums of the basis functions and their cross-products. Let us consider the simple equation for a plane:
By differentiating the expression for the sum of squared residuals for this simple equation, the following design matrix and constant vector is produced:
The weights wi are inverse variances or 1/s^2, where s is the standard deviation for a given data triplet. TableCurve 3D assumes wi‘s of 1.0 unless specific weights are entered.
The determination of a, b, and c requires no more than the computation of the eight sums and the solution of the three simultaneous equations, a very fast procedure compared to the iterative procedure required for non-linear equations.
Non-Linear Fitting¶
When an equation is non-linear, the least-squares procedure is similar. In this instance, however, it is not possible to express partial derivatives as a function of only the x or y basis functions. In a non-linear equation, the partial derivative with respect to one coefficient will include one or more of the other coefficients, making a single step matrix solution for the individual coefficients impossible.
As such, non-linear fitting consists of an iterative procedure that begins with an initial set of estimates for the parameters. Although there are a variety of methods to converge to the minimum least-squares solution, all procedures must compute a point by point sum of squared residuals for each iteration’s set of coefficients. This is especially time consuming with large data sets.
TableCurve 3D uses the Levenburg-Marquardt algorithm for fitting its non-linear equations and user-defined functions. Although this algorithm requires a matrix inversion and the computation of partial derivatives for each iteration, its rate of convergence is among the best of available methods.
Global vs. Local Minimum¶
Unlike linear fitting, non-linear fitting does not guarantee the minimum least-squares solution. Non-linear fitting algorithms sometimes find a local minimum in the n-dimensional space of the fit rather than the true global minimum which represents the desired least-squares solution. Good starting estimates are thus essential. TableCurve 3D determines effective starting estimates for the parameters in all of its built-in non-linear equations during its pre-scan procedure of the input data. For UDF’s, TableCurve 3D offers the means to graphically adjust UDF estimates prior to fitting. Accurate starting estimates insure convergence to this global minimum.
No Exact Solution¶
An exact least-squares solution on a digital computer would involve minimizing the sum of squared residuals to the full floating point precision of the machine. For Intel and compatible coprocessors, this would mean to 19 digits of precision.
A non-linear fit is sometimes referenced as asymptotic, meaning it produces a coefficient vector that only approaches the limit of exactly minimizing the sum of squared residuals. This is because you iterate to a specified tolerance or fractional error in the minimization. This tolerance is always less than the floating point precision of your computer.
TableCurve 3D’s default non-linear fractional convergence is 1e-6, but can be set anywhere from 1e-3 to 1e-15. The 1e-6 value means that the r² goodness of fit must be unchanging through six significant figures for five iterations before the algorithm signals convergence.
The one-step linear minimization is likewise likely to produce less than the 1e-19 floating point granularity of the 80x87, especially for higher term count equations. For example, consider the following polynomial:
The design matrix for this equation will contain elements that vary widely in magnitude. For example, the weighted n might be 100 whereas the weighted sum of x^10 might be 1e30. The problem arises due to the limitations of finite floating point in matrix operations where the matrix is close to singular.
A nearly singular matrix has a determinant that is nearly zero. In such cases it is difficult for conventional matrix solution methods to produce an accurate least-squares minimization. The solution to this problem is TableCurve 3D’s Auto-SVD algorithm.