Lills Methode

Grundidee und Konstruktion

Lills Methode ist ein graphisches Verfahren zur Bestimmung von Nullstellen eines Polynoms f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0 mit a_n\ne0. Zu den Koeffizienten werden von einem gemeinsamen Ausgangspunkt zwei Polygonzüge konstruiert: der erste hat n+1, der zweite n Streckenabschnitte. Treffen ihre Endpunkte zusammen, ist die Gegenzahl des Tangens des Schnittwinkels am Ausgangspunkt eine Nullstelle: x=-\tan(\alpha).

Der erste Polygonzug folgt den Koeffizienten a_n,\ldots,a_0. Bei positiven Koeffizienten verläuft die erste Strecke nach rechts; jede nächste dreht sich um 90^\circ nach links. Dadurch entsteht der Richtungszyklus rechts, aufwärts, links, abwärts. Ein negativer Koeffizient wird entgegen seiner zugeordneten Richtung abgetragen. Bei a_k=0 hat die Strecke Länge 0; ihre Richtung bleibt für die weitere Konstruktion dennoch formal im Zyklus erhalten.

Für den zweiten Polygonzug wählt man eine Gerade mit Ausgangswinkel \alpha zur ersten Strecke. Sie schneidet die Trägergerade der zweiten Strecke des ersten Polygonzugs. Von diesem Schnittpunkt aus wird jeweils eine Senkrechte errichtet, bis zur Trägergeraden der nächsten Strecke des ersten Polygonzugs. Trifft die letzte Senkrechte genau dessen Endpunkt, ist eine Nullstelle gefunden. Andernfalls wird ein anderer Ausgangswinkel gewählt. Theoretisch lassen sich durch geeignete Variation alle Nullstellen bestimmen. Bei einer leicht modifizierten Anwendung auf normierte quadratische Funktionen ergibt sich der Carlyle-Kreis.

Warum die Konstruktion Nullstellen liefert

Der Beweis beschreibt die Polygonzüge mit gedrehten Vektoren und dem Horner-Schema. Sei D die Drehung um +\pi/2. Die Strecken des ersten Polygonzugs sind \vec a_k=a_{n-k}D^k\binom10. Damit werden die Koeffizienten nacheinander in den vier Richtungen abgetragen.

Die Hilfsfunktionen des Horner-Schemas sind g_0(x)=a_n und g_k(x)=x\,g_{k-1}(x)+a_{n-k} für k=1,\ldots,n. Insbesondere gilt g_n(x)=f(x). Für einen Wert x werden die Strecken des zweiten Polygonzugs durch \vec b_k=g_k(x)D^k\binom{1}{-x} beschrieben.

Daraus folgt erstens \tan(\alpha)=-x, weil die erste Strecke des zweiten Polygonzugs die Koordinaten (a_n,-xa_n) hat. Zweitens stehen aufeinanderfolgende Strecken dieses Polygonzugs senkrecht aufeinander. Drittens liegt jeder Punkt B_k des zweiten Polygonzugs auf der Trägergeraden der entsprechenden Strecke A_{k-1}A_k des ersten Polygonzugs. Die entscheidende Beziehung lautet B_kA_k=g_k(x)D^k\binom10. Daher fallen B_k und A_k genau dann zusammen, wenn g_k(x)=0. Für den letzten Punkt gilt somit B_n=A_n genau dann, wenn g_n(x)=f(x)=0.

Rechtsdrehende Variante und ähnliche Dreiecke

Die Variante zu Lills Methode verwendet für positive Koeffizienten Rechtsabbiegungen statt Linksabbiegungen. Sie entsteht aus der ursprünglichen, linksdrehenden Konstruktion durch Spiegelung an der Geraden, welche die gemeinsame erste Strecke enthält. Wenn der zweite Polygonzug mit dem rechtsdrehenden Winkel \alpha^*=-\alpha im letzten Schritt den Endpunkt trifft, ist x=\tan(\alpha^*)=\tan(-\alpha) eine Nullstelle. Die Vorzeichenänderung gegenüber der Grundform erklärt sich durch diese Spiegelung.

In beiden Varianten bilden die nicht punktförmigen Teilstrecken des zweiten Polygonzugs Hypotenusen rechtwinkliger Dreiecke B_{k+1}B_kA_k. Alle diese Dreiecke sind ähnlich. Für die linksdrehende Form ist der Winkel bei B_k durch \tan(\alpha)=-x bestimmt, während der Winkel bei A_k stets ein rechter Winkel ist. Damit besitzen alle betrachteten Dreiecke dieselben Winkel; nach dem Ähnlichkeitssatz W:W:W sind sie ähnlich. Für Teilstrecken der Länge 0 wird keine Aussage getroffen.

Gespiegelte Polynome

Zum Polynom f(x)=\sum_{k=0}^{n}a_{n-k}x^{n-k} wird das gespiegelte Polynom f^*(x)=\sum_{k=0}^{n}(-1)^ka_{n-k}x^{n-k} gebildet: Die Vorzeichen der Koeffizienten wechseln dabei ab. Hat f die Nullstelle x_0, dann hat f^* die Nullstelle -x_0.

Die zentrale algebraische Beziehung lautet f^*(-x)=(-1)^nf(x). Für f(x_0)=0 folgt deshalb f^*(-x_0)=0. Geometrisch geht der Graph von f^* bei ungeradem n durch Punktspiegelung im Ursprung, bei geradem n durch Achsenspiegelung an der y-Achse aus dem Graphen von f hervor. Der Artikel begründet den Zusammenhang außerdem über die Spiegelung zwischen rechts- und linksdrehenden Polygonzugpaaren.

Reverse Polynome und Kehrwerte von Nullstellen

Vorausgesetzt sei a_0\ne0. Dann ist zum Polynom f(x)=\sum_{k=0}^{n}a_{n-k}x^{n-k} das reverse Polynom f^*(x)=\sum_{k=0}^{n}a_kx^{n-k} definiert; es schreibt die Koeffizienten in umgekehrter Reihenfolge. Ist x_0 eine Nullstelle von f, dann ist x_0^*=1/x_0 eine Nullstelle des reversen Polynoms. Wegen a_0\ne0 kann x_0 nicht 0 sein.

Algebraisch folgt dies aus x_0^n f^*(1/x_0)=f(x_0). Da f(x_0)=0 und x_0^n\ne0, ist f^*(1/x_0)=0. Die Umkehrung der Polygonzüge liefert zusätzlich für die Horner-Hilfsfunktionen das Korollar g_k^*(1/x_0)=-x_0\,g_{n-1-k}(x_0) für alle 0\le k\le n-1.

Polynomdivision aus dem Polygonzug

Wird f(x) durch x-x_a geteilt, so gilt \frac{f(x)}{x-x_a}=h(x)+\frac{r}{x-x_a}, wobei h(x) ein Polynom (n-1)-ter Ordnung ist. Im zu x_a konstruierten Polygonzugpaar ist der Betrag des Koeffizienten von x^{n-1-k} in h(x) gleich |B_kA_k| für k=0,\ldots,n-1. Der Restbetrag ist |r|=|B_nA_n|. Ein Koeffizient beziehungsweise der Rest ist negativ, wenn der Pfeil von B_k nach A_k der durch den Richtungszyklus vorgegebenen Richtung entgegengesetzt ist.

Die Grundlage ist das Horner-Schema: Die Koeffizienten von h sind g_k(x_a), und es gilt (x-x_a)h(x)=f(x)-f(x_a). Daher ist r=f(x_a); der Rest verschwindet genau dann, wenn x_a eine Nullstelle ist.

Beispiel: Für f(x)=4x^3+2x^2-2x-1 und x_a=-1/\sqrt2 ergibt sich h(x)=4x^2+2(1-\sqrt2)x-\sqrt2\approx4x^2-0{,}82x-1{,}41. Weil x_a eine Nullstelle ist, gilt B_3=A_3 und r=0.