ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

14. Mathematical Aspects of Computer Science

1991 MS Classification: 41, 65, 68 Asmuss, Svetlana, University of Latvia, Latvia On optimal algorithms of approximation under imprecise information. Let X, Y, Z and W be normed spaces. We consider algorithms of approximate solution of the linear problem defined by an operator B : X ⟼ Y under information given by an operator A : X ⟼ Z. By an algorithm we mean an operator φ : Z ⟼ Y which allows us to obtain an approximation φ(A(x)) of the exact solution B(x) for x ∈ X:

x ∈ X ⟼ A(x) ∈ Z ⟼ φ(A(x)) ≈ B(x) ∈ Y.

We develope concepts and results of the theory of optimal algorithms worked out by J. F. Traub and H. Wozniakowski for the case of imprecise information, i. e. we suppose that the data z ∈ Z about x ∈ X are known to within ε > 0: ∥A(x) − z∥ ≤ ε. We investigate the error

e(φ) = sup_{x∈X_{0}} sup{∥B(x) − φ(z)∥ : ∥A(x) − z∥ ≤ ε, z ∈ Z}

on the class X_{0} = {x ∈ X : ∥T (x)∥ ≤ 1} defined by a restriction operator T : X ⟼ W and consider error optimal and central algorithms.