Uploaded image for project: 'Commons Math'
  1. Commons Math
  2. MATH-599

Re-implementation of Secant-based root finding algorithms

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Closed
    • Major
    • Resolution: Fixed
    • None
    • 3.0
    • None

    Description

      Apache Commons Math currently has a SecantSolver. It is unclear exactly what algorithm this solver implements. It states: "The algorithm is modified to maintain bracketing of a root by successive approximations. Because of forced bracketing, convergence may be slower than the unrestricted Secant algorithm. However, this implementation should in general outperform the Regula Falsi method." The Regula Falsi method is exactly the Secant method modified to maintain a bracketed solution. It is therefore unclear what other modifications were done to make it 'better' than the Regula Falsi method.

      Besides the Secant and Regula Falsi methods, several other Secant-based root-finding algorithms exist, such as the the Illinois method, and the Pegasus method. All 4 are well-known, publisched algorithms.

      I created a patch, which changes the following:

      • Removed SecantSolver root-finding algorithm.
      • Implemented new Secant-based root-finding algorithms: SecantSolver, RegulaFalsiSolver, IllinoisSolver, and PegasusSolver.
      • Introduced BracketedSolution interface and AllowedSolutions enumeration, to control allowed solutions (under-approximations and over-approximations) for bracketed root-finding algorithms. Implemented for RegulaFalsiSolver, IllinoisSolver, and PegasusSolver.
      • Fixed documentation of BaseUnivariateRealSolver.solve methods, such that documentation order of arguments matches the order of the actual arguments.

      Note that the original SecantSolver was removed, and replaced by a root-finding algorithm that actually implements the Secant root-finding algorithm. As such, existing code using the SecantSolver is not backwards compatible. That is, even though the new SecantSolver does implement the same interfaces, the root-finding solutions may differ. In particular, the new SecantSolver does not maintain a bracketed solution, and does not guarantee convergence.

      I added unit tests, and I did a build, including checkstyle checking. I did not fix all checkstyle warnings though, as I consider some of them false positives.

      Attachments

        1. secant-based-root-finding-algos.patch
          57 kB
          Dennis Hendriks
        2. secant-based-root-finding-algos2.patch
          57 kB
          Dennis Hendriks
        3. secant-based-root-finding-algos2.zip
          18 kB
          Dennis Hendriks

        Issue Links

          Activity

            People

              Unassigned Unassigned
              dhendriks Dennis Hendriks
              Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: