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