Regula falsi

Das Regula-falsi-Verfahren (lateinisch: regula falsi = „Regel des Falschen“), auch: Regula duarum falsarum Posicionum (lateinisch: regula duarum falsarum posicionum = „Regel vom zweifachen falschen Ansatz“),^[1][2] Falsirechnung rsp. Falsi-Rechnung oder lineares Eingabeln genannt, ist eine Methode zum numerischen Berechnen von Nullstellen reeller Funktionen. Es kombiniert Methoden vom Sekantenverfahren und der Bisektion.

Das Verfahren (Primitivform)

Visualisierung der Regula falsi

Das Regula-falsi-Verfahren startet mit zwei Stellen (in der Nähe der Nullstelle) a₀ und b₀, deren Funktionsauswertungen f(a₀), f(b₀) 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})}\,$.

Nun wählt man a_k, b_k folgendermaßen:

• $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.

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(x) im k-ten Intervall nicht strikt konkav bzw. konvex ist, also im Intervall ein Vorzeichenwechsel der zweiten Ableitung vorliegt, liegt superlineare Konvergenz vor.

Verbesserung des Verfahrens

Ist f(x) 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. Die andere konvergiert jetzt nur noch linear gegen die Lösung.

Abhilfe schaffen die folgenden Verfahren.

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

Idee der Verfahren

Den verbesserten Verfahren liegt die folgende Idee zu Grunde. Falls sich die „linke“ Intervallgrenze x₁ im aktuellen Schritt nicht verändert – d. h. dass die tatsächliche Nullstelle zwischen der „linken“ Grenze und der genäherten Nullstelle liegt –, multipliziert man f(x₁) einfach mit einem Faktor 0 < m < 1 und bringt den Funktionswert an der Stelle x₁ 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{sonst}:\\ ~~\left[f_1:=m\cdot f_1,~x_2:=z,~f_2:=f_z,~x_1~\text{bleibt}\right.\\ \end{array}\right.\\~\\ \text{nimm beliebigen Wert aus}~[x_1,x_2]~\mathrm{als~N\ddot{a}herung~f\ddot{u}r}~x^* \end{array}$

Dabei sind x₁,x₂ die Intervallgrenzen im k-ten Schritt, f₁,f₂ und f_z die Funktionswerte an den Stellen x₁,x₂ und z. ε_x,ε_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 ε_x und im vierten Fall ε_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}\geq 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| < epsz 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 i. d. R. anderen Verfahren (wie z. B. dem Newton-Verfahren) vorzuziehen.

Geschichte

Das älteste erhaltene Dokument, das vom Wissen um die Methode des doppelten falschen Ansetzens zeugt, ist die indisch-mathematische Schrift „Vaishali Ganit“ (ca. 3. Jh. v. Chr.). Der altchinesische, mathematische Text, genannt Die Neun Kapitel der mathematischen Kunst (九章算術, 200 v. Chr. – 100 n. Chr.), erwähnt den Algorithmus ebenfalls. In diesem Text wurde das Verfahren in Beispielen allerdings nur auf lineare Gleichungen angewandt, sodass die Lösungen in nur einer Iteration erreicht wurden. Leonardo da Pisa (Fibonacci) beschrieb das Verfahren des doppelten falschen Ansetzens in seinem Buch „Liber Abaci“ (1202 n. Chr.),^[1] angelehnt an eine Methode, die er aus arabischen Quellen gelernt hatte.

Auch Adam Ries kannte die regula falsi und beschrieb die Methode, wie folgt:^[2]

„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.“

Einzelnachweise

1. ↑ ^{a b} Leonardo da Pisa: Liber abbaci. 1202, Kapitel 13. De regula elcataym qualiter per ipsam fere omnes erratice questiones soluantur.
2. ↑ ^{a b} Adam Ries: Rechenung auff der linihen und federn. 1522 (Siehe Matroids Matheplanet: Die regula falsi – Adam Ries’ wichtigste Rechenregel).