Classes (extension) |

RootFinder : ObjectExtension

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`.

Examples

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