Lills Methode

Lills Methode (nach Eduard Lill) ist ein graphisches Verfahren zur Bestimmung der Nullstellen eines Polynoms.

Zu einem gegebenen Polynom $f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}\ldots +a_{1}x+a_{0};\quad a_{n}\neq 0$ werden von einem gemeinsamen Punkt ausgehend zwei Polygonzüge mit $n+1$ und $n$ Streckenabschnitten konstruiert. Enden diese in einem gemeinsamen Punkt, so ist die Gegenzahl des Tangens ihres Schnittwinkels am gemeinsamen Ausgangspunkt eine Nullstelle des Polynoms.

Konstruktion

Polynom und die zugehörigen Polygonzüge mit gefundener Nullstelle

Polygonzüge und Nullstellen für das Polynom $f(x)=4x^{3}+2x^{2}-2x-1$
Man beachte, dass, weil die erste Gerade des zweiten Polygonzugs die zugehörige Gerade einer Strecke aus dem ersten Polygonzugs genau in deren Endpunkt schneidet, der zweite Polygonzug nicht in einem rechten Winkel abbiegt, sondern weiter geradeaus verläuft.

Der Polygonzug mit $n+1$ Strecken wird zuerst konstruiert und ergibt sich aus den Koeffizienten $a_{n}\ldots a_{0}$ des Polynoms. Zunächst sei vorausgesetzt, dass alle Koeffizienten positiv sind. Von einem beliebigen Anfangspunkt ausgehend verläuft der erste Streckenabschnitt um $a_{n}$ Längeneinheiten nach rechts, der nächste biegt dann im rechten Winkel links ab und ist $a_{n-1}$ Längeneinheiten lang. An seinem Ende biegt der nächste Streckenabschnitt erneut links ab und man setzt dies Verfahren für alle Koeffizienten fort. Man erhält so einen linksdrehenden Viererzyklus von rechts, aufwärts, links, abwärts, der jedem Koeffizienten eine dieser vier Richtungen zuordnet. Ist ein Koeffizient nun negativ, so bewegt man sich entgegen der dem Koeffizienten durch den Zyklus zugeordneten Richtung. Ist ein Koeffizient $a_{k}=0$, dann auch die Länge des zugehörigen Streckenabschnitts ${\mathtt {a_{k}}}$, und zwei aufeinander folgende Punkte des ersten Polygonzuges fallen zusammen. Die Richtung von ${\mathtt {a_{k}}}$ folgt aber formal dem Zyklus der Richtungen, und eine Gerade mit dieser Richtung ist zur Konstruktion des zweiten Polygonzuges einzuzeichnen (s. u.). Ausgehend vom Streckenabschnitt ${\mathtt {a_{k-1}}}$ hat der Streckenabschnitt ${\mathtt {a_{k+1}}}$ auch dann die übernächste (und nicht die nächste) Zyklusrichtung, wenn ${\mathtt {a_{k}}}$ die Länge $0$ hat.

Polynom und die zugehörigen Polygonzüge ohne gefundene Nullstelle

Der zweite Polygonzug wird basierend auf einem Ausgangswinkel und dem ersten Polygonzug konstruiert. Man wählt eine Gerade so, dass sie mit dem ersten Streckenabschnitt des ersten Polygons den vorgegebenen Ausgangwinkel $\alpha$ bildet. Dann schneidet man diese Gerade mit der Geraden, auf der der zweite Streckenabschnitt des ersten Polygonzugs liegt. Dieser Schnittpunkt bildet mit dem Ausgangspunkt den ersten Streckenabschnitt des zweiten Polygonzugs. In diesem Schnittpunkt errichtet man nun die Senkrechte und bestimmt deren Schnittpunkt mit der Geraden, auf der der dritte Streckenabschnitt des ersten Polygonzugs liegt, und hat damit den zweiten Streckenabschnitt des zweiten Polygonzugs erhalten. Genau dann, wenn bei der Konstruktion des zweiten Polygonzuges die $n>k$-te Gerade den $(k+1)$-ten Strecktenabschnitt des ersten Polynomzuges in dessen Endpunkt schneidet, fallen zwei aufeinander folgende Punkte des zweiten Polygonzuges zusammen, sodass dessen $k$-ter Streckenabschnitt $\textstyle {\mathtt {b_{k}}}$ die Länge $0$ hat. Da $\textstyle {\mathtt {b_{k}}}$ (formal) orthogonal zum vorangehenden Streckenabschnitt ist, ist die $\textstyle {\mathtt {b_{k+1}}}$ erzeugende Gerade nicht zur $\textstyle {\mathtt {b_{k-1}}}$ erzeugenden orthogonal, sondern (zu jener parallel und, weil beide je einen der zusammenfallenden Punkte enthalten,) mit jener identisch. Ein Beispiel für diesen Zusammenhang ist der zweite Abschnitt des zweiten Polygonzuges in der nebenstehenden Graphik „Polygonzüge und Nullstellen für das Polynom $f(x)=4x^{3}+2x^{2}-2x-1$“. Man fährt nun so fort, bis man beim letzten Streckenabschnitt des ersten Polygonzugs angelangt ist. Trifft man dort genau auf dessen Endpunkt, das heißt, der Schnittpunkt der letzten Senkrechten des zweiten Polygonzugs schneidet die Gerade, auf der der letzte Streckenabschnitt des ersten Polygonzugs liegt, genau in dessen Endpunkt, so hat man eine Nullstelle gefunden und ihr Wert entspricht die Gegenzahl des Tangens des Winkels am Ausgangspunkt. Trifft man nicht auf den Endpunkt des letzten Streckenzuges des ersten Polygonzugs, so hat man keine Nullstelle gefunden und man konstruiert daher einen neuen zweiten Polygonzug mit einem anderen Ausgangswinkel. Durch geschickte Variation des Ausgangswinkels lassen sich so theoretisch alle Nullstellen ermitteln.

Wendet man Lills Methode in einer leicht modifizierten Form auf eine normierte quadratische Funktion an, so erhält man eine Herleitung des Carlyle-Kreises (siehe dort).

Hauptbeweis

Zum Beweis der Aussage im Kopftext sind im Folgenden der erste und zweite Polygonzug jeweils als Abfolge gedrehter Vektoren vereinheitlicht modelliert. Alle Aussagen zur oben beschriebenen Konstruktion der Polygonzüge lassen sich aus diesem Modell herleiten. Zentrale Beweisidee ist die Rückführbarkeit von Streckenlängen im zweiten Polygonzug auf den Funktionswert je einer Hilfsfunktion, die sich aus der Zerlegung des Ausgangspolyoms analog Horner-Schema ergibt; dies wird etwa im Mathologer-Video (s. u. Weblinks) dargestellt.

I. Der Punkt $O$ sei der Ursprung eines kartesischen Koordinatensystems. Ausgehend von diesem definieren die Vektoren

${\vec {a}}_{k}=a_{n-k}\cdot D^{k}{\begin{pmatrix}1\\0\end{pmatrix}}$

mit ${\vec {a}}_{0}=OA_{0},\;{\vec {a}}_{k\geq 1}=A_{k-1}A_{k}$ die Lage der Punkte $A_{k},\;k=0,\dots ,n$ des ersten Polygonzuges; hierbei ist $D^{k}$ die $k$-te Potenz der (als Matrix darstellbaren) Drehung um $+{\tfrac {\pi }{2}}$ und $D^{0}$ die identische Abbildung.

II. Die Hilfsfunktionen $g_{k}(x)$ erlauben wie bei Nutzung des Horner-Schemas die schrittweise Berechnung des Wertes von $f(x)=g_{n}(x)$:

$g_{0}(x)=a_{n}$

$g_{k}(x)=x\cdot g_{k-1}(x)+a_{n-k}\;$ für $k=1,\dots ,n$

III. Ausgehend vom gemeinsamen Punkt $O=B_{0}$ definieren die Vektoren

${\vec {b}}_{k}=g_{k}(x)\cdot D^{k}{\begin{pmatrix}1\\-x\end{pmatrix}}$

mit ${\vec {b}}_{k}=B_{k}B_{k+1}$ die Lage der Punkte $B_{k+1},\;k=0,\dots ,n-1$ eines weiteren Polygonzuges. Zu zeigen ist, dass jener der zweite Polygonzug der Methode Lills ist.

(a) Mit $A_{0}(a_{n}|0)$ (nach I) und $B_{1}(a_{n}|-xa_{n})$ (nach II und III) ist für den Winkel bei $O=B_{0}$ im Dreieck $B_{1}B_{0}A_{0}$

$\tan(\alpha )={\frac {-xa_{n}}{a_{n}}}=-x$.

(b) Mit III sind aufeinander folgende Richtungen des betrachteten Polygonzugs orthogonal.

(c) Zu zeigen bleibt, dass jeder Punkt $B_{k\geq 1}$ auf der Gerade $(A_{k-1}A_{k})$ liegt. Dazu hinreichend ist der Nachweis der Beziehung

$B_{k}A_{k}=g_{k}(x)\cdot D^{k}{\begin{pmatrix}1\\0\end{pmatrix}},\quad k=0,\dots ,n$,

denn $D^{k}{\begin{pmatrix}1\\0\end{pmatrix}}$ ist mit I ein Richtungsvektor dieser Gerade.

Der Induktionsanfang $k=0$ entsteht durch Einsetzen der Definition von $a_{n}=g_{0}(x)$ aus II in die rechnerische Darstellung des Vektors ${\vec {a}}_{k=0}=OA_{0}=B_{0}A_{0}$ in I. – Induktionsschluss:

$B_{k+1}A_{k+1}=B_{k+1}B_{k}+B_{k}A_{k}+A_{k}A_{k+1}=$

$\quad -g_{k}(x)\cdot D^{k}{\begin{pmatrix}1\\-x\end{pmatrix}}+g_{k}(x)\cdot D^{k}{\begin{pmatrix}1\\0\end{pmatrix}}+a_{n-(k+1)}\cdot D^{k+1}{\begin{pmatrix}1\\0\end{pmatrix}}\ =$

$\quad D^{k}{\begin{pmatrix}-g_{k}(x)+g_{k}(x)\\x\cdot g_{(k+1)-1}(x)+a_{n-(k+1)}\end{pmatrix}}=D^{k}{\begin{pmatrix}0\\g_{k+1}(x)\end{pmatrix}}=g_{k+1}(x)\cdot D^{k+1}{\begin{pmatrix}1\\0\end{pmatrix}}$, q.e.d.

IV. Zwei Punkte $B_{k}$, $A_{k}$ fallen genau dann zusammen, wenn

${\vec {0}}=B_{k}A_{k}=g_{k}(x)\cdot D^{k}{\begin{pmatrix}1\\0\end{pmatrix}}\Leftrightarrow g_{k}(x)=0$,

insbesondere ist $B_{n}=A_{n}$ genau dann, wenn $0=g_{n}(x)=f(x)$, q.e.d.

Variante zu Lills Methode

Voraussetzung und Behauptung

Der erste Polygonzug lässt sich für positive Koeffizienten auch mit einem Viererzyklus von Rechtsabbiegungen (statt mit Linksabbiegungen) konstruieren. Die Überlegungen zu negativen Koeffizienten, solchen mit dem Wert $0$ und die Konstruktion des zweiten Polygonzuges entsprechen den oben beschriebenen. Ein solches Polygonzugpaar (PZP) soll im Folgenden als rechtsdrehend erzeugt bezeichnet werden, eines wie oben beschrieben konstruiertes als linksdrehend erzeugt. Zu den Koeffizienten eines Polynoms $f(x)=\textstyle \sum _{k=0}^{n}a_{n-k}x^{n-k}$ entsteht das rechtsdrehend erzeugte PZP, wie leicht einzusehen ist, aus dem linksdrehend erzeugten durch Achsenspiegelung an einer Gerade, die die (beiden PZP gemeinsame) erste Strecke des ersten Polygonzuges enthält.

Genau dann, wenn in einem rechtsdrehend erzeugten PZP ein mit dem (rechtsdrehenden) Winkel $\alpha ^{*}=-\alpha$ angelegter zweiter Polygonzug im letzten Schritt auf den Endpunkt des ersten Polygonzuges trifft, ist $x=\tan \alpha ^{*}=\tan(-\alpha )$ eine Nullstelle des Polynoms.

Beweis

In einem kartesischen $x,y$-Koordinatensystem sei $S$ ist die vorausgesetzte Spiegelung an der $x$-Achse, $D$ die Drehung um ${\tfrac {\pi }{2}}$. Dann ist $SD^{k}=D^{-k}S$, wie folgender Induktionsschluss nach Induktionsanfang mit $k=0$ Beweist:

$SD^{k+1}{\begin{pmatrix}x\\y\end{pmatrix}}=SD^{k}{\begin{pmatrix}-y\\x\end{pmatrix}}=D^{-k}S{\begin{pmatrix}-y\\x\end{pmatrix}}=D^{-k}{\begin{pmatrix}-y\\-x\end{pmatrix}}=D^{-k-1}{\begin{pmatrix}x\\-y\end{pmatrix}}=D^{-(k+1)}S{\begin{pmatrix}x\\y\end{pmatrix}}$

Wie im vorgelegten Hauptbeweis (für linksdrehend erzeugte PZP) lassen sich auch rechtsdrehend erzeugte PZP mit Vektoren definieren. Mit der eben bewiesenen Umformung entstehen diese Vektoren durch die vorausgesetzte Spiegelung S aus denen, die ein PZP linksdrehend erzeugen:

$S({\vec {a_{k}}})=a_{n-k}\cdot SD^{k}{\begin{pmatrix}1\\0\end{pmatrix}}=a_{n-k}\cdot D^{-k}S{\begin{pmatrix}1\\0\end{pmatrix}}=a_{n-k}\cdot D^{-k}{\begin{pmatrix}1\\0\end{pmatrix}}$;

$S({\vec {b_{k}}})=g_{k}(x)\cdot SD^{k}{\begin{pmatrix}1\\-x\end{pmatrix}}=g_{k}(x)\cdot D^{-k}S{\begin{pmatrix}1\\-x\end{pmatrix}}=g_{k}(x)\cdot D^{-k}{\begin{pmatrix}1\\+x\end{pmatrix}}$.

Im vorgelegten Hauptbeweis für linksdrehend erzeugte PZP werde nun die Drehung $D$ (überall) durch die Drehung $D^{-1}=-D$ ersetzt, außerdem in der Definition des Vektors $b_{k}$ die y-Koordinate $-x$ durch $+x$ sowie der Winkel $\alpha$ durch sein Spiegelbild $S(\alpha )=-\alpha$. Dann wird die Behauptung dieses Abschnitts bis auf die resultierenden Vorzeichenänderungen mit den dort notierten Schritten bewiesen.

Nullstellen gespiegelter Polynome

Voraussetzung und Behauptung

Hat das Polynom

$f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}\ldots +a_{0}=\textstyle \sum _{k=0}^{n}a_{n-k}x^{n-k}$

die Nullstelle $x=x_{0}$, so hat das das Polynom

$f^{*}(x)=a_{n}x^{n}-a_{n-1}x^{n-1}+a_{n-2}x^{n-2}\ldots \pm a_{0}=\textstyle \sum _{k=0}^{n}(-1)^{k}a_{n-k}x^{n-k}$

die Nullstelle $x=-x_{0}$. Die Aussage (und eine anschauliche Durchführung der Verfahrensweise) finden sich im Mathologer video (nach 9 min 21 s endende Passage, siehe Weblink hierzu).

In einem kartesischen $x,y$-Koordinatensystem geht der Graph von $f^{*}(x)$ für ungerade $n$ durch Punktspiegelung im Ursprung, für gerade $n$ durch Achsenspiegelung an der $y$-Achse aus dem Graph von $f(x)$ hervor (wie auch umgekehrt, da genannte Abbildungen Involutionen sind). Dies motiviert die Bezeichnung von $f(x)$ und $f^{*}(x)$ als gespiegelte Polynome.

Beweis

I. Zu einem ersten Beweis werden die im Hauptbeweis und dem im Beweis der Variante eingeführten Begriffe verwendet. Die Vektoren des rechtsdrehend erzeugten ersten Polygonzugs zu $f$ lassen sich in die Vektoren des linksdrehend erzeugten ersten Polygonzugs zu $f^{*}$ umformen:

$a_{n-k}\cdot D^{-k}{\begin{pmatrix}1\\0\end{pmatrix}}=(-1)^{k}a_{n-k}\cdot D^{k}{\begin{pmatrix}1\\0\end{pmatrix}}=a_{n-k}^{*}\cdot D^{k}{\begin{pmatrix}1\\0\end{pmatrix}},\quad k=0,\dots ,n$;

entsprechend ist der zugehörige zweite Polynomzug zu $f$ beim Argument $x$ bzw. zu $f^{*}$ beim Argument $x^{*}$:

$g_{k}(x)\cdot D^{-k}{\begin{pmatrix}1\\+x\end{pmatrix}}=(-1)^{k}g_{k}(x)\cdot D^{k}{\begin{pmatrix}1\\+x\end{pmatrix}}=g_{k}^{*}(x^{*})\cdot D^{k}{\begin{pmatrix}1\\-x^{*}\end{pmatrix}},\quad k=0,\dots ,n-1$;

(auch) die beiden Darstellungen des (mit $D^{k}$) linksdrehend erzeugten zweiten Polynomzuges zu $f^{*}$ sind vektorweise kongruent. Mit $g_{k=0}(x)=g_{k=0}^{*}(x)=a_{n}\neq 0$ hat mindestens eine Gleichung der Schar nicht die Form ${\vec {0}}={\vec {0}}$, sodass mit koordinatenweiser Gleichheit der Vektoren

$x=-x^{*}$,

folgt; insbesondere ist $x_{0}=-x_{0}^{*}$ für Nullstelle von $f$ bzw. $f^{*}$, wie behauptet. Weiterhin ist

$B_{k}A_{k}=g_{k}(x)\cdot D^{-k}{\begin{pmatrix}1\\0\end{pmatrix}}=(-1)^{k}g_{k}(x)\cdot D^{k}{\begin{pmatrix}1\\0\end{pmatrix}}=g_{k}^{*}(x^{*})\cdot D^{k}{\begin{pmatrix}1\\0\end{pmatrix}}=B_{k}^{*}A_{k}^{*},\quad k=0,\dots ,n$;

Vergleich der skalaren Vorfaktoren ergibt

$g_{k}^{*}(x^{*})=(-1)^{k}g_{k}(x)$;

mit $\pm x=\mp x^{*}$ und $g_{k=n}^{*}(x)=f^{*}(x)$ folgen aus

$f^{*}(-x)=f^{*}(x^{*})=(-1)^{n}f(x)$

die obigen Behauptungen zur Spiegelsymmetrie.

II. In der genannten Quelle wird auch ein weiterer Beweis (ohne Lills Methode) angeregt. Die behaupteten Spiegelsymmetrien folgen aus der Umformung:

$f^{*}(-x)=\sum _{k=0}^{n}(-1)^{k}a_{n-k}(-x)^{n-k}=\sum _{k=0}^{n}(-1)^{k+n-k}a_{n-k}x^{n-k}=(-1)^{n}\sum _{k=0}^{n}a_{n-k}x^{n-k}=(-1)^{n}f(x);$

für Nullstellen $x=x_{0}$ ist

$0=\pm f(x_{0})=f^{*}(-x_{0})$, q.e.d.

Ähnliche Dreiecke in einem Polygonzugpaar

Voraussetzung und Behauptung

In einem Polygonzugpaar ist jede Teilstrecke des zweiten Polygonzugs, deren Länge von $0$ verschieden ist, Hypotenuse eines rechtwinkligen Dreiecks. Alle diese Dreiecke sind ähnlich. Dies gilt sowohl für die Polygonzüge der Methode Lills als auch für diejenigen der Variante.

Mit den Bezeichnungen, die im Hauptbeweis eingeführten sind, wird die Ähnlichkeit der Dreiecke $B_{k+1}B_{k}A_{k},\quad k=0,\dots ,n-1$ betrachtet. Für punktförmige Dreiecke dieser Form wird nichts behauptet; solche entstehen, wenn zwei aufeinander folgende Punkte des zweiten Polygonzugs zusammenfallen, so dass sie Endpunkte einer Teilstrecke der Länge $0$ sind.

Beweis

Mit der Darstellung im Hauptbeweis lässt sich in einem linksdrehend erzeugten Polynomzugpaar die Seite $A_{k}B_{k+1}$ eines betrachteten Dreiecks als Vektor beschreiben:

$A_{k}B_{k+1}=A_{k}B_{k}+B_{k}B_{k+1}=g_{k}(x)\cdot D^{k}{\biggl (}-{\begin{pmatrix}1\\0\end{pmatrix}}+{\begin{pmatrix}1\\-x\end{pmatrix}}{\biggr )}=-x\cdot g_{k}(x)\cdot D^{k}{\begin{pmatrix}0\\1\end{pmatrix}}$;

mit

$B_{k}A_{k}=g_{k}(x)\cdot D^{k}{\begin{pmatrix}1\\0\end{pmatrix}}$

ist für den Winkel bei $B_{k}$ in allen betrachteten Dreiecken

$\tan(\alpha )={\frac {-x\cdot g_{k}(x)}{g_{k}(x)}}=-x$.

Ferner ist in allen betrachteten Dreieck der Winkel bei $A_{k}$ nach Konstruktion ein rechter, so dass $\alpha$ spitz und durch seinen Tangens gegeben ist. Mit dem Ähnlichkeitssatz W:W:W folgt die Behauptung.

Zum Beweis der Behauptung für rechtsdrehend erzeugte Polygonzugpaare der Variante zu Lills Methode werde die Drehung $D$ (überall) durch die Drehung $D^{-1}=-D$ ersetzt, außerdem in der Definition des Vektors $B_{k}B_{k+1}$ die y-Koordinate $-x$ durch $+x$.sowie $\alpha$ durch $-\alpha$.

Nullstellen reverser Polynome

Voraussetzung, Behauptung

Für das Polynom

$f(x)=\sum _{k=0}^{n}a_{n-k}x^{n-k}$

des Kopftexts sei $a_{0}\neq 0$. Dann ist das reverse Polynom

$f^{*}(x)=\sum _{k=0}^{n}a_{k}x^{n-k}$

definiert.

Ist $x_{0}$ eine Nullstelle von $f$, so ist $x_{0}^{*}={\tfrac {1}{x_{0}}}$ eine Nullstelle von $f^{*}$.

Ein Hinweis auf diesen Zusammenhang findet sich im Mathologer video (nach 9 min 49 s endende Passage, siehe Weblink hierzu).

Für die Hilfsfunktionen $g_{k}(x)$ zu $f$ (vgl. Hauptbeweis, II.) bzw. $g_{k}^{*}(x^{*})$ zu $f^{*}$ gilt zudem für alle $0\leq k\leq n-1$ das Korollar:

$g_{k}^{*}({\tfrac {1}{x_{0}}})=-x_{0}\cdot g_{n-1-k}(x_{0})$.

Beweis

Wegen $a_{0}\neq 0$ ist $x_{0}\neq 0$, so dass $x_{0}^{*}={\tfrac {1}{x_{0}}}$ existiert.

Für die Nullstelle $x_{0}$ des Polynoms $f$ sei ein erster Polygonzug $p_{1}:O,\ldots ,A_{n}$ bzw. ein zweiter Polygonzug $p_{2}(x_{0}):O=B_{0},\ldots ,B_{n}$ mit den Vektoren ${\vec {a}}_{k}$ bzw. ${\vec {b}}_{k}$ linksdrehend erzeugt.

Dann definieren die Vektoren ${\vec {a}}_{k}^{*}=-{\vec {a}}_{n-k}$ bzw. ${\vec {b}}_{k}^{*}=-{\vec {b}}_{n-1-k}$ den ersten Polygonzug $p_{1}^{*}:O^{*}=A_{n},\ldots ,A_{n}^{*}=O$ bzw. zweiten Polygonzug $p_{2}^{*}(x_{0}^{*}):O^{*}=B_{0}^{*}=B_{n},\ldots ,B_{n}^{*}=B_{0}=O$ für die Nullstelle $x_{0}^{*}$ des reversen Polynoms $f^{*}$.

Die Behauptung $x_{0}^{*}={\tfrac {1}{x_{0}}}$. lässt sich mit den Eigenschaften dieser Polygonzugpaare beweisen (Beweis I.) oder (einfacher) ohne Lills Methode mit Umformung (Beweis II.).

Beweis I. mit Beweis des Korollars

Die Abbildung $O\rightarrow O^{*}=A_{n}=B_{n},\;{\vec {x}}\rightarrow {\vec {x}}'=-D^{n}{\vec {x}}$ erzeugt ein neues Koordinatensystem.

$p_{1}^{*}$ ist mit

${\vec {a}}_{k}^{*}=$$-{\vec {a}}_{n-k}=a_{n-(n-k)}\cdot D^{n-k}{\begin{pmatrix}1\\0\end{pmatrix}}=$$a_{k}\cdot D^{-k}{\bigg (}-D^{n}{\begin{pmatrix}1\\0\end{pmatrix}}{\bigg )}=$$a_{n-k}^{*}\cdot D^{-k}{\begin{pmatrix}1\\0\end{pmatrix}}'$

rechtsdrehend erzeugt, da ${\vec {a}}_{k+1}^{*}$ höchstens bis auf das Vorzeichen von $a_{k+1}^{*}$ durch die Rechtsdrehung $D^{-1}$ aus ${\vec {a}}_{k}^{*}$ hervorgeht.

Für das Argument $x_{0}^{*}$ haben die Vektoren des an $p_{1}^{*}$ (ebenfalls rechtsdrehend) erzeugten zweiten Polynomzugs $p_{2}^{*}(x_{0}^{*})$ im neuen Koordinatensystem die Form

${\vec {b}}_{k}^{*}=g_{k}^{*}(x_{0}^{*})\cdot D^{-k}{\begin{pmatrix}1\\x_{0}^{*}\end{pmatrix}}'$;

die Gleichheit ${\vec {b}}_{k}^{*}=-{\vec {b}}_{n-1-k}$ hat die Koordinatendarstellung

$g_{k}^{*}(x_{0}^{*})\cdot D^{-k}{\begin{pmatrix}1\\x_{0}^{*}\end{pmatrix}}'=-g_{n-1-k}(x_{0})\cdot D^{n-1-k}{\begin{pmatrix}1\\-x_{0}\end{pmatrix}}$;

mit $D^{-k}{\begin{pmatrix}1\\x_{0}^{*}\end{pmatrix}}'=-D^{n-k}{\begin{pmatrix}1\\x_{0}^{*}\end{pmatrix}}$ und $-D^{n-1-k}{\begin{pmatrix}1\\-x_{0}\end{pmatrix}}=+D^{n-k}{\begin{pmatrix}+x_{0}\\+1\end{pmatrix}}$ sowie Multiplikation von links mit $-D^{k-n}$ folgt

$g_{k}^{*}(x_{0}^{*})\cdot {\begin{pmatrix}1\\x_{0}^{*}\end{pmatrix}}=-g_{n-1-k}(x_{0})\cdot {\begin{pmatrix}x_{0}\\1\end{pmatrix}}$;

mit $g_{0}(x_{0})=a_{n}\neq 0$ verschwindet mindestens ein Koeffizient nicht, also sind die beiden Vektoren kollinear. Aus

$\lambda {\begin{pmatrix}1\\x_{0}^{*}\end{pmatrix}}={\begin{pmatrix}x_{0}\\1\end{pmatrix}}\;\Leftrightarrow \;\lambda =x_{0}\,\land \,\lambda x_{0}^{*}=1\;\Rightarrow \;x_{0}x_{0}^{*}=1$;

folgt mit Division durch $x_{0}\neq 0$ die Behauptung. Einsetzen derselben in die Vektorgleichung der vorletzten Zeile ergibt

$g_{k}^{*}({\tfrac {1}{x_{0}}}){\begin{pmatrix}1\\{\tfrac {1}{x_{0}}}\end{pmatrix}}=-g_{n-1-k}(x_{0})\cdot {\begin{pmatrix}x_{0}\\1\end{pmatrix}}=-x_{0}\cdot g_{n-1-k}(x_{0})\cdot {\begin{pmatrix}1\\{\tfrac {1}{x_{0}}}\end{pmatrix}}$;

Vergleich der Skalare zeigt das Korollar.

Beweis II.

Wie im Abschnitt Nullstellen gespiegelter Polynome bietet sich auch hier ein einfacherer algebraischer Beweis (ohne Lills Methode) an:

$x_{0}^{n}\cdot f^{*}({\tfrac {1}{x_{0}}})=x_{0}^{n}\cdot \sum _{k=0}^{n}a_{k}({\tfrac {1}{x_{0}}})^{n-k}=x_{0}^{n}\cdot \sum _{k=0}^{n}a_{k}x_{0}^{k-n}=\sum _{k=0}^{n}a_{k}x_{0}^{k}=\sum _{k'=n}^{0}a_{n-k'}x_{0}^{n-k'}=f(x_{0})$,

wobei $k'=n-k$. Mit der Voraussetzung $f(x_{0})=0$ sowie $x_{0}^{n}\neq 0$ folgt die Behauptung.

Polynomdivision mit Lills Methode

Voraussetzung und Behauptung; Beispiel

Nach Lills Methode oder der Variante seien zum Argument $x=x_{a}$ des Polynoms $f(x)$ im Kopftext des ersten bzw. zweiten Polynomzuges mit den Punkten $O,A_{0},\ldots ,A_{n}$ bzw. $O=B_{0}\ldots ,B_{n}$ konstruiert. Eine Polynomdivision liefere

${\frac {f(x)}{x-x_{a}}}=h(x)+{\frac {r}{x-x_{a}}}$,

wobei $h(x)$ ein Polynom $(n-1)$-ter Ordnung ist.

(i) Dann ist für $h(x)$ der Betrag des Koeffizienten bei $x^{n-1-k}$ die Streckenlänge $|B_{k}A_{k}|$ für $k=0,\ldots ,n-1$. Weiter ist $|r|=|B_{n}A_{n}|$.

(ii) Der Koeffizient ist genau dann negativ, wenn die Richtung des Pfeils von $B_{k}$ nach $A_{k}$ der im ersten Polygonzug vom Viererzyklus definierten Richtung entgegengesetzt ist (s. o. Konstruktion); mit $k=n$ entsprechend für $r$.

Die Behauptungen finden sich im Mathologer video (nach 22 min 11 s endende Passage, siehe Weblink hierzu).

Beispiel: Für die Nullstelle $x_{a}={\tfrac {-1}{\sqrt {2}}}$ des Polynoms $f(x)=4x^{3}+2x^{2}-2x-1$ (siehe obige Zeichnung, roter zweiter Polygonzug) hat $h(x)$ einen negativen Koeffizienten für $k=1$, denn der Pfeil von $B_{1}$ nach $A_{1}$ weist nach unten, vom Viererzyklus der Richtungen ist aber „nach oben“ vorgegeben, ebenso auch für $k=2$, denn der Pfeil von $B_{2}$ nach $A_{2}$ weist nach rechts, vom Viererzyklus ist aber „nach links“ vorgegeben. Damit lassen sich die Koeffizienten von

$(4x^{3}+2x^{2}-2x-1):(x+{\tfrac {1}{\sqrt {2}}})\quad =\quad h(x)\quad =\quad 4x^{2}+2(1-{\sqrt {2}})x-{\sqrt {2}}\quad \approx \quad +4x^{2}-0{,}82x-1{,}41$

näherungsweise aus der Zeichnung ablesen. Da $x_{a}$ eine Nullstelle von $f(x)$ ist, ist $B_{3}=A_{3}$ und also $|B_{3}A_{3}|=0=r$.

Beweis

(a) Im Hauptbeweis, II. sind Hilfsfunktionen $g_{k}(x)$ eingeführt, deren Definition der Berechnung von Funktionswerten nach Horner-Schema entlehnt ist. Diese Hilfsfunktionen lassen sich auch zur Polynomdivision nach Horner-Schema verwenden:

Die Werte $g_{k}(x_{a})$ je einer Hilfsfunktion an der Stelle $x=x_{a}$ seien Koeffizienten eines Polynoms

$h(x)=\sum _{k=0}^{n-1}g_{k}(x_{a})\,x^{n-1-k}$

der Ordnung $n-1$. Wird dieses mit dem Linearfaktor $x-x_{a}$ multipliziert, so entsteht ein Polynom der Ordnung $n$:

$(x-x_{a})\cdot h(x)=\sum _{k=0}^{n-1}g_{k}(x_{a})\,x^{n-k}+\sum _{k=1}^{n}-x_{a}\,g_{k-1}(x_{a})\,x^{n-k}=$

$g_{0}(x_{a})\,x^{n}+{\bigg (}\sum _{k=1}^{n-1}(g_{k}(x_{a})-x_{a}\,g_{k-1}(x_{a}))\,x^{n-k}{\bigg )}-x_{a}\,g_{n}(x_{a})$;

Nach der Definition der Hilfsfunktionen ist:

$g_{0}(x_{a})=a_{n}$

$g_{k}(x_{a})=x_{a}\,g_{k-1}(x_{a})+a_{n-k}\;\Leftrightarrow \;g_{k}(x_{a})-x_{a}\,g_{k-1}(x_{a})=a_{n-k}$ für $k=1,\dots ,n-1$

$g_{n}(x_{a})=x_{a}\,g_{n-1}(x_{a})+a_{0}\;\Leftrightarrow \;-x_{a}\,g_{n-1}(x_{a})=a_{0}-g_{n}(x_{a})$

Einsetzen ergibt:

$(x-x_{a})\cdot h(x)=a_{n}\,x^{n}+{\bigg (}\sum _{k=1}^{n-1}a_{n-k}\,x^{n-k}{\bigg )}+a_{0}-g_{n}(x_{a})$;

mit der Definition der Funktion $f(x)$ im Kopftext und $g_{n}(x)=f(x)$ folgt

$(x-x_{a})\cdot h(x)=f(x)-f(x_{a})\;\Leftrightarrow \;{\frac {f(x)}{x-x_{a}}}=h(x)+{\frac {f(x_{a})}{x-x_{a}}}$;

Polynomdivision von $f(x)$ durch den Linearfaktor $x-x_{a}$ ergibt bis auf ein Restglied das Polynom $h(x)$ mit dem Koeffizienten $g_{k}(x_{a})$ bei der Potenz $x^{n-1-k}$, wobei $k=0,\ldots ,n-1$. Der Zähler des Restgliedes ist der Wert von $g_{n}(x)=f(x)$ an der Stelle $x=x_{a}$, weswegen das Restglied genau dann verschwindet, wenn $x_{a}$ eine Nullstelle von $f(x)$ ist (s.a. hier).

(b) Das Polygonzugpaar sei wie im Hauptbeweis modelliert. Mit $x=x_{a}$ in III (c) ist

$B_{k}A_{k}=g_{k}(x_{a})\cdot D^{k}{\begin{pmatrix}1\\0\end{pmatrix}}$;

Nach diesen Gleichungen ist $|B_{k}A_{k}|=|g_{k}(x_{a})|$ für $k=0,\ldots ,n$. Mit (a) folgt die Behauptung (i).

Weiter ist der Skalar $g_{k}(x_{a})$ genau dann negativ, wenn die Richtungen der Vektoren $D^{k}{\begin{pmatrix}1\\0\end{pmatrix}}$ und $B_{k}A_{k}$ entgegengesetzt sind. Mit (a) folgt die Behauptung (ii).

Durch den Ersatz von $D$ durch die Drehung $D^{-1}=-D$ gehen die verwendeten Gleichungen in ihre Entsprechungen in einem Modell der Variante über, entsprechend der für ein linksdrehend erzeugtes Polygonzugpaar vorgelegte Beweis der Behauptungen (i) und (ii) in einen solchen für ein rechtsdrehend erzeugtes.

Literatur

• Dan Kalman: Uncommon Mathematical Excursions: Polynomia and Related Realms. AMS, 2009, ISBN 978-0-88385-341-2, S. 13–22
• Rainer Kaenders (Hrsg.), Reinhard Schmidt (Hrsg.): Mit GeoGebra mehr Mathematik verstehen. Springer Spektrum, 2. Auflage, 2014, ISBN 978-3-658-04222-6, S. 71–75
• Thomas C. Hull: Solving Cubics With Creases: The Work of Beloch and Lill. American Mathematical Monthly, April 2011, S. 307–315 (Online-Kopie)
• Eduard Lill: Résolution graphique des équations numériques de tous les degrés à une seule inconnue, et description d’un instrument inventé dans ce but. Nouvelles Annales de mathématiques (2), Vol. 6, 1867, S. 359–362 (Online-Kopie)
• Eduard Lill: Résolution graphique des équations algébriques qui ont des racines imaginaires. Nouvelles Annales de mathématiques (2), Vol. 7, 1868, pp. 363–367 (Online-Kopie)

Weblinks

Commons: Lill's method – Sammlung von Bildern, Videos und Audiodateien

• Animation for Lill's Method
• Mathologer video: "Solving equations by shooting turtles with lasers"