%\documentclass[10pt,a4paper]{book} % testataan pienemmällä (10) \documentclass[finnish,12pt,twocolumn]{article} %\documentclass[12pt,a4paper]{book} \usepackage[finnish]{babel} \usepackage[latin1]{inputenc} % ISO Latin 1 -skandit % \usepackage[cp850]{inputenc} % PC-skandit \usepackage[T1]{fontenc} \usepackage[dvips]{epsfig} \usepackage{makeidx,theorem,float} \usepackage{amssymb,multicol} %\usepackage{amstex,amssymb,multicol} %\usepackage{amsmath} \usepackage{boxedminipage} \usepackage{/home/apiola/tex/skk} %\documentclass[finnish,12pt,twocolumn]{article} \usepackage{/home/apiola/tex/v2harj} %\usepackage{/home/apiola/tex/skk} \usepackage{makeidx,theorem,float} \include{/home/apiola/tex/defs} %\include{defs} \begin{document} %\vspace{0.2cm} %\begin{verbatim} %\end{verbatim} \harjoitus{2}{4--5}{29.1 -- 2.2.} \subsubsection*{Alkuviikko (AV), ke 31.1.} \begin{enumerate} \item 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=\pi + \overline{\arctan}\ \ x $ (miksi?) (c) $\sin x = e^{-x}$ \item Määritellään jono $(x_n)$ rekursiivisesti näin: $x_0=3,\\ x_{n+1}=\sqrt{15+2 x_n}, n=0,1,\ldots .$ Osoita, että $\exists s=\lim_{n \to \infty} 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ä. \item %BF s. 49 (b), luentosivu 9.5 Olkoon $g(x)=3^{-x}$, $x\in [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\in [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. \item %3 Kiintopisteiteraatiota sovelletaan funktioon $g(x)=2+(x-2)^4$ alkaen pisteestä $x=2.5$. Millä alkuarvoalueella suppenee? Mikä on suppenemiskertaluku? \item (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 $\root 3 \of c$:n laskemiseksi. %(b) $\root n \of c$:n laskemiseksi. Testaa laskemalla vaikkapa $\root 3 \of 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?) \item Olkoon $f(x)=e^x-x-1$. Totea, että $x=0$ on $f$:n kaksinkertainen 0-kohta. Osoita laskemalla, että Newtonin menetelmä suppenee vain lineaarisesti. (Ei varmaan ole työläs laskimellakaan, ellei Maplea satu olemaan käsillä.) \end{enumerate} \subsubsection*{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 {\tt fsolve}. \begin{enumerate} %\item %Kirjoita Maple-proc, joka toteuttaa bisektioalgoritmin. %Riittää sekin, että teet Maple skriptin, aloita joka tapauksessa sillä. \item Määritä yhtälön $x e^{-x}=|\sin(10 x)|$ kaksi lähinnä 0:aa olevaa positiivista juurta $10$:n numeron tarkkuudella. Huomaa, että itseisarvo on {\tt abs} ja kaiken kukkuraksi \maple\/ osaa derivoida itseisarvofunktion. \item 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{2 f'(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 $|\varepsilon_{n+1}| < |\varepsilon_{n}| $ (tässä otetaan $n=0$). %\item %Sopivia teht. BF s. 44 - > %Maple-ws:t: pc: k01\iter.mws (myös animaatio) %\item %BF s. 51 Exa 3: eri iterointifunkioiden vertailua %\item %Harj. tehtäviä Fixed p: BF ss. 54 - 56 \item % Vrt. Scheinerman s. 336 Muodosta Newtonin iteraatio, jolla etsit $\root 3 \of 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.4 i$, $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. %Ensimmäinen arvelu voisi olla: Jos johonkin juureen suppenevasta %alkupisteestä siirrytään lähemmäs tätä %juurta, niin iteraatio suppenee edelleen samaa juurta kohti. %Toinen voisi olla: %Ensimmäinen arvelu voisi olla: %Iteraatio suppenee aina sitä juurta kohti, joka on %valittua alkupistettä lähimpänä. %No -- todellisuus osoittautuu paljon ``repaleisemmaksi''. %harj2apu.mws-työarkilla on määritelty newt3 ... \item 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 {\tt newt3}-proc:n kaltainen Maple-proseduuri ja visualisoi sen avulla sitä, mistä alkupisteistä lähtien Newtonin iteraatio suppenee mitäkin juurta kohti. (ohjeita2.html) \item%{Väestö} Tarkastellaan v\"aest\"okasvumallia $$N(t)=N_0e^{\lambda t}+{\frac{v}{\lambda}}(e^{\lambda t}-1),$$ jossa otetaan huomioon biologisen lis\"a\"antymisen ohella my\"os maahanmuutto, jonka oletetaan tapahtuvan vakionopeudella $v$ yksil\"o\"a vuodessa (netto). Oletetaan, ett\"a tietty populaatio on alunperin $10^6$ yksil\"o\"a, $435 000$ yksil\"o\"a muuttaa "maahan" 1. vuoden aikana ja populaatiossa on $1 564 000$ yksil\"o\"a vuoden lopulla. M\"a\"arit\"a Newtonin menetelm\"all\"a luku $\lambda$ tarkkuudella $10^{-4}$. K\"ayt\"a t\"at\"a $\lambda$:n arvoa ennustamaan populaation koko toisen vuoden lopussa, kun oletetaan maahanmuuttovauhdin s\"ailyv\"an vakiona. Voit tietysti kokeilla myös Maplen {\tt fsolve}-komentoa. \item Etsi yhtälön $x^8-36 x^7+546 x^6 -4536 x^5 + 22449 x^4 - 67284 x^3 + 118124 x^2 -109584 x + 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 {\tt fsolve}:n käyttöön. \end{enumerate} \subsection*{Iterointilauseita ja muuta ohjetta} Tässä on alkuun sivulla {\tt ..L/newtiter.html} oleva \LaTeX-teksti ``\TeX:itettynä'' \subsection{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 \iff g(x)=x$, kun määritellään $g(x)=f(x)+x$. Huom: apufunktio $g$ voidaan valita mitä moninaisimmilla tavoilla, kuten vaikkapa $g(x)=10 f(x)+x$. Kääntäen, jos tehtävämme on etsiä funktion $f$ kiintopistettä, niin $f(p)=p \iff g(p)=0$, kun määrittelemme $g(x)=f(x)-x$. Kiintopistemuodossa on helpompi analysoida juurenhakuproblematiikkaa. {\bf Huom!} Juurenhaku voidaan muuntaa mitä moninaisimmilla tavoilla yhtälön ratkaisuksi. Toiset tavat voivat olla täysin kelvottomia, toiset taas loistokkaita. {\bf Esim:} $f(x)=0$ a) $g(x)=x-f(x)$ \quad b) $g(x)=x+3 f(x)$ \quad 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\infty}x_n$ on $g$:n kiintopiste, sillä toisaalta $$ \lim_{n\to\infty }x_n = p$$ ja toisaalta $$\lim_{n\to\infty }x_n = \lim_{n\to \infty}g(x_{n-1})= g(\lim_{n\to \infty}x_{n-1})= g(p) $$ funktion g jatkuvuuden takia. {\lause[Kiintopistelause] Olkoon $g\in C[a,b]$ ja $g(x)\in [a,b] \forall x\in [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)| \leq k \ \ \forall x\in [a,b],$$ missä $k<1$, niin kiintopiste on yksikäsitteinen ja iteraatiojono $x_n=g(x_{n-1}), n=0,1,\ldots$ suppenee mielivaltaisella alkupisteen $x_0$ valinnalla, $x_0\in [a,b]. $ Tod: (1) Olemassolo hoituu {\em Bolzanon lauseella} Jos $g(a)=a$ tai $g(b)=b$, on kiintopiste löytynyt. Oletetaan, että näin ei ole, eli $g(a)\ne a$ ja $g(b)\ne b$. Oletuksemme mukaan täytyy silloin olla $g(a)>a$ ja $g(b)0$ ja $g(b)<0$, joten {\em Bolzano} $\implies \exists p\in [a,b]$ siten, että $h(p)=0$, eli $f(p)=p$. (2) Yksikäsitteisyys seuraa suoraan väliarvolauseesta: \\ Jos olisi kaksi eri kiintopistettä $p\ne q$ välillä $[a,b]$, niin $$p-q=f(p)-f(q)=f'(\xi)(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'(\xi)||x_{n-1}-p| \leq k|x_{n-1}-p| \leq \ldots \leq k^n |x_0-p|.$ Koska $0 < k < 1$, niin $\lim_{n\to\infty}x_n = p .$ \loppu } \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. %{\lause[Virhearvio] %Jos $g$ toteuttaa kiintopistelauseen ehdot, niin %\begin{equation} %|x_n-p| \leq k^n \max\lbrace x_0 - a, b - x_0\rbrace %\end{equation} %\begin{equation} %|x_n-p| \leq \frac{k^n}{1-k} |x_0 - x_1| \ \ \forall n \ge 1. %\end{equation} %{\bf Tod:} Samanhenkisesti kuin edellä, kts. \cite[s. 53]{na:BF} %%Kts. myös oma iso vihko s. 87 . %\loppu} %\subsubsection*{Stabiilisuus, attraktiivisuus} %Usein iteraatiojono ajatellaan dynaamiseksi systeemiksi ja $x$-muuttuja %ajaksi. %\maar{ %Kiintopistettä $p$ %sanotaan {\em attraktiiviseksi} (puoleensa vetäväksi) tai {\em stabiiliksi}, %jos on olemassa %sellainen $p$:n \ysto\/ $U_\epsilon(p)$, että $x_0\in U_\epsilon(p) %\implies x_n \to p$. %Tarkenna tätä (HubW): %{\em Repulsiivinen} eli {\em epästabiili}: %Löytyy \ysto\/, jonka kaikki alkupisteet johtavat hajaantuvaan iteraatioon. %Sitten on niitä, jotka eivät ole kumpaakaan. %\loppu} %Olkoon $p$ funktion $g$ kiintopiste. %On helppo nähdä, että %\begin{itemize} %\item %Jos $g'(p)<1$, niin $p$ on attraktiivinen. %\item %Jos $g'(p)>1$, niin $p$ on repulsiivinen. %\end{itemize} %Jos $g'(p)=1$, niin kumpi tahansa on mahdollinen. \subsubsection*{Newtonin menetelmän suppenemiskertaluku} Koska Newtonia vastaava iterointifunktio $g$ toteuttaa "kivan ehdon": $g'(s)=0$, on Taylorin mukaan: $\varepsilon_{n+1}=-\frac{g''(s)}{2}\varepsilon_n^2 + O(\varepsilon_n^3)$. Kun $|\varepsilon|$ on pieni, on $|\varepsilon_{n+1}|\approx |\frac{f''(s)|}{2 |f'(s)|}\varepsilon_n^2 $ \end{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \item Wilkinsonin polynomin $(x-1)(x-2)...(x-20)$ kertoimet saadaan \matl-komennolla {\tt poly(1:20)}. Suorita kirjan s. 52 esitetyllä menetelmällä analyysi $x^{20}$:n kertoimen häiriön vaikutuksesta juuriin $r=1$ ja $r=16$. Mikä juurista $1,16,20$ on häiriöalttein. Vertaa tuloksiasi numeeristen kokeilujen antamiin arvioihin (vrt. tietokoneharj. teht. 1).