Niech:
\(\displaystyle{ f(x) = \frac{1}{1+x^{2}} - \frac{1}{2}}\)
\(\displaystyle{ x^{*} = 1}\)
1) Czy metoda Newtona będzie lokalnie zbieżna kwadratowo do \(\displaystyle{ x^{*}}\)?
2) Wykaż, że jeśli \(\displaystyle{ x_{0} = 2}\), to iteracja postaci \(\displaystyle{ x_{n+1} = x_{n} + 2f(x_{n})}\) jest kwadratowo zbieżna do \(\displaystyle{ x^{*}}\)
1)
Czy tutaj wystarczy pokazanie, że \(\displaystyle{ f(x^{*}) = 0}\) oraz \(\displaystyle{ f'(x^{*}) \neq 0}\)? Czy to tylko da nam zbieżność liniową i musimy jeszcze pokazać, że istnieje takie \(\displaystyle{ C > 0}\), że
\(\displaystyle{ |x_{n+1} - x^{*}| \le C \cdot |x_{n} - x^{*}|^{2}}\)
2)
\(\displaystyle{ |x_{n+1} - x^{*}| = |x_{n} + \frac{2}{1+x^{2}} - 2| = | \frac{x_{n}(x_{n} - 1)^{2}}{x_{n}^{2} + 1} | \le |x_{n}(x_{n} - 1)^{2}| \le |x_{n}| \cdot |x_{n}-1|^{2}}\)
Teraz wypadałoby znaleźć stałą \(\displaystyle{ C > 0}\), że \(\displaystyle{ |x_{x}| \le C}\). Co mogę podstawić pod C?
Wykaż zbieżność kwadratową
-
janusz47
- Użytkownik
- Posty: 7917
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1671 razy
Wykaż zbieżność kwadratową
Mamy wykazać nierówność:
\(\displaystyle{ \parallel x_{k+1} - 1\parallel \leq C \parallel x_{k} - 1\parallel ^2 , \ \ \forall_{k\in \mathbb{N}}}\)
Lemat o lokalnym szacowaniu funkcji i pochodnej
Istnieje dostatecznie małe \(\displaystyle{ \delta >0}\), że dla każdego \(\displaystyle{ x^{*}\in \mathcal{K}(x^{*}, \delta)}\) zachodzi:
1. \(\displaystyle{ \parallel f^{'}(x) \parallel \leq 2\parallel f^{'}(x^{*}) \parallel,}\)
2. \(\displaystyle{ \parallel f^{'}(x)^{-1} \parallel \leq 2\parallel f^{'}(x^{*})^{-1} \parallel,}\)
3. \(\displaystyle{ \frac{1}{2\parallel f^{'}(x^{*})\parallel}\parallel x - x^{*}\parallel \leq \parallel f(x) \parallel \leq 2\parallel f'(x^{*}) \parallel \cdot \parallel x - x^{*}\parallel.}\)
Na wstępie wybierzmy \(\displaystyle{ \delta>0}\), tak że dla \(\displaystyle{ x\in \mathcal{K}(1, \delta)}\) zachodzi lemat o oszacowaniu pochodnej.
Oznaczmy \(\displaystyle{ e_{k} = x_{k} -1}\)
Ze wzoru Newtona:
\(\displaystyle{ e_{k+1} = e_{k} - f^{'}(x_{k})^{-1}\cdot f(x_{k})}\)
\(\displaystyle{ e_{k+1} = e_{k} - \frac{(1+x^2)^2}{2x}\cdot \left( \frac{1}{1+x^2} -\frac{1}{2}\right) = e_{k} - \frac{2(1+x^2)-(1+x^2)^2}{4x}=\\ =e_{k}-\frac{2 + 2x^2-1 -2x^2 -x^4}{4x}= e_{k} - \frac{1- x^4}{4x}}\)
Na mocy założeń i lematu o wartości średniej
\(\displaystyle{ f(x_{k+1}) = f(x_{k}) - f(1) = \int_{0}^{1}f'(1 + t(x_{k} -1)dt = \int_{0}^{1}f'(1 + te_{k})e_{k} dt.}\)
Zatem
\(\displaystyle{ e_{k+1} = e_{k} - f^{'}(x_{k})^{-1}\int_{0}^{1}f'(1+ te_{k})e_{k}dt = f^{'}(x_{k})^{-1}\int_{0}^{1}(f^{'}(x_{k}) - f^{'}(1+ te_{k})e_{k}dt}\)
Korzystając z lipschitzowskości i jeszcze raz z lematu o oszacowaniu pochodnej:
\(\displaystyle{ \parallel e_{k+1} \parallel \leq \parallel f^{'}(x_{k})^{-1}\parallel \int_{0}^{1}\parallel f'(x_{k})- f^{'}(1 +te_{k})\parallel \parallel e_{k}\parallel dt \leq 2 \parallel f^{'}(1)^{-1}\parallel \\ \parallel e_{k}\parallel^2 \int_{0}^{1}(1 -t)dt = C \parallel e_{k}\parallel^2}\)
Stąd możemy obliczyć wartość stałej \(\displaystyle{ C}\)
\(\displaystyle{ f^{'}(1)^{-1}= \frac{(1+1)^2}{2\cdot 1}= \frac{4}{2}= 2.}\)
\(\displaystyle{ \parallel f^{'}(1)^{-1}\parallel = 2.}\)
\(\displaystyle{ \int_{0}^{1}(1-t)dt = \left[t - \frac{1}{2}t^2\right]_{0}^{1}= 1 - \frac{1}{2}\cdot 1^2 = 1-\frac{1}{2} = \frac{1}{2}.}\)
\(\displaystyle{ \parallel e_{k+1} \parallel \leq 2\cdot 2 \cdot \frac{1}{2} \cdot \parallel e_{k}\parallel^2}\)
\(\displaystyle{ \parallel e_{k+1} \parallel \leq 2 \cdot \parallel e_{k}\parallel^2}\)
Jeżeli \(\displaystyle{ 2\delta < 1,}\) czyli \(\displaystyle{ \delta < \frac{1}{2}}\) to
\(\displaystyle{ \parallel e_{k+1} \parallel \leq 2 \cdot \parallel e_{k}\parallel^2 = 2\parallel e_{k}\parallel \cdot \parallel e_{k} \parallel \leq 2 \delta \parallel e_{k}\parallel.}\)
\(\displaystyle{ \parallel x_{k+1} - 1\parallel \leq C \parallel x_{k} - 1\parallel ^2 , \ \ \forall_{k\in \mathbb{N}}}\)
Lemat o lokalnym szacowaniu funkcji i pochodnej
Istnieje dostatecznie małe \(\displaystyle{ \delta >0}\), że dla każdego \(\displaystyle{ x^{*}\in \mathcal{K}(x^{*}, \delta)}\) zachodzi:
1. \(\displaystyle{ \parallel f^{'}(x) \parallel \leq 2\parallel f^{'}(x^{*}) \parallel,}\)
2. \(\displaystyle{ \parallel f^{'}(x)^{-1} \parallel \leq 2\parallel f^{'}(x^{*})^{-1} \parallel,}\)
3. \(\displaystyle{ \frac{1}{2\parallel f^{'}(x^{*})\parallel}\parallel x - x^{*}\parallel \leq \parallel f(x) \parallel \leq 2\parallel f'(x^{*}) \parallel \cdot \parallel x - x^{*}\parallel.}\)
Na wstępie wybierzmy \(\displaystyle{ \delta>0}\), tak że dla \(\displaystyle{ x\in \mathcal{K}(1, \delta)}\) zachodzi lemat o oszacowaniu pochodnej.
Oznaczmy \(\displaystyle{ e_{k} = x_{k} -1}\)
Ze wzoru Newtona:
\(\displaystyle{ e_{k+1} = e_{k} - f^{'}(x_{k})^{-1}\cdot f(x_{k})}\)
\(\displaystyle{ e_{k+1} = e_{k} - \frac{(1+x^2)^2}{2x}\cdot \left( \frac{1}{1+x^2} -\frac{1}{2}\right) = e_{k} - \frac{2(1+x^2)-(1+x^2)^2}{4x}=\\ =e_{k}-\frac{2 + 2x^2-1 -2x^2 -x^4}{4x}= e_{k} - \frac{1- x^4}{4x}}\)
Na mocy założeń i lematu o wartości średniej
\(\displaystyle{ f(x_{k+1}) = f(x_{k}) - f(1) = \int_{0}^{1}f'(1 + t(x_{k} -1)dt = \int_{0}^{1}f'(1 + te_{k})e_{k} dt.}\)
Zatem
\(\displaystyle{ e_{k+1} = e_{k} - f^{'}(x_{k})^{-1}\int_{0}^{1}f'(1+ te_{k})e_{k}dt = f^{'}(x_{k})^{-1}\int_{0}^{1}(f^{'}(x_{k}) - f^{'}(1+ te_{k})e_{k}dt}\)
Korzystając z lipschitzowskości i jeszcze raz z lematu o oszacowaniu pochodnej:
\(\displaystyle{ \parallel e_{k+1} \parallel \leq \parallel f^{'}(x_{k})^{-1}\parallel \int_{0}^{1}\parallel f'(x_{k})- f^{'}(1 +te_{k})\parallel \parallel e_{k}\parallel dt \leq 2 \parallel f^{'}(1)^{-1}\parallel \\ \parallel e_{k}\parallel^2 \int_{0}^{1}(1 -t)dt = C \parallel e_{k}\parallel^2}\)
Stąd możemy obliczyć wartość stałej \(\displaystyle{ C}\)
\(\displaystyle{ f^{'}(1)^{-1}= \frac{(1+1)^2}{2\cdot 1}= \frac{4}{2}= 2.}\)
\(\displaystyle{ \parallel f^{'}(1)^{-1}\parallel = 2.}\)
\(\displaystyle{ \int_{0}^{1}(1-t)dt = \left[t - \frac{1}{2}t^2\right]_{0}^{1}= 1 - \frac{1}{2}\cdot 1^2 = 1-\frac{1}{2} = \frac{1}{2}.}\)
\(\displaystyle{ \parallel e_{k+1} \parallel \leq 2\cdot 2 \cdot \frac{1}{2} \cdot \parallel e_{k}\parallel^2}\)
\(\displaystyle{ \parallel e_{k+1} \parallel \leq 2 \cdot \parallel e_{k}\parallel^2}\)
Jeżeli \(\displaystyle{ 2\delta < 1,}\) czyli \(\displaystyle{ \delta < \frac{1}{2}}\) to
\(\displaystyle{ \parallel e_{k+1} \parallel \leq 2 \cdot \parallel e_{k}\parallel^2 = 2\parallel e_{k}\parallel \cdot \parallel e_{k} \parallel \leq 2 \delta \parallel e_{k}\parallel.}\)
-
cis123
- Użytkownik
- Posty: 177
- Rejestracja: 27 paź 2015, o 17:31
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 16 razy
Re: Wykaż zbieżność kwadratową
Te całki mnie trochę przerażają. Czy jeśli w 1) doprowadziłem do czegoś takiego:
\(\displaystyle{ |x_{n} - 1|^{2} \cdot \left| \frac{x_{n}^{2} + 2x_{n} - 1}{4x_{n}} \right|}\)
to mogę jakoś oszacować z góry \(\displaystyle{ \left| \frac{x_{n}^{2} + 2x_{n} - 1}{4x_{n}} \right|}\)?
Miałem wyznaczyć lokalną zbieżność, więc mogę po prostu wziąć sobie jakieś otoczenie \(\displaystyle{ (1- \alpha , 1+ \alpha )}\) i powiedzieć, że da się to oszacować przez pewną stałą?
Czy mógłbyś mi powiedzieć jeszcze jak zrobić 2)?
\(\displaystyle{ |x_{n} - 1|^{2} \cdot \left| \frac{x_{n}^{2} + 2x_{n} - 1}{4x_{n}} \right|}\)
to mogę jakoś oszacować z góry \(\displaystyle{ \left| \frac{x_{n}^{2} + 2x_{n} - 1}{4x_{n}} \right|}\)?
Miałem wyznaczyć lokalną zbieżność, więc mogę po prostu wziąć sobie jakieś otoczenie \(\displaystyle{ (1- \alpha , 1+ \alpha )}\) i powiedzieć, że da się to oszacować przez pewną stałą?
Czy mógłbyś mi powiedzieć jeszcze jak zrobić 2)?
Ostatnio zmieniony 19 lut 2019, o 22:21 przez cis123, łącznie zmieniany 1 raz.