Class container for the Algorithm 748. More...

#include <Algo748.hh>

Inherits Optimist::RootFinder::Bracketing< Scalar, Algo748< Scalar > >.

Public Member Functions
	Algo748 ()
constexpr std::string	name_impl () const
template<typename FunctionLambda>
Scalar	find_root_impl (FunctionLambda &&function)
Public Member Functions inherited from Optimist::RootFinder::Bracketing< Scalar, Algo748< Scalar > >
	Bracketing ()
constexpr std::string	name_impl () const
void	tolerance_bracketing (Scalar t_tolerance)
bool	solve_impl (FunctionLambda &&function, Scalar, Scalar &x_sol)
Scalar	find_root (FunctionLambda &&function)
Public Member Functions inherited from Optimist::RootFinder::RootFinder< Scalar, Algo748< Scalar > >
	RootFinder ()
constexpr std::string	name () const
Integer	jacobian_evaluations () const
Integer	max_jacobian_evaluations () const
Integer	hessian_evaluations () const
Integer	max_hessian_evaluations () const
bool	solve (FunctionLambda &&function, const Input &x_ini, Output &x_sol)
Public Member Functions inherited from Optimist::SolverBase< Scalar, Scalar, Algo748< Scalar > >
	SolverBase ()
void	reset_bounds (const Integer n=InputTrait::IsDynamic ? 0 :InputTrait::Dimension)
const Scalar &	lower_bound () const
const Scalar &	upper_bound () const
void	bounds (const Scalar &t_lower_bound, const Scalar &t_upper_bound)
constexpr Integer	input_dimension () const
constexpr Integer	output_dimension () const
Integer	function_evaluations () const
void	max_function_evaluations (const Integer t_max_function_evaluations)
Integer	iterations () const
Integer	max_iterations () const
Scalar	alpha () const
Integer	relaxations () const
Integer	max_relaxations () const
Scalar	tolerance () const
void	verbose_mode (bool t_verbose)
void	enable_verbose_mode ()
void	disable_verbose_mode ()
void	damped_mode (bool t_damped)
void	enable_damped_mode ()
void	disable_damped_mode ()
std::string	task () const
bool	converged () const
std::ostream &	ostream () const
bool	solve (FunctionLambda &&function, const Scalar &x_ini, Scalar &x_sol)
bool	rootfind (const FunctionBase< FunctionInput, FunctionOutput, DerivedFunction > &function, const Scalar &x_ini, Scalar &x_sol)
bool	optimize (const FunctionBase< FunctionInput, FunctionOutput, DerivedFunction > &function, const Scalar &x_ini, Scalar &x_sol)
constexpr std::string	name () const

Static Public Attributes
static constexpr bool	RequiresFunction {true}
static constexpr bool	RequiresFirstDerivative {false}
static constexpr bool	RequiresSecondDerivative {false}
Static Public Attributes inherited from Optimist::RootFinder::RootFinder< Scalar, Algo748< Scalar > >
static constexpr bool	IsRootFinder
static constexpr bool	IsOptimizer

Private Member Functions
bool	all_different (Scalar a, Scalar b, Scalar c, Scalar d) const
template<typename FunctionLambda>
bool	bracketing (FunctionLambda &&function)
Scalar	cubic_interpolation ()
Scalar	newton_quadratic (Integer n)

Additional Inherited Members
Public Types inherited from Optimist::RootFinder::RootFinder< Scalar, Algo748< Scalar > >
using	Scalar
using	Input
using	Output
Public Types inherited from Optimist::SolverBase< Scalar, Scalar, Algo748< Scalar > >
using	InputTrait
using	OutputTrait
using	Scalar
using	FirstDerivative
using	SecondDerivative
Protected Member Functions inherited from Optimist::RootFinder::RootFinder< Scalar, Algo748< Scalar > >
bool	evaluate_jacobian (JacobianLambda &&jacobian, const Input &x, FirstDerivative &out)
bool	evaluate_hessian (HessianLambda &&hessian, const Input &x, SecondDerivative &out)
Protected Member Functions inherited from Optimist::SolverBase< Scalar, Scalar, Algo748< Scalar > >
Integer	first_derivative_evaluations () const
Integer	max_first_derivative_evaluations () const
Integer	second_derivative_evaluations () const
Integer	max_second_derivative_evaluations () const
void	reset_counters ()
bool	evaluate_function (FunctionLambda &&function, const Scalar &x, Scalar &out)
bool	evaluate_first_derivative (FirstDerivativeLambda &&function, const Scalar &x, FirstDerivative &out)
bool	evaluate_second_derivative (SecondDerivativeLambda &&function, const Scalar &x, SecondDerivative &out)
bool	damp (FunctionLambda &&function, const Scalar &x_old, const Scalar &function_old, const Scalar &step_old, Scalar &x_new, Scalar &function_new, Scalar &step_new)
void	header ()
void	bottom ()
void	info (Scalar residuals, const std::string &notes="-")
Protected Attributes inherited from Optimist::RootFinder::Bracketing< Scalar, Algo748< Scalar > >
Scalar	m_tolerance_bracketing
Scalar	m_mu
Scalar	m_interval_shink
Scalar	m_a
Scalar	m_fa
Scalar	m_b
Scalar	m_fb
Scalar	m_c
Scalar	m_fc
Scalar	m_d
Scalar	m_fd
Scalar	m_e
Scalar	m_fe
Protected Attributes inherited from Optimist::SolverBase< Scalar, Scalar, Algo748< Scalar > >
Scalar	m_lower_bound
Scalar	m_upper_bound
Integer	m_function_evaluations
Integer	m_first_derivative_evaluations
Integer	m_second_derivative_evaluations
Integer	m_max_function_evaluations
Integer	m_max_first_derivative_evaluations
Integer	m_max_second_derivative_evaluations
Integer	m_iterations
Integer	m_max_iterations
Scalar	m_alpha
Integer	m_relaxations
Integer	m_max_relaxations
Scalar	m_tolerance
bool	m_verbose
bool	m_damped
std::ostream *	m_ostream
std::string	m_task
bool	m_converged

Detailed Description

template<typename Scalar>
class Optimist::RootFinder::Algo748< Scalar >

The algorithm 748 allows to find the roots of a scalar function \(f(x)\) in a given interval \([a, b]\). The algorithm is based on the work of G. Alefeld, F. Potra, and Y. Shi, Algorithm 748: Enclosing Zeros of Continuous Functions, ACM Transactions on Mathematical Software, 21 (1995), pp. 327-344, 10.1145/210089.210111.

Template Parameters

Scalar Floating-point number type.

Constructor & Destructor Documentation

◆ Algo748()

template<typename Scalar>

Optimist::RootFinder::Algo748< Scalar >::Algo748 ( )

inline

Class constructor for the Algorithm 748.

Member Function Documentation

◆ all_different()

template<typename Scalar>

bool Optimist::RootFinder::Algo748< Scalar >::all_different	(	Scalar	a,
		Scalar	b,
		Scalar	c,
		Scalar	d ) const

inlineprivate

Check if the input values are all different.

Parameters

[in]	a	The first value.
[in]	b	The second value.
[in]	c	The third value.
[in]	d	The fourth value.

Returns: The boolean flag, true if all the values are different, false otherwise.

◆ bracketing()

template<typename Scalar>

template<typename FunctionLambda>

bool Optimist::RootFinder::Algo748< Scalar >::bracketing ( FunctionLambda && function )

inlineprivate

Given current enclosing interval \([a, b]\) and \(a\) number \(c\) in \((a, b)\):

if \(f(c) = 0\) then sets the output \(a = c\).
Otherwise determines the new enclosing interval \([a, b] = [a, c]\) or \([a, b] = [c, b]\). also updates the termination criterion corresponding to the new enclosing interval. Adjust \(c\) if \((b-a)\) is very small or if \(c\) is very close to \(a\) or \(b\).
Template Parameters

FunctionLambda Function lambda type.

Parameters

[in] function Function lambda.

Returns
The boolean flag, true if the root is found, false otherwise.

◆ cubic_interpolation()

template<typename Scalar>

Scalar Optimist::RootFinder::Algo748< Scalar >::cubic_interpolation ( )

inlineprivate

Perform the cubic inverse interpolation of \(f(x)\) at \(a\), \(b\), \(d\), and \(e\) to get an approximate root \(r\) ( \(f(r) = 0\)).

Returns: The approximate root \(r\).

◆ find_root_impl()

template<typename Scalar>

template<typename FunctionLambda>

Scalar Optimist::RootFinder::Algo748< Scalar >::find_root_impl ( FunctionLambda && function )

inline

Finds either an exact solution or an approximate solution of the equation \(f(x) = 0\) in the interval \([a,b]\). At the beginning of each iteration, the current enclosing interval is recorded as \([a_0, b_0]\). The first iteration is simply a secant step. Starting with the second iteration, three steps are taken in each iteration.

The first two steps are either quadratic interpolation or cubic inverse interpolation.
The third step is a double-size secant step. If the diameter of the enclosing interval obtained after these three steps is larger than \(\mu*(b_0-a_0)\), an additional bisection step will be used to shrink the enclosing interval.
Template Parameters

FunctionLambda The lambda function type.

Parameters

[in] function Function lambda.

Returns
The approximate root.

◆ name_impl()

template<typename Scalar>

std::string Optimist::RootFinder::Algo748< Scalar >::name_impl ( ) const

inlineconstexpr

Get the Algorithm 748 solver name.

Returns: The Algorithm 748 solver name.

◆ newton_quadratic()

template<typename Scalar>

Scalar Optimist::RootFinder::Algo748< Scalar >::newton_quadratic ( Integer n )

inlineprivate

Perform \(n\) Newton steps to approximate the zero in \((a, b)\) of the quadratic polynomial interpolating \(f(x)\) at \(a\), \(b\), and \(d\). Safeguard is used to avoid overflow.

Parameters

[in] n The number of steps.

Returns: The approximate root.

Member Data Documentation

◆ RequiresFirstDerivative

template<typename Scalar>

bool Optimist::RootFinder::Algo748< Scalar >::RequiresFirstDerivative {false}

staticconstexpr

◆ RequiresFunction

template<typename Scalar>

bool Optimist::RootFinder::Algo748< Scalar >::RequiresFunction {true}

staticconstexpr

◆ RequiresSecondDerivative

template<typename Scalar>

bool Optimist::RootFinder::Algo748< Scalar >::RequiresSecondDerivative {false}

staticconstexpr

The documentation for this class was generated from the following file:

core/include/Optimist/RootFinder/Algo748.hh

Public Member Functions

Static Public Attributes

Private Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ Algo748()

Member Function Documentation

◆ all_different()

◆ bracketing()

◆ cubic_interpolation()

◆ find_root_impl()

◆ name_impl()

◆ newton_quadratic()

Member Data Documentation

◆ RequiresFirstDerivative

◆ RequiresFunction

◆ RequiresSecondDerivative