Iteracyjne metody znajdowania miejsc zerowych funkcji

Problemy:

lokalizacja pierwiastka (punkt startowy, przedział izolacji)

zbieżność procesu iteracyjnego, szybkość zbieżności

Metody dwupunktowe

bisekcji (połowienia)

siecznych

regula falsi

Metody jednopunktowe

stycznych (Newtona)

metoda iteracji prostych

gdy dla funkcji ciągłych to istnieją pierwiastki w

gdy pochodna nie zmienia znaku w to istnieje jeden pierwiastek

wybieramy przedział taki aby

dzielimy przedział na połowy

jeżeli to jest znalezionym pierwiastkiem

jeżeli ma ten sam znak co to powtarzamy szukanie pierwiastka w przedziale (krok 2)

jeżeli ma ten sam znak co to powtarzamy szukanie pierwiastka w przedziale (krok 2)

(prawie) zawsze zbieżna

wolno zbieżna (zbieżność liniowa)

nie uwzględnia kształtu funkcji w poszukiwaniu pierwiastka

często stosowana do znalezienia przybliżonego przedziału pierwiastka dla szybciej zbieżnych metod

Miejsca zerowe funkcji

Sprawdź przedziały izolacji: , .

Jaki jest problem z drugim przedziałem?

Czy proces jest zawsze zbieżny?

#include<stdio.h> #include<math.h> float f(float x) { return (x*x)-1; } int main() { float a, b, x0, eps; int i; printf("Podaj przedzial izolacji:"); scanf("%f%f", &a, &b); eps = 1e-6; i=0; while(fabs(a-b)>eps) { i++; x0 = (a+b)/2; printf("%f %f %f\n", a, b, b-a); if (fabs(f(x0)) < eps) break; if(f(a)*f(x0) < 0) b=x0; else a=x0; } printf("x0 = %f\niterations %d\n", x0, i); printf("f(%g)=%g\n", x0, f(x0)); return 0; }

dla iteracji przedział izolacji maleje do rozmiaru

metoda jest zbieżna liniowo, ze stałą asymptotyczną błedu .

Dla dwóch wartości początkowych i kolejne przybliżenie za pomocą linii prostej (siecznej)

w metodzie siecznych nie musi byc spełnione , jednak zaleca się aby początkowe punkty spełniały tą zależność

zatrzymanie algorytmu gdy lub gdy (dla małych przedziałow , w okolicy rozwiązania)

proces może być rozbieżny, wówczas zatrzymanie algorytmu można zabezpieczyć przez:

ustalenie maksymalnej liczby iteracji

zatrzymanie gdy rośnie

Metoda siecznych ze stałym punktem.

Złożenia:

przedział jest przedziałem izolacji i ma jeden pierwiastek

pierwsza i druga pochodna na odcinku nie zmienia znaku

wybieramy przedział taki aby

wyznaczamy przybliżenie pierwiastka

jeżeli to jest znalezionym pierwiastkiem (koniec)

jeżeli to wyznaczamy kolejne przybliżenie ustawiając (krok 2)

w przeciwnym wypadku wyznaczamy kolejne przybliżenie ustawiając (krok 2)

Treść zadania znajduje się w Moodle pod adresem Zadanie 4

Ćw. 1

Napisz program znajdujący pierwiastki rzeczywiste jednego z poniższych równań z dokładnością

Ćw. 2 Rozwiąż zadanie z zajęć używając metody Regula falsi, która jest modyfikacją metody siecznych polegająca na tym, że jeden punktów lub jest stały.

Jakie warunki musi spełniać funkcja na odcinku aby ta metoda znalazła pierwiastek.