×

Ein Einschließungsverfahren für Nullstellen. (German) Zbl 0159.21401

Bezugnehmend auf die vorstehend besprochenen Artikel [Zbl 0159.21202, Zbl 0159.21301] wird ein Verfahren angegeben zur Bestimmung der Nullstellen einer Funktion bzw. eines Funktionensystems in einem beliebigen, vorgegebenen Bereich \(B\). Sei \(f(x)\), \(x\in B\) eine komplexwertige Funktion, \(B\) ein abgeschlossener, beschränkter Teilbereich des \(n\)-dimensionalen Vektorraumes über den komplexen Zahlen. \(f(B)\) sei der Wertebereich von \(f\), und das Gleichungssystem \(f(x)=0\) habe in \(B\) endlich viele Nullstellen. Sei \(\hat f\) eine für jedes \(T\subseteq B\) stetige Abschätzung von \(f\) mit den Eigenschaften:
a) Für jedes \(T\subseteq B\) sei \(f(T)\subseteq \hat f(T)\),
b) Für jedes \(T\subseteq B\) und jedes \(T\) mit \(\tilde T\subseteq T\subseteq B\) gilt \(\hat f \xrightarrow {a}\hat f(\tilde T)\) für alle \(T\xrightarrow {a} \tilde T\),
c) Für alle \(x\in B\) gilt \(\hat f(x) = f(x)\).
Hat \(f(x)\) in \(B\) Nullstellen, so gilt \(0\in \hat f(T)\), und daraus läßt sich ein Einschließungsverfahren für die Nullstellen angeben, das von einer Intervallunterteilung von \(B=\cup_{i=1}^j B_j\) ausgeht. Alle Teilintervalle \(B_j\) mit \(0\in \hat f(B_j)\) werden weiter unterteilt usw. Führt man das Unterteilungsverfahren so aus, daß die Anzahl der Unterteilungen \(\nu\to\infty\) und gleichzeitig der Durchmesser jeder mitgeführten Teilmenge \(T\) von \(B\) mit der Eigenschaft \(0\in \hat f(T)\to 0\) strebt, so konvergiert jede dieser Teilmengen \(T\) gegen ein Nullstelle von \(f(x)\). In der Praxis liefert die einfache Intervallarithmetik eine derartige Abschätzung von \(f(x)\). Das Unterteilungsverfahren wird man in Abhängigkeit von der Stellenzahl der digitalen Rechenanlage nach endlich vielen Schritten abbrechen.
In Kapitel 2 des Artikels wird das Verfahren an einem Polynom mit reellen Koeffizienten erläutert. Weiter wird gezeigt, daß sich das Einschließungsverfahren auch auf die Bestimmung der reellen Nullstellen eines Gleichungssystems \(p_1(x,y) = 0\), \(p_2(x,y) = 0\) in einem beschränkten Teilbereich \(B\) der \((x,y)\)-Ebene anwenden läßt. Dabei seien \(p_1\) und \(p_2\) Polynome in \(x\) und \(y\) mit reellen Koeffizienten, d.h. dieser Spezialfall schließt die Behandlung von Polynomen mit komplexen Nullstellen oder komplexen Koeffizienten ein.
Kapitel 3 enthält die numerischen Ergebnisse von einigen einfachen Beispielen. Die Vielfachheit einer Nullstelle kann man dadurch bestimmen, daß man nach Beendigung des Verfahrens die Werte der Ableitung(en) in den zum Schluß noch mitgeführten Teilmengen untersucht.

MSC:

65Gxx Error analysis and interval analysis
68M07 Mathematical problems of computer architecture
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Apostolatos, N., undKulisch U.: Grundlagen einer Maschinenintervallarithmetik. Computing2, 89 (1967). · Zbl 0159.21203 · doi:10.1007/BF02239180
[2] Apostolatos, N. undU. Kulisch: Approximation der erweiterten Intervallarithmetik durch die einfache Maschinenintervallarithmetik. Computing2, 181 (1967). · Zbl 0159.21301 · doi:10.1007/BF02236606
[3] Nickel, K.: Über die Notwendigkeit einer Fehlerschranken-Arithmetik für Rechenautomaten. Numerische Mathematik,9, 69 (1966). · Zbl 0154.41905 · doi:10.1007/BF02165231
[4] Wilkinson, J. H.: Rounding Errors in Algebraic Processes. Notes on Applied Science No. 32, London. 1963. · Zbl 1041.65502
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.