Teknillinen korkeakoulu Apiola Matematiikka

Mat-1.414 Matematiikan peruskurssi V2 kevät 2001

http://www.math.hut.fi/teaching/v/3/H/

Laskuharjoitus 2 (viikko 4–5 , 29.1 – 2.2.)

Alkuviikko (AV), ke 31.1.

1. Ratkaise sopivalla kiintopisteiteraatiolla seuraavat yhtälöt (sopivalla tarkkuudella):

(a) x cosh x = 1, kaikki reaalijuuret.

(b) Määritä yhtälön tan x = x pienin positiivinen juuri. Kirjoita yhtälö muotoon x = π + \overline{arctan} x (miksi?)

(c) sin x = e^{−x}

2. Määritellään jono (x_{n}) rekursiivisesti näin: x_{0} = 3, x_{n+1} = \sqrt{15 + 2x_{n}}, n = 0, 1, …. Osoita, että ∃s = lim_{n→∞} x_{n} ja määritä s. Suorita tehtävä “näkemällä” se kiintopisteiteraationa, määrittämällä kiintopisteet ja soveltamalla kiintopistelausetta “attraktiivisen kiintopisteen” ympäristössä.

3. Olkoon g(x) = 3^{−x}, x ∈ [0, 1]. Totea, että kiintopistelauseen oletukset eivät aivan toteudu tällä välillä. Osoita siitä huolimatta, että g:llä on yksikäsitteinen kiintopiste välillä [0, 1]. (Ei siinä muuta kuin yksikäsitteisyyspuolessa vetoat monotonisuuteen, ao. erotusfunktio on pienenevä.)

Osoita sitten, että kiintopisteiteraatio suppenee kaikilla lähtöarvoilla x_{0} ∈ [0, 1], vaikka siis lähtöarvo olisi kiintopistelauseen kannalta “kielletyllä alueella”. Tässä on suurena apuna kuva (“cobweb”- piirros), josta heti näet, mitä tapahtuu pahimmassa tapauksessa, sitten jo pääsetkin kiintopistelauseen alueelle.

4. Kiintopisteiteraatiota sovelletaan funktioon g(x) = 2 + (x − 2)^{4} alkaen pisteestä x = 2.5. Millä alkuarvoalueella suppenee? Mikä on suppenemiskertaluku?

5. (a) Osoita, että Newtonin iteraatio neliöjuuren laskemiseksi suppenee kaikilla positiivisilla alkuarvoilla kohti positiivista neliöjuurta (ja siis vastaavasti negatiivisilla kohti negatiivista).

(b) Muodosta Newtonin menetelmään perustuva algoritmi

\sqrt[3]{c}:n laskemiseksi.

Testaa laskemalla vaikkapa \sqrt[3]{3} hyväksi katsomallasi laskentatarkkuudella (Maplella 10 numeroa on oletus).

(c) Selvittele sekä graafisesti että kiintopistelauseen avulla, millä (reaalisilla) alkuarvon valinnoilla kuutiojuuren Newtonin iteraatio suppenee (ehkä peräti kaikilla?)

6. Olkoon f(x) = e^{x}−x−1. Totea, että x = 0 on f:n kaksinkertainen 0kohta. Osoita laskemalla, että Newtonin menetelmä suppenee vain lineaarisesti. (Ei varmaan ole työläs laskimellakaan, ellei Maplea satu olemaan käsillä.)

Loppuviikko (LV), pe 2.2.

Alkuarvoja on tietysti luontevaa hakea piirtämällä ja zoomaamalla tarpeen mukaan.

Opettelun alaisina olevien menetelmien lisäksi kannattaa kokeilla myös “purkitettua” koodia, Maple-funktiota fsolve.

1. Määritä yhtälön xe^{−x} = | sin(10x)| kaksi lähinnä 0:aa olevaa positiivista juurta 10:n numeron tarkkuudella. Huomaa, että itseisarvo on abs ja kaiken kukkuraksi Maple osaa derivoida itseisarvofunktion.

2. Määritä vanhan tutun yhtälön tan x = x lähinnä lukua 100 oleva juuri 10 numeron tarkkuudella. Newtonin menetelmällä.

Alkuarvaus täytyy valita varsin tarkasti, arvioi tätä alla olevalla epäyhtälöllä (s on juuri (likiarvo))

|s − x_{0}| < |\frac{2f′(s)}{f′′(s)}|

Selvitä, miksi tämä on järkevä arvio. Vihje: Perustuu alla olevaan virhekaavaan, tehtävän ehdon vallitessa voit osoittaa, että likimain pätee |ε_{n+1}| < |ε_{n}| (tässä otetaan n = 0).

3. Muodosta Newtonin iteraatio, jolla etsit \sqrt[3]{1}:iä kompleksitasossa. Tutki, mistäpäin tasoa lähdettäessä iteraatio suppenee mitäkin juurta kohti. Kokeile nyt ainakin lähtöpisteitä z_{0} = \frac{i}{2}, 0.4i, z_{0} = \frac{i}{3},

Visualisoi ohjeita2.html-tiedostossa (tulee) olevien ideoiden mukaisesti.

Tarkoituksena on antaa ensituntuma Newtonin menetelmään globaalisti, tarkasteltuna ja kompleksitasossa riehuttaessa.

4. Tarkastellaan Newtonin menetelmää polynomin f(x) = x^{3} − x tapauksessa.

(a) Piirrä paremmat kuvat kuin luennolla tapauksista, joissa esiintyy 2-pituinen sykli.

(b) Tee edellisen tehtävän ohjeissa esiintyvän newt3-proc:n kaltainen Maple-proseduuri ja visualisoi sen avulla sitä, mistä alkupisteistä lähtien Newtonin iteraatio suppenee mitäkin juurta kohti. (ohjeita2.html)

5. Tarkastellaan väestökasvumallia

N(t) = N_{0}e^{λt} + \frac{v}{λ}(e^{λt} − 1),

jossa otetaan huomioon biologisen lisääntymisen ohella myös maahanmuutto, jonka oletetaan tapahtuvan vakionopeudella v yksilöä vuodessa (netto). Oletetaan, että tietty populaatio on alunperin 10^{6} yksilöä, 435000 yksilöä muuttaa "maahan"1. vuoden aikana ja populaatiossa on 1564000 yksilöä vuoden lopulla. Määritä Newtonin menetelmällä luku λ tarkkuudella 10^{−4}. Käytä tätä λ:n arvoa ennustamaan populaation koko toisen vuoden lopussa, kun oletetaan maahanmuuttovauhdin säilyvän vakiona.

Voit tietysti kokeilla myös Maplen fsolve-komentoa.

6. Etsi yhtälön x^{8} − 36x^{7} + 546x^{6} − 4536x^{5} + 22449x^{4} − 67284x^{3} + 118124x^{2} − 109584x + 40320 = 0 välillä [5.5, 6.5] oleva juuri. Muuta x^{7}:n kerroin luvuksi −36.001 ja katso, mikä vaikutus sillä on juureen.

Voit rajoittua fsolve:n käyttöön.

Iterointilauseita ja muuta ohjetta

Tässä on alkuun sivulla ..L/newtiter.html oleva L^{A}TEX-teksti “TEX:itettynä”

0.1. Kiintopisteiteraatio

Funktion f kiintopiste on luku p, jonka funktio pitää paikallaan, ts. f(p) = p.

Kiintopisteen etsiminen voidaan muuntaa funktion nollakohdan hakemiseksi ja kääntäen.

f(x) = 0⟺g(x) = x, kun määritellään g(x) = f(x) + x. Huom: apufunktio g voidaan valita mitä moninaisimmilla tavoilla, kuten vaikkapa g(x) = 10f(x) + x.

Kääntäen, jos tehtävämme on etsiä funktion f kiintopistettä, niin

f(p) = p⟺g(p) = 0, kun määrittelemme g(x) = f(x) − x.

Kiintopistemuodossa on helpompi analysoida juurenhakuproblematiikkaa.

Huom! Juurenhaku voidaan muuntaa mitä moninaisimmilla tavoilla yhtälön ratkaisuksi. Toiset tavat voivat olla täysin kelvottomia, toiset taas loistokkaita.

Esim: f(x) = 0

a) g(x) = x − f(x) b) g(x) = x + 3f(x) c) g(x) = x − \frac{f(x)}{f′(x)}

Huom! Jos g on jatkuva ja jos iteraatiolla muodostettu jono x_{n} = g(x_{n−1}) suppenee, niin p = lim_{n∞} x_{n} on g:n kiintopiste, sillä toisaalta

lim_{n→∞} x_{n} = p

ja toisaalta

lim_{n→∞} x_{n} = lim_{n→∞} g(x_{n−1}) = g( lim_{n→∞} x_{n−1}) = g(p)

funktion g jatkuvuuden takia.

Lause 0.1. (Kiintopistelause) Olkoon g ∈ C[a, b] ja g(x) ∈ [a, b]∀x ∈ [a, b], ts. g kuvaa välin [a, b] sille itselleen. Tällöin g:llä on kiintopiste välillä [a, b]. Jos lisäksi oletetaan, että g on derivoituva ja

|g′(x)| ≤ k ∀x ∈ [a, b],

missä k < 1, niin kiintopiste on yksikäsitteinen ja iteraatiojono x_{n} = g(x_{n−1}), n = 0, 1, … suppenee mielivaltaisella alkupisteen x_{0} valinnalla, x_{0} ∈ [a, b].

Tod:

(1) Olemassolo hoituu Bolzanon lauseella

Jos g(a) = a tai g(b) = b, on kiintopiste löytynyt. Oletetaan, että näin ei ole, eli g(a) ≠ a ja g(b) ≠ b. Oletuksemme mukaan täytyy silloin olla g(a) > a ja g(b) < b (muutenhan jompikumpi päätepiste kuvautuisi välin ulkopuolelle).

Määritellään apufunktio h(x) = g(x) − x. No nythän sitten g(a) > 0 ja g(b) < 0, joten Bolzano ⇒∃p ∈ [a, b] siten, että h(p) = 0, eli f(p) = p.

(2) Yksikäsitteisyys seuraa suoraan väliarvolauseesta: Jos olisi kaksi eri kiintopistettä p ≠ q välillä [a, b], niin

p − q = f(p) − f(q) = f′(ξ)(p − q),

joten saataisiin ristiriitainen epäyhtälö

|p − q| < k|p − q| < |p − q|.

(3) Suppeneminen seuraa epäyhtälöketjusta:

|x_{n} − p| = |g(x_{n−1}) − g(p)| = |g′(ξ)||x_{n−1} − p| ≤ k|x_{n−1} − p| ≤ … ≤ k^{n}|x_{0} − p|.

Koska 0 < k < 1, niin lim_{n→∞} x_{n} = p.

□

Esim.Luentoesimerkki. Yksikäsitteinen kiintopiste voi toki olla ilmankin lauseen ehtoja, se lienee tuiki ilmeistä, otetaan vain jokin jyrkästi nouseva funktio, kuten e^{x}. Kiintopisteiteraation suppeneminen on sitten kyllä eri juttu. Tällainen tapaus oli AV tehtävässä 3.

Newtonin menetelmän suppenemiskertaluku

Koska Newtonia vastaava iterointifunktio g toteuttaa "kivan ehdon": g′(s) = 0, on Taylorin mukaan: ε_{n+1} = −\frac{g′′(s)}{2}ε_{n}^{2} + O(ε_{n}^{3}).

Kun |ε| on pieni, on |ε_{n+1}| ≈ |\frac{f′′(s)|}{2|f′(s)|}ε_{n}^{2}