Subsection 6.3.1 Initial insights
¶Before giving a general result, let us focus on the case where the vectors \(x \) and \(y \) have only a few elements:
Example 6.3.1.1.
Consider
\begin{equation*}
x = \left( \begin{array}{c}
\chi_0 \\
\chi_1
\end{array} \right)
\mbox{ and }
y = \left( \begin{array}{c}
\psi_0 \\
\psi_1
\end{array} \right)
\end{equation*}
and the computation
\begin{equation*}
\kappa \becomes x^T y .
\end{equation*}
Under the SCM given in Subsubsection 6.2.3.2, the computed result, \(\check \kappa \text{,}\) satisfies
\begin{equation}
\check \kappa =
\left( \begin{array}{c} \chi_0 \\ \chi_1 \end{array} \right)^T
\left( \begin{array}{c c } ( 1 + \epsilon_*^{(0)})( 1 + \epsilon_+^{(1)}) \amp0 \\0 \amp ( 1 + \epsilon_*^{(1)})( 1 + \epsilon_+^{(1)})\end{array} \right)
\left( \begin{array}{c} \psi_0 \\ \psi_1 \end{array}
\right). \label{chapter06-stab-dot-1}\tag{6.3.1}
\end{equation}
Solution
\begin{equation*}
\begin{array}{l}
\check \kappa \\
~~~= ~~~~ \lt \check \kappa = \left[ x^T y \right] \gt \\
\left[ \left( \begin{array}{c} \chi_0 \\ \chi_1 \end{array} \right)^T
\left( \begin{array}{c} \psi_0 \\ \psi_1 \end{array} \right) \right] \\
~~~= ~~~~ \lt \mbox{ definition of } x^T y \gt \\
\left[ \chi_0 \psi_0 + \chi_1 \psi_1 \right] \\
~~~= ~~~~ \lt
\mbox{ each suboperation is performed in floating point arithmetic }
\gt \\
\left[ \left[\chi_0 \psi_0\right] + \left[\chi_1 \psi_1\right] \right] \\
~~~= ~~~~ \lt \mbox{ apply SCM multiple times } \gt \\
\left[ \chi_0 \psi_0 ( 1 + \epsilon_*^{(0)}) + \chi_1 \psi_1 ( 1 + \epsilon_*^{(1)}) \right] \\
~~~= ~~~~ \lt \mbox{ apply SCM } \gt \\
( \chi_0 \psi_0 ( 1 + \epsilon_*^{(0)}) + \chi_1 \psi_1 ( 1 + \epsilon_*^{(1)}) ) ( 1 + \epsilon_+^{(1)}) \\
~~~= ~~~~ \lt \mbox{ distribute } \gt \\
\chi_0 \psi_0
( 1 + \epsilon_*^{(0)})( 1 + \epsilon_+^{(1)})
+ \chi_1 \psi_1 ( 1 + \epsilon_*^{(1)}) ( 1 + \epsilon_+^{(1)}) \\
~~~= ~~~~ \lt \mbox{ commute } \gt \\
\chi_0
( 1 + \epsilon_*^{(0)})( 1 + \epsilon_+^{(1)}) \psi_0
+ \chi_1 ( 1 + \epsilon_*^{(1)}) ( 1 + \epsilon_+^{(1)})
\psi_1
\\
~~~= ~~~~ \lt
\mbox{ (perhaps too) slick way of expressing the final result } \gt \\
% \left( \begin{array}{c} \chi_0 \\ \chi_1 \end{array} \right)^T
% \left( \begin{array}{c} \psi_0 ( 1 + \epsilon_*^{(0)})( 1 + \epsilon_+^{(1)}) \\ \psi_1 ( 1 + \epsilon_*^{(1)})( 1 + \epsilon_+^{(1)})\end{array} \right)
% \\
% \amp=\amp
\left( \begin{array}{c} \chi_0 \\ \chi_1 \end{array} \right)^T
\left( \begin{array}{c c } ( 1 + \epsilon_*^{(0)})( 1 + \epsilon_+^{(1)}) \amp0 \\0 \amp ( 1 + \epsilon_*^{(1)})( 1 + \epsilon_+^{(1)})\end{array} \right)
\left( \begin{array}{c} \psi_0 \\ \psi_1 \end{array} \right) \\
% \amp=\amp
% \left( \begin{array}{c} \chi_0 ( 1 + \epsilon_*^{(0)})( 1 + \epsilon_+^{(1)}) \\ \chi_1 ( 1 + \epsilon_*^{(1)})( 1 + \epsilon_+^{(1)})\end{array} \right)^T
% \left( \begin{array}{c} \psi_0 \\ \psi_1 \end{array} \right)
,
\end{array}
\end{equation*}
where \(\vert \epsilon_{*}^{(0)} \vert , \vert \epsilon_{*}^{(1)} \vert, \vert \epsilon_{+}^{(1)} \vert \leq \meps \text{.}\)
An important insight from this example is that the result in (6.3.1) can be manipulated to associate the accummulated error with vector \(x \) as in
\begin{equation*}
\check \kappa =
\left( \begin{array}{c} \chi_0 ( 1 + \epsilon_*^{(0)})( 1 + \epsilon_+^{(1)}) \\ \chi_1 ( 1 + \epsilon_*^{(1)})( 1 + \epsilon_+^{(1)})\end{array} \right)^T
\left( \begin{array}{c} \psi_0 \\ \psi_1 \end{array} \right)
\end{equation*}
or with vector \(y \)
\begin{equation*}
\check \kappa =
\left( \begin{array}{c} \chi_0 \\ \chi_1 \end{array} \right)^T
\left( \begin{array}{c} \psi_0 ( 1 + \epsilon_*^{(0)})( 1 + \epsilon_+^{(1)}) \\ \psi_1 ( 1 + \epsilon_*^{(1)})( 1 + \epsilon_+^{(1)})\end{array} \right) .
\end{equation*}
This will play a role when we later analyze algorithms that use the dot product.
Homework 6.3.1.1.
Consider
\begin{equation*}
x = \left( \begin{array}{c}
\chi_0 \\
\chi_1 \\
\chi_2 \end{array} \right)
\mbox{ and }
y = \left( \begin{array}{c}
\psi_0 \\
\psi_1 \\
\psi_2
\end{array} \right)
\end{equation*}
and the computation
\begin{equation*}
\kappa \becomes x^T y
\end{equation*}
computed in the order indicated by
\begin{equation*}
\kappa := ( \chi_0 \psi_0 + \chi_1 \psi_1 ) + \chi_2
\psi_2.
\end{equation*}
Employ the SCM given in Subsubsection 6.2.3.2, to derive a result similar to that given in (6.3.1).
Answer
Solution
\begin{equation*}
\left( \begin{array}{c} \chi_0 \\ \chi_1 \\ \chi_2 \end{array} \right)^T
\left( \begin{array}{c c c } ( 1 + \epsilon_*^{(0)}) ( 1 +
\epsilon_+^{(1)}) ( 1 + \epsilon_+^{(2)}) \amp 0 \amp 0
\\
0 \amp
( 1 + \epsilon_*^{(1)})( 1 + \epsilon_+^{(1)})
( 1 + \epsilon_+^{(2)})
\amp 0 \\
0 \amp 0 \amp
( 1 + \epsilon_*^{(2)})
( 1 + \epsilon_+^{(2)})
\end{array} \right)
\left( \begin{array}{c} \psi_0 \\ \psi_1 \\ \psi_2 \end{array} \right) \\
,
\end{equation*}
where \(\vert \epsilon_{*}^{(0)} \vert , \vert \epsilon_{*}^{(1)} \vert, \vert \epsilon_{+}^{(1)} \vert , \vert \epsilon_{*}^{(2)} \vert, \vert \epsilon_{+}^{(2)} \vert \leq \meps \text{.}\)
Here is a solution that builds on the last example and paves the path toward the general solution presented in the next unit.
\begin{equation*}
\begin{array}{l}
\check \kappa \\
~~~= ~~~~ \lt \check \kappa = \left[ x^T y \right] \gt \\
\left[ ( \chi_0 \psi_0 + \chi_1 \psi_1 ) + \chi_2 \psi_2 \right] \\
~~~=~~~~ \lt \mbox{ each suboperation is performed in floating point arithmetic } \gt \\
\left[ \left[ \chi_0 \psi_0 + \chi_1 \psi_1 \right] + \left[\chi_2 \psi_2\right] \right] \\
~~~ = ~~~ \lt
\mbox{ reformulate so we can use result from Example 6.3.1.1 } \gt \\
\left[ \left[
\left( \begin{array}{c}
\chi_0 \\
\chi_1
\end{array} \right)^T
\left( \begin{array}{c}
\psi_0 \\
\psi_1
\end{array} \right)
\right] + \left[ \chi_2 \psi_2 \right]\right] \\
~~~ = ~~~ \lt
\mbox{ use Example 6.3.1.1; twice SCM } \gt \\
\left(
\left( \begin{array}{c} \chi_0 \\ \chi_1 \end{array} \right)^T
\left( \begin{array}{c c } ( 1 + \epsilon_*^{(0)})( 1 + \epsilon_+^{(1)}) \amp0 \\0 \amp ( 1 + \epsilon_*^{(1)})( 1 + \epsilon_+^{(1)})\end{array} \right)
\left( \begin{array}{c} \psi_0 \\ \psi_1 \end{array} \right)
% \amp=\amp
% \left( \begin{array}{c} \chi_0 ( 1 + \epsilon_*^{(0)})( 1 + \epsilon_+^{(1)}) \\ \chi_1 ( 1 + \epsilon_*^{(1)})( 1 + \epsilon_+^{(1)})\end{array} \right)^T
% \left( \begin{array}{c} \psi_0 \\ \psi_1 \end{array}
\right. \\
~~~~~~~~~~~~~ \left.
+ \chi_2 \psi_2 ( 1 + \epsilon_*^{(2)} ) \right) ( 1 + \epsilon_+^{(2)} )
\\
~~~= ~~~~ \lt
\mbox{ distribute, commute } \gt \\
\left( \begin{array}{c} \chi_0 \\ \chi_1 \end{array} \right)^T
\left( \begin{array}{c c } ( 1 + \epsilon_*^{(0)})( 1 +
\epsilon_+^{(1)}) \amp0 \\0 \amp ( 1 +
\epsilon_*^{(1)})( 1 + \epsilon_+^{(1)})\end{array}
\right)
( 1 + \epsilon_+^{(2)} )
\left( \begin{array}{c} \psi_0 \\ \psi_1 \end{array} \right)
\\
~~~~~~~~~~~~~
+ \chi_2 ( 1 + \epsilon_*^{(2)} ) ( 1 + \epsilon_+^{(2)} ) \psi_2
\\
~~~ = ~~~~ \lt
\mbox{ (perhaps too) slick way of expressing the final result } \gt \\
\left( \begin{array}{c} \chi_0 \\ \chi_1 \\ \chi_2 \end{array} \right)^T
\left( \begin{array}{c c c } ( 1 + \epsilon_*^{(0)}) ( 1 +
\epsilon_+^{(1)}) ( 1 + \epsilon_+^{(2)}) \amp 0 \amp 0
\\
0 \amp
( 1 + \epsilon_*^{(1)})( 1 + \epsilon_+^{(1)})
( 1 + \epsilon_+^{(2)})
\amp 0 \\
0 \amp 0 \amp
( 1 + \epsilon_*^{(2)})
( 1 + \epsilon_+^{(2)})
\end{array} \right)
\left( \begin{array}{c} \psi_0 \\ \psi_1 \\ \psi_2 \end{array} \right) \\
,
\end{array}
\end{equation*}
where \(\vert \epsilon_{*}^{(0)} \vert , \vert \epsilon_{*}^{(1)} \vert, \vert \epsilon_{+}^{(1)} \vert , \vert \epsilon_{*}^{(2)} \vert, \vert \epsilon_{+}^{(2)} \vert \leq \meps \text{.}\)