Näherungsweise Berechnung von Nullstellen und Fixpunkten.
Letzte Woche hatten wir gesehen, daß Preis-Gleichgewichte sich als Fixpunkte bestimmter Abbildungen bestimmen lassen. Vor zwei 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. Wir werden nächste Woche einen konstruktiven Beweis des Fixpunktsatzes beschreiben, mit dem man dann also Preis-Gleichgewichte näherungsweise bestimmen kann. Heute soll es zur Einstimmung zunächst um den trivialen (und für wirtschaftswissenschaftliche Anwendungen natürlich irrelevanten) 1-dimensionalen Fall gehen.
Der 1-dimensionale Brouwersche Fixpunktsatz ist die Aussage, dass jede stetige Abbildung f:[-1,1]–>[-1,1] einen Fixpunkt hat. Er folgt einfach einfach aus dem Zwischenwertsatz, angewandt auf die Funktion g(x):=f(x)-x.
| Der Zwischenwertsatz besagt bekanntlich, daß eine stetige Funktion auf dem Intervall [a,b] alle Zwischenwerte zwischen f(a) und f(b) annimmt, im Bild rechts also zum Beispiel den Wert u.
Wenn man also zum Beispiel für f(x)=x3-2x weiß, daß f(1)>0 und f(2)<0, dann muß es zwischen 1 und 2 eine Nullstelle geben. Durch sukzessive Verkleinerung der Intervalle kann man die Nullstelle mit beliebiger Genauigkeit bestimmen. (Das ist natürlich nicht sehr effizient, in der Praxis werden bessere Verfahren zur Nullstellenbestimmung von Funktionen verwendet.) |
Der 1-dimensionale Fixpunktsatz für stetige Funktionen f:[-1,1]–>[-1,1] ergibt sich nun wie folgt aus dem Zwischenwertsatz:
Setze g(x)=f(x)-x. Wegen g(-1)>0 und g(1)<0 muss die stetige Funktion g zwischen -1 und 1 eine Nullstelle x haben. (Falls g(-1)=0 oder g(1)=0 hat man natürlich eine Nullstelle schon in -1 bzw. 1.)
Aus g(x)=0 folgt f(x)=x. x ist also ein Fixpunkt von f.
Dieser 1-dimensionale Zwischenwertsatz lasst sich leicht “diskretisieren” :
man zerlege das Intervall [-1,1] mittels Zwischenpunkten irgendwie in Teilintervalle. Jeder Zwischenpunkt werde grün oder blau gefärbt. Wenn -1 grün und 1 blau gefarbt ist, dann gibt es zwischendurch mindestens eine Stelle, wo benachbarte Punkte unterschiedliche Farben haben. (Genauer: es gibt eine ungerade Anzahl von Stellen, wo benachbarte Punkte unterschiedliche Farben haben.) Bild hier.
Den Zusammenhang zum Zwischenwertsatz bekommt man, wenn grüne Punkte die mit g(x)>0 und blaue Punkte die mit g(x)<0 sind.
Diese diskrete Version ist zugegebenerweise noch banaler als der Zwischenwertsatz selbst. Man kann sie aber zum näherungsweisen Bestimmen eines Fixpunktes verwenden: man wählt immer feinere Zerlegungen, hat in jeder dieser Zerlegungen ein Intervall mit unterschiedlich-farbigen Randpunkten, und bekommt auf diese Weise eine immer bessere Approximation fur einen Fixpunkt.
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. Dazu nächste Woche.
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
Letzte Kommentare