Error Estimation for Indirect Measurements : Interval Computation Problem is (Slightly) Harder than a Similar Probabilistic Computational Problem

O. Kosheleva, V. Kreinovich

IBP-Laforia 1996/24: Rapport de Recherche Laforia / Laforia research reports
16 pages - Octobre/October 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Error Estimation for Indirect Measurements : Interval Computation Problem is (Slightly) Harder than a Similar Probabilistic Computational Problem

Résumé : Une des principales applications du calcul d'intervalles est l'estimation d'erreurs de mesurages indirects. Une quantité y est mesurée indirectement si l'on mesure des quantités x1,...,xn liées à y, puis que l'on estime y à partir des résultats X1,...,Xn de ces mesurages par l'intermédiaire de f(X1,...,Xn) en utilisant une fonction connue f. Les calculs d'intervalles sont utilisés pour trouver les valeurs de f(x1,...,xn) quand on sait que les xi appartiennent à des intervalles [Xi-Di,Xi+Di], où les Di sont des précisions garanties des mesurages directs. On sait que le problème correspondant est NP-difficile, même pour des fonctions polynomiales f. Dans certaines situations réelles, on connaît les probabilités des différentes valeurs de xi; en général les erreurs xi-Xi sont des variables aléatoires gaussiennes indépendantes, de moyenne nulle et de déviation standard connue si. Pour de telles situations, on peut formuler un problème probabiliste similaire : étant donné si, on calcule la déviation standard de f(x1,...,xn). Il est raisonnablement facile de montrer que ce problème est faisable pour des fonctions polynomiales f. Donc, pour un polynôme f, le problème du calcul probabiliste est plus facile que le problème du calcul d'intervalles.
Il n'est pas beaucoup plus facile. En fait, les polynômes peuvent être décrits comme des fonctions obtenues à partir de xi en appliquant l'addition, la soustraction et la multiplication. Une extension naturelle est d'ajouter la division pour obtenir des fonctions rationnelles. Nous prouvons que, pour des fonctions rationnelles, le problème du calcul probabiliste (issu de l'estimation d'erreur pour des mesurages indirects) est NP-difficile.

Abstract : One of main applications of interval computations is estimating errors of indirect measurements. A quantity y is measured indirectly if we measure some quantities x1,...,xn related to y and then estimate y from the results X1,...,Xn of these measurements as f(X1,...,Xn) by using a known relation f. Interval computations are used to find the range of f(x1,...,xn) when xi are known to belong to intervals [Xi-Di,Xi+Di], where Di are guaranteed accuracies of direct measurements. It is known that the corresponding problem is intractable (NP-hard) even for polynomial functions f.
In some real-life situations, we know the probabilities of different value of xi; usually, the errors xi-Xi are independent Gaussian random variables with 0 average and known standard deviations si. For such situations, we can formulate a similar probabilistic problem: given si, compute the standard deviation of f(x1,...,xn). It is reasonably easy to show that this problem is feasible for polynomial functions f. So, for polynomial f, the probabilistic computation problem is easier than the interval computation problem.
It is not too much easier: Indeed, polynomials can be described as functions obtained from xi by applying addition, subtraction, and multiplication. A natural expansion is to add division, thus getting rational functions. We prove that for rational functions, probabilistic computational problem (emerging from error estimation for indirect measurements) is NP-hard.

Publications internes Laforia 1996 / Laforia research reports 1996