Metoda Riddersa

Metoda Riddersa – iteracyjna metoda numeryczna, służąca do rozwiązywania równań nieliniowych z jedną niewiadomą.

Metoda Riddersa jest to jedna z odmian metody fałszywych przybliżeń (łac. regula falsi). Opiera się ona na aproksymacji równania za pomocą funkcji eksponencjalnej. Algorytm ten gwarantuje, że punkt wyznaczony w kolejnej iteracji, będzie zawierał się w założonym przedziale. Wykorzystanie funkcji eksponenty do aproksymacji powoduje osłabienie niekorzystnego wpływu wypukłości funkcji aproksymowanej. Metoda ta jest prostsza w implementacji niż podobnie działające metody Brenta i Mullera, a jej zbieżność w porównaniu z analogicznymi metodami jest duża. Dokładność wartości rozwiązania metody zwiększa się dwukrotnie po dwóch iteracjach. Konieczność wyznaczenia dwóch wartości w każdej iteracji powoduje, że rząd zbieżności metody wynosi ${\displaystyle {\sqrt {2}}.}$

Z racji tego, że jest to rodzaj reguly falsi spełnione muszą być następujące założenia: w przedziale ${\displaystyle (x_{a};x_{b})}$ istnieje jedno miejsce zerowe (pierwiastek), oraz że funkcja ${\displaystyle f(x)}$ jest ciągła w przedziale ${\displaystyle <x_{a};x_{b}>.}$

Przebieg algorytmu

• Wyznaczamy środek przedziału:

${\displaystyle x_{c}={\frac {(x_{a}+x_{b})}{2}}}$

• Szukamy ${\displaystyle e^{Q}}$ spełniającego równanie:

${\displaystyle f(x_{a})-2f(x_{c})e^{Q}+f(x_{b})e^{2Q}=0}$

• Otrzymujemy:

${\displaystyle e^{Q}={\frac {f(x_{c})+sign[f(x_{b})]{\sqrt {(f(x_{c})^{2}-f(x_{a})f(x_{b})}}}{f(x_{b})}}}$

• Stosujemy regule falsi, lecz nie do wartości ${\displaystyle f(x_{a}),}$ ${\displaystyle f(x_{b})}$ i ${\displaystyle f(x_{c}),}$ ale dla: ${\displaystyle f(x_{a}),}$${\displaystyle f(x_{c})e^{Q}}$ i ${\displaystyle f(x_{b})e^{2Q}}$ znajdując przy ich pomocy nowe ${\displaystyle x_{d}.}$

${\displaystyle x_{d}=x_{c}+(x_{c}-x_{a}){\frac {sign[f(x_{a})-f(x_{b})]f(x_{c})}{\sqrt {(f(x_{c})^{2}-f(x_{a})f(x_{b})}}}}$

• Sprawdzamy wartość ${\displaystyle f(x_{d})}$ jeżeli jest ona wystarczająco bliska 0 to algorytm kończy pracę, w innym wypadku koniec przedziału zostaje zastąpiony przez ${\displaystyle x_{d},}$ następuje ponowne przejście do punktu pierwszego. Iteracje powtarzamy, aż do uzyskania wartości satysfakcjonującej.

Pierwsze 4 iteracje na przykładzie funkcji:${\displaystyle f(x)=x^{3}-11x^{2}+14x+80}$

Iteracja nr 1

${\displaystyle x_{a}=-6,}$ ${\displaystyle f(x_{a})=-616,}$
${\displaystyle x_{b}=10,}$ ${\displaystyle f(x_{b})=120,}$
${\displaystyle x_{c}=8,}$ ${\displaystyle f(x_{c})=72,}$
${\displaystyle e^{Q}=2{,}9438,}$
${\displaystyle x_{d}=-0{,}048,}$ ${\displaystyle f(x_{d})=79{,}303.}$

Iteracja nr 2

${\displaystyle x_{a}=-6,}$ ${\displaystyle f(x_{a})=-616,}$
${\displaystyle x_{b}=-0{,}048,}$ ${\displaystyle f(x_{b})=79{,}303,}$
${\displaystyle x_{c}=-3{,}024,}$ ${\displaystyle f(x_{c})=-90{,}577,}$
${\displaystyle e^{Q}=1{,}8698,}$
${\displaystyle x_{d}=-1{,}8955,}$ ${\displaystyle f(x_{d})=7{,}1331.}$

Iteracja nr 3

${\displaystyle x_{a}=-6,}$ ${\displaystyle f(x_{a})=-616,}$
${\displaystyle x_{b}=-1{,}8955,}$ ${\displaystyle f(x_{b})=7{,}1331,}$
${\displaystyle x_{c}=-3{,}9477,}$ ${\displaystyle f(x_{c})=-208{,}223,}$
${\displaystyle e^{Q}=1{,}4435,}$
${\displaystyle x_{d}=-1{,}922,}$ ${\displaystyle f(x_{d})=0{,}5475.}$

Iteracja nr 4

${\displaystyle x_{a}=-6,}$ ${\displaystyle f(x_{a})=-616,}$
${\displaystyle x_{b}=-1{,}922,}$ ${\displaystyle f(x_{b})=0{,}5475,}$
${\displaystyle x_{c}=-3{,}9961,}$ ${\displaystyle f(x_{c})=-215{,}4126,}$
${\displaystyle e^{Q}=1{,}4272,}$
${\displaystyle x_{d}=-1{,}9994,}$ ${\displaystyle f(x_{d})=0{,}0415.}$

Jeżeli uznamy, że wynik 0,0415 jest wystarczającym przybliżeniem wartości 0 to algorytm kończy działanie, w przeciwnym wypadku kontynuujemy iteracje do uzyskania wartości satysfakcjonującej.

• Ridders, C. (1979). „A new algorithm for computing a single root of a real continuous function”. IEEE Transactions on Circuits and Systems 26: 979–980.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Section 9.2.1. Ridders’ Method”. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press.