nag_zero_nonlin_eqns_deriv_1 (c05ubc) : NAG Library, Mark 24

2 Specification

#include <nag.h>

#include <nagc05.h>

void

nag_zero_nonlin_eqns_deriv_1 (Integer n, double x[], double fvec[], double fjac[], Integer tdfjac,

void	(f)(Integer n, const double x[], double fvec[], double fjac[], Integer tdfjac, Integer userflag, Nag_User *comm),

double xtol, Nag_User *comm, NagError *fail)

3 Description

The system of equations is defined as:

f_{i} (x_{1}, x_{2}, \dots, x_{n}) = 0,   for ​ i = 1, 2, \dots, n .

nag_zero_nonlin_eqns_deriv_1 (c05ubc) is based upon the MINPACK routine HYBRJ1 (see Moré et al. (1980)). It chooses the correction at each step as a convex combination of the Newton and scaled gradient directions. Under reasonable conditions this guarantees global convergence for starting points far from the solution and a fast rate of convergence. The Jacobian is updated by the rank-1 method of Broyden. At the starting point the Jacobian is calculated, but it is not recalculated until the rank-1 method fails to produce satisfactory progress. For more details see Powell (1970).

5 Arguments

1: n – IntegerInput

On entry:

n

, the number of equations.

Constraint:

n > 0

2: x[n] – doubleInput/Output

On entry: an initial guess at the solution vector.

On exit: the final estimate of the solution vector.

3: fvec[n] – doubleOutput

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

4: fjac[

n \times tdfjac

] – doubleOutput

On exit: the orthogonal matrix

Q

produced by the

Q R

factorization of the final approximate Jacobian.

5: tdfjac – IntegerInput

On entry: the stride separating matrix column elements in the array fjac.

Constraint:

tdfjac \geq n

6: f – function, supplied by the userExternal Function

Depending upon the value of userflag, f must either return the values of the functions

f_{i}

at a point

x

or return the Jacobian at

x

The specification of f is:

void	f (Integer n, const double x[], double fvec[], double fjac[], Integer tdfjac, Integer userflag, Nag_User comm)

1: n – IntegerInput

On entry:

n

, the number of equations.

2: x[n] – const doubleInput

On entry: the components of the point

x

at which the functions or the Jacobian must be evaluated.

3: fvec[n] – doubleOutput

On exit: if

userflag = 1

on entry, fvec must contain the function values

f_{i} (x)

(unless userflag is set to a negative value by f).

userflag = 2

on entry, fvec must not be changed.

4: fjac[ $n \times tdfjac$ ] – doubleOutput

On exit: if

userflag = 2

on entry,

fjac [(i - 1) \times tdfjac + j - 1]

must contain the value of

\frac{\partial f_{i}}{\partial x_{j}}

at the point

x

, for

i = 1, 2, \dots, n

and

j = 1, 2, \dots, n

(unless userflag is set to a negative value by f).

userflag = 1

on entry, fjac must not be changed.

5: tdfjac – IntegerInput

On entry: the stride separating matrix column elements in the array fjac.

6: userflag – Integer *Input/Output

On entry:

userflag = 1

2

$userflag = 1$: fvec is to be updated.
$userflag = 2$: fjac is to be updated.

On exit: in general, userflag should not be reset by f. If, however, you wish to terminate execution (perhaps because some illegal point x has been reached), then userflag should be set to a negative integer. This value will be returned through

fail . errnum

7: comm – Nag_User *

Pointer to a structure of type Nag_User with the following member:

p – Pointer: On entry/exit: the pointer $comm \to p$ should be cast to the required type, e.g., struct user *s = (struct user *)comm → p, to obtain the original object's address with appropriate type. (See the argument comm below.)

7: xtol – doubleInput

On entry: the accuracy in x to which the solution is required.

Suggested value: the square root of the machine precision.

Constraint:

xtol \geq 0.0

8: comm – Nag_User *

Pointer to a structure of type Nag_User with the following member:

p – Pointer: On entry/exit: the pointer $comm \to p$ , of type Pointer, allows you to communicate information to and from f(). You must declare an object of the required type, e.g., a structure, and its address assigned to the pointer $comm \to p$ by means of a cast to Pointer in the calling program, e.g., comm.p = (Pointer)&s. The type pointer will be void * with a C compiler that defines void * and char * otherwise.

9: fail – NagError *Input/Output

The NAG error argument (see Section 3.6 in the Essential Introduction).

6 Error Indicators and Warnings

NE_2_INT_ARG_LT

On entry,

tdfjac = ⟨value⟩

while

n = ⟨value⟩

. These arguments must satisfy

tdfjac \geq n

NE_ALLOC_FAIL

Dynamic memory allocation failed.

NE_INT_ARG_LE

On entry,

n = ⟨value⟩

.
Constraint:

n > 0

NE_NO_IMPROVEMENT

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 (see Section 7). Otherwise, rerunning nag_zero_nonlin_eqns_deriv_1 (c05ubc) from a different starting point may avoid the region of difficulty.

NE_REAL_ARG_LT

On entry, xtol must not be less than 0.0:

xtol = ⟨value⟩

NE_TOO_MANY_FUNC_EVAL

There have been at least

100 \times (n + 1)

evaluations of f(). Consider restarting the calculation from the point held in x.

NE_USER_STOP

User requested termination, user flag value

= ⟨value⟩

NE_XTOL_TOO_SMALL

No further improvement in the solution is possible. xtol is too small:

xtol = ⟨value⟩

7 Accuracy

\hat{x}

is the true solution, nag_zero_nonlin_eqns_deriv_1 (c05ubc) tries to ensure that

‖x - \hat{x}‖ \leq xtol \times ‖\hat{x}‖ .

If this condition is satisfied with

xtol = 10^{- k}

, then the larger components of

x

have

k

significant decimal digits. There is a danger that the smaller components of

x

may have large relative errors, but the fast rate of convergence of nag_zero_nonlin_eqns_deriv_1 (c05ubc) usually avoids this possibility.

If xtol is less than machine precision and the above test is satisfied with the machine precision in place of xtol, then the function exits with NE_XTOL_TOO_SMALL.

Note: this convergence test is based purely on relative error, and may not indicate convergence if the solution is very close to the origin.

The test assumes that the functions and the Jacobian are coded consistently and that the functions are reasonably well behaved. If these conditions are not satisfied, then nag_zero_nonlin_eqns_deriv_1 (c05ubc) may incorrectly indicate convergence. The coding of the Jacobian can be checked using nag_check_derivs (c05zdc). If the Jacobian is coded correctly, then the validity of the answer can be checked by rerunning nag_zero_nonlin_eqns_deriv_1 (c05ubc) with a tighter tolerance.

9 Further Comments

The time required by nag_zero_nonlin_eqns_deriv_1 (c05ubc) to solve a given problem depends on

n

, the behaviour of the functions, the accuracy requested and the starting point. The number of arithmetic operations executed by nag_zero_nonlin_eqns_deriv_1 (c05ubc) is about

11.5 \times n^{2}

to process each evaluation of the functions and about

1.3 \times n^{3}

to process each evaluation of the Jacobian. Unless f can be evaluated quickly, the timing of nag_zero_nonlin_eqns_deriv_1 (c05ubc) will be strongly influenced by the time spent in f.

Ideally the problem should be scaled so that, at the solution, the function values are of comparable magnitude.

NAG Library Function Document

nag_zero_nonlin_eqns_deriv_1 (c05ubc)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG Library Function Documentnag_zero_nonlin_eqns_deriv_1 (c05ubc)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG Library Function Document

nag_zero_nonlin_eqns_deriv_1 (c05ubc)