Lösen von Gleichungen mit numerischen Verfahren

Page 1

1.1. Einleitung

Bei der Untersuchung von Funktionen auf Nullstellen, Horizonztal-und Flachstellen oder beim Bestimmen der Schnittpunkte zweier Graphen muss man im allgemeinen Gleichungen lösen. n Gleichungen vom Grade sind noch mit allgemeinen Lösungsmethoden lösbar,

wobei mit zunehmenden Grad die Lösungsformel ausführlicher und umständlicher wird. H. Abel hat nachgewiesen, dass Gleichungen ab dem 5. Grad nicht mehr exakt mit expliziten Lösungsmethoden lösbar sind.

≥ 5 n Spätestens ab dem Grade ist man folglich zum Lösen von Gleichungen auf andere

Lösungsmethoden angewiesen, sogenannte numerische Verfahren, falls eine Substitution, oder ein Erraten der Nullstelle(n) als Teiler des absoluten Glieds verbunden mit einer Polynomdivision zum Zerlegen der Funktion in leichter lösbare Faktoren nicht möglich ist. Diese Näherungsverfahren finden auch z.B. für das Lösen von transzendenten Gleichungen oder für das Bestimmen von Wurzeln und Reziprokwerten ihren Gebrauch. Falls man zeichnerisch Näherungswerte für die Nullstelle gefunden hat oder anhand von Wertetabellen mindestens eine Nullstelle in einem bestimmten Intervall voraussagen kann, helfen rechnerische Verfahren zum genauen Annähern der Lösung. Da man dabei das Rechenverfahren, je nach gewünschter Genauigkeit des Näherungswertes an die Nullstelle, iterieren (Erläuterung s.u.) muss, ist der Einsatz von Computern ratsam. Diese erleichtern das numerische Lösen einer Gleichung, da sie die sich iterierenden Rechnungen schneller berechnen können.

1.2. Der Begriff Iteration

Die Bezeichnung stammt aus dem Lateinischen. Iteration bedeutet Wiederholung. Im mathematischen Sinne versteht man darunter die Anwendung desselben Rechenvorgangs auf den zuvor berechneten Wert, um sich schrittweise an die gesuchte Lösung anzunähern. Dabei geht man von einer Näherungslösung aus und nimmt den berechneten Wert als neuen Ausgangspunkt zur Berechnung einer exakteren Lösung. Diese schrittweise Näherung wird als sukzessive Approximation bezeichnet. Die Iterationsformel, die den Rechenvorgang bestimmt, ist von Verfahren zu Verfahren verschieden. Sie ermöglicht es, durch Iteration die gesuchte Zahl beliebig genau anzunähern.

Page 2

2.1. Voraussetzungen für alle Verfahren

Für die folgenden numerischen Verfahren gibt es bestimmte Voraussetzungen und Bedingungen, damit sie gegen die gesuchte Nullstelle konvergieren. Man braucht einen bzw. zwei möglichst genaue Näherungen an die Nullstelle. Diese erhält man anhand einer Zeichnung des Graphen oder indem man eine Wertetabelle aufstellt und damit die Nullstelle tabellarisch eingrenzt (siehe Beispiele). Der Zwischenwertsatz von Bolzano sagt voraus, dass es zwischen zwei Funktionswerten mindestens eine Nullstelle gibt, falls: ) ( ); ( x f x f 2 1

Die Funktion in dem Intervall differenzierbar und somit stetig ist, also im Intervall ≤ ≤ ∧ jeder x-Wert eingesetzt werden darf, und verschiedene x x x ) ( ) ( x f x f 2 1 2 1

Vorzeichen haben. Wenn die 2.Ableitung zudem im Intervall [x1 ;x2 ] ihr Vorzeichen nicht ändert und ungleich „Null“ ist, gibt es genau eine Nullstelle (s. Abb.1). Bei einem Vorzeichenwechsel der 2.Ableitung im Intervall kann es mehrere Nullstellen geben. Die Verfahren konvergieren jedoch bei einem bestimmten Näherungswert nur gegen eine Nullstelle. Um die Verfahren gegen eine andere Nullstelle konvergieren zu lassen, muss man dann andere anhand einer Skizze herausgelesene Anfangswerte verwenden.

Wenn die Funktion f(x) in dem betrachteten Intervall nicht stetig, ist, kann es anstatt der oben vorhergesagten Existenz von mindestens einer Nullstelle, keine Nullstelle geben, weil z.B. durch eine senkrechte Asymptote mit Vorzeichenwechsel die Funktionswerte auch verschiedene Vorzeichen haben können, ohne dass ein Funktionswert im Intervall den Wert „Null“ annehmen muss.

Die numerischen Verfahren sind erst sinnvoll, wenn die Funktion im Intervall konkav oder konvex ist, ihre zweite Ableitung also ungleich Null ist, weil man sonst im Intervall eine einfach lösbare lineare Gleichung hätte.

2.2. Bisektion

Hierbei handelt es sich um ein Iterationsverfahren, bei dem ein Intervall, in dem nach dem Nullstellensatz eine Nullstelle vorhanden sein muss, bei jedem Schritt halbiert wird. Man erhält zwei halb so große Teilintervalle. Danach wird der Funktionswert des arithmetischen Mittels f(xh) berechnet. In einem Intervall gilt weiterhin, dass die Funktionwerte

Page 3

Page 4

jeweils den gleichen Betrag wie die Näherungsstelle x Daraus ergibt sich die iterative + 1 m ϕ = Folge: ) ( x x , die bei der oben genannten Bedingung mit einem aus der Skizze + m 1 m

abgelesen, groben Ausgangswert x1 gegen die Schnittstelle xs und somit der Nullstelle von f(x) konvergiert.

Falls die oben genannte Voraussetzung in der Nähe der Schnittstelle nicht gegeben ist, ist die Iteration divergent. Man erhält dann bei dieser Äquivalenzumformung keine Lösung anhand des allgemeinen Iterationsverfahrens. In dem folgenden Beispiel ist dieses Problem gegeben.

2.3.1. Beispiel für das allgemeine Iterationsverfahren

Page 5

− − =
f

Funktion Die Funktion wird auf die gewünschte Form

x 2 ) ( e x x y Es ist also die Schnittstelle der Graphen gesucht. Ein aus der

Zeichnung abzulesender Näherungswert ist x1=1. Man erhält unter Anwendung der

Iterationsformel

Die Schnittstelle bzw. die Nullstelle wurde 3 Stellen nach dem Komma genau bestimmt. Obwohl der Anfangswert nahe bei xs1 gewählt wurde, ist das Verfahren gegen die viel weiter gelegene Schnittstelle konvergiert. Auch wenn man einen rechts gelegenen Annäherungswert wählt, konvergiert das Verfahren nicht gegen die gewünschte Schnittstelle. Im Gegenteil, es divergiert. Der Grund ist die unerfüllte Bedingung, weil in

′ x ( > ϕ 1 ) der nahen Umgebung der Schnittstelle die Steigung ist. Dieses Problem kann

aber umgangen werden, indem man versucht die Funktion f(x) anders nach x umzuformen.

Page 6

Wir erhalten:

Die zweite Schnittstelle konnte ebenfalls auf 3 Stellen hinter dem Komma berechnet werden.

Das Einsetzen der Lösungen in f(x) bestätigt die Näherungswerte, da die Funktionswerte beinahe „Null“ betragen.

Ein anderes iteratives Näherungsverfahren ist die ,,Regula falsi “

2.4. Regula falsi

Dieses Verfahren kannten die Araber schon um 870 n. Chr.

Die Babylonier konnten Gleichungen 3.Grades mit einer Art „Regula falsi“ schon ab 1900 v.Chr. lösen.

Es ist ein Iterationsverfahren. Ausgehend von einem bzw. zwei Näherungswerten an die Nullstelle wird durch die Iteration des Verfahrens mit dem zuvor berechneten Wert ein neuer verbesserter Näherungwert der Nullstelle ermittelt.

Dabei sind x1 und x2 Näherungswerte an die Nullstelle. Sie werden zeichnerisch oder durch das Berechnen von Funktionswerten anhand einer Wertetabelle ermittelt.

Page 7

mindestens eine Nullstelle sein (s.S.2-3).

Da der Graph (s. Abb.) zwischen P1(x1/f(x1)) und P2(x2/f(x2)) monoton wächst, gibt es genau eine im Intervall [x1;x2] liegende Nullstelle. Diese kann mit dem folgenden Verfahren beliebig nahe angenähert werden.

Ansatz:

Der Graph f(x) wird durch die Sehne P1P2 dargestellt. Diese Sehne ist eine Gerade. Somit läßt sich ihre Steigung folgendermaßen darstellen.

Das Ziel ist ein Näherungswert für die Nullstelle. Man läßt die Sehne deshalb die x-Achse

an der Schnittstelle xs schneiden. Somit ist f(xs)=0 Man erhält nun eine neue Sehnengleichung, die man nach xs umformt, da man den Schnittpunkt mit der x-Achse haben möchte.

Page 8

Verfahren iteriert, wiederholt, und dabei die erhaltene Schnittstelle der Sehne mit der x-Achse xs beim nächstfolgenden Schritt wieder als x1 betrachtet, xs = x1 setzt, erhält man immer genauere Schnittstellen, die gegen die gesuchte Nullstelle konvergieren. Rekursiv dargestellt ergibt sich daraus folgendes Rechenverfahren:

= x + 1 m

lim x m

∞ → m

Diese Art der „Regula falsi“ ist die Fixpunktmethode. x2 bleibt dabei unbeweglich und unverändert. Bei einer Kombination der „Regula falsi“ mit dem „Newton-Verfahren“ beispielsweise, nähert sich x2 auch der Nullstelle.(siehe S. 10-11) Die „Regula falsi“ ist somit ein iteratives Verfahren zur genauen Annäherung an die Nullstelle.

2.5. Newton-Verfahren

Es ähnelt dem Sehnenverfahren, „Regula falsi“, und dient ebenso dem numerischen Lösen von Gleichungen.

Anstatt der Sehnengleichung, bei der die Steigung der Sekante durch zwei Differenzenquotienten ausgedrückt wird und die Schnittstelle der Sekante mit der x-Achse eine Näherung an die Nullstelle ist , tritt beim „Newton-Verfahren“, dem Tangentenverfahren, die Tangentensteigung f ´(x2) an die Stelle der Sekantensteigung. Die Stelle x1 wird der Stelle x2 beliebig nahe angenähert und somit entspricht die Sekante durch die Punkte P1 und P2 der Tangente im Punkt P2, die den Unterschied der beiden Verfahren ausmacht.

′ = ) ( x f

2

Die Tangente geht durch den Punkt P2(x2/f(x2)). Ihre Schnittstelle mit der x-Achse xt ergibt eine Näherung zur Nullstelle. Es gilt:

Page 9

Umformung nach xt (s. Erläuterungen zu „Regula falsi“ S.8)

− = − x x t

− = x x t

2

Im nächsten Schritt würde man xt2 bestimmen:

− = x x

2 t t

Die (m + 1)-te numerische Annäherung ist:

= x + 1 m

lim x m

∞ → m

Wenn man das „Newton-Verfahren“ iteriert, bekommt man eine immer bessere Genauigkeit der Nullstelle. Falls die Näherung keine Veränderung mehr ergibt, hat man die Nullstelle exakt bestimmt. Es gilt bei einer Konvergenz des „Newton-Verfahrens“, wie bei der „Regula falsi“:

− < − x x x x + o m m 0 1

Je öfter man iteriert, desto kleiner wird der Abstand zwischen gesuchter Nullstelle und der Schnittstelle der Tangente und

x-Achse. Mit jedem Iterationsschritt nähert man sich also der Nullstelle. Normalerweise verdoppelt sich mit jedem Schritt die Zahl der Dezimalstellen. Ein Rechenbeispiel des „Newton-Verfahrens“ befindet sich auf Seite 13-14.

2.6. Kombination ,, Newton-Verfahren“/,,Regula falsi“

Die beiden vorhin beschriebenen numerischen Verfahren zum Lösen von Gleichungen , die ,,Regula falsi“ und das ,,Newton-Verfahren“, sind eng miteinander verwandt. Man kann sie auch miteinander kombinieren. Dies läßt das Sekantenverfahren schneller konvergieren, da beide Punkte sich der Nullstelle nähern, und nicht wie bei der Fixpunktmethode ein Wert festgehalten wird. Dies hat aber den Nachteil, dass man schnell die Übersicht verliert, weil man zwei Verfahren anwendet. Damit man gegen gegen die Nullstelle x0 konvergiert, müssen die „Voraussetzungen für alle Verfahren“(s.S.2-3) erfüllt sein.

Page 10

Die gesuchte Nullstelle x0 wird dabei durch immer kleiner werdende Intervalle eingegrenzt. Man nähert sich von beiden Seiten der Nullstelle. Dies geschieht folgendermaßen:

Von rechts nähert man sich mit Hilfe des „Newton-Verfahrens“ von dem Näherungswert x2 aus; von links mit dem „Regula falsi“-Verfahren von x1 aus.

Die angenäherten Stellen xt bzw. xs werden dann wieder als x2 bzw. x1 betrachtet und die Verfahren iteriert, damit man eine exaktere Berechnung der Nullstelle bekommt.

2.7.1. Iterative Reziprokwertermittlung

Die numerischen Verfahren ermöglichen die Berechnung des Kehrwerts von einer reellen Zahl a. Diese wird in eine mit iterativen Verfahren, wie z.B. mit dem „Newton-Verfahren“, lösbare Funktion eingeflochten und die Lösung der Gleichung ist der Reziprokwert von a. Es gilt:

= x f ) (

mit der 1. Ableitung

′ ( x f

Bei der Iterationsformel des,,Newton-Verfahrens” gilt:

= x x + 1 m m

Page 11

= x x + m m 1

Der gesuchte Reziprokwert ist der Wert gegen den das Verfahren bei ausreichender Iteration konvergiert.

Ein veranschaulichendes Rechenbeispiel befindet sich im nächsten Kapitel unter ,,Iterative Berechnung reeller Wurzeln” auf Seite 14.

2.7.2. Iterative Berechnung reeller Wurzeln

Die numerischen Näherungsverfahren eignen sich nicht nur für die Lösung von Gleichungen, dem Bestimmen von Nullstellen.

Mit numerischen Verfahren kann man auch reelle Wurzeln beliebig genau berechnen. Die Wurzeln müssen dabei in eine Funktion eingebettet werden, die man dann mit den Näherungsverfahren lösen kann.

Eine Umformung zur Berechnung von Wurzeln, bei der alle Verfahren zur Lösung führen, falls die Wurzel reell ist, ist:

x =

m − = x n a a

m = − a x n 0

Wenn man diese Gleichung löst, also die Nullstelle(n) der Funktion

= x x f ) (

numerisch bestimmt, erhält man damit auch das Ergebnis der zu bestimmenden Wurzel. m negativ ist, stellt kein

Auch das Berechnen einer reellen Wurzel, bei der der Quotient n

Problem dar. Die Lösung ist aber schwerer zu berechnen, da die Ableitung und die Funktion, die man für das „Newton-Verfahren“ benötigt, komplizierter werden. Dies kann man jedoch umgehen, indem man anfangs bei der Berechnung der Wurzel den Quotienten als positiv ansieht.

Die erhaltene numerische Lösung bzw. Lösungen ist erst dann Lösung der Wurzel, wenn man den Kehrwert nimmt, da gilt:

= x

Da dies auch noch anhand der „iterativen Reziprokwertermittlung“ (s. Seite 11-12) durchgeführt werden kann, ist das Berechnen von reellen Wurzeln allein unter zu Hilfenahme von den beschriebenen iterativen numerischen Verfahren möglich. Die Fallunterscheidung gilt für positiven und negativen Quotienten.

Page 12

a>0

1)Falls der Quotient n

Achsensymmetrie muss nur eine Nullstelle berechnet werden,weil

m nicht gerade ist, existiert immer genau eine Lösung.

2)Falls der Quotient n

a<0

Fall 1) hat keine reelle Lösung.

Diese theoretischen und allgemeinen Erkenntnisse können am Besten an einem Beispiel erläutert werden. − Zu berechnen ist die 5 5 , 31 auf 4 Stellen hinter dem Komma.

Lösung:

Man betrachtet anfangs den Quotienten, hier -5 als positiv

und formt vorerst 5

Die Funktion

Grades; der Quotient ist nicht gerade. Folglich ist genau eine Lösung zu ermitteln ( s. Fall 2) Anhand einer Wertetabelle kann man die Lösung eingrenzen.

Die Nullstelle liegt also im Intervall [1,99;2]. In der Regel ist es nicht notwendig, die Nullstelle so genau einzugrenzen.

Der Funktionswert f(2)=0,5 ist bereits so klein, so dass man einen ausreichend genauen Näherungswert bei x2 =2 hat.

Nach dem „Newton-Verfahren“ gilt:

= x x + 1 m m

x t

Die beiden Näherungswerte unterscheiden sich nur noch ab der 5 Stelle hinter dem 10 − < − m 4 x x Komma. + 1 m

Die vorläufige Lösung wurde also auf 4 Stellen, auf

−

Abschließend muss nun noch der Reziprokwert genommen werden, um die richtige Lösung der Wurzel mit negativen Quotienten zu bekommen.

Page 13

Das genaue Vorgehen ist im vorherigen Kapitel ,,Iterative Reziprokwertermittlung” auf Seite 11-12 beschrieben worden. 1 − =

( x f

Die Iterationsvorschrift für den Reziprokwert von 2

Eine Wertetabelle liefert uns das Intervall [0.5 ; 1]

= 5015774 , 0 x

2 t

Die ersten 5 Nachkommastellen stimmen überein. Also wurde die Wurzel auf sogar 5 Stellen genau bestimmt. ≈ − 5 50157 , 0 5 , 31

Besonders bei einer nachfolgenden Berechnung des Reziprokwerts sollte man die erste Lösung der Wurzel möglichst genau berechnen, damit die erhaltene Näherungslösung den Reziprokwert nicht zu stark vom tatsächlichen Wurzelwert abweichen läßt.

3.1. Vor-und Nachteile der einzelnen Verfahren

Jedes der vorgestellten Verfahren hat seine Qualitäten. Die folgenden Vor- und Nachteile sind allgemein zu sehen. Es gibt sicherlich einige Sonderfälle, bei denen die Aussagen bezüglich der Konvergenzgeschwindigkeit oder des Rechenaufwands der verschiedenen Verfahren nicht zutreffen.

Beim „Newton-Verfahren“ muss man die Ableitung der Funktion kennen. Dies macht besondere Schwierigkeiten bei transzendenten und trigonometrischen Funktionen. Die Ableitung ist meistens sehr kompliziert und umfangreich oder sie muss selbst sogar numerisch berechnet werden. Hingegen braucht man für die ,,Regula falsi“ nur die Sekante, die durch zwei Kurvenpunkte eindeutig bestimmt wird.

Dafür hat das „Newton-Verfahren“ den Vorteil, dass es meistens schneller zum Ziel führt, da es eine höhere Konvergenzgeschwindigkeit als die ,,Regula falsi“ hat. Das liegt daran, dass die Tangente, die den Graphen ersetzt, dem Graphen mehr ähnelt als die Sekante der „Regula falsi“. Zudem ist der Rechenaufwand aufgrund der kürzeren Formel geringer. Das „Newton-Verfahren“ kann versagen, wenn der Graph bei einem Näherungswert nahezu parallel ist oder wenn ein Extremum oder Sattelpunkt mit zur x-Achse paralleler Tangente zwischen Näherungswert und gesuchter Nullstelle ist. Die Konvergenzgeschwindigkeit der „Bisektion/Trisektion“ wird nur durch die Halbierung/Drittelung der Intervalle bestimmt, und ist nicht funktionsabhängig. Die „Trisektion“ erreicht daher schnellere Konvergenz als die „Bisektion“, da das Intervall gedrittelt und dann ausgewertet wird. Die niedrigere Konvergenzgeschwindigkeit läßt sich damit erklären, dass die „Bisektion/Trisektion“ nur das Vorzeichen der Funktionswerte

Page 14

und nicht deren Betrag verwendet. Dadurch werden Informationen verschenkt, die zur Erhöhung der Konvergenzgeschwindigkeit verwendet werden können. Dies Informationen werden bei den anderen Verfahren nicht verschenkt, sondern werden unterschiedlich in die Iterationsformel verarbeitet.

Aufgrund der niedrigereren Konvergenzgeschwindigkeit bei der „Bisektion/Trisektion“ sind meistens viele Iterationsschritte nötig. Dementsprechend sind die Verfahren aufgrund des hohen Rechenaufwands ohne Computereinsatz nicht sehr geeignet.

Vorteilhaft bei der „Bisektion/Trisektion“ist es, dass die benötigten Iterationsschritte für eine gewünschte Genauigkeit der Lösung vorhergesagt werden können. Bei der Bisektion, beispielsweise wird das Intervall [ ] x − x in dem die Nullstelle liegt schrittweise 1 2

halbiert. Nach m-maliger Iteration beträgt die Intervalllänge und somit die überhaupt 2 − x x 1

mögliche Abweichung von der exakten Lösung m 2

Um die Nullstelle auf Seite 3 mit der Bisektion auf zwei Stellen nach dem Komma genau zu bestimmen, sind bei den gewählten Anfangsintervallgrenzen m-Iterationsschritte nötig,

also

Nachkommastellen von der tatsächlichen Nullstelle abweichen.

Die „Regula falsi“ und das „Newton-Verfahren“ versagen bei schlecht gewählten Intervallgrenzen. Der Näherungswert muss möglichst in der Umgebung der Nullstelle gewählt werden, damit eine Konvergenz wahrscheinlicher wird.

Der Vorteil bei der „Bisektion/Trisektion“ hingegen liegt darin, dass die Intervallgrenzen nicht möglichst nahe bei der Nullstelle gewählt sein müssen, damit das Verfahren konvergiert. Diese beiden Verfahren konvergieren bei stetigen Funktionen immer, wenn die Voraussetzungen auf Seite 2-3 gegeben sind.

Das allgemeine Iterationsverfahren hat zwar noch im Vergleich mit den anderen Verfahren den Nachteil, dass die Steigung in der Nähe der Nullstelle kleiner als 1 sein muss, muss aber auch keinen genauen Näherungswert wie die „Regula falsi“ oder das „Newton-Verfahren“ haben, damit die Folge konvergiert.

4. Zusammenfassung

Die in der Facharbeit vorgestellten Verfahren reichen im Grunde genommen aus, jegliche Gleichungen zu lösen. Sei es, um eine Funktion auf Null-, Horizontal-Flachstellen zu überprüfen, den Schnittpunkt zweier Graphen zu ermitteln, reelle Wurzeln oder den Reziprokwert zu berechnen.

Falls ein Verfahren versagt, kann die Gleichung vielleicht mit den anderen drei Verfahren gelöst werden. Grundsätzlich ist das „Newton-Verfahren“ (s. Seite 9-10) zu empfehlen. Meistens konvergiert es schneller als die anderen Verfahren und hat einen geringeren Rechenaufwand.