D05 Chapter Introduction : NAG Library, Mark 26

This chapter is concerned with the numerical solution of integral equations. Provision will be made for most of the standard types of equation (see Section 2). The following are, however, specifically excluded:

(a)	Equations arising in the solution of partial differential equations by integral equation methods. In cases where the prime purpose of an algorithm is the solution of a partial differential equation it will normally be included in Chapter D03.
(b)	Calculation of inverse integral transforms. This problem falls within the scope of Chapter C06.

Background to the Problems

2.1

Introduction

Any functional equation in which the unknown function appears under the sign of integration is called an integral equation. Integral equations arise in a great many branches of science; for example, in potential theory, acoustics, elasticity, fluid mechanics, radiative transfer, theory of population, etc. In many instances the integral equation originates from the conversion of a boundary value problem or an initial value problem associated with a partial or an ordinary differential equation, but many problems lead directly to integral equations and cannot be formulated in terms of differential equations.

Integral equations are of many types; here we attempt to indicate some of the main distinguishing features with particular regard to the use and construction of algorithms.

2.2

Classification of Integral Equations

In the classical theory of integral equations one distinguishes between Fredholm equations and Volterra equations. In a Fredholm equation the region of integration is fixed, whereas in a Volterra equation the region is variable. Thus, the equation

c y (t) = f (t) + λ \int_{a}^{b} K (t, s, y (s)) d s, a \leq t \leq b

(1)

is an example of Fredholm equation, and the equation

c y (t) = f (t) + λ \int_{a}^{t} K (t, s, y (s)) d s, a \leq t

(2)

is an example of a Volterra equation.

Here the forcing function

f (t)

and the kernel function

K (t, s, y (s))

are prescribed, while

y (t)

is the unknown function to be determined. (More generally the integration and the domain of definition of the functions may extend to more than one dimension.) The parameter

λ

is often omitted; it is, however, of importance in certain theoretical investigations (e.g., stability) and in the eigenvalue problem discussed below.

If in (1) or (2),

c = 0

, the integral equation is said to be of the first kind. If

c = 1

, the equation is said to be of the second kind.

Equations (1) and (2) are linear if the kernel

K (t, s, y (s)) = k (t, s) y (s)

, otherwise they are nonlinear.

Note: in a linear integral equation,

k (t, s)

is usually referred to as the kernel. We adopt this convention throughout.

These two types of equations are broadly analogous to problems of initial- and boundary value type for an ordinary differential equation (ODE); thus the Volterra equation, characterised by a variable upper limit of integration, is amenable to solution by methods of marching type whilst most methods for treating Fredholm equations lead ultimately to the solution of an approximating system of simultaneous algebraic equations. For comprehensive discussion of numerical methods see Atkinson (1976), Baker (1977), Brunner and van der Houwen (1986) and Delves and Walsh (1974). In what follows, the term ‘integral equation’ is used in its general sense, and the type is distinguished when appropriate.

2.3

Structure of Kernel

When considering numerical methods for integral equations, particular attention should be paid to the character of the kernel, which is usually the main factor governing the choice of an appropriate quadrature formula or system of approximating functions. Various commonly occurring types of singularity call for individual treatment.

Likewise provision can be made for cases of symmetry, periodicity or other special structure, where the solution may have special properties and/or economies may be effected in the solution process. We note in particular the following cases to which we shall often have occasion to refer in the description of individual algorithms.

(a)

A linear integral equation with a kernel

k (t, s) = k (s, t)

is said to be symmetric. This property plays a key role in the theory of Fredholm integral equations.

(b)

k (t, s) = k (a + b - t, a + b - s)

in a linear integral equation, the kernel is called centro-symmetric.

(c)

If in Equations (1) or (2) the kernel has the form

K (t, s, y (s)) = k (t - s) g (s, y (s))

, the equation is called a convolution integral equation; in the linear case

g (s, y (s)) = y (s)

(d)

If the kernel in (1) has the form

\begin{array}{l} K (t, s, y (s)) = K_{1} (t, s, y (s)), a \leq s \leq t, \\ K (t, s, y (s)) = K_{2} (t, s, y (s)), t < s \leq b, \end{array}

where the functions

K_{1}

and

K_{2}

are well behaved, whilst

K

or its

s

-derivative is possibly discontinuous, may be described as discontinuous or of ‘split’ type; in the linear case

K (t, s, y (s)) = k (t, s) y (s)

and consequently

K_{1} = k_{1} y

and

K_{2} = k_{2} y

. Examples are the commonly occurring kernels of the type

k (|t - s|)

and the Green's functions (influence functions) which arise in the conversion of ODE boundary value problems to integral equations. It is also of interest to note that the Volterra equation (2) may be conceived as a Fredholm equation with kernel of split type, with

K_{2} (t, s, y (s)) \equiv 0

; consequently methods designed for the solution of Fredholm equations with split kernels are also applicable to Volterra equations.

2.4

Singular and Weakly Singular Equations

An integral equation may be called singular if either

(a)	its kernel contains a singularity, or
(b)	the range of integration is infinite,

and it is said to be weakly singular if the kernel becomes infinite at

s = t

Sometimes a solution can be effected by a simple adaptation of a method applicable to a nonsingular equation: for example, an infinite range may be truncated at a suitably chosen point. In other cases, however, theoretical considerations will dictate the need for special methods and algorithms. Examples are:

(i)	Integral equations with singular kernels of Cauchy type;
(ii)	Equations of Wiener–Hopf type;
(iii)	Various dual integral equations arising in the solution of boundary value problems of mathematical physics;
(iv)	The well-known Abel integral equation, an equation of Volterra type, whose kernel contains an inverse square root singularity at $s = t$ .

Problems of inversion of integral transforms also fall under this heading but, as already remarked, they lie outside the scope of this chapter.

2.5

Fredholm Integral Equations

2.5.1

Eigenvalue problem

Closely connected with the linear Fredholm integral equation of the second kind is the eigenvalue problem represented by the homogeneous equation

y (t) - λ \int_{a}^{b} k (t, s) y (s) d s = 0, a \leq t \leq b .

(3)

λ

is chosen arbitrarily this equation in general possesses only the trivial solution

y (t) = 0

. However, for a certain critical set of values of

λ

, the characteristic values or eigenvalues (the latter term is sometimes reserved for the reciprocals

μ = 1 / λ

), there exist nontrivial solutions

y (t)

, termed characteristic functions or eigenfunctions, which are of fundamental importance in many investigations. The analogy with the eigenproblem of linear algebra is readily apparent, and indeed most methods of solution of equation (3) entail reduction to an approximately equivalent algebraic problem

(K - μ I) y = 0 .

(4)

2.5.2

Equations of the first kind

The Fredholm integral equation of the first kind

\int_{a}^{b} k (t, s) y (s) d s = f (t), a \leq t \leq b,

(5)

belong to the class of ‘ill-posed’ problems; even supposing that a solution corresponding to the prescribed

f (t)

exists, a slight perturbation of

f (t)

may give rise to an arbitrarily large variation in the solution

y (t)

. Hence the equation may be closely satisfied by a function bearing little resemblance to the ‘true’ solution. The difficulty associated with this instability is aggravated by the fact that in practice the specification of

f (t)

is usually inexact.

Nevertheless a great many physical problems (e.g., in radiography, spectroscopy, stereology, chemical analysis) are appropriately formulated in terms of integral equations of the first kind, and useful and meaningful ‘solutions’ can be obtained with the aid of suitable stabilizing procedures. See Chapters 12 and 13 of Delves and Walsh (1974) for further discussion and references.

2.5.3

Equations of the second kind

Consider the nonlinear Fredholm equation of the second kind

y (t) = f (t) + \int_{a}^{b} K (t, s, y (s)) d s, a \leq t \leq b .

(6)

The numerical solution of equation (6) is usually accomplished either by simple iteration or by a more sophisticated iterative scheme based on Newton's method; in the latter case it is necessary to solve a sequence of linear integral equations. Convergence may be demonstrated subject to suitable conditions of Lipschitz continuity of the functions

K

with respect to the parameter

y

Examples of Fredholm type (for which the provision of algorithms is contemplated) are:

(a)

the Uryson equation

u (t) - \int_{0}^{1} F (t, s, u (s)) d s = 0, 0 \leq t \leq 1,

(7)

(b)

the Hammerstein equation

u (t) - \int_{0}^{1} k (t, s) g (s, u (s)) d s = 0, 0 \leq t \leq 1,

(8)

where

F

and

g

are arbitrary functions.

2.6

Volterra Integral Equations

2.6.1

Equations of the first kind

Consider the Volterra integral equation of the first kind

\int_{a}^{t} k (t, s) y (s) d s = f (t), a \leq t .

(9)

Clearly it is necessary that

f (a) = 0

; otherwise no solution to (9) can exist. The following types of Volterra integral equations of the first kind occur in real life problems:

equations with unbounded kernel at $s = t$ ,
equations with sufficiently smooth kernel.

These types belong also to the class of ‘ill-posed’ problems. However, the instability is appreciably less severe in the equations with unbounded kernel. In general, a nonsingular Volterra equation of the first kind presents less computational difficulty than the Fredholm equation (5) with a smooth kernel.

A Volterra equation of the first kind may, under suitable conditions, be converted by differentiation to one of the second kind or by integration by parts to an equation of the second kind for the integral of the wanted function.

2.6.2

Equations of the second kind

A very general Volterra equation of the second kind is given by

y (t) = f (t) + \int_{a}^{t} K (t, s, y (s)) d s, a \leq t .

(10)

The resemblance of Volterra equations to ODEs suggests that the underlying methods for ODE problems can be applied to Volterra equations. Indeed this turns out to be the case. The main advantages of implementing these methods are their well-developed theoretical background, i.e., convergence and stability; see Brunner and van der Houwen (1986) and Wolkenfelt (1982).

Many Volterra integral equations arising in real life problems have a convolution kernel (see Section 2.3(c)); see Brunner and van der Houwen (1986) for references. However, a subclass of these equations which have kernels of the form

k (t - s) = \sum_{j = 0}^{M} λ_{j} {(t - s)}^{j},

(11)

where

\{λ_{j}\}

are real, can be converted into a system of linear or nonlinear ODEs; see Brunner and van der Houwen (1986).

For more information on the theoretical and the numerical treatment of integral equations we refer you to Atkinson (1976), Baker (1977), Brunner and van der Houwen (1986), Cochran (1972) and Delves and Walsh (1974).

Recommendations on Choice and Use of Available Routines

The choice of routine will depend first of all upon the type of integral equation to be solved.

3.1

Fredholm Equations of the Second Kind

(a)

Linear equations

d05aaf is applicable to an equation with a discontinuous or ‘split’ kernel as defined in Section 2.3(d). Here, however, both the functions

k_{1}

and

k_{2}

are required to be defined (and well-behaved) throughout the square

a \leq s

t \leq b

d05abf is applicable to an equation with a smooth kernel. Note that d05aaf may also be applied to this case, by setting

k_{1} = k_{2} = k

, but d05abf is more efficient.

3.2

Volterra Equations of the Second Kind

(a)

Linear equations

d05aaf may be used to solve a Volterra equation by defining

k_{2}

(or

k_{1}

) to be identically zero. (See also (b).)

(b)

Nonlinear equations

d05baf is applicable to a nonlinear convolution Volterra integral equation of the second kind. The kernel function has the form

K (t, s, y (s)) = k (t - s) g (s, y (s)) .

The underlying methods used in the routine are the reducible linear multistep methods. You have a choice of variety of these methods. This routine can also be used for linear

g

d05bdf is applicable to a nonlinear convolution equation having a weakly-singular kernel (Abel). The kernel function has the form

K (t, s, y (s)) = \frac{k (t - s)}{\sqrt{t - s}} g (s, y (s)) .

The underlying methods used in the routine are the fractional linear multistep methods based on Backward Difference Formula (BDF, see Section 3.1 in the D02 Chapter Introduction) methods. This routine can also be used for linear

g

3.3

Volterra Equations of the First Kind

3.4

Utility Routines

d05bwf generates the weights associated with Adams' and BDF linear multistep methods. These weights can be used for the solution of nonsingular Volterra integral and integro-differential equations of general type.

d05byf generates the weights associated with BDF linear multistep methods. These weights can be used for the solution of weakly-singular Volterra (Abel) integral equations of general type.

3.5

User-supplied Routines

Many of the routines in this chapter require you to supply procedures defining the kernels and other given functions in the equations. It is important to test these independently before using them in conjunction with NAG Library routines.

Functionality Index

Fredholm equation of second kind,

linear,

nonsingular discontinuous or ‘split’ kernel

d05aaf

nonsingular smooth kernel

d05abf

Volterra equation of first kind,

nonlinear,

weakly-singular,

convolution equation (Abel):

d05bef

Volterra equation of second kind,

nonlinear,

nonsingular,

convolution equation

d05baf

weakly-singular,

convolution equation (Abel):

d05bdf

Weight generating routines,

weights for general solution of Volterra equations

d05bwf

weights for general solution of Volterra equations with weakly-singular kernel

d05byf

NAG Library Chapter Introduction

D05 (inteq)
Integral Equations

▸▿ Contents

1

Scope of the Chapter

2

Background to the Problems

2.1

Introduction

2.2

Classification of Integral Equations

2.3

Structure of Kernel

2.4

Singular and Weakly Singular Equations

2.5

Fredholm Integral Equations

2.5.1

Eigenvalue problem

2.5.2

Equations of the first kind

2.5.3

Equations of the second kind

2.6

Volterra Integral Equations

2.6.1

Equations of the first kind

2.6.2

Equations of the second kind

3

Recommendations on Choice and Use of Available Routines

3.1

Fredholm Equations of the Second Kind

3.2

Volterra Equations of the Second Kind

3.3

Volterra Equations of the First Kind

3.4

Utility Routines

3.5

User-supplied Routines

4

Functionality Index

5

Auxiliary Routines Associated with Library Routine Arguments

6

Routines Withdrawn or Scheduled for Withdrawal

7

References

NAG Library Chapter Introduction

D05 (inteq)Integral Equations

▸▿ Contents

1 Scope of the Chapter

2 Background to the Problems

2.1 Introduction

2.2 Classification of Integral Equations

2.3 Structure of Kernel

2.4 Singular and Weakly Singular Equations

2.5 Fredholm Integral Equations

2.5.1 Eigenvalue problem

2.5.2 Equations of the first kind

2.5.3 Equations of the second kind

2.6 Volterra Integral Equations

2.6.1 Equations of the first kind

2.6.2 Equations of the second kind

3 Recommendations on Choice and Use of Available Routines

3.1 Fredholm Equations of the Second Kind

3.2 Volterra Equations of the Second Kind

3.3 Volterra Equations of the First Kind

3.4 Utility Routines

3.5 User-supplied Routines

4 Functionality Index

5 Auxiliary Routines Associated with Library Routine Arguments

6 Routines Withdrawn or Scheduled for Withdrawal

7 References