Root Finder Framework

 

Lakshmi Krishnamurthy

v1.6, 6 Dec 2012

 

1. Introduction

 

1.1  Purpose

 

The paper composes and presents a comprehensive software knowledge unit framework for the Root finder solution. To do this effectively, the paper starts by discussing the mathematical, computational, and software aspects related to the different root finder approaches, as well as their suitability under different scenarios.

 

Finally, this paper presents the knowledge unit abstraction, the component and the framework design, the constituent modules, and the API details.

 

 

1.2  Definition and Scope

 

The root-finding algorithm is a numerical method, or algorithm, for finding an x such that f(x) = 0, for a given function f. Such an x is called a root of the function f.

 

Univariate root-finding algorithm finds the scalar, real roots that exist as floating point numbers. Focus is on functions that are continuous in the root neighborhood; well-behaved, differentiable functions are a special case, with specialized techniques available for solution.

 

Although most of the treatment is for black box functions, extensions to polynomial functions are considered as well.

 

 

1.3 Literature

 

Univariate root finder algorithms/methodologies are a well-researched area, so a number of solid overviews and trade-offs of the approaches are available [1, 2, 3].

 

A number of popular bracketing root finder methods have been proposed and examined in varying detail – the more common ones include the bisection method, interpolation methods (linear, quadratic, and inverse quadratic [4]), Brent’s method ([2, 3, 5, 6, 7]) with modifications ([8]), and Ridder’s method [2, 8, 9].

 

Among the non-bracketing methods, the secant method and, in particular, Newton’s method [10, 11], have been examined in detail. Additional approaches enable Newton’s method to deal with root multiplicity, convergence zone estimation [12], as well as customized root neighborhood proxy functions for robustness [13].

 

Finally, several root finding methods specific to polynomial solvers have also proposed – typically these deal with issues related to isolation of multiple roots, root multiplicities, and root ill-conditioning [14, 15, 16].

 

 

1.4  Framework Goals

 

The following are the goals for this framework:

 

·        Framework glossary

·        Framework description

·        Root search initialization techniques (e.g., brackets and starting variate determination)

·        Open root search iteration methods

·        Primitive bracketing iteration methods

·        Compound bracketing iteration methods

·        Brief discussion of polynomial roots

·        Root Finder software implementation details

 

2. Root Finder Framework Description

 

 

2.1 Framework Glossary

 

·        Hyperspace Search: Hyperspace search is a search to determine whether the entity is inside the zone of a range, e.g., bracketing search.

·        Hyperpoint Search: Hyperpoint searches are hard searches that search for an exact specific point (to within an appropriately established tolerance).

·        Iterate Nodes: This is the set of the traveled nodes (variate/Objective Function ordered pairs) that contain the trajectory traveled.

·        Iteration Search Primitives: The set of variate iteration routines that generate the subsequent iterate nodes.

·        Compound iterator search scheme: Search schemes where the primitive iteration routine to be invoked at each iteration is evaluated.

 

 

2.2 Framework

 

The root search given an objective function and its goal is achieved by iteratively evolving the variate, and involves the following steps:

 

·        Search initialization and root reachability determination: Searched is kicked off by spawning a root variate iterator for the search initialization process (described in detail in the next section).

·        Absolute Tolerance Determination.

·        Root Search Iteration: The root is searched iteratively according to the following steps:

1.      The iterator progressively reduces the bracket width.

2.      Successive iteration occurs using either a single primitive (e.g., using the bisection primitive), or using a selector scheme that picks the primitives for each step (e.g., Brent’s method).

3.      For Open Method, instead of 1 and 2, the routine drives towards convergence iteratively.

·        Search Termination Detection: The search termination occurs typically based on the following:

1.      Proximity to the Objective Function Goal

2.      Convergence on the variate

3.      Exhaustion if the number of iterations

 

The flow behind these steps is illustrated in Figure 1.

 

 

The “Flow Control Variate” in root search is the “Objective Function Distance to Goal” Metric.

 

 

2.2.1 Search Initialization

 

Broadly speaking, root finding approaches can be divided into a) those that bracket roots before they solve for them, and b) those that don’t need to bracket, opting instead to pick a suitable starting point.

 

Depending upon the whether the search is a bracketing or an open method, the search initialization does one the following:

·        Determine the root brackets for bracketing methods

·        Locate root convergence zone for open methods

Initializes begins by a search for the starting zone. A suitable starting point/zone is determined where, by an appropriate choice for the iterator, you are expected to reach the fixed-point target within a sufficient degree of reliability. Very general-purpose heuristics often help determine the search start zone.

 

Both bracketing and open initializers are hyperspace searches, since they search for something “IN”, not “AT”.

 

 

2.2.2 Bracketing Start Initialization

 

Bracketing is the process of localizing the fixed point to within a target zone with the least required number of Objective Function calculations. Steps are:

1.      Determine a valid bracketing search start

2.      Choose a suitable bracket expansion

3.      Limit attention to where the Objective Function is defined (more on this below).

 

Figure 2 shows the flow for the Bracketing routine.

 

Bracketing methods require that the initial search interval bracket the root (i.e. the function values at interval end points have opposite signs). Bracketing traps the fixed point between two variate values, and uses the intermediate value theorem and the continuity of the Objective Function to guarantee the presence/existence of the fixed point between them. Unless the objective function is discontinuous, bracketing methods guarantee convergence (although may not be within the specified iteration limit). Typically, they do not require the objective function to be differentiable.  Bracketing iteration primitives’ convergence is usually linear to super-linear.

 

Bracketing methods preserve bracketing throughout computation and allow user to specify which side of the convergence interval to select as the root. It is also possible to force a side selection after a root has been found, for example, in sequential search, to find the next root.

 

Generic root bracketing methods that treat the objective function as a black box will be slower than targetted ones – so much so that they can constitute the bulk of the time for root search. This is because, to accommodate generic robustness coupled with root-pathology avoidance (oscillating bracket pairs etc), these methods have to perform a full variate space sweep without any assumptions regarding the location of the roots (despite this most bracketing algorithms cannot guarantee isolation of root intervals). For instance, naďve examination of the Objective Function’s “sign-flips” alone can be misleading, especially if you bracket fixed-points with even numbered multiplicity within the brackets. Thus, some ways of analyzing the Black Box functions (or even the closed form Objective Functions) are needed to better target/customize the bracketing search (of course, parsimony in invoking the number of objective function calls is the main limitation).

 

The first step is to determine a valid bracketing search start. One advantage with univariate root finding is that objective function range validity maybe established using an exhaustive variate scanner search without worrying about combinatorial explosion. Objective Function may fail evaluation at the specified variate for the following reason:

·        Objective Function is not defined at the specified variate.

·        Objective Function evaluates to a complex number.

·        Objective Function evaluation produces NaN/Infinity/Under-flow/Over-flow errors.

 

In such situations, the following steps are used to steer the variate to a valid zone.

 

·        Objective Function undefined at the Bracketing Candidate Variate: If the Objective Function is undefined at the starting variate, the starting variate is expanded using the variate space scanner algorithm described above. If the objective Function like what is seen in Figure 3, a valid starting variate will eventually be encountered.

 

 

·        Objective Function not defined at any of the Candidate Variates: The risk is that the situation in Figure 4 may be encountered, where the variate space scanner iterator “jumps over” the range over which the objective function is defined. This could be because the objective function may have become complex. In this case, remember that an even power of the objective function also has the same roots as the objective function itself. Thus, solving for an even power of the objective function (like the square) – or even bracketing for it – may help.

 

 

Figure 5 shows the flow behind a general-purpose bracket start locator.

 

Once the starting variate search is successful, and the objective function validity is range-bound, then use an algorithm like bisection to bracket the root (as shown in Figure 6 below). However, if the objective function runs out of its validity range under the variate scanner scheme, the following steps need to undertaken:

·        If the left bracketing candidate fails, bracketing is done towards the right using the last known working left-most bracketing candidate as the “left edge”.

·        Likewise, if the right bracketing candidate fails, bracketing is done towards the left using the last known working right-most bracketing candidate as the “right edge”.

 

 

 

The final step is to trim the variate zone. Using the variate space scanner algorithm, and the mapped variate/Objective Function evaluations, the tightest bracketing zones are extracted (Figure 7).

 

 

2.2.3 Open Search Initialization

 

Non-bracketing methods use a suitable starting point to kick off the root search. As is obvious, the chosen starting point can be critical in determining the fate of the search. In particular, it should be within the zone of convergence of the fixed-point root to guarantee convergence. This means that specialized methods are necessary to determine zone of convergence.

When the objective function is differentiable, the non-bracketing root finder often may make use of that to achieve quadratic or higher speed of convergence. If the non-bracketing root finder cannot/does not use the objective function’s differentiability, convergence ends up being linear to super-linear. Section 2.3 discusses these issues in detail.

The typical steps for determining the open method starting variate are:

 

1.      Find a variate that is proximal to the fixed point

2.      Verify that it satisfies the convergence heuristic

 

Bracketing followed by a choice of an appropriate primitive variate (such as bisection/secant) satisfies both, thus could be a good starting point for open method searches like Newton’s method.

 

Before delving into the root finders in detail, there are several inherent software challenges in root finding that need to be remembered (see, e.g, [3]):  a) numerical, (e.g., due to bit cancellation), b) ill-conditioning (e.g., see high order polynomial roots [16]), c) "domains of indeterminacy" – existence of sizeable intervals around which the objective function hovers near the target, d) Continuous, but abrupt changes (e.g., near-delta Gaussian objection function), e) Under-flow/over-flow/roundoff errors, f) root multiplicity (e.g., [14] in the context of polynomial roots). Typical solution is to transform the objective function to a better conditioned function – insight into the behavior of the objective can be used to devise targetted solutions, as shown in [13].

 

 

2.3 Open Root Search Methods

 

2.3.1 Solver for differentiable univariate function: Newton’s method

 

Newton’s method uses the objective function f and it’s derivative f’ to iteratively evaluate the root. Given a well-behaved function f and it’s derivative f’ defined over real x, the algorithm starts with an initial guess of x0 for the root. First iteration yields . This is repeated in  till a value xn that is convergent enough is obtained.


If  is a simple root (root with multiplicity 1), and  and  respectively, then for sufficiently large n, the convergence is quadratic:

 



Clearly, Newton’s method only works when f has continuous derivatives in the root neighborhood. When analytical derivatives are hard to compute, calculate slope through nearby points, but convergence tends to be linear (like secant). If the first derivative is not well behaved/does not exit/undefined in the neighborhood of a particular root, the method may overshoot, and diverge from that root.

 

If a stationary point of the function is encountered, the derivative is zero and the method will fail due to division by zero. The stationary point can be encountered at the initial or any of the other iterative points. Even if the derivative is small but not zero, the next iteration will be a far worse approximation. A large error in the initial estimate can contribute to non-convergence of the algorithm (owing to the fact that the zone is outside of the neighborhood convergence zone).

 

If  is a root with multiplicity, then for sufficiently large n, the convergence becomes linear - When there are two or more roots that are close together then it may take many iterations before the iterates get close enough to one of them for the quadratic convergence to be apparent. However, if the multiplicity m of the root is known, one can use the following modified algorithm that preserves the quadratic convergence rate (equivalent to using successive over-relaxation) (see [12]):

 

 

The algorithm estimates m after carrying out one or two iterations, and then use that value to increase the rate of convergence. Alternatively, the modified Newton’s method may also be used:

 

 

It is easy to show that if  and , the convergence in the neighborhood becomes linear. Further, if  and , convergence becomes cubic.

[12] illustrates one way of determining the neighborhood of the root. Define

where
(a)  is a fixed point of []
(b)  is a positive constant,
(c) , and
(e) for all .
[12] shows that a sufficient condition for to initialize a convergent sequence , which converges to the root of is that and that  be chosen so that  for all .

It is easy to show that under specific choices for the starting variate, Newton’s method can fall into a basin of attraction [11]. These are segments of the real number line such that within each region iteration from any point leads to one particular root - can be infinite in number and arbitrarily small. Also, the starting or the intermediate point can enter a cycle - the n-cycle can be stable, or the behavior of the sequence can be very complex (forming a Newton fractal).

Newton's method for optimization is equivalent to iteratively maximizing a local quadratic approximation to the objective function. But some functions are not approximated well by quadratic, leading to slow convergence, and some have turning points where the curvature changes sign, leading to failure. Approaches to fix this use a more appropriate choice of local approximation than quadratic, based on the type of function we are optimizing. [13] demonstrates three such generalized Newton rules. Like Newton's method, they only involve the first two derivatives of the function, yet converge faster and fail less often.

One significant advantage of Newton’s method is that it can be readily generalized to higher dimensions.

 

2.3.2 Solver for univariate function: Secant

 

Secant method results on the replacement of the derivative in the Newton’s method with a secant-based finite difference slope.

 

Convergence for the secant method is slower than the Newton’s method (approx. order is 1.6); however, the secant method does not require the objective function to be differentiable. It also tends to be less robust than the popular bracketing methods.

 

 

2.4 Bracketing Iterative Root Search

 

Bracketing iterative root searches attempt to progressively narrow the brackets and to discover the root within. The first set discusses the goal search univariate iterator primitives that are commonly used to iterate through the variate. These goal search iterator primitives continue generating a new pair of iteration nodes (just like their bracketing search initialization counter-parts). Certain iterator primitives carry bigger “local” cost, i.e., cost inside a single iteration, but may reduce global cost, e.g., by reducing the number iterations due to faster convergence. Further, certain primitives tend to be inherently more robust, i.e., given enough iteration, they will find the root within – although they may not be fast.

 

Finally the case of compound iterator search schemes, search schemes where the primitive iteration routine to be invoked at each iteration is evaluated on-the-fly, are discussed. Iterative searches that maintain extended state across searches pay a price in terms of scalability – the price depending on the nature and the amount of state held (e.g., Brent’s method carries iteration selection state, whereas Zheng’s does not).

 

 

2.4.1 Univariate iterator primitive: Bisection

 

Bisection starts by determining a pair of root brackets a and b. It iteratively calculates f at , then uses c to replace either a or b, depending on the sign. It eventually stops when f has attained the desired tolerance.

 

Bisection relies on f being continuous within the brackets. While the method is simple to implement and reliable (it is a fall-back for less reliable ones), the convergence is slow, producing a single bit of accuracy with each iteration.

 

 

2.4.2 Univariate iterator primitive: False Position

 

False position works the same as bisection, except that the evaluation point c is linearly interpolated; f is computed at , where f(a) and f(b) have opposite signs. This holds obvious similarities with the secant method.

 

False position method also requires that f be continuous within the brackets.  It is simple enough, more robust than secant and faster than bisection, but convergence is still linear to super-linear.

 

Given that the linear interpolation of the false position method is a first-degree approximation of the objective function within the brackets, quadratic approximation using Lagrange interpolation may be attempted as

 

 

where we use the three iterates, xn−2, xn−1 and xn, with their function values, fn−2, fn−1 and fn. This reduces the number of iterations at the expense of the function point calculations.

 

Using higher order polynomial fit for the objective function inside the bracket does not always produce roots faster or better, since it may result in spurious inflections (e.g., Runge’s phenomenan [17]). Further, quadratic or higher fits may also cause complex roots.

 

 

2.4.3 Univariate iterator primitive: Inverse Quadratic [4]

 

Performing a fit of the inverse 1/f instead of f avoids the quadratic interpolation problem above. Using the same symbols as above, the inverse can be computed as

 

 

Convergence is faster than secant, but poor when iterates not close to the root. If two of the function values fn−2, fn−1 and fn coincide, the algorithm fails.

 

 

2.4.4 Univariate iterator primitive: Ridder’s [9]

 

Ridders' method is a variant on the false position method that uses exponential function to successively approximate a root of f. Given the bracketing variates, x1 and x2, which are on two different sides of the root being sought, the method evaluates f at . It extracts exponential factor  such that  forms a straight line across x1, x2, and x3. x2 is calculated from

 

 

Ridder’s method is simpler than Brent's method, and has been claimed to perform about the same. However, the presence of the square root can render it unstable for many of the reasons discussed above.

 

 

2.4.5        Univariate compound iterator: Brent [5, 6, 7] and Zheng [8]

 

Brent’s predecessor method first combined bisection, secant, and inverse quadratic to produce the optimal root search for the next iteration. Starting with the bracket points a0 and b0, two provisional values for the next iterate are computed; the first given by the secant method , and the second by bisection . If s lies between bk and m, it becomes the next iterate bk+1, otherwise the m is the next iterate.

 

Then, the value of the new contrapoint is chosen such that f(ak+1) and f(bk+1) have opposite signs. Finally, if |f(ak+1)| < |f(bk+1)|, then ak+1 is probably a better guess for the solution than bk+1, and hence the values of ak+1 and bk+1 are exchanged.

To improve convergence, Brent’s method requires that two inequalities must be simultaneously satisfied.

a)      Given a specific numerical tolerance , if the previous step used the bisection method, if , the bisection method is performed and its result used for the next iteration. If the previous step used interpolation, then the check becomes .

b)      If the previous step used bisection, if, secant is used; otherwise the bisection used for the next iteration. If the previous step performed interpolation,  is checked instead.

 

Finally, since Brent's method uses inverse quadratic interpolation, s has to lie between (3ak + bk) / 4 and bk.

As can be seen, Brent’s algorithm uses three points for the next inverse quadratic interpolation, or secant rule, based upon the criterion specified above. One simplification to the Brent’s method [8] adds one more evaluation for the function at the middle point before the interpolation. This simplification reduces the times for the conditional evaluation and reduces the interval of convergence. [8] shows that the convergence is better than Brent’s, and as fast and simple as Ridder’s (next section).

 

 

2.6 Polynomial Roots

 

This section carries out a brief treatment of computing roots for polynomials. While closed form solutions are available for polynomials up to degree 4, they may not be stable numerically. Popular techniques such as Sturm’s theorem and Descartes’ rule of signs are used for locating and separating real roots. Modern methods such as VCA [14] and the more powerful VAS [15] use these with Bisection/Newton methods – these methods are used in Maple/Mathematica.

 

Since the eigenvalues of the companion matrix to a polynomial correspond to the polynomial’s roots, common fast/robust methods used to find them may also be used.

 

A number of caveats apply specifically to polynomial root searches, e.g., Wilkinson’s polynomial [16] shows why high precision is needed when computing the roots – proximal/other ill-conditioned behavior may occur.

 

Finally, special ways exist to identify/extract multiplicity in polynomial roots – they use the fact that f(x) and f’(x) share the root, and by figuring out their GCD.

 

 

3. Software Framework Components

 

 

3.1 Execution Initialization

 

3.1.1 ExecutionInitializer

 

ExecutionInitializer implements the initialization execution and customization functionality. It performs two types of variate initialization:

·        Bracketing initialization: This brackets the fixed point using the bracketing algorithm described above. If successful, one pair of variate/ObjectiveFunction coordinate nodes that bracket the root is generated. These brackets are eventually used by routines that iteratively determine the root. Bracketing initialization is controlled by the parameters in BracketingControlParams.

·        Convergence Zone initialization: This generates a variate that lies within the convergence zone for the iterative determination of the fixed point using the Newton's method. Convergence Zone Determination is controlled by the parameters in ConvergenceControlParams.

 

 

3.1.2 ExecutionInitializationOutput

 

ExecutionInitializationOutput holds the output of the root initializer calculation. It contains the following fields:

·        Whether the initialization completed successfully the number of iterations, the number of ObjectiveFunction calculations, and the time taken for the initialization

·        The starting variate from the initialization

 

 

3.2 Bracketing

 

3.2.1 BracketingControlParameters

 

BracketingControlParams implements the control parameters for bracketing solutions. It provides the following parameters:

·        The starting variate from which the search for bracketing begins

·        The initial width for the brackets

·        The factor by which the width expands with each iterative search

·        The number of such iterations.

 

 

3.2.2 BracketingOutput

 

BracketingOutput carries the results of the bracketing initialization. In addition to the fields of ExecutionInitializationOutput, BracketingOutput holds the left/right bracket variates and the corresponding values for the ObjectiveFunction.

 

 

3.3 Convergence

 

3.3.1 ConvergenceControlParameters

 

ConvergenceControlParams holds the fields needed for the controlling the execution of Newton's method. It does that using the following parameters:

·        The determinant limit below which the convergence zone is deemed to have been reached.

·        Starting variate from where the convergence search is kicked off.

·        The factor by which the variate expands across each iterative search.

·        The number of search iterations.

 

 

3.3.2 ConvergenceOutput

 

ConvergenceOutput extends the ExecutionInitializationOutput by retaining the starting variate that results from the convergence zone search.

 

ConvergenceOutput does not add any new field to ExecutionInitializationOutput.

 

 

3.4 Differentiation

 

3.4.1 ObjectiveFunction

 

ObjectiveFunction provides the evaluation of the ObjectiveFunction and its derivatives for a specified variate. Default implementation of the derivatives is meant for non-analytical black box ObjectiveFunction.

 

 

3.4.2 DerivativeControl

 

DerivativeControl provides bumps needed for numerically approximating derivatives.

 

 

3.4.3 Differential

 

Differential holds the incremental differentials for the variate and the ObjectiveFunction.

 

 

3.5 Execution Customization

 

3.5.1 ExecutionControl

 

ExecutionControl implements the core root search execution control and customization functionality. It is used for a) calculating the absolute tolerance, and b) determining whether the ObjectiveFunction has reached the goal.

 

ExecutionControl determines the execution termination using its ExecutionControlParams instance.

 

 

3.5.2 ExecutionControlParams

 

ExecutionControlParams holds the parameters needed for controlling the execution of the root finder.

 

ExecutionControlParams fields control the root search in one of the following ways:

·        Number of iterations after which the search is deemed to have failed

·        Relative ObjectiveFunction Tolerance Factor which, when reached by the objective function, will indicate that the fixed point has been reached

·        Absolute Tolerance fall-back, which is used to determine that the fixed point has been reached when the relative tolerance factor becomes zero

 

 

3.6 Fixed Point Search

 

3.6.1 FixedPointFinder

 

FixedPointFinder is the base abstract class that is implemented by customized invocations, e.g., Newton's method, or any of the bracketing methodologies. It invokes the core routine for determining the fixed point from the goal. ExecutionControl determines the execution termination.

 

FixedPointFinder main flow comprises of the following steps:

·        Initialize the root search zone by determining either a) the brackets, or b) the starting variate.

·        Compute the absolute ObjectiveFunction tolerance that establishes the attainment of the fixed point.

·        Launch the variate iterator that iterates the variate.

·        Iterate until the desired tolerance has been attained

·        Return the root finder output.

 

Root finders that derive from this provide implementations for the following:

·        Variate initialization: They may choose either bracketing initializer, or the convergence initializer - functionality is provided for both in this module.

·        Variate Iteration: Variates are iterated using a) any of the standard primitive built-in variate iterators (or custom ones), or b) a variate selector scheme for each iteration.

 

 

3.6.2 FixedPointFinderOutput

 

FixedPointFinderOutput holds the result of the root search. It contains the following fields:

·        Whether the search completed successfully

·        The number of iterations, the number of objective function base/derivative calculations, and the time taken for the search

·        The output from initialization

 

 

3.6.3 FixedPointFinderNewton

 

FixedPointFinderNewton customizes the FixedPointFinder for Open (Newton's) root finder functionality.

 

FixedPointFinderNewton applies the following customization:

·        Initializes the fixed point finder by computing a starting variate in the convergence zone

·        Iterating the next search variate using the Newton's method.

 

 

3.6.4 FixedPointFinderBracketing

 

FixedPointFinderBracketing customizes the FixedPointFinder for bracketing based root finder functionality.

 

FixedPointFinderBracketing applies the following customization:

·        Initializes the root finder by computing the starting brackets

·        Iterating the next search variate using one of the specified variate iterator primitives.

 

FixedPointFinderBracketing does not do compound iterations of the variate using any schemes - that is done by classes that extend it.

 

 

3.6.5 FixedPointFinderBrent

 

FixedPointFinderBrent customizes FixedPointFinderBracketing by applying the Brent's scheme of compound variate selector.

 

Brent's scheme, as implemented here, is described above. This implementation retains absolute shifts that have happened to the variate for the past 2 iterations as the discriminant that determines the next variate to be generated.

 

FixedPointFinderBrent uses the following parameters specified in VariateIterationSelectorParams:

·        The Variate Primitive that is regarded as the "fast" method

·        The Variate Primitive that is regarded as the "robust" method

·        The relative variate shift that determines when the "robust" method is to be invoked over the "fast"

·        The lower bound on the variate shift between iterations that serves as the fall-back to the "robust"

 

 

3.6.6 FixedPointFinderZheng

 

FixedPointFinderZheng implements the root locator using Zheng's improvement to Brent's method. It overrides the iterateCompoundVariate method in FixedPointFinderBrent to achieve the desired simplification in the iterative variate selection.

 

 

3.7 Iteration Entities

 

3.7.1 IteratedBracket

 

IteratedBracket holds the left/right bracket variates and the corresponding values for the ObjectiveFunction during each iteration.

 

 

3.7.2 IteratedVariate

 

IteratedVariate holds the variate and the corresponding value for the ObjectiveFunction during each iteration.

 

 

3.7.3 VariateIteratorPrimitive

 

VariateIteratorPrimitive implements the various variate iterator primitives. It implements the following primitives:

·        Bisection

·        False Position

·        Quadratic

·        Inverse Quadratic

·        Ridder

 

It may be readily enhanced to accommodate additional primitives.

 

 

3.7.4 VariateIteratorSelectorParameters

 

VariateIteratorSelectorParameters implements the control parameters for the compound variate selector scheme used in Brent's method.

 

Brent's method uses the following fields in VariateIteratorSelectorParameters to generate the next variate:

·        The Variate Primitive that is regarded as the "fast" method

·        The Variate Primitive that is regarded as the "robust" method

·        The relative variate shift that determines when the "robust" method is to be invoked over the "fast"

·        The lower bound on the variate shift between iterations that serves as the fall-back to the "robust".

 

 

4. References

 

 

[1] Root finding Algorithms (Wiki): http://en.wikipedia.org/wiki/Root-finding_algorithm

[2] Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 9.2.1. Ridders' Method". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press.

[3] Apache Commons Math Documentation http://commons.apache.org/math/userguide/analysis.html

[4] Inverse Quadratic Interpolation (Wiki): http://en.wikipedia.org/wiki/Inverse_quadratic_interpolation

[5] Dekker, TJ (1969). Finding a zero by means of successive linear interpolation, Constructive Aspects of the Fundamental Theorem of Algebra, Wiley

Interscience, London.

[6] Brent, RP (1973). Algorithms for Minimization without Derivatives, Chapter 4. Prentice-Hall, Englewood Cliffs, NJ.

[7] Antia, HM (2002), Numerical Methods for Scientists and Engineers, Birkhäuser, pp.362-365, 2nd ed.

[8] Zhang, Z (2011). An Improvement to the Brent’s Method, International Journal of Experimental Algorithms (IJEA), Volume (2) : Issue (1) : 2011

[9] Ridders, C. (1979). "A new algorithm for computing a single root of a real continuous function". IEEE Transactions on Circuits and Systems 26: 979–980.

[10] Newton's Method: http://en.wikipedia.org/wiki/Newton%27s_method

[11] Dence, T (November 1997), Cubics, chaos and Newton's method, Mathematical Gazette 81, 403-408.

[12] Accelerated and Modified Newton’s Method http://math.fullerton.edu/mathews/n2003/newtonacceleratemod.html

[13] Minka, TP (2002) Beyond Newton’s Method http://research.microsoft.com/en-us/um/people/minka/papers/newton.html

[14] Rouillier, F and Zimmerman, P (2004) Efficient isolation of polynomial's real roots, Journal of Computational and Applied Mathematics 162

[15] Akritas, AG; Strzeboński, AW (2005). A Comparative Study of Two Real Root Isolation Methods. Nonlinear Analysis: Modelling and Control 10 (4): 297–304.

[16] Trefethen, LN, Bau, D (1997), Numerical Linear Algebra, SIAM

[17] Berrut, JP, Trefethen, LN. (2004), Barycentric Lagrange interpolation, SIAM Review 46 (3): 501–517.