Skip to main content

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

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

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

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