To tylko jedna z 3 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Algorytm Newtona-Raphsona Do odnajdywania wartości pierwiastka kwadratowego z liczby a
Metoda ta polega na obliczaniu kolejnych przybliżeń pierwiastka danej liczby a. Przybliżenie (n+1) otrzymujemy przez podstawienie przybliżenia n-tego do wzoru:
Wynika to z faktu, że jeśli nasze przybliżenie nie jest na tyle dokładne by nas zadowolić, to kolejne dokładniejsze będzie na pewno gdzieś po środku pomiędzy liczbą i liczbą (dwa boki prostokąta o polu a, który nam powstał zamiast kwadratu, poprzez niedokładne wytypowanie długości jego boku, muszą się coraz bardziej długościami zbliżać do siebie)
Jako pierwsze przybliżenie można przyjąć dowolną liczbę dodatnią
Obliczenia kolejnych przybliżeń kończymy, gdy:
gdzie e - przyjęta dokładność obliczeń
Bisekcja Metoda bisekcji (połowienia) jest jedną z najprostszych metod numerycznego rozwiązywania algebraicznych równań nieliniowych, czyli znajdowania przybliżonej wartości pierwiastka równania:
f(x)=0 O funkcji f(x) zakłada się, że jest ciągła na przedziale domkniętym , wewnątrz którego znajduje się dokładnie jeden, wyizolowany pierwiastek i, na którego końcach wartości funkcji f(x) mają przeciwne znaki (czyli f(x A )f(x B ) na połowy punktem
x C = (x A + x B )/2 Jeżeli f(x C ) = 0 , to x C jest szukanym pierwiastkiem, jeśli zaś f(x C ) 0 , to z otrzymanych dwóch przedziałów oraz , wybieramy do dalszej analizy ten, na końcach którego funkcja f(x) ma przeciwne znaki. To znaczy, jeśli f(x A )f(x C ) , zatem wartość x C podstawiamy w miejsce x B , w przeciwnym przypadku wartość x C podstawiamy w miejsce x A . Z kolei ten nowo wybrany przedział dzielimy na połowy wyznaczając nowy punkt x C , ponownie badamy wartość funkcji f(x) w punkcie x C i znaki funkcji f(x) na końcach przedziałów itd. W wyniku takiego postępowania po pewnej liczbie kroków albo otrzymany pierwiastek dokładny, tzn. dla pewnego n otrzymamy f(xC)=0 , albo ciąg przedziałów takich że : f(x i A )f(x i B )
(…)
… rozwiązywanego równania. Ostatnia obliczona wartość xC może stanowić jego przybliżenie.
Jako kryterium zakończenia obliczeń można przyjąć wykonanie maksymalnej dopuszczalnej liczby iteracji, MaxIter, lub otrzymanie przedziału < xiA ; xiB > o długości mniejszej od zadanej dokładności epsilon, tzn.
|xiA - xiB| < eps.
Metoda hybrydowa
Metoda hybrydowa jest połączeniem bisekcji i algorytmu Newtona-Raphsona.
Program
Wnioski:
Metoda hybrydowa jest zawsze zbieżna (dla funkcji ciągłych), jeżeli metoda Newtona jest zbieżna to ilość iteracji jest dużo mniejsza niż w przypadku bisekcji, natomiast gdy metoda Netwona jest rozbieżna to algorytm korzysta z bisekcji która jest zawsze zbieżna tak więc zawsze otrzymamy wynik.
2
…
... zobacz całą notatkę
Komentarze użytkowników (0)