Stability and length of computations in the variational-difference method

Yu. K. Dem'yanovich

Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms, Tome 80 (1978), pp. 5-29

Résumé

The article considers a stable algorithm for computing the matrix and the righthand side of a variational-difference system of equations for one-dimensional nonsingular problems with a differential operator of order $2k$. Since usually such systems are $O(h^{-2k})$ conditioned, an error $\varepsilon$ in the coefficients in general leads to an asymptotic error $\varepsilon O(h^{-2k})$ in the solution of the system. A matrix subspace is identified in which an error $\varepsilon$ leads to an error $C_\varepsilon$ in the solution of the system (in the energy norm) the constant $C$ is independent of $h$), and then an algorithm is proposed which leaves the matrix computation error in this subspace. An approximate solution is represented as a sequence (a “word” ) of elementary arithmetic operations, and a bound on the computation length is derived. A measure of the computation length is a nonnegative functional defined on the set of words of some alphabet which has certain desirable properties. Particular instances of this functional include the number of operations, the weighted average number of macroinstructions of different types, the computation time, etc.