SOLVESYS 3.1 SIMULTANEOUS NON-LINEAR EQUATIONS SOLVER for the HP48G Series Calculators Copyright 1996, Sune Bredahl, All Rights Reserved [ Check out http://www.gbar.dtu.dk/~c947086/hp48.html for a nicely formatted HTML version of this document ] --------------------------------------------------------------------------- Disclaimers SOLVESYS.LIB, STKSOLVE.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 AND STKSOLVE.LIB CAN BE COPIED FREELY PROVIDED THIS MANUAL IS DISTRIBUTED WITH THEM. SOLVESYS.LIB AND STKSOLVE.LIB MAY NOT BE USED FOR COMMERCIAL PURPOSES WITHOUT WRITTEN PERMISSION FROM THE AUTHOR. --------------------------------------------------------------------------- Release Notes A bunch of changes have been done since v3.0a, most of them related to the functionality of the The START VALUES Dialog Box. The solver is faster than in previous versions, especially when numeric derivatives are used. If there are less than six variables, SOLVESYS will monitor the variable progress in real-time. Users of earlier versions should note that the "Linear" derivatives model is no longer available in v3.1. Instead, "Numeric" derivatives can be used without any loss of performance. I do not support the S/SX version of the STKSOLVE library no more (don't have the time - don't have any S/SX) - HP48S/SX users must use the library distributed with SOLVESYS v3.0a. --------------------------------------------------------------------------- What is SOLVESYS? SOLVESYS is an easy-to-use environment for solving systems of nonlinear equations. Unlike MES (the built-in Multiple Equations Solver) which only works with systems that can be solved by recursive use of a one-dimensional solver, SOLVESYS is a true multi-dimensional solver. SOLVESYS allows on-the-fly definitions of constants and variables and can also solve systems with more equations than variables and vice-versa. Also linear systems are solved very fast. A programmable (stack-mode) version of the solver is available via the library command STKSOLVE. The program is far from perfect, but you'll hardly find any HP48 equation system solver more advanced and user-friendly than this. SOLVESYS uses unsupported and undocumented features of the HP48, so use it at your own risk. SOLVESYS.LIB works exclusively on the HP48G/GX models. (Earlier releases of this program were called SIMN, the last version being SIMN 5.2. The next release was called SOLVESYS 1.0.) --------------------------------------------------------------------------- Installation To install SOLVESYS.LIB: 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 is # 9973h, size: 3974.5 bytes. To remove SOLVESYS.LIB: 1. Put the library ID (n: 1550) in the stack 2. Press: [DUP][DETACH][PURGE] If the calc. returns an "Object in use" error at this point, then 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 calc. - use binary transfer. --------------------------------------------------------------------------- Solving Principles The solver is based on a globally convergent modification of the multi-dimensional Newton-Raphson method. The original source for this is Dennis and Schnabel [1] and is also well described (including C-source) in Press et al. [2]. SOLVESYS extends this to a least-squares model in cases where the number of equations is different from the number of variables. One pitfall is that the method may converge to a non-solution. It minimizes a 'transform' function having minima where the system has solutions but may also have minima that are not solutions to the system, hence the problem. The method is not based on minimization alone. It's a Newton method adjusted according to a minimization principle when it diverges. When it does fine, it behaves like a general 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. 1988, "Numerical Recipes in C: The Art of Scientific Computing" (Cambridge: University Press). --------------------------------------------------------------------------- The SOLVESYS Dialog Box This dialog box appears when starting the program. Most of the default settings here will usually suffice: SYSTEM { EQ1 EQ2 ... }: This is the list of equations to be solved. You can enter the list directly here or store it in 'EQ' prior to starting SOLVESYS. Equations don't have to be arranged in any particular way, eg. 'Y*X+9=X','Y*X+9-X=0' and 'Y*X+9-X' are all equal expressions. There is no limit as to the number of equations in this list, also the number of variables can be different from the number of equations. TOL: The error tolerance. No solution is returned until all equations have 'function' values less than this value. A low(er) tolerance implies a high(er) accuracy of the solution. The default value is 0.00001 and this should be fine for most purposes. DER: The solver uses partial derivatives of the equations and can use either analytic or numeric derivatives. You can change the setting using [CHOOSE] or the [+/-] key. "Analytic" derivatives must first be computed by symbolic differentiation before the solver can start, whereas "Numeric" derivatives are computed dynamically in each iteration. This allows the solver to start immediately at the expense of a slightly slower iteration speed, but the total time needed is usually less than "Analytic". Furthermore, "Numeric" handles user-defined functions and certain HP48 functions without built-in derivatives (such as XROOT() or SIGN()) and is also ideal for systems of linear equations. Note however, that "Analytic" is more numerically stable than "Numeric" and can handle certain systems which "Numeric" fails to solve. COMPLEX Checking this field enables SOLVESYS to search for complex roots. Since that's generally not what you want, just leave it unchecked. This setting is not required for input of complex constants (for a possible application of complex constants, see Example). --------------------------------------------------------------------------- The START VALUES Dialog Box After the equations have been entered in The SOLVESYS Dialog Box, the equations are analyzed for variables and constants and the result displayed in the START VALUES dialog box. A maximum of 12 variables/constants will be displayed at a time, so more screens are sometimes necessary. Three types of 'start values' are accepted: Guess This is what any numerical solver needs - an initial value, guess or seed (whatever you prefer to call it), ie. something to guide the solver to the root you want. A guess value is entered as a real or complex number in the corresponding variable field. Depending on the setting of COMPLEX, a complex number defines either a complex guess-value (if checked) or a real-valued range (see below). SOLVESYS will use '1' as default for all variables but clearly this should be changed according to any knowledge about the solution. For systems of linear equations, the default values are sufficient. Range A range can be used instead of a real-valued guess value. A range is defined by a complex number, for example (-2,2) forces the solver to search for real-valued roots in the interval -2 to 2 for the variable in question. You should only use ranges if you're 100% sure that it actually encloses a root. Note that if interrupting the solver to input other guess values, range definitions (if any) will be lost and must be entered again if needed. Constant Constants are defined by placing the value in a single-element vector, like [0.25], in the corresponding field. Storing the value in the variable prior to starting SOLVESYS has the same effect (both the current and the HOME directory are searched). Constant values are always stored in HOME. Using complex constants do not require COMPLEX to be checked. Pressing the [SOLVE] menukey activates the solver. The total number of equations, variables and constants defined is displayed briefly. If there are less than six variables, the solving progress for each variable displayed in real-time as well as the current error. For more variables, only the error is displayed. If the solver is terminated (because a solution is found or due to a user-interrupt or some other error), the user is returned to this dialog box again. The current values of the variables can now be inspected and the system can be resolved with other guesses if needed (constant definitions are not possible at this point). Pressing the [INFO] button shows the current error, elapsed time and the number of iterations used for the session just finished. --------------------------------------------------------------------------- Example A well known problem is to find the radius r and center (a,b) of a circle given three points on the circle. The three points must then satisfy (x - a)2 + (x - b)2 = r2. The following list of equations can be used to solve this: { 'SQ(RE(P1)-A)+SQ(IM(P1)-B)=SQ(R)' 'SQ(RE(P2)-A)+SQ(IM(P2)-B)=SQ(R)' 'SQ(RE(P3)-A)+SQ(IM(P3)-B)=SQ(R)' } These equations refer to the three complex constants P1, P2 and P3 (rather than six real-valued constants). When entering these values later, you'll see that it's much easier to input coordinate sets as complex numbers rather than dealing with the y and x coordinates individually. (Obviously, you could place the constant values directly in the equations, but then you wouldn't be able to re-use the equations to solve for other constant values.) The three known points in this example are P1=(3,5), P2=(4,1) and P3=(2,3). To solve this, store this list of equations in the 'EQ' variable and start SOLVESYS. Accept the default settings in The SOLVESYS Dialog Box and press [INIT]. The START VALUES Dialog Box now appears. First, fill in the three complex constants in single element vectors ie. P1:[(3,5)], P2:[(4,1)] and P3:[(2,3)]. Now provide some guess values for the variables to solve for (A, B and R). A quick sketch of the three points on a paper, reveals that R must be somewhere in the range 1LIST 0.00001 0 1 STKSOLVE >> (size: 108,5 bytes, checksum #4C8Ch) Using a hidden library routine in solvesys.lib and some system calls, a list of variables and a list of guess values (all 1) are created. This is put together in a list, the error term 0.00001 is used, numeric derivatives are selected and the complex-results flag is enabled. --------------------------------------------------------------------------- Error Messages Some (more or less) common error messages returned by SOLVESYS are listed below. Bad Guess(es): a) Iterations converged but didn't provide any satisfying solution or b) too many iterations without progress. In either case, you should try again with other guesses or ranges. This error could also occur if the error tolerance is too low. Constant?: At least one equation did not respond to change(s) in variable value(s). This error will usually be due to incorrect constant/variable definitions. All Variables Known: All variables were assigned a constant value. Consult the The START VALUES Dialog Box section for proper variable/constant definitions. Undefined Name: This error will occur if "Analytic" derivatives are selected, but one or more of the current equations contain a function without (built-in) derivative, such as XROOT(), SIGN(), or a user-defined function. "Numeric" derivatives can be used instead or you can define your own derivatives (must be placed in HOME) for the function(s) in question. Undefined Result: Calculation such as 0/0 occurred - change guesses. Infinite Result: Calculation such as 1/0 occurred - change guesses. In general, avoid rational expressions if possible. Eg. X/(X-1)=Y+2 should be written as X=(Y+2)*(X-1). The latter form usually has much better convergence properties. Inconsistent Units: Units are not supported. Note that SOLVESYS automatically disables units for functions such as CONST(). --------------------------------------------------------------------------- How To Contact The Author Feel free to e-mail me if you have any comments, questions, probs., suggestions, etc. Also if you find any bugs (or what you think is a bug), please notify me. Hope you like the program, Sune Bredahl c947086@student.dtu.dk The latest version of SOLVESYS and any relevant information regarding the program are available from: www.gbar.dtu.dk/~c947086/hp48.html ---------------------------------------------------------------------------