Integral equations, numerical methods

Methods for finding approximate solutions of integral equations.

It is required to find the solution of a one-dimensional Fredholm equation of the second kind,

(1)

where is continuous on , is a numerical parameter and is continuous on .

Suppose that is not an eigen value of . Then equation (1) has a unique solution , which is continuous on . Under these conditions one can give the following methods for obtaining an approximate solution.

First method.

Let and be finite numbers. The integral in (1) is replaced by an integral sum over a grid , , while the variable takes the values . One then obtains a system of linear algebraic equations with respect to the ,

(2)

where , and are the coefficients of the quadrature formula by means of which the integral in (1) is replaced by the integral sum. For sufficiently large , the system (2) has a unique solution . As an approximate solution to (1) one can take the function

since as and , the sequence of functions converges uniformly on to the required solution of equation (1). See [1]–[4].

When replacing the integral by a quadrature formula, one has to bear in mind that the greater the precision of the quadrature formula used, the greater the smoothness of the kernel and solution (and hence also ) needs to be.

In the case when the range of integration is infinite, it is replaced by a finite interval by using a priori information concerning the behaviour of the required solution for large values of . The equation so obtained is then approximately solved by the above method. Alternatively, by a change of the integration variable the range of integration is reduced to a finite range. As another alternative, quadrature formulas for an infinite range can be applied.

Second method.

In equation (1) the kernel is replaced by a degenerate kernel approximating it:

in which the functions are linearly independent. The equation

(3)

obtained in this way has a solution of the form

(4)

in which the constants

have to be determined. On substituting the function into equation (3) and comparing the coefficients at the functions one obtains a system of linear algebraic equations for the :

where

Having determined the from the above system and by substituting them in (4) one obtains the function , which is taken as the approximate solution of (1), since for a sufficiently good approximation of the kernel by a degenerate kernel the solution of equation (3) differs by an arbitrarily small amount from the required solution on any interval , as well as on in the case when is a finite interval (see [1], [4]).

Third method.

As approximate solutions one takes functions obtained by iteration based on the formula

; the sequence converges uniformly to the required solution as , provided that , where . Convergence of to the exact solution also holds for kernels with an integrable singularity (see [1]). Estimates of the errors of these methods are given in [1]–[7]. In [8] the question is considered of the minimum number of arithmetical operations required in order to obtain an approximate value of the integral with a prescribed precision. The solution of this problem is equivalent to finding the size of the minimal error of an approximate solution of the problem under a prescribed number of arithmetical operations.

For the solution of Fredholm integral equations of the first kind special methods need to be applied, since these problems are ill-posed. If in equation (1) is one of the eigen values of the kernel , then the problem of finding a solution of (1) is ill-posed and requires special methods (see Ill-posed problems).

Non-linear equations of the second kind are usually solved approximately by an iterative method (see [3]).

The Galerkin method for obtaining approximate solutions of linear and non-linear equations is also used.

Similar methods can also be applied for obtaining approximate solutions of multi-dimensional Fredholm integral equations of the second kind. However, their numerical implementation is more complicated. See [5]–[10] for cubature formulas for the approximate computation of multiple integrals and their error estimates. A Monte-Carlo method of approximate numerical computation of multiple integrals is discussed in [10].

References

[1]	I.G. Petrovskii, "Lectures on the theory of integral equations" , Graylock (1957) (Translated from Russian)
[2]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[3]	I.S. Berezin, N.P. Zhidkov, "Computing methods" , Pergamon (1973) (Translated from Russian)
[4]	L.V. Kantorovich, V.I. Krylov, "Approximate methods of higher analysis" , Noordhoff (1958) (Translated from Russian)
[5]	I.P. Mysovskikh, "Cubature formulae for evaluating integrals on the surface of a sphere" Sibirsk. Mat. Zh. , 5 : 3 (1964) pp. 721–723 (In Russian)
[6]	I.P. Mysovskikh, "The application of orthogonal polynomials to cubature formulae" USSR Comp. Math. Math. Phys. , 12 : 2 (1972) pp. 228–239 Zh. Vychisl. Mat. i Mat. Fiz. , 12 : 2 (1972) pp. 467–475
[7]	I.P. Mysovskikh, "On Chakalov's theorem" USSR Comp. Math. Math. Phys. , 15 : 6 (1976) pp. 221–227 Zh. Vychisl. Mat. i Mat. Fiz. , 15 : 6 (1975) pp. 1589–1593
[8]	K.B. Emel'yanov, A.M. Il'in, "Number of arithmetical operations necessary for the approximate solution of Fredholm integral equations of the second kind" USSR Comp. Math. Math. Phys. , 7 : 4 (1970) pp. 259–266 Zh. Vychisl. Mat. i Mat. Fiz. , 7 : 4 (1967) pp. 905–910
[9]	S.L. Sobolev, "Introduction to the theory of cubature formulas" , Moscow (1974) (In Russian)
[10]	I.M. Sobol', "Multi-dimensional cubature formulas and Haar functions" , Moscow (1969) (In Russian)

Comments

The Fredholm equation (1) is said to be of the first kind if vanishes and of the second kind otherwise (cf. also Fredholm equation, numerical methods). It is a special case of the more general integral equation with variable limits of integration:

This equation is often referred to as Andreoli's integral equation. If and , this equation reduces to a Volterra integral equation (cf. Volterra equation) of the second or first kind .

In the numerical analysis of integral equations (including Fredholm and Voltera equations as well), one uses the terminology degenerate kernel (of rank ) or Pincherle–Goursat kernel for indicating kernels of the form . In the non-linear case, where the integrand in (1) is of the form , one may approximate by a finite sum of terms . Kernels of this type are called separable or finitely decomposable.

A thorough discussion of numerical methods for linear integral equations of the second kind including Fortran programs can be found in [a2]; see also [a3]. The "first method" of the main article is usually called the Nyström method. A functional-analytic basis for numerical methods for both linear and non-linear integral equations is the theory of collectively-compact operators ([a1]). Numerical methods for integral equations of the first kind are the so-called "regularization methodregularization methods" (cf. Regularization method, [a4]).

References

[a1]	P.M. Anselone, "Collectively compact operator approximation theory and applications to integral equations" , Prentice-Hall (1971)
[a2]	K.E. Atkinson, "A survey of numerical methods for the solution of Fredholm integral equations of the second kind" , SIAM (1976)
[a3]	C.T.H. Baker, "The numerical treatment of integral equations" , Clarendon Press (1977)
[a4]	C.W. Groetsch, "The theory of Tikhonov regularization for Fredholm equations of the first kind" , Pitman (1984)
[a5]	J.L. Walsh, L.M. Delver, "Numerical solution of integral equations" , Oxford Univ. Press (1974)