Metoda Punktu Stałego jest jedną z metod iteracyjnych rozwiązywania równań postaci:
\(\displaystyle{ g(x) = x. }\)
Rozwiązanie tego równania \(\displaystyle{ \alpha }\) nazywamy punktem stałym funkcji \(\displaystyle{ g. }\)
Startujemy od punktu początkowego \(\displaystyle{ p_{0}. }\)
Generujemy ciąg punktów \(\displaystyle{ (x_{n}) }\) takich, że
\(\displaystyle{ p_{n+1} = g(p_{n}), \ \ n=0, 1, 2,... }\)
Jeśli proces iteracyjny jest zbieżny do pierwiastka \(\displaystyle{ \alpha }\) i funkcja \(\displaystyle{ g
}\) jest ciągła, to
\(\displaystyle{ \lim_{n\to \infty} p_{n} = \alpha. }\)
Następujące twierdzenie podaje warunki konieczne i wystarczające istnienia punktu stałego i zbieżności metody:
Twierdzenie
Jeśli funkcja jest funkcją ciągłą w przedziale \(\displaystyle{ [a, b] }\) i \(\displaystyle{ a\leq g(x) \leq b
}\) dla w każdego \(\displaystyle{ x \in [a, b]. }\)
Ponadto zakładamy, że jeśli \(\displaystyle{ g'(x) }\) jest funkcją ciagłą na \(\displaystyle{ (a, b) }\) i istnieje taka dodatnia
stała \(\displaystyle{ c }\) , że \(\displaystyle{ |g'(x)|\leq c < 1 }\) dla wszystkich \(\displaystyle{ x\in (a, b),}\)
to wtedy istnieje dokładnie jeden punkt stały \(\displaystyle{ \alpha }\) funkcji \(\displaystyle{ g }\)
i proces iteracyjny \(\displaystyle{ x_{n+1} = g(x_{n}), \ \ n\geq 0 }\) jest zbieżny do \(\displaystyle{ \alpha }\) dla punktu początkowego \(\displaystyle{ x_{0} \in [a, b]. }\)
Dowód
Definiujemy fnkcję \(\displaystyle{ f(x) = x - g(x).}\) Stąd funkcja \(\displaystyle{ f }\) jest ciągła na \(\displaystyle{ [a,b] }\) i \(\displaystyle{ f(a)\leq 0, \ \ f(b)\geq 0.
}\)
Z twierdzenia o istnieniu punktu pośredniego, istnieje \(\displaystyle{ \alpha \in [a,b] }\) dla którego \(\displaystyle{ f(x) =0.}\)
Punkt \(\displaystyle{ \alpha }\) jest punktem stałym funkcji \(\displaystyle{ g.}\)
Z twierdzenia o wartości średniej (Lagrange'a) wynika, że istnieją dwa punkty \(\displaystyle{ r, s \in [a,b] }\) i istnieje takie \(\displaystyle{ \xi }\), że
\(\displaystyle{ |r - s| = |g(r) - g(s)|= |g'(\xi)|\cdot |r-s| \leq c\cdot |r-s| }\)
Stąd
\(\displaystyle{ |r-s|\leq c\cdot |r-s| }\) lub \(\displaystyle{ (1-c)\cdot |r-s| \leq 0 }\)
Z założenia \(\displaystyle{ c <1 }\) więc musi zachodzić równość \(\displaystyle{ r = s, }\) i funkcja \(\displaystyle{ g }\) ma dokładnie jeden punkt stały.
Dla wykazania zbieżności metody korzystamy ponownie z twierdzenia Lagrange'a:
\(\displaystyle{ |\alpha -x_{n+1}|=|g(\alpha) - g(x_{n})|=|g'(\xi_{n})|\cdot |\alpha -x_{n}|\leq c|\alpha -x_{n}|, }\)
gdzie: \(\displaystyle{ \xi_{n} \in (\alpha, x_{n}). }\)
Stosując indukcję względem \(\displaystyle{ n, }\) otrzymujemy równanie:
\(\displaystyle{ |\alpha -x_{n}| \leq c^{n}\cdot |\alpha -x{0}| , \ \ n\geq 0.}\)
Jeśli \(\displaystyle{ n \rightarrow \infty, \ \ c^{n}\rightarrow 0, }\)
stąd
\(\displaystyle{ x_{n} \rightarrow \alpha. }\)
Program w OCTAVE
Kod: Zaznacz cały
function fixed(g,x0,tol,n)
iter =0;
u=feval(g,x0);
err=abs(u-x0);
disp('___________________________________________')
disp(' iter xn g(xn) |xn+1-xn| ')
disp('___________________________________________')
fprintf('%2.0f %12.6f %12.6f\n',iter,x0,u)
while(err>tol)&(iter<=n)
x1 =u;
err=abs(x1-x0);
x0=x1;
u=feval(g,x0);
iter=iter+1;
fprintf('%2.0f %12.6f %12.6f %12.8f\n',iter,x0,u,err)
end
if(iter>m)
disp('Metoda nie jest zbieżna')
end
Kod: Zaznacz cały
function f=g1(x);
f=5/x.^2+2;
Kod: Zaznacz cały
>> fixed('g1',2.5,10^(-4),100)
___________________________________________
iter xn g(xn) |xn+1-xn|
___________________________________________
0 2.500000 2.800000
1 2.800000 2.637755 0.30000000
2 2.637755 2.718623 0.16224490
3 2.718623 2.676507 0.08086781
4 2.676507 2.697965 0.04211628
5 2.697965 2.686906 0.02145790
6 2.686906 2.692572 0.01105819
7 2.692572 2.689660 0.00566568
8 2.689660 2.691154 0.00291154
9 2.691154 2.690387 0.00149391
10 2.690387 2.690781 0.00076713
11 2.690781 2.690579 0.00039377
12 2.690579 2.690683 0.00020216
13 2.690683 2.690629 0.00010378
14 2.690629 2.690657 0.00005328