naginterfaces.library.roots.sys_​func_​aa

naginterfaces.library.roots.sys_func_aa(fcn, x, atol=1.0536712127723509e-08, rtol=1.0536712127723509e-08, m=0, cndtol=0.0, astart=0, data=None)

sys_func_aa finds a solution of a system of nonlinear equations by fixed-point iteration using Anderson acceleration.

For full information please refer to the NAG Library document for c05mb

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/c05/c05mbf.html

Parameters

fcncallable fvec = fcn(x, data=None)

$fcn$ must return the values of the functions $f_k$ at a point $x$.

Parameters

xfloat, ndarray, shape $\left(n\right)$

The components of the point $x$ at which the functions must be evaluated.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns

fvecfloat, array-like, shape $\left(n\right)$

The function values $f_k\left(x\right)$.

xfloat, array-like, shape $\left(n\right)$

An initial guess at the solution vector, ${\hat{x}}_0$.

atolfloat, optional

The absolute convergence criterion; see $rtol$.

rtolfloat, optional

The relative convergence criterion. At each iteration $\parallel f\left({\hat{x}}_i\right)\parallel$ is computed. The iteration is deemed to have converged if $\parallel f\left({\hat{x}}_i\right)\parallel \le max(atol,rtol\times \parallel f\left({\hat{x}}_0\right)\parallel )$.

mint, optional

$m$, the number of previous iterates to use in Anderson acceleration. If $m=0$, Anderson acceleration is not used.

cndtolfloat, optional

The maximum allowable condition number for the triangular $QR$ factor generated during Anderson acceleration. At each iteration, if the condition number exceeds $cndtol$, columns are deleted until it is sufficiently small.

If $cndtol=0.0$, no condition number tests are performed.

astartint, optional

The number of iterations by which to delay the start of Anderson acceleration.

dataarbitrary, optional

User-communication data for callback functions.

Returns

xfloat, ndarray, shape $\left(n\right)$

The final estimate of the solution vector.

fvecfloat, ndarray, shape $\left(n\right)$

The function values at the final point, $x$.

Raises

NagValueError

(errno $1$)

On entry, $n=⟨value⟩$.

Constraint: $n>0$.

(errno $2$)

On entry, $atol=⟨value⟩$.

Constraint: $atol\ge 0.0$.

(errno $3$)

On entry, $rtol=⟨value⟩$.

Constraint: $rtol\ge 0.0$.

(errno $4$)

On entry, $m=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $0\le m\le n$.

(errno $5$)

On entry, $cndtol=⟨value⟩$.

Constraint: $cndtol\ge 0.0$.

(errno $6$)

On entry, $astart=⟨value⟩$.

Constraint: $astart\ge 0$.

(errno $7$)

An error occurred in evaluating the $QR$ decomposition during Anderson acceleration. This may be due to slow convergence of the iteration. Try setting the value of $cndtol$. If condition number tests are already performed, try decreasing $cndtol$.

(errno $11$)

The iteration has diverged and subsequent iterates are too large to be computed in floating-point arithmetic.

Warns

NagAlgorithmicWarning

(errno $8$)

The iteration is not making good progress. This failure exit may indicate that the system does not have a zero, or that the solution is very close to the origin. Rerunning sys_func_aa from a different starting point may avoid the region of difficulty.

(errno $9$)

There have been at least $200\times (n+1)$ calls to $fcn$. Consider restarting the calculation from the point held in $x$.

NagCallbackTerminateWarning

(errno $10$)

Termination requested in $fcn$.

Notes

The system of equations is defined as:

$$f_k(x_1,x_2,\dots ,x_n)=0\text{,}k=1,2,\dots ,n\text{.}$$

This homogeneous system can readily be reformulated as

$$g\left(x\right)=x\text{,}x\in R^n\text{.}$$

A standard fixed-point iteration approach is to start with an approximate solution ${\hat{x}}_0$ and repeatedly apply the function $g$ until possible convergence; i.e., ${\hat{x}}_{i+1}=g\left({\hat{x}}_i\right)$, until $\parallel {\hat{x}}_{i+1}-{\hat{x}}_i\parallel <\text{tol}$. Anderson acceleration uses up to $m$ previous values of $\hat{x}$ to obtain an improved estimate ${\hat{x}}_{i+1}$. If a standard fixed-point iteration converges, Anderson acceleration usually results in convergence in far fewer iterations (therefore, using far fewer function evaluations).

Full details of Anderson acceleration are provided in Anderson (1965). In summary, the previous $m$ iterates are combined to form a succession of least squares problems. These are solved using a $QR$ decomposition, which is updated at each iteration.

You are free to choose any value for $m$, provided $m\le n$. A typical choice is $m=4$.

Anderson acceleration is particularly useful if evaluating $g\left(x\right)$ is very expensive, in which case functions such as sys_deriv_easy() or sys_func_easy(), which require the Jacobian or its approximation, may perform poorly.

References

Anderson, D G, 1965, Iterative Procedures for Nonlinear Integral Equations, J. Assoc. Comput. Mach. (12), 547–560