A posteriori error bounds for the zeros of polynomials (Q2395673)

Aus bekannten Gründen (Diskretisieren und Runden) liefern vom menschlichen Rechner oder mittels Rechenautomaten ausgeführte Berechnungen in den meisten Fällen nur Approximationswerte. Hat man Näherungswerte \(\lambda_i\) für die Wurzeln \(x_i\) eines Polynoms \(F(x) = \prod_{i=1}^n (x-x_i)\) erhalten, so ist die Frage nach oberen Schranken für die mit den vorliegenden Werten \(\lambda_i\) erreichten Näherungen \(| x_i-\lambda_i|\), \(i\!:\!1(1) n\), äußerst wichtig. Angegeben werden Defektabschätzungen (unabhängig vom jeweils verwendeten Rechenalgorithmus). Benutzt werden bei den vorliegenden Untersuchungen im wesentlichen die logarithmische Ableitung von \(F(x)\): \(\frac{d\ln F(x)}{dx}=\sum_{i=1}^n \frac{d\ln(x-x_i)}{dx}\) in der Form: \[ x_j-\lambda_j = \alpha_j / \left[1+\alpha_j\sum_{i=1}^n \frac{1}{\lambda_j-x_i}\right] \tag{*} \] (Summation über alle \(i\neq j)\), \(\alpha_j = -F(\lambda_j)/F'(\lambda_j)\), \(j\!:\!1(1) n\), und der Brouwersche Fixpunkt\-satz, womit die Existenz der Lösung \(x_i\), \(i:1(1) n\), von \(F(x) = 0\) als ein Fixpunkt \(\mathfrak x_0\) der zu Abbildungen im komplexen \(R_n\) erweiterten Gleichungen (*) gesichert wird. Es werden der Fall 1 der einfachen Nullstellen \(x_i\) -- unter der zusätzlichen Voraussetzung: \(\min_{i,j;\;i\neq j} | x_i-x_j|\) groß gegenüber Diskretisierungs- und Rundungsfehlern in den entsprechenden Werten \(\lambda_i\) und \(\lambda_j\) -- und der Fall 2 der mehrfachen und ,,büschelartig'' (als cluster) auftretenden (sowohl einfachen als auch mehrfachen) Nullstellen gesondert untersucht. Im Fall 1 erhält man die Abschätzungen \[ | x_j-\lambda_j|\leq | \alpha_j| / \left[1-|\alpha_j| \sum_{i=1}^n \frac 1{|\lambda_j-\lambda_i|-d_i}\right],\quad j: 1(1) n. \] Schwierigkeiten (keine einfachen festen Regeln angebbar) kann die Wahl der Größen \(d_i\) \(i\!:\!1(1) n\), bereiten, deren Wahl bei vorliegenden Werten \(\lambda_j\) und \(\alpha_j\), \(j\!:\!1(1) n\), so vorzunehmen ist, daß die zitierten Abbildungsfunktionen die Voraussetzungen des Brouwerschen Fixpunktsatzes erfüllen, um obige Einschließungen für die \(x_j\) zu erhalten. (Verf. fand \(d_i = 1.1\times |\alpha_i|\), \(i\!:\!1(1) n\), als brauchbar.) Die obigen Abschätzungen werden durch Berücksichtigung von Diskretisierungs- und Rundungsfehlern in den Größen \(\alpha_i\), \(i\!:\!1(1) n\) (hiermit sollen auch Ungenauigkeiten an den das Polynom \(F(x)\) charakterisierenden Daten erfaßt sein) -- nicht in den \(\lambda_i\) -- und durch Berücksichtigung von Argumenten bestimmender komplexer Größen (der abzuschätzenden Ausdrücke) verfeinert. Für ein Polynom vom Grad 6 mit komplexen (nicht konjugiert auftretenden) Wurzeln wird der Rechenaufwand für die verschiedenen Fehlerschranken erörtert. Der Einfluß einer Änderung (des Moduls) an den Approximationswerten \(\lambda_j\) auf die verschiedenen Fehlerschranken wird mitgeteilt [Versagen (Schranken \(\to\infty\)) mancher Formeln bei Änderung des Moduls eines \(\lambda_j\) um wenige Prozent]. Im Fall 2 -- wenn der Abstand zwischen (mindestens 2) Wurzeln \(x_i\), \(x_j\) in der Größenordnung der Diskretisierungs- und Rundungsfehler der \(\lambda_i\), \(\lambda_j\) liegt und/oder mehrfache Wurzeln auftreten -- gruppiert man die Wurzeln \(x_i\), \(i\!:\! 1(1) n\), sinngemäß zu ,,cluster'': \(x_j^{(\mu)}\), \(\mu\!:\!1(1) k_j\), \(j\!:\!1(1) m\), \(\sum_{j=1}^n k_j= n\), und setzt für jedes cluster (genau) eine Approximation \(\lambda_j\), \(j\!:\!1(1) m\), voraus. Verf. verwendet in diesem Fall 2 keine höheren logarithmischen Ableitungen von \(F(x)\), sondern die Taylorentwicklungen \[ F(x) = \sum_{\rho=0}^n f_{\rho}^{(j)}\times (x-\lambda_j)^\rho,\quad\text{ und } Q_j(x) =\sum_{\rho=0}^{n-k_j} q_\rho^{(j)} \times (x - \lambda_j)^\rho,\quad j\!:\!1(1) m, \] mit der Anweisung \(P_j(x): = F(x)/Q_j(x)\). Betrachtet man die Wurzeln von \(P_j(x)=0\) als Funktionen der Wurzeln von \(Q_j(x) = 0\), so wird man zu den den Gleichungen (*) im Fall 1 analogen Gleichungen und den für einen Einsatz des Brouwerschen Fixpunktsatzes erforderlichen Abbildungsfunktionen geführt. [In einem Anhang A wird der Zusammenhang (Äquivalenz) zwischen \(F(x)= 0\) und den in den Fällen 1 und 2 benutzten Abbildungsfunktionen ausgeführt.] Eine Einschließung der Wurzeln von \(P_j(x) = 0\), \(j\!:\! 1(1) m\) hat zu erfolgen. Eine geeignete Abschätzung für \(| x_j^{(\mu)}-\lambda_j|\), \(\mu\!:\! 1(1) k_j\), \(j\!:\! 1(1) n\), findet man als die (einzige) positive Lösung der Gleichung \[ \underline{p_{k_j}^{(j)}}\times D_j^{k_j} = \sum_{\rho=0}^{k_j-1} \overline{p_{\rho}^{(j)}}\times D_j^\rho, \tag{**} \] vorausgesetzt, daß \(\underline{p_{k_j}^{(j)}} > 0\) für \(j\!:\! 1(1) m\) ist -- \(\underline{p_{k_j}^{(j)}}\) eine untere Schranke für die Größe \(p_{k_j}^{(j)}\), \(\overline{p_\rho^{(j)}}\), \(\rho\!:\! 0(1)k_j-1\), analoge obere Schranken -- und wenn die in die Abschätzungen für die Koeffizienten der obigen Gleichung eingehenden Größen \(d_j\), \(j\!:\! 1(1) m\), für einen Einsatz des Fixpunktsatzes gemäß gewählt werden können. Im allgemeinen wird aber folgende zugänglichere obere Schranke [ für alle Lösungen der obigen Gleichung (**) ] zur Abschätzung von \(| x_j^{(\mu)}-\lambda_j|\), \(\mu\!:\! 1(1) k_j\), verwendet: \[ D_j:= 2 \max_{\rho:0(1)/k_j-1}\{(\overline{p_{\rho}^{(j)}}/\underline{p_{k_j}^{(j)}})^{1/(k_j-\rho)}\},\quad j\!:\!1(1) m. \] In einem Anhang B werden mehrere Wege zur Berechnung der Koeffizienten von \(P_j(x)\) skizziert und verglichen. Unter Verwendung des im Fall 1 zitierten Beispiels wird die Abhängigkeit der für den Fall 2 abgeleiteten Fehlerschranke \(D_j\) von der Vielfachheit einer Wurzel aufgezeigt. Außerdem wird auf Modifizierungen der für die Fälle 1 und 2 erhaltenen Resultate hingewiesen: falls Näherungswerte \(\lambda_j\) nur für \(l\) Wurzeln \(x_j\) \((1\leq l< n)\) vorliegen, jedoch untere Grenzen für die Abstände der \(x_j\) zu den übrigen \(x_i\) (a priori) bekannt sind oder, falls diese Abstände unbekannt sind, die Wurzeln \(x_i\) \(i\!:\! l+1(1)n\), als cluster mit der Approximation \(\infty\) zu deuten sind, um zu brauchbaren Abänderungen der Methoden (bzw. Resultate) zu gelangen.