Textversion des Videos

Transkript Picarditeration eindimensional Teil 1

Hallo. In diesem Video wollen wir uns die Picard-Iteration und den Banach'schen Fixpunktsatz angucken. Die Picard-Iteration ist ein sehr sehr einfaches Verfahren zur Bestimmung eines Fixpunktes. In diesem Video gucken wir uns dabei nur den eindimensionalen Fall an. Zunächst möchte ich noch einmal erläutern, was ein Fixpunkt überhaupt ist. Am einfachsten lässt sich dies anhand einer kleinen Zeichnung darstellen. Wir haben hier ein Koordinatensystem gegeben mit den Achsen x und y bzw. f(x). Hier haben wir jetzt eine Funktion gegeben und zeichnen uns nun die Winkelhalbierende ein. Die Winkelhalbierende, hier blau dargestellt, hat die Steigung 1 und geht durch den Ursprung. Also hat sie die Gleichung f(x)=x. Die Schnittpunkte unserer Funktion mit der Winkelhalbierenden heißen Fixpunkte dieser Funktion. Die Fixpunkte einer Funktion f sind also die Punkte, für die gilt: f(x)=x. Ausgehend von dieser Definition eines Fixpunktes können wir nun die Picard-Iteration formulieren. Wir nehmen uns einen Startwert x(0), der eine Näherung unseres Fixpunktes darstellt, und setzen den in unserer Fixpunktgleichung auf der linken Seite ein. Wir werten die Funktion f also an der Stelle x(0) aus und den so erhaltenen Wert x, denn f(x(0))=x, wie da steht, nennen wir x(1) und x(1) ist jetzt unsere neue Näherung für unseren Fixpunkt. Diese Gleichung, wie wir sie da mit x(0) und x(1) stehen haben, können wir jetzt verallgemeinern, indem wir für x(0) x(k) schreiben und für x(1) x(k+1). Unsere Iterationsvorschrift ist jetzt also, dass wir einfach uns einen Wert x nehmen, einen Startwert x(0) und unsere Funktion an dieser Stelle auswerten. Der so erhaltene Wert ist unsere neue Näherung für den Fixpunkt und dann werten wir die Funktion wieder an dieser neuen Stelle aus. Und das machen wir immer und immer weiter. Wir wollen uns jetzt einmal veranschaulichen, wie genau das in unserem eindimensionalen Fall aussieht. Wir haben hier also unsere Funktion f(x) und diese Winkelhalbierende mit der Gleichung f(x)=x. Jetzt haben wir einen Startwert x(0) und fangen von dem jetzt an mit unserer Picard-Iteration. Wir werten unsere Funktion f also an dieser Stelle x(0) aus und lesen den Wert f(x(0)) ab. Diesen Wert f(x(0)) nennen wir jetzt x(1) und werten dann die Funktion wieder an der Stelle x(1) aus und das geht dann immer so weiter. Da unsere blaue Linie f(x)=x die Winkelhalbierende ist, ist die Stelle x(1) genau dort, wo unsere 1. Auswertung f(x(0)) die blaue Lnie trifft. Wir hätten diese erste gestrichelte Linie also gar nicht bis nach links zu der Achse f(x) weiterziehen müssen, sondern hätten direkt von der blauen Achse heruntergehen können zu der Stelle x(1). Von dort gehen wir dann ja wieder hoch zu der Funktion f(x) usw. Was ich damit sagen will, ist, dass das, was hier eigentlich passiert das Folgende ist: Wir geben uns unseren Wert x(0) vor, gehen dann zu der Funktion f(x) an der Stelle, gehen dann rüber zu unserer blauen Winkelhalbierenden, von da wieder herunter zu unserer Funktion f, wieder zur Winkelhalbierenden usw. Und wir sehen, dass das gegen unseren Fixpunkt konvergiert. Gucken wir uns dazu einmal ein Zahlenbeispiel an. Wir haben die Funktion: g(x)=e-x-x gegeben. Und gesucht ist die Nullstelle dieser Funktion im Bereich [0,1], also die Stelle x für die gilt g(x)=0 Wir sollen jetzt also eine Nullstelle berechnen und eigentlich sollte es in diesem Video doch um Fixpunkte gehen. Ich habe dieses Beispiel extra so gewählt, da häufig die Aufgaben nicht direkt als Fixpunktaufgabe formuliert sind, sondern erst umgeformt werden müssen. Was wir in unserem Fall machen können, ist unsere Gleichung g(x)=0 umzustellen, sodass da steht x=e^-x. Wir müssen also immer eine Fixpunktgleichung finden, sodass da steht x= irgendeine Funktion von x. Wenn wir diese rechte Seite, also e^-x jetzt als f(x) definieren, dann haben wir eine Fixpunktgleichung genau in dieser Form, wie wir sie vorhin hatten x=f(x) und können da jetzt unsere Picard-Iteration darauf anwenden. Wir wollen also jetzt von dieser Funktion f(x), die dann ja e^-x ist, den Fixpunkt finden, und da wir vorhin gegeben hatten, dass die Nullstelle im Bereich [0,1] liegen soll, liegt unser Fixpunkt jetzt natürlich auch im Bereich [0,1]. Daher nehmen wir jetzt einfach einmal irgendeinen Startwert aus diesem Intervall. Ich habe mich jetzt für die 1 entscheiden. Unser Startwert x0 ist also 1. Wir erinnern uns: Um x1 auszurechnen, müssen wir f nur an der Stelle x(0) auswerten, also f(x(0)) berechnen. In diesem Fall also e^-1 und das ist 0,36788. Um jetzt x(2) zu berechnen, müssen wir in unserer Gleichung nur die 1 durch die 2 und die 0 durch die 1 ersetzen. Und dann erhalten wir das Ergebnis x(2)=0,69220. Der nächste Schritt geht wieder genauso. x(2) durch x(3) ersetzen und x(1) durch x(2) und da kommt dann heraus x(3)=0,50047. Wenn wir das ganze jetzt noch ein paar Mal machen, also noch ein paar Iterationsschritte mehr machen, dann konvergiert unser x irendwann gegen den Fixpunkt 0,56714. Wir müssen also um x(k+1) zu berechnen, immer nur x(k) in unsere Funktion einsetzen. Das ist ein super leichtes Verfahren und ihr könntet euch jetzt fragen, wozu man ein Video braucht, wenn das doch alles so einfach ist. Dazu möchte ich euch jetzt einmal ein 2. Beispiel zeigen: Hier haben wir die Funktion f(x)=ex-1 und sollen ausgehend vom Startwert 1 mithilfe der Picard-Iteration den Fixpunkt bestimmen. Ist doch gar kein Problem, denken wir uns. Einfach f an der Stelle x(0) also an der Stelle 1 auswerten und wir erhalten unser x(1)=1,71828. Weil es so einfach ist, gleich den nächsten Schritt hinterher und wir erhalten x(2)=4,57494. Das ist also größer als x(1). Und wir sehen jetzt, wenn wir in unsere Funktionsgleichung etwas einsetzen, also für x etwas einsetzen, das größer war als das voher, dann wird unser f(x) auch größer. Unsere Näherungswerte für den Fixpunkt x(k) werden also immer und immer größer und konvergieren gar nicht gegen unseren wirklichen Fixpunkt. Woran liegt das? Der Fixpunkt dieser Funktion war x=0. Den Punkt hatten wir erhofft zu erreichen mit unserer Picard-Iteration. Wir haben aber angefangen bei Startwert x(0)=1 und dann ist Folgendes passiert: Wenn wir uns, wie ich das vorhin schon einmal gezeichnet hatte, immer zwischen unserer Funktion und der Geraden f(x)=x hin und her bewegen, das ist ja das, was bei der Picard-Iterations passiert, dann wird unser Näherungswert immer und immer größer und entfernt sich hierbei sogar immer weiter von unserem Fixpunkt. Hier konvergiert das Verfahren also nicht gegen den tatsächlichen Fixpunkt x=0. Was wir brauchen, ist also ein Konvergenzkriterium, das uns sagt, ob unser Verfahren gegen den tatsächlichen Fixpunkt konvergiert. Und dieses Konvergenzkriterium ist im Fall der Picard-Iteration der Banach'sche Fixpunktsatz, den wir uns im nächsten Video angucken wollen. Bis dann.

Informationen zum Video