Skip to main content

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 computational model given in (((Unresolved xref, reference "stability-model-of-floating-point-computation"; check spelling or use "provisional" attribute))) , 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 = [ x^T y ] \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{ distribute } \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
\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{.}\)

Solution

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{.}\)