Lista 4 - HackMD

###### tags: `Analiza Numeryczna (L)` # Lista 4 ## 1 :::info Niech $[a_0, b_0]$, $[a_1, b_1]$, . . będzie ciągiem przedziałów zbudowanym za pomocą metody bisekcji zastosowanej do lokalizacji zer funkcji $f$ ciągłej w przedziale $[a_0, b_0]$, niech ponadto $m_{n+1} := \frac12(a_n + b_n)$, $α = \lim_{n→∞} m_n$ oraz $e_n := α − m_{n+1}$. ::: ### a) $[a_{n+1},b_{n+1}] = \begin{cases} [\frac{a_n}{2},b_n] & \quad \text{dla } \alpha\in [\frac{a_n}{2},b_n] \\ [a_n,\frac{b_n}{2}] & \quad \text{w p.p. } \end{cases}$ A wiemy, że $[a_n,b_n]\supset [\frac{a_n}{2},b_n]$ oraz $[a_n,b_n]\supset [a_n,\frac{b_n}{2}]$ więc z tego wynika, że $[a_n,b_n]\supset[a_{n+1},b_{n+1}]$ co należało udowodnić. ### b) Teza: Długość przedziału wynosi $\frac{b_0 - a_0}{2^n}$ Dowód przeprowadzę przez indukcję. $1^\circ$ dla n=0 $\frac{b_0 - a_0}{2^0} = b_0-a_0$ $1^\circ$ Załóżmy, że długość przedziału $[a_n,b_n]$ wyraża się wzorem $n=\frac{b_0 - a_0}{2^n}$ Wtedy dla n+1 $długość[a_{n+1},b_{n+1}] = \frac{1}{2}\times długość[a_n,b_n] = \frac{1}{2}\times \frac{b_0 - a_0}{2^n} = \frac{b_0-a_0}{2^{n+1}}$ Na podstawie indukcji pokazałem, że długość przedziału $[a_n,b_n]$ Wyraża się wzorem $\frac{b_0 - a_0}{2^n}$. ### c) $|e_n| = |\alpha - m_{n+1}| = |\alpha - \frac{1}{2}(a_n+b_n)|$ Możemy zauważyć, że $\alpha\in[a_n,b_n]$ więc podana rożnica będzie największa dla $\alpha = a_n$ lub $\alpha = b_n$ w obu przypadkach po podstawieniu za $\alpha$ otrzymamy $|e_n| = |\frac{b_n-a_n}{2}| = |\frac{b_n}{2} - \frac{a_n}{2}|$ Zauważmy, że jest to długość odcinka, która wynosi (z podpunktu b) $|\frac{b_0-a_0}{2^{n+1}}|$, a $|\frac{b_0-a_0}{2^{n+1}}| = P$ Czyli w przypadku największego $|e_n|$ zachodzi równość, z czego wynika, że dla każdego n zachodzi $|e_n|\leq|\frac{b_0-a_0}{2^{n+1}}|$ Co należało udowodnić. ### d) Wiemy, że miejsce zerowe funkcji $f\in[a_0,b_0]$. Załóżmy, że miesjce zerowe $\alpha = b_0$. Wtedy przy kolejnych podziałach odcinka będziemy brać zawsze "drugą" połowę i nie będziemy zmieniać $b_0$, co za tym idzie będziemy zawsze zwiększać $a$ więc zachodzi nierówność $a_0<a_1<a_2<...$ ## 2 Korzystając z poprzedniego zadania $\epsilon_n < \epsilon$ $\epsilon_n = |\alpha - m_{m+1}| \leq 2^{-n-1}(b_0-a_0)$ $\frac{b_0-a_0}{2^{n+1}} < \epsilon$ $\frac{b_0-a_0}{\epsilon} < 2^{n+1}$ Obie strony są dodatnie, więc mogę nałożyć $log_2$ $log_2(\frac{b_0-a_0}{\epsilon}) < n+1$ $log_2(\frac{b_0-a_0}{\epsilon}) - 1 < n$ $log_2(\frac{b_0-a_0}{\epsilon}) - log_22 < n$ $log_2(\frac{b_0-a_0}{2\epsilon}) < n$ Aby ta nierówność była prawdziwa trzeba wykonać conajmniej $log_2(\frac{b_0-a_0}{2\epsilon})$ kroków, czyli co najmniej $\lfloor log_2(\frac{b_0-a_0}{2\epsilon})\rfloor + 1$ ## 3 ```java= import static java.lang.Math.pow; public class Main { public static double L41function(double x){ return x - 0.49d; } public static void L41(){ double start = 0d; double end = 1d; double mid, result, fault; for (int i=0; i<=5; i++){ mid = (start + end)/2d; result = L41function(mid); fault = pow(2,-i-1); if (i>0) System.out.println("Dla n=" + i + " przybliżona wartość miejsca zerowego:" + mid + ". Błąd: |e_n| <= " + fault); if (result == 0) System.out.println("Miejsce zerowe a = " + result); if (result < 0) start = mid; else end = mid; } } public static void main(String args[]){ L41(); } } ``` ![](https://i.imgur.com/7C4oGpj.png) Dla każdego kolejnego n funkcja wyznacza coraz to lepsze przybliżenie miejsca zerowego. Szacowany błąd z każdym nowym przybliżeniem maleje dwukrotnie, co daje nam coraz to lepszy wynik. ## 4 ![](https://i.imgur.com/YjfBRbq.png) Po naszkicowaniu wykresów ze wskazówki możemy zauważyć, że funkcja $f(x) =x^22−2cos(3x+ 1)$ ma 2 miejsca zerowe oraz, że znajdują się one kolejno w przedziale $x_1\in[-1,0]$, $x_2\in[0,1]$ Sprawdzamy znaki wartości w tych punktach: $f(-1) =$ dodatnia wartość $f(0) =$ ujemna wartość $f(1) =$ dodatnia wartość Po podstawieniu do wzoru z zadania 2, musimy wykonać w obu przypadkach obliczenia do n = 16. ## 5 ### a) $\frac{1}{R} = x$ $\frac{1}{x} = R$ $\frac{1}{x}- R = 0$ Dla $f(x) = \frac{1}{x} - R$ Chcemy znaleźć miejsce zerowe tej funkcji (Jest to $\frac{1}{R}$) $f'(x) = -\frac{1}{x^2}$ Więc z metody Newtona $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{\frac{1}{x_n} - R}{\frac{-1}{x_n^2}} = x_n - \frac{\frac{1}{x_n} - R}{\frac{-1}{x_n^2}} = x_n + \frac{\frac{1}{x_n} - R}{\frac{1}{x_n^2}} = x_n + (\frac{1}{x_n} - R)\times x_n^2 =$ $=x_n + x_n - Rx_n^2 = 2x_n - Rx_n^2 = x_n(2-Rx_n)$ ### b) ![](https://i.imgur.com/QXZ91kC.png) ### c) $x_{n+1} < 0 \iff x_n > 0$ oraz $2 - x_nR < 0$ LUB $x_n < 0$ oraz $2 - x_nR > 0$ $1^\circ$ $x_n > 0$ oraz $2 - x_nR < 0$ $x_nR > 2$ **$x_n > \frac{2}{R}$** $2^\circ$ $x_n < 0$ oraz $2 - x_nR > 0$ $x_nR < 2$ $x_n < \frac{2}{R}$ Czyli $x_n <0$ **Odp $x_n < 0$ lub $x_n > \frac{2}{R}$** ### d) Załóżmy, że $x_n < 0$ Wtedy $x_{n+1} =x_n(2-x_nR)$ (x_n < 0, R > 0) $x_n(2-x_nR) < x_n(2) = 2\times x_n$ $x_{n+1} < 2\times x_n < x_n$ Czyli $x_{n+1} < x_n$ Co nalezało udowodnić. ### e) $x_{n+1} > 0$ oraz $x_n < \frac{1}{R}$ **1$^\circ$ $x_{n+1} > 0$** $x_{n+1} = x_n(2-x_nR) > 0$ Rozwiążmy równanie $x_n(2-x_nR) = 0$ Wtedy $x_n = 0$ LUB $2-x_nR = 0$ Czyli $x_n=0$ LUB $x_n = \frac{2}{R}$ Wracając do nierównośći, $x_n(2-x_nR) > 0 \iff x_n\in(0,\frac{2}{R})$ **2$^\circ$ $x_{n+1} < \frac{1}{R}$** $x_{n+1} = x_n(2-x_nR)$ $x_n(2-x_nR)< \frac{1}{R}$ / $\times R$ (R dodatnie) $x_nR(2-x_nR)< 1$ / $-1$ $x_nR(2-x_nR) - 1 < 0$ $x_nR(2-x_nR - \frac{1}{x_nR}) < 0$ / $\times x_n$ ($x_n$ dodatnie) $x_nR(2x_n-x_n^2R - \frac{1}{R}) < 0$ $\times \frac{-1}{R^2}$ $x_n(x_n^2 - \frac{2x_n}{R} + \frac{1}{R^2}) > 0$ $x_n(x_n - \frac{1}{R})^2 > 0$ Czyli $x_n\in (0,+\infty)$ \ {$\frac{1}{R}$} Czyli, aby $x_{n+1}\in(0,\frac{1}{R})$ to $x_n\in(0,\frac{2}{R})$ \ {$\frac{1}{R}$} ### f) Załóżmy, że $x_n\in(0,R^{-1})$ Pokażę, że $x_{n+1} > x_n$ oraz $x_{n+1} < R^{-1}$ **1$^\circ$ $x_{n+1} > x_n$** $x_{n+1} = x_n(2-x_nR)$ $x_n < \frac{1}{R}$ (Z założenia prawdziwe, rozpatrujemy tylko dodatnie $x_n$) $x_nR < 1$ $-x_nR > -1$ $2-x_nR > 1$ \ $\times x_n$ ($x_n dodatnie$) $x_n(2-x_nR) > x_n$ **2$^\circ$ $x_{n+1} < R^{-1}$** $(x_n+\frac{1}{R})^2>0$ (Z założenia prawdziwie) $x_n^2 - 2\frac{x_n}{R} +\frac{1}{R^2} > 0$ $x_n^2 - 2\frac{x_n}{R} +\frac{1}{R^2} > 0$ / $\times R$ (R dodatnie) $x_n^2R - 2x_n +\frac{1}{R} > 0$ / $\times-1$ $2x_n-x_n^2R - \frac{1}{R} < 0$ $x_n(2-x_nR - \frac{1}{x_nR}) < 0$ $x_n(2-x_nR) - \frac{1}{R} < 0$ $x_n(2-x_nR) < \frac{1}{R}$ ### g) Załóżmy nie wprost, że $\lim\limits_{x \to \infty} x_n \neq \frac{1}{R}$ Wtedy rozpatrzmy 2 przypadki. **1$^\circ$ $\lim\limits_{x \to \infty} x_n > \frac{1}{R}$** Sprzeczność, ponieważ maksymalną wartość jaką mogą osiągnąć elementy $x_n$ wynoszą $\frac{1}{R}$ (Z podpunktu f) **2$^\circ$ $\lim\limits_{x \to \infty} x_n < \frac{1}{R}$** Weźmy takie g, że $\lim\limits_{x \to \infty} x_n = g$ oraz z założenia g < $\frac{1}{R}$ Weźmy małe $\epsilon > 0$ takie , że $x_n = |g - \epsilon| = g - \epsilon$ Wtedy $x_{n+1} = x_n(2 - x_n\times R) = x_n \times (2-(g-\epsilon)\times R) = x_n\times(1 + \alpha)$ Gdzie $\alpha >\frac{1}{R} - g$ Możemy zauważyć, że kolejny element będzie zawsze przemnożony przez coś co jest >1, co pokazuje, że po pewnym czasie przekroczymy $g$ i dostaniemy liczbę większą, co pokazuje, że ciąg $x_n$ na pewno nie dąży do g. Co kończy dowód. Zbieżne jest dla liczby $x_0\in(0,\frac{2}{R})$ ### h) KOD ## 6 :::info Stosując metodę Newtona, zaproponuj algorytm numerycznego obliczania $\frac1{\sqrt a}\space (a >0)$ bez wykonywania dzieleń. Opracowaną metodę sprawdź eksperymentalnie, w tym zbadaj m.in. jak warto dobierać $x_0$ oraz ile średnio iteracji wystarczy do osiągnięcia satysfakcjonujących wyników. ::: $\frac{1}{\sqrt{a}} = x$ $\frac{1}{x} = \sqrt{a}$ $\frac{1}{x^2} = a$ $\frac{1}{x^2} - a = 0$ Dla $f(x) = \frac{1}{x^2} - a$ $f'(x) = -\frac{2}{x^3}$ $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{\frac{1}{x_n^2} - a}{-\frac{2}{x_n^3}} = x_n + \frac{x_n - ax_n^3}{2} = \frac{x_n}{2}(3 - ax_n^2)$ $\Phi(x) =\frac{3}{2}x - \frac{ax^3}{2}$ $\Phi'(x) =\frac{3}{2} - \frac{3ax^2}{2}$ Zbieżne, gdy: **$1^\circ$** $\Phi(\alpha) = \alpha$ $\Phi(\frac{1}{\sqrt{a}}) = \frac{3}{2\sqrt{a}} - \frac{a}{a\sqrt{a}} = \frac{3}{2\sqrt{a}} - \frac{1}{\sqrt{a}} = \frac{1}{\sqrt{a}}$ **$2^\circ$** $|\Phi'(x)| < 1$ $|\Phi'(x)| < 1$ $|\frac{3}{2} - \frac{3ax^2}{2}| < 1$ $|1 - ax^2| < \frac{2}{3}$ $|ax^2 - 1| < \frac{2}{3}$ $-\frac{2}{3} < ax^2 - 1 < \frac{2}{3}$ $\frac{1}{3} < ax^2 < \frac{5}{3}$ $\frac{1}{3a} < x^2 < \frac{5}{3a}$ $\frac{1}{\sqrt{3a}} < x < \frac{\sqrt{5}}{\sqrt{3a}}$ Zbieżne dla $x\in (\frac{1}{\sqrt{3a}},\frac{\sqrt{5}}{\sqrt{3a}}$ Im bliżej dobierzemy wartość $\frac{1}{\sqrt{a}}$ tym bliżej będziemy wyniku. ## 7 **Niech będziea=m2c, gdziecjest liczbą całkowitą, am–ułamkiem z przedziału[12,1). Zaproponuj efektywną metodę obliczania√a, otrzymanąprzez zastosowanie metody Newtona do wyznaczania zera pewnej funkcjif.Ustaleksperymentalniedla jakich wartościx0metoda jest zbieżna** $\sqrt{m\times2^{c}} = \begin{cases} \sqrt{m}\times2^{k} & \quad \text{dla } c \text{ parzystego takiego, że c = 2k}\\ \sqrt{2m}\times2^{k} & \quad \text{dla } c \text{ nieparzystego takiego, że c = 2k + 1} \end{cases}$ Wiemy, że $m\in[\frac{1}{2},1)$ Czyli zawężyliśmy problem wyszukiwania pierwiastka do przedziału $[\frac{1}{2},1)$ dla n parzystego oraz do $[\frac{\sqrt{2}}{2},\sqrt{2})$ dla c nieparzystego. Czyli musimy napisać skuteczny algorytm obliczania pierwiastka z liczby, która jest z przedziału $[\frac{1}{2},\sqrt{2})$ **Wzór funkcji** $\sqrt{a} = x$ $a = x^2$ $x^2-a = 0$ $f(x) = x^2-a$ $f'(x) = 2x$ $x_{n+1} = x_n - \frac{x_n^2-a}{2x_n} = x_n - \frac{x_n}{2} + \frac{a}{2x_n} =\frac{x_n}{2} + \frac{a}{2x_n} = \frac{1}{2}(x_n + \frac{a}{x_n})$ $\Phi(x) = \frac{1}{2}(x + \frac{a}{x}) = \frac{x}{2} + \frac{a}{2x}$ $\Phi'(x) = \frac{1}{2} - \frac{a}{2x^2}$ Zbieżność: **$1^\circ$** $\Phi(\alpha) = \alpha$ $\Phi(\sqrt{a}) = \frac{\sqrt{a}}{2} + \frac{a}{2\sqrt{a}} = \frac{\sqrt{a}}{2} + \frac{\sqrt{a}}{2} = \sqrt{a}$ **$2^\circ$** $|\Phi'(x)| < 1$ $|\frac{1}{2} - \frac{a}{2x^2}| < 1$ $|1 - \frac{a}{x^2}| < 2$ $|\frac{a}{x^2} - 1| < 2$ $-2 < \frac{a}{x^2} - 1 < 2$ $-1 < \frac{a}{x^2} < 3$ $\frac{-1}{a} < \frac{1}{x^2} < \frac{3}{a}$ $0 < \frac{1}{x^2} < \frac{3}{a}$ $x^2 > \frac{a}{3}$ $x > \frac{\sqrt{3a}}{3}$ Wiemy, że nasz pierwiastek, którego szukamy jest z przedziału $[\frac{1}{2},\sqrt{2})$