Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2023 mgr Jerzy Wałaszek |
SPIS TREŚCI |
|
Podrozdziały |
Algorytm regula falsi ( łac. fałszywa prosta) (ang. false position method ) posiada takie same warunki początkowe jak opisany wcześniej algorytm bisekcji:
Nazwa "fałszywej prostej" bierze się stąd, iż w coraz węższych przedziałach wykres funkcji zaczyna przypominać wykres prostej:
Naszą funkcją jest:
W przedziale [-3, 1] funkcja posiada wykres:
Zmniejszamy przedział do [-1,5 , -1]. Wykres jest następujący:
Zwróć uwagę, iż w tym przedziale wykres jest bardzo zbliżony do wykresu prostej. Ponieważ nie jest to dokładna prosta, stąd nazwa "fałszywa prosta". W metodzie traktujemy funkcję tak, jakby była funkcją, której wykres jest prostą. Prosta ta przecina oś OX w punkcie, który jest przybliżeniem pierwiastka. Wyliczamy punkt przecięcia fałszywej prostej x0 z osią OX, obliczamy wartość funkcji w tym punkcie. Jeśli jest ona dostatecznie bliska zeru, to kończymy z wynikiem x0. Jeśli nie trafiliśmy, to punkt x0 dzieli przedział poszukiwań pierwiastka na dwie części ( tutaj nie będą to zwykle połówki jak w metodzie bisekcji ). Za nowy przedział przyjmujemy tę część, w której funkcja ma różne znaki na krańcach.
Dlaczego metoda regula falsi jest zwykle szybsza od metody bisekcji? Otóż wykorzystywany jest tutaj przebieg funkcji. W metodzie bisekcji x0 było wyznaczane zawsze w środku przedziału poszukiwań pierwiastka. Tutaj punkt ten jest wyliczany jako punkt przecięcia fałszywej prostej z osią OX. Gdy przedział maleje, prosta ta zaczyna coraz bardziej przypominać faktyczny przebieg funkcji, a zatem x0 jest wyznaczany bardziej trafnie niż zawsze w środku przedziału. Dlatego algorytm wymaga mniej kroków.
Podstawowym problemem jest tutaj znalezienie wzoru na x0. Wbrew pozorom jest to łatwe pod warunkiem, iż znasz geometrię.
Fałszywą prostą prowadzimy zawsze, tak aby przechodziła przez punkty krańcowe wykresu: a,f(a)) i (b,f(b). Popatrz na rysunek powyżej. Powstają tutaj dwa trójkąty podobne:
![]() |
p – podstawa trójkąta niebieskiego w – wysokość trójkąta niebieskiego p' – podstawa
trójkąta żółtego |
Długości boków trójkątów są następujące:
p' = b - x0
w' = – f ( b )
Ponieważ trójkąty są podobne, to odpowiadające sobie boki spełniają proporcje:
Podstawiamy i wyliczamy x0:
Mamy wszystkie elementy.
εy | – | dokładność obliczania funkcji |
a | – | początek przedziału poszukiwań pierwiastka |
b | – | koniec przedziału poszukiwań pierwiastka |
f() | – | funkcja, której pierwiastek będzie obliczany |
n | – | maksymalna liczba aproksymacji |
x0 | – | przybliżony pierwiastek funkcji |
fa | – | wartość funkcji w punkcie a |
fb | – | wartość funkcji w punkcie b |
fx | – | wartość funkcji w punkcie x0 |
K01: | fa ← f ( a ) fb ← f ( b ) |
Obliczamy wartości funkcji na krańcach przedziału [a,b]. |
K02: | Jeśli fa ·
fb > 0, to Zakończ z błędem |
Funkcja nie ma różnych znaków na krańcach przedziału [a,b]. |
K03: | ![]() |
Wyznaczamy x0. |
K04: | Jeśli n = 0, to zakończ inaczej n ← n - 1 |
Przekroczono dozwoloną liczbę iteracji. Wynik w x0. |
K05: | fx ← f ( x0 ) | Obliczamy wartość funkcji w środku przedziału |
K06: | Jeśli | fx | < εy, to zakończ |
Sprawdzamy, czy funkcja ma wartość 0 w środku przedziału. Wynik w x0. |
K07: | Jeśli fx ·
fa < 0, to b ← x0, fb ← fx Inaczej a ← x0, fa ← fx |
Za nowy przedział [a,b]
przyjmujemy tę połówkę [a,x0], [x0,b], w której funkcja zmienia znak |
K08: | Idź do kroku K03 | Kontynuujemy obliczenia |
Zwróć uwagę, że algorytm regula falsi jest praktycznie taki sam jak algorytm bisekcji. Różnice występują w krokach 3, 4 i 7.
Poniższy program jest przykładową realizacją algorytmu bisekcji. Program oblicza pierwiastek funkcji:
Wykres tej funkcji w przedziale [-3,1] jest następujący:
Z wykresu wynika, iż pierwiastek znajduje się w przedziale [-1,1 , -1]. Taki więc przedział został przyjęty w programie.
Przykładowy program w języku C++
// Pierwiastek funkcji - metoda regula falsi // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //------------------------------------------ #include <iostream> #include <cmath> #include <iomanip> using namespace std; // Tutaj definiujemy funkcję, której pierwiastek jest wyliczany //------------------------------------------------------------- double f(double x) { return sin(x*x-x+1/3.0)+0.5*x; } // Tutaj definiujemy parametry początkowe double epsy = 1e-14; // Dokładność y double a = -1.1; // Początek przedziału poszukiwań pierwiastka double b = -1.0; // Koniec przedziału poszukiwań pierwiastka int n = 64; // Maksymalna liczba obiegów // Program główny //--------------- int main() { // Zmienne double fa,fb,fx,x0; // Licznik obiegów pętli // Zmienna informująca o znalezieniu wyniku bool result = false; setlocale(LC_ALL,""); cout << setprecision(15) << fixed; cout << "Obliczanie przybliżonego pierwiastka funkcji metodą regula falsi" << endl << "----------------------------------------------------------------" << endl << endl; // Obliczamy i zapamiętujemy wartości funkcji na krańcach przedziału [a,b] fa = f(a); fb = f(b); //Sprawdzamy, czy na krańcach przedziału [a,b] wartości funkcji mają różne znaki if(fa * fb > 0) cout << "BŁĄD!!! Funkcja nie ma różnych znaków na krańcach przedziału"; else { result = true; // W pętli wyznaczamy kolejne przybliżenia pierwiastka while(true) { // Wyznaczamy x0 x0 = (fa * b - fb * a) / (fa - fb); // Sprawdzamy, wykonano maksymalną liczbę iteracji. if(!n) break; // Jeśli tak, to kończymy else n--; // Obliczamy i zapamiętujemy wartość funkcji w punkcie x0 fx = f(x0); // Sprawdzamy, czy wartość funkcji jest dostatecznie bliska zeru if(fabs(fx) < epsy) break; // Jeśli tak, to kończymy // Za nowy przedział [a,b] przyjmujemy tą z części [a,x0], [x0,b], // w której funkcja ma różne znaki na krańcach if(fa * fx < 0) { b = x0; fb = fx; } else { a = x0; fa = fx; } } } if(result) cout << "Pierwiastek x0 = " << setw(18) << x0 << endl << "Wartość funkcji f(x0) = " << setw(18) << f(x0) << endl << "Dokładność dla y epsy = " << setw(18) << epsy << endl << "Liczba obiegów = " << 64 - n; cout << endl << endl; return 0; } |
Wynik |
Obliczanie przybliżonego pierwiastka
funkcji metodą regula falsi ---------------------------------------------------------------- Pierwiastek x0 = -1.077713513691339 Wartość funkcji f(x0) = 0.000000000000001 Dokładność dla y epsy = 0.000000000000010 Liczba obiegów = 9 |
Zwróć uwagę na liczbę obiegów oraz wartość funkcji dla wyliczonego pierwiastka. Porównaj je z wartościami otrzymanymi w metodzie bisekcji:
Obliczanie przybliżonego pierwiastka funkcji metodą
bisekcji ------------------------------------------------------------ Pierwiastek x0 = -1.077713513691339 Wartość funkcji f(x0) = 0.000000000000002 Dokładność dla x epsx = 0.000000000000010 Dokładność dla y epsy = 0.000000000000010 Liczba obiegów i = 44 |
Metoda regula falsi ze względu na swoją prostotę jest dobrym wyborem przy obliczaniu pierwiastków funkcji.
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2023 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.