Nullstellen komplexer Polynome - Methode von Jenkins und Traub

• Um die Nullstellen eines komplexen Polynoms p(z) zu bestimmen, kann man dieses Polynom als das charakteristische Polynom einer Matrix, der sogenannten Frobenius-Begleitmatrix, interpretieren. Das QR-Verfahren zur Eigenwertbestimmung:
  A_k+1=Q^T_kA_kQ_k
  mit Q_k(A_k-s_kI)=R_k obere Dreiecksmatrix
  konvergiert für geeignet gewählte Shifts s_k de facto immer, falls, wie im vorliegenden Fall, A₀ eine nichtzerfallende Hessenbergmatrix ist. Immer in dem Sinne, dass das letzte Nebendiagonalelement null wird, worauf die Dimension des Problems reduzierbar ist.
• Das Verfahren von Jenkins und Traub wendet deshalb eine solche QR-Technik auf diese Matrix an, um alle Eigenvektoren und Eigenwerte zu bestimmen. Alle Transformationen sind als Operationen auf den Polynomkoeffizienten darstellbar, d.h. es werden keine Matrizenoperationen benötigt.

Die Eingaben

• Der Grad n der komplexen Polynoms.
• Sie haben nun die Wahl, sich entweder das Polynom durch Vorgabe von n komplexen Nullstellen erst zu erzeugen und diese dann ''zurückzurechnen'', oder Sie geben ein
• n+1 komplexe Koeffizienten a_n, ... ,a₀, die jeweils als Zahlenpaare (re,im) für re + i*im eingegeben werden müssen. Wichtig: a_n*a₀ ungleich 0.
• Ferner kann angegeben werden, ob eine graphische Ausgabe der Betrages des Polynoms p(z) gewünscht wird. Dazu wird im Ja-Fall s ein Rand b benötigt, der die Größe des Bildes festlegt. |p| wird dann über [re_min-b,re_max+b] × [im_min-b,im_max+b] geplottet, wobei re/im_min, re/im_max minimaler bzw. maximaler Real- bzw. Imaginärteil der Nullstellen sind.

Die Ausgaben

• Ausgegeben werden Real- und Imaginärteil der bestimmten Nullstellen.
• Falls gewünscht, der Plot von |p|, wobei der Bereich bei Bedarf (z.B. wenn alle Nullstellen reell sind) intern angepasst wird, um eine vernünftige Grafik zu erhalten.

Fragen ?!

• Wie verhalten sich Nullstellen bei Änderungen in den Koeffizienten, vor allem wenn man mehrfache Nullstellen hatte z.B. (x-1)^4 und (x-1)^4+(x^2-2x+0.99)*eps
• Schafft "er" es wirklich immer ?
• Einfach mal von den Plots beeindrucken lassen ! Hätten Sie sich ein komplexes Polynom so vorgestellt?

Das Eingabeformular

Zurück: Nichtlineare Gleichungssysteme