Olen jo jonkin aikaa pohtinut kiintopistemenetelmän suppenemisehtoa. Asiahan on tällä tavalla:
Kiintopisteiteraatio x_{n 1} = g(x_n) suppenee, jos valitaan iteraation alkuarvo joltain sellaiselta kiintopisteen sisältävältä väliltä, jossa aidosti |g'(x)| \leq k < 1.
(Tässä siis \leq on "pienempi tai yhtäsuuri kuin".)
Kysymykseni: Miksi derivaatan itseisarvolta valitaan yläraja k? Miksi ei riittäisi vaatia |g'(x)| < 1?
Yritin ensin konstruoida esimerkkifunktiota, jolla pätisi vain |g'(x)| < 1 ja jolla iteraatio ei suppenisi. Tällaisellahan täytyisi päteä kiintopisteessä x* ehdot g'(x) \neq 1 ja lim_{x -> x*} |g'(x)| = 1. En sitten kuitenkaan osannut muodostaa sellaista funktiota, jolla olisin osannut osoitaa iteraation hajaantuvaksi.
Sitten yritin tutkia lauseen todistusta, mutta minusta mikään siellä ei estä valitsemasta ykköstä aidoksi ylärajaksi.
On minulla sellainen kutina, että jokin patologinen tapaus käy vastaesimerkiksi, mutta en nyt sellaista vain keksi. Osaako joku auttaa?
Kiintopisteiteraatio x_{n 1} = g(x_n) suppenee, jos valitaan iteraation alkuarvo joltain sellaiselta kiintopisteen sisältävältä väliltä, jossa aidosti |g'(x)| \leq k < 1.
(Tässä siis \leq on "pienempi tai yhtäsuuri kuin".)
Kysymykseni: Miksi derivaatan itseisarvolta valitaan yläraja k? Miksi ei riittäisi vaatia |g'(x)| < 1?
Yritin ensin konstruoida esimerkkifunktiota, jolla pätisi vain |g'(x)| < 1 ja jolla iteraatio ei suppenisi. Tällaisellahan täytyisi päteä kiintopisteessä x* ehdot g'(x) \neq 1 ja lim_{x -> x*} |g'(x)| = 1. En sitten kuitenkaan osannut muodostaa sellaista funktiota, jolla olisin osannut osoitaa iteraation hajaantuvaksi.
Sitten yritin tutkia lauseen todistusta, mutta minusta mikään siellä ei estä valitsemasta ykköstä aidoksi ylärajaksi.
On minulla sellainen kutina, että jokin patologinen tapaus käy vastaesimerkiksi, mutta en nyt sellaista vain keksi. Osaako joku auttaa?
Vastaukset 19
Vanhimmat
En juuri nyt keksi vastaesimerkkiä, mutta tiedän kyllä mihin määritelmä perustuu.
Olkoon X metrinen avaruus.
Olkoon kontraktio funktio f:X-->X, jolle pätee d(f(x),f(y))
Mitä nopeasti vilkaisin tuota nkorpin antamaa lausetta, joka tunnetaan myös Banachin kiintopistelauseena, niin tämän todistuksessa käytetään geometrisen jonon suppenemista ja sen häntäosan pienenemistä Cauchyn jonon konstruoimiseen. Tämän lauseen todistus ei toimi, jos jostakin pisteestä lähtien voitaisiin konstruoida jono, jossa "peräkkäisten" kuvien etäisyys olisi aina aidosti pienempi kuin yksi, mutta kasvaisi koko ajan, koska Cauchyn jonoa ei tuon todistuksen keinoin pystytä konstruoimaan.
Tässä tuon lauseen todistus LaTeX:lla esitettynä:
http://planetmath.org/?op=getobj&from=objects&id=3581
Tarkoitin, että todistus ei toimi, jos
d(Tx,Ty)
Ymmärsimme tämän, mutta yritämme löytää konkreettista esimerkkiä, esim. reaaliluvuilla, jossa iteraatio, q:n lähestyessä vapaasti ykköstä, ei suppene.
Mitä tarkoittaa 'q:n lähestyessä vapaasti ykköstä'?
Jos tuo tarkoittaa samaa kuin omassa kommenttissani, niin ilmaisu tarkoittaa, että tuossa iteraatiossa q ei ole kiinteä luku avoimella välillä (0,1)
vaan voi vaihdella ts. kaikille x,y \in X on sellainen q \in (0,1), että
d(Tx,Ty)
Ilmeisesti tässä haetaan nyt takaa sitä, riittääkö vaatimus d(Tx,Ty) < d(x,y)?
Yksi vastaesimerkki on
T: [0,∞) -> [1,∞), T(x) = x 1/x
Mutta jos X on kompakti, niin d(Tx,Ty) ≤ q*d(x,y) jollain q
"Ilmeisesti tässä haetaan nyt takaa sitä, riittääkö vaatimus d(Tx,Ty) < d(x,y)?"
Ei ehkä. Antamallasi funktiolla ei ole kiintopistettä, joten on aika triviaalia, että kiintopisteiteraatio ei suppene. Vai enkö ymmärtänyt, mitä tarkoitit?
Haluaisin siis nähdä funktion g, jolla on seuraavat ominaisuudet:
(1) g:llä on kiintopiste,
(2) |g'(x)| < 1 (mutta ei |g'(x)|
Olisin tietysti voinut vähän paremmin syventyä ketjuun ennen kirjoittamista. Eihän tuolla tosiaan ole kiintopistettä ollenkaan.
Tässä joitakin ideoita. Toivottavasti niistä on jotain apua:
-Jos iteraatio pysyy välillä I, niin mitä pidemmälle iteraatiota viedään, niin sitä lähemmäksi kiintopistettä mennään, sillä kiintopisteelle x* on d(x*,x_n) < ... < d(x*,x_1) < d(x*,x_0), jos x_0 on piste, josta iteraatio aloitetaan ja JOS siis jono pysyy välillä I. Tuo ei siis tarkoita, että se menisi kiintopisteeseen, mutta jotain kai sekin, että lähellä pysytään. Sitä en ole tutkinut, meneekö se välttämättä aina kiintopisteeseen.
-Mieleen tuli, että jos iteraatio karkaa välin I ulkopuolelle, niin se voisi hajaantua. Esim. jos
f(x) = -0.5x, kun x ≥ 0 ja -x^2-0.5x, kun x
olet varmaan näin tehnytkin, mutta tuntematta asiaa juurikaan k.o. ehtohan selvästi viittaa siihen että jollain tapaa tasaisesti pitäisi aito epäyhtälö olla voimassa eli siis konstruoitava g' tietenkin lähestyy rajatta 1:tä x:n suhteen varmaan siis avoimella välillä.
ja olit ilmeisesti tehnyt juuri noin.
googlata vähän ja Esa Lappi esittää homman noin, mutta käyttää k:ta suppenemisen nopeuden arviointiin. Apiola sanoo vaan että g' < 1 tosin ei oo mitään todistuksia ja taitaa liittyä johonkin Maple harjoitustyöhön tms. Mutta saatat olla oikeassa.
... muistiinpanoista ilmenee, että ainakin reaaliluvuilla |f'| < 1, on riittävä ehto, jos todistukset ovat oikein: http://www.physics.arizona.edu/~restrepo/475A/Notes/sourcea/node21.html
Nimittäin 'Mean-value-theorem' antaa kiintopisteen reaaleilla aivan ilmaiseksi, ja ainoastaan pisteen ainutkertaisuus on todistettava.
Toisaalta, sivulta ilmenee myös se, että jos aiot käyttää iteraatiota approximointitarkoitukseen, ei iteraatiosta ole juuri mitään hyötyä jos |f'| yltää mielivaltaisen lähelle lukua 1. Nimittäin tällöin suppeneminen on mahdollisimman hidasta.
(Mitä pienempi k, sitä nopeampi suppeneminen, eli pienempi approximaatiovirhe.)
Sen sijaan jos hylkäämme Euklikisella normilla varustetut reaalit, ja siirrymme muuhunb täydelliseen metriseen avaruuteen, en ole lainkaan varma ettemmekö voisi löytää sopivaa vasta-esimerkkiä. Yritän vielä miettiä asiaa.
... alan epäillä nyt myös reaalitapausta. Nimittäin se kohta todistuksessa, jossa sanotaan että mistä tahansa alkupisteestä saadaan onnistunut iteraatio vaatii edelleen k < 1.
Hohhoijaa. No aion kyllä vielä selvittää asian.
Olisiko kyse siitä, että ehdolla |g´(x)|
... reaaliluvuille todistus osoittaa että on tasan yksi kiintopiste, kunhan |g'| < 1. (Tämä on myös intuitiivisesti selvää.)
Ainoa ongelma on osoittaa, että iteraatio suppenee ilman ehtoa |g'|
Reaaliluvuille tämä on kyllä ilmeistä.
Jostain mieleeni putkahti tietty optimointiongelma, jonka ratkaisemiseksi reaalilukuja laajennetaan ottamalla mukaan - ääretön. Liittyiköhän tämä duaaliprobleeman ratkaisun yksikäsitteisyyteen?
Mahtavaa pohdintaa teiltä, kiitos!
Alan ehkä jotenkin päästä asiasta jyvälle. Tai en itse asiasta, vaan siitä, mikä siinä hämää. Seuraava todistus on (merkintöjä vaille) Courantin ja Johnin Introduction to Calculus and Analysis 1:stä (se on muuten toisiksi pahanhajuisin matematiikan kirja ikinä), mutta pikasilmäyksellä Nkorpin antamassa linkissä näyttiin käyttävän samaa tekniikkaa.
* * * * *
Kiintopisteiteraation suppenemisehto: Olkoon jatkuvasti derivoituvan funktion g kiintopiste x* välillä I. Iteraatio x_{n 1} = g(x_n) suppenee kohti kiintopistettä kaikilla välin I alkuarvoilla, jos |g'(x)| \infty, eli väite on todistettu.
* * * * *
Kritisoin siis aloitusviestissä sitä, että koko q on otettu mukaan väitteeseen. Eikö voisi yksinkertaisesti kirjoittaa |g'(x)| < 1, jolloin epäyhtälö (*) olisi yksinkertaisesti
|x_1 - x*| < |x_0 - x*|,
ja induktiivisesti jokaisella n pätisi
|x_n - x*| < |x_{n-1} - x*|?
Ilmeisesti tämä ei kuitenkaan toimisi, sillä |x_n - x*| ei välttämättä häviäisi, kun n -> \infty. Eli ollaan seuraavassa johtopäätöksessä:
Jos iteraatio suppeneekin myös yleisemmällä ehdolla |g'(x)| < 1, tämä ei ainakaan seuraa yo. todistuksesta.
Jään siis yhä vaille todistusta tai vastaesimerkkiä.
(Ja ettei kenellekään jää epäselväksi: En tarkoittanut, että yleisesti ottaen voisi olla q = 1 ja iteraatio silti suppenisi.)
Doctöör: "Olisiko kyse siitä, että ehdolla |g´(x)|
Tavallaan tässä todistetaan Contraction Mapping Teoreeman erikoistapausta reaaliluvuille.
Reaaliluvuille on selvää, että |g'|