Section 1.3 Compensated Summation
As mentioned above, the growth of the round-off error in the Euler method is due to the increase of the number of summands as \(h\) decreases. The problem of accumulation of round-off errors in summations with a large number of summands can be greatly reduced by using the Kahan summation algorithm, also known as compensated summation. In this method, in order to sum \(n\) elements of the array \(X = [x(1),\dots,x(n)]\text{,}\) we use the following algorithm:
s=0; e=0;
for i = 1:n
temp = s
y = x(i) + e
s = temp + y
e = (temp-s) + y
end
As an example, we sum the components of
\begin{equation*}
X = [10.0,0.23,0.44]
\end{equation*}
first in the naif way and then with the compensated algorithm way in the 3-digits decimal floating-point system \(D_3\). The exact sum is \(10.67\text{,}\) that approximates to \(10.7\) after dropping the 4-th digit. In the naif summations following the index order, though, we do not get the correct result:
s = x(1) + x(2) = 10.0 + 0.23 = 10.2
s = s + x(3) = 10.2 + 0.44 = 10.64 = 10.6
Using the compensated algorithm, instead, we do:
temp = s = 0
y = x(1) + e = 10.0 + 0
s = temp + y = 0 + 10.0 = 10.0
e = (temp - s) + y = (0-10.0) + 10.0 = 0
temp = s = 10.0
y = x(2) + e = 0.23 + 0 = 0.23
s = temp + y = 10.0 + 0.23 = 10.2
e = (temp-s) + y = (10.0-10.2) + 0.23 = -0.2 + 0.23 = 0.03
temp = s = 10.2
y = x(3) + e = 0.44 + 0.03 = 0.47
s = temp + y = 10.2 + 0.47 = 10.67 = 10.7
e = (temp-s) + y = (10.2-10.7) + 0.47 = -0.03.
In short, in the variable \(e\) is kept the quantity that is discarded in the sum and then this quantity is added to the new summand.