Testing linear operators

The goal of testing is to determine whether an implementation linear operatorA conforms to a specification linear operatorS within a given error bound for all elements from an input setF. Suppose that an upper boundK on the norm of the difference ofS andA is given a priori. Then it is shown that in general any finite number of tests is inconclusive both in the worst case and on the average. However, the testing problem is still decidable in the limit for an arbitraryK; there is an algorithm of an infinite sequence of test-and-guess such that all but finitely many guesses are correct. On the other hand, if the error bound is relaxed for weak conformance then finite tests suffice even in the worst case and tight lower and upper bounds on the number of tests are derived. The test set is universal; it only depends on the set of valid inputsF. Furthermore, the test elements are on the boundary ofF. Two examples are used to illustrate the approaches and the paper is concluded with comments on two related problems: computation and verification.This work was done while consulting at AT&T Bell Laboratories, and is partially supported by the National Science Foundation grant IRI-92-12597 and the Air Force Office of Scientific Research 91-0347.