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?
kiintopisteiteraation suppeneminen
19
1253
Vastaukset
- nkorppi
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))- Erdös
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 - Erdös
Erdös kirjoitti:
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=3581Tarkoitin, että todistus ei toimi, jos
d(Tx,Ty) - nkorppi
Erdös kirjoitti:
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.
- jukepuke
nkorppi kirjoitti:
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ä'?
- Erdös
jukepuke kirjoitti:
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) - jukepuke
Erdös kirjoitti:
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 - ash
jukepuke kirjoitti:
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)| - jukepuke
ash kirjoitti:
"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
- vaan hatusta
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ä.
- luin uudestaan tuon
ja olit ilmeisesti tehnyt juuri noin.
- nyt vielä
luin uudestaan tuon kirjoitti:
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.
- nkorppi
... 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.- nkorppi
... 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.
- Doctöör
Olisiko kyse siitä, että ehdolla |g´(x)|
- nkorppi
... 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'| - Doctöör
nkorppi kirjoitti:
... 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?
- ash
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)|- nkorppi
Tavallaan tässä todistetaan Contraction Mapping Teoreeman erikoistapausta reaaliluvuille.
Reaaliluvuille on selvää, että |g'|
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Työsuhdepyörän veroetu poistuu
Hallituksen veropoliittisen Riihen uutisia: Mitä ilmeisimmin 1.1.2026 alkaen työsuhdepyörän kuukausiveloitus maksetaan844333Ruumis kanavassa
Mikä juttu eilen ollut poliisit palokunta ambulanssi ja ruumis auto sillalla. Tekikö itsemurhan313222- 1712601
- 142026
Onko tässä paljon lääkettä..
Keski-ikäselle 43v Ketipinor 100mg Brintellix 10mg Venlafaxin 75mg Xanor 1mg Propral 40mg Xatral CR 10mg Esomepratsol 42281492Ei mitään menetettävää
Arvostin ja kunnioitin sun tunteita. Menit nyt liian pitkälle. Mulla ei ole enää mitään menetettävää ja sä tulet sen huo1631376Oi! Jorma Uotinen ja Helena Lindgren paljastivat yllätysuutisen: "Rakkaudella"
Professori, tanssija, koreografi, Tanssii Tähtien Kanssa -tuomari Jorma Uotinen ja Suomen meikkitaiteen pioneeri, laulaj131160- 741009
Pakko tulla tänne
jälleen kertomaan kuinka mahtava ja ihmeellinen sekä parhaalla tavalla hämmentävä nainen olet. En ikinä tule kyllästymää38960Riittäisi juoruakkoille puhumista tässä kylässä
On mennyt mahottomaksi touhut. Taksi renki kuskaa akkaansa töihin lienekkö mitään lupaa yrittäjältä tähän touhuun. Kylän13872