Hands-On Math

Last Revision March, 2011

Last Revision March, 2011

Data and Curve Fitting, Approximation, and Optimization are mathematical procedures.
They all employ numerical representations of: an **Initial
State**, **Objectives**
to be achieved, **Controllables**
that can be adjusted to reduce error, a **
Current State **or result** **that can be compared
with the objectives to produce a **Current Error,** and a **Strategy**
or strategies to find successive values for the controllables that reduce error.

**Maximization and Minimization Procedures** also employ numerical
representations of Initial State, Controllables, Current State and Strategy but
differ in that the Objective(s), and hence the Error(s), is(are) not usually defined by
fixed numerical values.

Sometimes a tentative numerical objective is provided as a large or small value that can be compared with a Current State to produce, over some iterations, a least achievable numerical Error. Although Excel's Solver is equipped to find Max, Min and Equals as objectives, the tentative objective technique can be illustrated with a simple example, the minimum of (1+sinx/x). A graph of this function and the value of its minimum are shown next:

As Excel cannot readily find values for this function at x = 0, provide Solver with a constraint such as x > = 0.0000001.

Now provide Solver with the tentative objective of setting the value of the function to, for example, -1,000,000,000.

Set x to an initial value of 1.0 and start Solver. Solver will complain that it was unable to reach a feasible solution. Notwithstanding the complaint it will have found a somewhat inaccurate value for x quite close to the value for the location of the actual minimum, for example, 4.49330.

The user may now choose an objective only slightly smaller than the minimum, e.g. 0.782 and Solver finds the value for x as 4.4934341 i.e. in agreement with the value it would find if set up to locate a minimum rather than being set up to meet an objective.

Gauss is credited with being first, in 1795 at age 18, to find the "Linear Least Squares" method that he used for fitting observations that contain observational errors. Linear implies that the parameters of a model are linearly combined. When this is so, a closed form of solution can be found, not necessarily, but often in the form of polynomial coefficients. When the application is non-linear, iterative procedures are employed.

Ceres, a new asteroid, was discovered on January 1, 1801 and tracked for 40 days at which time it was lost in the Sun's glare. At the age of 24, Gauss employed Linear Least Squares to estimate and project the orbit of Ceres so that it could be located when it emerged from behind the Sun.

In 1829, Gauss was able to show that a least-square estimator was the best linear unbiased estimator of the polynomial coefficients when the measurements being fitted had uncorrelated, equal variance, zero-mean errors - all properties that might be expected of careful human measurements. This is the reason that the Least Squares representation of error is used when observational data is to be fitted with a curve. Least Squares minimization can also be thought of as a neat way of smoothing data that has a large error component

There are cases where the curve to be fitted is not the result of noisy physical measurements that require smoothing and instead is the result of labour-intensive calculation.

What is then desired is a more simple expression for a range of the calculated curve. In this case the objective is to find a new curve that is less complex to calculate and which, although not an exact fit, is satisfactory in some sense.

This is a case where the data to be fitted is regarded as exact and, for the sake of reduced calculation effort, we are willing to accept a less precise representation.

As an example, the A and B coefficients of the function Y = A * X + B / X
are now chosen, using Solver, to fit the calculated function Y = X ^ 0.5 which
has been calculated at 201 points from X = 0.25 to X = 2.25.
*(The fitting function has been chosen rather arbitrarily only to show the
effect of using two alternatives to Least Squares.) *

Name the 201 values of calculated Y, C1 through C201. Name the corresponding 201 values that will be found for function Y, F1 through F201. Postulate errors, E1 through E201, which can be found for each point by comparing the corresponding Ci and Fi values. There are many possible ways of forming the Ei values.

Least Squares would set Ei = (Ci-Fi)^2 and Solver would be used to choose A and B so as to minimize the sum of the 201 Ei values.

Sometimes it is of interest to chose Ei as Abs(Ci-Fi) so as to minimize Absolute Error rather than squared error.

At other times it is Relative Error that is important. We would might use either Ei = abs( Fi / Ci - 1) or Ei = ( Fi / Ci - 1) ^2.

In addition to such choices, some users would prefer to minimize the greatest of the Ei rather than their sum, MiniMax. Perhaps there are other users who would prefer to make the two largest errors as equal and as small as possible. Who knows?

To illustrate the effects that can occur with choice of the error criterion, Solver was employed to fit the list of square roots using MiniMax for both the Absolute Error criterion and the Relative Error criterion as seen next:

For the Minimum Absolute Error fit, blue, the maximum error is seen to occur at both the largest and smallest X values. This results in a comparatively high relative error for X near 0.25.

For the Minimum Relative Error fit, red, the maximum error is seen to occur at the largest X value.

Which of these two fits would you prefer?

When the object is solely a close fit, greatest interest may be on using the criterion and other strategy that would provide a satisfactory fit with the least expenditure of calculation time. That is a subject outside of the scope of Hands-On Math.

Note in the foregoing example of curve fitting that it was incidental that the fitting expression interpolated the 201-point list. There can be occasions when the interpolation aspect of curve fitting is the primary objective although the fit remains important.

Curve fitting can be described as having the objective of fitting a curve with minimum error. However there are times when the objective is not a curve but is instead a combination of disparate items such as fuel efficiency, dollar cost and size and the objective is to minimize a weighted combination of such items.

If the objective were to maximize the ratio of size to dollar cost for a given fuel efficiency we would think of the problem as one where the optimum was found when that ratio was largest.

Methods for minimization and maximization differ little. A large quantity becomes small when; instead, its inverse is the objective.

The term Optimization is most often employed when the objective combines disparate items whether or not the application is one of maximization or minimization.

**Optimization**

When the objective function is a weighted sum of disparate items, such as are found in modeling a projectile aiming at a target. Example items are: the time that a position is reached, the angle of approach at that time and the velocity at that time. The controllables may also be disparate such as Charge, Elevation, and Azimuth.

If the projectile were a grenade aiming at a moving target then the time and angle of approach might be given most weight. If it were a shell aiming at a stationary target then velocity and angle of approach might be weighted most.

**
When the controllables are disparate.** The sensitivities of the weighted objective to the
controllables will be disparate and must be separately weighted in adjusting the
controllables. Otherwise one or more of the sensitivities could be too small to
affect the optimization or so large as to weaken or destroy convergence.
This situation can be looked after by the user intervening initially to set the
weights and from time to time intervening to adjust the weights. In come cases
means can be found to automatically adapt the sensitivity weights as iteration progresses.

Just as numerical integration resides at the core of the numerical solution of differential equations, numerical differentiation to determine sensitivities is the core procedure of numerical optimization. The methods to be employed could be absolute or relative, e.g., a controllable could be changed by a small constant amount such as 0.0001 or by 0.01%, the former being a concern when the value of the controllable is both very large such as 1,000,000,000,000 and very small such as 0.000,000,000,001, the latter creating concerns when the value of the controllable is at or near zero.

There are two-point, three-point and even five-point differentiation methods. There is Differential Quadrature, which uses weighted sums of function values. There are methods based on Splines, methods based on Taylor series, and other methods can be devised or found.

This writer tends to favour the use of forms of relative error in situations where the controllable does not take on the value of zero and the computer being used is efficient at division.

Sets of linear and non-linear equations or a mixture of both may be solved iteratively with an optimization routine such as Solver.

This ability to solve can be looked upon more broadly as an ability to estimate or infer the cause of an observed effect.

Could observation of the tides, at a position on the Earth, and over a period of months become a basis for any inferences about our Moon, its orbit or about properties of Earth?

Top | Prev. Topic | Topics |