{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Numerical differentiation example"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"I'm going to try to explain the example of estimating the derivative of\n",
"$f(x)=e^x \\sin x$\n",
"at the point $a=2.2$.\n",
"\n",
"Here we are using the estimate\n",
"$$f'(a) \\approx \\frac{f(a+h) - f(a)}{h}.$$\n",
"The main difficulty is figuring out approximately what $h$ is best. There are two primary sources of error:\n",
"* Loss of precision due to subtracting numbers at a similar scale\n",
"* Mathematical error in our approximation (the difference between the actual values of $f'(a)$ and $\\frac{f(a+h) - f(a)}{h}$)\n",
"\n",
"There is a trade off here because if we were doing exact arithmetic, we'd be best off choosing $h$ very small, but choosing $h$ very small will cause much more loss of precision. We analyze these two errors separately below, and then combine the analyses to decide which $h$ is best.\n",
"\n",
"This example was discussed in the Numerical Differentiation Notebook, but I hope this discussion will more clearly explain why $h \\approx 2^{-27}$ is best."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Loss of precision"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We are using floating point numbers which have $53$ bits of precision. We are interested in the loss of precision in computing $f(a+h)-f(a)$. But a basic principle is that if $f$ is a nice function (differentiable with continuous derivative), then the loss of precision in computing $f(a+h)-f(a)$ will roughly match the loss of precision in computing in $(a+h) - a$.\n",
"\n",
"To simplify things, we'll assume that $h=2^{-k}$ with $k \\geq 0$ an integer. (We could more generally assume that $2^{-k-1} < h \\leq 2^{-k}$ and the analysis would be basically the same.)\n",
"\n",
"Because $a=2.2$ satisfies $2^1 \\leq a < 2^2$, its most significant bit is the place value $2^1$. Then the numbers $a$ and $a+2^{-k}$ will agree (roughly) in place values $2^1, 2^0, 2^{-1}, \\ldots, 2^{1-k}$ but disagree in place value $2^{-k}$. So they agree in $k+1$ bits. So, by our assumption, $f(a+h)$ and $f(a)$ also agree in about $k+1$ bits. This means that computing $f(a+h)-f(a)$ results in the loss of $k+1$ bits of precision. This means we are left with $53-(k+1)=52-k$ bits of precision.\n",
"\n",
"We can convert this to an estimate of the error. We know $f'(a)$ is between $1=2^0$ and $2=2^1$. So, the most significant bit is in the $2^0$ place value. We have $52-k$ bits of precision, and our error is on the order of the place value of the least significant bit of precision. Since $2^0$ is the place value of the most significant bit, $2^{k-51}$ is the place value of our least significant bit of precision. So, we have estimated that the error in our computation due to loss of precision is $$2^{k-51}.$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Mathematical error"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The absolute mathematical error in our estimate is\n",
"$$\\left|f'(a) - \\frac{f(a+h) - f(a)}{h}\\right|,$$\n",
"assuming we are doing exact arithmetic.\n",
"\n",
"We can understand this error through Taylor's Theorem. Applying the Taylor's theorem for the degree one Taylor polynomial gives that\n",
"$$f(a+h) = f(a) + f'(a) h + \\frac{f''(y)}{2} h^2$$\n",
"for some $y$ between $a$ and $a+h$. (The first two terms are the degree one Taylor polynomial, and the last term is the Lagrange form of the remainder.)\n",
"\n",
"Solving this expression for $f'(a)$ yields \n",
"$$f'(a) = \\frac{f(a+h)-f(a)}{h} - \\frac{f''(y)}{2} h.$$\n",
"So the absolute error in our estimate is\n",
"$$\\left|f'(a) - \\frac{f(a+h) - f(a)}{h}\\right|=\\left|\\frac{f''(y)}{2} h\\right|,$$\n",
"for some $y$ between $a$ and $a+h$. Since the interval $(a, a+h)$ is small and the second derivative is a continuous function, the second derivative doesn't vary much on the interval. We can just assume that the second derivative is a reasonable number (it works out to be about -10, but we don't need this level of detail).\n",
"\n",
"So, the mathematical error is about \n",
"$$ch = c 2^{-k}$$\n",
"where $c$ is a reasonable positive number. (We actually have $c \\approx \\frac{f''(a)}{2} \\approx 5$ in this case.)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# The best choice"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The best choice for $h$ is the value which makes the mathematical error and the error due to loss of precision about equal. (If the mathematical error is larger than the error due to loss of precision, then we can shrink $h$ and get better results. If the error due to loss of precision is larger, then we should grow $h$ to get better results.)\n",
"\n",
"So we are looking to choose a value of $k$ which makes \n",
"$$2^{k-51} \\approx c 2^{-k}.$$\n",
"Simplifying, we see that\n",
"$$2^{2k} \\approx c 2^{51}.$$\n",
"Then taking a log to base $2$, we see that\n",
"$$2k \\approx 51 + \\log_2 c$$\n",
"and\n",
"$$k \\approx 25.5 + \\frac{1}{2} \\log_2 c.$$\n",
"Ignoring the term $\\frac{1}{2} \\log_2 c$ because it is small, we can guess that the best choice for $k$ would be $k=25$ or $k=26$.\n",
"\n",
"*Remark:* We can do a bit better if we knew that $c \\approx 5$, because $\\log_2 c \\approx 2.3$ is then slightly bigger than $2$. So, we get the better approximation \n",
"$$k \\approx 25.5 + \\frac{1}{2} 2.3 \\approx 26.6,$$\n",
"which rounds up to $27$, the best value we found in the Numerical Differentation notebook. While this might seem unfair (unsing the second derivative $f''(a)$ to estimate $f'(a)$), we certainly don't need an accurate estimate of $c$, only the scale of $c$ ($\\log_2 c$) plays a role, so even a poor estimate of $f''(a)$ could be useful."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Estimate of accuracy"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's just assume we are using $k=27$ so $h=2^{-27}$ and that we know that with this choice we have at most $52-k=25$ bits of precision. We have a mathematical error of similar size, so it is more reasonable to assume we have $24$ bits of precision (i.e., we loose another bit through mathematical error). We can convert from bits of precision to digits of precision by dividing by \n",
"$$\\frac{\\log 10}{\\log 2} \\approx 3.3,$$\n",
"so we can expect to have about $7$ digits of precision. We will check that this is correct."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"# Our function and its derivative:\n",
"import math as m\n",
"def f(x):\n",
" return m.exp(x) * m.sin(x)\n",
"def df(x):\n",
" return m.exp(x) * (m.sin(x) + m.cos(x))"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1.9854604310541828"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The actual derivative\n",
"a = 2.2\n",
"der = df(a)\n",
"der"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1.9854604005813599"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Compute our estimated derivative\n",
"k = 27\n",
"h = 2**-k\n",
"est = (f(a+h) - f(a))/h\n",
"est"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Comparing the numbers above, we can see they agree to 8 digits, a bit more that our estimated 7 digits."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## General take away"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"I believe the following is a general observation you should take away from this:\n",
"\n",
"* When $a$ and $f''(a)$ are not very large, a good choice for estimating the derivative with the formula using floats $\\frac{f(a+h) - f(a)}{h}$ is $h=2^{-26}$. In greater generality, if you are doing computation with $N$-bit floating point arithmetic, then $h=2^{-N/2}$ would be a good choice.*\n",
"\n",
"If $a$ or $f''(a)$ are very large, you might have to think harder about what the best choice of $h$ would be."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.2"
}
},
"nbformat": 4,
"nbformat_minor": 4
}