Twierdzenie Banacha o punkcie stałym

Q: Co to dokładnie jest punkt stały?

Punkt, którego odwzorowanie nie przesuwa: T(x^) = x^. Rozwiązywanie równania f(x) = 0 można zawsze przerobić na szukanie punktu stałego, np. dla T(x) = x - f(x) - dlatego twierdzenia o punktach stałych są uniwersalnym narzędziem do równań.

Q: Dlaczego przestrzeń musi być zupełna?

Bo iteracja produkuje ciąg Cauchy'ego, a bez zupełności taki ciąg może nie mieć granicy w przestrzeni - punkt stały „wycieka przez dziurę", jak √2 przy iteracji Herona na liczbach wymiernych.

Q: Czy wystarczy, że odwzorowanie zbliża każde dwa punkty?

Nie - kontrprzykład x + 1/x pokazuje, że ściąganie bez wspólnego współczynnika q < 1 nie gwarantuje punktu stałego. Tempo zbliżania musi być jednolite w całej przestrzeni.

Q: Ile iteracji potrzeba do zadanej dokładności?

Oszacowanie d(x_n, x^*) ≤ q^n/1-q d(x_1, x_0) pozwala to policzyć z góry: błąd maleje geometrycznie, każda iteracja mnoży go co najwyżej przez q. Dla q = 0,85 (PageRank) sto iteracji redukuje błąd około 10^7 razy.

Q: Czym różni się to twierdzenie od twierdzenia Brouwera o punkcie stałym?

Brouwer mówi, że każde ciągłe odwzorowanie kuli w siebie ma punkt stały - bez założenia kontrakcji, ale też bez jednoznaczności i bez przepisu na znalezienie go. Banach zakłada więcej i w zamian daje jedyność, konstrukcję oraz tempo zbieżności. To dwa różne narzędzia na dwa różne problemy.

Twierdzenie Banacha o punkcie stałym (1922)

Niech $(X, d)$ będzie zupełną przestrzenią metryczną, a $T \colon X \to X$ kontrakcją, czyli odwzorowaniem zbliżającym punkty w jednolitym tempie:

$d(T(x), T(y)) \leq q \cdot d(x, y) \qquad \text{dla pewnego } 0 \leq q < 1.$

Wtedy $T$ ma dokładnie jeden punkt stały $x^*$ (czyli $T(x^*) = x^*$ ), a iteracja $x_{n+1} = T(x_n)$ zbiega do niego z każdego punktu startowego, z oszacowaniem błędu

$d(x_n, x^*) \leq \frac{q^n}{1-q} \, d(x_1, x_0).$

Co mówi twierdzenie

Punkt stały odwzorowania to punkt, którego ono nie rusza: $T(x^*) = x^*$ . Najbardziej obrazowy przykład: rozłóż mapę Polski na stole gdziekolwiek w Polsce. Mapa jest pomniejszoną kopią terytorium - kontrakcją ze skalą $q$ równą skali mapy. Twierdzenie mówi, że istnieje dokładnie jeden punkt mapy leżący fizycznie na miejscu, które przedstawia - i że można go znaleźć, składając w myślach mapę w mapę w mapę…

Siła twierdzenia leży w trzech rzeczach naraz: punkt stały istnieje, jest jedyny, a dowód podaje przepis na jego znalezienie wraz z gwarancją tempa. To rzadkość - większość twierdzeń o istnieniu (jak twierdzenie o wartości pośredniej) nie mówi, jak szybko przybliżenia zbiegają.

Przykład - klawisz cosinus

Weź kalkulator (w trybie radianów), wpisz dowolną liczbę i naciskaj cos w kółko:

$1 \to 0{,}5403 \to 0{,}8576 \to 0{,}6543 \to 0{,}7935 \to 0{,}7014 \to 0{,}7640 \to \ldots \to 0{,}7390851\ldots$

Wynik zawsze zastyga na tej samej liczbie $x^* \approx 0{,}739$ - jedynym rozwiązaniu równania $\cos x = x$ . Dlaczego? Bo na przedziale, w którym iteracja szybko ląduje, cosinus jest kontrakcją: jego pochodna spełnia $|\sin x| \leq \sin 1 \approx 0{,}84 < 1$ , więc każde naciśnięcie klawisza zmniejsza odległość od $x^*$ co najmniej o czynnik $0{,}84$ .

Diagram pajęczynowy: z punktu startowego x₀ idziemy pionowo do wykresu T, poziomo do przekątnej y = x i znów pionowo - schodki zbiegają do punktu stałego x*, w którym wykres przecina przekątną.

Dowód

Pokaż dowódUkryj dowód

Krok 1. Uruchamiamy iterację. Wybieramy dowolny punkt startowy $x_0$ i definiujemy $x_{n+1} = T(x_n)$ . Odległości kolejnych wyrazów kurczą się geometrycznie:

$d(x_{n+1}, x_n) = d(T(x_n), T(x_{n-1})) \leq q \, d(x_n, x_{n-1}) \leq \ldots \leq q^n \, d(x_1, x_0).$

Krok 2. Ciąg jest ciągiem Cauchy’ego. Dla $m > n$ szacujemy przez nierówność trójkąta i sumę szeregu geometrycznego:

$d(x_m, x_n) \leq \sum_{k=n}^{m-1} d(x_{k+1}, x_k) \leq d(x_1, x_0) \sum_{k=n}^{\infty} q^k = \frac{q^n}{1-q} \, d(x_1, x_0).$

Prawa strona dąży do zera, więc wyrazy ciągu zbijają się dowolnie blisko siebie.

Krok 3. Granica istnieje - tu pracuje zupełność. W przestrzeni zupełnej każdy ciąg Cauchy’ego ma granicę; oznaczmy ją $x^*$ . To jedyne miejsce dowodu, w którym korzystamy z zupełności - i bez niej twierdzenie upada (kontrprzykład niżej). Ten sam wniosek można uzyskać z zasady zstępujących zbiorów domkniętych Cantora: kule domykające ogon iteracji mają średnice dążące do zera, a ich przecięcie to właśnie $x^*$ .

Krok 4. Granica jest punktem stałym. Kontrakcja jest ciągła (zbliża punkty, więc tym bardziej nie rozrywa granic), zatem

$x^* = \lim_{n \to \infty} x_{n+1} = \lim_{n \to \infty} T(x_n) = T\left(\lim_{n \to \infty} x_n\right) = T(x^*).$

Krok 5. Punkt stały jest jedyny. Gdyby $T(x^*) = x^*$ oraz $T(y^*) = y^*$ dla $x^* \neq y^*$ , to

$d(x^*, y^*) = d(T(x^*), T(y^*)) \leq q \, d(x^*, y^*) < d(x^*, y^*)$

liczba dodatnia mniejsza od samej siebie. Sprzeczność, więc $x^* = y^*$ .

Krok 6. Oszacowanie błędu za darmo. Przechodząc w kroku 2 z $m \to \infty$ :

$d(x_n, x^*) \leq \frac{q^n}{1-q} \, d(x_1, x_0). \qquad \blacksquare$

Ostatnia nierówność jest praktyczna: przed rozpoczęciem obliczeń wiadomo, ile iteracji wystarczy do zadanej dokładności - wystarczy znać $q$ i pierwszy krok.

Kontrprzykłady - po co każde założenie

Bez zupełności. Weźmy $T(x) = \tfrac{x}{2}$ na przedziale $(0, 1]$ - wzorowa kontrakcja z $q = \tfrac{1}{2}$ . Iteracja zbiega do zera… którego nie ma w przestrzeni. Punkt stały „ucieka przez dziurę”. To samo dzieje się na liczbach wymiernych: iteracja Herona $x \mapsto \tfrac{1}{2}\left(x + \tfrac{2}{x}\right)$ prowadzona na ułamkach zbiega do $\sqrt{2}$ , którego wśród ułamków nie ma.

Bez jednolitego $q$ . Odwzorowanie $T(x) = x + \tfrac{1}{x}$ na przedziale $\langle 1, +\infty)$ ściśle zbliża każdą parę punktów: $d(T(x), T(y)) < d(x, y)$ . A mimo to punktu stałego nie ma - równanie $x + \tfrac{1}{x} = x$ nie ma rozwiązań, a iteracja ucieka do nieskończoności. Samo „zbliżanie” nie wystarcza: potrzebny jest wspólny mnożnik $q < 1$ , ten sam dla wszystkich par. (Na przestrzeniach zwartych słabsze założenie już wystarcza - to twierdzenie Edelsteina.)

Bez $q < 1$ . Przesunięcie $T(x) = x + 1$ zachowuje odległości ( $q = 1$ ) i oczywiście nie ma punktu stałego. Granica między $q < 1$ a $q = 1$ jest ostra.

Po co to komu

Równania różniczkowe. Najważniejsze zastosowanie: twierdzenie Picarda-Lindelöfa o istnieniu i jednoznaczności rozwiązań równań różniczkowych to twierdzenie Banacha zastosowane do odwzorowania całkowego na przestrzeni funkcji. Cała deterministyczna fizyka - od trajektorii planet po obwody elektryczne - opiera się na tym, że układ równań ruchu ma dokładnie jedno rozwiązanie.
Metody iteracyjne. Schemat „przekształcaj wynik aż przestanie się zmieniać” to chleb powszedni obliczeń numerycznych: iteracja prosta, metoda Jacobiego i Gaussa-Seidla dla wielkich układów równań, uczenie przez iterację w ekonomii i teorii gier.
PageRank. Ranking stron Google to punkt stały odwzorowania „rozdaj swoją ważność linkowanym stronom”. Współczynnik tłumienia $0{,}85$ czyni z niego kontrakcję z $q = 0{,}85$ - twierdzenie Banacha gwarantuje, że ranking istnieje, jest jedyny i policzalny iteracyjnie w kilkudziesięciu krokach dla całego internetu.
Fraktale. Paproć Barnsleya i podobne obrazy to punkty stałe kontrakcji działających na przestrzeni zbiorów (systemy funkcji iterowanych). Rysowanie fraktala to dosłownie iteracja z dowodu - a jednoznaczność punktu stałego tłumaczy, czemu z każdego obrazka startowego wychodzi ta sama paproć.

Kto i kiedy

Stefan Banach (1892-1945) udowodnił twierdzenie w swoim doktoracie (1920), opublikowanym w 1922 roku w „Fundamenta Mathematicae” - w pracy, która przy okazji ufundowała analizę funkcjonalną, z przestrzeniami nazwanymi później jego imieniem.

Banach był w dużej mierze samoukiem; do matematyki akademickiej trafił, gdy Hugo Steinhaus przypadkiem usłyszał na krakowskich Plantach dwóch młodych ludzi rozmawiających o całce Lebesgue’a. Steinhaus nazywał później Banacha swoim „największym odkryciem naukowym”. Wokół Banacha wyrosła lwowska szkoła matematyczna, obradująca przy kawiarnianych stolikach - problemy zapisywano w słynnej Księdze Szkockiej, a za rozwiązania wyznaczano nagrody od kawy po żywą gęś.

Zasada kontrakcji jest dziś jednym z najczęściej stosowanych twierdzeń całej matematyki - i chyba najkrótszą drogą od polskiej kawiarni do algorytmu, który rankinguje internet.

Najczęstsze pytania

Co to dokładnie jest punkt stały? Punkt, którego odwzorowanie nie przesuwa: $T(x^*) = x^*$ . Rozwiązywanie równania $f(x) = 0$ można zawsze przerobić na szukanie punktu stałego, np. dla $T(x) = x - f(x)$ - dlatego twierdzenia o punktach stałych są uniwersalnym narzędziem do równań.

Dlaczego przestrzeń musi być zupełna? Bo iteracja produkuje ciąg Cauchy’ego, a bez zupełności taki ciąg może nie mieć granicy w przestrzeni - punkt stały „wycieka przez dziurę”, jak $\sqrt{2}$ przy iteracji Herona na liczbach wymiernych.

Czy wystarczy, że odwzorowanie zbliża każde dwa punkty? Nie - kontrprzykład $x + \tfrac{1}{x}$ pokazuje, że ściąganie bez wspólnego współczynnika $q < 1$ nie gwarantuje punktu stałego. Tempo zbliżania musi być jednolite w całej przestrzeni.

Ile iteracji potrzeba do zadanej dokładności? Oszacowanie $d(x_n, x^*) \leq \tfrac{q^n}{1-q} d(x_1, x_0)$ pozwala to policzyć z góry: błąd maleje geometrycznie, każda iteracja mnoży go co najwyżej przez $q$ . Dla $q = 0{,}85$ (PageRank) sto iteracji redukuje błąd około $10^7$ razy.

Czym różni się to twierdzenie od twierdzenia Brouwera o punkcie stałym? Brouwer mówi, że każde ciągłe odwzorowanie kuli w siebie ma punkt stały - bez założenia kontrakcji, ale też bez jednoznaczności i bez przepisu na znalezienie go. Banach zakłada więcej i w zamian daje jedyność, konstrukcję oraz tempo zbieżności. To dwa różne narzędzia na dwa różne problemy.

Podsumowanie

Kontrakcja na przestrzeni zupełnej ma dokładnie jeden punkt stały, a iteracja $x_{n+1} = T(x_n)$ znajduje go z każdego startu.
Dowód w trzech ruchach: odległości kurczą się geometrycznie → ciąg Cauchy’ego → zupełność daje granicę; jednoznaczność to jedna nierówność.
Twierdzenie jest konstruktywne: oszacowanie $\tfrac{q^n}{1-q} d(x_1, x_0)$ z góry mówi, ile iteracji wystarczy.
Założenia są ostre: bez zupełności punkt ucieka przez dziurę, bez wspólnego $q < 1$ może go nie być wcale ( $x + \tfrac{1}{x}$ ).
Zastosowania od Picarda-Lindelöfa (jednoznaczność rozwiązań równań różniczkowych) przez metody iteracyjne i fraktale po PageRank - autorstwa Stefana Banacha, z doktoratu z 1920 roku.