Direkt zum Inhalt

Lexikon der Mathematik: Graeffe-Verfahren

Näherungsverfahren zur Berechnung von Polynomnullstellen, das auf dem Wurzelsatz von Vieta basiert.

Sei \begin{eqnarray}{p}_{0}(x)={a}_{0}^{(0)}\,{x}^{n}\,+\,{a}_{1}^{(0)}\,{x}^{n-1}\,+\,\ldots \,+\,{a}_{n-1}^{(0)}\,{x}^{n}\,{a}_{n}^{(0)}\end{eqnarray}

das vorgegebene Polynom n-ten Grades mit nur reellen Nullstellen x1, x2,…,xn, für die überdies |x1| > |x2| >…> |xn| gelten soll. Dann wird durch das nachfolgende Berechnungsschema eine Polynomfolge (pk) definiert, deren Nullstellen jeweils \({x}_{j}^{{2}^{k}}\), j = 1,…,n, sind: \begin{array}{l}{a}_{0}^{(k+1)}\,\,:={({a}_{0}^{(k)})}^{2}\\ {a}_{j}^{(k+1)}\,\,:={({a}_{j}^{(k)})}^{2}\,+\,2\,\displaystyle \sum _{l=1}^{j^* }{(-1)}^{l}{a}_{j+l}^{(k)}{a}_{j-l}^{(k)}\end{array} für j = 1,…,n und j := min{j, nj}. Daraus lassen sich dann die Beträge der Nullstellen ermitteln, die Vorzeichen ergeben sich durch Einsetzprobe in das Ausgangspolynom.

Durch geeignete Erweiterungen ist das Verfahren auch für mehrfach reelle oder betragsgleiche komplexe Nullstellen tauglich. Mit dem Newtonverfahren lassen sich die Näherungen weiter verfeinern.

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