View source for Integral equations, numerical methods

<!--
i0514301.png
$#A+1 = 73 n = 0
$#C+1 = 73 : ~/encyclopedia/old_files/data/I051/I.0501430 Integral equations, numerical methods
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

Methods for finding approximate solutions of integral equations.

It is required to find the solution  $  \phi ( x) $
of a one-dimensional [[Fredholm equation|Fredholm equation]] of the second kind,

$$ \tag{1 }
\phi ( x)  =  \lambda
\int\limits _ { a } ^ { b } 
K ( x , s ) \phi ( s) \ 
d s + f ( x) ,
$$

where  $  f ( x) $
is continuous on  $  [ a , b ] $, 
$  \lambda $
is a numerical parameter and  $  K ( x , s ) $
is continuous on  $  a \leq  x , s \leq  b $.

Suppose that  $  \lambda $
is not an eigen value of  $  K ( x , s ) $. 
Then equation (1) has a unique solution  $  \phi ( x) $, 
which is continuous on  $  [ a , b ] $. 
Under these conditions one can give the following methods for obtaining an approximate solution.

==First method.==
Let  $  a $
and  $  b $
be finite numbers. The integral in (1) is replaced by an integral sum over a grid  $  \{ s _ {j} \} $, 
$  j = 0 \dots n $, 
while the variable  $  x $
takes the values  $  x _ {1}, \dots, x _ {n} $. 
One then obtains a system of linear algebraic equations with respect to the  $  \phi _ {j} $,

$$ \tag{2 }
\sum _ { j=  1} ^ { n } 
A _ {ij} \phi _ {j}  = \ 
f _ {i} ,\  i = 1 \dots n ,
$$

where  $  A _ {ij} = 1 - \lambda C _ {j} K ( x _ {i} , x _ {j} ) $, 
and  $  C _ {j} $
are the coefficients of the quadrature formula by means of which the integral in (1) is replaced by the integral sum. For sufficiently large  $  n $, 
the system (2) has a unique solution  $  \{ \overline \phi _ {j} \} $. 
As an approximate solution to (1) one can take the function

$$ 
\overline \phi _ {n} ( x)  = \ 
f ( x) + \lambda
\sum _ { j= 1} ^ { n } 
C _ {j} K ( x , x _ {j} ) ,
$$

since as  $  n \rightarrow \infty $
and  $  \Delta _ {n} = \max _ {i} \{ | x _ {i+ 1} - x _ {i} | \} \rightarrow 0 $, 
the sequence of functions  $  \overline \phi _ {n} ( x) $
converges uniformly on  $  [ a , b ] $
to the required solution of equation (1). See [[#References|[1]]]–[[#References|[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  $  f ( x) $) 
needs to be.

In the case when the range of integration  $  ( a , b ) $
is infinite, it is replaced by a finite interval  $  ( a _ {1} , b _ {1} ) $
by using a priori information concerning the behaviour of the required solution  $  \overline \phi ( x) $
for large values of  $  | x | $. 
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  $  K ( x , s ) $
is replaced by a degenerate kernel approximating it:

$$ 
K _ {1} ( x , s )  = \ 
\sum _ { i= 1} ^ { n }  a _ {i} ( x) b _ {i} ( s) ,
$$

in which the functions  $  \{ a _ {i} ( x) \} $
are linearly independent. The equation

$$ \tag{3 }
\phi ( x)  =  \lambda
\int\limits _ { a } ^ { b }  \ 
\sum _ { i= 1} ^ { n } 
a _ {i} ( x) b _ {i} ( s) \phi ( s)  d s + f ( x)
$$

obtained in this way has a solution  $  \widehat \phi   ( x) $
of the form

$$ \tag{4 }
\widehat \phi   ( x)  =  \lambda
\sum _ { i= 1} ^ { n } 
C _ {i} a _ {i} ( x) + f ( x) ,
$$

in which the constants

$$ 
C _ {i}  = \ 
\int\limits _ { a } ^ { b } 
\widehat \phi   ( s) b _ {i} ( s)  d s
$$

have to be determined. On substituting the function  $  \widehat \phi   ( x) $
into equation (3) and comparing the coefficients at the functions  $  a _ {i} ( x) $
one obtains a system of linear algebraic equations for the  $  C _ {i} $:

$$ 
C _ {i} - \lambda
\sum _ { i= 1} ^ { n } 
\alpha _ {ij} C _ {j}  = \ 
\beta _ {i} ,\  i = 1, \dots, n ,
$$

where

$$ 
\alpha _ {ij}  = \ 
\int\limits _ { a } ^ { b } 
a _ {j} ( s) b _ {i} ( s) \ 
d s ,\  \beta _ {i}  = \ 
\int\limits _ { a } ^ { b } 
f ( s) b _ {i} ( s)  d s .
$$

Having determined the  $  C _ {i} $
from the above system and by substituting them in (4) one obtains the function  $  \widehat \phi   ( x) $, 
which is taken as the approximate solution of (1), since for a sufficiently good approximation of the kernel  $  K ( x , s ) $
by a degenerate kernel the solution of equation (3) differs by an arbitrarily small amount from the required solution  $  \phi ( x) $
on any interval  $  [ a _ {1} , b _ {1} ] \subset  ( a , b ) $, 
as well as on  $  [ a , b ] $
in the case when  $  ( a , b ) $
is a finite interval (see [[#References|[1]]], [[#References|[4]]]).

==Third method.==
As approximate solutions one takes functions  $  \phi _ {n} ( x) $
obtained by iteration based on the formula

$$ 
\phi _ {n+ 1} ( x)  =  \lambda
\int\limits _ { a } ^ { b } 
K ( x , s ) \phi _ {n} ( s)  d s + f ( x) ,\ \ 
n = 0 , 1 \dots
$$

$  \phi _ {0} ( x) = f ( x) $; 
the sequence  $  \{ \phi _ {n} ( x) \} $
converges uniformly to the required solution as  $  n \rightarrow \infty $, 
provided that  $  | \lambda | < 1 / M ( b - a ) $, 
where  $  M = \sup _ {x,s}  | K ( x , s ) | $. 
Convergence of  $  \{ \phi _ {n} ( x) \} $
to the exact solution also holds for kernels with an integrable singularity (see [[#References|[1]]]). Estimates of the errors of these methods are given in [[#References|[1]]]–[[#References|[7]]]. In [[#References|[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)  $  \lambda $
is one of the eigen values of the kernel  $  K ( x , s ) $, 
then the problem of finding a solution of (1) is ill-posed and requires special methods (see [[Ill-posed problems|Ill-posed problems]]).

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

The [[Galerkin method|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 [[#References|[5]]]–[[#References|[10]]] for cubature formulas for the approximate computation of multiple integrals and their error estimates. A [[Monte-Carlo method|Monte-Carlo method]] of approximate numerical computation of multiple integrals is discussed in [[#References|[10]]].

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  I.G. Petrovskii,   "Lectures on the theory of integral equations" , Graylock  (1957)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N.S. Bakhvalov,   "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  I.S. Berezin,   N.P. Zhidkov,   "Computing methods" , Pergamon  (1973)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  L.V. Kantorovich,   V.I. Krylov,   "Approximate methods of higher analysis" , Noordhoff  (1958)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  S.L. Sobolev,   "Introduction to the theory of cubature formulas" , Moscow  (1974)  (In Russian)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  I.M. Sobol',   "Multi-dimensional cubature formulas and Haar functions" , Moscow  (1969)  (In Russian)</TD></TR></table>

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

$$ 
\phi ( x)  =  \int\limits _ {a ( x) } ^ { {b }  ( x ) } K ( x , s )
\phi ( s)  d s + f ( x) .
$$

This equation is often referred to as Andreoli's integral equation. If  $  a ( x) = a $
and  $  b ( x) = x $, 
this equation reduces to a Volterra integral equation (cf. [[Volterra equation|Volterra equation]]) of the second  $  ( f \neq 0 ) $
or first kind  $  ( f = 0 ) $.

In the numerical analysis of integral equations (including Fredholm and Voltera equations as well), one uses the terminology [[Degenerate kernel|degenerate kernel]] (of rank  $  n $) 
or Pincherle–Goursat kernel for indicating kernels of the form  $  K _ {1} ( x , s ) $. 
In the non-linear case, where the integrand in (1) is of the form  $  k ( x , s , \phi ) $, 
one may approximate  $  k $
by a finite sum of terms  $  a _ {i} ( x) b _ {i} ( s , \phi ) $. 
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 [[#References|[a2]]]; see also [[#References|[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 ([[#References|[a1]]]). Numerical methods for integral equations of the first kind are the so-called  "regularization methods"  (cf. [[Regularization method|Regularization method]], [[#References|[a4]]]).

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