Regula Falsi

Das Regula-Falsi-Verfahren (lat. „Regel des falschen Ansatzes“) 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₀) unterschiedliches 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
• $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]$.
• Solange f(x) im k-ten Intervall nicht strikt konkav bzw. konvex ist, also $\forall\zeta(\zeta\in[a_k,b_k]\rightarrow\exists\xi(\xi\in[a_k,b_k]\rightarrow f''(\zeta)\cdot f''(\xi)\leq 0))$, liegt superlineare Konvergenz vor.

Verbesserung des Verfahrens

Ist f(x) konkav oder konvex im Intervall [a_k,b_k], also $\forall\xi(\xi\in[a_k,b_k]\rightarrow\forall\zeta(\zeta\in[a_k,b_k]\rightarrow f''(\xi)\cdot f''(\zeta)>0))$, 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

Den folgenden Algorithmus haben diese Verfahren gemeinsam:

$\!\, \begin{array}{l} \text{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~\text{mit}~s=\frac{f_2-f_1}{x_2-x_1}\\ f_z:=f(z)\\ \text{falls}~f_z\cdot f_2<0:\\ ~~\left[x_1:=x_2,f_1:=f_2,x_2:=z,f_2:=f_z\right.\\ \text{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\overset{..}{a}herung~f\overset{..}{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. $\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ähren hier die Disjunktion, die Konjunktion, die Negation des ersten und die Negation 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örk-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}$

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.