« vorheriger Beitrag  · nächster Beitrag »

17.10.08 · 20:45 Uhr

Topologie von Flächen XXXVI

Kategorie: Politik  ·  Kommentare: 1

Preisgleichgewichte, Diskretisierungen und Sperners Lemma.

Vorletzte Woche hatten wir gesehen, daß Preis-Gleichgewichte sich als Fixpunkte bestimmter Abbildungen bestimmen lassen. Vor drei Wochen hatten wir (nach Brouwer) bewiesen, daß jede stetige Abbildung (der Kreisscheibe auf sich) einen Fixpunkt hat, es also immer ein Preis-Gleichgewicht gibt.

Der Beweis des Brouwerschen Fixpunktsatzes war allerdings nicht konstruktiv: er lieferte kein Verfahren zur (näherungsweisen) Berechnung der Fixpunkte.

Auch wenn es sich bei Preis-Gleichgewichten zunächst um ein theoretisches Konzept (und eine grobe Annäherung der Wirklichkeit handelt), gibt es durchaus Probleme, bei denen man die Gleichgewichte tatsächlich berechnen will. Z.B. schreibt Scarf: "The availability of these numerical techniques has led to the construction and solution of generalized equilibrium models designed to illustrate a variety of economical issues. Several authors have been concerned with the impact on the economies of the United States and other countries of changes in domestic taxes, international negotiations to reduce tariffs and other barriers, and the ways in which individual taxes and subsidies affect each other."

Näherungsweise Berechnungen arbeiten oft mit Diskretisierungen stetiger Probleme, d.h. zum Beispiel mit Zerlegungen von Flächen in kleinere Dreiecke. Wie letzte Woche am (trivialen) 1-dimensionalen Beispiel gezeigt.

Und auf ähnliche, aber natürlich kompliziertere Weise, kann man auch im 2-dimensionalen Problem Fixpunkte näherungsweise bestimmen. Die Rolle des (diskreten) Zwischenwertsatzes wird hier von Sperners Lemma ubernommen. Dieses besagt:

Sperners Lemma: Man habe eine beliebige Zerlegung des Dreiecks ABC in kleinere Dreiecke. Die Eckpunkte dieser Zerlegung seien mit den Farben Rot, Blau, Grün gefarbt, so dass:
- A ist Rot, B ist Blau, C ist Grün
- jeder Punkt auf der Seite AB ist Rot oder Blau, jeder Punkt auf der Seite BC ist Blau oder Grün, jeder Punkt auf der Seite CA ist Grün oder Rot.
Dann gibt es mindestens ein kleines Dreieck, dessen Ecken mit drei unterschiedlichen Farben gefärbt sind.

(Genauer: es gibt eine ungerade Zahl kleiner Dreiecke, deren Ecken mit unterschiedlichen Farben gefärbt sind.)

Einen kurzen Beweis von Sperner's Lemma findet man hier.

Aus Sperner's Lemma ergibt sich nun der Brouwer'sche Fixpunktsatz (für Dreiecke¹) und sogar eine Methode zur näherungsweisen Berechnung eines Fixpunkts.

Herleitung des Brouwerschen Fixpunktsatzes aus Sperners Lemma:

Die Idee ist: wenn eine Abbildung f auf dem Dreieck f keine Fixpunkte hat, dann muß für jeden Punkt x mindestens eine der Koordinaten von x nicht mit der entsprechenden Koordinate von f(x) übereinstimmen. (Wir rechnen jetzt mit baryzentrischen Koordinaten, d.h. A,B,C sind die Ecken des Dreiecks, (a,b,c) sind die Koordinaten von aA+bB+cC. Zum Beispiel haben A,B,C die baryzentrischen Koordinaten (1,0,0),(0,1,0) und (0,0,1).)

Man färbe Ecken x blau, wenn die erste Kordinate von f(x) kleiner ist als die von x; grün, wenn die zweite Kordinate von f(x) kleiner ist als die von x (und die erste größer); rot, wenn die dritte Kordinate von f(x) kleiner ist als die von x (und die ersten beiden größer). (Bild)

Man kann sich leicht überlegen, dass die Bedingungen aus Sperners Lemma für diese Färbung erfüllt sind.

Nun nehme man immer feinere Zerlegungen in Dreiecke, sehe sich die dazugehörige Färbung an, und bekommt nach Sperners Lemma, daß es kleine Dreiecke mit 3 unterschiedlich gefärbten Eckpunkten gibt. Die immer kleineren Dreiecke schachteln einen Punkt ein und für diesen eingeschachtelten Punkt gilt, daß keine seiner baryzentrischen Koordinaten durch f vergrößert wird (denn der Punkt ist ja gleichzeitig ein Grenzwert von blauen, grünen und roten Punkten). In baryzentrischen Koordinaten können aber nicht alle Koordinaten gleichzeitig verkleinert werden. Der eingeschachtelte Punkt muß also ein Fixpunkt sein.
o

Formaler aufgeschrieben findet man diese Herleitung hier. Ein ähnliches Verfahren zur Bestimmung der Fixpunkte funktioniert auch in höheren Dimensionen.

¹ Wenn man den Brouwer'schen Fixpunktsatz für stetige Abbildungen von Dreiecken beweist, bekommt man ihn automatisch auch für stetige Abbildungen der Kreisscheibe. Es gibt nämlich eine stetige Abbildung h von der Kreisscheibe auf das Dreieck, die eine stetige Umkehrabbildung h^-1 hat. Wenn jetzt f:D² --> D² irgendeine stetige Abbildung ist, dann ist hfh^-1 eine stetige Abbildung des Dreiecks. Wenn wir für letztere bewiesen haben, daß es einen Fixpunkt, also ein x mit hfh^-1(x)=x, gibt, dann ist y=h^-1x ein Fixpunkt von f: f(y)=fh^-1(x)=h^-1hfh^-1(x)=h^-1(x)=y.

Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13, Teil 14, Teil 15, Teil 16, Teil 17, Teil 18, Teil 19, Teil 20, Teil 21, Teil 22, Teil 23, Teil 24, Teil 25, Teil 26, Teil 27, Teil 28, Teil 29, Teil 30, Teil 31, Teil 32, Teil 33, Teil 34, Teil 35

 

Autor: Thilo· 1 Kommentar· Permalink· Trackback-URL

Tags: brouwer· diskretisierung· fixpunkt· sperner