View source for Method of undetermined coefficients in developing numerical algorithms

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

<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>

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>

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>

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>

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

<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>

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

<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>

to hold for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063610/m06361013.png" /> 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>

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).

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>

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

<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>

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>

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]]]).

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

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  I.S. Berezin,   N.P. Zhidkov,   "Computing methods" , Pergamon  (1973)  (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">  S.K. Godunov,   V.S. Ryaben'kii,   "The theory of difference schemes" , North-Holland  (1964)  (Translated from Russian)</TD></TR></table>



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