# What is the error associated with Fornberg's algorithm?

Bengt Fornberg derived a general way to compute the weights for arbitrary finite difference schemes in two papers: his 1988 paper and (better) his 1998 paper.

What are the numerical errors associated with his approach as codified in the 1998 paper? Can the truncation and round-off errors be calculated for double precision arithmetic, or even estimated, for this particular algorithm -- and if so, how?

I understand how it is done with standard finite difference schemes that are derived from Taylor expansions, but this seems a bit more tricky, what with Lagrange polynomials and all.

• I'm not sure if this is what you're asking, but you can get the truncation errors' leading terms by substituting $f(x)=e^{\mathrm{i}\omega x}$ (Fourier transform diagonalizes finite difference schemes). Round-off errors in the explicit case would be bounded by the sum of coefficients' absolute values, and in the implicit case multiply that by the norm of the inverse of the l.h.s. matrix. Is this the sort of thing? I don't see what Lagrange polynomials have to with it. Also, his method is exact, so any CAS would give the coefficients to full precision as rational numbers. – Kirill Nov 10 '16 at 21:10
• "The Fourier transform diagonalizes finite difference schemes"? In what sense? In what cases? (I've seen that used before, but have no concrete idea what it means or how to use it.) I mentioned Lagrange polynomials because that is the basis for Fornberg's derivation. – jvriesem Nov 12 '16 at 15:11
• If you apply, e.g., $\mathcal{L}f = h^{-2}(f(x+h)-2f(x)+f(x-h))$ to $f(x)=e^{\mathrm{i}\omega x}$, you get $(-\omega^2+O(h^2))f(x)$. So if you treat $\mathcal{L}$ as a linear operator, $f$ is an eigenfunction. One possible book: people.maths.ox.ac.uk/trefethen/pdetext.html. [Right, but the Lagrange polynomials aren't involved in any error bounds, so it wasn't clear what you were asking.] – Kirill Nov 12 '16 at 15:50

## 1 Answer

It seems to me that ultimately you do not care about the numerical error in the finite-difference weights themselves, but in the numerical error you incur when you use these weights. Assessing the latter error is very simple. Just plug into your approximation constant function values. Assuming your weights approximate a derivative, you should obtain identically zero. Most likely you will not obtain exactly zero, but a value on the order of the machine precision. If your result is much larger than that, the cause might be numerical errors in the computed weights.

You can carry out this test also for higher-order functions. Assuming you have a second-order accurate approximation of the second derivative, you will have a TE that is proportional to

$h^2\dfrac{d^4 u}{dx^4}$

Now the fourth derivative of a cubic polynomial is zero, so your approximation should give you the exact second derivative if you plug in the function values of a cubic polynomial. The deviation between the exact derivative and your computed derivative is again an indication of the numerical error in your weights.

In my use of Fornberg's algorithm, I did not see any indication that errors in the numerically computed weights were significant.