Direkt zum Inhalt

Lexikon der Mathematik: E-Methode

selbst validierendes Verfahren, numerisches Verfahren, welches die Existenz einer Lösung des zugrunde liegenden Problems beweist, eine Einschließung berechnet und oft auch die Eindeutigkeit der Lösung innerhalb des Einschließungsintervalls sicherstellt.

E-Methoden berechnen eine Lösungsverifikation, sie prüfen durch Anwendung von Intervallarithmetik während ihrer Ausführung nach, ob die Voraussetzungen für ihre Anwendbarkeit gegeben sind. In vielen Fällen, wie z. B. der Lösungsverifikation bei linearen Gleichungssystemen oder Lösungsverifikation bei nichtlinearen Gleichungssystemen, geschieht dies durch Anwendung von auf dem Rechner überprüfbaren Folgerungen aus bekannten Fixpunktsätzen.

Gilt für eine in Maschinenintervallarithmetik berechnete Intervallauswertung feiner stetigen Funktion f : ℝn → ℝn \begin{eqnarray}\begin{array}{cc}{{\bf{\text{f}}}}_{\lozenge }({\bf{\text{x}}})\subseteq {\bf{\text{x}}},\end{array}\end{eqnarray}so bildet f den Intervallvektor x in sich ab und besitzt deshalb nach dem Brouwerschen Fixpunktsatz einen Fixpunkt x* = f (x*) ∈ f (x).

In der Praxis ist es günstiger, nicht den Fixpunkt, sondern die Differenz zu einer bekannten Näherung \(\mathop{x}\limits^{\sim }\) einzuschließen. Außerdem wird die ϵ-Inflation angewendet. Ein geeignetes Einschließungsintervall kann durch Iteration bestimmt werden. \begin{eqnarray}\left\{\begin{array}{c}\begin{array}{ccc}{{\bf{\text{x}}}}^{(0)} & = & {\bf{\text{x}}}-[\tilde{x},\tilde{x}]\\ {{\bf{\text{x}}}}^{(k+1)} & = & {{\bf{\text{f}}}}_{\diamondsuit}({{\bf{\text{x}}}}_{\varepsilon }^{(k)}),k=0,1,\ldots, \end{array}\end{array}\right.\end{eqnarray} solange bis \begin{eqnarray}\begin{array}{cc}{{\bf{\text{x}}}}^{({k}_{0}+1)}\subseteq {{\bf{\text{x}}}}_{\varepsilon }^{({k}_{0})}\end{array}\end{eqnarray} für ein k0. Dann ist die Existenz eines Fixpunkts \begin{eqnarray}{x}^{* }\in \tilde{x}+{{\bf{\text{x}}}}^{({k}_{0}+1)}\end{eqnarray} verifiziert. E-Methoden berechnen also eine a posteriori-Einschließung, die von einer Näherung ausgehend bestimmt wird. Der Erfolg dieser Iteration hängt von der Güte der Startnäherung \(\tilde{x}\) ab, die mit einem beliebigen Verfahren berechnet werden kann.

Hat man anstelle von (1) oder (3) komponentenweise echtes Enthaltensein oder Enthaltensein im Innern, so lassen sich auch Eindeutigkeitsaussagen treffen. Durch Nachiteration lassen sich die Schranken der Intervalleinschließung verbessern, so daß ( für Probleme mit exakt gegebenen Daten) möglichst viele führende Ziffern der Intervalluntergrenze mit den entsprechenden der Intervallobergrenze übereinstimmen. Durch die Berechnung werden also Ziffern der Lösung x* garantiert.

E-Methoden können auch verwendet werden, um zu zeigen, daß ein gegebenes Intervall keinen Fixpunkt enthält.

Ist f (x) ∩ x = ∅, so hat f keinen Fixpunkt in x.

[1] Herzberger, J. (ed.): Topics in Validated Computations. North-Holland Amsterdam, 1994.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos