# root_finders#

Functions for root-finding of algebraic univariate functions using various algorithms. In this submodule, various methods can be selected to:

$\text{find }x\text{, such that: } f(x)=0$

The methods that can be selected here are iterative methods to find approximate solutions to the above problem, starting from an initial guess $$x_{0}$$, for which $$f_{0}=f(x_{0})$$. The various methods implement different iterative algorithms to compute $$x_{i}\rightarrow x_{i+1}$$. That is, they (attempt to) compute an improved guess of the root at iteration $$i+1$$ from the guess at iteration $$i$$, and continue iterating until convergence has been reached.

Depending on the method that is use, the root-finder may need several initial guesses, or have a formulation for one or more derivatives of the function $$f(x)$$. If the required information is not available when performing the root-finding, and exception will be thrown.

There are several convergence criteria that can be defined for this

• When an absolute tolerance $$\epsilon_{a}$$ is met, such that $$|x_{i}-x_{i-1}|<\epsilon_{a}$$

• When a relative tolerance $$\epsilon_{r}$$ is met, such that $$|(x_{i}-x_{i-1})/x_{i}|<\epsilon_{r}$$

• When the root function gets within $$\epsilon_{f}$$ of the true root $$|f(x_{i}|<\epsilon_{f}$$)

• When the number if iterations exceeds some threshold $$N$$, such that $$i=N$$

The root finder algorithm continues until as single one of the required convergence criteria is met.

When meeting the convergence criterion on number of iterations $$N$$, a user can choose to deal with this in one of several manners (see below).

## Functions#

 bisection(relative_variable_tolerance, ...) Function to create settings for a bisection root-finder. newton_raphson(relative_variable_tolerance, ...) Function to create settings for a Newton-Raphson root-finder. secant(relative_variable_tolerance, ...) Function to create settings for a secant method root-finder. halley(relative_variable_tolerance, ...) Function to create settings for a Halley root-finder.
bisection(relative_variable_tolerance: float = nan, absolute_variable_tolerance: float = nan, root_function_tolerance: float = nan, maximum_iteration: int = 1000, maximum_iteration_handling: tudatpy.kernel.math.root_finders.MaximumIterationHandling = <MaximumIterationHandling.throw_exception: 2>) #

Function to create settings for a bisection root-finder.

Function to create settings for a bisection root finder. This root finder approximates the root by initializing with two initial guesses $$x_{\downarrow,0}$$ and $$x_{\uparrow,0}$$, for which it is required that $$f(x_{\downarrow,0}) < 0$$ and $$f(x_{\uparrow,0}) > 0$$. At each iteration $$i$$, the current guess of the root $$x_{i}$$ is:

$\begin{split}x_{i}=\begin{cases} x_{\downarrow,i}, & |f(x_{\downarrow,i})|<|f(x_{\uparrow,i})|\\ x_{\uparrow,i}, & |f(x_{\downarrow,i})|\ge|f(x_{\uparrow,i})| \end{cases}\end{split}$

The midpoint $$x_{m,i}$$ of $$x_{\downarrow,i}$$ and $$x_{\uparrow,i}$$ is then computed from $$x_{m,i}=(x_{\downarrow,i}-x_{\uparrow,i})/2$$. Depending on the sign of $$f(x_{m,i})$$, it then replaces either $$x_{\downarrow,i}$$ or $$x_{\uparrow,i}$$ (depending on whether its sign matches $$f(x_{\downarrow,i})$$ for iteration $$i+1$$ and $$f(x_{\uparrow,i})$$), while the other point from iteration $$i$$ is retained.

Although slow, the algorithm is ensured to converge to a root, if the two initial guesses indeed have opposite signs (if not, an exception is thrown).

Parameters:
• relative_variable_tolerance (float, default = nan) – Relative tolerance $$\epsilon_{r}$$ (setting not used if nan)

• absolute_variable_tolerance (float, default = nan) – Relative absolute $$\epsilon_{a}$$ (setting not used if nan)

• root_function_tolerance (float, default = nan) – Root function tolerance $$\epsilon_{f}$$ (setting not used if nan)

• maximum_iteration (int, default = 1000) – Maximum number of iterations $$N$$

• maximum_iteration_handling (MaximumIterationHandling, default = throw_exception) – Algorithm behaviour if maximum number of iterations $$N$$ is reache

Returns:

Bisection root-finding settings object

Return type:

RootFinderSettings

newton_raphson(relative_variable_tolerance: float = nan, absolute_variable_tolerance: float = nan, root_function_tolerance: float = nan, maximum_iteration: int = 1000, maximum_iteration_handling: tudatpy.kernel.math.root_finders.MaximumIterationHandling = <MaximumIterationHandling.throw_exception: 2>) #

Function to create settings for a Newton-Raphson root-finder.

Function to create settings for a bisection root finder. This root finder approximates the root by initializing with a single initial guesses $$x_{0}$$ and requires an analytical formulation for $$f(x)$$ and $$f'(x)=\frac{d}{dx}f(x)$$. The algorithm uses the following equation to iterate:

$x_{i+1}=x_{i}-\frac{f(x_{i})}{f'(x_{i})}$
Parameters:
• relative_variable_tolerance (float, default = nan) – Relative tolerance $$\epsilon_{r}$$ (setting not used if nan)

• absolute_variable_tolerance (float, default = nan) – Relative absolute $$\epsilon_{a}$$ (setting not used if nan)

• root_function_tolerance (float, default = nan) – Root function tolerance $$\epsilon_{f}$$ (setting not used if nan)

• maximum_iteration (int, default = 1000) – Maximum number of iterations $$N$$

• maximum_iteration_handling (MaximumIterationHandling, default = throw_exception) – Algorithm behaviour if maximum number of iterations $$N$$ is reache

Returns:

Newton-Raphson root-finding settings object

Return type:

RootFinderSettings

secant(relative_variable_tolerance: float = nan, absolute_variable_tolerance: float = nan, root_function_tolerance: float = nan, maximum_iteration: int = 1000, maximum_iteration_handling: tudatpy.kernel.math.root_finders.MaximumIterationHandling = <MaximumIterationHandling.throw_exception: 2>) #

Function to create settings for a secant method root-finder.

Function to create settings for a root finder using the secant method. This root finder approximates the root by initializing with two initial guesses $$x_{0}$$ and $$x_{1}$$. The algorithm uses the following equation to iterate:

$x_{i+1}=x_{i}-f(x_{i})\frac{x_{i}-x_{i-1}}{f(x_{i})-f(x_{i-1})}$
Parameters:
• relative_variable_tolerance (float, default = nan) – Relative tolerance $$\epsilon_{r}$$ (setting not used if nan)

• absolute_variable_tolerance (float, default = nan) – Relative absolute $$\epsilon_{a}$$ (setting not used if nan)

• root_function_tolerance (float, default = nan) – Root function tolerance $$\epsilon_{f}$$ (setting not used if nan)

• maximum_iteration (int, default = 1000) – Maximum number of iterations $$N$$

• maximum_iteration_handling (MaximumIterationHandling, default = throw_exception) – Algorithm behaviour if maximum number of iterations $$N$$ is reache

Returns:

Secant root-finding settings object

Return type:

RootFinderSettings

halley(relative_variable_tolerance: float = nan, absolute_variable_tolerance: float = nan, root_function_tolerance: float = nan, maximum_iteration: int = 1000, maximum_iteration_handling: tudatpy.kernel.math.root_finders.MaximumIterationHandling = <MaximumIterationHandling.throw_exception: 2>) #

Function to create settings for a Halley root-finder.

Function to create settings for a Halley root finder. This root finder approximates the root by initializing with a single initial guesses $$x_{0}$$ and requires an analytical formulation for $$f(x)$$, $$f'(x)=\frac{d}{dx}f(x)$$ and $$f''(x)=\frac{d^{2}}{dx^{2}}f(x)$$. The algorithm uses the following equation to iterate:

$x_{i+1}=x_{i}-\frac{2f(x_{i})f'(x_{i})}{2(f'(x_{i}))^{2}-f(x_{i})f''(x_{i})}$
Parameters:
• relative_variable_tolerance (float, default = nan) – Relative tolerance $$\epsilon_{r}$$ (setting not used if nan)

• absolute_variable_tolerance (float, default = nan) – Relative absolute $$\epsilon_{a}$$ (setting not used if nan)

• root_function_tolerance (float, default = nan) – Root function tolerance $$\epsilon_{f}$$ (setting not used if nan)

• maximum_iteration (int, default = 1000) – Maximum number of iterations $$N$$

• maximum_iteration_handling (MaximumIterationHandling, default = throw_exception) – Algorithm behaviour if maximum number of iterations $$N$$ is reache

Returns:

Halley root-finding settings object

Return type:

RootFinderSettings

## Enumerations#

 MaximumIterationHandling Enumeration of types of behaviour to be used when the convergence criterion on maximum number of iterations is reached.
class MaximumIterationHandling#

Enumeration of types of behaviour to be used when the convergence criterion on maximum number of iterations is reached.

Members:

accept_result :

The program will accept the root at the final iteration, without any additional output

accept_result_with_warning :

The program will accept the root at the final iteration, but will print a warning to the terminal that the root finder may not have converged

throw_exception :

The program will not accept the root at the final iteration, and will throw an exception

property name#

## Classes#

 RootFinderSettings Class to define settings for a root finder.
class RootFinderSettings#

Class to define settings for a root finder.