SOLVESYS 4.02

Simultaneous Nonlinear Equations and Least Squares Solver 
for the HP48G series

Copyright 1994-1998, Sune Bredahl

 

HTML documentation v. 1.03

Disclaimers and Legal Issues
Version 4.0 Release Notes
Version 4.01 Addendum
Version 4.02 Addendum


What is SOLVESYS?
Installation
Examples
Modifying Error Tolerances
Termination Messages


How to Contact the Author

 

DISCLAIMERS AND LEGAL ISSUES

SOLVESYS.LIB AND THIS MANUAL ARE PRESENTED WITHOUT WARRANTIES, EXPRESSED OR IMPLIED. THE AUTHOR MAKES NO GUARANTEE AS TO THE FITNESS OF THIS SOFTWARE. SOLVESYS.LIB CAN BE COPIED FREELY PROVIDED THIS MANUAL IS DISTRIBUTED WITH IT. SOLVESYS.LIB MAY NOT BE USED FOR COMMERCIAL PURPOSES WITHOUT PERMISSION FROM THE AUTHOR.
 

VERSION 4.0 RELEASE NOTES

The present library is a completely rewritten version of SOLVESYS. Since most of the interface has changed, I suggest you read the entire manual even if you're familiar with previous versions of the program.

SOLVESYS 4.0 includes support for nonlinear least squares problems (overdetermined systems). The major application of this is datafitting, but SOLVESYS is not limited to this case. Underdetermined systems are now treated as an error to avoid "false" solutions (e.g. due to an unassigned constant)

Two main features known from v3.1 and earlier releases have been removed; analytic derivatives (just wasn't worth it compared to the speed of numeric derivatives) and ranges for variables (too much overhead for little gain). Also there's no "complex number" switch in v4.0, but complex valued results are allowed if complex numbers are also given as start guesses.

Two new error tolerances are available, one for the least squares case (cosine test) and a tolerance for the convergence of the iterate values. The latter applies to both zero finding and least squares.

SOLVESYS 4.0 does not include a stack version of the solver. If you need this feature, you must stick to version 3.1.

 

VERSION 4.01 ADDENDUM

SOLVESYS 4.01 (released January 11, 1998) fixes a bug in the v4.0 library:

Using the solver after "Too many unknowns" error will in certain situations generate random errors or even cause a memory clear! More precisely, the bug occurs if trying to solve a system with at least one constant defined but still more unknowns than equations. This correctly produces a "Too many unknowns" error but when trying to solve the system again with altered variable definitions, SOLVESYS returns some error or what is worse. Thanks to Carlos Hartwich for reporting the bug.

Furthermore a change to the converge tests used by the solver has been implemented. This should fix some potential convergence problems for linear least-squares. This change causes the LSQ value in the INFO box not to be updated/computed until XTOL has been satisfied.

 

VERSION 4.02 ADDENDUM

SOLVESYS 4.02 (released August 12, 1998) includes a minor modification that fixes some problems primarily related to linear equations.

The solver now terminates with a "Zero" message if an equation set evaluates exactly to zero regardless of the XTOL tolerance. This prevents the solver from stalling if the equations are solved (with no error) in the first iteration without the user having to change the XTOL setting. This situation will usually occur only when solving linear equations, but could also happen for certain nonlinear equations.

 

INSTALLATION

To install SOLVESYS on your HP48G/GX:

  1. Transfer SOLVESYS.LIB to the HP48G/GX.
  2. Recall the library to the stack and press n [STO], where n is the desired RAM port (0 if you have a HP48G). After storing the library, you can purge the original copy to save memory.
  3. Turn the HP48 off, then on. This adds SOLVESYS to your library menu.

The checksum for SOLVESYS.LIB (version 4.02 in the ABOUT box) is # D743h, size 3996 bytes.

To check that SOLVESYS has been correctly installed, press [right-shift]+[2] to enter the library menu, choose the [SOLVESYS] menukey and you should see the[SOLVESYS][FITEQ][ABOUT]labels.

To remove SOLVESYS.LIB:

  1. Put the library ID (n: 1550) in the stack
  2. Execute the sequence: [DUP][DETACH][PURGE]

If the HP48 gives an "Object in use" error at this point, press [ON]+[C] and repeat the above steps.

To transfer SOLVESYS.LIB to another HP48G/GX:

  1. Put the library ID (n: 1550) in the stack and press [RCL].
  2. Store the returned library in any variable
  3. Transfer this variable to the other HP48 - use binary transfer.

 

WHAT IS SOLVESYS?

SOLVESYS is graphical environment for solving systems of nonlinear equations and nonlinear least squares problems. The library works exclusively on the HP48G series and is approx. 4 kb in size. 

SOLVESYS is designed to either zero or least-squares minimize sets of m linear or nonlinear equations in n unknowns.When m=n, the problem is obviously to find a solution satisfying all equations. If m>n, the equations are generally inconsistent so instead SOLVESYS searches for a least squares solution, i.e. the minimizer of the sum of squared equation deviations. Least squares minimization is primarly used in datafitting applications but SOLVESYS is not limited to this case. The case n>m is subject to error.

Nonlinear equations must be solved iteratively, i.e. the user must provide an initial guess which the solver (hopefully) uses to find the true soluton. It can be necessary to try out different starting guesses before the solver succeeds in this quest, but if qualified starting values are provided the system can often be solved with only a few iterations.

The solver engine based on a globally convergent modification of the multidimensional Newton-Raphson method found in Dennis and Schnabel [1] and is also well described in Press et al. [2]. For least-squares problems, this extends to a damped Gauss-Newton method.

[1] Dennis, J.E., and Schnabel, R.B. 1983, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Englewood Cliffs, NJ: Prentice-Hall).
[2] Press, W.H. et al. 1992, Numerical Recipes in C: The Art of Scientific Computing. 2nd ed. (Cambridge: University Press).

 

EXAMPLES

There are two ways to input equations to SOLVESYS.  Either store the equation list in the 'EQ' variable prior to starting SOLVESYS or enter the equations manually in the SOLVESYS equation editor (see below).

As an example, consider the following equations;

R=n+n2+ikcos(n+ik)-k2
T=n+iksin2(n+ik)-cos(n+ik)

These equations should be solved for the complex valued variables (n,k) for given values of (R,T). In this example, we will use R=10 and T=3.

As mentioned, you can either store these to equation in the 'EQ' list before you start SOLVESYS or you can enter them manually in the SOLVESYS equation editor. The list would look like

{ 'R=N*(N+1)+K*(i*COS(N+i*K)-K)'  'T=N+i*K*SQ(SIN(N+i*K))-COS(N+i*K)' }

Whichever way you prefer, the equation editor display should look like this:

When you press [OK] SOLVESYS analyzes the equations for variables and displays the Current Values dialog box where guesses of the unknown variables must be provided. The dialog box should be filled out according to the following rules;

Following these rules, we'll enter (1,1) for both n and k. The T=3 and R=10 values are entered in square brackets. The display should then look like this;.

Press [SOLVE]and after a few iterations, a solution (Zero) is found;

Press [INFO]to get more information about this result;

The values should be correct to 4 significant digits (see the Error Tolerance section) so we'll take k=0.506+2.379i and n=2.357+0.310i as our solution.

You can copy the current values to the stack using the [->STK] menukey. To quit, first press [ON] to return to the equation editor and press [ON] again to exit.

 

NONLINEAR LEAST SQUARES MINIMIZATION

Least-squares minimization performs the task of finding a "best fit" solution (in the least squares sense) of a set of inconsistent equations. Normally you'll have more equations than variables causing the inconsistency. 

The most common application of nonlinear least-squares is curvefitting where one is attempting to fit m observations to an expression of n unknown parameters for which the "best-fit" values are required. If each observation is inserted in the expression, the result is a system of m "observational" equations in n unknowns. The library utility FITEQ can be used to create this equation set. An example follows.

The relationship between the measured pressure and temperature in saturated steam can be written as

Y=aALOG[bT/(c+T)]+eY

where Y is the measured pressure of the steam at various values of a controllable temperature T
a, b and c are unknown parameters (to be estimated)
eY is a normally distributed measurement error (of Y) with mean zero and variance v.

The following data were collected.  

T: 0 10 20 30 40 50 60 70 80 85 90 95 100 105
Y: 4.14 8.52 16.31 32.18 64.62 98.76 151.13 224.74 341.35 423.36 522.78 674.32 782.04 920.01

Half the job is to obtain some guesses of the parameters to solve for. In this example, the T=0 value in the first measurement causes a=4.14 in the equation so we can use this as a starting value. Furthermore by inserting a=4.14 in the next two "observational" equations we have;

8.52=4.14*ALOG[10b/(c+10)]
16.31=4.14*ALOG[(20b/(c+20)]

Taking LOG on both sides of both equations and multiplying with (b+10) and (c+20) respectively gives;

(c+10)*LOG(8.52)=LOG(4.14)*(c+10)+10b
(c+20)*LOG(16.31)=LOG(4.14)*(c+20)+20b

which are just two linear equations with the solution (b,c)=(5.93,179). Thus an initial guess such as (a,b,c)=(4,6,180) seems reasonable.

Now we're ready to solve the real problem. The utility FITEQ is used to create the 14 equations needed. First store the data as vectors (or lists) in global variables such as 'T' and 'Y' in the current directory. Then apply FITEQ with the arguments;

3: 'Y(k)=A*ALOG(B*T(k)/(C+T(k)))'
2: 'k'
1: 14

where the level 2 variable is the data index used in the level 3 expression and level 1 is the number of observations. Make sure the variables { A B C } do not exist in the current or parent directories.

After applying FITEQ, start SOLVESYS and the equation set editor appears. The equations are already created so just press [OK] and fill in the initial guesses (a,b,c)=(4,6,180).

Press [SOLVE] and after a few iterations, the solver has found a minimizer;

You can press [INFO] to get additional information about the current result (see below for a description of these diagnostics);

This tells us that the values should be correct to almost 5 significant digits but we can do with less. If we use (a,b,c)=(5.27, 8.56, 295) then the best fit function is Y(T)=5.27*ALOG[8.56*T/(295+T)].

Since the RMS error of the equations is 41.45, the error sum of squares (SSE) is 41.452=1718. The estimated variance v of the measurement error eY is SSE/(m-n)=1718/11=156.2.

Be aware that there are no simple ways to distinguish  between a local or global minimum. This means that the choice of starting values is very crucial. With poor values, the solver could just as well converge towards any of the local minima listed below (and there are even more!):

(a,b,c)=(4.14,-168,1), eq=1603
(a,b,c)=(4.14,infinity,-infinity), eq=1603
(a,b,c)=(305,infinity,0), eq=1127
(a,b,c)=(0,infinity,infinity), eq=1083

A good initial guess is not only a real time-saver, it will also pick out the right (global) minimum for you!

WEIGHTED LEAST SQUARES

Often it is desired to use different weights for observations used in datafitting, eg. when the observations have unequal variance. To compute a weighted fit, divide the equations (eg. the EQ list produced by FITEQ) with a list standard-deviations (squareroot of variance) of the corresponding observations and use SOLVESYS on the new list.

 

ERROR TOLERANCES

For nonlinear problems, a two-level convergence test is applied. First, convergence for the iterates is tested, and if passed, the result is verified by a second level test specific to the problem type. The first-level test is generally applicable to nonlinear problems only and is ignored under certain circumstances (see below).

It's possible to modify the tolerances used for these tests although you should not meddle too much with the default values. In the Current Values dialog box, press the [TOL] menukey to open the Tolerance dialog box;

XTOL:
First level test. Tolerance for the relative change in the iterate values. A value of 10-p basically corresponds to p significant digits of the computed result, but values of XTOL below 10-6 should not be trusted to comply with this. The default value is 10-3 corresponding to 3 significant digits.       
EQTOL:
Second level test. Tolerance for the RMS (root mean square) error of the equations used for zero finding. E.g. with {xy=9,x+y=6} the RMS error at (x,y)=(2.9,3.1) is [(8,99-9)2+(6-6)2]½= 0.01. EQTOL defaults to 10-5 which should be sufficient for most purposes. In case the RMS error is exactly zero, the solver assumes that a solution has been found and terminates with a "Zero" message regardless of the XTOL test above.
LSQTOL:
Second level test. Tolerance for cosine test (Dennis & Schnabel) used for least squares problems. The test returns values between 0 and 1 where a value close to 0 indicates a least squares minimizer. The test is rather strict and will usually be close to 1 even near a minimum so I suggest using 0.1>LSQTOL>0.001 and not lower. The default value is 0.01. LSQTOL does not apply to zero-residual least squares problems so EQTOL is used in this case.

You can view the actual test values by pressing the [INFO] menukey in the Current Values dialog box.

 

TERMINATION MESSAGES

Some (more or less) common error and termination messages returned by SOLVESYS are listed below.

RETURN MESSAGES FROM THE SOLVER:

Zero:
A result satisfying XTOL and EQTOL was found (or only EQTOL if the error is exactly zero).
Minimum:
A result satisfying XTOL and LSQTOL  was found. It is not guaranteed to be a global minimum if several mimima exists.
Bad Guess(es):
This happens if the initial values provided are too far away from any solution. Typically this means convergence to a local minimizer of the sum of squared equation deviations.
Non-Real Result:
A complex valued result occurred although no complex initial values were provided by the user (indicating a complex result to be valid). This is caused by a variable moving into a region where some equation or its derivative do not evaluate to a real number. Either, better initial values must be provided or in simpler cases the equations may be manipulated to avoid complex domain functions and/or derivatives. Alternatively, it may help to provide complex valued guesses with zero imaginary parts (to allow iterations in the complex domain) although this will slow down the solver noticeably. Be aware that the HP48 power function (^) often is the culprit of these errors since it returns complex results for negative arguments raised to a non-integer power. For example, the expression '(-1)^(1/3)' evaluates to a complex result instead of -1. You can fix this by replacing 'X^(a/b)' with 'XROOT(b,X^a)'.
Undefined Result:
(Math exception.) Calculation such as 0/0 occurred or the XROOT function was used with arguments that cannot give a real-valued result. Check the current solution or try with other starting guesses.
Infinite Result:
(Math exception.) Calculation such as 1/0 occurred. Check the current solution or try with other starting guesses.

INITIALIZATION ERRORS:

All Variables Known:
All variables were defined as constants (i.e. placed in square brackets).
Too Many Unknowns:
The number of unknowns is greater than the number of equations. Although the solver in principle can handle this situation too, a solution to such a system is unlikely to be of any interest.
Constant?:
At least one equation does not contain any unknowns. SOLVESYS does not allow redundant equations.
Inconsistent Units:
Units are not supported.  SOLVESYS automatically strips off units for the CONST() function.

FITEQ ERRORS:

Invalid User Function:
A referenced data variable (such as 'T' in the example above) does not contain a list or vector of data values.
Bad Argument Value:
The number of observations argument passed to FITEQ is greater than the number of observations present in at least one of the data vectors or lists.

 

HOW TO CONTACT THE AUTHOR

Feel free to e-mail me if you have any comments, questions, problems or suggestions. Also if you find any bugs (or what you think is a bug), please notify me.

Hope you like the program,

Sune Bredahl

sune_bredahl@hotmail.com or
c947086@student.dtu.dk

The latest version of SOLVESYS including and other information regarding the program are available from: www.student.dtu.dk/~c947086/hp48.html