RootFinder | SuperCollider 3.13.0 Help

Description

A multi-dimensional root finder based on the Levenberg-Marquardt optimization algorithm¹ . The LM algorithm is an iterative technique that finds a local minimum of a function that is expressed as the sum of squares of nonlinear functions. It has become a standard technique for nonlinear least-squares problems and can be thought of as a combination of steepest descent and the Gauss-Newton method. When the current solution is far from the correct one, the algorithm behaves like a steepest descent method: slow, but guaranteed to converge. When the current solution is close to the correct solution, it becomes a Gauss-Newton method² .

Part of MathLib, a diverse library of mathematical functions.

NOTE: RootFinder requires the user to provide an analytic Jacobian (or the single analytic derivative in the case of one function and one independent variable) in order to work. See the examples below.

Class Methods

.findRoot

Find a shared root of N real-valued functions each containing M independent variables.

Arguments:

func	An (array of) instance(s) of AbstractFunction, where each instance returns a single scalar value of type SimpleNumber. These are the functions `F_n(x)` to be minimized.
jacobian	An (array of) instance(s) of AbstractFunction, where each instance returns a single scalar value of type SimpleNumber. This is the Jacobian: a matrix of all first-order partial derivatives of a scalar-valued function `F(x)` with respect to the coordinate vector `x = [x_1, x_2, ... , x_{M - 1}, x_M]`.
x0	An (array of) instance(s) of SimpleNumber. This denotes the initial guess `x_0 = [x_{0, 1}, x_{0, 2}, ... , x_{0, M - 1}, x_{0, M}]` for the location of the root.
param	An optional Collection or single instance of SimpleNumber. This may be used for supplying any additional function parameters.
opts	An instance of Array holding 4 optional parameters which are used in the stopping criteria of the algorithm. The first parameter `tau` is a number between `1 * 10^{-8}` and `1`. Smaller values apply if it is assumed that `x_0` is already close to `x_r`. The second parameter `epsilon_1` is used in the stoping criterion `\|F'(x)\| <= epsilon_1`, the third parameter `epsilon_2` is used in the stopping criterion `\|h\| <= epsilon_2 \|x\|`, and the fourth parameter `k_max` denotes the maximum nr. of iterations so that the algorithm stops as soon as the iteration count `k` satisfies the condition `k >= k_max`.

Returns:

An Array holding the location x_r of the shared root.

Discussion:

First example: solving a system of two equations in two unknowns

2x_1 - x_2 - e^{-x_1} = 0
-x_1 + 2x_2 - e^{-x_2} = 0

with initial guess x_0 = [-5, -5].

Second example: finding a root of one equation in one unknown

2x-e^{-x} = 0

with initial guess x_0 = 0.

Examples

[1] - The SC code is based on the MATLAB implementation of the algorithm found at http://www2.imm.dtu.dk/~hbn/Software/

[2] - http://www.ics.forth.gr/~lourakis/levmar/

helpfile source: HelpSource/Classes/RootFinder.schelp
link::MathLib/Classes/RootFinder::

RootFinderExtension