manual:chapter3:solver

newRPL includes an implementation of the Nelder-Mead Simplex Algorithm, which is a generic search algorithm for multiple variables. The implementation provides a very flexible framework for the user to experiment with root searching for anything from a single linear equation to a system of multiple non-linear equations.

In order to find a root to multiple equations with multiple variables, newRPL implementation creates a surface with the sum of the squares of the residuals of all the equations provided by the user, and tries to find a minimum of that function. Ideally, the minimum will have zero residual for all variables and will therefore be a valid solution. In some cases the algorithm will converge to minimums where some equations might be satisfied and others don't, or they may all have a residual. The residuals are provided as part of the result of the algorithm and the user should ALWAYS look at the residuals to see if a true solution was found. It may happen sometimes that the algorithm converges to a local minimum and a better solution exists. This all depends on the initial guess provided by the user.

The Simplex method uses a “simplex” which is a shape defined by a series of “points” to investigate. It can be thought of as a drop of liquid that falls over the surface of the function being investigated. This simplex will change shape and slowly “roll down” towards points of minimal residual differences (hence this is an optimization/minimization algorithm rather than a root seeking algorithm). When the drop reaches a minimum point, the algorithm will provide with the values for all variables and the residual values of each equation.

In a similar way as other root-seeking methods need an initial guess, the Simplex method needs an initial “simplex”. However, a simplex is not a point but an initial “range” of values to explore for each variable. Note that the algorithm is not restricted to explore within that range, and the results may be outside of the specified range. The specified range is merely to define the size and shape of that initial “drop of liquid” that will be placed over the surface you are investigating. The larger the drop, the more broad is the area explored and the more chances of the drop finding a minimum point, but at the same time the user has less control over where that drop will roll (in case of systems with multiple minimum points). So the user has to experiment not only with an initial “guess” but with initial guessed ranges for all variables, and if a solution isn't found, perhaps try other ranges for some variables.

The solver is accessed through a single command MSOLVE which takes 4 arguments:

  • The equations
  • The variables to solve for
  • A lower limit of a range to explore for each variable
  • A higher limit of a range to explore for each variable
  • A real number indicating a tolerance to stop the algorithm. The number is the largest acceptable residual for each individual equation.

This command requires all its input arguments as lists, even if there's a single item, except the tolerance which is a real number.

Let's assume the user needs to find a root of '2*X+4=8'. The first step is to provide the list of equations, in this case just one: { '2*X+4=8' }. Then we need to provide a list of the variables to solve for, in this case only one { 'X' }. Now it's time to decide where the algorithm will begin exploring. Let's say our guess is that the root is between 0 and 10. First, we need to provide a list of the lower bounds for all variables, in this case it's just one { 0 }, and then a list of the upper bounds { 10 }. Finally, we need to provide a tolerance. Let's say 4 decimal figures are good, so we'll use 1E-4.

We are now ready to run the MSOLVE command. The stack looks now like this:

5:                { '2*X+4=8' }
4:                      { 'X' }
3:                        { 0 }
2:                       { 10 }
1:                         1E-4

……………………………………………………………………………………
MSOLVE

Which will produce:

2:           { 1.999969482422 }
1:          { -0.000061035156 }

The first list returned in level 2 contains the value found for all variables, in this case X=2 was the exact solution. The list in level 1 has the residuals of all equations. The residual is defined as the difference between the left and right sides of the equation. Notice that the residual is within the requested tolerance. Requesting a tighter tolerance would produce a result for X closer to 2 but at the expense of longer running time to find the solution.

  • manual/chapter3/solver.txt
  • Last modified: 2021/09/24 09:56
  • by claudio