\documentclass[twoside]{article}
\usepackage{latexsym,amsfonts,amssymb,amsmath,amsbsy}
\usepackage{graphics}
\usepackage[croatian]{babel}
\usepackage{color}
\input seteps
\input setbmp
\topmargin-1.2cm
\textheight=23cm
\textwidth=16cm
\oddsidemargin=0cm
\evensidemargin=0cm
\newtheorem{tm}{Teorem}
\newtheorem{kor}{Korolar}
\newtheorem{lema}{Lema}
\newtheorem{prop}{Propozicija}
\newtheorem{nap}{Primjedba}
\newtheorem{dfn}{Definicija}
\newtheorem{zad}{Zadatak}
\newtheorem{sem}{Seminar}
\newtheorem{pr}{Primjer}
\def\C{{\mathbb{C}}}
\def\R{{\mathbb{R}}}
\def\Z{{\mathbb{Z}}}
\def\N{{\mathbb{N}}}
\def\be{\begin{equation}}
\def\ee{\end{equation}}
\def\R{{\mathbb{R}}}
\def\Q{{\mathbb{Q}}}
\def\C{{\mathbb{C}}}
\def\N{{\mathbb{N}}}
\def\Z{{\mathbb{Z}}}

\usepackage[dvips]{graphicx}

\input c:/pctexv4/amstex/cyracc.def
\font\tencyr=wncyr10 % wncyr10 se moze zamijeniti s drugim fontom. Vidi
                     % file c:\pctex32\amstex\userdoc.tex
\def\cyr{\tencyr\cyracc}



\pagestyle{myheadings}
\markboth{Newtonova metoda}{Newtonova metoda}
 
\begin{document}  
\thispagestyle{empty}

\begin{flushleft}
Sveu\v{c}ili\v{s}te J.\,J.\,Strossmayera u Osijeku\\
Elektrotehni\v{c}ki fakultet\\
Kneza Trpimira bb\\
31\,000 Osijek
\end{flushleft}
\begin{flushright}
Osijek, 19.\ studenog 2007.
\end{flushright}
\vspace*{1cm}

\begin{center}
{\sf Seminarski rad iz predmeta ``Matemati\v{c}ko programiranje''}\\[5ex]
{\large\bf Newtonova metoda\\ za rje\v{s}avanje nelinearne jednad\v{z}be $f(x)=0$}\\[1ex]
{\sc Ime Prezime I}\footnote{e-mail: {\tt ImePrezimeI@etfos.hr}}, 
{\sc Ime Prezime II}\footnote{e-mail: {\tt ImePrezimeII@etfos.hr}}
\end{center}
\vspace*{2cm}

\noindent
{\bf Sa\v{z}etak.} U ovom seminarskom radu analizira se Newtonova metoda za rje\v{s}avanje jednad\v{z}be $f(x)=0$, gdje je $f\in C^2[a,b]$ funkcija zadan na intervalu $[a,b]$. Dane su osnovne karakteristike i svojstva ove metode. Izra\dj en je odgovaraju\'ci {\em Mathematica}--modul pomo\'cu kojega je analizirana metoda na nekoliko ilustrativnih primjera.
\bigskip

\noindent
{\bf Klju\v{c}ne rije\v{c}i:} Newtonova metoda, nulto\v{c}ke funkcije
\bigskip

 
\noindent
{\bf Abstract.\ (Newton's method for solving a nonlinear equation $f(x)=0$)} In this seminar paper Newton's method for solving equation $f(x)=0$ is analysed, where $f\in C^2[a,b]$ is a function defined on the interval $[a,b]$. Basic characteristics and properties of this method are given. A corresponding {\em Mathematica} module is made by means of which the method is analysed on several illustrative examples.   
\bigskip
% abstract je potrebno lektorirati

\noindent
{\bf Keywords:} Newton's method, roots of a function

\bigskip

\noindent
{\bf AMS Mathematical Classifications (2000): 65H05} 
% vidi http://www.ams.org/msc/

\vfill
{\sf 
\begin{center}
\begin{tabular}{|p{3.5cm}|p{3cm}|p{3cm}|p{3cm}|p{3cm}|}\hline
Preuzimanje seminara & Izlaganje & Ocjena &  Datum & Potpis \\
\hline
&\vspace*{.7cm}&&&\\
\hline
\end{tabular}
\end{center}
}
\newpage


\baselineskip=16pt


\section{Uvod}

 Promatramo realnu neprekidnu funkciju $f$ definiranu  na  zatvorenom
intervalu $[a,b]$. Op\'cenito, svaki kompleksni broj $\xi$,  koji
je  rje\v{s}enje jednad\v{z}be
\begin{equation} \label{N1}
f(x) = 0,
\end{equation}
nazivamo {\sf nulto\v{c}kom} funkcije $f$. Mi \'cemo se ograni\v{c}iti na
istra\v{z}ivanje samo realnih nulto\v{c}aka funkcije $f$ (sjeci\v{s}ta grafa
funkcije s osi $x$). Op\'cenito se mo\v{z}e dogoditi da neka funkcija ima
vi\v{s}e realnih nulto\v{c}aka, da su neke vi\v{s}estruke ili da uop\'ce
nema realnih nulto\v{c}aka.

     Ako je funkcija $f$ neprekidna na intervalu $I = [a,b]$ i ako na
rubovima intervala prima suprotne vrijednosti (tj. ako  je  $f(a)\cdot f(b)<0)$,
onda (vidi {\sc Juki\'c}\,(2000), str.\,120),
postoji barem jedna to\v{c}ka $\xi\in I$,
za koju vrijedi  $f(\xi) = 0$. Ako je, osim toga, prva derivacija $f'$ stalnog
predznaka  na  intervalu  $I$, onda je to i jedina nulto\v{c}ka funkcije $f$
na intervalu $I$.
 Na taj se na\v{c}in posao oko tra\v{z}enja  realnog  rje\v{s}enja
jednad\v{z}be  (\ref{N1}) svodi na dva koraka:
\begin{enumerate}
\item Separirati interval $I$, u kome funkcija ima nulto\v{c}ku,
\item Nekom iterativnom metodom odrediti aproksimaciju nulto\v{c}ke  $\xi$  s
      unaprijed zadanom to\v{c}no\v{s}\'cu.
\end{enumerate}
\medskip

Spomenuti interval $I = [a,b]$, u kome se nalazi barem jedna nulto\v{c}ka
funkcije $f$, treba odrediti tako da na njegovim rubovima funkcija prima
vrijednosti suprotnog predznaka, tj. da bude
\[
f(a)\cdot f(b) < 0.
\]




\section{Newtonova metoda}


Pretpostavimo da smo na neki na\v{c}in odredili interval $I=[a,b]$, u
kome se nalazi jedinstvena nulto\v{c}ka neprekidne i dovoljno ``glatke''
funkcije $f$ za koju je $f'(x)\neq 0$ $\forall x\in I$. Izaberimo po\v{c}etnu
aproksimaciju $x_0\in I$, razvijmo
funkciju $f$ u  Taylorov red u okolini to\v{c}ke $x_0$ i zadr\v{z}imo se na
linearnom \v{c}lanu. Tako smo  funkciju $f$ u okolini to\v{c}ke $x_0$
aproksimirali linearnom funkcijom
\[
f_1(x) = f(x_0 ) + (x - x_0) f'(x_0)
\]
\v{c}iji graf je tangenta na graf funkcije $f$ u to\v{c}ki $x_0$.

Sada \'cemo  umjesto rje\v{s}avanja jednad\v{z}be (\ref{N1}),
rje\v{s}avati  jednad\v{z}bu $f_1(x) = 0$  (geometrijski gledano,
umjesto tra\v{z}enja
sjeci\v{s}ta grafa funkcije $f$ s osi $x$, tra\v{z}imo  sjeci\v{s}te
tangente s osi $x$). Rje\v{s}enje jednad\v{z}be $f_1(x) = 0$ ozna\v{c}imo s $x_1$
\[
x_1:= x_0-\frac{f(x_0)}{f'(x_0)}.
\]
Ponavljaju\'ci postupak, dobivamo niz $x_0,x_1,\ldots$ zadan rekurzivnom
formulom\footnote{U literaturi \v{c}esto ovu metodu mo\v{z}emo na\'ci
pod imenom {\em Newton-Raphsonova metoda}.}

\begin{equation}\label{N2} 
x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)},\;\;n = 0,1,\ldots
\end{equation}
Va\v{z}no je primijetiti da u svakoj iteraciji konstruiramo lokalni aproksimant
funkcije $f$ i onda tra\v{z}imo nulto\v{c}ku lokalnog aproksimanta.

Ako je $x_n$  jedna aproksimacija nulto\v{c}ke $\xi$ u intervalu
$I = [a,b]$  i  ako je $f$ derivabilna funkcija, takva da je
$|f'(x)|>0,\,x\in I$, onda iz Lagrangeovog teorema o srednjoj vrijednosti (vidi primjerice \cite{Jukic}) slijedi ovakva ocjena apsolutne pogre\v{s}ke $n$-te aproksimacije
\begin{equation} \label{N3}
|\xi-x_n|\leq\frac{|f(x_n)|}{m_1},\;\mbox{ gdje je }\;0<m_1=\min_{x\in I}|f'(x)|.
\end{equation}

O konvergenciji Newtonove metode mo\v{z}e se vidjeti u \cite{Cheney}, \cite{Plato}, \cite{Sci}. Vrijedi slijede\'ci teorem (dokaz vidi primjerice u \cite{Sci}):

\begin{tm} \label{T1}
Neka funkcija $f:I\rightarrow\R$ ima neprekidnu drugu derivaciju  na
intervalu $I = [a,b]$. Neka je nadalje, $f(a)\cdot f(b) < 0$, a  prva
($f'$)  i  druga ($f''$) derivacija funkcije $f$ na intervalu $I$ imaju
stalan predznak.

     Tada, ako je $x_0\in I$ izabran tako da bude
\begin{equation}\label{N4} 
f(x_0)\cdot f''(x_0) > 0,
\end{equation}
niz definiran s (\ref{N2}) konvergira prema jedinstvenom rje\v{s}enju
$\xi$ jednad\v{z}be $f(x) = 0$.

     Pri tome vrijedi ocjena pogre\v{s}ke aproksimacije 
\begin{equation}\label{N5} 
|\xi - x_n|\leq\frac{M_2}{2m_1}(x_n-x_{n-1})^2,
\end{equation}
gdje je
\[ 
m_1=\min_{x\in I}|f'(x)|,\;\;\;\;M_2=\max_{x\in I}|f''(x)|,
\]
a metoda ima kvadratnu brzinu konvergencije, tj. vrijedi
\begin{equation}\label{N6} 
|\xi-x_{n+1}|\leq\frac{M_2}{2m_1}(\xi-x_n)^2.
\end{equation}
\end{tm}



\section{Numeri\v{c}ki eksperimenti}

Na nekoliko numeri\v{c}kih i prakti\v{c}nih primjera, a na bazi vlastitog programa izra\dj enog u programskom sustavu {\em Mathematica} ilustrirat \'cemo prednosti i nedostatke Newtonove metode.
 
\begin{pr}
S to\v{c}no\v{s}\'cu $\epsilon=0.00005$ ($4$ signifikantne decimale)  treba
odrediti po\-zi\-tiv\-nu nulto\v{c}ku funkcije
\[f(x) = e^{-x}+x^2-2.\]
\end{pr}

Ova funkcija ima dvije nulto\v{c}ke. Jednu mo\v{z}emo lokalizirati u intervalu $I_1= [-1,0]$
a druga u intervalu $I_2=[1,2]$  ({\it Slika\,1}). Mi \'cemo potra\v{z}iti
nulto\v{c}ku  iz intervala $[1,2]$. Kako je $f'(x)=-e^{-x}+2x$, funkcija $f$ je  rastu\'ca na intervalu $I_2$ i imamo $m_1=f'(1)\geq 1.6$, a kako je
 $f(2)\cdot f''(2) > 0$ za po\v{c}etnu
aproksimaciju izabrat \'cemo $x_0= 2$.


% slika je napravljena u Mathematica, snimljena u eps formatu i dopunjena naredbom \put 
\begin{figure}[h]
\centerline{\scalebox{1}{\includegraphics{newton1.eps}}
\put(-230,82){{\small $f(x)=e^{-x}+x^2-2$\hspace*{2cm}$x\mapsto e^{-x},\quad x->\mapsto 2-x^2$}}
}
\caption{Lokalizacija nulto\v{c}aka}
\end{figure}

Nakon $3$ iteracije dobivamo $x^*=1.3160$. Tijek iterativnog procesa prikazan
je u {\em Tablici\,1} ($g_0$ je desna strana ocjene (\ref{N3}). Primijetite da sama vrijednost funkcije jo\v{s} uvijek nije manja od $\varepsilon$.
\begin{center}


\[
\begin{array}{|c|c|c|c|} \hline
n & x_n & g_0 & f(x_n)  \\ \hline
0 & 2        & 1.334585  & 2.135336  \\
1 & 1.4475   & 0.206462 & 0.330339  \\
2 & 1.3233   & 0.010823  & 0.017316  \\
3 & 1.3160   & 0.000037  & 0.000060  \\ \hline
\end{array}
 \]
{\sf Tablica\,1} {\em Tijek iterativnog procesa}
\end{center}

Ni\v{z}e je naveden modul {\tt NewtonMethod} kojim se uz primjenu Newtonove metode tra\v{z}i nulto\v{c}ka funkcije.

{\small
\begin{verbatim}
In[1]:= NewtonMethod[f_, x0_, m1_, eps_, Imax_, ind_] := Module[{x = x0, n = 0},
              (* f - funkcija *)
              (* x0 - pocetna aproksimacija *)
              (* m1 - broj iz ocjene (3) *)
              (* eps - tocnost *)
              (* Imax - maksimalno dozvoljen broj iteracija *)
              (* ako je ind = 0, nece se ispisivati iterativni proces; u protivnom, hoce *)
        While[N[Abs[f[x]]/m1] > eps && n < Imax,
           If[ind != 0, 
               Print[" x_", n, " = ", x, ",  pogreska = ", f[x]/m1, ",  f(x_", n,")=", f[x]//N]];
                  x = N[x - f[x]/f'[x]]; n = n + 1]; 
          {n, x}]
\end{verbatim}
}

\noindent
koji uz poziv 
{\small
\begin{verbatim}
In[1]:= f[x_] := Exp[-x] + x^2 - 2;
        NewtonMethod[f, 2, 1.6, .00005, 10, 0]
\end{verbatim}
}
daje broj potrebnih iteracija i vrijednost dobivene aproksimacije nulto\v{c}ke
{\small
\begin{verbatim}
Out[3]:= {3, 1.316}
\end{verbatim}
}


\begin{thebibliography}{10}

\bibitem{Jukic}
{\sc D.\,Juki\'c, R.\,Scitovski}, {\em Matematika I}, Odjel za matematiku, Sveu\v{c}ili\v{s}te u Osijeku, Osijek, 2000.


\bibitem{Cheney}
{\sc D.\,Kincaid,W.\,Cheney}, {\em Numerical Analysis}, Brooks/Cole Publishing Company, New  York, 1996.

\bibitem{Plato}
{\sc R.\,Plato}, {\em Concise Numerical Mathematics}, American Mathematical Society, Providence, 2003.

\bibitem{PlatoD}
{\sc R.\,Plato}, {\em Numerische Mathematk kompakte}, Vieweg Verlag, M\"unchen, 1962. {\tt http://www.ams.org/bookpages/gsm-57}

\bibitem{Press}
{\sc W.\,H.\,Press, B.\,P.\,Flannery, S.\,A.\,Teukolsky, W.\,T.\,Vetterling},
{\em Numerical Recipes}, Cambridge University Press, Cambridge, 1989.

\bibitem{Sci}
{\sc R.\,Scitovski}, {\em Numeri\v{c}ka matematika}, Odjel za matematiku, Sveu\v{c}ili\v{s}te u Osijeku, Osijek, 2000

\bibitem{Stoer}
{\sc J.\,Stoer}, {\em Numerische Mathematik 1}, 8.\ Auflage, Springer--Verlag, Berlin, 2002.

\bibitem{SB}
{\sc J.\,Stoer, R.\,Bulirsch}, {\em Introduction to Numerical Analysis}, 2nd Ed., Springer Verlag, New York, 1993.

\end{thebibliography}

\end{document}
