BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-69-141
       ENTRY:: November 27, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Bounds for the error of linear systems of equations using the
               theory of moments
        TYPE:: Technical Report
      AUTHOR:: Dahlquist, Germund
      AUTHOR:: Eisenstat, Stanley C.
      AUTHOR:: Golub, Gene H.
        DATE:: October 1969
       PAGES:: 29
    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$.
       NOTES:: [Adminitrivia V1/Prg/19951127]
         END:: STAN//CS-TR-69-141