Voir la source de User Manual 4.13 Root-Finding Algorithms

__NOTOC__ 
== Introduction ==
=== Scope ===
This section is about the root-finding algorithms for univariate real functions provided by the library.
First we explain how to use the root-finding algorithms.
Then a focus is made on the following root finding methods: Brent, Newton, Bisection and Müller.

=== Javadoc ===
All solvers are in the following package :
[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/analysis/solver/package-summary.html fr.cnes.sirius.patrius.math.analysis.solver]

=== Links ===
None as of now.

=== Useful Documents ===
None as of now.

=== Package Overview ===
The package <code>fr.cnes.sirius.patrius.math.analysis.solvers</code> contains all the solvers described here.

== Features Description ==

=== About root finding ===
This library provides root-finding algorithms for real univariate functions.
The function for which a root is searched has to be provided as a [{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/analysis/UnivariateFunction.html UnivariateFunction].
The root-finding algorithm is implemented through the [{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/analysis/solver/UnivariateSolver.html UnivariateSolver] interface.

A very generic example would be :

<syntaxhighlight lang="java">
        UnivariateFunction f = <some function>;
        UnivariateSolver solver = <some solver>;
        int numberOfEvals = 100;    
        double startInterval = 5.;
        double endInterval = 10.;

        double root = solver.solve(numberOfEvals , f, startInterval , endInterval);
</syntaxhighlight>

This means the solver with look for a root value of f in the interval [5. , 10.], and will have to do so in no more than 100 evaluation steps.

==== Test functions ====

We will demonstrate the use of root-finding algorithms with two test input functions : a periodic function and a linear function. These functions are defined as follows :<br>
'''''sinus function''''' : SinFunction 

<syntaxhighlight lang="java">
public class SinFunction implements DifferentiableUnivariateFunction {

    public double value(double x) {
        return FastMath.sin(x);
    }

    public UnivariateFunction derivative() {
        return new UnivariateFunction() {
            public double value(double x) {
                return FastMath.cos(x);
            }
        };
    }
</syntaxhighlight>

'''''linear function''''' : XMinus5Function 

<syntaxhighlight lang="java">
public class XMinus5Function implements DifferentiableUnivariateFunction {

    public double value(double x) {
        return x- 5;
    }

    public UnivariateFunction derivative() {
        return new UnivariateFunction() {
            public double value(double x) {
                return 1.0;
            }
        };
    }
</syntaxhighlight>

==== Available solvers ====

The library provides around ten solvers, but the following have been more thoroughly tested :
* BrentSolver
* NewtonSolver
* BisectionSolver
* MullerSolver

=== Brent method ===
The'''''Brent's method''''' is a root-finding algorithm combining the bisection method, the secant method and inverse quadratic interpolation. It has the reliability of bisection but it can be as quick as some of the less reliable methods. The idea is to use the secant method or inverse quadratic interpolation if possible, because they converge faster, but to fall back to the more robust bisection method if necessary.

<syntaxhighlight lang="java">
        UnivariateFunction f = new SinFunction ();
        double r;
        UnivariateSolver solver = new BrentSolver();

        r = solver.solve(100, f, 3, 4);
</syntaxhighlight>

Result : r = PI

<syntaxhighlight lang="java">
        UnivariateFunction f = new XMinus5Function ();
        double r;
        UnivariateSolver solver = new BrentSolver();

        r = solver.solve(100, f, 1, 2);
</syntaxhighlight>

Result : NoBracketingException exception


'''''<u>behavior deteriorated in case of several roots in the interval</u>'''''<u> :</u>

<syntaxhighlight lang="java">
        UnivariateFunction f = new SinFunction ();
        double r;
        UnivariateSolver solver = new BrentSolver();

        r = solver.solve(100, f, 1, 20);
</syntaxhighlight>

Result : r = PI

<syntaxhighlight lang="java">
        UnivariateFunction f = new SinFunction ();
        double r;
        UnivariateSolver solver = new BrentSolver();

        r = solver.solve(100, f, 2, 20);
</syntaxhighlight>

Result : r = 3 PI

<syntaxhighlight lang="java">
        UnivariateFunction f = new SinFunction ();
        double r;
        UnivariateSolver solver = new BrentSolver();

        r = solver.solve(100, f, 7, 20);
</syntaxhighlight>

Result : NoBracketingException exception

=== Newton method ===
The '''''Newton's method''''' (also known as the Newton–Raphson method) is a method for finding successively better approximations to the roots of a real-valued function. The idea of the method is as follows: one starts with an initial guess which is reasonably close to the true root, then the function is approximated by its tangent line, and one computes the x-intercept of this tangent line. This x-intercept will typically be a better approximation to the function's root than the original guess, and the method can be iterated.

IMPORTANT : the Newton solver only works for differentiable functions, this is reflected in the interface and class inheritances.

<syntaxhighlight lang="java">
        DifferentiableUnivariateFunction f = new XMinus5Function ();
        double r;
        DifferentiableUnivariateSolver solver = new NewtonSolver();

        r = solver.solve(100, f, 1, 6);
</syntaxhighlight>

Result : r = 5


'''''<u>aberrant behavior</u>'''''<u> :</u>

<syntaxhighlight lang="java">
        DifferentiableUnivariateFunction f = new SinFunction();
        double r;
        DifferentiableUnivariateSolver solver = new NewtonSolver();

        r = solver.solve(100, f, 1, 2);
</syntaxhighlight>

Result : r =- 4 PI

<syntaxhighlight lang="java">
        DifferentiableUnivariateFunction f = new SinFunction();
        double r;
        DifferentiableUnivariateSolver solver = new NewtonSolver();

        r = solver.solve(100, f, 1, 3);
</syntaxhighlight>

Result : r = PI

<syntaxhighlight lang="java">
        DifferentiableUnivariateFunction f = new XMinus5Function ();
        double r;
        DifferentiableUnivariateSolver solver = new NewtonSolver();

        r = solver.solve(100, f, 5.1, 20);
</syntaxhighlight>

Result : r = 5

=== Bisection method ===
The '''''bisection method''''' is a root-finding method which repeatedly bisects an interval and then selects a subinterval in which a root must lie for further processing. It is a very simple and robust method, but it is also relatively slow.

<syntaxhighlight lang="java">
        UnivariateFunction f = new XMinus5Function ();
        double r;
        UnivariateSolver solver = new BisectionSolver();

        r = solver.solve(100, f, 3, 4);
</syntaxhighlight>

Result : r = PI


'''''<u>behavior deteriorated</u>'''''<u> :</u>

<syntaxhighlight lang="java">
        UnivariateFunction f = new XMinus5Function ();
        double r;
        UnivariateSolver solver = new BisectionSolver();

        r = solver.solve(100, f, 5.1, 20);
</syntaxhighlight>

Result : r = 20 (the upper bound of the interval)

=== Müller method ===
The'''''Müller's method''''' is based on the secant method, which constructs at every iteration a line through two points on the graph of f. Instead, Müller's method uses three points, constructs the parabola through these three points, and takes the intersection of the x-axis with the parabola to be the next approximation.

<syntaxhighlight lang="java">
        UnivariateFunction f = new XMinus5Function ();
        double r;
        UnivariateSolver solver = new MullerSolver();

        r = solver.solve(100, f, 1, 6);
</syntaxhighlight>

Result : r = 5

<syntaxhighlight lang="java">
        UnivariateFunction f = new XMinus5Function ();
        double r;
        UnivariateSolver solver = new MullerSolver();

        r = solver.solve(100, f, 2, 3);
</syntaxhighlight>

Result : NoBracketingException exception

<syntaxhighlight lang="java">
        UnivariateFunction f = new SinFunction ();
        double r;
        UnivariateSolver solver = new MullerSolver();

        r = solver.solve(100, f, 1, 20);
</syntaxhighlight>

Result : NoBracketingException exception

== Getting Started ==
{{specialInclusion prefix=$theme_sub section="GettingStarted"/}}

== Contents ==
=== Interfaces ===
The library defines the following interfaces related to solvers:

{| class="wikitable"
|-
! scope="col"| Interface
! scope="col"| Summary
! scope="col"| Javadoc
|-
|'''UnivariateSolver'''
|Interface for a univariate solver
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/analysis/solver/UnivariateSolver.html ...]
|-
|'''UnivariateDifferentiableSolver'''
|Interface for a differentiable univariate real solver
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/analysis/solver/UnivariateDifferentiableSolver.html ...]
|}

=== Classes ===
This section is about the following classes related to solvers :

{| class="wikitable"
|-
! scope="col"| Class
! scope="col"| Summary
! scope="col"| Javadoc
|-
|'''BrentSolver'''
|Brent solver implementation.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/analysis/solver/BrentSolver.html ...]
|-
|'''NewtonRaphsonSolver'''
|Newton-Raphson solver implementation.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/analysis/solver/NewtonRaphsonSolver.html ...]
|-
|'''BisectionSolver'''
|Bisection solver implementation.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/analysis/solver/BisectionSolver.html ...]
|-
|'''MullerSolver'''
|Müller solver implementation.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/analysis/solver/MullerSolver.html ...]
|}

== [[File:lightBulb.png]] Tips & Tricks ==
Summing up : the solvers appear to behave in unexpected ways when the initial conditions are not "ideal". Therefore It is advised, when using the solvers, to :

* avoid non-ideal initial conditions,
* read the solvers' javadoc carefully,
* always check if the solvers' results are appropriate.

[[Category:User_Manual_4.13_Mathematics]]