\documentclass[finnish,11pt,twocolumn]{article}
\usepackage{/home/apiola/tex/v2harj}
\usepackage[dvips]{epsfig}
%\include{/home/apiola/tex/defs}
%\usepackage{v23harj}
%\include{defs}
\def\abs#1{\vert #1\vert}      
\def\norm#1{\Vert #1\Vert}      
\def\innerp#1{\langle #1 \rangle}
\def\vnormone#1{\sum_k \vert #1_k \vert}
\def\vnorminf#1{\max_k \vert #1_k \vert}
\def\mnormone#1{\max_j \sum_i \vert#1_{ij}\vert}
\def\mnorminf#1{\max_i \sum_j \vert#1_{ij}\vert}
\def\rv{\hfill\break}
\def\matl{{\sc Matlab}}
\def\maple{{\sc Maple}}
%\def\Arg#1{\textit{Arg} #1}
\def\Arg{{\textit{Arg}}\ \ }
\def\erf{{\textit{erf}}\ \ }

\begin{document}

%\vspace{0.2cm}
%\begin{verbatim}
%\end{verbatim}

\harjoitus{9}{13--14}{27.3 ,4--5.4.2002}

Ke-harj. ennen p��si�ist�, to ja pe j�lkeen.

{\bf Ohjetiedostoja, ty�arkkkeja, linkkej�:}

harj9ohje.mws (ehk� H9.html) ja lopussa olevat ohjeet sek� n�m�:
\begin{verbatim}
http://www.math.hut.fi/teaching/v/2/02/L/LSQ.html (.mws)
http://www.math.hut.fi/teaching/v/2/02/L/SD.html/ (.mws)
http://www.math.hut.fi/teaching/v/2/02/L/newtopt.html (.mws)
\end{verbatim}
%Kaikista on my�s vastaava {\tt .mws} .
% 1.4.2000:  281,421,906 

\subsection*{Alkuviikko (AV)}


\begin{enumerate}

\item %1
Sovita PNS-suora dataan {\tt [[2,5],[3,9],[4,15],[5,2]] }. 
Kirjoita normaaliyht�l�t muotoon $C^T C a = C^T y$ ja ratkaise.
(Jaksat varmasti ratkaista k�sin $2\times 2$-yht�l�systeemin).

Piirr� datapisteet
ja suora.

T�m� on siis puhdas k�sinlasku, 



\item %2 %Ad s. 813 Exa 1
Suorita yksi askel Newtonin menetelm�� harj.8 AV funktion
$f(\V{x})=2(x_1^2+x_2^2)+x_1x_2 -5(x_1+x_2)$ minimoimiseksi.

Alkupisteeksi voit valita saman $\V{p_0}=[1 -2]^T$ tai mink� tahansa.
Minimin pit�isi l�yty� yhdell� askeleella. Miksi? 




\item %3
Tarkastellaan yht�l�ryhm�� 
\[
\begin{cases}
             x^2 -xy + 2y^2=10 \\
             x^3 y^2 = 2 
\end{cases} 
\]
Kirjoita Newtonin menetelm�n askel t�lle systeemille.
(Huom! Lineaarisen yht�l�systeemin ratkaisua ei kannata kirjoittaa
symboliseen muotoon, vaikka se $2\times 2$-tapauksessa olisikin yksinkertaisen Jakobiaanin tilanteessa mahdollista.)

Hahmottele k�yr�t ja l�hde jotain leikkauspistett� l�hell� olevasta 
iteroimaan Newtonilla. Yksi askel k�sin laskettuna riitt��.

Saat mielell��n jatkaa Maplella (mutta ei ole pakko).



\item %4
Tasossa liikkuvan 2-osaisen robotin k�sivarren OAB piste O on kiinnitetty 
origoon. Pisteess� A on nivel, jolla varren osat OA ja AB on kiinnitetty
toisiinsa.
Varren OA ja x-akselin v�linen kulma olkoon $\alpha$ ja varren OA ja AB 
v�linen kulma olkoon $\beta$.

Olkoot varsien pituudet $d_1$ ja $d_2$. Lausu pisteen B koordinaatit 
ohjauskulmien $\alpha$ ja $\beta$ avulla.

Robottia ohjattaessa halutaan annettua pistett� vastaavat ohjauskulmien 
arvot, ts. edell� lasketun funktion k��nteisfunktion arvot.

Kirjoita Newtonin menetelm�n askel teht�v�n ratkaisemiseksi. Siis l�ht�pisteen� jokin robotin k�den "ulottumisalueeseen" kuuluva piste.
(Jatkoa LV)




%\item
%Tarkastellaan yht�l�ryhm�� 
%\[
%\begin{cases}
%             1+x^2-y^2+e^x\cos y=0 \\
%             2xy+e^x\sin y=0 
%\end{cases} 
%\]

%Kirjoita Newtonin menetelm�n iteraatioaskel t�lle systeemille.
%(Jatkoa LV-teht�v�ss�)


\end{enumerate}

Teht�v�t ovat loppuviikkopainotteisia, erityisesti, koska k�sinlasku
ei juuri ole mielek�st�. K�ytet��n ke harjoituksen loppuaika
LV-teht�vien aloitteluun ohjatusti.

%%%%%%%%%%% AV:n loppu %%%%%%%%%%


\subsection*{Loppuviikko (LV)}

\begin{enumerate}
\item %1
Joulukuun 1--28 p�iv�n� 1981 aurinko laski {\it Lund}:ssa klo 15.30:n ja 
15.45:n v�lill� seuraavan taulukon mukaisesti, miss� x tarkoittaa p�iv��
($1 \leq x \leq 28$) ja y minuuttim��r�� klo 15.30:n j�lkeen, jolloin aurinko
laski. 

%\vfill\eject

\begin{verbatim}
     x     y     x     y

     1     8   19-21   3
     2     7   22-23   4
     3     6    24     5
    4-5    5    25     6
    6-7    4   26-27   7
    8-9    3    28     7
   10-18   2
\end{verbatim}

Data voidaan esitt�� varsin hyvin 2. asteen polynomilla. M��rit� kertoimet 
$a_0,a_1,a_2$, piirr� data ja polynomi. 
Min� p�iv�n� auringonlaskuaika saavuttaa
minimins� mallin mukaan. (Kirjasta {\it Fr�berg}: Numerical Analysis 1985)


\item %2
Sovita eriasteisia PNS-polynomeja USA:n v�est�laskenta- (Census)-dataan. (Luvut tietysti "megahenkil��")

\begin{tabular}{|c|c|c|c|c|c|c|}\hline
%\multicolumn{7}{|c|} \\ \hline
  Vuosi & 1940  & 1950  & 1960 & 1970 & 1980 & 1990 \\ \hline
  V�ki & 132.165 &151.326 &179.323 &203.302 & 226.542 & 249.633  \\ \hline
\end{tabular}.

Piirr� datapisteet ja PNS-polynomit.
Mik� n�ytt�� j�rkevimm�lt� ja mik� v�hiten j�rkev�lt� mallilta?

Mik� polynomi antaa parhaan arvon vuodelle $2000$ ?
( kts. {\tt  http://www.census.gov/main/www/cen2000.html} )

(Huomaa, ett� normaaliyht�l�ratkaisulla on taipumusta h�iri�alttiuteen, voit
joutua lis��m��n laskentatarkkuutta. Parempi tapa olisi skaalata data. )



\item %3
Tutki harj8lv teht�v�n 5 funktion 
$f(x,y)=e^x(4x^2+2y^2+4xy+2y+1)$
��riarvoja.

(Vaihteluksi voit yht� hyvin ottaa vaikkapa funktion
$f(x,y)=\frac{1}{2} (x^4 -16x^2 + 5x + y^4-16 y^2 + 5y) $)

Nyt aiheena on erityisesti Newtonin menetelm�. Vertaa Newton- ja SD-menetelmien
reittej� ja tee my�s taulukot, joista n�kyy reittipisteet ja funktion arvo niiss�. 
(Vrt. {\tt harj9ohje.mws/html})

%Sis�llyt� Hessen matriisin posdef/negdef/indef-tarkistus.

Voit vertailun vuoksi testata my�s
 {\tt NonlinearProgramming}-funktioita.

%\item
%Jokin LP-teht�v� 


\item %4
Palataan AV yht�l�ryhm��n (mutta muutettiin kuitenkin)
\[
\begin{cases}
             1+x^2-y^2+e^x\cos y=0 \\
             2xy+e^x\sin y=0 
\end{cases} 
\]

Piirr� kuvaajat {\tt implicitplot}:lla ja etsi siit� sopivat l�ht�arvot.

Suorita Maplen avulla Newtonin iteraatioita ainakin jostakin
l�ht�arvosta.

Tee taulukko, jossa on sarakkeina: iteraatiokierros, reittipiste,
funktion arvo siin�.

Piirr� reitin kuva.
(kts. harj9ohje.mws)

Kokeile lopuksi Maplen {\tt fsolve}-komentoa.

\item %5
Jatkoa robottiteht�v��n.

Olkoon $d_1=6$ ja $d_2=5$. M��rit� Newtonin menetelm�ll� ohjauskulmat,
joilla p��st��n pisteeseen $(10,4)$, kun alkuarvoiksi otetaan $\alpha=0.7$
$\beta=0.7$ Onko ratkaisu 1-k�sitteinen.

Mit� tapahtuu, jos joudutaan pisteeseen, jossa Jakobin determinantti = 0 ? 

``Vapaaehtoinen'' lis�piirre:
Tee Newtonin iteraatiosta animaatio, joka n�ytt�� k�sivarren asennon kullakin
iteraatioaskeleella. Samantien voit vaihdella kohdepistett� ja alkuarvoja.

%Mik� on k��nteisfunktion m��rittelyjoukko (robotin toiminta-alue)?


\end{enumerate}



\subsection*{Ohjeita}


\subsubsection*{Newton ja Newton}

{\bf Newton optimointiin}

Etsit��n funktion $f$ minimi� $\R^n$:ss�: \\
Alkupiste $x_0$. \\
M��r�t��n $h$ ehdosta $H_f(x_0)h=-\nabla f(x_0)$ \\
P�ivitys: $x_1=x_0+h$ \\
Sitten iteroidaan.

{\bf Huom!} Toimintavarmuus on olennaisesti parempi, jos $H_f(x_n)$ on
positiividefiniitti ``nykypisteess�'' $x_n$.

{\bf Newton yht�l�systeemiin}

Vektoriarvoinen funktio $f:\R^n \to \R^n$. Etsit��n 0-kohtaa, ts. vektoria
$x$, joka toteuttaa $n\times n$-yht�l�systeemin $f(x)=0$. \\
Alkupiste $x_0$. \\
M��r�t��n $h$ ehdosta $J_f(x_0) h = -f(x_0)$ \\
P�ivitys: $x_1=x_0+h$ \\
Sitten iteroidaan.

Huom: $J_f(x_0)$ tarkoittaa $f$:n Jacobin matriisia 
$(\frac{\partial f_i}{\partial x_j})_{i,j}$, miss� $f_i$ on $f$:n $i$:s
komponenttifunktio (ei mit��n tekemist� osittaisderivaatan kanssa). 

Huom! Jos Jakobiaani tulkitaan derivaataksi ja kirjoitetaan kaava
k��nteismatriisin avulla, saadaan t�sm�llinen analogia yhden muuttujan
Newtoniin.

\subsubsection{Maple-kirjasto optimointiin}



\begin{verbatim}
libname:= /p/edu/mat-1.414/maple/,libname; (kannattaa sijoittaa  
                                           .mapleinit-tiedostoon.)
Sitten 
with(linalg): with(LinearAlgebra): with(NonlinearProgramming);
\end{verbatim}
Kts my�s:\\ 
\verb_ http://www.mapleapps.com/powertools/optimization/html/nlpdemo.html _






\end{document}


\begin{itemize}
\item

\item


\end{itemize}






\item %1
%\item
%M��rit� Lagrangen kertojamenetelm�ll� funktion $f(x,y)=x^3y^5$ maksimi suoralla
%$x+y=8$.

\item
M��rit� Lagrangen kertojamenetelm�ll� funktion 
$f(x,y,z)=x^2+y^2+z^2$ maksimi- ja minimiarvot kartion 
$z^2=x^2+y^2$ ja tason $x-2z=3$ leikkausellipsill�.

\item %1
Lanka, jonka pituus on $L$ leikataan (sis�lt�� my�s yhden p�tk�n
mahdollisuuden, jolloin oikeasti ei leikata) 
korkeintaan kolmeen p�tk��n ja jokainen
p�tk� taivutetaan neli�ksi. M��rit� neli�iden alojen summan maksimi ja minimi.


\item
Sovita PNS-suora dataan $(2,2),(5,4),(6,6),(9,9),(11,10)$
Piirr� datapisteet ja suora.

\item
Joulukuun 1--28 p�iv�n� 1981 aurinko laski {\it Lund}:ssa klo 15.30:n ja 
15.45:n v�lill� seuraavan taulukon mukaisesti, miss� x tarkoittaa p�iv��
($1 \leq x \leq 28$) ja y minuuttim��r�� klo 15.30:n j�lkeen, jolloin aurinko
laski. 

%\vfill\eject

\begin{verbatim}
     x     y     x     y

     1     8   19-21   3
     2     7   22-23   4
     3     6    24     5
    4-5    5    25     6
    6-7    4   26-27   7
    8-9    3    28     7
   10-18   2
\end{verbatim}

Data voidaan esitt�� varsin hyvin 2. asteen polynomilla. M��rit� kertoimet 
a,b,c, piirr� data ja polynomi. Min� p�iv�n� auringonlaskuaika saavuttaa
minimins� mallin mukaan. (Kirjasta {\it Fr�berg}: Numerical Analysis 1985)

%N�m� ovat kesken��n vaihtoehtoisia.

\item
Sovita eriasteisia PNS-polynomeja vanhaan kunnon census-dataan.

\begin{tabular}{|c|c|c|c|c|c|c|}\hline
%\multicolumn{7}{|c|} \\ \hline
  Vuosi & 1940  & 1950  & 1960 & 1970 & 1980 & 1990 \\ \hline
  V�ki & 132.165 &151.326 &179.323 &203.302 & 226.542 & 249.633  \\ \hline
\end{tabular}.


Kokeile eri muotoisia kantafunktioita (muista eri skaalaukset 
interpolaatioteht�vien yhteydess�).
(Huomaa, ett� normaaliyht�l�ratkaisulla on taipumusta h�iri�alttiuteen.)

\item
Tutustu ohjeiden mukaan numeerisiin optimointimenetelmiin, erityiseti
jyrkimm�n laskeuman, eli "steepest descent", eli gradienttimenetelm��n
ja Newtonin menetelm��n (sek� optim. ett� yht�l�syst.)
Implementoi Maplella sopiva versio/yhdistelm� ja testaa. Ohjeita 
implementointiin ja
sopivia testiesimerkkej� annetaan.

\item
\item
M��rit� Lagrangen kertojamenetelm�ll� funktion $f(x,y)=x^3y^5$ maksimi suoralla
$x+y=8$.

\item
M��rit� funktion $f(x,y,z)=x^2+y^2+z^2$ maksimi- ja minimiarvot kartion 
$z^2=x^2+y^2$ ja tason $x-2z=3$ leikkausellipsill�.

\item
Sama kuin edell� funktiolle $$f(x,y)=\frac{xy}{2+x^4+y^4}$$

\item
Maplessa on linalg-pakkauksessa funktiot eigenvectors ja hessian. Laske teht�vien 3 ja 4 tapauksessa Hessen matriisin ominaisarvot ja -vektorit.
Tee hypoteesi, jolla uskot voivasi p��tt�� ominaisarvojen merkkien avulla
KRP:n luonteen (tai sen, ettei luonteesta voi sanoa).

T�ydenn� n�iden teht�vien kuvia piirt�m�ll� ainakin johonkin KRP:een
ominaisvektorit.


\end{enumerate}

\subsubsection*{Esimerkkej� optimointiin ja ep�lin. systeemeihin}

\begin{enumerate}
\item 
$f(x,y)=e^x(4x^2+2y^2+4xy+2y+1)$

$f(x,y)=100(y-x^2)^2+(1-x)^2$  {\em Rosenbrockin banaanifunktio}

$f(x_1,x_2,x_3)=x_1^2+10x_2^2+100x_2^2$



\end{enumerate}

\item
Ohjetiedostossa ../H/ohjeita3.html on annettu USA:n v�est�laskentadataa 
vuosina $1940$ -- $1990$. Muodosta interpolaatiopolynomi ja laske sen avulla
arviot v�kiluvulle vuosina $1930, 1965, 2000, 2010$. 
Havainnollista kuvilla, joissa datapisteet ja interpolaatiopolynomi.
Tiedet��n, ett� vuoden 1930 lukema on $123 203 000$. Mit� arvelet
muiden arvojen tarkkuudesta? (Etsi jostain (Alta Vista) Census 2000-
arvo ja vertaa.)

\item %3
Tarkastellaan yht�l�ryhm�� 
\[
\begin{cases}
             x^2 -xy + 2y^2=10 \\
             x^3 y^2 = 2 
\end{cases} 
\]

Kirjoita Newtonin menetelm�n askel t�lle systeemille.
(Huom! Lineaarisen yht�l�systeemin ratkaisua ei kannata kirjoittaa
symboliseen muotoon, vaikka se $2\times 2$-tapauksessa olisikin yksinkertaisen Jakobiaanin tilanteessa mahdollista.)

Hahmottele k�yr�t ja l�hde jotain leikkauspistett� l�hell� olevasta 
iteroimaan Newtonilla. Yksi askel k�sin laskettuna riitt��.
(Jatkoa LV-teht�v�ss�)

\item
$z=x^3+y^3-3xy$

Onko ��riarvoa pist. (0,0) tai (1,1).


\item
$f(x,y)=1/x+1/y+\sin(x^2y^2)$ joukossa $[1,2]\times [1,2]$