Class container for the Algorithm 748. More...

#include <Algo748.hh>

Inherits Optimist::ScalarRootFinder::Bracketing< Real, Algo748< Real > >.

Public Types
using	FunctionWrapper = typename Bracketing<Real, Algo748<Real>>::FunctionWrapper

using	FirstDerivativeWrapper = typename Bracketing<Real, Algo748<Real>>::FirstDerivativeWrapper

using	SecondDerivativeWrapper = typename Bracketing<Real, Algo748<Real>>::SecondDerivativeWrapper

Public Types inherited from Optimist::ScalarRootFinder::Bracketing< Real, Algo748< Real > >
using	FunctionWrapper

using	FirstDerivativeWrapper

using	SecondDerivativeWrapper

Public Types inherited from Optimist::ScalarRootFinder::ScalarRootFinder< Real, Algo748< Real > >
using	FunctionWrapper

using	FirstDerivativeWrapper

using	SecondDerivativeWrapper

Public Member Functions
	Algo748 ()

std::string	name_impl () const

Real	find_root_impl (FunctionWrapper function)

Public Member Functions inherited from Optimist::ScalarRootFinder::Bracketing< Real, Algo748< Real > >
	Bracketing ()

std::string	name_impl () const

void	tolerance_bracketing (Real t_tolerance)

bool	solve_impl (FunctionWrapper function, Real, Real &x_sol)

Real	find_root (FunctionWrapper function)

Public Member Functions inherited from Optimist::ScalarRootFinder::ScalarRootFinder< Real, Algo748< Real > >
	ScalarRootFinder ()

std::string	name () const

bool	solve (FunctionWrapper function, Real x_ini, Real &x_sol)

bool	solve (FunctionWrapper function, FirstDerivativeWrapper first_derivative, Real x_ini, Real &x_sol)

bool	solve (FunctionWrapper function, FirstDerivativeWrapper first_derivative, SecondDerivativeWrapper second_derivate, Real x_ini, Real &x_sol)

Public Member Functions inherited from Optimist::Solver< Real, 1, 1, Algo748< Real > >
	Solver ()

	Solver (FunctionWrapper function, const InputType &x_ini, InputType &x_sol)

	Solver (FunctionWrapper function, FirstDerivativeWrapper first_derivative, const InputType &x_ini, InputType &x_sol)

	Solver (FunctionWrapper function, FirstDerivativeWrapper first_derivative, SecondDerivativeWrapper second_derivative, const InputType &x_ini, InputType &x_sol)

const InputType &	lower_bound () const

void	lower_bound (const InputType &t_lower_bound)

const InputType &	upper_bound () const

void	upper_bound (const InputType &t_upper_bound)

void	bounds (const InputType &t_lower_bound, const InputType &t_upper_bound)

constexpr Integer	input_dimension () const

constexpr Integer	output_dimension () const

Integer	function_evaluations () const

void	max_function_evaluations (Integer t_max_function_evaluations)

Integer	max_function_evaluations () const

Integer	iterations () const

Integer	max_iterations () const

void	max_iterations (Integer t_max_iterations)

Real	alpha () const

void	alpha (Real t_alpha)

Integer	relaxations () const

Integer	max_relaxations () const

void	max_relaxations (Integer t_max_relaxations)

Real	tolerance () const

void	tolerance (Real t_tolerance)

void	verbose_mode (bool t_verbose)

bool	verbose_mode () const

void	enable_verbose_mode ()

void	disable_verbose_mode ()

void	damped_mode (bool t_damped)

bool	damped_mode () const

void	enable_damped_mode ()

void	disable_damped_mode ()

std::string	task () const

void	task (std::string t_task)

bool	converged () const

const TraceType &	trace () const

std::ostream &	ostream () const

void	ostream (std::ostream &t_ostream)

bool	solve (FunctionWrapper function, const InputType &x_ini, InputType &x_sol)

bool	solve (FunctionWrapper function, FirstDerivativeWrapper first_derivative, const InputType &x_ini, InputType &x_sol)

bool	solve (FunctionWrapper function, FirstDerivativeWrapper first_derivative, SecondDerivativeWrapper second_derivative, const InputType &x_ini, InputType &x_sol)

bool	rootfind (Function< Real, FunInDim, FunOutDim, DerivedFunction > const &function, const InputType &x_ini, InputType &x_sol)

bool	optimize (Function< Real, FunInDim, FunOutDim, DerivedFunction > const &function, const InputType &x_ini, InputType &x_sol)

std::string	name () const

Static Public Attributes
static constexpr bool	requires_function {true}

static constexpr bool	requires_first_derivative {false}

static constexpr bool	requires_second_derivative {false}

Static Public Attributes inherited from Optimist::ScalarRootFinder::Bracketing< Real, Algo748< Real > >
static constexpr bool	requires_function

static constexpr bool	requires_first_derivative

static constexpr bool	requires_second_derivative

Static Public Attributes inherited from Optimist::ScalarRootFinder::ScalarRootFinder< Real, Algo748< Real > >
static constexpr bool	is_rootfinder

static constexpr bool	is_optimizer

static constexpr bool	requires_function

static constexpr bool	requires_first_derivative

static constexpr bool	requires_second_derivative

Private Member Functions
bool	all_different (Real a, Real b, Real c, Real d) const

bool	bracketing (FunctionWrapper function)

Real	cubic_interpolation ()

Real	newton_quadratic (Integer n)

Additional Inherited Members
Public Attributes inherited from Optimist::ScalarRootFinder::ScalarRootFinder< Real, Algo748< Real > >
friend	Solver< Real, 1, 1, ScalarRootFinder< Real, DerivedSolver > >

Protected Types inherited from Optimist::Solver< Real, 1, 1, Algo748< Real > >
using	InputType

using	OutputType

using	TraceType

using	FirstDerivativeType

using	SecondDerivativeType

using	FunctionWrapper

using	FirstDerivativeWrapper

using	SecondDerivativeWrapper

Protected Member Functions inherited from Optimist::Solver< Real, 1, 1, Algo748< Real > >
Integer	first_derivative_evaluations () const

Integer	max_first_derivative_evaluations () const

void	max_first_derivative_evaluations (Integer first_derivative_evaluations)

Integer	second_derivative_evaluations () const

Integer	max_second_derivative_evaluations () const

void	max_second_derivative_evaluations (Integer second_derivative_evaluations)

bool	solve (Function< Real, FunInDim, FunOutDim, DerivedFunction > const &function, const InputType &x_ini, InputType &x_sol, bool is_optimization)

void	reset ()

void	evaluate_function (FunctionWrapper function, const InputType &x, OutputType &out)

void	evaluate_first_derivative (FirstDerivativeWrapper function, const InputType &x, FirstDerivativeType &out)

void	evaluate_second_derivative (SecondDerivativeWrapper function, const InputType &x, SecondDerivativeType &out)

void	store_trace (const InputType &x)

bool	damp (FunctionWrapper function, InputType const &x_old, InputType const &function_old, InputType const &step_old, InputType &x_new, InputType &function_new, InputType &step_new)

void	header ()

void	bottom ()

void	info (Real residuals, std::string const &notes="-")

Protected Attributes inherited from Optimist::ScalarRootFinder::Bracketing< Real, Algo748< Real > >
Real	m_tolerance_bracketing

Real	m_mu

Real	m_interval_shink

Real	m_a

Real	m_fa

Real	m_b

Real	m_fb

Real	m_c

Real	m_fc

Real	m_d

Real	m_fd

Real	m_e

Real	m_fe

Protected Attributes inherited from Optimist::Solver< Real, 1, 1, Algo748< Real > >
InputType	m_lower_bound

InputType	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

Real	m_alpha

Integer	m_relaxations

Integer	m_max_relaxations

Real	m_tolerance

bool	m_verbose

bool	m_damped

std::ostream *	m_ostream

std::string	m_task

bool	m_converged

TraceType	m_trace

Detailed Description

template<typename Real>
class Optimist::ScalarRootFinder::Algo748< Real >

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

Real	Scalar number type.

Member Typedef Documentation

◆ FirstDerivativeWrapper

template<typename Real>

using Optimist::ScalarRootFinder::Algo748< Real >::FirstDerivativeWrapper = typename Bracketing<Real, Algo748<Real>>::FirstDerivativeWrapper

◆ FunctionWrapper

template<typename Real>

using Optimist::ScalarRootFinder::Algo748< Real >::FunctionWrapper = typename Bracketing<Real, Algo748<Real>>::FunctionWrapper

◆ SecondDerivativeWrapper

template<typename Real>

using Optimist::ScalarRootFinder::Algo748< Real >::SecondDerivativeWrapper = typename Bracketing<Real, Algo748<Real>>::SecondDerivativeWrapper

Constructor & Destructor Documentation

◆ Algo748()

template<typename Real>

Optimist::ScalarRootFinder::Algo748< Real >::Algo748 ( )

inline

Class constructor for the Algorithm 748.

Member Function Documentation

◆ all_different()

template<typename Real>

bool Optimist::ScalarRootFinder::Algo748< Real >::all_different	(	Real	a,
		Real	b,
		Real	c,
		Real	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 Real>

bool Optimist::ScalarRootFinder::Algo748< Real >::bracketing ( FunctionWrapper 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\).
Parameters

[in] function Function wrapper.

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

◆ cubic_interpolation()

template<typename Real>

Real Optimist::ScalarRootFinder::Algo748< Real >::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 Real>

Real Optimist::ScalarRootFinder::Algo748< Real >::find_root_impl ( FunctionWrapper 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.
Parameters

[in] function Function wrapper.

Returns
The approximate root.

◆ name_impl()

template<typename Real>

std::string Optimist::ScalarRootFinder::Algo748< Real >::name_impl ( ) const

inline

Get the Algorithm 748 solver name.

Returns: The Algorithm 748 solver name.

◆ newton_quadratic()

template<typename Real>

Real Optimist::ScalarRootFinder::Algo748< Real >::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

◆ requires_first_derivative

template<typename Real>

bool Optimist::ScalarRootFinder::Algo748< Real >::requires_first_derivative {false}

staticconstexpr

◆ requires_function

template<typename Real>

bool Optimist::ScalarRootFinder::Algo748< Real >::requires_function {true}

staticconstexpr

◆ requires_second_derivative

template<typename Real>

bool Optimist::ScalarRootFinder::Algo748< Real >::requires_second_derivative {false}

staticconstexpr

Basic constants.

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

include/Optimist/ScalarRootFinder/Algo748.hh

Public Types

Public Member Functions

Static Public Attributes

Private Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ FirstDerivativeWrapper

◆ FunctionWrapper

◆ SecondDerivativeWrapper

Constructor & Destructor Documentation

◆ Algo748()

Member Function Documentation

◆ all_different()

◆ bracketing()

◆ cubic_interpolation()

◆ find_root_impl()

◆ name_impl()

◆ newton_quadratic()

Member Data Documentation

◆ requires_first_derivative

◆ requires_function

◆ requires_second_derivative