Numerische Methoden und Fehlertheorie

Numerische Auswertung und Fehlertypen

Bei der numerischen Auswertung einer problematischen Situation in einem Computer ist das Ergebnis von Fehlern betroffen. Es gibt mindestens drei wesentliche Fehlerarten:

• Rundungsfehler: Diese entstehen, da Rechner eine begrenzte Präzision haben. Daten werden mit einer endlichen Anzahl von Nachkommastellen dargestellt, wodurch arithmetische Operatoren Fehler produzieren. Quelle: Die Berechnung selbst. Klassifikation: Symmetrisches Runden und Abschneiden.
• Abbruchfehler: Unendliche Prozesse (wie Annäherungen in Serienentwicklungen) werden durch endliche Prozesse ersetzt. Quelle: Das Fehlen der Entwicklung unendlicher Prozesse.
• Inhärente Fehler: Diese haben ihren Ursprung in der Annäherung an die Wirklichkeit durch mathematische Modelle und die Verwendung von Daten, die bereits Fehler aufweisen. Quelle: Messfehler.
• Modellierungs- oder Programmierfehler: Quelle: Der Algorithmus selbst.
• Fehlerfortpflanzung: Herkunft: Die Ausbreitung durch arithmetische Operationen (+, -, *, /). Die Subtraktion ist der Vorgang, der die größten Rundungsfehler produziert, besonders wenn die Werte sehr nahe beieinander liegen.

Anwendung der Fehlertheorie

Die Fehlertheorie ist ein Kriterium für die Entscheidung, ob ein Ergebnis korrekt ist oder nicht (dient der Entscheidungsfindung).

Iterative Techniken und Rundungsfehler

Warum breiten sich bei iterativen Techniken Rundungsfehler nicht aus (außer in der letzten Iteration)? Dies liegt daran, dass der Rechenbetrieb nicht angekettet ist und die Werte jeweils als wahre Eingabewerte übernommen werden.

Die Bairstow-Methode

Warum wird die Bairstow-Methode bei der Annäherung komplexer Wurzeln verwendet? Sie erlaubt es, komplexe Wurzeln zu finden, obwohl nicht mit komplexer Arithmetik gearbeitet wird. Bairstow zerlegt das Polynom in quadratische Faktoren, sodass immer mit reeller Arithmetik gearbeitet werden kann. Die Koeffizienten sind reell und die Wurzeln konjugiert komplex.

Die Bisektionsmethode (Zweiteilung)

Bei der Annäherung der Wurzeln von nichtlinearen Gleichungen ist die einzige Methode, die sicherstellt, dass der berechnete Fehler größer als der Rundungsfehler ist, die Methode der Zweiteilung. So kann der Status der Ergebnisse überprüft werden, um die Anforderungen des Problems stets zu erfüllen. Dies liegt daran, dass bei jeder Annäherung an die Wurzel mittels Bisektion (Xr = (Xu + Xi) / 2) bekannt ist, dass die genaue Wurzel innerhalb des Intervalls liegt. Daher sollte sie sich innerhalb von plus oder minus (deltaX / 2) befinden.

Lösung linearer algebraischer Gleichungssysteme

Um über das Verfahren zur Lösung linearer algebraischer Gleichungssysteme zu entscheiden, muss man die Größe und den Zustand des Systems bewerten. Dies geschieht durch die Berechnung der Determinante des Systems. Wenn die Determinante nahe bei 0 liegt, ist das System schlecht konditioniert. In einem solchen Fall würde man die Gauß-Elimination verwenden, die einen einfachen Weg bietet. Sie beruht darauf, dass die Determinante einer Dreiecksmatrix einfach das Produkt der Diagonalelemente ist (D = A11 * A22 * A33 ... Ann).

Vorteile der Gauß-Seidel-Methode

Warum eignet sich die Gauß-Seidel-Methode besonders für große oder schlecht konditionierte Systeme im Vergleich zu finiten Methoden? Da dies ein iteratives Verfahren ist, kann es bis zur Konvergenz innerhalb einer vorgegebenen Fehlertoleranz fortgesetzt werden. Rundungsfehler sind hier kein Problem, da die Methode das gewünschte Fehlerniveau kontrolliert.

Einsatz unendlicher Methoden

Wann und warum sollte man eine unendliche Methode zur Lösung linearer algebraischer Gleichungen einsetzen? Wenn das System schlecht konditioniert ist, da diese Methoden iterieren, bis der Fehler konvergiert. Der Rundungsfehler ist unproblematisch, da das gewünschte Fehlerniveau gesteuert wird.

Klassifizierung der Wurzelbestimmungsmethoden

Methoden zur Annäherung der Wurzeln nichtlinearer algebraischer Gleichungen werden wie folgt klassifiziert:

Offene Methoden

Diese nutzen keine festen Intervalle und müssen die Wurzel nicht zwingend einschließen. Sie konvergieren nicht immer, aber wenn sie es tun, dann schneller. Sie können divergieren, d. h. sich von der Wurzel entfernen, wenn die Anzahl der Iterationen wächst.

• Sekantenverfahren
• Von-Mises-Methode
• Newton-Raphson-Methode
• Fixpunkt-Iteration (sukzessive Approximation)

Geschlossene Methoden

Diese konvergieren immer.

• Halbierungsmethode (Bisektion)
• Regula Falsi (falsche Position)

Methoden für lineare algebraische Gleichungen

Diese werden unterteilt in:

Finite Methoden

• Gauß-Jordan
• Crout-Verfahren
• Gauß-Elimination

Unendliche Methoden (Iterative Verfahren)

• Jacobi-Verfahren
• Gauß-Seidel-Verfahren

Zuverlässigkeit unendlicher Methoden

Warum liefern unendliche Methoden in schlecht konditionierten Systemen zuverlässige Ergebnisse? Die unendlichen Methoden (Gauß-Seidel und Jacobi) sind iterativ oder sequentiell, und ihr Wert wird bei jeder Iteration unabhängig bestimmt. Die Annäherungen sind nicht fehlerbehaftet verkettet, sodass der Fehler nicht weitergegeben wird. Zudem ändern diese Methoden die Koeffizienten des Systems nicht.

Konvergenzgeschwindigkeit

Die Ordnung wird durch die Ableitung der Rekursionsgleichung bestimmt. Sie misst die Geschwindigkeit der Konvergenz:

• 1. Ordnung: Wenn F'(x) ≠ 0 bei X* → E(i+1) = K * Ei
• 2. Ordnung: Wenn F'(x) = 0 bei X* und F''(x) ≠ 0 bei X* → E(i+1) = K * Ei²

Wann nutzt man finite oder unendliche Methoden?

• Unendliche Methoden: Bei großen oder schlecht konditionierten Systemen, da sie Fehler nicht fortpflanzen und bis zur gewünschten Fehlertoleranz konvergieren (sofern sie konvergieren).
• Finite Methoden: Werden verwendet, um etwa 25 bis 50 gleichzeitige lineare Gleichungen zu lösen, wenn Teil-Pivotisierung und viele signifikante Stellen vorhanden sind.

Konvergenz ist die Anzahl der notwendigen Iterationen. Effizienz ist die Zeit bis zur Lösung. Geschwindigkeit bezieht sich auf die Anzahl der Iterationen.

Unterschied zwischen Bairstow und Newton-Raphson

• Bairstow: Findet Wurzeln mithilfe quadratischer Faktoren. Der Prozess ist stabil und arbeitet mit reeller Arithmetik. Wenn x eine Wurzel ist, ist auch die konjugierte Wurzel einfach zu finden. Es werden reelle Koeffizienten verwendet und das Ruffini-Schema wird zweifach auf die partiellen Ableitungen angewendet.
• Newton-Raphson: Erzielt Werte für komplizierte lineare und komplexe Wurzeln direkt aus den Faktoren. Es arbeitet mit komplexer Arithmetik, was instabil sein kann (kann bei manchen Polynomen keine Lösung geben). Es erfordert, dass das erste Element einen Imaginärteil ungleich 0 hat. Das Ruffini-Schema kann einmal angewendet werden.