## Unit6.6.2Summary

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{.}$

###### Definition6.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*}
###### Definition6.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.

###### Definition6.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*}
###### Definition6.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{.}$

###### Definition6.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*}