# Compute algorithmic error for incremental ratio using computational graph

Intro

I am reading an exercise in which the inherent, analytic and algorithmic errors are obtained when computing an approximation of the derivative using the incremental ratio.

Definitions

First let me recall the definition of the errors listed above. Let us choose a function $f(x)\colon \mathbb{R}^n \to \mathbb{R}$ which we want to compute, and, since the machine operations $+, -, \cdot \text{and} /$ make the computer able to calculate rational functions, let us denote with $g \colon \mathbb{R}^n \to \mathbb{R}$ a rational approximation of $f$. Let $\tilde{g}$ be the internal computer version of the rational function $g$. For $x$ real number we denote with $\tilde{x}$ its machine number representation.

We call total error the quantity \begin{equation*} \varepsilon_{\text{tot}} := \frac{\tilde{g}(\tilde{x}) - f(x)}{f(x)}. \end{equation*}

We call inherent error \begin{equation*} \varepsilon_{\text{in}} := \frac{f(\tilde{x}) - f(x)}{f(x)}. \end{equation*}

Analytic error \begin{equation*} \varepsilon_{\text{an}} := \frac{g(\tilde{x}) - f(\tilde{x})}{f(\tilde{x})}. \end{equation*}

Algorithmic error \begin{equation*} \varepsilon_{\text{alg}} := \frac{\tilde{g}(\tilde{x}) - g(\tilde{x})}{g(\tilde{x})}. \end{equation*}

The problem

In our specific problem we introduce a function $\phi \colon \mathbb{R} \to \mathbb{R}$ derivable in $x \in \mathbb{R}$. And we define $f(x) := \phi'(x)$. Our $g$ is the function \begin{equation*} \frac{\phi(x+h)-\phi(x)}{h} \end{equation*} for a fixed $h > 0$. We want to study the errors above as function of $x, \phi$ and $h$.

With a first order Taylor expansion we find that $$\label{inherent} \varepsilon_{\text{in}} \doteq \frac{(\tilde{x} - x) \phi''(x)}{\phi'(x)}$$

and again with Taylor we find that \begin{equation*} \left\vert \varepsilon_{\text{an}}\right\vert \leq \frac{h\left\Vert \phi''\right\Vert_{\infty}}{2 \left\vert \phi'(x)\right\vert}. \end{equation*}

My book says that the following holds \begin{equation*} \left\vert \varepsilon_{\text{alg}}\right\vert \dot{\leq} \left(3 + \frac{2 \left\Vert \phi\right\Vert_{\infty}}{h \left\vert \phi'(x)\right\vert}\right)u, \end{equation*} where $u$ is the machine precision.

The book says that the last formula can be obtained following the computational graph in the figure. Can someone please explain me how to get the result? With or without the computational graph (but preferably with). Thank you.

In the caption of the figure the term "amplification factor" is used. Let me recall how it is defined.

Let \begin{equation*} \epsilon_i := \frac{\tilde{x_i} - x_i}{x_i}, \end{equation*} then $$\label{sum} \varepsilon_{\text{in}} \doteq \sum_{i = 1}^n c_i \epsilon_i,$$ where the $c_i$ (called the amplification factors) are defined as \begin{equation*} c_i := \frac{x_i}{f(x)}\frac{\partial f}{\partial x_i}(x). \end{equation*} Eq~\eqref{sum} can be obtained with the same first order analysis which led to eq~\eqref{inherent}, or if you prefer,~\eqref{inherent} can obtained just applying eq~\eqref{sum}.

Conlusions

Just for sake of completeness, this example shows that the best $h$ is not the smaller, but there is a tradeoff between the analytic and the algorithmic errors. The best $h$ can be then found minimising the sum of those errors. I attached a figure with a simulation showing what is happening.

• Can someone fix the eqrefs? Not sure what happened – Nisba Jan 20 '18 at 17:19