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