Some Refined Error Estimates

Let the rounding mode be RN. Assume no overflow occurs. Then if you do recursive summation, the following inequality related to the error bound holds:

\begin{equation*} \left|s-\sum a_{i}\right|\le(n-1)\mathbf{u}\sum|a_{i}| \end{equation*}

The proof for this is via induction. It is trivially true for \(n=1\). Assume it is true up to \(n-1\). Define \(r_{k}\) to be the result of summing up to \(a_{k}\) using the algorithm (i.e. with all the errors). Let \(s_{k}\) be the exact partial sum. And let \(\tilde{s}_{k}=|a_{1}|+\cdots+|a_{k}|\).

Now define:

\begin{equation*} \delta=\RN(r_{n-1}+a_{n})-(r_{n-1}+a_{n}) \end{equation*}

Now

\begin{equation*} \left|r_{n}-s_{n}\right|=|\RN(r_{n-1}+a_{n})-s_{n}| \end{equation*}

which is the same as

\begin{equation*} \left|r_{n}-s_{n}\right|=|\delta+(r_{n-1}+a_{n})-(s_{n-1}+a_{n})| \end{equation*}

Expanding and using the triangle inequality:

\begin{equation*} \left|r_{n}-s_{n}\right|\le|\delta|+|r_{n-1}-s_{n-1}| \end{equation*}

Using the inductive assumption:

\begin{equation*} \left|r_{n}-s_{n}\right|\le|\delta|+(n-2)\mathbf{u}\tilde{s}_{n-1} \end{equation*}

Now note that \(|\delta|\le|a_{n}|\). Spend a few minutes convincing yourself of this! \(\delta\le\beta^{e-p+1}\) for some \(e\), and \(a_{n}\) will either share the same \(e\), or will be of \(e-1\). Work from there.

Also, \(\left|\frac{\delta}{r_{n-1}+a_{n}}\right|\le \mathbf{u}\) - this follows from the standard model.

Now consider two cases:

Case I:

If \(|a_{n}|\le \mathbf{u}\tilde{s}_{n-1}\), then use \(|\delta|\le|a_{n}|\) and just plug into the expression of \(\left|r_{n}-s_{n}\right|\) above to complete the proof.

Case II:

We assume \(|a_{n}|>\mathbf{u}\tilde{s}_{n-1}\)

We have:

\begin{equation*} \left|r_{n}-s_{n}\right|\le|\delta|+(n-2)\mathbf{u}\tilde{s}_{n-1} \end{equation*}

(just copied the equation above).

But \(\left|\frac{\delta}{r_{n-1}+a_{n}}\right|\le \mathbf{u}\)

Manipulating and inserting, we get

\begin{equation*} \left|r_{n}-s_{n}\right|\le \mathbf{u}|r_{n-1}+a_{n}|+(n-2)\mathbf{u}\tilde{s}_{n-1} \end{equation*}

Now consider the first term on the RHS:

\begin{equation*} \left|r_{n-1}+a_{n}\right|\le|r_{n-1}-s_{n-1}|+|s_{n-1}-a_{n}| \end{equation*}

Using the inductive assumption, we get:

\begin{equation*} \left|r_{n-1}+a_{n}\right|\le(n-2)\mathbf{u}\tilde{s}_{n-1}+\tilde{s}_{n} \end{equation*}

Using the assumption for Case II:

\begin{equation*} \left|r_{n-1}+a_{n}\right|\le(n-2)|a_{n}|+\tilde{s}_{n} \end{equation*}

Plugging this back in, we complete the proof.

Now it has been shown that for dot products, assuming no over/under flow, and with round to nearest:

\begin{equation*} \left|r-\sum a_{i}\cdot b_{i}\right|\le n\mathbf{u}\sum|a_{i}\cdot b_{i}| \end{equation*}

And for the naive Horner’s rule for polynomial evaluation (order \(n\))

\begin{equation*} \left|r(x)-p(x)\right|\le2n\mathbf{u}\sum|a_{i}|\cdot|x|^{i} \end{equation*}

as long as \(n<1/\sqrt{\mathbf{u}}\).