next up previous contents
Next: 4.1.6 Approximation of the Up: 4.1 Optimization Methods Previous: 4.1.4 Newton Direction


4.1.5 Finite-Difference Approximations of First Derivatives

For the approximation of the first derivatives finite-difference approximations can be used. The finite-differences are calculated from a number of function evaluations of particular $\vec{x}$ values. The Taylor-series approximation of the twice continuously differentiable univariate4.1 function f(x) is

f(x + h) = f(x) + h f'(x) + O(h2) . (4.11)

O(h2) represents a term of order 2 or higher. The forward-difference formula

\begin{displaymath}
\varphi_F (f,h) = \frac{f(x+h) - f(x)}{h} = f'(x) + O(h)
\end{displaymath} (4.12)

$\varphi_F (f,h)$ is the approximation of the first derivative of f(x) using the step length h. Similarly, the backward-difference approximation can be calculated by

\begin{displaymath}
\varphi_B (f,h) = \frac{f(x) - f(x-h)}{h}
.
\end{displaymath} (4.13)

The truncation error of both, the forward and backward-differences is

\begin{displaymath}
\frac{1}{2} \cdot h \cdot f''(x + \theta \cdot h)
\end{displaymath} (4.14)

where $0 \le \theta \le 1$.

For higher accuracy the central-difference approximation can be used.

Central-differences are derived from the Taylor expansion of second order

f(x + h) = $\displaystyle f(x) + h f'(x) + \frac{1}{2} h^2 f''(x) + O(h^3)$ (4.15)
f(x - h) = $\displaystyle f(x) - h f'(x) + \frac{1}{2} h^2 f''(x) + O(h^3)
.$ (4.16)

From these equations the central-difference formula

\begin{displaymath}
\varphi_C (f,h) = \frac{f(x+h) - f(x-h)}{2 h} = f'(x) + O(h^2)
\end{displaymath} (4.17)

is derived.

In this approximation the truncation error is of second order

\begin{displaymath}
\frac{1}{6} \cdot h^2 \cdot f^{(3)}(x + \theta \cdot h) ,
\end{displaymath} (4.18)

but two function evaluations around $\vec{x}$ are required.

When the target function has n independent parameters $2 \cdot n$ function evaluations are required using a central-difference approximation. If a single evaluation takes several minutes to hours the forward-difference formula is preferable to reduce the overall calculation time. To keep the error of the approximation in an acceptable range the step size is adapted for each input parameter, depending on the values of the previous iteration.



Footnotes

... univariate4.1
Here the function f(x) is assumed to be a univariate function. For multivariate functions finite differences are performed for each dimension of $\vec{x}$.

next up previous contents
Next: 4.1.6 Approximation of the Up: 4.1 Optimization Methods Previous: 4.1.4 Newton Direction

R. Plasun