Report Number: CS-TR-69-141
Institution: Stanford University, Department of Computer Science
Title: Bounds for the error of linear systems of equations using the theory of moments
Author: Dahlquist, Germund
Author: Eisenstat, Stanley C.
Author: Golub, Gene H.
Date: October 1969
Abstract: Consider the system of linear equations $A\underset ~\to x = \underset ~\to b$ where A is an n$\times$n real symmetric, positive definite matrix and $\underset ~\to b$ is a known vector. Suppose we are given an approximation to $\underset ~\to x$, $\underset ~\to \xi$, and we wish to determine upper and lower bounds for $\Vert \underset ~\to x\ - \underset ~\to \xi \Vert$ where $\Vert ...\Vert$ indicates the euclidean norm. Given the sequence of vectors ${\{ {\underset ~\to r}_i \} }^{k}_{i=0}$ where ${\underset ~\to r}_i\ = A{\underset ~\to r}_{i-1}$ and ${\underset ~\to r}_o\ = \underset ~\to b -A\underset ~\to \xi$, it is shown how to construct a sequence of upper and lower bounds for $\Vert \underset ~\to x\ - \underset ~\to \xi \Vert$ using the theory of moments. In addition, consider the Jacobi algorithm for solving the system $\underset ~\to x\ = M\underset ~\to x +\underset ~\to b \underline{viz.} {\underset ~\to x}_{i+1} = M{\underset ~\to x}_i +\underset ~\to b$. It is shown that by examining ${\underset ~\to \delta}_i\ = {\underset ~\to x}_{i+1} - {\underset ~\to x}_i , it is possible to construct upper and lower bounds for $\Vert {\underset ~\to x}_i -\underset ~\to x \Vert$.