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)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]$ - jeżeli $f(x_0)$ ma ten sam znak co $f(b)$ to powtarzamy szukanie pierwiastka w przedziale $[a, x_0]$ ===== ===== {{ 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 | }} ===== 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?800 | }} ===== ===== * zatrzymanie algorytmu gdy $|x_{i}-x_{i-1}|<\epsilon$ lub gdy $f(x_i) < \epsilon$ * proces może być rozbieżny (ustalenie maks. liczby iteracji lub zatrzymanie gdy $|x_{i}-x_{i-1}|$ rośnie) ===== Zadanie: ==== Zaimplementuj program znajdujący rozwiązanie równania postaci $$x = \sin{x} + \frac{1}{4}$$ za pomocą metod **bisekcji** oraz **siecznych** ===== ===== Program wczytuje wartości początkowe $a$ i $b$ po czym wypisuje dla każdej z metod: * przybliżoną wartość miejsca zerowego $x_0$ lub informację o braku znalezienia pierwiastka lub o tym, że proces jest rozbieżny * wartość funkcji $f(x_0)$ w wyznaczonym punkcie * wartość zastosowanej precyzji obliczeń $\epsilon$ * ilość wykonanych iteracji ===== 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.