Twierdzenie Banacha o punkcie stałym. Zastosowania.

Przypomnienie.

Liczby naturalne $\mathbb N$ zaczynają się u nas od $1$.

Jeśli $X$ $-$ dowolny zbiór, to nieskończony ciąg $(x_n\in X \colon n \in \mathbb N)$ jego elementów będziemy też oznaczać krótko $(x_n)$.

Niech $(X,d)$ przestrzeń metryczna. Mówimy, że ciąg $(x_n)$ jej elementów jest zbieżny, jeśli istnieje $g\in X$, że $\lim_{n\to \infty} d(x_n,g)=0$. Ciągi zbieżne mają dalekie wyrazy bliskie sobie, to znaczy, jeśli $(x_n)$ jest zbieżny, to
$$ \bigwedge_{\varepsilon>0} \bigvee_{N}\bigwedge_{n\ge m>N} d(x_n,x_m)<\varepsilon $$ Opisana własność ciągów zbieżnych nazywamy własnością Cauchy'ego a ciągi, które ją mają, nazywamy ciągami Cauchy'ego. Ciągi zbieżne są więc ciągami Cauchy'ego.

Przykład 1k.

Nie każdy ciąg Cauchy'ego liczb wymiernych jest zbieżny do liczby wymiernej, ale każdy ciąg Cauchy'ego zbudowany z liczb rzeczywistych jest zbieżny do liczby rzeczywistej.

Mówimy, że przestrzeń $(X,d)$ jest zupełna, jeśli każdy jej ciąg Cauchy'ego jest zbieżny.

W takim razie zbiór liczb wymiernych ze zwykłą odległością nie jest przestrzenią zupełną, a zbiór liczb rzeczywistych jest.

Zasada kontrakcji. (Twierdzenie Banacha o punkcie stałym.)

Niech $(X,d)$ $-$ przestrzeń metryczna. Odwzorowanie $T\colon X\to X$ nazywamy zwężającym ze stałą $0\le L<1$, jeśli dla wszelkich $x, y \in X$ zachodzi nierówność $d(T(x), T(y))\le Ld(x,y)$.

Tw 1k.

Niech $(X,d)$ $-$ przestrzeń metryczna zupełna. Niech $T\colon X\to X$ $-$ odwzorowanie zwężające ze stałą $L$. Wówczas istnieje jedyny punkt $x_0 \in X$, że

$$ T(x_0)=x_0 \tag{1} $$

oraz dla wszelkich $m\in \mathbb N$ i $x\in X$

$$ d(T^m(x), x_0)\le \frac{L^m}{1-L} d(x, T(x)). \tag{2} $$

Komentarz.

Z $(2)$ wynika, że ciąg $(T^n(x))$ jest zbieżny do $x_0$. Wzór ten szacuje także tempo zbieżności.

Dowód. Dowód rozbijemy na proste obserwacje.

Obserwacja a.

Dla każdej liczby naturalnej $m$ i wszelkich $x,y \in X$ $$ d(T^m(x),T^m(y))\le L^m d(x,y). $$

Dowód. Jeśli $m=1$, to nierówność wyraża jedynie definicję odwzorowania zwężającego. Jeśli $m>1$, to

$$ d(T^m(x),T^m(y))\le=d(T(T^{m-1}(x)),T(T^{m-1}(y)))\le Ld(T^{m-1}(x),T^{m-1}(y)) $$

i stosowna nierówność jest konsekwencją zasady indukcji.

Obserwacja b.

Dla każdej liczby naturalnej $k$ i każdego $x\in X$

$$ d(x,T^k(x))\le \frac 1{1-L} d(x,T(x)). $$

Dowód. Z nierówności trójkąta, dla każdego ciągu $(y_i\colon i=1,\ldots , k+1)$

$$ d(y_1, y_{k+1})\le d(y_1,y_2)+d(y_2,y_3)+\cdots +d(y_k,y_{k+1}). $$

Podstawmy $y_1=x, y_2=T(x), \ldots , y_{k+1}=T^{k}(x)$. Korzystając z obserwacji a otrzymamy

$$ d(x, T^k(x))\le d(x, T(x))+d(T(x),T^2(x))+\cdots +d(T^{k-1}(x), T^k(x))\le (1+L+\cdots + L^{k-1})d(x,T(x)\le \frac 1{1-L} d(x, T(x)). $$

Obserwacja c.

Dla każdej pary liczb naturalnych $m $$ d(T^m(x), T^n(x))\le \frac{L^m}{1-L} d(x, T(x)). $$

Dowód. Przyjmijmy $y=T^{n-m}(x)$ i skorzystajmy z obserwacji a:

$$ d(T^m(x), T^n(x))=d(T^m(x), T^m(y))\le L^m d(x, y). $$

Teraz podstawmy $k=n-m$. Wtedy $y=T^k(x)$ i w odniesieniu do $d(x,y)$ możemy skorzystać z obserwacji b.

Obserwacja d.

Wszystkie ciągi $(T^n(x))$, $x\in X$, są zbieżne do wspólnej granicy $x_0$.

Dowód. Ponieważ $\lim_{m\to \infty} L^m=0$, więc z obserwacji c wynika, że każdy z ciągów $(T^n(x))$, $x\in X$, jest Cauchy'ego. Wobec założenia o zupełności przestrzeni $X$ każdy z nich jest zbieżny. Ustalmy $u\in X$. Niech $x_0$ będzie granicą ciągu $(T^n(u))$. Dla wszelkich $n$ z nierówności trójkąta oraz obserwacji a mamy: $$ d(T^n(x),x_0)\le d(T^n(x), T^n(u))+d(T^n(u),x_0)\le L^nd(x,u)+d(T^n(u), x_0)\stackrel{\longrightarrow}{_{n\to \infty}} 0. $$ W takim razie wszystkie ciągi $(T^n(x))$ zbiegają do $x_0$.

Obserwacja e. $x_0$ jest jedynym punktem stałym odwzorowania $T$.

Dowód. Odwzorowanie $T$, jako zwężające jest ciągłe. W takim razie ciąg $T^{n+1}(x)=T(T^n(x))$ zbiega do zarówno do $T(x_0)$ (ciągłość), jak i do $x_0$ (obserwacja d). Ciąg zbieżny może mieć tylko jedną granicę, więc $T(x_0)=x_0$ i $x_0$ jest punktem stałym.

Przypuśćmy, że także pewien $u_0$ jest punktem stałym. Wtedy $T^n(u_0)=u_0$ i na podstawie obserwacji d ciąg stały $(u_0)$ zbiega do $x_0$. Stąd $u_0=x_0$.

Pozostaje wykazać $(2)$. Z nierówności trójkąta oraz obserwacji c dla $n>m$ mamy $$ d(T^m(x), x_0)\le d(T^m(x), T^n(x))+ d(T^n(x), x_0)\le \frac{L^m}{1-L} d(x, T(x))+ d(T^n(x), x_0). $$ Jednak drugi składnik po prawej stronie dąży do zera, gdy $n\to\infty$ na podstawie obserwacji d. Skąd natychmiast otrzymujemy żądaną nierówność.$\square$

Przykład 2k.

Niech $\mathbb C_{\mathbb R}[0,2]$ oznacza przestrzeń funkcji ciągłych, określonych na przedziale $[0,2]$ o wartościach rzeczywistych z metryką supremum. Niech $X$ oznacza jej podzbiór złożony z takich funkcji $f$, że $f(0)=f(2)=0$. Oczywiście $X$ jest podzbiorem domkniętym, a ponieważ sama przestrzeń jest zupełna, więc i $X$ jest przestrzenią zupełną. Obierzmy liczbę $L\in [0,1)$ i określmy odwzorowanie $T\colon X\to X$ wzorem $$ T(f)(x)=\left\{ \begin{array}{rl} Lf(2x)+x, & \text{dla $x\in [0,1]$},\\ Lf(-2x+4) -x+2, & \text{dla $x\in [1,2]$}. \end{array} \right. $$ Funkcja $T(f)$ jest sklejona z dwu funkcji ciągłych określonych na przedziałach $[0,1]$ i $[1,2]$ i zgodnych w $1$. Sama jest więc ciągła. Jej wspólna wartość w $0$ i $2$ jest równa $0$. W rezultacie $T$ jest poprawnie określonym odwzorowaniem z $X$ w $X$. Co więcej, dla każdej pary $f, g\in X$ mamy $$ |T(f)(x)-T(g)(x)|\le L|f-g|_\infty. $$ Stąd $$ |T(f)-T(g)|_\infty\le L|f-g|_\infty. $$ W oparciu o zasadę kontrakcji, istnieje jedyna funkcja $f_0$ będąca punktem stałym odwzorowania $T$. Jeśli przyjąć $f\equiv 0$, to ciąg $(T^n(f))$ zbiega do $f_0$. Można wykazać, że funkcja graniczna $f_0$ nie jest różniczkowalna w żadnym swoim punkcie. Poniżej znajdują się wykresy funkcji $T^n(f)$ dla $n=1, 4, 7, 9, 11, 15, 60$ oraz $L=0.7$. Po 15 iteracjach odwzorowania $T$ otrzymamy funkcję niewiele różniącą się od $f_0$. Kolejne rysunki dobrze ilustrują, dlaczego nie należy oczekiwać różniczkowalności funkcji $f_0$.

In [1]:
'''
Kontrakcja T, n - liczba iteracji,  f- funkcja startowa, x- argument, w którym wyliczamy wartość iteracji T^nf(x), 
L - stała Lipschitza o domyślnej wartości 0.7
'''
def T(n, f, x, L=0.7):  
    if n==0: return f(x)
    else:
        if 0<= x<= 1: return L*T(n-1, f, 2*x, L)+x
        if 1<= x<=2: return L*T(n-1, f,-2*x+4, L)-x+2
In [2]:
def zero(x): #funkcja startowa
    if 0<=x<=2: return 0

#współrzędne punktów do wyświetlenia    
xdat1=[n/5000 for n in range(10000)] 
def ydat1(n,f):
    return [T(n, f, x/5000, 0.7) for x in range(10000)]
In [3]:
import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl
In [4]:
for n in [1,4,7,9,15,60]:  
    mpl.rcParams['lines.linewidth'] = 1-n/100
    x=xdat1
    y=ydat1(n,zero)
    plt.plot(x,y)
    plt.title('Iteracja '+str(n)+ '. odwzorowania $T$ na funkcji zero')
    plt.show()
In [5]:
'''Zmieniamy funkcję startową na wiel(x)=x*(x-2)*(x-3) i powtarzamy iteracje'''

def wiel(x):
    return x*(x-2)*(x-3)

for n in [1,4,7,9,15,60]:  
    mpl.rcParams['lines.linewidth'] = 1-n/100
    x=xdat1
    y=ydat1(n,wiel)
    plt.plot(x,y)
    plt.title('Iteracja '+str(n)+ '. odwzorowania $T$ na funkcji wiel' )
    plt.show()

Ćwiczenie 1k.

Wzorując się na poprzedzającym przykładzie, zbuduj własne odwzorowania zwężające na przestrzeni $\mathbb C[a,b]$. Sporządź ilustracje sugerujące wygląd $f_0$.

Za pomocą zasady kontrakcji wskażemy teraz drogę $f\colon [0,1]\to \mathbb R^2$, która przechodzi przez wszystkie punkty kwadratu $K=[0,1]^2$. Jako pierwszy przykład takiej drogi wskazał Giuseppe Peano. Potem wskazano nieprzebraną liczbę rozmaitych dróg (przypomnijmy, że drogi są odwzorowaniami ciągłymi) o dodatkowych własnościach przekształcających przedział na kwadrat.

Przykład 2k.

Niech $X$ oznacza zbiór wszystkich takich dróg $g$ z $[0,1]$ w $[0,1]^2$, że $$ g(0)=(0,0), \qquad g(1)=(1,0). $$ $X$ jest przestrzenią metryczną zupełną z metryką supremum: $$ |f-g|_\infty= \sup \{|f(t)-g(t)|\colon t \in [0,1]\}. $$ Metryka w $\mathbb R^2$, względem której liczymy odległość $|f(t)-g(t)|$ to standardowa metryka euklidesowa. Jeśli utożsamić $\mathbb R^2$ z $\mathbb C$, to jest to metryka zadana przez moduł (liczby zespolonej). Określmy odwzorowanie $T\colon X\to X$ następująco:

Dla $g\in X$ przyjmijmy oznaczenia $g(t)=(x(t), y(t))$. Wtedy $$ T(g)(t)=\left\{ \begin{array}{rl} \frac 1 2 (y(4t), x(4t)), & t\in [0,\frac 1 4];\\ (0, \frac 1 2) +\frac 1 2(x(4t-1), y(4t-1)), & t\in [\frac 1 4, \frac 1 2];\\ (\frac 1 2, \frac 1 2) +\frac 1 2(x(4t-2), y(4t-2)), & t\in [\frac 1 2, \frac 3 4];\\ (1, \frac 1 2) -\frac 1 2(y(4t-3), x(4t-3)), & t\in [\frac 3 4, 1].\\ \end{array} \right. $$

$T(g)$ powstaje przez sklejenie czterech dróg. Tam gdzie dziedziny tych dróg zachodzą na siebie (końce przedziałów), wartości są równe, więc funkcja $T(g)$ też jest ciągła. Wprost z definicji wynika, że jeśli składowe drogi $T(g)$ oznaczyć przez $h_1,\ldots, h_4$, to obrazy tych dróg zawarte są w czterech kwadratach

$ K_1=\frac 1 2 K, \quad K_2=(0,\frac 1 2)+ \frac 1 2 K, \quad K_3=(\frac 1 2, \frac 1 2)+\frac 1 2 K, \quad K_4=(1,\frac 1 2) +\frac 1 2 K $

zawartych w $K$. Ponadto mamy,
$ T(g)(0)=(0,0),\quad T(g)(\frac 1 4 )=(0,\frac 1 2),\quad T(g)(\frac 1 2 )=(\frac 1 2, \frac 1 2),\quad T(g)(\frac 3 4)=(1,\frac 1 2), \quad T(g)(1)=(1,0). $

Stąd $T$ rzeczywiście przekształca $X$ w $X$ i co więcej, możemy sobie wyobrazić jak ono działa. W tym celu wybraliśmy trzy drogi startowe $d_1(x)=(x, 0)$, $d_2(x)=(x,\frac 12-|x-\frac 12|)$ oraz $d_3(x)=(x,\sin(\pi x))$. Dla $d_1$ wyliczylismy iteracje $1,2,7,9,10$, dla $d_2$ $-$ $1,2,7,9$, zaś dla numerycznie najbardziej złożonej $d_3$ $-$ $1,2,7$. Odwzorowanie $T$ jest kontrakcją ze stałą $L=0.5$, więc w zgodzie z twierdzeniem, bez względu na wybór drogi startowej wszystkie iteracje są zbieżne do tej samej drogi $g_0$.

Ćwiczenie 2k.

Wykazać, że $T$ jest kontrakcją ze stałą $L=\frac 12$.

In [6]:
from math import * 

def T(n, t , g):
    if n==0: return g(t)
    else:
        if 0<=t<=0.25: return [0.5*T(n-1,4*t,g)[1], 0.5*T(n-1,4*t,g)[0]]
        elif 0.25<=t<=0.5: return [0.5*T(n-1,4*t-1,g)[0], 0.5 +0.5*T(n-1,4*t-1,g)[1]]
        elif 0.5<=t<=0.75: return [0.5+0.5*T(n-1,4*t-2,g)[0], 0.5 +0.5*T(n-1,4*t-2,g)[1]]
        elif 0.75<=t<=1: return [1-0.5*T(n-1,4*t-3,g)[1], 0.5 -0.5*T(n-1,4*t-3,g)[0]]
    
def xdat(n,g):
    return [T(n,x/10000, g)[0] for x in range(10000)]
def ydat(n,g):
    return [T(n,x/10000, g)[1] for x in range(10000)]
In [7]:
def d1(x):
    return [x,0]

for n in [0,1,2,7,9,10]:  
    mpl.rcParams['lines.linewidth'] = 1-n/100
    x=xdat(n,d1)
    y=ydat(n,d1)
    plt.plot(x,y)
    plt.title('Iteracja '+str(n)+ '. odwzorowania $T$ na $d_1$'  )
    plt.show()
In [8]:
def d2(x):
    return [x,1/2-abs(x-1/2)]
for n in [0,1,2,7,9]:  
    mpl.rcParams['lines.linewidth'] = 1-n/100
    x=xdat(n,d2)
    y=ydat(n,d2)
    plt.plot(x,y)
    plt.title('Iteracja '+str(n)+ '. odwzorowania $T$ na $d_2$'  )
    plt.show()
In [9]:
def d3(x):
    return [x, sin(pi*x)]

for n in [0,1,2,7]:  
    mpl.rcParams['lines.linewidth'] = 1-n/100
    x=xdat(n,d3)
    y=ydat(n,d3)
    plt.plot(x,y)
    plt.title('Iteracja '+str(n)+ '. odwzorowania $T$ na $d_3$'  )
    plt.show()

Dwa kolejne rysunki przedstawiają wykresy odciętej i rzędnej drogi $T^9(d_2)$. Dzięki nim możemy się zorientować, w jaki sposób współrzędne drogi są skorelowane.

In [10]:
mpl.rcParams['lines.linewidth'] = 0.4
xx=[x/10000 for x in range(10000)]
u=[xdat(10,d2),ydat(10,d2)]
for i in range(2):
    plt.plot(xx,u[i])
    plt.title('Wykres współrzędnej $x_'+str(i+1)+'$ drogi $T^{9}(d_2)$')
    plt.show()

Niech $g_0$ oznacza punkt stały przekształcenia $T$. Pozostaje nam wykazać, że jeśli $B=g_0([0,1])$, to $B=K$. W istocie wystarczy wykazać, że $B$ jest gęstym podzbiorem $K$. Rzeczywiście, $[0,1]$ jest zbiorem zwartym, więc $B$, jako obraz zbioru zwartego w odwzorowaniu ciągłym. też musi być zwarty. Zwarte podzbiory przestrzeni metrycznej są automatycznie domknięte, więc jeśli $B$ jest gęstym podzbiorem zbioru $K$, to będąc równocześnie domkniętym musi być równy $K$. Przypuśćmy więc, że $B$ nie jest gęsty w $K$. Wtedy liczba $R$ zadana zależnością $$ R=\sup\{r>0\colon B(x,r)\cap B=\emptyset,\,\,\text{dla pewnego $x\in [0,1]^2$}\} $$ jest poprawnie określoną liczbą dodatnią. Niech $B_i=B\cap K_i$. Jeśli $B(x,r)\cap B$ jest zbiorem pustym, to oczywiście także $B(x,r)\cap B_i=\emptyset$. W takim razie,

$$ R\le \max\{R_i\colon i=1,\ldots, 4 \},\,\,\text{gdzie},\,\, R_i=\sup\{r>0\colon B(x,r)\cap B_i =\emptyset,\,\, \text{dla pewnego $x \in K_i$}\}. $$

Jednak w każdym z kwadratów $K_i$ mamy wierną kopię zbioru $B$ pomniejszoną dwukrotnie i położoną względem $K_i$ w taki sam sposób jak $B$ względem $K$ bądź lustrzanie. Stąd $R_i=\frac 1 2 R$. W konsekwencji, $R\le \frac 12 R$, co nie jest możliwe w przypadku liczby dodatniej.

Hiperprzestrzenie.

Mówimy, że funkcja $F\colon X\to Y$ z przestrzeni metrycznej $(X,d)$ w przestrzeń metryczną $(Y,D)$ jest lipschitzowska jeśli istnieje stała $L\ge 0$, że dla wszelkich $u,v\in X$ $$ D(F(u),F(v))\le Ld(u,v) $$ Kontrakcje są więc przykładami funkcji lipschitzowskich.

Dla dowolnego niepustego podzbioru $A$ przestrzeni metrycznej $(X,d)$ określamy odstęp punktu $x$ od zbioru $A$ wzorem $$ d(x,A)=\inf\{d(x,a)\colon a\in A\}. $$ Funkcję $x\mapsto d(x,A)$ nazywamy funkcją odstępu zbioru $A$.

Stwierdzenie 1h.

Niech $(X,d)$ $-$ przestrzeń metryczna oraz $A\subseteq X$ $-$ niepusty. Funkcja odstępu zbioru $A$ jest lipschitzowska z $L\le 1$.

Dowód. Dla każdej naturalnej $n$ i $v\in X$ istnieje $a \in A$, że $d(v,a)\le d(v, A)+\frac 1 n$. Stąd wobec definicji odstępu $$ d(u,A)-d(v,A)\le d(u,a)-d(v,a) + \frac 1 n\le d(u,v)+\frac 1 n $$ Po przejściu do granicy ze względu na $n$ $$ d(u,A)-d(v,A)\le d(u,v) $$ Ponieważ możemy zamienić rolami $u$ i $v$, więc wobec symetryczności metryki otrzymamy $$ |d(u,A)-d(v,A)|\le d(u,v). \qquad \square $$

Zbiór $A\subseteq X$ nazywamy ograniczonym jeśli $\operatorname{diam}(A)=\sup\{d(u,v)\colon u,v \in A\}< \infty$.

Przez $H(X)$ oznaczamy rodzinę wszystkich niepustych, domkniętych i ograniczonych podzbiorów przestrzeni $X$. Rodzina ta bywa nazywana hiperprzestrzenią przestrzeni $X$. Dla każdej pary $A, B\in H(X)$ określmy wielkość

$$ H(A,B)=\sup_{x\in X}|d(x,A)-d(x,B)|. \tag{hip1} $$

Stwierdzenie 2h.

$$ H(A,B)=\sup_{x\in A\cup B}|d(x,A)-d(x,B)|. $$

Dowód. Podobnie jak w dowodzie lipschitzowskości funkcji odstępu, dla każdej naturalnej $n$ istnieje $b\in B$, że $d(x,b)\le d(x,B)+\frac 1n$. Stąd wobec nierówności trójkąta, dla każdego $a\in A$ $$ d(x,A)-d(x,B)\le d(x,A)-d(x,b) +\frac 1 n\le d(x,a)-d(x,b) +\frac 1 n\le d(a,b)+\frac 1n. $$ Liczba $d(x,A)-d(x,B)$ jest więc dolnym ograniczeniem zbioru liczb $\{d(a,b)+\frac 1 n\colon a\in A\}$. Biorąc kres dolny tego zbioru otrzymamy

$$ d(x,A)-d(x,B)\le d(b, A)+\frac 1 n. $$

Stąd
$$ d(x,A)-d(x,B)\le \sup_{b\in B}d(b,A)+\frac 1n, $$ dla każdej naturalnej $n$. Składnik $\frac 1 n$ możemy teraz wyelimować, bo pozostałe składniki nierówności nie zależą od $n$. W takim razie $$ d(x,A)-d(x,B)\le \sup_{b\in B}d(b,A)=\sup_{x\in B}|d(x,A)-d(x,B)|. $$ Zamieniając rolami $A$ i $B$, $$ d(x,B)-d(x,A)\le \sup_{x\in A}|d(x,B)-d(x,A)|. $$ W rezultacie, $$ |d(x,A)-d(x,B)|\le \sup_{x\in A\cup B}|d(x,A)-d(x,B)|. $$ A stąd, wobec definicji $H(A,B)$, $$ H(A,B)\le \sup_{x\in A\cup B}|d(x,A)-d(x,B|\le H(A,B). \square $$

Ćwiczenie 1h.

Dla wszelkich $A, B\in H(X)$, $0\le H(A,B)=H(B,A)<\infty$. Ponadto, $H(A,B)=0$ wtedy i tylko wtedy, gdy $A=B$.

Ćwiczenie 2h.

Wykazać, że dla wszelkich $A,B\in H(X)$ zachodzą wzory:

  • $H(A,B)=\max\{ \sup_{x\in A} d(x,B), \sup_{x\in B} d(x,A)\}.$
  • $H(A,B)= \inf\{\rho\colon A\subseteq \bigcup_{x\in B} B(x,\rho), B\subseteq \bigcup_{x\in A} B(x,\rho)\}.$

Twierdzenie 3h.

Funkcja $(A,B)\mapsto H(A,B)$ jest metryką na $H(X)$. Przestrzeń metryczna $(H(X), H)$ jest zupełna.

Dowód. W świetle ćwiczenia 1h by wykazać, że $H$ jest metryką, pozostaje sprawdzić nierówność trójkąta. Niech $A,B,C\in H(X)$ i $x\in X$. Z definicji $H$ mamy

$$ |d(x,A)−d(x,B)|\le |d(x,A)−d(x,C)|+|d(x,C)−d(x,B)|\le H(A,C)+H(C,B) $$

W takim razie $ H(A,C)+H(C,B)$ jest górnym ograniczeniem liczb $|d(x,A)−d(x,B)|$, $x\in X$. I teraz już łatwo otrzymujemy nierówność trójkąta.

Ćwiczenie 3h.

Wykazać zupełność przestrzeni $(H(X),H)$. $\square$

Uwaga.

Metryka $H$ jest nazywana metryką Hausdorffa.

Twierdzenie 4h.

Niech $(X,d)$ $-$ przestrzeń metryczna zupełna. Niech $T_1,\ldots, T_s\colon X \to X$ $-$ skończony ciąg kontrakcji ze stałymi $L_1, \ldots, L_s$ . Określmy odwzorowanie $T\colon H(X)\to H(X)$ wzorem $$ T(A)=T_1[A]\cup\cdots \cup T_s[A]. $$ Wówczas $T$ jest kontrakcją przestrzeni $(H(X),H)$ ze stałą $L=\max\{L_1,\ldots, L_S\}$. W szczególności, istnieje jedyny zbiór $F\in H(X)$, dla którego zachodzi równość $$ F=T_1[F]\cup\cdots\cup T_s[F]. $$

Dowód. Wybierzmy dowolną parę zbiorów $A, B\in H(X)$. Ustalmy $x\in T(A)$. Wtedy istnieje $i\le s$ oraz $u \in A$, że $x=T_i(u)$. Stąd

$$ d(x,T(B))\le d(x, T_i[B])=\inf_{b\in B} d(T_i(u), T_i(b))\le \inf_{b\in B} L_id(u, b)\le Ld(u,B)\le LH(A,B) $$

Z takich samych powodów dla $x\in T(B)$

$$ d(x,T(A))\le LH(A,B). $$

W świetle pierwszego ze wzorów z ćwiczenia 2h mamy więc

$$ H(T(A), T(B))\le LH(A,B).\qquad \square $$

Uwaga. Nim przystąpimy do rozpatrzenia przykładu zauważmy, że jeśli w charakterze punktu startowego $A\in H(X)$ ciągu iteracji $(T^n(A))$ wziąć zbiór jednopunktowy (to znaczy, $A=\{u\}$ dla pewnego $u\in X$), to wszystkie zbiory $ T^n(A)$ są skończone. Co więcej, w świetle twierdzenia 1h

$$ H(T^m(A),F)\le \frac{L^m}{1-L} H(A,T(A))=\frac{L^m}{1-L} H(\{u\},\{T_i(u)\colon i\le k)=\frac{L^m}{1-L}\max_{i\le k}d(u,T_i(u)). $$

W takim razie zbiór skończony $T^m(\{u\}$ świetnie przybliża $F$ nawet, gdy liczba $m$ jest niewielka.

Ćwiczenie 4h.

Niech $(A_n)$ będzie ciągiem zbieżnym do $A$ w przestrzeni $H(X)$, złożonym jedynie ze zbiorów skończonych. Wykazać, że $A$ jest zbiorem zwartym.

Ćwiczenie 5h.

Wykazać, że zbiór $F$, o którym mowa w twierdzeniu 4h, musi być zwarty.

Przykład 1h.

Niech $X=\mathbb R^2$. Niech $R(x)=R(x, \varphi, L, t)$ $-$ złożenie obrotu o kąt $\varphi$ z jednokładnością o skali $L<1$ i przesunięciem o wektor $t$. Niech $T_i(x)=R(x,\varphi_i, L_i, t_i)$, gdzie $i=1,\ldots, k$. Szukamy punktu stałego odwzorowania $T$.

Zacznijmy od opisania odwzorowania $R$. $$ R(x)=L\left[\begin{array}{rr} \cos \varphi & -\sin \varphi\\ \sin \varphi & \cos \varphi \end{array}\right]\left[\begin{array}{r} x_1\\x_2\end{array}\right] +\left[\begin{array}{r} t_1\\t_2\end{array}\right]. $$

Następnie określmy $T_1$ i $T_2$ przyjmując na początek $\varphi_1=\frac \pi 8$, $L_1=0.65$, $t_1=(1,0)$ oraz $\varphi_2=\frac 7{12}\pi$, $L_2=0.67$, $t_2=(-1,-1)$.

Niech $A=\{(0,0)\}$. Jak łatwo sprawdzić, przy takich danych $H(A, T^m(A))\le 10(0.67^m)$. W takim razie $T^{15}(A)$ różni się, w sensie odległości Hausdorffa, od zbioru $F$, będącego punktem stałym odwzorowania $T$ o mniej niż $0.025$.

In [1]:
from math import *
def R(x,fi,L,t): #określenie obrotu; indeksy pomniejszone o 1 zgodnie z konwencją Pythona 
    return [L*(cos(fi)*x[0]-sin(fi)*x[1])+t[0], L*(sin(fi)*x[0]+cos(fi)*x[1])+t[1]]

def T(x):
    return [R(x, pi/8, 0.65,[1,0]), R(x, (7/12)*pi, 0.67, [-1,-1])]


F=[[0,0]]
for i in range(15):
    F=[T(x)[0] for x in F]+[T(x)[1] for x in F]
In [12]:
xax=[x[0] for x in F]
yax=[x[1] for x in F]
plt.scatter(xax,yax,marker='.', s=0.15, color='darkred')
plt.title('Zbiór graniczny $F$ $-$ punkt stały odwzorowania $T$')
plt.show()
In [13]:
color=['r' for x in range(16384)]+['b' for x in range(16384, 32768)]
plt.scatter(xax,yax,marker='.', s=0.15, color=color)
plt.title('Zbiór $F$ rozłożony na dwie części: $T_1(F)$ $-$ czerwona, $T_2(F)$ $-$ niebieska')
plt.show()

Zbiór $F$ jest przykładem fraktala. Fraktale charakteryzują się tym, że jeśli powiększać ich niewielkie fragmenty, to te nadal mają złożoną strukturę. Oczywiście powinniśmy sprecyzować co rozumiemy przez fragment. Można przyjąć, że jest to część wspólna fraktala i dowolnej kuli (w sensie metrycznym), o ile jest niepusta. Niektórzy wskazują na inną własność fraktali $-$ samopodobieństwo. Czynił to także twórca i propagator tego pojęcia Benoit Mandelbrot.

Ćwiczenie 6h.

Przygotuj krótki szkic na maksimum dwie strony na temat fraktali.