Regula falsi

Regula-falsi-Verfahren (lateinisch regula falsi ‚Regel des Falschen‘), auch: Regula duarum falsarum Positionum (lateinisch regula duarum falsarum positionum ‚Regel vom zweifachen falschen Ansatz‘), Falsirechnung rsp. Falsi-Rechnung sind Methoden zur Berechnung von Nullstellen.

• Die ursprüngliche, historische Regula Falsi diente der Lösung einer linearen Gleichung mit Hilfe zweier „falscher“ Testwerte.
• Als numerische Methode, auch lineares Eingabeln genannt, dient die Regula Falsi als Iterationsmethode zur Ermittlung der Nullstelle reeller Funktionen. Sie kombiniert Methoden vom Sekantenverfahren und der Bisektion.

Das Regula-Falsi-Iterationsverfahren (Primitivform)

Die ersten zwei Iterationen des Regula-falsi-Verfahrens; rot dargestellt die Funktion f, blau die Sekanten

Das Regula-falsi-Verfahren startet mit zwei Stellen (in der Nähe der Nullstelle) $a_{0}$ und $b_{0}$, deren Funktionsauswertungen $f(a_{0})$, $f(b_{0})$ unterschiedliche Vorzeichen haben. In dem Intervall $[a,b]$ befindet sich somit nach dem Zwischenwertsatz (für stetiges $f$) eine Nullstelle. Nun verkleinert man in mehreren Iterationsschritten das Intervall und bekommt so eine immer genauere Näherung für die Nullstelle.

Iterationsvorschrift

In Schritt $k$ berechnet man:

$\!\,c_{k}=a_{k-1}-{\frac {b_{k-1}-a_{k-1}}{f(b_{k-1})-f(a_{k-1})}}f(a_{k-1})$  $\!\,={\frac {a_{k-1}{f(b_{k-1})}-b_{k-1}{f(a_{k-1})}}{f(b_{k-1})-f(a_{k-1})}}$.

Ist $f(c_{k})=0$, so wird das Verfahren beendet, denn mit $c_{k}$ ist eine Nullstelle gefunden. Anderenfalls wählt man $a_{k}$, $b_{k}$ wie folgt:

• $a_{k}=c_{k},\ b_{k}=b_{k-1}$ falls $f(a_{k-1})$ und $f(c_{k})$ gleiches Vorzeichen haben sowie
• $a_{k}=a_{k-1},\ b_{k}=c_{k}$ falls $f(b_{k-1})$ und $f(c_{k})$ gleiches Vorzeichen haben,

und geht damit in den nächsten Iterationsschritt.

Bemerkungen

• Die Berechnung des $c_{k}$ entspricht dem Anwenden des Sekantenverfahrens mit einer Iteration im $(k-1)$-ten Intervall. Im Gegensatz zum Sekantenverfahren befindet sich in diesem Intervall aber stets eine Nullstelle.
• Geometrisch kann man $c_{k}$ als die Nullstelle der Sekante durch $\left(a_{k-1},f(a_{k-1})\right)$ und $\left(b_{k-1},f(b_{k-1})\right)$ deuten.
• $c_{k}$ liegt natürlich immer im Intervall $\left[a_{k-1},b_{k-1}\right]$.
• Konvergenz: Solange $f$ im $k$-ten Intervall nicht strikt konkav bzw. konvex ist, also im Intervall ein Vorzeichenwechsel der zweiten Ableitung vorliegt, liegt superlineare Konvergenz vor.

• Visualisierung der Regula falsi
• 
• 
• 
• 
• 

Verbesserung des Verfahrens

Ist $f$ konkav oder konvex im Intervall $[a_{k},b_{k}]$, hat die zweite Ableitung also überall im Intervall das gleiche Vorzeichen, so bleibt eine der Intervallgrenzen für alle weiteren Iterationen stehen, denn die Sekante liegt immer unterhalb bzw. oberhalb der Funktion. Die andere Intervallgrenze konvergiert jetzt nur noch linear gegen die Lösung.

Abhilfe schaffen die folgenden Verfahren.

Illinois-, Pegasus- und Anderson/Björck-Verfahren

Idee der Verfahren

Den verbesserten Verfahren liegt die folgende Idee zu Grunde: Falls sich die „linke“ Intervallgrenze $x_{1}$ im aktuellen Schritt nicht verändert – das heißt, dass die tatsächliche Nullstelle zwischen der „linken“ Grenze und der genäherten Nullstelle liegt –, multipliziert man $f(x_{1})$ mit einem Faktor $0<m<1$ und bringt den Funktionswert an der Stelle $x_{1}$ damit näher an Null.

Entweder verkürzt sich somit der Abstand der Näherung zur Nullstelle im nächsten Schritt oder die Nullstelle wird im nächsten Schritt zwischen der tatsächlichen Nullstelle und der „rechten“ Intervallgrenze genähert.

Im zweiten Fall werden dann einfach „rechts“ und „links“ für den nächsten Schritt vertauscht. Da der zweite Fall irgendwann – auch in konvexen Intervallen – immer eintritt, ist sicher, dass keine der beiden Intervallgrenzen bis zum Abbruch stehen bleibt. Somit ist die Konvergenz garantiert superlinear.

Algorithmus

Den folgenden Algorithmus haben diese Verfahren gemeinsam:

$\!\,{\begin{array}{l}{\mathsf {solange}}~\circledast (|x_{2}-x_{1}|\geq \varepsilon _{x},|f_{z}|\geq \varepsilon _{f}):\\~~\left[{\begin{array}{l}z:=x_{1}-{\frac {f_{1}}{s}}~\mathrm {mit} ~s={\frac {f_{2}-f_{1}}{x_{2}-x_{1}}}\\f_{z}:=f(z)\\{\mathsf {falls}}~f_{z}\cdot f_{2}<0:\\~~\left[x_{1}:=x_{2},~f_{1}:=f_{2},~x_{2}:=z,~f_{2}:=f_{z}\right.\\{\mathsf {falls}}~f_{z}\cdot f_{2}>0:\\~~\left[f_{1}:=m\cdot f_{1},~x_{2}:=z,~f_{2}:=f_{z},~x_{1}~{\text{bleibt}}\right.\\{\mathsf {sonst}}:\\~~\left[x_{1}:=z,~f_{1}:=f_{z},~x_{2}:=z,~f_{2}:=f_{z}\right.\\\end{array}}\right.\\~\\{\text{nimm }}z{\text{ als Näherung für }}x^{*}\end{array}}$

Dabei sind $x_{1},x_{2}$ die Intervallgrenzen im $k$-ten Schritt, $f_{1},f_{2}$ und $f_{z}$ die Funktionswerte an den Stellen $x_{1},x_{2}$ und $z$. $\varepsilon _{x},\varepsilon _{f}$ sind die Abbruchgrenzen und $m$ der Verkürzungsfaktor. $\circledast (\cdot ,\cdot )$ steht hier für eine nicht näher spezifizierte, zweistellige Boolesche Funktion. Sinnvolle Funktionen wären hier die Disjunktion, die Konjunktion, die Identität des ersten und die Identität des zweiten Operanden. Im ersten Fall muss eine der beiden Abbruchgrenzen, im zweiten Fall beide, im dritten Fall lediglich $\varepsilon _{x}$ und im vierten Fall $\varepsilon _{f}$ unterschritten werden, damit $\circledast (|x_{2}-x_{1}|\geq \varepsilon _{x},|f_{z}|\geq \varepsilon _{f})$ falsch wird und das Verfahren abbricht.

Die unterschiedlichen Verfahren unterscheiden sich lediglich im Verkürzungsfaktor $m$.

Illinois-Verfahren

$m_{I}=0{,}5$

Pegasus-Verfahren

$m_{P}={\frac {f_{2}}{f_{2}+f_{z}}}$

Anderson/Björck-Verfahren

$m_{A/B}={\begin{cases}1-{\frac {f_{z}}{f_{2}}}&{\text{falls}}~1-{\frac {f_{z}}{f_{2}}}>0\\0{,}5&{\text{sonst}}\end{cases}}$

Rekursive Implementierung des Pegasus-Verfahrens

Die zu untersuchende Funktion und die Abbruchkriterien:

epsx, epsf seien definiert
f(x) sei definiert

Der Verkürzungsfaktor für das Pegasus-Verfahren:

m(f2, fz): return f2 ÷ (f2 + fz)

Der eigentliche, rekursive Algorithmus:

betterFalsePosition(x1, x2, f1, f2):
  z := x1 − f1 · (x2 − x1) ÷ (f2 − f1) // Näherung für die Nullstelle berechnen
  fz := f(z)

  // Abbruchgrenze unterschritten?: z als Näherung zurückgeben
  if |x2 − x1| < epsx or |fz| < epsf then return z

  // ansonsten, Nullstelle in [f(xz), f(x2)]?: „Links und Rechts“ vertauschen, Nullstelle in [f(xz), f(x2)] suchen
  if fz · f2 < 0 then return betterFalsePosition(x2, z, f2, fz)

  // ansonsten: „verkürzen“ und Nullstelle in [x1, z] suchen
  return betterFalsePosition(x1, z, m(f2, fz) · f1, fz)

Die Methode, mit der das Verfahren für das zu untersuchende Intervall, gestartet wird:

betterFalsePosition(x1, x2): return betterFalsePosition(x1, x2, f(x1), f(x2))

Bemerkungen

• Die Konvergenz der Verfahren ist superlinear und mit der des Sekantenverfahrens vergleichbar.
• Durch die superlineare, garantierte Konvergenz und den relativ geringen Rechenaufwand je Iteration sind diese Verfahren bei eindimensionalen Problemen in der Regel anderen Verfahren (wie z. B. dem Newton-Verfahren) vorzuziehen.

Zweidimensionales regula falsi

Gegeben sind drei Sender mit den Koordinaten
x1=12 und y1 = 8
x2 = 11 und y2 = −9
x3 = −10 und y3 = 1
Die Sender senden zur gleichen Zeit ein Signal mit bekannter Laufgeschwindigkeit aus. Diese Signale kommen beim Empfänger E zu unterschiedlichen Zeiten an. Aus den Zeitdifferenzen kann der Empfänger die Entfernungsdifferenzen ausrechnen. Er ist dem Sender 1 am nächsten der Sender 2 ist 4.814… weiter entfernt und der Sender 3 ist 6.530… weiter entfernt. Aus diesen Differenzen kann der Sender seinen Standort berechnen. Den Schnittpunkt der schräg stehenden Hyperbeln können nur versierte Mathematiker berechnen. Die übrigen müssen zur Allzweckwaffe regula falsi greifen. Ein Blick auf die Skizze macht sofort klar, dass die Hyperbel 1&3 für den x-Wert zuständig ist und die Hyperbel 1&2 für den y-Wert. Wenn dieser Sachverhalt nicht sofort klar ist, muss durch Probeschritte in alle Richtungen des Halbkreises (im Ursprung durch Pfeile angedeutet) geklärt werden, welche Parabel für welchen Wert zuständig ist.
Beim Start von regula falsi müssen generell zwei Schätzwerte angenommen werden. Sie liegen zweckmäßig 1E-6 auseinander. Der Schnittpunkt der Parabel 1&3 mit der x-Achse ist noch weit von dem Empfänger entfernt, so dass seine genaue Berechnung überflüssig ist. Der Versuch zeigt, dass die optimale Berechnung erreicht ist, wenn die Zahl der Iterationen generell auf 3 beschränkt ist. Nach 97 Iterationen wird der x-Wert 5 genau getroffen und der y-Wert 3 hat einen Fehler von 9E-16(2 hoch −50). Nach 25 Iterationen sind schon drei Stellen hinter dem Komma richtig.

Dreidimensionales regula falsi

Eine dreidimensionale Skizze ist hier so einfach nicht möglich. Zunächst wird ein vierter Sender gebraucht. Er hat die Koordinaten
x4 = −1 und y4 = −2 und z4 = −9 y
z1 = 9 und z2 = 2 und z3 = 5
Der Empfänger hat die Koordinaten xE= 5 und yE = 3 und zE= 7
Durch Probeschritte in alle Richtungen der Halbkugel wird ermittelt, welche Parabel für x,y und z zuständig ist. Für x ist die Parabel 1&3, für y 1&2 für z 3&4 zuständig. Nach 328 Iterationen beträgt der Fehler für alle drei Werte 9E-16. Nach 80 Iterationen sind schon drei Stellen hinter dem Komma richtig.

Geschichte

Die Regula falsi zur Lösung einer linearen Gleichung

Die historische Regula falsi findet sich bereits in sehr alten mathematischen Texten, beispielsweise wird sie im Papyrus Rhind (ca. 1550 v. Chr.) angewandt.

Unter den ältesten erhaltenen Dokumenten, die vom Wissen um die Methode des doppelten falschen Ansetzens zeugen, befindet sich die indisch-mathematische Schrift „Vaishali Ganit“ (ca. 3. Jahrhundert v. Chr.). Der altchinesische mathematische Text Die Neun Kapitel der mathematischen Kunst (200 v. Chr. – 100 n. Chr.) erwähnt den Algorithmus ebenfalls. In diesem Text wurde das Verfahren auf eine lineare Gleichung angewandt, sodass die Lösung direkt, also ohne Iteration, erreicht wurde. Auf den Bagdader Mathematiker, Philosoph und Arzt Qusta ibn Luqa (820–912) geht eine geometrische Begründung der Regula falsi zurück. Leonardo da Pisa (Fibonacci) beschrieb das Verfahren des doppelten falschen Ansetzens in seinem Buch „Liber Abaci“ (1202 n. Chr.), angelehnt an eine Methode, die er aus arabischen Quellen gelernt hatte.

Auch Adam Ries kannte die regula falsi und beschrieb die Methode wie folgt:

„wird angesetzt mit zwei falschen Zahlen, die der Aufgabe entsprechend gründlich überprüft werden sollen in dem Maße, wie es die gesuchte Zahl erfordert. Führen sie zu einem höheren Ergebnis, als es in Wahrheit richtig ist, so bezeichne sie mit dem Zeichen + plus, bei einem zu kleinen Ergebnis aber beschreibe sie mit dem Zeichen −, minus genannt. Sodann ziehe einen Fehlbetrag vom anderen ab. Was dabei als Rest bleibt, behalte für deinen Teiler. Danach multipliziere über Kreuz jeweils eine falsche Zahl mit dem Fehlbetrag der anderen. Ziehe eins vom anderen ab, und was da als Rest bleibt, teile durch den vorher berechneten Teiler. So kommt die Lösung der Aufgabe heraus. Führt aber eine falsche Zahl zu einem zu großen und die andere zu einem zu kleinen Ergebnis, so addiere die zwei Fehlbeträge. Was dabei herauskommt, ist dein Teiler. Danach multipliziere über Kreuz, addiere und dividiere. So kommt die Lösung der Aufgabe heraus.“

Die Regula falsi als numerische Methode

Die ursprünglichen Schöpfer der entsprechenden numerischen Verfahren sind nicht bekannt. Die Illinois-Methode wurde 1971 veröffentlicht, mit einem Hinweis auf den möglichen Ursprung in den 1950er Jahren im Rechenzentrum der University of Illinois. Die 1972 öffentlich beschriebene Pegasus-Methode wurde so benannt, weil unbekannte Autoren sie zuvor auf einem Röhrenrechner des Typs Pegasus eingesetzt hatten; dieser Rechner war von der britischen Firma Ferranti Pegasus ab 1956 ausgeliefert worden.

Weblinks

Commons: Regula falsi – Sammlung von Bildern, Videos und Audiodateien