naginterfaces.library.roots.sys_​func_​aa_​rcomm

naginterfaces.library.roots.sys_func_aa_rcomm(irevcm, x, fvec, comm, atol=1.0536712127723509e-08, rtol=1.0536712127723509e-08, m=0, cndtol=0.0, astart=0)

sys_func_aa_rcomm is a comprehensive reverse communication function that 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 c05md

https://www.nag.com/numeric/nl/nagdoc_29.3/flhtml/c05/c05mdf.html

Parameters

irevcmint

On initial entry: must have the value $0$.

xfloat, ndarray, shape $\left(n\right)$, modified in place

On initial entry: an initial guess at the solution vector, ${\hat{x}}_0$.

On intermediate exit: contains the current point.

On final exit: the final estimate of the solution vector.

fvecfloat, ndarray, shape $\left(n\right)$, modified in place

On initial entry: need not be set.

On intermediate entry: if $irevcm=1$, $fvec$ must not be changed.

If $irevcm=2$, $fvec$ must be set to the values of the functions computed at the current point $x$, $f\left({\hat{x}}_i\right)$.

On final exit: the function values at the final point, $x$.

commdict, communication object, modified in place

Communication structure.

On initial entry: need not be set.

atolfloat, optional

On initial entry: the absolute convergence criterion; see $rtol$.

rtolfloat, optional

On initial entry: 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

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

cndtolfloat, optional

On initial entry: 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

On initial entry: the number of iterations by which to delay the start of Anderson acceleration.

Returns

irevcmint

On intermediate exit: specifies what action you must take before re-entering sys_func_aa_rcomm with $irevcm$ set to this value. The value of $irevcm$ should be interpreted as follows:

$irevcm=1$

Indicates the start of a new iteration. No action is required by you, but $x$ and $fvec$ are available for printing, and a limit on the number of iterations can be applied.

$irevcm=2$

Indicates that before re-entry to sys_func_aa_rcomm, $fvec$ must contain the function values $f\left({\hat{x}}_i\right)$.

On final exit: $irevcm=0$ and the algorithm has terminated.

Raises

NagValueError

(errno $1$)

On initial entry, $irevcm=⟨value⟩$.

Constraint: $irevcm=0$.

(errno $1$)

On intermediate entry, $irevcm=⟨value⟩$.

Constraint: $irevcm=1$ or $2$.

(errno $2$)

On entry, $n=⟨value⟩$.

Constraint: $n>0$.

(errno $3$)

On entry, $atol=⟨value⟩$.

Constraint: $atol\ge 0.0$.

(errno $4$)

On entry, $rtol=⟨value⟩$.

Constraint: $rtol\ge 0.0$.

(errno $5$)

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

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

(errno $6$)

On entry, $cndtol=⟨value⟩$.

Constraint: $cndtol\ge 0.0$.

(errno $7$)

On entry, $astart=⟨value⟩$.

Constraint: $astart\ge 0$.

(errno $8$)

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 $9$)

The iteration is not making good progress, as measured by the reduction in the norm of $f\left(x\right)$ in the last $⟨value⟩$ iterations.

(errno $10$)

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

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, then Anderson acceleration usually results in convergence in far fewer iterations (and, 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_rcomm() or sys_func_rcomm(), 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