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 done 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*}$