hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox Chapter Introduction

C05 — Roots of One or More Transcendental Equations

Scope of the Chapter

This chapter is concerned with the calculation of zeros of continuous functions of one or more variables. The majority of problems considered are for real-valued functions of real variables, in which case complex equations must be expressed in terms of the equivalent larger system of real equations.

Background to the Problems

The chapter divides naturally into two parts.

A Single Equation

The first deals with the real zeros of a real function of a single variable f(x) f(x) .
There are three functions with simple calling sequences. The first assumes that you can determine an initial interval [a,b] [a,b]  within which the desired zero lies, (that is, where f(a) × f(b) < 0 f(a)×f(b)<0 ), and outside which all other zeros lie. The function then systematically subdivides the interval to produce a final interval containing the zero. This final interval has a length bounded by your specified error requirements; the end of the interval where the function has smallest magnitude is returned as the zero. This function is guaranteed to converge to a simple zero of the function. (Here we define a simple zero as a zero corresponding to a sign-change of the function; none of the available functions are capable of making any finer distinction.) However, as with the other functions described below, a non-simple zero might be determined and it is left to you to check for this. The algorithm used is due to Brent (1973).
The two other functions are both designed for the case where you are unable to specify an interval containing the simple zero. One starts from an initial point and performs a search for an interval containing a simple zero. If such an interval is computed then the method described above is used next to determine the zero accurately. The other method uses a ‘continuation’ method based on a secant iteration. A sequence of subproblems is solved; the first of these is trivial and the last is the actual problem of finding a zero of f(x) f(x) . The intermediate problems employ the solutions of earlier problems to provide initial guesses for the secant iterations used to calculate their solutions.
Three other functions are also supplied. They employ reverse communication and use the same core algorithms as the functions described above.
Finally, two functions are provided to return values of Lambert's WW function (sometimes known as the ‘product log’ or ‘Omega’ function), which is the inverse function of
f(w) = wew  for  wC;
f(w)=wew  for  wC;
that is, if Lambert's WW function W(x) = aW(x)=a for x,aCx,aC, then aa is a zero of the function F(w) = wewxF(w)=wew-x. One function uses the iterative method described in Barry et al. (1995) to return values from the real branches of WW (restricting x,aRx,aR). The second function enforces no such restriction, and uses the approach described in Corless et al. (1996).

Systems of Equations

The functions in the second part of this chapter are designed to solve a set of nonlinear equations in nn unknowns
fi(x) = 0 ,   i = 1,2,,n ,   x = (x1,x2,,xn) T ,
fi(x) = 0 ,   i= 1,2,,n ,   x= (x1,x2,,xn)T ,
(1)
where TT stands for transpose.
It is assumed that the functions are continuous and differentiable so that the matrix of first partial derivatives of the functions, the Jacobian matrix Jij(x) = ((fi)/(xj)) J ij (x)=( fi xj )  evaluated at the point xx, exists, though it may not be possible to calculate it directly.
The functions fi fi  must be independent, otherwise there will be an infinity of solutions and the methods will fail. However, even when the functions are independent the solutions may not be unique. Since the methods are iterative, an initial guess at the solution has to be supplied, and the solution located will usually be the one closest to this initial guess.

Recommendations on Choice and Use of Available Functions

Zeros of Functions of One Variable

The functions can be divided into two classes. There are three functions (nag_roots_contfn_interval_rcomm (c05av), nag_roots_contfn_cntin_rcomm (c05ax) and nag_roots_contfn_brent_rcomm (c05az)) all written in reverse communication form and three (nag_roots_contfn_brent_interval (c05au), nag_roots_contfn_cntin (c05aw) and nag_roots_contfn_brent (c05ay)) written in direct communication form. The direct communication functions are designed for inexperienced users and, in particular, for solving problems where the function f(x) f(x)  whose zero is to be calculated, can be coded as a user-supplied (sub)program. These functions find the zero by using the same core algorithms as the reverse communication functions. Experienced users are recommended to use the reverse communication functions directly as they permit you more control of the calculation. Indeed, if the zero-finding process is embedded in a much larger program then the reverse communication functions should always be used.
The recommendation as to which function should be used depends mainly on whether you can supply an interval [a,b] [a,b]  containing the zero; that is, where f(a) × f(b) < 0 f(a)×f(b)<0 . If the interval can be supplied, then nag_roots_contfn_brent (c05ay) (or, in reverse communication, nag_roots_contfn_brent_rcomm (c05az)) should be used, in general. This recommendation should be qualified in the case when the only interval which can be supplied is very long relative to your error requirements and you can also supply a good approximation to the zero. In this case nag_roots_contfn_cntin (c05aw) (or, in reverse communication, nag_roots_contfn_cntin_rcomm (c05ax)) may prove more efficient (though these latter functions will not provide the error bound available from nag_roots_contfn_brent_rcomm (c05az)).
If an interval containing the zero cannot be supplied then you must choose between nag_roots_contfn_brent_interval (c05au) (or, in reverse communication, nag_roots_contfn_interval_rcomm (c05av) followed by nag_roots_contfn_brent_rcomm (c05az)) and nag_roots_contfn_cntin (c05aw) (or, in reverse communication, nag_roots_contfn_cntin_rcomm (c05ax)). nag_roots_contfn_brent_interval (c05au) first determines an interval containing the zero, and then proceeds as in nag_roots_contfn_brent (c05ay); it is particularly recommended when you do not have a good initial approximation to the zero. If a good initial approximation to the zero is available then nag_roots_contfn_cntin (c05aw) is to be preferred. Since neither of these latter functions has guaranteed convergence to the zero, you are recommended to experiment with both in case of difficulty.

Solution of Sets of Nonlinear Equations

The solution of a set of nonlinear equations
fi(x1,x2,,xn) = 0,  i = 1,2,,n
fi(x1,x2,,xn)=0,  i=1,2,,n
(2)
can be regarded as a special case of the problem of finding a minimum of a sum of squares
m
s(x) = [fi(x1,x2,,xn)]2,  (mn).
i = 1
s ( x ) = i = 1 m [ f i ( x 1 , x 2 ,, x n ) ] 2 ,   ( m n ) .
(3)
So the functions in Chapter E04 are relevant as well as the special nonlinear equations functions.
The functions for solving a set of nonlinear equations can also be divided into classes. There are five functions (nag_roots_sys_func_easy (c05qb), nag_roots_sys_func_expert (c05qc), nag_roots_sparsys_func_expert (c05qs), nag_roots_sys_deriv_easy (c05rb) and nag_roots_sys_deriv_expert (c05rc)) all written in direct communication form and two (nag_roots_sys_func_rcomm (c05qd) and nag_roots_sys_deriv_rcomm (c05rd)) written in reverse communication form. The direct communication functions are designed for inexperienced users and, in particular, these functions require the fi fi  (and possibly their derivatives) to be calculated in user-supplied functions. These should be set up carefully so the Library functions can work as efficiently as possible. Experienced users are recommended to use the reverse communication functions as they permit you more control of the calculation. Indeed, if the zero-finding process is embedded in a much larger program then the reverse communication functions should always be used.
The main decision you have to make is whether to supply the derivatives (fi)/(xj) fi xj . It is advisable to do so if possible, since the results obtained by algorithms which use derivatives are generally more reliable than those obtained by algorithms which do not use derivatives.
nag_roots_sys_deriv_easy (c05rb), nag_roots_sys_deriv_expert (c05rc) and nag_roots_sys_deriv_rcomm (c05rd) require you to provide the derivatives, whilst nag_roots_sys_func_easy (c05qb), nag_roots_sys_func_expert (c05qc), nag_roots_sys_func_rcomm (c05qd) and nag_roots_sparsys_func_expert (c05qs) do not. nag_roots_sys_func_easy (c05qb), nag_roots_sparsys_func_expert (c05qs) and nag_roots_sys_deriv_easy (c05rb) are easy-to-use functions; greater flexibility may be obtained using nag_roots_sys_func_expert (c05qc) and nag_roots_sys_deriv_expert (c05rc) (or, in reverse communication, nag_roots_sys_func_rcomm (c05qd) and nag_roots_sys_deriv_rcomm (c05rd)), but these have longer parameter lists.
nag_roots_sparsys_func_expert (c05qs) is an easy-to-use function specially adapted for sparse problems, that is, problems where each function depends on a small subset of the nn variables so that the Jacobian matrix has many zeros. It employs sparse linear algebra methods and consequently is expected to take significantly less time to complete than the other functions, especially if nn is large.
nag_roots_sys_deriv_check (c05zd) is provided for use in conjunction with nag_roots_sys_deriv_easy (c05rb), nag_roots_sys_deriv_expert (c05rc) and nag_roots_sys_deriv_rcomm (c05rd) to check the user-supplied derivatives for consistency with the functions themselves. You are strongly advised to make use of this function whenever nag_roots_sys_deriv_easy (c05rb), nag_roots_sys_deriv_expert (c05rc) or nag_roots_sys_deriv_rcomm (c05rd) is used.
Firstly, the calculation of the functions and their derivatives should be ordered so that cancellation errors are avoided. This is particularly important in a function that uses these quantities to build up estimates of higher derivatives.
Secondly, scaling of the variables has a considerable effect on the efficiency of a function. The problem should be designed so that the elements of xx are of similar magnitude. The same comment applies to the functions, i.e., all the fi fi  should be of comparable size.
The accuracy is usually determined by the accuracy parameters of the functions, but the following points may be useful.
(i) Greater accuracy in the solution may be requested by choosing smaller input values for the accuracy parameters. However, if unreasonable accuracy is demanded, rounding errors may become important and cause a failure.
(ii) Some idea of the accuracies of the xi xi  may be obtained by monitoring the progress of the function to see how many figures remain unchanged during the last few iterations.
(iii) An approximation to the error in the solution xx is given by ee where ee is the solution to the set of linear equations
J(x)e = f(x)
J(x)e=-f(x)
where f(x) = (f1(x),f2(x),,fn(x)) T f(x) = (f1(x),f2(x),,fn(x))T .
Note that the QR QR  decomposition of JJ is available from nag_roots_sys_func_expert (c05qc) and nag_roots_sys_deriv_expert (c05rc) (or, in reverse communication, nag_roots_sys_func_rcomm (c05qd) and nag_roots_sys_deriv_rcomm (c05rd)) so that
Re = QTf
Re=-QTf
and QTf QTf  is also provided by these functions.
(iv) If the functions fi(x) fi(x)  are changed by small amounts εi ε i , for i = 1,2,,ni=1,2,,n, then the corresponding change in the solution xx is given approximately by σσ, where σσ is the solution of the set of linear equations
J(x)σ = ε .
J(x)σ = -ε .
Thus one can estimate the sensitivity of xx to any uncertainties in the specification of fi(x) fi(x) , for i = 1,2,,ni=1,2,,n. As noted above, the sophisticated functions nag_roots_sys_func_expert (c05qc) and nag_roots_sys_deriv_expert (c05rc) (or, in reverse communication, nag_roots_sys_func_rcomm (c05qd) and nag_roots_sys_deriv_rcomm (c05rd)) provide the QR QR  decomposition of JJ.

Values of Lambert's W function

If you require purely-real values of WW, these will be evaluated marginally more efficiently by nag_roots_lambertw_real (c05ba) than nag_roots_lambertw_complex (c05bb) owing to the differing iterative procedures used by each function.

Decision Trees

Tree 1: Functions of One Variable

Is reverse communication required? _
yes
Is there available an interval [a,b] [a,b]  containing a simple zero, and no others? _
yes
nag_roots_contfn_brent_rcomm (c05az)
| no
|
| Is a good approximation to the zero available? _
yes
nag_roots_contfn_cntin_rcomm (c05ax)
| no
|
| nag_roots_contfn_interval_rcomm (c05av) followed by nag_roots_contfn_brent_rcomm (c05az)
no
|
Do you wish to compute the values of Lambert's WW function? _
yes
do you require values from only the real branches? _
yes
nag_roots_lambertw_real (c05ba)
| no
|
| nag_roots_lambertw_complex (c05bb)
no
|
Is there available an interval [a,b] [a,b]  containing a simple zero, and no others? _
yes
nag_roots_contfn_brent (c05ay)
no
|
Is a good approximation to the zero available? _
yes
nag_roots_contfn_cntin (c05aw)
no
|
nag_roots_contfn_brent_interval (c05au)

Tree 2: Functions of several variables

Is the Jacobian matrix sparse? _
yes
nag_roots_sparsys_func_expert (c05qs)
no
|
Is reverse communication required? _
yes
Is the Jacobian matrix available? _
yes
nag_roots_sys_deriv_rcomm (c05rd) and nag_roots_sys_deriv_check (c05zd)
| no
|
| nag_roots_sys_func_rcomm (c05qd)
no
|
Is the Jacobian matrix available? _
yes
Is flexibility required? _
yes
nag_roots_sys_deriv_expert (c05rc) and nag_roots_sys_deriv_check (c05zd)
| no
|
| nag_roots_sys_deriv_easy (c05rb) and nag_roots_sys_deriv_check (c05zd)
no
|
Is flexibility required? _
yes
nag_roots_sys_func_expert (c05qc)
no
|
nag_roots_sys_func_easy (c05qb)

Functionality Index

Lambert's W function, 
    complex values nag_roots_lambertw_complex (c05bb)
    real values nag_roots_lambertw_real (c05ba)
Zeros of functions of one variable, 
    direct communication, 
        binary search followed by Brent algorithm nag_roots_contfn_brent_interval (c05au)
        Brent algorithm nag_roots_contfn_brent (c05ay)
        continuation method nag_roots_contfn_cntin (c05aw)
    reverse communication, 
        binary search nag_roots_contfn_interval_rcomm (c05av)
        Brent algorithm nag_roots_contfn_brent_rcomm (c05az)
        continuation method nag_roots_contfn_cntin_rcomm (c05ax)
Zeros of functions of several variables, 
    checking function, 
        checks user-supplied Jacobian nag_roots_sys_deriv_check (c05zd)
    direct communication, 
        easy-to-use, 
            derivatives required nag_roots_sys_deriv_easy (c05rb)
            no derivatives required nag_roots_sys_func_easy (c05qb)
            no derivatives required, sparse nag_roots_sparsys_func_expert (c05qs)
        sophisticated, 
            derivatives required nag_roots_sys_deriv_expert (c05rc)
            no derivatives required nag_roots_sys_func_expert (c05qc)
    reverse communication, 
        sophisticated, 
            derivatives required nag_roots_sys_deriv_rcomm (c05rd)
            no derivatives required nag_roots_sys_func_rcomm (c05qd)

References

Barry D J, Culligan–Hensley P J, and Barry S J (1995) Real values of the WW-function ACM Trans. Math. Software 21(2) 161–171
Brent R P (1973) Algorithms for Minimization Without Derivatives Prentice–Hall
Corless R M, Gonnet G H, Hare D E G, Jeffrey D J and Knuth D E (1996) On the Lambert WW function Advances in Comp. Math. 3 329–359
Gill P E and Murray W (1976) Algorithms for the solution of the nonlinear least squares problem Report NAC 71 National Physical Laboratory
Moré J J, Garbow B S and Hillstrom K E (1980) User guide for MINPACK-1 Technical Report ANL-80-74 Argonne National Laboratory
Ortega J M and Rheinboldt W C (1970) Iterative Solution of Nonlinear Equations in Several Variables Academic Press
Rabinowitz P (1970) Numerical Methods for Nonlinear Algebraic Equations Gordon and Breach

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013