Namespaces
Variants
Actions

Difference between revisions of "Integral equations, numerical methods"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fixing subscripts etc.)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 +
<!--
 +
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.
 
Methods for finding approximate solutions of integral equations.
  
It is required to find the solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i0514301.png" /> of a one-dimensional [[Fredholm equation|Fredholm equation]] of the second kind,
+
It is required to find the solution $  \phi ( x) $
 +
of a one-dimensional [[Fredholm equation|Fredholm equation]] of the second kind,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i0514302.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
\phi ( x)  = \lambda
 +
\int\limits _ { a } ^ { b }
 +
K ( x , s ) \phi ( s) \
 +
d s + f ( x) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i0514303.png" /> is continuous on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i0514304.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i0514305.png" /> is a numerical parameter and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i0514306.png" /> is continuous on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i0514307.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i0514308.png" /> is not an eigen value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i0514309.png" />. Then equation (1) has a unique solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143010.png" />, which is continuous on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143011.png" />. Under these conditions one can give the following methods for obtaining an approximate solution.
+
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.==
 
==First method.==
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143013.png" /> be finite numbers. The integral in (1) is replaced by an integral sum over a grid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143015.png" />, while the variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143016.png" /> takes the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143017.png" />. One then obtains a system of linear algebraic equations with respect to the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143018.png" />,
+
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} $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143019.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
\sum _ { j= 1} ^ { n }
 +
A _ {ij} \phi _ {j}  = \
 +
f _ {i} ,\  i = 1 \dots n ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143020.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143021.png" /> are the coefficients of the quadrature formula by means of which the integral in (1) is replaced by the integral sum. For sufficiently large <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143022.png" />, the system (2) has a unique solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143023.png" />. As an approximate solution to (1) one can take the function
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143024.png" /></td> </tr></table>
+
$$
 +
\overline \phi _ {n} ( x)  = \
 +
f ( x) + \lambda
 +
\sum _ { j= 1} ^ { n }
 +
C _ {j} K ( x , x _ {j} ) ,
 +
$$
  
since as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143026.png" />, the sequence of functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143027.png" /> converges uniformly on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143028.png" /> to the required solution of equation (1). See [[#References|[1]]]–[[#References|[4]]].
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143029.png" />) needs to be.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143030.png" /> is infinite, it is replaced by a finite interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143031.png" /> by using a priori information concerning the behaviour of the required solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143032.png" /> for large values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143033.png" />. 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.
+
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.==
 
==Second method.==
In equation (1) the kernel <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143034.png" /> is replaced by a degenerate kernel approximating it:
+
In equation (1) the kernel $  K ( x , s ) $
 +
is replaced by a degenerate kernel approximating it:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143035.png" /></td> </tr></table>
+
$$
 +
K _ {1} ( x , s )  = \
 +
\sum _ { i= 1} ^ { n }  a _ {i} ( x) b _ {i} ( s) ,
 +
$$
  
in which the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143036.png" /> are linearly independent. The equation
+
in which the functions $  \{ a _ {i} ( x) \} $
 +
are linearly independent. The equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143037.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143038.png" /> of the form
+
obtained in this way has a solution $  \widehat \phi  ( x) $
 +
of the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143039.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
$$ \tag{4 }
 +
\widehat \phi  ( x)  = \lambda
 +
\sum _ { i= 1} ^ { n }
 +
C _ {i} a _ {i} ( x) + f ( x) ,
 +
$$
  
 
in which the constants
 
in which the constants
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143040.png" /></td> </tr></table>
+
$$
 +
C _ {i}  = \
 +
\int\limits _ { a } ^ { b }
 +
\widehat \phi  ( s) b _ {i} ( s)  d s
 +
$$
  
have to be determined. On substituting the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143041.png" /> into equation (3) and comparing the coefficients at the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143042.png" /> one obtains a system of linear algebraic equations for the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143043.png" />:
+
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} $:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143044.png" /></td> </tr></table>
+
$$
 +
C _ {i} - \lambda
 +
\sum _ { i= 1} ^ { n }
 +
\alpha _ {ij} C _ {j}  = \
 +
\beta _ {i} ,\  i = 1, \dots, n ,
 +
$$
  
 
where
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143045.png" /></td> </tr></table>
+
$$
 +
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143046.png" /> from the above system and by substituting them in (4) one obtains the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143047.png" />, which is taken as the approximate solution of (1), since for a sufficiently good approximation of the kernel <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143048.png" /> by a degenerate kernel the solution of equation (3) differs by an arbitrarily small amount from the required solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143049.png" /> on any interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143050.png" />, as well as on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143051.png" /> in the case when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143052.png" /> is a finite interval (see [[#References|[1]]], [[#References|[4]]]).
+
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.==
 
==Third method.==
As approximate solutions one takes functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143053.png" /> obtained by iteration based on the formula
+
As approximate solutions one takes functions $  \phi _ {n} ( x) $
 +
obtained by iteration based on the formula
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143054.png" /></td> </tr></table>
+
$$
 +
\phi _ {n+ 1} ( x)  = \lambda
 +
\int\limits _ { a } ^ { b }
 +
K ( x , s ) \phi _ {n} ( s)  d s + f ( x) ,\ \
 +
n = 0 , 1 \dots
 +
$$
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143055.png" />; the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143056.png" /> converges uniformly to the required solution as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143057.png" />, provided that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143058.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143059.png" />. Convergence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143060.png" /> 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.
+
$  \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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143061.png" /> is one of the eigen values of the kernel <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143062.png" />, then the problem of finding a solution of (1) is ill-posed and requires special methods (see [[Ill-posed problems|Ill-posed problems]]).
+
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]]]).
 
Non-linear equations of the second kind are usually solved approximately by an iterative method (see [[#References|[3]]]).
Line 68: Line 176:
 
====References====
 
====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>
 
<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====
 
====Comments====
The Fredholm equation (1) is said to be of the first kind if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143063.png" /> 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:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143064.png" /></td> </tr></table>
+
$$
 +
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143065.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143066.png" />, this equation reduces to a Volterra integral equation (cf. [[Volterra equation|Volterra equation]]) of the second <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143067.png" /> or first kind <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143068.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143069.png" />) or Pincherle–Goursat kernel for indicating kernels of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143070.png" />. In the non-linear case, where the integrand in (1) is of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143071.png" />, one may approximate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143072.png" /> by a finite sum of terms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051430/i05143073.png" />. Kernels of this type are called separable or finitely decomposable.
+
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 methodregularization methods"  (cf. [[Regularization method|Regularization method]], [[#References|[a4]]]).
+
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====
 
====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>
 
<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>

Latest revision as of 13:26, 14 January 2022


Methods for finding approximate solutions of integral equations.

It is required to find the solution $ \phi ( x) $ of a one-dimensional 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 [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 $ 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 [1], [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 [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) $ \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).

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 $ f $ 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:

$$ \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) 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 (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 [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 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)
How to Cite This Entry:
Integral equations, numerical methods. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Integral_equations,_numerical_methods&oldid=14561
This article was adapted from an original article by V.Ya. Arsenin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article