Metoda Riddersa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Cztery pierwsze iteracje algorytmu, niebieska pozioma linia oznacza funkcję x=x_d

Metoda Riddersaiteracyjna 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 \sqrt{2}.

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


Przebieg algorytmu
  • Wyznaczamy środek przedziału:
x_c=\frac{(x_a+x_b)}{2}
  • Szukamy e^Q spełniającego równanie:
f(x_a )-2f(x_c ) e^Q  -f(x_b ) e^{2Q}  =0
  • Otrzymujemy:
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 f(x_a ),f(x_b ) i f(x_c ), ale dla: f(x_a ),f(x_c ) e^Q i f(x_b ) e^{2Q} znajdując przy ich pomocy nowe x_d.
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ść 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 x_d, następuje ponowne przejście do punktu pierwszego. Iteracje powtarzamy, aż do uzyskania wartości satysfakcjonującej.

Przykładowe rozwiązanie[edytuj | edytuj kod]

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

Animacja przedstawia cztery pierwsze iteracje algorytmu

Iteracja nr 1

x_a=-6, f(x_a)=-616,
x_b=10, f(x_b)= 120,
x_c=-6, f(x_c)= 72,
e^Q=2.9438,
x_d=-0.048, f(x_d)= 79,303.

Iteracja nr 2

x_a=-6, f(x_a)=-616,
x_b=-0.048, f(x_b)= 79,303,
x_c=-3.024, f(x_c)= -90,577,
e^Q=1.8698,
x_d=-1.8955, f(x_d)= 7,1331.

Iteracja nr 3

x_a=-6, f(x_a)=-616,
x_b=-1.8955, f(x_b)= 7,1331,
x_c=-3.9477, f(x_c)= -208,223,
e^Q=1.4435,
x_d=-1.922, f(x_d)= 0,5475.

Iteracja nr 4

x_a=-6, f(x_a)=-616,
x_b=-1.922, f(x_b)= 0,5475,
x_c=-3.9961, f(x_c)= -215,4126,
e^Q=1.4272,
x_d=-1.9994, 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.

Bibliografia[edytuj | edytuj kod]