RootFinder:
Filter:
Classes (extension) | Math | Libraries > MathLib > Solvers

RootFinder : Object
ExtensionExtension

a multi-dimensional root finder

Description

A multi-dimensional root finder based on the Levenberg-Marquardt optimization algorithm1 . 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 method2 .

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

RootFinder.findRoot(func, jacobian, x0, param, opts)

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.

Inherited class methods

Instance Methods

Inherited instance methods

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: /home/stefan/.local/share/SuperCollider/downloaded-quarks/MathLib/HelpSource/Classes/RootFinder.schelp
link::Classes/RootFinder::