%\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)<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
{\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).

