Relative error of floating point in inner product Prove that the floating point arithmetic with machine epsilon $\epsilon$ produces an inner product satisfying: $$\text{fl}(x^Ty) = x^T(y+e)$$ where $$|e_i| \leq 2n\epsilon|y_i|$$
as long as $n\epsilon < 1/2$. Under what conditions on x and y does this bound guarantee small relative error in $x^Ty$.
Can someone please show me how to do this problem because I don't know where to start?
 A: $\def\fl{\mathrm{fl}}$ The standard model for rounding error analysis uses the following assumptions: $$\fl(\alpha+\beta)=(\alpha+\beta)(1+\delta_+), \quad\fl(\alpha\beta)=\alpha\beta(1+\delta_\times), \quad |\delta_+|\leq\epsilon, \quad|\delta_\times|\leq\epsilon.$$
You can show the result is, e.g., by induction. It is easy to see that it is true for $n=1$; if $x$ and $y$ are 1-vectors (scalars), then
$$
\fl(x^Ty)=x^Ty(1+\delta), \quad |\delta|\leq\epsilon,
$$
and hence
$$
\fl(x^Ty)=x^T(y+e), \quad |e|=|\delta y|\leq \epsilon |y|\leq 2\epsilon |y|.
$$
Assume that the statement holds for $n-1$. Then if $x$ and $y$ are $n$-vectors ($n\geq 2$) and $x:=(\tilde{x}^T,x_n)^T$ and $y:=(\tilde{y}^T,y_n)^T$ are partitioned vectors $x$ and $y$ so that the tilded vectors have dimension $n-1$, respectively, we have
$$
\begin{split}
\fl(x^Ty)&=[\fl(\tilde{x}^T\tilde{y})+x_ny_n(1+\delta_\times)](1+\delta_+)
=\tilde{x}^T(\tilde{y}+\hat{e})(1+\delta_+)+x_ny_n(1+\delta_\times)(1+\delta_+)
\end{split}
$$
with $\hat{e}$ such that $\hat{e}:=(\hat{e}_1,\ldots,\hat{e}_{n-1})$ satisfies $|\hat{e}_i|\leq 2(n-1)|y_i|$, $i=1,\ldots,n-1$. So, we have to put this expression to the form $x^T(y+e)$ and cook a bound for the entries of $e$. Let $e:=(\tilde{e}^T,e_n)^T$ be the partitioning similar to that of $x$ and $y$. We have
$$
\tilde{x}^T(\tilde{y}+\hat{e})(1+\delta_+)=\tilde{x}^T(\tilde{y}+\hat{e}+\delta_+ y+\delta_+\hat{e})=:\tilde{x}^T(\tilde{y}+\tilde{e})
$$
and
$$
x_ny_n(1+\delta_\times)(1+\delta_+)=x_n(y_n+e_n), \quad
e_n:=(\delta_\times+\delta_++\delta_\times\delta_+)y_n.
$$
It remains to show that $e:=(e_1,\ldots,e_n)^T$ satisfies $|e_i|\leq 2n\epsilon|y_i|$.
We have, for $i=1,\ldots,n-1$,
$$
\begin{split}
|e_i|\leq|\hat{e}_i|+|\delta_+y_i|+|\delta_+\hat{e}_i|\leq [2(n-1)\epsilon+\epsilon+2(n-1)\epsilon^2]|y_i|\leq[2(n-1)\epsilon+2\epsilon]|y_i|
=2n\epsilon|y_i|.
\end{split}
$$
In the last inequality, we used the assumption that $2n\epsilon<1$ [and so $2(n-1)\epsilon<1$ as well], which implies that $2(n-1)\epsilon^2\leq\epsilon$ (thus eliminating the second-order term in the parentheses). The last term of the vector $e$ goes similarly:
$$
|e_n|\leq(|\delta_\times|+|\delta_\times|+|\delta_\times||\delta_+|)|y_n|
\leq (2\epsilon+\epsilon^2)|y_n|\leq 4\epsilon|y_n|\leq 2n\epsilon|y_n|.
$$
