\documentclass{article}
\usepackage[slovene]{babel}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{color}
\begin{document}

\begin{center}
\LARGE{Re"sene izpitne naloge iz numeri"cnih metod 2000-2007}
\end{center}

\section{Iterativno re"sevanje nelinearnih ena"cb}

\begin{enumerate}

\item Poi"s"ci re"sitev ena"cbe $x=f(x)$, kjer je
$$
    f(x)=-\frac{1}{2}(x^3+3),
$$
s pomo"cjo Newtonove iteracije. Izberi za"cetni pribli"zek $x_0=1$.
Ali lahko dobimo to re"sitev tudi s pomo"cjo iteracije
\begin{equation}\label{negibna_tocka-1}
    x_{n+1}=f(x_n)
\end{equation}
s primerno izbranim za"cetnim pribli"zkom?

\textit{Re"sitev:} Newtonova iteracija za ena"cbo $f(x)-x=0$:
$$
    x_{n+1}= x_n-\frac{f(x_n)-x_n}{f'(x_n)-1}
$$
Izberimo za"cetni pribli"zek $x_0=1$ in dobimo:
$$
\left(
\begin{array}{lllllll}
    x_n : & 1.000 & -2.000 & -1.423 & -1.085 & -1.004 & -1.000
\end{array}
\right)
$$
Gornja iteracija \eqref{negibna_tocka-1} ne konvergira k $x=-1$, ker
je $f'(x)=-\frac{3}{2}x^2$ v to"cki $x=-1$ enak $-\frac{3}{2}$, ki
je po absolutni vrednosti ve"c kot ena. To"cka $x=-1$ je odbojna.
\begin{figure}[h!]
\begin{center}
    \includegraphics[scale=0.8]{negibna_tocka-1.pdf}
    \caption{To"cka $x=-1$ je odbojna.}
\end{center}
\end{figure}

\item Na intervalu $[0,1]$ ima ena"cba $f(x)=x$, kjer je
$$
    f(x)=3\sqrt{x}e^{-x}-\frac{1}{3},
$$
dve re"sitvi. Katero od teh dveh re"sitev je mogo"ce poiskati s
pomo"cjo iteracije
\begin{equation}\label{fix_point-2}
    x_{n+1}=f(x_n),\quad  x_{n+1}=3\sqrt{x_n}e^{-x_n}-\frac{1}{3}
\end{equation}
s primerno izbranim za"cetnim pribli"zkom $x_0$?

\textit{Re"sitev:} Najprej s pomo"cjo Newtonove iteracije poi"s"cemo
re"sitvi ena"cbe $f(x)=x$.
$$
    x_{n+1}=x_{n}-\frac{f(x_n)-x_n}{f'(x_n)-1}
$$
Izberimo za"cetna pribli"zka $x_0=\{0.02,1.0\}$:
$$
    \left(\begin{array}{ll}
    0.02 & 1.0 \\
    0.0130373 & 0.851983 \\
    0.013748 & 0.84922 \\
    0.0137594 & 0.849218
    \end{array}\right)
$$
Poi"s"cemo absolutno vrednost odvoda iteracijske funkcije
\eqref{fix_point-2}:
$$
    f'(\{0.0137594,0.849218\})=\{12.2658, -0.486293\}
$$
Prva to"cka je odbojna, druga pa privla"cna.
\begin{figure}[h!]
\begin{center}
    \includegraphics[scale=0.8]{negibna_tocka-2.pdf}
    \caption{Prva to"cka je odbojna, druga pa privla"cna.}
\end{center}
\end{figure}

\item Na intervalu $[0,2]$ ima ena"cba $f(x)=0$, kjer je
$$
    f(x)=\sqrt{x}e^{-x}-\frac{1}{3},
$$
dve re"sitvi. Katero od teh dveh re"sitev je mogo"ce poiskati s
pomo"cjo iteracije
\begin{equation}\label{fix_point-3}
    x_{n+1}=f(x_n)+x_n,\quad  x_{n+1}=\sqrt{x_n}e^{-x_n}-\frac{1}{3}+x_n
\end{equation}
s primerno izbranim za"cetnim pribli"zkom $x_0$?

\textit{Re"sitev:} Najprej s pomo"cjo Newtonove iteracije poi"s"cemo
re"sitvi ena"cbe $f(x)=0$.
$$
    x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)}
$$
Izberimo za"cetna pribli"zka $x_0=\{0.02,1.0\}$:
$$
    \left(\begin{array}{ll}
    0.02 & 1. \\
    0.04513 & 1.7919 \\
    0.05449 & 1.7972 \\
    0.05514 & 1.7972 \\
    \end{array}\right)
$$
Poi"s"cemo absolutno vrednost odvoda iteracijske funkcije
\eqref{fix_point-3}:
$$
    f'(\{0.05514,1.7972\})=\{2.6893, -0.2406\}
$$
Prva to"cka je odbojna, druga pa privla"cna.
\begin{figure}[h!]
\begin{center}
    \includegraphics[scale=0.8]{negibna_tocka-3.pdf}
    \caption{Prva to"cka je odbojna, druga pa privla"cna.}
\end{center}
\end{figure}

\item S pomo"cjo Newtonove iteracije dolo"ci vrednost $\sqrt[3]{2}$ na
tri decimalna mesta natan"cno.

\textit{Re"sitev:} Re"simo ena"cbo $x^3-2=0$ s pomo"cjo Newtonove
metode. Za"cetni pribli"zek bomo vzeli $x_0=1$.
$$
    x_{n+1}=x_n-\frac{x_n^3-2}{3x_n^2}
$$
$$
    \left(
    \begin{array}{lllll}
    x_n : & 1. & 1.333 & 1.264 & 1.260
    \end{array}
    \right)
$$

\item Zapi"si tri korake sekantne metode za re"sevanje ena"cbe $f(x)=0$, kjer je
$$
    f(x)=x+(x^3+3)/2.
$$
Izberi za"cetne vrednosti $x_0=-3.0$ $x_1=-2.0$.

\textit{Re"sitev:} Pri sekantni metodi je iteracija:
$$
    x_{n+1}=x_{n}-f(x_n)\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}
$$
Po treh korakih metode je $x_4=-0.888$.

\item Re"sujemo ena"cbo $x=bx(1-x)$ za razli"cne vrednosti parametra $b$.
V kak"snih mejah se mora gibati parameter $b$, da iteracija
\begin{equation}\label{fix_point_2}
    x_{n+1}=bx_n(1-x_n)
\end{equation}
s primerno izbiro za"cetnega pribli"zka, konvergira k pozitivni
re"sitvi ena"cbe.

\textit{Re"sitev:} Re"sitev ena"cbe, ki je razli"cna od ni"c, je
$x=\frac{(b-1)}{b}$. Od tod sledi, da je $b>1$, "ce je ta re"sitev
pozitivna. To"cka je privla"cna za iteracijo \eqref{fix_point_2},
"ce je odvod desne strani po absolutni vrednosti manj kot ena v tej
to"cki.
$$
    b(1-2x)=2-b,\quad \mbox{za}\quad x=\frac{(b-1)}{b}
$$
Od tod sledi, da mora biti $b\in(1,3)$.

\item Poka"zite, da le"zi na intervalu $I=[0.1,1]$ natanko en koren ena"cbe
$$
    x+\log x = 0.
$$
Poi"s"ci ta koren z Newtonovo metodo.\\
Naslednje tri funkcije
$$
    f(x)=-\log x,\quad f(x)=e^{-x}, \quad f(x)=\frac{1}{2}(x+e^{-x})
$$
imajo natanko eno fiksno to"cko $x=f(x)$ na intervalu $I$, ki se
ujema z re"sitvijo zgornje ena"cbe. V katerih primerih je ta to"cka
privla"cna in v katerih odbojna. Z drugimi besedami, v katerih
primerih lahko poi"s"cemo za"cetni  pribli"zek, razli"cen od fiksne
to"cke, tako da iteracija konvergira k fiksni to"cki in kdaj to ni
mogo"ce?
$$
    x_{k+1}=-\log x_k,\quad x_{k+1}=e^{-x_k},
    \quad x_{k+1}=\frac{1}{2}(x_k+e^{-x_k})
$$

\textit{Re"sitev:} $x= 0.56714$,
$$
    f'(x)=-1/x,\quad -e^{-x},\quad\mbox{in}\quad \frac{1}{2}(1-e^{-x})
$$
Vrednosti odvodov funkcij $f(x)$ v negibni to"cki so
$$
    -1.76291, -0.567086, 0.216457
$$
Prva je odbojna, ker je odvod po absolutni vrednosti ve"cji od 1,
drugi dve pa sta privla"cni.

\end{enumerate}

\section{Sistemi linearnih ena"cb}

\subsection{Dolo"ceni sistemi}

\begin{enumerate}

\item Polo"zi parabolo skozi to"cke $T_1(1,1)$ $T_2(2,2)$ in $T_3(-2,1)$.

\textit{Re"sitev:} Re"sujemo sistem
$$
    y_i=ax_i^2+bx_i+c,\quad i=1,2,3.
$$
Neznanke so $a$, $b$ in $c$. Sistem zapi"semo v matri"cni obliki
takole:
$$
    \left[\begin{array}{lll}
    1 &  1 & 1\\
    4 &  2 & 1\\
    4 & -2 & 1
    \end{array}\right]
    \left[\begin{array}{l}
    a \\
    b \\
    c
    \end{array}\right]
    =\left[\begin{array}{l}
    1 \\
    2 \\
    1
    \end{array}\right]
$$
Re"sitev tega sistema je $a=\frac{1}{4}$, $b=\frac{1}{4}$ in $c=\frac{1}{2}$. \\
Parabola, ki poteka skozi te tri to"cke je podana z ena"cbo:
$$
    y= \frac{1}{4}x^2+\frac{1}{4}x+\frac{1}{2}.
$$

\item Poka"zi, da je matrika sistema $Ax=b$ pozitivno definitna in re"si
sistem s pomo"cjo razcepa Choleskega.
$$
    A=\left[\begin{array}{ll}
    2 & 1 \\
    1 & 3
    \end{array}\right],
    \quad
    b=\left[\begin{array}{l}
    0 \\
    1
    \end{array}\right]
$$

\textit{Re"sitev:} Matrika $A$ pozitivno definitna, "ce so vsi
glavni minorji matrike pozitivni. Glavna minorja sta:
$$
    2\quad\mbox{in}\quad
    \left|\begin{array}{ll}
    2 & 1 \\
    1 & 3
    \end{array}\right|=6-2=4,
$$
ki sta oba pozitivna. \\
Razcepimo matriko $A=R^TR$, kjer je $R$ zgornjetrikotna matrika.
$$
    \left[\begin{array}{ll}
    \alpha & a^T \\
    a & A_*
    \end{array}\right]=
    \left[\begin{array}{ll}
    \rho & 0 \\
    r & R_*^T
    \end{array}\right]
    \left[\begin{array}{ll}
    \rho & r^T \\
    0 & R_*
    \end{array}\right]
$$
Od tod sledi:
\begin{eqnarray*}
    \alpha=\rho^2 & \Rightarrow & \rho=\sqrt{\alpha}\\
    a^T=\rho r^T & \Rightarrow & r^T=a^T/\rho\\
    A_*=R_*^TR_*+r r^T & \Rightarrow & R_*^TR_*=A_*-r r^T
\end{eqnarray*}
V na"sem primeru je
\begin{eqnarray*}
    \alpha=2 & \Rightarrow & \rho=\sqrt{2}\\
    a^T=1 & \Rightarrow & r^T=\frac{1}{\sqrt{2}}\\
    A_*=3 & \Rightarrow & R_*^TR_*=3-\frac{1}{2}=\frac{5}{2},\quad R_*=\sqrt\frac{5}{2}
\end{eqnarray*}
Od tod sledi, da je
$$
    R=\left[\begin{array}{ll}
    \sqrt{2} & \frac{1}{\sqrt{2}} \\
    0 & \sqrt\frac{5}{2}
    \end{array}\right]
$$
Re"simo sistem
$$
    R^TRx=b,\quad Rx=y,\quad R^Ty=b
$$
Oba sistema sta trikotna, zato jih re"simo z vstavljanjem.
$$
    \left[\begin{array}{ll}
    \sqrt{2} & 0 \\
    \frac{1}{\sqrt{2}} & \sqrt{\frac{5}{2}}
    \end{array}\right]y=
    \left[\begin{array}{l}
    0 \\
    1
    \end{array}\right], \quad
    y=\left[\begin{array}{ll}
    \sqrt{2} & \frac{1}{\sqrt{2}} \\
    0 & \sqrt{\frac{5}{2}}
    \end{array}\right] x
$$
Od tod sledi, da je
$$
    y=
    \left[\begin{array}{l}
    0 \\
    \sqrt\frac{2}{5}
    \end{array}\right] \quad\mbox{in}
    \quad x=\left[\begin{array}{l}
    -\frac{1}{5} \\
    \frac{2}{5}
    \end{array}\right]
$$

\item Izra"cunaj neskon"cno in prvo normo matrike
$$
    A =
    \left[
    \begin{array}{ccc}
    1 & 2 & -1 \\
    0 & 3 & -1 \\
    5 & -1 & 1
    \end{array}
    \right].
$$

\textit{Re"sitev:} Neskon"cna norma matrike $A$, $\|A\|_{\infty}$, je maksimalna vrsti"cna vsota absolutnih vrednosti:
$$
    \|A\|_{\infty} = \max_{1 \le i \le n} \sum_{j=1}^n |a_{ij}|
$$
Torej v na"sem primeru: $\|A\|_{\infty} = \max{\{4, 4, 7\}} = 7$. \\
Prva norma matrike $A$, $\|A\|_1$, je maksimalna stolpi"cna vsota absolutnih vrednosti:
$$
    \|A\|_1 = \max_{1 \le j \le n} \sum_{i=1}^n |a_{ij}|
$$
Torej v na"sem primeru: $\|A\|_1 = \max{\{6, 6, 3\}} = 6$.

\item Poka"zi, da lahko sistem $Ax=b$ re"simo s pomo"cjo Jacobijeve iteracijske
metode in zapi"si tretjo iteracijo. Za"cetni pribli"zek je enak 0.
$$
    A=\left[\begin{array}{ll}
    1 & -1 \\
    -1 & 2
    \end{array}\right],
    \quad b=\left[\begin{array}{l}
    0 \\
    1
    \end{array}\right]
$$

\textit{Re"sitev:} Napravimo razcep matrike po Jacobiju:
$$
    A=D-N, \quad A=\left[\begin{array}{ll}
    1 & 0 \\
    0 & 2 \\
    \end{array}\right]-\left[\begin{array}{ll}
    0&1 \\
    1&0
    \end{array}\right]
$$
Iteracijska matrika $S$ je enaka
$$
    S=D^{-1}N=
    \left[\begin{array}{ll}
    1 & 0 \\
    0 & \frac{1}{2}
    \end{array}\right]
    \left[\begin{array}{ll}
    0 & 1 \\
    1 & 0
    \end{array}\right]=
    \left[\begin{array}{ll}
    0 & 1 \\
    \frac{1}{2} & 0
    \end{array}\right]
$$
Lastne vrednosti iteracijske matrike so:
$$
    \left|\begin{array}{ll}
    -\lambda & 1 \\
    \frac{1}{2} & -\lambda
    \end{array}\right|
    =\lambda^2-\frac{1}{2}=0,\quad
    \lambda_{1,2}=\pm\frac{1}{\sqrt{2}}
$$
Lastni vrednosti sta po absolutni vrednosti manj kot 1, zato je
Jacobijeva iteracija konvergentna.
$$
    x_{n+1}=\left[\begin{array}{l}
    0 \\
    \frac{1}{2}
    \end{array}\right]+
    \left[\begin{array}{ll}
    0 & 1 \\
    \frac{1}{2} & 0
    \end{array}\right]x_n
$$
Tretja iteracija, "ce izberemo za"cetni pribli"zek 0, in to"cna
re"sitev sta enaki
$$
    x_{3}=\left[\begin{array}{l}
    1/2 \\
    3/4
    \end{array}\right],\quad
    x=\left[\begin{array}{ll}
    1 \\
    1
    \end{array}\right]
$$

\item Poka"zi, da lahko sistem $Ax=b$ re"simo s pomo"cjo Gauss-Seidlove
iteracijske metode. Zapi"si to"cno re"sitev in tretjo iteracijo.
Za"cetni pribli"zek je enak 0.
$$
    A=\left[\begin{array}{ll}
    1 & -1 \\
    -1 & 2
    \end{array}\right],
    \quad b=\left[\begin{array}{l}
    0 \\
    1
    \end{array}\right]
$$

\textit{Re"sitev:} Napravimo razcep matrike po Gauss-Seidlu:
$$
    A=M-N, \quad A=\left[\begin{array}{ll}
    1 & 0 \\
    -1 & 2
    \end{array}\right] -
    \left[\begin{array}{ll}
    0 & 1 \\
    0 & 0
    \end{array}\right]
$$
Iteracijska matrika $S$ je enaka
$$
    S=M^{-1}N=
    \left[\begin{array}{ll}
    1 & 0 \\
    \frac{1}{2} & \frac{1}{2}
    \end{array}\right]
    \left[\begin{array}{ll}
    0 & 1 \\
    0 & 0
    \end{array}\right] =
    \left[\begin{array}{ll}
    0 & 1 \\
    0 & \frac{1}{2}
    \end{array}\right]
$$
Lastne vrednosti iteracijske matrike so:
$$
    \left|\begin{array}{ll}
    -\lambda & 1 \\
    0 & \frac{1}{2} -\lambda
    \end{array}\right|
    =\lambda(\lambda-\frac{1}{2})=0,\quad
    \lambda_1=0\quad\mbox{in}\quad \lambda_2=\frac{1}{2}
$$
Lastni vrednosti sta po absolutni vrednosti manj kot 1, zato je
Gauss-Seidlova iteracija konvergentna.
$$
    x_{n+1}=\left[\begin{array}{l}
    0 \\
    \frac{1}{2}
    \end{array}\right]+
    \left[\begin{array}{ll}
    0 & 1 \\
    0 & \frac{1}{2}
    \end{array}\right]x_n
$$
Tretja iteracija, "ce izberemo za"cetni pribli"zek 0, in to"cna
re"sitev sta enaki:
$$
    x_{3}=\left[\begin{array}{l}
    3/4 \\
    7/8
    \end{array}\right],\quad
    x=\left[\begin{array}{ll}
    1 \\
    1
    \end{array}\right]
$$

\item Poka"zi, da lahko sistem $Ax=b$ re"simo s pomo"cjo Jacobijeve
iteracijske metode. Zapi"si to"cno re"sitev in tretjo iteracijo.
Za"cetni pribli"zek je enak 0.
$$
    A=\left[\begin{array}{lll}
    4 & 1 & 1\\
    1 & 3 & 1\\
    1 & 0 & 2
    \end{array}\right],\quad
    b=\left[\begin{array}{l}
    1 \\
    1 \\
    1
    \end{array}\right]
$$

\textit{Re"sitev:} Matrika sistema je diagonalno dominantna, zato
Jacobijeva iteracija konvergira. Zapi"simo Jacobijevo iteracijo po
komponentah:
\begin{eqnarray*}
    x_1^{(n+1)}&=&\frac{1}{4}(1-x^{(n)}_2-x^{(n)}_3)\\
    x_2^{(n+1)}&=&\frac{1}{3}(1-x^{(n)}_1-x^{(n)}_3)\\
    x_3^{(n+1)}&=&\frac{1}{2}(1-x^{(n)}_1)
\end{eqnarray*}
Tretja iteracija in to"cna re"sitev sta enaki:
$$
    x_3=\left[\begin{array}{l}
    0.1354 \\
    0.1944 \\
    0.4792
    \end{array}\right],\quad
    x=\left[\begin{array}{l}
    0.10 \\
    0.15 \\
    0.45
    \end{array}\right]
$$

\item Poka"zi, da lahko sistem $Ax=b$ re"simo s pomo"cjo Gauss-Seidlove
iteracijske metode. Zapi"si to"cno re"sitev in tretjo iteracijo.
Za"cetno pribli"zek je enak 0.
$$
    A=\left[\begin{array}{lll}
    4 & 1 & 1\\
    1 & 3 & 1\\
    1 & 0 & 2
    \end{array}\right],\quad
    b=\left[\begin{array}{l}
    1 \\
    1 \\
    1
    \end{array}\right]
$$

\textit{Re"sitev:} Matrika sistema je diagonalno dominantna, zato
Gauss-Seidlova iteracija konvergira. Zapi"simo Gauss-Seidlovo
iteracijo po komponentah
\begin{eqnarray*}
    x_1^{(n+1)}&=&\frac{1}{4}(1-x^{(n)}_2-x^{(n)}_3)\\
    x_2^{(n+1)}&=&\frac{1}{3}(1-x^{(n+1)}_1+x^{(n)}_3)\\
    x_3^{(n+1)}&=&\frac{1}{2}(1-x^{(n+1)}_1)
\end{eqnarray*}
Tretja iteracija in to"cna re"sitev sta enaki:
$$
    x_3=\left[\begin{array}{l}
    0.0924 \\
    0.1515 \\
    0.4538
    \end{array}\right],\quad
    x=\left[\begin{array}{l}
    0.10 \\
    0.15 \\
    0.45
    \end{array}\right]
$$

\item Ali lahko re"simo sistem $Ax=b$ z Gauss-Seidlovo iteracijo?
$$
    A=\left[\begin {array}{ccc}
    2& 2& 0\\
    0& 2& 1\\
    0& 0& 1\\
    \end {array}\right ]
    \quad b=
    \left [\begin {array}{c}
    1\\
    2\\
    1
    \end {array}\right ]
$$
Izra"cunaj prve tri korake iteracije. Za"cetni pribli"zek izberi
$x_0=[0,0,0]^T$. Kdaj bi se lahko zgodilo, da nas iteracijska metoda
pripelje do re"sitve v kon"cno korakih?

\textit{Re"sitev:} Gauss-Seidlova iteracija je konvergentna, ker ima
matrika
$$
    S=-M^{-1}N=
    \left[\begin{array}{lll}
    0 & -1 & 0 \\
    0 & 0 & -1/2 \\
    0 & 0 & 0
    \end{array}\right]
$$
samo ni"celne lastne vrednosti. \\[1mm]
Ker je matrika $S$ zgornjetrikotna z diagonalo enako ni"c, je njena
tretja potenca identi"cno enaka ni"c. Zato se tretja iteracija ujema
s to"cno re"sitvijo: $x_3=[0,1/2,1]^T$ in $x_{\infty}=[0,1/2,1]^T$.

\end{enumerate}

\subsection{Predolo"ceni sistemi}

\begin{enumerate}

\item Poi"s"ci vektor $x$, ki minimizira evklidsko normo $\|Ax-b\|_2$, kjer je
$$
    A=\left[\begin{array}{ll}
    1 & 2 \\
    1 & 1 \\
    1 & 3
    \end{array}\right],
    \quad b=\left[\begin{array}{l}
    1 \\
    0 \\
    1
    \end{array}\right].
$$

\textit{Re"sitev:} Iskani vektor $x$ je re"sitev ena"cbe
$$
    A^TAx=A^Tb,\quad x=(A^TA)^{-1}A^Tb.
$$
Sistem ima enoli"cno re"sitev, "ce je matrika $A$ polnega ranga. V
tem primeru to pomeni, da so stolpci linearno neodvisni, torej mora
biti
rang enak 2. V na"sem primeru to velja. \\
Ker je
$$
    A^TA=\left[\begin{array}{ll}
    3 & 6 \\
    6 & 14
    \end{array}\right],\quad
    A^Tb=\left[\begin{array}{l}
    2\\
    5
    \end{array}\right],
$$
je
$$
    x=\left[\begin{array}{ll}
    \frac{7}{3} & -1 \\
    -1 & \frac{1}{2}
    \end{array}\right]
    \left[\begin{array}{l}
    2\\
    5
    \end{array}\right]=
    \left[\begin{array}{l}
    -\frac{1}{3}\\
    \frac{1}{2}
    \end{array}\right].
$$

\item Aproksimiraj podatke $P$ z linearno funkcijo $f(x)=a_1x+a_2$.
$$
    P=\left[\begin{array}{llll}
    x_n :&1&2&3\\
    y_n :&1&3&4
    \end{array}\right]
$$

\textit{Re"sitev:}
$$
    A=\left[\begin{array}{ll}
    x_1&1\\
    x_2&1\\
    x_3&1
    \end{array}\right]=
    \left[\begin{array}{ll}
    1&1\\
    2&1\\
    3&1
    \end{array}\right],\quad
    b=\left[\begin{array}{l}
    y_1\\
    y_2\\
    y_3
    \end{array}\right]=
    \left[\begin{array}{l}
    1\\
    3\\
    4
    \end{array}\right].
$$
Re"sitev, ki minimizira normo $\|Aa-b\|_2$, dobimo takole:
$$
    a=\left[\begin{array}{l}
    a_1\\
    a_2
    \end{array}\right]
    =(A^TA)^{-1}A^Tb=
    \left[\begin{array}{l}
    \frac{3}{2}\\
    -\frac{1}{3}
    \end{array}\right]
$$
Linearna funkcija, ki aproksimira podatke $P$, je
$y=\frac{3}{2}x-\frac{1}{3}$.

\item Aproksimiraj tabelo podatkov $P$ s funkcijo $f(x)=a_1e^{a_2x}$, tako da
uvede"s nove spremenljivke, za katere postane problem linearen.
$$
    P=\left[\begin{array}{lllllll}
    x_n :& 0   & 1   & 2   & 3   & 4   & 5\\
    y_n :& 1.14& 0.89& 0.71& 0.67& 0.64& 0.48
    \end{array}\right]
$$

\textit{Re"sitev:} Uvedba novih spremenljivk:
$$
    y=a_1e^{a_2x},\quad \log y= \log a_1 + a_2x
$$
Ozna"cimo
$$
    Y=\log{y} \quad\mbox{in}\quad X=x
$$
in aproksimiramo tabelo
$$
    P'=\left[\begin{array}{lllllll}
    X_n :& 0   & 1   & 2   & 3   & 4   & 5\\
    Y_n :& 0.13& -0.12& -0.34& -0.4& -0.45& -0.73
    \end{array}\right]
$$
z linearno funkcijo $Y=a'_1X+a'_2$
$$
    A=\left[\begin{array}{ll}
    0 & 1 \\ 1 & 1 \\ 2 & 1  \\ 3 & 1 \\ 4 & 1 \\ 5 & 1
    \end{array}\right],\quad
    b=\left[\begin{array}{l}
    0.13\\ -0.12\\ -0.34\\ -0.4\\ -0.45\\ -0.73
    \end{array}\right],\quad
    a'=(A^TA)^{-1}A^Tb=
    \left[\begin{array}{l}
    -0.15\\ 0.07
    \end{array}\right].
$$
Od tod sledi:
$$
    a_1=e^{a'_2}=1.07\quad\mbox{in}\quad a_2=a'_1=-0.15.
$$
\begin{figure}[h!]
\begin{center}
    \includegraphics[scale=0.8]{least_sqr_2.pdf}
    \caption{Podatki in graf funkcije $f(x)=1.07\,e^{-0.15x}$}
\end{center}
\end{figure}

\item Aproksimiraj  podatke
$$
    \left[\begin{array}{l|cccc}
    x&1&2&3&4\\
    y&3&0&-1&1
    \end{array}\right]
$$
s polinomom druge stopnje in poi"s"ci najmanj"so vrednost tega
polinoma.

\textit{Re"sitev:} Polimom
$$
    y=1.25x^2-6.95x+8.75
$$
Najmanj"sa vrednost je $y_{min}=-0.9105$.

\end{enumerate}

\subsection{Nedolo"ceni sistemi}

\begin{enumerate}

\item Poi"s"ci to"cko ravnine
$$
    3x_1+4x_2+5x_3=5,
$$
ki je najbli"ze koordinatnemu izhodi"s"cu.

\textit{Re"sitev:} Re"sujemo sistem $Ax=b$, kjer je
\begin{equation}\label{min_norm}
    A=\left[\begin{array}{lll}3 & 4 & 5\end{array}\right],
    \quad b=5\quad\mbox{in}\quad
    x=\left[\begin{array}{lll}x_1 & x_2 & x_3\end{array}\right]^T.
\end{equation}
Sistem ima neskon"cno re"sitev. I"s"cemo tisto, katere druga norma
$\|x\|_2$ je najmanj"sa. "Ce je matrika $A$ polnega ranga, kar v tem
primeru pomeni, da so vrstice linearno neodvisne, potem obstaja
enoli"cna re"sitev problema. Pi"semo:
$$
    x=A^Ty,\quad AA^Ty=b,\quad y=(AA^T)^{-1}b,\quad x=A^T(AA^T)^{-1}b
$$
Re"sitev z minimalno normo $x$ sistema \eqref{min_norm} zapi"semo
takole:
$$
    x=\left[\begin{array}{l}
    3\\
    4\\
    5
    \end{array}\right]
    \left( \left[\begin{array}{lll}3 & 4 & 5\end{array}\right]
    \left[\begin{array}{l}
    3\\
    4\\
    5
    \end{array}\right]\right)^{-1}5=
    \frac{1}{10}\left[\begin{array}{l}
    3\\
    4\\
    5
    \end{array}\right]
$$

\item Poi"s"ci re"sitev sistema $Ax=b$  z najmanj"so evklidsko normo.
$$
    A=\left[\begin{array}{lll}
    1&2&3\\
    1&1&1
    \end{array}\right], \quad
    b=\left[\begin{array}{l}
    1\\
    2\\
    \end{array}\right]
$$

\textit{Re"sitev:} Kot v prej"snji nalogi dobimo:
$$
    x=A^T(AA^T)^{-1}b
$$
Ker je
$$
    AA^T=\left[\begin{array}{lll}
    1&2&3\\
    1&1&1
    \end{array}\right]
    \left[\begin{array}{ll}
    1&1\\
    2&1\\
    3&1
    \end{array}\right]=
    \left[\begin{array}{ll}
    14&6\\
    6&3
    \end{array}\right]
$$
je
$$
    (AA^T)^{-1}=\left[\begin{array}{ll}
    \frac{1}{2}&-1\\
    -1&\frac{7}{3}
    \end{array}\right]
$$
Re"sitev $x$ izrazimo
$$
    x=\left[\begin{array}{ll}
    1&1\\
    2&1\\
    3&1
    \end{array}\right]
    \left[\begin{array}{ll}
    \frac{1}{2}&-1\\
    -1&\frac{7}{3}
    \end{array}\right]
    \left[\begin{array}{l}
    1\\
    2
    \end{array}\right]=
    \left[\begin{array}{l}
    \frac{13}{6}\\
    \frac{2}{3}\\
    -\frac{5}{6}
    \end{array}\right]
$$

\end{enumerate}

\section{Numeri"cno odvajanje in integriranje}

\subsection{Numeri"cno odvajanje in interpolacija}

\begin{enumerate}

\item Funkcija je podana tabelari"cno:
$$
    \begin{array}{c|ccc}
    x & 2 & 2.5 & 4 \\
    \hline
    f(x) & 0.5 & 0.4 & 0.25
    \end{array}
$$
S pomo"cjo kvadratne interpolacije izra"cunaj $f(3)$.

\textit{Re"sitev:} Funkcijo interpoliramo s kvadratno parabolo $f(x) \approx a x^2 + b x + c$. Ko vstavimo v funkcijo podatke iz tabele,
dobimo sistem ena"cb za koeficiente:
\begin{eqnarray*}
    0.5 & = & 4a + 2b + c \\
    0.4 & = & 6.25a + 2.5b + c \\
    0.25 & = & 16a + 4b + c
\end{eqnarray*}
Sistem ima re"sitev $a = -0.05$, $b = 0.425$ in $c = -0.15$. \\
Torej je
$$
    f(x) = -0.05x^2 + 0.425x - 0.15
$$
in zato je $f(3) = 0.675$.

\item Z uporabo deljenih razlik izra"cunajte $f(8.2)$, "ce je
funkcija $f(x)$ podana tabelari"cno:
$$
    P= \left[\begin{array}{llll}
    i :&0&1&2\\
    x_i :&8.0&8.1&8.3\\
    y_i :&16.0&17.6&17.5
    \end{array}\right]
$$

\textit{Re"sitev:} Zapi"semo tabelo deljenih razlik
$$
    D=
    \left[\begin{array}{llll}
    x_0&y_0&&\\
    x_1&y_1&y_{0,1}=\frac{y_1-y_0}{x_1-x_0}\\
    x_2&y_2&y_{1,2}=\frac{y_2-y_1}{x_2-x_1}&y_{0,1,2}=\frac{f_{1,2}-f_{0,1}}{x_2-x_0}
    \end{array}\right]
$$
Vrednost v to"cki $x$ izra"cunamo s pomo"cjo polinoma:
$$
    p(x)=y_0+y_{0,1}(x-x_0)+y_{0,1,2}(x-x_0)(x-x_1)
$$
V na"sem primeru je
$$
    D=
    \left[\begin{array}{llll}
    8.0&16.0&&\\
    8.1&17.6&16.0&\\
    8.3&17.5&-0.5&-55.0
    \end{array}\right]
$$
$$
    p(8.2)=16.0+16.0(8.2-8.0)-55.0(8.2-8.0)(8.2-8.1)=18.1
$$

\item Dolo"ci ute"zi formule za numeri"cno odvajanje, oblike:
$$
    f'(x)\approx w_1f(x-h)+w_2f(x)+w_3f(x+h)
$$
tako, da bo to"cna za polinome stopnje manj"se ali enake 2.

\textit{Re"sitev:} Zapi"simo sistem ena"cb, kjer vstavimo
$f(x)=\{1,\ x,\ x^2\}$.
\begin{eqnarray*}
    0&=&w_1+w_2+w_3\\
    1&=&w_1(x-h)+w_2x+w_3(x+h) \\
    2x&=&w_1(x-h)^2+w_2x^2+w_3(x+h)^2
\end{eqnarray*}
Re"sitev mora biti neodvisna od $x$, $x$ se okraj"sa. Sistem, po
kraj"sanju $x$:
\begin{eqnarray*}
    0&=&w_1+w_2+w_3\\
    1&=&-w_1h+w_3h\\
    0&=&w_1h^2+w_3h^2
\end{eqnarray*}
Od tod sledi, da je $w_1=-\frac{1}{2h}$, $w_2=0$ in
$w_3=\frac{1}{2h}$. Torej:
$$
    f'(x)\approx\frac{f(x+h)-f(x-h)}{2h}
$$

\item Dolo"ci ute"zi formule za numeri"cno odvajanje, oblike:
$$
    f'(x)=w_1f(x-2h)+w_2f(x-h)+w_3f(x)
$$
tako, da bo to"cna za polinome stopnje manj"se ali enake 2.

\textit{Re"sitev:} Zapi"simo sistem ena"cb, kjer vstavimo
$f(x)=\{1,\ x,\ x^2\}$.
\begin{eqnarray*}
    0&=&w_1+w_2+w_3\\
    1&=&w_1(x-2h)+w_2(x-h)+w_3x\\
    2x&=&w_1(x-2h)^2+w_2(x-h)^2+w_3x^2
\end{eqnarray*}
Re"sitev mora biti neodvisna od $x$, $x$ se okraj"sa. Sistem, po
kraj"sanju $x$:
\begin{eqnarray*}
    0&=&w_1+w_2+w_3\\
    1&=&-2w_1h-w_2h\\
    0&=&w_14h^2+w_2h^2
\end{eqnarray*}
Od tod sledi, da je $w_1=\frac{1}{2h}$, $w_2=-\frac{2}{h}$ in
$w_3=\frac{3}{2h}$. Torej:
$$
    f'(x)\approx\frac{f(x-2h)-4f(x-h)+3f(x)}{2h}
$$

\end{enumerate}

\subsection{Numeri"cno integriranje}

\begin{enumerate}

\item Izra"cunaj integral
$$
    I = \int_{-1}^2 x^3 e^x \, dx
$$
s pomo"cjo trapezne, Simpsonove in triosminske formule ($n = 6$). Rezultate primerjajte s to"cno re"sitvijo.

\textit{Re"sitev:} Ker je $n = 6$, $a = -1$ in $b = 2$, je $h = \frac{1}{2}$, vozli pa so v to"ckah $-1, -\frac{1}{2}, 0, \frac{1}{2}, 1, \frac{3}{2}, 2$. \\
Trapezna formula se glasi:
\[
    \int_a^b f(x) \, dx \approx \frac{h}{2} \left( f(a) + 2f(a+h) + \cdots 2f(b-h) + f(b) \right)
\]
Pribli"zna vrednost integrala po tej formuli je $I = 23.6733$. \\
Simpsonova formula se glasi:
\begin{eqnarray*}
    \int_a^b f(x) \, dx & \approx & \frac{h}{3} \Big( f(a) + 4f(a+h) + 2f(a+2h) + \cdots \\
    & & \quad + 2f(b-2h) + 4f(b-h) + f(b) \Big)
\end{eqnarray*}
Pribli"zna vrednost integrala po tej formuli je $I = 20.8675$. \\
Triosminska formula se glasi:
\begin{eqnarray*}
    \int_a^b f(x) \, dx & \approx & \frac{3h}{8} \Big( f(a) + 3f(a+h) + 3f(a+2h) + 2f(a+3h) + \cdots \\
    & & \quad + 2f(b-3h) + 3f(b-2h) + 3f(b-h) + f(b) \Big)
\end{eqnarray*}
Pribli"zna vrednost integrala po tej formuli je $I = 21.0865$. \\
To"cna vrednost integrala je $I = 20.6642$.

\item Konstruiraj kvadraturno formulo
$$
    I(f) = \int_{-1}^1 f(x) \, dx \approx A_0 f \left( -\frac{1}{2} \right) + A_1 f(0) + A_2 f \left( \frac{1}{2} \right),
$$
ki je to"cna za polinome reda $\le 2$. S pomo"cjo te formule izra"cunaj "se vrednost integrala
$$
    \int_{-1}^1 x e^x \, dx
$$
in jo primerjaj s to"cno vrednostjo.

\textit{Re"sitev:} Najprej dolo"cimo koeficiente kvadraturne formule tako, da bo le-ta to"cna za $f(x) = 1, x, x^2$.
\begin{eqnarray*}
    f(x) = 1 & : & \int_{-1}^1 dx = x \big|_{-1}^1 = 2 = A_0 + A_1 + A_2 \\
    f(x) = x & : & \int_{-1}^1 x \, dx = \frac{x^2}{2} \Big|_{-1}^1 = 0 = -\frac{1}{2} A_0 + \frac{1}{2} A_2 \\
    f(x) = x^2 & : & \int_{-1}^1 x^2 \, dx = \frac{x^3}{3} \Big|_{-1}^1 = \frac{2}{3} = \frac{1}{4} A_0 + \frac{1}{4} A_2
\end{eqnarray*}
Re"sitev tega sistema je $A_0 = A_2 = \frac{4}{3}$, $A_1 = -\frac{2}{3}$. \\
Kvadraturna formula se torej glasi:
$$
    I(f) = \frac{4}{3} f \left( -\frac{1}{2} \right) - \frac{2}{3} f(0) + \frac{4}{3} f \left( \frac{1}{2} \right).
$$
Izra"cunajmo integral po kvadraturni formuli:
$$
    \int_{-1}^1 x e^x \, dx = \frac{2}{3} \left( e^{1/2} - e^{-1/2} \right) = 0.6948.
$$
To"cna vrednost: $I = 0.7358$.

\item Sestavi enostavno kvadraturno formulo oblike
$$
    \int_0^1f(x)dx\approx \frac{1}{2}f(\xi_1)+\frac{1}{2}f(\xi_2).
$$
Vozli"s"ci $\xi_1$ in $\xi_2$ izbere"s tako, da je formula to"cna za
$f(x)=1$, $x$ in $x^2$. S pomo"cjo dobljene formule izra"cunaj
pribli"zno vrednost integrala
$$
    \int_0^1\sin(\pi x)\,dx
$$
in jo primerjaj s to"cno re"sitvijo.

\textit{Re"sitev:} Za $f(x)=1$ je pogoj na prazno izpolnjen.
Zapi"simo sistem za $x$ in $x^2$.
\begin{eqnarray*}
    \int_0^1x\,dx=\frac{1}{2}&=&\frac{1}{2}(\xi_1+\xi_2)\\
    \int_0^1x^2\,dx=\frac{1}{3}&=&\frac{1}{2}(\xi_1^2+\xi_2^2)
\end{eqnarray*}
Re"sitev sistema je
$$
    \xi_{1,2}=\frac{1}{2}(1\pm\frac{1}{\sqrt{3}})
$$
Od tod je:
$$
    \int_0^1\sin(\pi x)\,dx\approx  0.616191
$$
To"cna re"sitev je $\frac{2}{\pi}\approx 0.63662$.

\item Sestavi enostavno kvadraturno formulo oblike
$$
    \int_{-1}^1f(x)dx\approx wf(\xi_1)+wf(\xi_2).
$$
Ute"z $w$ in vozli"s"ci $\xi_1$ in $\xi_2$ izbere"s tako, da je
formula to"cna za $f(x)=1$, $x$, in $x^2$. S pomo"cjo dobljene
formule izra"cunaj pribli"zno vrednost integrala
$$
    \int_{-1}^1 e^x\,dx
$$
in jo primerjaj s to"cno re"sitvijo.

\textit{Re"sitev:} Zapi"simo sistem ena"cb:
\begin{eqnarray*}
    \int_{-1}^1\,dx=2&=&2w\\
    \int_{-1}^1x\,dx=0&=&w\xi_1+w\xi_2\\
    \int_{-1}^1x^2\,dx=\frac{2}{3}&=&w\xi_1^2+w\xi_2^2
\end{eqnarray*}
Iz gornjega sledi, da je $w=1$ in $\xi_{1,2}=\pm
\frac{1}{\sqrt{3}}$. Od tod je:
$$
    \int_{-1}^{1}e^x\,dx\approx e^{-\frac{1}{\sqrt{3}}}+e^{\frac{1}{\sqrt{3}}}=2.3427
$$
To"cna re"sitev je $e-1/e\approx 2.3504$.

\item Sestavi enostavno kvadraturno formulo oblike
$$
    \int_{-1}^1f(x)dx\approx wf(\xi)
$$
Ute"z $w$ in vozli"s"ce $\xi$ izbere"s tako, da je formula to"cna za
$f(x)=1$ in $x$. S pomo"cjo dobljene formule izra"cunaj pribli"zno
vrednost integrala
$$
    \int_{-1}^1\frac{\sin x}{x}\,dx
$$
in jo primerjaj z re"sitvijo, natan"cno na "stiri decimalna mesta,
ki jo dobi"s s pomo"cjo razvoja v Taylorjevo vrsto.

\textit{Re"sitev:} Zapi"simo sistem ena"cb:
\begin{eqnarray*}
    \int_{-1}^1\,dx=2&=&w\\
    \int_{-1}^1x\,dx=0&=&w\xi
\end{eqnarray*}
Iz gornjega sledi, da je $w=2$ in $\xi=0$. Od tod je:
$$
    \int_{-1}^{1}\frac{\sin x}{x}\,dx\approx
    2\lim_{x\to 0}\frac{\sin x}{x}=2
$$
Razvijemo funkcijo $\sin x$ v Taylorjevo vrsto v okolici to"cke 0 in
dobimo
$$
    \frac{\sin x}{x}=1-\frac{x^2}{3!}+\frac{x^4}{5!}-\dots
$$
Integriramo po $x$ v mejah od $-1$ do $1$ in dobimo
$$
    \int_{-1}^1\frac{\sin x}{x}\, dx=x-\frac{x^3}{3 \cdot 3!}+\frac{x^5}{5 \cdot 5!}-\dots=
    2-\frac{2}{3 \cdot 3!}+\frac{2}{5 \cdot 5!}-\dots
$$
"Ce "zelimo, da se delna vsota $n$ "clenov razlikuje od to"cne
vrednosti za manj kot $10^{-4}$, mora biti absolutna vrednost
$(n+1)$-vega "clena manj kot $10^{-4}$.
Tak"sno oceno napake lahko naredimo zato, ker je vrsta alternirajo"ca. \\
Iz $\frac{2}{(2n-1)(2n-1)!}<10^{-4}$ sledi, da je  $n>4$ in
$$
    2-\frac{2}{3 \cdot 3!}+\frac{2}{5 \cdot 5!}-\frac{2}{7 \cdot 7!}=1.89217
$$

\item Sestavi enostavno kvadraturno formulo za singularne integrale oblike
$$
    \int_{0}^1\frac{f(x)}{\sqrt{x}}dx\approx w_0f(0)+w_1f(1/2)+w_2f(1)
$$
Ute"zi $w_i$ izbere"s tako, da je formula to"cna za $f(x)=1$, $x$ in
$x^2$. S pomo"cjo dobljene formule izra"cunaj pribli"zno vrednost
integrala
\begin{equation}\label{integral-x}
    \int_{0}^1\frac{\cos \frac{x}{2}}{\sqrt{x}}\,dx
\end{equation}
in jo primerjaj z re"sitvijo, natan"cno na "stiri decimalna mesta.
ki jo dobi"s s pomo"cjo razvoja v Taylorjevo vrsto funkcije $f(x)$ v
okolici to"cke $0$.

\textit{Re"sitev:} Re"simo sistem ena"cb:
\begin{eqnarray*}
    \int_0^1\frac{1}{\sqrt{x}}dx=2&=&w_0+w_1+w_2\\
    \int_0^1\frac{x}{\sqrt{x}}dx=\frac{2}{3}&=&\frac{1}{2}w_1+w_2\\
    \int_0^1\frac{x^2}{\sqrt{x}}dx=\frac{2}{5}&=&\frac{1}{4}w_1+w_2\\
\end{eqnarray*}
in dobimo re"sitev $w_0=4/5$, $w_1=16/15$ in  $w_2=2/15$. Pribli"zna
vrednost integrala \eqref{integral-x} je
$$
    \int_0^1\frac{\cos\frac{x}{2}}{\sqrt{x}}dx \approx
    \frac{4}{5}\cos 0 + \frac{16}{15}\cos\frac{1}{4}+\frac{2}{15}\cos{\frac{1}{2}}=1.95052
$$
Razvijemo funkcijo $f(x)$ v Taylorjevo vrsto v okolici $x=0$.
$$
    f(x)=1 - \frac{x^2}{8} + \frac{x^4}{384} - \dots
$$
Izra"cunamo integral
\begin{equation}\label{integral-s}
    \int_0^1 \left( \frac{1}{\sqrt{x}} - \frac{x^{3/2}}{8} + \frac{x^{7/2}}{384} \right) \,dx=1.95058
\end{equation}
Rezultat se razlikuje od to"cne vrednosti za manj kot $1/46080$,
kolikor je maksimalna vrednost prvega izpu"s"cenega "clena v razvoju
\eqref{integral-s} (alternirajo"ca vrsta).


\item Re"si integral s popravljeno Simpsonovo kvadraturno formulo za singularne integrale in primerjaj
rezultat z re"sitvijo, to"cno na tri decimalna mesta, ki jo dobi"s s
pomo"cjo razvoja v Taylorjevo vrsto.
$$
    \int_{0}^{1/2} \frac{e^{-x^2}}{\sqrt{x}}\,dx
$$

\textit{Re"sitev:}
$$
    \int_{-1}^{1/2} \frac{f(x)}{\sqrt{x}}dx \approx w_1 f(0)+w_2 f(1/4)+w_3f(1/2)
$$
Taylorjeva vrsta: $F(x)=2\sqrt{x} - \frac{2}{5}x^{5/2} +
\frac{1}{9}x^{9/2}$,
$I=F(1/2)-F(0)=1.348$ \\
Kvadraturna formula: $\frac{\sqrt{2}}{15}\left(9 f(0) + 7 f(1/4)-
f(1/2)\right)=1.328$

\item Poi"s"ci pribli"zno vrednost integrala
$$
    \int_0^1xe^{-x^2}\,dx
$$
s pomo"cjo enostavne Gaussove kvadraturne formule.
$$
    \int_0^1f(x)\,dx\approx wf(\xi)+wf(1-\xi)
$$
Parametra $w$ in $\xi$ dolo"ci"s tako, da je formula to"cna
za poten"cne funkcije $x^n$, kjer je $n=0$, $1$, $2$. \\[1mm]
Rezultat primerjaj s to"cno re"sitvijo.

\textit{Re"sitev:} Izpolnjeni morajo biti naslednji pogoji:
$$
    \int_0^1 x^n \,dx = w\xi^n+w(1-\xi)^n, \quad n=0,1,2
$$
Od tod dobimo sistem ena"cb
\begin{eqnarray*}
    1&=&2w, \quad n=0\\
    \frac{1}{2}&=&w\xi+w(1-\xi), \quad n=1\\
    \frac{1}{3}&=&w\xi^2+w(1-\xi)^2, \quad n=2
\end{eqnarray*}
Prva in druga ena"cba sta odvisni, iz njiju pa dobimo
$w=\frac{1}{2}$. Vstavimo v tretjo ena"cbo in dobimo
\begin{eqnarray*}
    \frac{1}{3}&=&\xi^2-\xi+\frac{1}{2}\\
    0&=&\xi^2-\xi+\frac{1}{6}\\
    \xi&=&\frac{1}{2}-\frac{\sqrt{3}}{6}
\end{eqnarray*}
To"cna vrednost: $\frac{e-1}{2e} \approx 0.31606$. \\
Kvadraturna formula: $0.312754$.

\end{enumerate}

\subsection{Diferencialne ena"cbe}

\begin{enumerate}

\item Numeri"cno re"si diferencialno ena"cbo
$$
    y'(x)=-y,\quad y(0)=1,
$$
po navadni Eulerjevi metodi in po Heunovi metodi.
\begin{itemize}
\item Euler:
$$
        y_{k+1}=y_k+f(x_k,y_k)\,h
$$
\item Heun:
$$
        y_{k+1}=y_k+\frac{h}{2}(f(x_k,y_k)+f(x_{k+1},y_{k+1}))
$$
\end{itemize}
Vzemi, da je $h=\frac{1}{2}$ in izra"cunaj pribli"zno vrednost $y(1)$ po eni in drugi metodi. \\
Funkcija $y(x)$ je padajo"ca in v limiti, ko $x$ nara"s"ca "cez vse
meje, gre proti ni"c. Najve"c kolik"sen je lahko korak $h$ po eni in
po drugi metodi da re"sitev "se ohrani to lastnost.

\textit{Re"sitev:} Zapi"simo formulo za izra"cun funkcijskih
vrednosti $y_k$ po eni in drugi metodi.
\begin{itemize}
\item Euler:
$$
    y_{k+1}=y_k-y_k\,h=y_k(1-h)=y_0(1-h)^{k+1}
$$
Pribli"zna vrednost $y(1)$ je v tem primeru enaka
$y_2=1(1-1/2)^2=0.25$.
\item Heun:
\begin{eqnarray*}
    y_{k+1}&=&y_k+\frac{h}{2}(-y_k-y_{k+1})\\
    y_{k+1}(1+\frac{h}{2})&=&y_k(1-\frac{h}{2})\\
    y_{k+1}&=&y_k\frac{1-\frac{h}{2}}{1+\frac{h}{2}}=
    y_0\left(\frac{1-\frac{h}{2}}{1+\frac{h}{2}}\right)^{k+1}
\end{eqnarray*}
Pribli"zna vrednost $y(1)$ je v tem primeru enaka
$y_2=1(1-1/4)^2/(1+1/4)^2=0.36$.
\end{itemize}
To"cna vrednost na 6 decimalnih mest pa je enaka $0.367879$. \\[1mm]
Vidimo, da mora biti v prvem primeru izpolnjeno $|1-h|<1$, to
pomeni, da mora biti pozitiven $h<1$. V drugem primeru pa je za
pozitivne $h$ kvocient vedno manj kot 1.
$$\left|\frac{1-\frac{h}{2}}{1+\frac{h}{2}}\right|<1,\quad h>0 $$

\item Numeri"cno re"si diferencialno ena"cbo
$$
    y'(x)=-y(x),\quad y(0)=y_0=1
$$
Izberi korak $h=0.1$ in dolo"ci $y(1)$, po metodi, ki jo izpeljemo
iz razvoja v Taylorjevo vrsto do vklju"cno kvadratnega "clena.
Primerjaj re"sitev s to"cno re"sitvijo in re"sitvijo, ki jo dobimo s
po obi"cajni Eulerjevi metodi. \\[1mm]
Re"sitev diferencialne ena"cbe je:
\begin{itemize}
    \item[(1)] monotono padajo"ca funkcija, katere
    \item[(2)] limita je enaka ni"c, ko $x$ raste "cez vse meje.
\end{itemize}
Primerjaj na"so metodo z obi"cajno Eulerjevo metodo in ugotovi pri
obeh, za katere pozitivne vrednosti koraka $h$ pribli"zna re"sitev
ohranja obe oziroma eno od lastnosti.

\textit{Re"sitev:} Razvoj v Taylorjevo vrsto do vklju"cno
kvadratnega "clena je:
\begin{equation*}
    y(x+h)\approx y(x)+y'(x)h+y''(x)\frac{h^2}{2}
\end{equation*}
Od tod sledi formula
\begin{eqnarray*}
    y_{k+1}&=&y_k-y_k\,h+y_k\frac{h^2}{2}\\
    y_{k+1}&=&\frac{y_k}{2}(2-2h+h^2)\\
    y_{k+1}&=&\frac{y_k}{2}\left(1+(1-h)^2\right)\\
    y_{k+1}&=&y_0\left(\frac{1}{2}\left(1+(1-h)^2\right)\right)^{k+1}
\end{eqnarray*}
Pribli"zna vrednost $y(1)$ pri koraku $h=0.1$ po tej metodi je
$0.368541$, medtem ko je to"cna re"sitev
enaka $1/e\approx 0.367879$. \\[1mm]
Izraz $\frac{1}{2}(1+(1-h)^2)$ je vedno pozitiven in je manj"si od 1
za pozitivne $h$, ki so manj od $2$. Od  tod velja, da se za $0<h<2$
ohranita obe lastnosti (1) monotonost, ker je izraz pozitiven in (2)
pada proti 0, ker je izraz absolutno manj kot 1.
\begin{figure}[h!]
\begin{center}
    \includegraphics[scale=0.8]{ode-t.pdf}
    \caption{Re"sitve za $h=0.6$ in $h=1.2$ po na"si metodi in to"cna re"sitev.}
\end{center}
\end{figure}
Za obi"cajno Eulerjevo formulo velja
\begin{eqnarray*}
     y_{k+1}&=&y_k-y_k\,h\\
     y_{k+1}&=&y_0(1-h)^{k+1}
\end{eqnarray*}
Pribli"zna vrednost $y(1)$ pri koraku $h=0.1$ po Eulerjevi metodi je $0.348678$. \\[1mm]
Za pozitivne $h$ sta izpolnjeni obe lastnosti, "ce je $h<1$. "Ce je
$1<h<2$, lastnost monotonosti ni izpolnjena. "Ce je $h\ge2$ ni
izpolnjena nobena od lastnosti.
\begin{figure}[h!]
\begin{center}
    \includegraphics[scale=0.8]{ode-e.pdf}
    \caption{Re"sitve za $h=0.6$ in $h=1.2$ po
    Eulerjevi metodi in to"cna re"sitev.}
\end{center}
\end{figure}

\item Numeri"cno re"si diferencialno ena"cbo
$$
    y' = y, \quad y(0) = 1
$$
na dva na"cina. "Ce je ena"cba $y' = f(y)$, potem je
\begin{itemize}
\item[a)] Eulerjeva metoda: $y_{n+1} = y_n + hf(y_n)$
\item[b)] Heunova metoda: $y_{n+1} = y_n + \frac{h}{2} (f(y_n) + f(y_{n+1}))$
\end{itemize}
Vzemi korak $h = 0.5$ in naredi $4$ korake po prvi in drugi metodi. Rezultate, ki jih dobi"s, primerjaj s to"cno re"sitvijo.
Katera metoda je bolj"sa?

\textit{Re"sitev:} To"cno re"sitev dobimo z nekaj znanja Matematike II: $y(x) = e^x$. \\
Za obe numeri"cni metodi, je $f(y) = y$. \\
Pri Eulerjevi metodi dobimo:
\begin{eqnarray*}
    y_1 & = & y_0 + hy_0 = y(0) (1 + h) \\
    y_2 & = & y_1 + hy_1 = y(0) (1 + h)^2 \\
    & \hdots & \\
    y_n & = & y(0) (1 + h)^n
\end{eqnarray*}
Pri Heunovi metodi dobimo:
\begin{eqnarray*}
    y_1 & = & y_0 + \frac{h}{2} (y_0 + y_1) = y_0 \frac{1 + \frac{h}{2}}{1 - \frac{h}{2}} \\
    y_2 & = & y_1 + \frac{h}{2} (y_1 + y_2) = y_0 \left( \frac{1 + \frac{h}{2}}{1 - \frac{h}{2}} \right)^2 \\
    & \hdots & \\
    y_n & = & y_0 \left( \frac{1 + \frac{h}{2}}{1 - \frac{h}{2}} \right)^n
\end{eqnarray*}
Upo"stevamo, da je $h = \frac{1}{2}$ in $y_0 = 1$, in dobimo naslednje vrednosti:
$$
    \begin{array}{c|ccccc}
    & y_0 & y_1 & y_2 & y_3 & y_4 \\
    \hline
    \textrm{to"cna} & 1.0000 & 1.6487 & 2.7183 & 4.4817 & 7.3891 \\
    \hline
    \textrm{Heun} & 1.0000 & 1.6667 & 2.7778 & 4.6296 & 7.7160 \\
    \hline
    \textrm{Euler} & 1.0000 & 1.5000 & 2.2500 & 3.3750 & 5.0625 \\
    \hline
    \end{array}
$$
Opazimo, da je Heunova metoda bolj natan"cna od Eulerjeve metode.

\item Re"si robni problem za Airyevo diferencialno ena"cbo.
$$
    y''(x)=-16xy(x),\quad y(0)=1,\quad y(1)=0
$$
Naj bo $h=1/4$. Drugi odvod nadomesti"s z drugo razliko
$$
    \frac{y_{k-1}-2y_k+y_{k+1}}{h^2},\quad k=1,\dots,3,
$$
$$
    y_0=y(0)\quad\mbox{in}\quad y_4=y(1).
$$

\textit{Re"sitev:} Re"siti moramo sistem ena"cb
$$
    y_{k-1}+(x_k-2)y_k+y_{k+1}=0,\quad k=1,2,3.
$$
Raz"sirjena matrika sistema je
$$
    \left[\begin{array}{ccc|c}
    -\frac{7}{4}&1&0&-1 \\
    1&-\frac{3}{2}&1&0\\
    0&1&-\frac{5}{4}&0
    \end{array}\right]
$$
Re"sitev je
$$
    y_1=\frac{28}{9},\quad y_2=\frac{40}{9},\quad\mbox{in}\quad
    y_3=\frac{32}{9}.
$$

\end{enumerate}
\end{document}
