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$.
http://i.stanford.edu/pub/cstr/reports/cs/tr/69/141/CS-TR-69-141.pdf