On Rates of Convergence in Metric Fixed Point Theory

Briseid, Eyvind Martol (2009)
On Rates of Convergence in Metric Fixed Point Theory.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

URL / URN: urn:nbn:de:tuda-tuprints-19663

Kurzbeschreibung (Abstract)

This thesis investigates some effective and quantitative aspects of metric fixed point theory in the light of methods from proof theory. The thesis consists of contributions to the program of proof mining, as developed by Kohlenbach and various collaborators since the early 1990s (but with roots back to Kreisel's program "unwinding of proofs" from the 1950s). The contributions involve both case studies - studying given prima facie ineffective proofs of certain fixed point theorems to extract "hidden" effective information like explicit bounds and rates of convergence for iteration sequences, and also developing further the use of the logical machinery involved. The main theoretical tools involve Gödel's functional ("Dialectica") interpretation combined with negative translation and a variant of Howard's majorizability relation - and specically the logical metatheorems of Kohlenbach and Gerhardy, where the reach of these techniques is extended to formal systems for analysis with various abstract spaces added as new ground types. The main contributions of the thesis are twofold: (1) We construct explicit and effective full rates of convergence for the Picard iteration sequences for two classes of selfmaps on metric spaces. One of these are Kirk's asymptotic contractions, and as a byproduct of the logical analysis we obtain a string of results concerning this class of mappings, including a characterization on nonempty, bounded, complete metric spaces as exactly the mappings for which there exists a point to which all Picard iteration sequences converge with a rate of convergence which is uniform in the starting point. This shows that in the setting of bounded metric spaces the asymptotic contractions in the sense of Kirk in some sense are the most general mappings which still exhibit convergence of the Picard iteration sequences of "Banach type" - to the same point and with strong uniformity with respect to the starting point. The other class of mappings for which we construct explicit rates of convergence are the so-called uniformly continuous uniformly generalized p-contractive mappings. Logical analysis of the concepts involved - using monotone functional interpretation - allows us to develop an extension of a related fixed point theorem from the case where the space is compact to arbitrary metric spaces. This is possible because monotone functional interpretation automatically leads us to consider the "right" uniform version of the corresponding contractive type condition - whereas in the proof of the original theorem the compactness of the space "secretly" upgrades the generalized contractive condition in question to this uniform version. Also in this case we were able to give an effective and highly uniform rate of convergence for the Picard iteration sequences, and by the uniformity features of the resulting rate of convergence it follows that the mappings under consideration are asymptotic contractions in the sense of Kirk. (2) We develop a method for finding, under general conditions, explicit and highly uniform rates of convergence for the Picard iteration sequences for selfmaps on bounded metric spaces from ineffective proofs of convergence to a unique fixed point. We are able to extract full rates of convergence by extending the use of a logical metatheorem due to Kohlenbach. Our novel method provides an explanation in logical terms for the fact that we in the case studies mentioned above could find such explicit rates of convergence. This amounts, loosely speaking, to general conditions under which we in this specic setting can transform a $\forall\exists\forall$-sentence into a $\forall\exists$-sentence via an argument involving product spaces. This reduction in logical complexity allows us to use the existing machinery to extract quantitative bounds of the sort we need.

Typ des Eintrags:

Dissertation

Erschienen:

2009

Autor(en):

Briseid, Eyvind Martol

Art des Eintrags:

Erstveröffentlichung

Titel:

On Rates of Convergence in Metric Fixed Point Theory

Sprache:

Englisch

Referenten:

Kohlenbach, Prof. Dr. U. ; Kirk, Prof. Dr. W. A. ; Streicher, Prof. Dr. T.

Publikationsjahr:

24 November 2009

Ort:

Darmstadt

Verlag:

Technische Universität

Datum der mündlichen Prüfung:

20 Oktober 2009

URL / URN:

urn:nbn:de:tuda-tuprints-19663

Kurzbeschreibung (Abstract):

Alternatives oder übersetztes Abstract:

Alternatives Abstract

Sprache

Diese Dissertation untersucht effektive und quantitative Aspekte metrischer Fixpunkttheorie mit Hilfe von Methoden der Beweistheorie. Sie besteht aus Beiträgen zum "proof mining"-Programm, entwickelt von Kohlenbach und anderen seit Anfang der 1990er Jahre, welches seinerseits seine Ursprünge in Kreisels "unwinding of proofs"-Programm aus den 1950er Jahren hat. Wir untersuchen prima facie ineffektive Beweise bestimmter Fixpunkttheoreme, um ihnen "versteckte" effektive Informationen, wie zum Beispiel explizite Schranken und Konvergenzraten für Iterationsfolgen, zu entnehmen. Darüber hinaus entwickeln wir die Anwendung der logischen Methoden weiter. Die wichtigsten theoretischen Methoden umfassen Gödels Funktionalinterpretation ("Dialectica") kombiniert mit Negativübersetzung und einer Variante von Howards Majorisierbarkeit, sowie logische Metatheoreme von Kohlenbach und Gerhardy. Diese erweitern die Anwendung der zuerst genannten Techniken auf formale Systeme der Analysis, die verschiedene abstrakte Räume als neu hinzugefügte Grundtypen besitzen. Die zwei wichtigsten Beiträgen sind die folgenden: (1) Wir konstruieren explizite und effektive Konvergenzraten für die Picard-Iterationsfolgen von zwei Klassen von Selbstabbildungen auf metrischen Räumen. Die eine Klasse sind Kirks asymptotische Kontraktionen. Als Konsequenz der logischen Analysen erhalten wir außerdem eine Reihe qualitative Ergebnisse bezüglich dieser Klasse von Abbildungen. Insbesondere beweisen wir eine Charakterisierung der Klasse der asymptotischen Kontraktionen im Sinne von Kirk für den Fall nichtleerer beschränkter, vollständiger metrischer Räume als genau denjenigen Abbildungen, für welche es einen Punkt gibt, gegen den alle Picard-Iterationsfolgen mit einer Konvergenzrate konvergieren, die gleichmäßig bezüglich des Startpunkts ist. Dies zeigt, dass im Falle von beschränkten metrischen Räumen die asymptotischen Kontraktionen im Sinne von Kirk in gewissem Sinne die allgemeinsten Abbildungen sind, die noch eine Konvergenz der Picard-Iterationsfolgen vom "Banach-Typ" aufweisen, das heißt Konvergenz gegen einen einzelnen Punkt und mit starker Gleichmäßigkeit bezüglich des Startpunktes. Die andere Klasse von Abbildungen, für die wir explizte Konvergenzraten konstruiren, sind die sogenannten gleichmäßig stetigen gleichmäßig verallgemeinerten p-kontraktiven Abbildungen. Es gelingt uns, ein verwandtes Fixpunkttheorem zu erweitern, bei dem wir nicht länger die Kompaktheit des Raumes (X, d) fordern. Aus den Gleichmäßigkeitseigenschaften der Konvergenzrate folgt, dass diese Abbildungen asymptotische Kontraktionen im Sinne von Kirk sind. (2) Wir entwickeln Methoden, um unter allgemeinen Bedingungen explizite und stark gleichmäßige Konvergenzraten für die Picard-Iterationsfolge von Selbstabbildungen auf beschränkten metrischen Räumen aus ineffektiven Beweisen von Konvergenz gegen einen eindeutigen Fixpunkt zu entnehmen. Wir können volle Konvergenzraten extrahieren, indem wir die Anwendung eines logischen Metatheorems von Kohlenbach erweitern. Unsere neuartigen Methode liefert eine metamathematische Erklärung für die Tatsache, dass wir in den oben erwähnten Fallstudien solche expliziten Konvergenzraten finden konnten. Dies kommt allgemeinen Bedingungen gleich, unter denen wir in bestimmten Zusammenhängen $\forall\exists\forall$-Sätze mit Hilfe eines Arguments über Produkträume zu $\forall\exists$-Sätzen umformen können. Diese Vereinfachung der logischen Komplexität erlaubt es uns, die vorhandenen Methoden zu nutzen, um quantitative Schranken, wie wir sie brauchen, zu bestimmen.

Deutsch

Sachgruppe der Dewey Dezimalklassifikatin (DDC):

500 Naturwissenschaften und Mathematik > 510 Mathematik

Fachbereich(e)/-gebiet(e):

04 Fachbereich Mathematik > Logik
04 Fachbereich Mathematik

Hinterlegungsdatum:

24 Nov 2009 16:46

Letzte Änderung:

05 Mär 2013 09:28

PPN:

Referenten:

Kohlenbach, Prof. Dr. U. ; Kirk, Prof. Dr. W. A. ; Streicher, Prof. Dr. T.