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. 5 Rozwiązywanie równań nieliniowych ====== ===== Metody iteracyjne ===== * Metody dwupunktowe * bisekcji (połowienia) * siecznych * regula falsi * Metody jednopunktowe * **stycznych (Newtona)** * **metoda iteracji prostych (punktu stałego)** ===== Metoda Newtona ===== Metoda stycznej (Newtona-Raphsona) uwzględnia kształt funkcji {{ zajecia:mn1_2021_2:metoda_newtona.png?600 | }} Zał: znamy pochodną funkcji $f'(x)$ ===== ===== Równanie stycznej w punkcie $x_0$ $$y(x)=f^{\prime}\left(x_{o}\right)\left(x-x_{o}\right)+f\left(x_{o}\right)$$ Przybliżenie, w miejscu przecięcia stycznej z osią OX - metoda Newtona-Raphsona $$x_{i+1}=x_{i}-\frac{f\left(x_{i}\right)}{f^{\prime}\left(x_{i}\right)}$$ Warunek stopu: $|x_{x+1} - x_i|<\epsilon$ lub $|f(x_i)| < \epsilon$ ===== ===== * szybciej zbieżna niż bisekcja (zbieżność kwadratowa) * nie zawsze zbieżna, zbieżna gdy $f'$ ma taki sam znak co $f''$ * wymagana analityczna wartość pochodnej $f'$, przybliżenie za pomocą metod różnicowych prowadzi do metody stycznych {{ zajecia:mn1_2021_2:newton_problems.png?600 | }} ===== Przykład ===== Funkcja $f(x) = x^3 + x - 1$ {{ zajecia:mn1_2021_2:fun_x3_plot.png?400 | }} Pochodna $f'(x) = 3x^2 + 1$ Wzór iteracyjny $$x_{i+1}=x_{i}-\frac{f\left(x_{i}\right)}{f^{\prime}\left(x_{i}\right)} = x_i - \frac{x_i^3 + x - 1}{3x_i^2+1} = \frac{2x^3+1}{3x^2+1}$$ ===== ===== <file C newton.c> #include<stdio.h> #include<math.h> #define EPS 1e-6 float f(float x) { return x * (x * x + 1) - 1; } float fp(float x) { return 3.0 * x * x + 1.0; } int main() { float x0, x1; int i=0, n=100; printf("Punkt startowy x0 = "); scanf("%f", &x0); while(fabs(f(x0)) > EPS && i < n) { x1 = x0 - f(x0) / fp(x0); printf("%d %f\n", i+1, x1); x0 = x1; i++; } if (i == n) printf("Nie znaleziono rozwiazania\n"); else { printf("x = %f\n", x1); printf("ilosc iteracji = %d\n", i); } } </file> ===== Metoda iteracji prostych ===== Równanie $f(x)=0$ sprowadzamy do postaci $$x = g(x)$$ wówczas otrzymujemy zaleznośc rekurencyjną $$x_{i+1} = g(x_{i})$$ ===== ===== * metoda może nie być zbieżna, zależy to od: * punktu startowego * postaci funkcji $g(x)$ {{ zajecia:mn1_2021_2:iteracje_proste.png?600 | }} ===== Przykład ===== Funkcja $f(x) = x^3 + x - 1$ $$x = 1 - x^3 = g(x)$$ Wzór iteracyjny $$x_{i+1}= 1 - x^3_{i} $$ Ćwiczenie: zaimplementuj program znajdujący miejsce zerowe $f(x) = x^3 + x - 1$ za pomocą metody iteracji prostej. ===== Inna postać funkcji g(x) ===== $$x = 1 - x^3$$ * $g(x) = 1 - x^3$ rozbieżna * $g(x) = \sqrt[3]{1-x}$ * $g(x) = \frac{1+2x^3}{1+3x^2}$ Ćwiczenie: porównaj zbieżność metod dla punktu startowego $0.5$ ===== ===== | $g(x) = 1 - x^3$ | $g(x) = \sqrt[3]{1 - x}$ | $g(x) = \frac{1+2x^3}{1+3x^2}$ | | {{ zajecia:mn1_2021_2:fixed_point_ex1.png?350 | }} | {{ zajecia:mn1_2021_2:fixed_point_ex2.png?350 | }} | {{ zajecia:mn1_2021_2:fixed_point_ex3.png?350 | }} | Zbieżność gdy $|g'(x)| < 1$ w przedziale izolacji ===== Zadanie 5 ===== Treść zadania znajduje się w Moodle pod adresem [[https://moodle.umk.pl/WFAIIS/mod/assign/view.php?id=4617|Zadanie 5]] ===== Dodatkowe ćwiczenia ===== **Ćw. 1** Napisz program wyznaczający wartość $\sqrt[N]{a}$ dla $a>0$ korzystając z metody Newtona (stycznych) oraz z metody iteracji prostych. Zadanie sprowadza się do znalezienia pierwiastków równania $f(x) = x^N - a$. **Ćw. 2** Napisz program wyznaczający za pomocą metody Newtona oraz metody iteracji prostych pierwiastki równania $$x^{2}-4 x \sin x+(2 \sin x)^{2}=0$$