Edytuj stronę Odnośniki Fold/unfold all ODT export Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić. ~~NOCACHE~~ ~~REVEAL theme=simple&size=1024x800~~ ====== Lab. 4 Rozwiązywanie równań nieliniowych ====== ===== Znajdowanie pierwiastków ===== Iteracyjne metody znajdowania miejsc zerowych funkcji $$f(x) = 0 $$ Problemy: * lokalizacja pierwiastka (punkt startowy, przedział izolacji) * zbieżność procesu iteracyjnego, szybkość zbieżności ===== Metody iteracyjne ===== * Metody dwupunktowe * **bisekcji (połowienia)** * **siecznych** * regula falsi * Metody jednopunktowe * stycznych (Newtona) * metoda iteracji prostych ===== Przedział izolacji ===== * gdy $f(a) \cdot f(b) < 0$ dla funkcji ciągłych to istnieją pierwiastki w $[a, b]$ * gdy pochodna nie zmienia znaku w $[a, b]$ to istnieje jeden pierwiastek {{ zajecia:mn1_2021_2:miejsce_zerowe.png | }} ===== Metoda bisekcji ===== - wybieramy przedział $[a,b]$ taki aby $f(a)f(b)<0$ - dzielimy przedział na połowy \\ $$x_{0}=a+\frac{b-a}{2}$$ - jeżeli $|f(x_0)| < \epsilon$ to $x_0$ jest znalezionym pierwiastkiem - jeżeli $f(x_0)$ ma ten sam znak co $f(a)$ to powtarzamy szukanie pierwiastka w przedziale $[x_0, b]$ (krok 2) - jeżeli $f(x_0)$ ma ten sam znak co $f(b)$ to powtarzamy szukanie pierwiastka w przedziale $[a, x_0]$ (krok 2) ===== ===== {{ zajecia:mn1_2021_2:bisekcja.png |}} ===== ====== * (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 ===== Przykład ==== Miejsca zerowe funkcji $f(x) = x^2 - 1$ Sprawdź przedziały izolacji: $[0, 1.5]$, $[2, 3]$. Jaki jest problem z drugim przedziałem? Czy proces jest zawsze zbieżny? ===== ===== <file C bisekcja.c> #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; } </file> ===== Problemy bisekcji ===== {{ zajecia:mn1_2021_2:bisekcja-problemy.png?600 | }} ===== Błąd metody ===== dla $n$ iteracji przedział izolacji maleje do rozmiaru $$ \frac{1}{2^n}(b - a) $$ metoda jest zbieżna liniowo, ze stałą asymptotyczną błedu $\frac{1}{2}$. ===== Metoda siecznych ===== Dla dwóch wartości początkowych $x_0$ i $x_1$ kolejne przybliżenie za pomocą linii prostej (siecznej) $$x_{n+1}=x_{n}-f\left(x_{n}\right)\left(\frac{x_{n}-x_{n-1}}{f\left(x_{n}\right)-f\left(x_{n-1}\right)}\right)$$ ===== ===== {{ zajecia:mn1_2021_2:siecznych.png?1000 | }} ===== ===== * w metodzie siecznych nie musi byc spełnione $f(x_n)\cdot f(x_{n+1}) < 0$, jednak zaleca się aby początkowe punkty $x_0, x_1$ spełniały tą zależność * zatrzymanie algorytmu gdy $f(x_i) < \epsilon$ lub gdy $|x_{i}-x_{i-1}|<\epsilon$ (dla małych przedziałow $[a, b]$, w okolicy rozwiązania) * proces może być rozbieżny, wówczas zatrzymanie algorytmu można zabezpieczyć przez: * ustalenie maksymalnej liczby iteracji * zatrzymanie gdy $|x_{i}-x_{i-1}|$ rośnie ===== Regula falsi ===== Metoda siecznych ze stałym punktem. {{ zajecia:mn1_2021_2:regula_falsi_method.png?600| }} ===== ===== Złożenia: * przedział $[a,b]$ jest przedziałem izolacji i ma jeden pierwiastek * pierwsza i druga pochodna na odcinku $[a,b]$ nie zmienia znaku ===== Algorytm: regula falsi ===== - wybieramy przedział $[a,b]$ taki aby $f(a)f(b)<0$ - wyznaczamy przybliżenie pierwiastka $$x_0= b-f\left(b\right)\left(\frac{b-a}{f\left(b\right)-f\left(a\right)}\right)$$ - jeżeli $|f(x_0)| < \epsilon$ to $x_0$ jest znalezionym pierwiastkiem (koniec) - jeżeli $f(x_0) f(a) < 0$ to wyznaczamy kolejne przybliżenie ustawiając $b=x_0$ (krok 2) - w przeciwnym wypadku wyznaczamy kolejne przybliżenie ustawiając $a=x_0$ (krok 2) ===== Zadanie 4 ===== Treść zadania znajduje się w Moodle pod adresem [[https://moodle.umk.pl/WFAIIS/mod/assign/view.php?id=4588|Zadanie 4]] ===== Dodatkowe ćwiczenia ===== **Ćw. 1** Napisz program znajdujący pierwiastki rzeczywiste jednego z poniższych równań z dokładnością $\epsilon=1\cdot10^{-6}$ * $x-2=\sqrt[3]{x}$ * $10x = e^{-x}$ * $x^2 - 6x - 8 = \ln{x}$ **Ćw. 2** Rozwiąż zadanie z zajęć używając metody [[wppl>Regula falsi]], która jest modyfikacją metody siecznych polegająca na tym, że jeden punktów $a$ lub $b$ jest stały. Jakie warunki musi spełniać funkcja na odcinku $[a, b]$ aby ta metoda znalazła pierwiastek.