Small errors imply large evaluation instabilities

Abstract

Numerical analysts and scientists working in applications often observe that once they improve their techniques to get a better accuracy, some instability of the evaluation creeps in through the back door. This paper shows for a large class of numerical methods that such a Trade-off Principle between error and evaluation stability is unavoidable. It is an instance of a no free lunch theorem. Here, evaluation is the mathematical map that takes input data to output data. This is independent from the numerical routine that calculates the output. Therefore, evaluation stability is different from computational stability. The setting is confined to recovery of functions from data, but it includes solving differential equations by writing such methods as a recovery of functions under constraints imposed by differential operators and boundary values.