root_finders#
Functions for root-finding of algebraic univariate functions using various algorithms. In this submodule, various methods can be selected to:
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#
|
Function to create settings for a bisection root-finder. |
|
Function to create settings for a Newton-Raphson root-finder. |
|
Function to create settings for a secant method root-finder. |
|
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>) tudatpy.kernel.math.root_finders.RootFinderSettings#
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:
- 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>) tudatpy.kernel.math.root_finders.RootFinderSettings#
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:
- 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>) tudatpy.kernel.math.root_finders.RootFinderSettings#
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:
- 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>) tudatpy.kernel.math.root_finders.RootFinderSettings#
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:
Enumerations#
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#
Class to define settings for a root finder. |
- class RootFinderSettings#
Class to define settings for a root finder.