znajdowanie punktu stałego metodą iteracji prostej

Przybliżanie, metoda najmniejszych kwadratów, wielomiany interpolacyjne i inne.
aneta909811
Użytkownik
Użytkownik
Posty: 260
Rejestracja: 1 lut 2015, o 19:20
Płeć: Kobieta
Lokalizacja: Poznań
Podziękował: 68 razy

znajdowanie punktu stałego metodą iteracji prostej

Post autor: aneta909811 »

Wykaż, że funkcja
\(\displaystyle{ ϕ(x)= \frac{1}{x+2}+ \frac{1}{2} x + 100π }\)
ma w przedziale \(\displaystyle{ [0, 2104]}\) dokładnie jeden punkt stały i że można ten punkt znaleźć za pomocą metody iteracji prostej. Jaki jest wykładnik zbieżności tej metody?
aneta909811
Użytkownik
Użytkownik
Posty: 260
Rejestracja: 1 lut 2015, o 19:20
Płeć: Kobieta
Lokalizacja: Poznań
Podziękował: 68 razy

Re: znajdowanie punktu stałego metodą iteracji prostej

Post autor: aneta909811 »

Czy mógłby ktoś pomóc?
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: znajdowanie punktu stałego metodą iteracji prostej

Post autor: janusz47 »

Skorzystamy z twierdzenia (*)

Niech funkcja \(\displaystyle{ \phi(x) }\) będzie określona i różniczkowalna w przedziale domkniętym \(\displaystyle{ \langle a, b \rangle }\) i jej wartości należą do tego przedziału (\(\displaystyle{ \phi(x) \in \langle a, b \rangle) }\).

Wtedy, kiedy istnieje ułamek właściwy \(\displaystyle{ q }\) taki, że

\(\displaystyle{ |\phi^{'}(x)| \leq q < 1 }\) dla \(\displaystyle{ a < x < b }\), to proces iteracyjny:

\(\displaystyle{ x_{0},}\)
\(\displaystyle{ x_{1} = \phi(x_{0}), }\)
\(\displaystyle{ x_{2} = \phi(x_{1}), }\)
...................
\(\displaystyle{ x_{n} = \phi(x_{n-1}),}\)
..................
jest zbieżny (istnieje punkt stały) niezależnie do wyboru punktu początkowego \(\displaystyle{ x_{0}\in < a, b > }\)

wartość \(\displaystyle{ \xi = \lim_{n\to \infty} x_{n} }\) jest jedynym pierwiastkiem równania \(\displaystyle{ x = \phi(x) }\)

Zgodnie z twierdzeniem możemy napisać

\(\displaystyle{ |\phi^{'}(x)| = \left |-\frac{1}{(x+2)^2} + \frac{1}{2} \right |\leq \frac{1}{2} = q < 1 }\) dla \(\displaystyle{ x \in [ 0, 2004]. }\)

Wykazaliśmy, że istnieje dokładnie jeden punkt stały należący do przedziału \(\displaystyle{ [0, 2004 ] }\)

Wykonajmy kilkanaście kroków procesu iteracyjnego:

\(\displaystyle{ x_{0} = \phi(0) = \frac{1}{0+2} +0,5\cdot 0 + 100\cdot \pi \approx 314,7 }\)

\(\displaystyle{ x_{1}= \phi(314,7) = \frac{1}{314,7 +2} + 0,5\cdot 314,7 + 100\pi \approx 471,5 }\)

\(\displaystyle{ x_{2} = \phi(471,5) = \frac{1}{471,5 +2} + 0,5\cdot 471,5 +100\pi \approx 549,9 }\)

\(\displaystyle{ x_{3} = \phi(549,9) = \frac{1}{549,9+2} + 0,5\cdot 549,9 + 100\pi \approx 589,1 }\)

\(\displaystyle{ x_{4} = \phi(589,1) = \frac{1}{589,1+2}+ 0,5\cdot 589,1 +100\pi \approx 608, 7 }\)

\(\displaystyle{ x_{5} = \phi(608,7) = \frac{1}{608,7+2} + 0,5\cdot 608,7 +100\pi \approx 618,5 }\)

\(\displaystyle{ x_{6} = \phi(618,5) = \frac{1}{618,5+2} + 0,5\cdot 618,5 +100\pi \approx 623, 4 }\)

\(\displaystyle{ x_{7} = \phi(623,4) = \frac{1}{623,4+2} + 0,5\cdot 623,4 +100\pi \approx 625,9 }\)

\(\displaystyle{ x_{8} = \phi(625,9) = \frac{1}{625,9+2} + 0,5\cdot 625,9 +100\pi \approx 627,1 }\)

\(\displaystyle{ x_{9} = \phi(627,1) = \frac{1}{627,1+2} + 0,5\cdot 627,1 +100\pi \approx 627, 7 }\)

\(\displaystyle{ x_{10}=\phi(627,7) = \frac{1}{627,7+2} + 0,5\cdot 627,7 +100\pi \approx 628,0}\)

\(\displaystyle{ x_{11}=\phi(628,0) = \frac{1}{628,0+2} + 0,5\cdot 628,0 +100\pi \approx 628,1}\)

\(\displaystyle{ x_{12}=\phi(628,1) = \frac{1}{628,1+2} + 0,5\cdot 628,1 +100\pi \approx 628,2}\)

\(\displaystyle{ x_{13}=\phi(628,2) = \frac{1}{628,2+2} + 0,5\cdot 628,2 +100\pi \approx 628,3}\)

\(\displaystyle{ x_{14}=\phi(628,3) = \frac{1}{628,3+2} + 0,5\cdot 628,3 +100\pi \approx 628,3}\)

Znaleźliśmy punkt stały funkcji \(\displaystyle{ \phi(x), \ \ \xi = 628,3\in [0, 2004] }\)

Proces iteracyjny należy kontynuować tak długo dopóki

\(\displaystyle{ |x_{n} - x_{n-1}| < \frac{1 - q}{q} \cdot \varepsilon }\)

gdzie \(\displaystyle{ \varepsilon }\) kresem górnym błędu bezwzględnego poszukiwanego punktu stałego (przyjętą dokładnością).

W tym przypadku

\(\displaystyle{ |x_{n} - x_{n-1}| < \frac{1 - \frac{1}{2}}{\frac{1}{2}} \cdot \varepsilon = \varepsilon. }\)


Informacją o szybkości zbieżności metody jest tzw. wykładnik zbieżności \(\displaystyle{ p.}\)

Mówi się, że metoda jest rzędu \(\displaystyle{ p\in \NN ,}\) jeśli

\(\displaystyle{ |x_{i+1}- \xi| \leq K\cdot |x_{i} -\xi|^{p} }\)

W naszym przypadku istnieje taka stała \(\displaystyle{ K > 0, }\) że zachodzi nierówność

\(\displaystyle{ |x_{i+1}- 628,3| \leq K\cdot |x_{i} -628,3|.}\)

Wykładnik potęgi \(\displaystyle{ p = 1. }\)

Jest to metoda liniowa.

(*) Demidowicz B. P., Maron I. A., Szuwałowa E. Z. Metody numeryczne, cz. I, II. Warszawa PWN 1965.

Dodano po 40 minutach 8 sekundach:
Stosunkowo prosto można zaimplementować metodę iteracji prostej na przykład w programach Matlab-Octave.

Wówczas dla przyjętej dokładności \(\displaystyle{ \varepsilon }\) na przykład \(\displaystyle{ \varepsilon = 0,01 }\) i punktu początkowego \(\displaystyle{ x_{0}\in \langle a, b \rangle }\) otrzymamy ilość potrzebnych iteracji \(\displaystyle{ n }\) do obliczenia wartości punktu stałego danej funkcji \(\displaystyle{ \phi.}\)

Dodano po 34 minutach 19 sekundach:
Trochę historii.

Metoda numeryczna iteracji prostej bazuje na twierdzeniu sformułowanym przez Stefana Banacha.

Punkt \(\displaystyle{ x \in X }\) nazywa się punktem stałym odwzorowania \(\displaystyle{ T\colon X\to X }\) wtedy i tylko wtedy, gdy \(\displaystyle{ T(\vec{x})=\vec{x}. }\)
.
Twierdzenie [Banacha o punkcie stałym (o kontrakcji)]

Jeśli \(\displaystyle{ (X,\varrho) }\) jest przestrzenią metryczną zupełną, zaś \(\displaystyle{ T\colon X\to X }\) jest kontrakcją, to \(\displaystyle{ T }\) ma dokładnie jeden punkt stały \(\displaystyle{ \vec{x} \in X }\).

Dowód tego twierdzenia, nazywanego także zasadą odwzorowań zwężających, jest krótki i nietrudny, a samo twierdzenie - opublikowane w wersji abstrakcyjnej w roku \(\displaystyle{ 1922}\), w pracy doktorskiej Banacha (Fundamenta Math., tom 3, rok 1922, str. 133-181.) - ma mimo swojej prostoty wiele zastosowań, w których \(\displaystyle{ X }\) bywa zwykle jakąś przestrzenią funkcyjną, a równanie \(\displaystyle{ T(\vec{x})=\vec{x} }\) równaniem różniczkowym.
aneta909811
Użytkownik
Użytkownik
Posty: 260
Rejestracja: 1 lut 2015, o 19:20
Płeć: Kobieta
Lokalizacja: Poznań
Podziękował: 68 razy

Re: znajdowanie punktu stałego metodą iteracji prostej

Post autor: aneta909811 »

janusz47 Niezmiernie dziękuję!
ODPOWIEDZ