Namespaces
Variants
Actions

Difference between revisions of "Method of undetermined coefficients in developing numerical algorithms"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
{{TEX|done}}
 
A special method for constructing algorithms based on the requirement that the algorithms should be exact or have an error of prescribed order of accuracy on some set of problems.
 
A special method for constructing algorithms based on the requirement that the algorithms should be exact or have an error of prescribed order of accuracy on some set of problems.
  
A typical example of problems that can be solved by the method of undetermined coefficients is the following (see [[#References|[1]]], [[#References|[2]]]). (It can also be solved by other methods.) Let the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063610/m0636101.png" /> of a function be known. It is required to construct a formula for the approximation of the function
+
A typical example of problems that can be solved by the method of undetermined coefficients is the following (see [[#References|[1]]], [[#References|[2]]]). (It can also be solved by other methods.) Let the values $f(P_1),\ldots,f(P_N)$ of a function be known. It is required to construct a formula for the approximation of 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/m/m063/m063610/m0636102.png" /></td> </tr></table>
+
$$f(P)\approx g(f(P_1),\ldots,f(P_N),P);$$
  
 
to construct a formula for computing the derivative:
 
to construct a formula for computing the derivative:
  
<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/m/m063/m063610/m0636103.png" /></td> </tr></table>
+
$$Df(P)\approx g_D(f(P_1),\ldots,f(P_N),P);$$
  
 
and to construct a formula for computing the integral:
 
and to construct a formula for computing the integral:
  
<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/m/m063/m063610/m0636104.png" /></td> </tr></table>
+
$$I(f)=\int\limits_\Omega f(P)p(P)dP\approx g_1(f(P_1),\ldots,f(P_n)).$$
  
 
To solve the last of these problems one is given some form of an approximate solution, for example, linear:
 
To solve the last of these problems one is given some form of an approximate solution, for example, linear:
  
<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/m/m063/m063610/m0636105.png" /></td> </tr></table>
+
$$g_1=\sum_{n=1}^NC_nf(P_n),$$
  
and one determines the coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063610/m0636106.png" /> from the requirement that the approximate formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063610/m0636107.png" /> should be exact for functions of a certain collection; for example, for those of the form
+
and one determines the coefficients $C_n$ from the requirement that the approximate formula $I(f)\approx g_1$ should be exact for functions of a certain collection; for example, for those 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/m/m063/m063610/m0636108.png" /></td> </tr></table>
+
$$f(P)=\sum_{m=1}^Ma_m\omega_m(P),$$
  
where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063610/m0636109.png" /> are fixed and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063610/m06361010.png" /> are arbitrary. As a rule one takes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063610/m06361011.png" />. For the equality
+
where the $\omega_m(P)$ are fixed and the $a_m$ are arbitrary. As a rule one takes $M=N$. For the equality
  
<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/m/m063/m063610/m06361012.png" /></td> </tr></table>
+
$$I\left(\sum_{m=1}^Ma_m\omega_m\right)=\sum_{n=1}^NC_n\left(\sum_{m=1}^Ma_m\omega_m(P_n)\right)$$
  
to hold for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063610/m06361013.png" /> it suffices that
+
to hold for all $a_m$ it suffices that
  
<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/m/m063/m063610/m06361014.png" /></td> </tr></table>
+
$$I(\omega_m)=\sum_{n=1}^NC_n\omega_m(P_n),\quad m=1,\ldots,M.$$
  
From this one determines the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063610/m06361015.png" /> (if this is possible).
+
From this one determines the $C_n$ (if this is possible).
  
 
Sometimes one is given a more complicated form of dependence. For example, frequently it is known that the function in question has a good approximation by functions of the form
 
Sometimes one is given a more complicated form of dependence. For example, frequently it is known that the function in question has a good approximation by functions 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/m/m063/m063610/m06361016.png" /></td> </tr></table>
+
$$g(a_1,\ldots,a_M,P),$$
  
where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063610/m06361017.png" /> are known. The parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063610/m06361018.png" /> are chosen from the system of equations
+
where the $a_m$ are known. The parameters $a_m$ are chosen from the system of equations
  
<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/m/m063/m063610/m06361019.png" /></td> </tr></table>
+
$$g(a_1,\ldots,a_M,P_n)=f(P_n),\quad n=1,\ldots,N.$$
  
 
In the case of formulas for numerical integration, often the coordinates of the nodes of integration stand out as unknown parameters. For example, in the [[Gauss quadrature formula|Gauss quadrature formula]]
 
In the case of formulas for numerical integration, often the coordinates of the nodes of integration stand out as unknown parameters. For example, in the [[Gauss quadrature formula|Gauss quadrature 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/m/m063/m063610/m06361020.png" /></td> </tr></table>
+
$$I(f)=\int\limits_a^bf(x)p(x)dx\approx\sum_{n=1}^NC_nf(P_n)$$
  
one considers as free parameters the coordinates of the nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063610/m06361021.png" />; owing to this one succeeds in constructing quadratures that are exact for polynomials of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063610/m06361022.png" />. In the construction of approximations of differential equations by the method of undetermined coefficients it is required that under substitution in a finite-difference scheme the solutions of the problem give compatible ([[Discrepancy|discrepancy]]) values of prescribed order of smallness in relation to the step of the grid. Such a device lies at the basis of ways for constructing Runge–Kutta methods and finite-difference methods (see [[#References|[1]]], [[#References|[2]]]).
+
one considers as free parameters the coordinates of the nodes $P_n$; owing to this one succeeds in constructing quadratures that are exact for polynomials of degree $2N-1$. In the construction of approximations of differential equations by the method of undetermined coefficients it is required that under substitution in a finite-difference scheme the solutions of the problem give compatible ([[Discrepancy|discrepancy]]) values of prescribed order of smallness in relation to the step of the grid. Such a device lies at the basis of ways for constructing Runge–Kutta methods and finite-difference methods (see [[#References|[1]]], [[#References|[2]]]).
  
 
The method of undetermined coefficients is also used in constructing approximations of partial differential equations (see [[#References|[3]]]).
 
The method of undetermined coefficients is also used in constructing approximations of partial differential equations (see [[#References|[3]]]).

Latest revision as of 11:59, 12 August 2014

A special method for constructing algorithms based on the requirement that the algorithms should be exact or have an error of prescribed order of accuracy on some set of problems.

A typical example of problems that can be solved by the method of undetermined coefficients is the following (see [1], [2]). (It can also be solved by other methods.) Let the values $f(P_1),\ldots,f(P_N)$ of a function be known. It is required to construct a formula for the approximation of the function

$$f(P)\approx g(f(P_1),\ldots,f(P_N),P);$$

to construct a formula for computing the derivative:

$$Df(P)\approx g_D(f(P_1),\ldots,f(P_N),P);$$

and to construct a formula for computing the integral:

$$I(f)=\int\limits_\Omega f(P)p(P)dP\approx g_1(f(P_1),\ldots,f(P_n)).$$

To solve the last of these problems one is given some form of an approximate solution, for example, linear:

$$g_1=\sum_{n=1}^NC_nf(P_n),$$

and one determines the coefficients $C_n$ from the requirement that the approximate formula $I(f)\approx g_1$ should be exact for functions of a certain collection; for example, for those of the form

$$f(P)=\sum_{m=1}^Ma_m\omega_m(P),$$

where the $\omega_m(P)$ are fixed and the $a_m$ are arbitrary. As a rule one takes $M=N$. For the equality

$$I\left(\sum_{m=1}^Ma_m\omega_m\right)=\sum_{n=1}^NC_n\left(\sum_{m=1}^Ma_m\omega_m(P_n)\right)$$

to hold for all $a_m$ it suffices that

$$I(\omega_m)=\sum_{n=1}^NC_n\omega_m(P_n),\quad m=1,\ldots,M.$$

From this one determines the $C_n$ (if this is possible).

Sometimes one is given a more complicated form of dependence. For example, frequently it is known that the function in question has a good approximation by functions of the form

$$g(a_1,\ldots,a_M,P),$$

where the $a_m$ are known. The parameters $a_m$ are chosen from the system of equations

$$g(a_1,\ldots,a_M,P_n)=f(P_n),\quad n=1,\ldots,N.$$

In the case of formulas for numerical integration, often the coordinates of the nodes of integration stand out as unknown parameters. For example, in the Gauss quadrature formula

$$I(f)=\int\limits_a^bf(x)p(x)dx\approx\sum_{n=1}^NC_nf(P_n)$$

one considers as free parameters the coordinates of the nodes $P_n$; owing to this one succeeds in constructing quadratures that are exact for polynomials of degree $2N-1$. In the construction of approximations of differential equations by the method of undetermined coefficients it is required that under substitution in a finite-difference scheme the solutions of the problem give compatible (discrepancy) values of prescribed order of smallness in relation to the step of the grid. Such a device lies at the basis of ways for constructing Runge–Kutta methods and finite-difference methods (see [1], [2]).

The method of undetermined coefficients is also used in constructing approximations of partial differential equations (see [3]).

References

[1] I.S. Berezin, N.P. Zhidkov, "Computing methods" , Pergamon (1973) (Translated from Russian)
[2] N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[3] S.K. Godunov, V.S. Ryaben'kii, "The theory of difference schemes" , North-Holland (1964) (Translated from Russian)


Comments

The techniques of curve and surface fitting may be considered as a form of, what is here called, the method of undetermined coefficients.

How to Cite This Entry:
Method of undetermined coefficients in developing numerical algorithms. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Method_of_undetermined_coefficients_in_developing_numerical_algorithms&oldid=13040
This article was adapted from an original article by N.S. Bakhvalov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article