What is the upper bound on the error of a matrix multiplication When both A and B are n x n upper-triangular matrices, the entries of C = AB are defined as follows:
$$
c_{ij} = \begin{cases} \sum _{k=i}^ja_{ik}b_{kj} & 1\leq i\leq j\leq n \\0 & 1\leq j\lt i\leq n \end{cases}
$$
For n = 2 show that 
$$ fl(AB) = \hat A \hat B $$ 
where 
$$ \hat A = A + E_A\\\hat B = B + E_B $$ 
Derive bounds for 
$$||E_A||, ||E_B||$$
showing that they are small relative to ||A|| and ||B||, respectively. In other words, show that the computed product is the exact product of slightly perturbed A and B.
 A: I hope a $2\times 2$ example will be enough for the start :-)
Since $\mathrm{fl}(a+b)=(a+b)(1+\delta_+)$ and $\mathrm{fl}(a\times b)=ab(1+\delta_{\times})$ for scalars $a$ and $b$, where $|\delta_+|\leq u$ and $|\delta_{\times}|\leq u$ with the unit roundoff $u$, we have
$$
\mathrm{fl}(AB)=
\begin{bmatrix}
a_{11}b_{11}(1+\delta_1) & (a_{11}b_{12}(1+\delta_2)+a_{12}b_{22}(1+\delta_3))(1+\delta_4) \\ 0 & a_{22}b_{22}(1+\delta_5)
\end{bmatrix}
$$
with $|\delta_i|\leq u$ ($i=1,\ldots,5$). This can be written as $\mathrm{fl}(AB)=\tilde{A}\tilde{B}$, where
$$
\tilde{A}=\begin{bmatrix} a_{11} & a_{12}(1+\delta_3)(1+\delta_4) \\ 0 & a_{22}(1+\delta_5)\end{bmatrix},
\quad
\tilde{B}=\begin{bmatrix} b_{11}(1+\delta_1) & b_{12}(1+\delta_2)(1+\delta_4) \\ 0 & b_{22} \end{bmatrix}.
$$
The following is used a lot in rounding error analysis: Let $|\delta_i|\leq u$, $\sigma_i=\pm 1$ for $i=1,\ldots,n$ and $nu<1$ (of course, one normally assumes that $nu$ is really much much smaller than 1). Then
$$
\prod_{i=1}^n(1+\delta_i)^{\sigma_i}=1+\epsilon_n,
$$
where either one takes just the first order approximation:
$$
|\epsilon_n|\leq nu+O(u^2),
$$
or a more precise bound:
$$
|\epsilon_n|\leq \frac{nu}{1-nu} \equiv \gamma_n.
$$
The choice depends on the personal preferences :-)
Using the above we have that $\tilde{A}=A+E_A$, $\tilde{B}=B+E_B$ with global component-wise bounds
$$
|E_A|\leq \gamma_2|A|, \quad |E_B|\leq \gamma_2|B|.
$$
From this you can already derive bounds for your norm. From the component-wise bounds it is quite easy to get a bound, e.g., for the $\infty$-norm:
$$
\|E_A\|_{\infty} = \||E_A|\|_{\infty} \leq \gamma_2\||A|\|_{\infty} = \gamma_2\|A\|_{\infty}.
$$
If you like other norms, e.g., the spectral one, you can simply use the equivalence relations $\frac{1}{\sqrt{n}}\|A\|_{\infty}\leq\|A\|_2\leq\sqrt{n}\|A\|_{\infty}$. Note that there will be an additional factor $n$ in the resulting bound though:
$$
\|E_A\|_2 \leq 2n^2u\|A\|_2 + O(u^2).
$$
Hope this helps with the general $n\times n$ case :-)
