Prove $\frac{S_n-\hat{S}_n}{S_n}$ is bounded by $2\epsilon n$ Let $a_1, ..., a_n$ be a list of positive real numbers, and let $S_n =\sum_{i=1}^{n} a_i$. To focus on the error propagation
due to addition, we will use the following model of 
oating-point addition: $x\dotplus y = \mathrm{fl}(x+y)=(1+\delta)(x+y)$, and $\hat{S}_{n+1}= \hat{S}\dotplus a_{n+1}$, where $\epsilon$ is the machine epsilon. 
Let $S_n$ be the result of evaluating the sum
with naive summation, i.e. letting  $\hat{S}_{k+1} = \hat{S}_k \dotplus a_{k+1}$ for $k = 1, ..., n-1.$ Also, assume that $n$ is small enough that $n\epsilon < 0.5$. 
I have already proved $\hat{S}_n=(a_1+a_2)\prod_{k=2}^{n}(1+\delta_k)+\sum_{i=3}^{n}a_i\prod_{k=i}^{n}(1+\delta_k)$ and $\prod_{k=1}^{n}(1+\delta_k)=1+\theta_n, |\theta_n|\le \frac{n\epsilon}{1-n\epsilon}$.
How can I prove $|{\frac{S_n-\hat{S}_n}{S_n}}|$ is bounded by $2\epsilon n$? 
Thank you all. 
 A: This result is given in Higham's paper The Accuracy of Floating Point Summation, but let's go through the argument here.
We have
\begin{align*}
\hat{S}_{n} = (a_1+a_2) \prod_{k=2}^{n} (1+\delta_k) + \sum_{i=3}^{n} \prod_{k=i}^{n} (1+\delta_{k}) = (a_1+a_2)(1 +\theta_{n-1}) + \sum_{i=3}^{n}a_{i}(1+ \theta_{n-i+1})
\end{align*}
Let $\gamma_{n} := \frac{n\epsilon}{1-n\epsilon}$, where $\epsilon$ is the unit roundoff. Then
\begin{align*}
\left|S_{n} - \hat{S}_{n} \right| 
&=
\left| (a_1+a_2)\theta_{n-1} + \sum_{i=3}^{n}a_{i}\theta_{n-i+1} \right| \\
&\le
|a_1+a_2||\theta_{n-1}| + \sum_{i=3}^{n}|a_{i}||\theta_{n-i+1}| \\
&\le
(|a_1|+|a_2|)|\gamma_{n-1}| + \sum_{i=3}^{n}|a_{i}||\gamma_{n-i+1}| \\
&\le
\gamma_{n-1}\sum_{i=1}^{n} |a_{i}|
\end{align*}
as $\gamma_{i} < \gamma_{j}$ for $i < j$ and $1-j\epsilon > 0$. Since $\gamma_{n-1} := \frac{(n-1)\epsilon}{ 1- (n-1)\epsilon}$ and you assume that $n\epsilon < 1/2$, then $\gamma_{n-1} \le n\epsilon/(1-0.5) = 2n\epsilon$, we have
\begin{align*}
\left|S_{n} - \hat{S}_{n} \right|  \le 2n\epsilon\sum_{i=1}^{n} |a_{i}|
\end{align*}
Divide both sides by $|S_{n}|$ to obtain
\begin{align*}
\frac{\left|S_{n} - \hat{S}_{n} \right|}{|S_{n}|}  \le 2n\epsilon\sum_{i=1}^{n} |a_{i}|/|S_{n}|
\end{align*}
Hence $\frac{\left|S_{n} - \hat{S}_{n} \right|}{|S_{n}|}$ is bounded by $2n\epsilon$ multiplied by the condition number of summation defined as
\begin{align*}
\mathrm{cond}(S_{n}):= \frac{\sum_{i=1}^{n}|a_{i}|}{\left| \sum_{i=1}^{n} a_{i}\right|}
\end{align*}
However, since you have assumed that all $a_{i}$ are positive, the condition number is unity, and hence
\begin{align*}
\frac{\left|S_{n} - \hat{S}_{n} \right|}{|S_{n}|}  \le 2n\epsilon
\end{align*}
