View source for Method of undetermined coefficients in developing numerical algorithms

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

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