ALAFF Summary

Subsection 6.6.2 Summary

In our discussions, the set of floating point numbers, \(F \text{,}\) is the set of all numbers \(\chi = \mu \times \beta^e \) such that

\(\beta = 2 \text{,}\)
\(\mu = \pm. \delta_0 \delta_1 \cdots \delta_{t-1}\) (\(\mu \) has only \(t \) (binary) digits), where \(\delta_j \in \{ 0, 1 \} \)),
\(\delta_0 = 0 \) iff \(\mu = 0 \) (the mantissa is normalized), and
\(-L \leq e \leq U \text{.}\)

Definition 6.6.2.1. Machine epsilon (unit roundoff).

The machine epsilon (unit roundoff), \(\meps \text{,}\) is defined as the smallest positive floating point number \(\chi \) such that the floating point number that represents \(1 + \chi \) is greater than one.

\begin{equation*} \fl{ {\rm expression} } = [ {\rm expression} ] \end{equation*}

equals the result when computing \({\rm expression} \) using floating point computation (rounding or truncating as every intermediate result is stored). If

\begin{equation*} \kappa = {\rm expression} \end{equation*}

in exact arithmetic, then we indicate the associated floating point result with

\begin{equation*} \check \kappa = [ {\rm expression} ]. \end{equation*}

The Standard Computational Model (SCM) assumes that, for any two floating point numbers \(\chi\) and \(\psi\text{,}\) the basic arithmetic operations satisfy the equality

\begin{equation*} \fl{ \chi\ {\rm op}\ \psi } = (\chi\ {\rm op}\ \psi)( 1 + \epsilon), \vert \epsilon \vert \leq \meps, \ {\rm and\ \ op}\ \in \{+, -, *, /\}. \end{equation*}

The Alternative Computational Model (ACM) assumes for the basic arithmetic operations that

\begin{equation*} \fl{ \chi\ {\rm op}\ \psi } = \frac{\chi\ {\rm op}\ \psi}{1 + \epsilon}, \vert \epsilon \vert \leq \meps, \ {\rm and\ \ op}\ \in \{+, -, *, /\}. \end{equation*}

Definition 6.6.2.2. Backward stable implementation.

Given the mapping \(f: D \rightarrow R \text{,}\) where \(D \subset \Rn \) is the domain and \(R \subset \Rm \) is the range (codomain), let \(\check f: D \rightarrow R \) be a computer implementation of this function. We will call \(\check f \) a backward stable (also called "numerically stable") implementation of \(f \) on domain \({\mathcal D} \) if for all \(x \in D \) there exists a \(\check x \) "close" to \(x \) such that \(\check f( x ) = f( \check x ) \text{.}\)

Conditioning is a property of the problem you are trying to solve. A problem is well-conditioned if a small change in the input is guaranteed to only result in a small change in the output. A problem is ill-conditioned if a small change in the input can result in a large change in the output.
Stability is a property of an implementation. If the implementation, when executed with an input always yields an output that can be attributed to slightly changed input, then the implementation is backward stable.

Definition 6.6.2.3. Absolute value of vector and matrix.

Given \(x \in \Rn \) and \(A \in \Rmxn \text{,}\)

\begin{equation*} \vert x \vert = \left( \begin{array}{c} \vert \chi_0 \vert \\ \vert \chi_1 \vert \\ \vdots \\ \vert \chi_{n-1} \vert \end{array} \right) \quad \mbox{and} \quad \vert A \vert = \left( \begin{array}{c c c c} \vert \alpha_{0,0} \vert \amp \vert \alpha_{0,1} \vert \amp \dots \amp \vert \alpha_{0,n-1} \vert \\ \vert \alpha_{1,0} \vert \amp \vert \alpha_{1,1} \vert \amp \dots \amp \vert \alpha_{1,n-1} \vert \\ \vdots \amp \vdots \amp \ddots \amp \vdots \\ \vert \alpha_{m-1,0} \vert \amp \vert \alpha_{m-1,1} \vert \amp \dots \amp \vert \alpha_{m-1,n-1} \vert \end{array} \right)\!. \end{equation*}

Definition 6.6.2.4.

Let \(\vartriangle \in\!\{\lt, \leq, =, \geq, >\}\) and \(x, y \in \Rn \text{.}\) Then

\begin{equation*} \vert x \vert \! \vartriangle \! \vert y \vert \quad \mbox{iff} \quad \vert \chi_i \vert \! \vartriangle \! \vert \psi_i \vert, \end{equation*}

with \(i = 0, \ldots, n-1 \text{.}\) Similarly, given \(A\) and \(B \in \Rmxn \text{,}\)

\begin{equation*} \vert A \vert \! \vartriangle \! \vert B \vert \quad \mbox{iff} \quad \vert \alpha_{ij} \vert\!\vartriangle\!\vert \beta_{ij} \vert , \end{equation*}

with \(i = 0, \ldots, m-1 \) and \(j = 0, \ldots, n-1 \text{.}\)

Theorem 6.6.2.5.

Let \(A, B \in \Rmxn \text{.}\) If \(\vert A \vert \leq \vert B \vert \) then \(\| A \|_1 \leq \| B \|_1 \text{,}\) \(\| A \|_\infty \leq \| B \|_\infty \text{,}\) and \(\| A \|_F \leq \| B \|_F \text{.}\)

Consider

\begin{equation*} \kappa \becomes x^T y = \left( \begin{array}{c} \chi_0 \\ \chi_1 \\ \vdots \\ \chi_{n-2} \\ \chi_{n-1} \end{array} \right)^T \left( \begin{array}{c} \psi_0 \\ \psi_1 \\ \vdots \\ \psi_{n-2} \\ \psi_{n-1} \end{array} \right) = \Big( \big( ( \chi_0 \psi_0 + \chi_1 \psi_1 ) + \cdots \big) + \chi_{n-2} \psi_{n-2} \Big) + \chi_{n-1} \psi_{n-1}. \end{equation*}

Under the computational model given in Subsection 6.2.3 the computed result, \(\check \kappa \text{,}\) satisfies

\begin{equation*} \check \kappa = \sum_{i=0}^{n-1} \left( \chi_i \psi_i ( 1 + \epsilon_{*}^{(i)} ) \prod_{j=i}^{n-1} ( 1 + \epsilon_{+}^{(j)} ) \right) , \end{equation*}

where \(\epsilon_{+}^{(0)} = 0 \) and \(\vert \epsilon_{*}^{(0)} \vert , \vert \epsilon_{*}^{(j)} \vert, \vert \epsilon_{+}^{(j)} \vert \leq \meps \) for \(j = 1, \ldots , n-1 \text{.}\)

Lemma 6.6.2.6.

Let \(\epsilon_i \in \mathbb{R}\text{,}\) \(0\leq i\leq n-1\text{,}\) \(n \meps \lt 1 \text{,}\) and \(\vert \epsilon_i \vert \leq \meps\text{.}\) Then \(\exists\ \theta_{n} \in \mathbb{R}\) such that

\begin{equation*} \prod_{i=0}^{n-1} (1 + \epsilon_i)^{\pm 1} = 1 + \theta_{n}, \end{equation*}

with \(\vert \theta_n \vert \leq {n \meps}/{(1 - n \meps)} \text{.}\)

Here the \(\pm 1 \) means that on an individual basis, the term is either used in a multiplication or a division. For example

\begin{equation*} (1 + \epsilon_0)^{\pm 1} (1 + \epsilon_1)^{\pm 1} \end{equation*}

might stand for

\begin{equation*} (1 + \epsilon_0) (1 + \epsilon_1) ~~~\mbox{ or }~~~ \frac{(1 + \epsilon_0)}{(1 + \epsilon_1)} ~~~\mbox{ or }~~~ \frac{(1 + \epsilon_1)}{(1 + \epsilon_0)} ~~~\mbox{ or }~~~ \frac{1}{(1 + \epsilon_1)(1 + \epsilon_0)} \end{equation*}

so that this lemma can accommodate an analysis that involves a mixture of the Standard and Alternative Computational Models (SCM and ACM).

Definition 6.6.2.7.

For all \(n \geq 1 \) and \(n \meps \lt 1\text{,}\) define

\begin{equation*} \displaystyle \gamma_n = {n \meps}/{(1 - n \meps)}\text{.} \end{equation*}

simplifies to

\begin{equation*} \begin{array}{l} \check \kappa \\ ~~~=~~~~\\ \chi_0 \psi_0 ( 1 + \theta_n ) + \chi_1 \psi_1 ( 1 + \theta_n ) + \cdots + \chi_{n-1} \psi_{n-1} ( 1 + \theta_2 ) \\ % \label{eqn:dot3b} \\ ~~~=~~~~\\ \left( \begin{array}{c} \chi_0 \\ \chi_1 \\ \chi_2 \\ \vdots \\ \chi_{n-1} \end{array} \right)^T \left( \begin{array}{c c c c c} ( 1 + \theta_n ) \amp 0 \amp 0\amp \cdots \amp 0 \\ 0 \amp ( 1 + \theta_n ) \amp0 \amp \cdots \amp 0 \\ 0 \amp 0 \amp ( 1 + \theta_{n-1} ) \amp \cdots \amp 0 \\ \vdots \amp\vdots \amp\vdots \amp\ddots \amp \vdots \\ 0 \amp 0 \amp 0 \amp \cdots \amp ( 1 + \theta_{2} ) \end{array} \right) \left( \begin{array}{c} \psi_0 \\ \psi_1 \\ \psi_2 \\ \vdots \\ \psi_{n-1} \end{array} \right) \\ %\nonumber ~~~=~~~~\\ \left( \begin{array}{c} \chi_0 \\ \chi_1 \\ \chi_2 \\ \vdots \\ \chi_{n-1} \end{array} \right)^T \left( I + \left( \begin{array}{c c c c c} \theta_n \amp 0 \amp 0\amp \cdots \amp 0 \\ 0 \amp \theta_n \amp0 \amp \cdots \amp 0 \\ 0 \amp 0 \amp \theta_{n-1} \amp \cdots \amp 0 \\ \vdots \amp\vdots \amp\vdots \amp\ddots \amp \vdots \\ 0 \amp 0 \amp 0 \amp \cdots \amp \theta_{2} \end{array} \right) \right) \left( \begin{array}{c} \psi_0 \\ \psi_1 \\ \psi_2 \\ \vdots \\ \psi_{n-1} \end{array} \right), \end{array} \end{equation*}

where \(\vert \theta_j \vert \leq \gamma_j \text{,}\) \(j = 2, \ldots, n \text{.}\)

Lemma 6.6.2.8.

If \(n, b \geq 1 \) then \(\gamma_{n} \leq \gamma_{n+b} \) and \(\gamma_n + \gamma_{b} + \gamma_n \gamma_b \leq \gamma_{n+b} \text{.}\)

Theorem 6.6.2.9.

Let \(x,y \in \mathbb{R}^n\) and let \(\kappa := x^T y\) be computed in the order indicated by

\begin{equation*} ( \cdots ( ( \chi_0 \psi_0 + \chi_1 \psi_1 ) + \chi_2 \psi_2 ) + \cdots ) + \chi_{n-1} \psi_{n-1}. \end{equation*}

Then

\begin{equation*} \check \kappa = \big[ x^T y\big] = x^T ( I + \Sigma^{(n)} ) y. \end{equation*}

Corollary 6.6.2.10.

Under the assumptions of Theorem 6.6.2.9 the following relations hold:

R-1B: \(\check \kappa = ( x + \deltax )^T y \text{,}\) where \(\vert \deltax \vert \leq \gamma_n \vert x \vert \text{,}\)
R-2B: \(\check \kappa = x^T ( y + \deltay ) \text{,}\) where \(\vert \deltay \vert \leq \gamma_n \vert y \vert \text{;}\)
R-1F: \(\check \kappa = x^T y + \delta\!\kappa \text{,}\) where \(\vert \delta\!\kappa \vert \leq \gamma_n \vert x \vert^T \vert y \vert \text{.}\)

Theorem 6.6.2.11.

Error results for matrix-vector multiplication. Let \(A \in \Rmxn \text{,}\) \(x \in \Rn \text{,}\) \(y \in \Rm \) and consider the assignment \(y \becomes A x \) implemented via dot products as expressed in (6.3.4). Then these equalities hold:

R-1B: \(\check y = ( A + \Delta\!A) x \text{,}\) where \(\vert \Delta\!A \vert \leq \gamma_{n} \vert A \vert \text{.}\)
R-1F: \(\check y = A x + \deltay \text{,}\) where \(\vert \deltay \vert \leq \gamma_{n} \vert A \vert \vert x \vert \text{.}\)

Theorem 6.6.2.12. Forward error for matrix-matrix multiplication.

Let \(C \in \Rmxn \text{,}\) \(A \in \Rmxk \text{,}\) and \(B \in \Rkxn \) and consider the assignment \(C \becomes A B \) implemented via matrix-vector multiplication. Then there exists \(\Delta\!C \in \Rmxn \) such that

: \(\check C = A B + \Delta\!C \text{,}\) where \(\vert \Delta\!C \vert \leq \gamma_{k} \vert A \vert \vert B \vert \text{.}\)

Lemma 6.6.2.13.

Let \(n \geq 1 \text{,}\) \(\lambda, \nu \in \R \) and \(x, y \in \Rn \text{.}\) Assume \(\lambda \neq 0\) and consider the computation

\begin{equation*} \nu := ( \alpha - x^T y ) / \lambda, \end{equation*}

Then

\begin{equation*} ( \lambda + \delta\!\lambda) \check \nu = \alpha - ( x + \delta\!x )^T y , \mbox{ where } \vert \delta\!\lambda \vert \leq \gamma_2\vert \lambda \vert \mbox{ and } \vert \delta\!x \vert \leq \gamma_n \vert x \vert . \end{equation*}

Theorem 6.6.2.14.

Let \(L \in \Rnxn \) be a nonsingular lower triangular matrix and let \(\check x \) be the computed result when executing Figure 6.4.1.1 to solve \(L x = y \) under the computation model from Subsection 6.2.3. Then there exists a matrix \(\Delta\!L \) such that

\begin{equation*} ( L + \Delta\!L ) \check x = y \mbox{ where } \vert \Delta\!L \vert \leq \max( \gamma_2, \gamma_{n-1} ) \vert L \vert. \end{equation*}

Corollary 6.6.2.15.

\begin{equation*} ( L + \Delta\!L ) \check x = y \mbox{ where } \vert \Delta\!L \vert \leq \gamma_n \vert L \vert. \end{equation*}

Theorem 6.6.2.16. Backward error of Crout variant for LU factoriztion.

Let \(A \in \Rnxn \) and let the LU factorization of \(A \) be computed via the Crout variant, yielding approximate factors \(\check L \) and \(\check U \text{.}\) Then

\begin{equation*} ( A + \Delta \!\!\ A ) = \check L \check U \quad \mbox{with} \quad \vert \Delta\!\!A \vert \leq \gamma_n \vert \check L \vert \vert \check U \vert. \end{equation*}

Theorem 6.6.2.17.

Let \(A \in \Rnxn \)and \(x,y \in \Rn \) with \(A x = y \text{.}\) Let \(\check x \) be the approximate solution computed via the following steps:

Compute the LU factorization, yielding approximate factors \(\check L\) and \(\check U \text{.}\)
Solve \(\check L z = y \text{,}\) yielding approximate solution \(\check z \text{.}\)
Solve \(\check U x = \check z \text{,}\) yielding approximate solution \(\check x \text{.}\)

Then

\begin{equation*} ( A + \Delta \!\! A) \check x = y \quad \mbox{with} \quad \vert \Delta \!\! A \vert \leq ( 3 \gamma_n + \gamma_n^2 ) \vert \check L \vert \vert \check U \vert. \end{equation*}

Theorem 6.6.2.18.

Let \(A \) and \(A + \Delta\! A \) be nonsingular and

\begin{equation*} A x = y \mbox{ and } ( A + \Delta\!A ) ( x + \delta\!x ) = y \end{equation*}

then

\begin{equation*} \frac{\| \delta\!x \|}{\| x \|} \leq \frac{\kappa( A ) \frac{\| \Delta\!A \|}{\| A \|}} {1 - \kappa( A ) \frac{\| \Delta\!A \|}{\| A \|}}. \end{equation*}

Theorem 6.6.2.19.

Let \(A \) be nonsingular, \(\| \cdot \| \) be a subordinate norm, and

\begin{equation*} \frac{\| \Delta\!A \|}{\| A \|} \lt \frac{1}{\kappa( A )}. \end{equation*}

Then \(A + \Delta\!A \) is nonsingular.

An important example that demonstrates how LU with partial pivoting can incur "element growth":

\begin{equation*} A = \left( \begin{array}{r r r r r r} 1 \amp 0 \amp 0 \amp \cdots \amp 0 \amp 1 \\ -1 \amp 1 \amp 0 \amp \cdots \amp 0 \amp 1 \\ -1 \amp -1 \amp 1 \amp \cdots \amp 0 \amp 1 \\ \vdots \amp \vdots \amp \vdots \amp \ddots \amp \vdots \amp \vdots \\ -1 \amp -1 \amp \amp \cdots \amp 1 \amp 1 \\ -1 \amp -1 \amp \amp \cdots \amp -1 \amp 1 \\ \end{array} \right). \end{equation*}