Computability of solutions of operator equations

✍ Scribed by Volker Bosserhoff

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 226 KB
• Volume: 53
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.200710006

✦ Synopsis

Abstract

We study operator equations within the Turing machine based framework for computability in analysis. Is there an algorithm that maps pairs (T, u) (where T is given in form of a program) to solutions of Tx = u ? Here we consider the case when T is a bounded linear mapping between Hilbert spaces. We are in particular interested in computing the generalized inverse T^†^u, which is the standard concept of solution in the theory of inverse problems. Typically, T^†^ is discontinuous (i. e. the equation Tx = u is ill‐posed) and hence no computable mapping. However, we will use effective versions of theorems from the theory of regularization to show that the mapping (T, T *, u, ‖T^†^u ‖) ↦ T^†^u is computable. We then go on to study the computability of average‐case solutions with respect to Gaussian measures which have been considered in information based complexity. Here, T^†^ is considered as an element of an L^2^‐space. We define suitable representations for such spaces and use the results from the first part of the paper to show that (T, T *, ‖T^†^‖) ↦ T^†^ is computable. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)