„Banach fixponttétele” változatai közötti eltérés

[ellenőrzött változat][ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
jobb a lektor
Klj (vitalap | szerkesztései)
Nincs szerkesztési összefoglaló
1. sor:
A '''Banach-féle fixponttétel''' azt mondja, hogy [[Teljes metrikus tér|teljes metrikus térben]] minden [[kontrakció|kontrakciónak]] („távolságzsugorító függvénynak”) létezik pontosan egy [[fixpont]]ja. A tétel jelentőségét az adja, hogy az analízis olyan alapvető tételeinek, mint az [[inverzfüggvény-tétel]], vagy [[Picard-Lindelöf-tétel]], a bizonyítása Banach fixponttételén múlik. A tétel eredeti bizonyítása maga is [[konstruktív bizonyítás|konstruktív]], vagyis a fixpontnak nemcsak a létezését bizonyítja, de az konkrétan (legalábbis határértékként) meg is adható, sőt, a kapott sorozat a konvergenciasebessége is jól becsülhető, így a tétel jól alkalmazható a [[Numerikus analízis|numerikus matematikában]] is. A tétel a nevét [[Stefan Banach]]ról kapta (1892-1945), aki 1922-ben publikálta.
{{lektor}}
==A tétel==
A '''Banach-féle fixponttétel''', amely a [[metrikus tér|metrikus terek]] elméletének egyik fontos része, az ún. [[kontrakció]]k („távolságzsugorító függvények”) [[fixpont]]jának egyértelmű létezését biztosítja. A tételre [[konstruktív bizonyítás]] is adható, vagyis a fixpontnak nemcsak a létezését bizonyítja, de az konkrétan (legalábbis határértékként) meg is adható. A tétel a nevét [[Stefan Banach]]ról kapta (1892-1945), aki 1922-ben publikálta.
Azokat a [[Lipschitz-tulajdonság|Lipschitz-függvényeket]], amiknek a Lipschitz-konstansa kisebb mint egy, kontrakciónak nevezzük, tehát ''f'':''X''→''X'' kontrakció, ha van olyan ''L''<1, hogy minden ''X''-beli ''x''-re és ''y''-ra:
:<math>d(f(x),f(y))\leq L\cdot d(x,y)</math>
<blockquote>'''Banach fixponttétele.''' Legyen ''X'' nem üres tér metrikus tér, és ''f'':''X''→''X'' kontrakció. Ekkor pontosan egy olyan ''x*'' van ''X''-ben, amire ''f''(''x*'')=''x*''. </blockquote>
 
===Bizonyítás===
== Banach-féle fixponttétel ==
Minden kontrakciónak legfeljebb egy fixpontja van. Legyen ugyanis ''x'' és ''y'' ''f'' kontrakció két fixpontja. Ekkor ''x'' és ''y'' távolsága ugyanakkora, mint ''f''(''x'') és ''f''(''y'') távolsága, de alkalmas ''L'' egynél kisebb Lipschitz-konstansra:
:<math>d(f(x),f(y))\leq Ld(x,y)</math>,
amiből kapjuk, hogy ''d''(''x'',''y'')=0, amivel a fixpont unicitását igazoltuk.
 
Legyen ''x<sub>''0''</sub>'' ''X'' tetszőleges eleme, és definiáljuk rekurzióval az ''x<sub>n+''1''</sub>''=''f''(''x<sub>n</sub>'') sorozatot, erről fogjuk belátni, hogy konvergens, és a határértéke fixpontja ''f''-nek.
[[Teljes metrikus tér|Teljes]] [[metrikus tér]]ben [[kontrakció]]nak egyértelműen létezik fixpontja. Ha tehát ''F'' merikus tér és ''f'': ''F'' <math>\to</math> ''F'' kontrakció, akkor létezik egyértelműen olyan ''x''* ∈ ''F'', hogy
Először is tegyük fel, hogy ''x<sub>n</sub>'' sorozat konvergens, és határértéke ''x*''. Mivel ''f'' Lipschitz, folytonos, így az átviteli elvet alkalmazva:
:<math> f \left(x^* \right) =x^* </math>.
:<math>\lim\limits_n f(x_n)=f(x^*)</math>
Tekintve, hogy ''f''(''x<sub>n</sub>'')=''x<sub>n+''1''</sub>'', a baloldali határérték is ''x*'', így ''x*'' valóban fixpont.
Csak azt kell megmutatnunk, hogy ''x''<sub>''n''</sub> sorozat konvergens. Teljes indukcióval rögtön adódik, hogy:
:<math>d(x_n,x_{n+1})\leq L^nd(x_0,x_1)</math>
Legyen ''n''<''m''. A háromszögegyenlőtlenség ismételt alkalmazásával kapjuk, hogy
:<math>d(x_n,x_m)\leq d(x_n,x_n+1) + \ldots + d(x_m-1,x_m)</math>
ahol a jobboldalt az előző becsléssel felűlről becsülhetjük:
:<math>d(x_n,x_n+1) + \ldots + d(x_m-1,x_m)\leq (L^n+\ldots+L^{m-1})d(x_0,x_1)</math>
Alkalmazva a [[mértani sorozat]] összegképletét:
:<math>d(x_n,x_m)\leq L^n \frac{1-L^{m-n}}{1-L}d(x_0,x_1)</math>
mivel 1-''L<sup>m-n</sup>''<1, a jobboldal ismét felülről becsülhető:
:<math>L^n \frac{1-L^{m-n}}{1-L}d(x_0,x_1)\leq \frac{L^n}{1-L}d(x_0,x_1)</math>
Legyen ''ε''>0 tetszőleges, és ''N'' olyan, hogy
:<math>\frac{L^N}{1-L}d(x_0,x_1)<\varepsilon</math>
Ha ''N''<''n''<''m'', akkor az előző becslést alkalmazva
:<math>d(x_n,x_m)\leq\frac{L^n}{1-L}d(x_0,x_1),</math>
ahol a jobboldal a feltételek szerint:
:<math>\frac{L^n}{1-L}d(x_0,x_1)<\frac{L^N}{1-L}d(x_0,x_1),</math>
azaz
:<math>d(x_n,x_m)<\varepsilon,</math>
tehát ''x<sub>n</sub>'' sorozat Cauchy, és a tér Banach, így a sorozat konvergens, amivel a bizonyítást befejeztük.
 
===Konvergencia-sebesség===
(Itt ''teljes metrikus téren'' olyan teret értünk, melyben minden [[Cauchy-sorozat]] [[Konvergencia (matematika)|konvergens]]. ''f'': ''F'' <math>\to</math> ''F'' kontrakció (néhány szerzőnél: ''erős'' v. ''szűkebb értelemben vett) kontrakció'', amennyiben létezik olyan ''q'' < 1 pozitív [[valós szám]], hogy minden ''x'',''y'' ∈ ''F''-re
A bizonyításnál felhasznált sorozat konvergencia-sebességére a bizonyításból is kiolvasható, hogy
:<math> d\left(f\left(x\right),f\left(y\right)\right)\leq q\cdot d\left(x,y\right)</math>
:<math>d(x_n,x^*)\leq \frac{L^n}{1-L}d(x_0,x_1).</math>
Mint láttuk,
:<math>d(x_n,x^m)\leq \frac{L^n}{1-L}d(x_0,x_1),</math>
és mivel a jobboldal független ''m''-től, ''m''-mel tartva a végtelenhez, kapjuk a becslést.
 
==Alkalmazások==
Ez esetben az ''f'' számára ''q'' nem más, mint egy egynél kisebb [[Lipschitz-tulajdonság|Lipschitz-konstans]].
* A tétel egyik legfontosabb alkalmazása a Picard-Lindelöf-tétel bizonyítása, ami bizonyos [[közönséges differenciálegyenlet|közönséges differenciálegyenletek]] megoldásának egyértelmű létezéséről szól. A bizonyítás során a [[differenciálegyenlet]] keresett megoldását egy olyan alkalmas integráloperátor fixpontjaként állítjuk elő, ami folytonos függvényeket folytonos függvényekbe visz. A Banach-fixponttétellel a fixpont egyértelműségét igazoljuk.
 
*A fixponttétel másik fontos következménye, hogy az identitás kicsiny Lipschitz-perturbációi bilipschitz homeomorfizmusok. Ez utóbbi ténynek közvetlen folyománya az [[Inverzfüggvény-tétel|inverzfüggvény-tétel]].
=== Bizonyítás ===
* A numerikus analízisben a gyökközelítő módszerek tekintélyes osztályát adják az úgynevezett fixpontiterációs módszerek, amelyek azon az elven nyugszanak, hogy az ''f''(''x'')=0 gyökét egy olyan alkalmas függvény fixpontjaként állítják elő, ami a keresett gyök valamilyen környezetén kontrakció. Ezen módszerek tipikus példája elég sima függvényekre a [[Newton-módszer]] és lineáris egyenletrendszerek numerikus megoldására a [[Jacobi-iteráció]].
 
A következő bizonyítás konstruktív, abban az értelemben, hogy egy rekurzív sorozat határértékeként szolgáltatja a fixpontot.
 
Legyen (''x''<sub>''k''</sub>) az az '''F''-ben haladó sorozat, melyben
:<math>x_0 \in F </math>
rögzített és minden ''k'' természetes számra
:<math> x_{k+1}=f \left(x_k\right) </math>
 
A fenti [[sorozat (matematika)|sorozat]] megadása alapján a tagok távolságára adódik, hogy
:<math> d\left(x_{k+1},x_k\right)=d\left(f\left(x_k\right),f\left(x_{k-1}\right)\right)\le q\cdot \left(x_k,x_{k-1}\right)</math>
A rekurziót folytatva azt kapjuk, hogy <math> d\left(x_{k+1},x_k\right)\le q^k\cdot d\left(x_0,x_1\right) </math>.<br />
A [[háromszög-egyenlőtlenség]]et felhasználva:<math> d\left(x_n,x_m\right)\le d\left(x_n,x_{n+1}\right)+d\left(x_{n+1},x_{n+2}\right)+ \cdots +d\left(x_{m-1},x_m\right)</math> adódik.<br />
Erre alkalmazva az első összefüggést (a <math>d\left(x_0,x_1\right) </math> konstanst D-vel jelölve) adódik a következő:
<math> d\left(x_n,x_m\right)\le d\left(x_n,x_{n+1}\right)+d\left(x_{n+1},x_{n+2}\right)+ \cdots +d\left(x_{m-1},x_m\right)\le q^n\cdot D +q^{n+1}\cdot D +\cdots +q^{m-1}\le D\cdot q^n \left(1+q+q^2+\cdots +q^{m-n+1}+\cdots \right)=\frac{D\cdot q^n}{1-q}\longrightarrow 0 </math> amiből következik hogy <math> \left\{x_n\right\} </math> [[Cauchy-sorozat]].<br />
Mivel a metrikus tér teljes (így benne minden [[Cauchy-sorozat]] konvergens) így <math> \exist x^* \in F </math> amire <math> x_n \rightarrow x^* </math>.<br />
Ekkor <math> x^*=f\left(x^*\right) </math> ugyanis,a [[háromszög-egyenlőtlenség]]et majd f kontrakció voltát felhasználva adódik,hogy:<br />
<math> d\left(x^*,f\left(x^* \right) \right) \le d\left(x^*,x_{n+1}\right)+d\left(x_{n+1},f\left(x^* \right)\right) \le </math> <br />
<math> \le d\left(x^*,x_{n+1}\right)+d\left(f\left(x_n \right),f\left(x^*\right)\right) \le d\left(x^*,x_{n+1}\right)+q\cdot d\left(x_{n+1},x^*\right) \le </math> <br />
<math> \le \left(1+q \right)\cdot d\left(x_n,x^*\right) </math> igaz tetszőleges n-re (ahol <math> n \in \mathbb{N} </math>).<br />
Így mivel <math> x_n\rightarrow x^* \Rightarrow \forall \varepsilon </math>-ra <math> d\left(x^*,f\left(x^*\right)\right)<\varepsilon \Rightarrow d\left(x^*,f\left(x^*\right)\right)=0 </math> amely metrikus térben csak akkor teljesül ha <math> x^*=f\left(x^*\right) </math>.<br />
Egyértelműség igazolása.<br />
Tegyük fel,hogy <math> \exist x^*,y^* </math> két fixpont.<br />
Ekkor <math> d\left(x^*,y^* \right)=d\left(f\left(x^* \right),f\left(y^* \right)\right) \le q\cdot d\left(x^*,y^* \right) \Rightarrow d\left(x^*,y^*\right)=0 \Rightarrow x^*=y^* </math>.
 
== Banach-féle fixponttételhez kapcsolódó egyéb tételek ==
=== Tétel(1) ===
 
Legyen <math> f\in \mathcal{C}_{\left[a,b \right]} </math> és <math> \left|f'\left(x\right)\right|< 1,\forall x\in \left[a,b\right] </math> akkor <math> f </math> kontrakció.
 
=== Bizonyítás ===
<math> q:=max_{x \in \left[a,b\right]} \left|f'\left(x\right)\right| </math>.A [[Lagrange]]-középértéktétel alapján <math> \forall x,y \in \left[a,b\right] \exist \xi \in \left(a,b\right)</math>:<br />
<math> \left|f\left(x\right)-f\left(y\right)\right|= \left|x-y\right|\cdot f'\left(\xi\right)\le q\cdot\left|x-y\right|</math>.
 
=== Tétel(2) ===
Legyen <math> f\in \mathcal{C}_{\left[a,b\right]} </math> és létezzen <math> \xi \in \left[a,b\right]</math> és <math> \psi > 0 </math> melyre <math> \left|f'\left(x\right)\right|\le q < 1, \forall x \in \left[\xi-\psi,\xi+\psi\right]
\subseteq \left[a,b\right]</math>.Ha <math> \exist 0<r<\psi</math>,melyre <math> \left|f\left(\xi\right)-\xi\right|\le\left(1-q\right)</math>,akkor <math> f </math> kontrakció <math>\left[\xi-r,\xi+r\right]</math>-en és <math> \forall \in \left[\xi-r,\xi+r\right] </math> esetén <math> \xi-r\le\left(x\right)\le \xi+r </math>.
 
=== Bizonyítás ===
Legyen <math> x \in \left[\xi-r,\xi+r\right]</math>.Ekkor <math> \left|f\left(x\right)-\xi\right|</math>-ot becsülhetjük a [[háromszög-egyenlőtlenség]]et felhasználva a következőképpen:<br />
<math> \left|f\left(x\right)\right|=\left|f\left(x\right)-f\left(\xi\right)+f\left(\xi\right)-\xi\right| \le</math> <math>\left|f\left(x\right)-f\left(\xi\right)\right|+\left|f\left(\xi\right)-\xi\right|</math> <math> \le q\cdot \left|x-\xi\right|+\left(1-q\right) \cdot r \le r </math>
azaz<math> f\left(x\right)\in \left[\xi-r,\xi+r\right]</math>.Így ezzel belázzuk,hogy <math>f</math>-re a fixponttétel feltételei teljesülnek <math> \left[a,b\right]=\left[\xi-r,\xi+r\right]</math>-rel.
=== Következmény ===
<math>\exist ! x^*\in\left[\xi-r,\xi+r\right] </math> és <math> \forall x_0 \in \left[\xi-r,\xi+r\right]</math>-re az <math> x_{k+1}=f\left(x_k\right)</math> iteráció konvergál x*-hoz.
 
=== Fogalom ===
Az <math> x_k</math> [[konvergens]] sorozat p-edrendben konvergál <math> x^*</math>-hoz,ha <math> \exist C\in\mathbb{R^{+}}:\lim_{k \to \infty}\frac{\left|x_{k+1}-x^*\right|}{\left|x_k-x^*\right|^{p}}=C</math>.
=== Megjegyzés ===
1.A gyakorlatban a következő egyenlőtlenséget szokták,helyette használni:<math>\exist K\in\mathbb{R}:\left|x_{k+1}-x^*\right|\le K\cdot\left|x_k-x^*\right|^{p} \forall k</math>(Ekkor legalább p-edrendben konvergens).
2.
p=1:lineáris konvergencia<br />
p>1:superlineáris konvergencia<br />
p=2:kvadratikus konvergencia<br />
3.
A fixponttétel lineáris konvergenciát biztosít.
=== Tétel(3) ===
Ha <math> f\in\mathcal{C}^{(m)}_{\left[a,b\right]}</math> és <math> f'\left(x^*\right)=\cdots=f^{\left(m-1\right)}\left(x^*\right)=0</math> de <math> f^{(m)}\left(x^*\right) \ne 0 </math> és az <math> x_{k+1}:=f\left(k\right)</math> [[sorozat (matematika)|sorozat]] [[konvergens]] akkor a konvergenciája m-edrendű.
=== Bizonyítás ===
Írjuk fel <math>f</math>-nek az <math>x^*</math> középpontú Taylor-polinomját az m-edrendű maradéktaggal.<br />
<math>f\left(x\right)=f\left(x^*\right)+f'\left(x^*\right)\left(x-x^*\right)+\cdots+\frac{f^{(m-1)}\left(x^*\right)}{\left(m-1\right)!}\left(x-x^*\right)^{m-1}+\frac{f^{(m)}\left(\xi\right)}{m!}\left(x-x^*\right)</math>,ahol <math> \xi\in\left(x,x^*\right)</math>vagy <math>\left(x^*,x\right)</math>.<br />
Mivel a megfelelő deriváltak 0-k,ezért <math>f\left(x\right)=f\left(x^*\right)+\frac{f^{(m)}\left(\xi\right)}{m!}\left(x-x^*\right)^{m}</math>.<br />
Az <math> x=x_k</math> helyen és <math>x^*=f\left(x^*\right)</math> beírásával:<br />
<math>f\left(x_k\right)=x_{k+1}=x^*+\frac{f^{(m)}\left(\xi\right)}{m!}\left(x-x^*\right)^{m}</math> <br />
<math>\left|x_{k+1}-x^*\right|=\frac{\left|f^{(m)}\left(\xi\right)\right|}{m!}\left|x_k-x\right|^{p}\le\frac{M_{m}}{m!}\left|x_k-x^*\right|</math>,
ahol <math> M_{m}=max_{\xi \in\left[a,b\right]}\left|f{(m)}\left(\xi\right)\right|</math> innen látszik az m-edrendű konvergencia.
=== Következmény ===
Ha <math>f:\left[a,b\right]\mapsto\left[a,b\right]</math> kontrakció és<math>f'\left(x^*\right)=\cdots=f^{(m-1)}\left(x^*\right)=o </math> de <math> f{(m)}\left(x^*\right)\ne 0 </math> akkor <br />
1.<math> \exist ! x^*\in \left[a,b\right]</math> <br />
2.<math> \forall x_0\in\left[a,b\right]</math>-re az <math>x_{k+1}=f\left(x_k\right)</math> sorozat m-edrendeben konvergál <math>x^*</math>-hoz.<br />
3.<math>\left|x_{k+1}-x^*\right|\le\frac{M_m}{m!}</math>.
 
 
== Alkalmazások ==
 
===„Beragadt” koszinuszgomb===
 
A Banach-féle fixponttétel érdekes közvetlen alkalmazása a következő feladat: mi történik, ha egy tetszőleges számra a számológéppel egymás után sokszor alkalmazzuk a [[koszinusz]] függvényt?
Az egyik érdekes dolog, mely magyarázható a fixpontokkal kapcsolatos tételekkel is; az, hogy mit tapasztalunk, ha a számológépen egy valós számból kiindulva ismételten megnyomjuk - például - a [[koszinusz|cos]] gombot (a koszinusz helyett pl. a négyzetgyökfüggvényre is kipróbálható)? Szaknyelven szólva, hogyan viselkedik egy egyváltozós (és valós-valós) függvény [[iteráció]] hatására?
Legyen ''x''<sub>0</sub> tetszőleges valós szám, cos ''x''<sub>0</sub> ekkor már [-1,1] intervallumba esik. Ezen az intervallumon a koszinusz kontrakció, lévén a deriváltja abszolútértékének a korlátja sin 1 < 1, így létezik fixpontja. A fixponttétel bizonyításakor használt sorozat épp a koszinusz iterálása, amiről beláttuk, hogy koszinusz fixpontjához tart, így bármely számról is indulunk a koszinusz gomb kitartó nyomkodásával a cos ''x''=''x'' egyenlet egyetlen gyökét közélítjük.
 
A matematika nyelvén megfogalmazva ez a következőt jelenti: jelölje <math> x_{n} </math> azt a [[sorozat (matematika)|sorozatot]], amelyre:<br />
<math> x_{1}=\cos x </math> és (ha n>1) <math> x_{n}=\cos x_{n-1}</math>.<br />
 
Először belátjuk , hogy ha az <math> x_{n}</math> sorozat tart valahová, akkor az csakis a koszinuszfüggvény fixpontja lehet, ugyanis ha <math> \lim_{n \to \infty}x_{n}\rightarrow x </math> akkor <math> \lim_{n \to \infty}x_{n-1}\rightarrow x </math> így <math>\cos x </math> [[folytonos]]sága miatt és a sorozat megadása alapján,tehát <math> \lim_{n \to \infty}x_n= \lim_{n \to \infty}\cos x_{n-1}</math> ami éppen azt jelenti,hogy <math>x=\cos x</math> így valóban ha <math>x_n </math> tart valahová, akkor az csak a fixpontja lehet.
 
Most már csak azt kell belátnunk,hogy <math>x_n </math> konvergens. Ehhez elég ha <math> \left|x_n-x^*\right|\rightarrow 0 </math> tetszőleges <math>x_0</math>-ra (ahol <math>x^*</math> a feltételezett hatáérték).<br />
 
Ehhez felhasználjuk a [[sorozat (matematika)|sorozat]] megadását és azt a [[Lagrange]]-középértéktételből adódó állítást, hogy tetszőleges <math>x,y\in\mathbb{R}</math>-re <math>\left|\cos x -\cos y\right|\le \left|x-y\right|</math>.<br />
Tehát <math>\left|x_n-x^*\right|=\left|\cos x_{n-1} -\cos x^*\right|\le c\cdot\left|x_{n-1}-x^*\right|=\left|\cos x_{n-2}-x^*\right|\le c^{2}\cdot\left|x_{n-2}-x^*\right|\le \cdots \le c^{n-1}\left|x_1-x^*\right|</math> <br />
Így <math>\lim_{n \to \infty}\left|x_n-x^*\right|\rightarrow 0 </math> mert <math>0\le c \le 1</math>.<br />
 
===Pozitív számnak és reciprokának sorozatos átlagolása===
 
A következő alkalmazás is egy sorozat határértékének megállapítására szolgál.<br />
Legyen a sorozat a következőképpen definiálva:<math> x_0 > 0,x_{n+1}=\frac{x_n +\frac{1}{x_n}}{2}</math>.<br />
 
Először is be kell látni, hogy a sorozat konvergens,amit az azzal az analízisből jól ismert tétellel bizonyítunk, miszerint ha egy sorozat monoton csökken, és alulról [[korlátos]], akkor [[konvergens]]. A monoton csökkenés egyszerűen adódik az <math> f(x)=\frac{x+\frac{1}{x}}{2} </math> [[Függvény (matematika)|függvény]] vizsgálatából, a korlátosság pedig a [[számtani-közép]] és a [[mértani-közép]] közötti egyenlőtlenségből (így alsó korlátja az 1). Tehát konvergens, így az első bizonyítás szerint csak fixponthoz tarthat, tehát a határértékét a <math> A=\frac{A+\frac{1}{A}}{2}</math> [[egyenlet]] adja, amiből <math>A=1</math> következik, tehát [[határérték]]e az 1.
 
== Lásd még ==
[[Brouwer-féle fixponttétel]]
 
== Felhasznált jegyzet ==
 
==Lásd még==
Analízis 1. előadásjegyzet Math Bsc BME 2008/2009<br />
*[[Fixponttételek]]
Feladatmegoldó szeminárium 2. gyakorlat anyaga Math Bsc BME 2008/2009<br />
*[[Brouwer-féle fixponttétel]]
http://www.ttk.pte.hu/matek/numanal/ttk_elemei/jegyzet/elte/03ea.pdf
 
==Források==
== Ajánlott,témához kapcsolódó anyagok ==
*Rudin, W. : A matematikai analízis alapjai; Műszaki Könyvkiadó, 1978
{{források}}
*Komornik Vilmos: Valós analízis előadások, TypoTEX, 2003
* Járai Antal: Modern alkalmazott analízis,Typotex kiadó,2007.
* Komornik Vilmos: Valós analízis előadások,Typotex kiadó,2003.
 
{{DEFAULTSORT:Banachfixponttetele}}