\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\\ Strojarski fakultet\\ Trg Ivane Brli\'c-Ma\v{z}urani\'c 18\\ 35\,000 Slavonski Brod \end{flushleft} \begin{flushright} Slavonski Brod, 25.\ studenog 2006. \end{flushright} \vspace*{1cm} \begin{center} {\sf Seminarski rad iz ``Matematike''}\\[1ex] {\sf na poslijediplomskom doktorskom studiju}\\[5ex] {\large\bf Newtonova metoda za rje\v{s}avanje jednad\v{z}be $f(x)=0$}\\[1ex] {\sc Nata\v{s}a Velji\'c}\footnote{e-mail: {\tt natasa.veljic@sfsb.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 \noindent {\bf Nastavnici:} {\sf doc.\,dr.\,sc.\ Mirta Ben\v{s}i\'c, prof.\,dr.\,sc.\ Rudolf Scitovski}\\ {\sf \begin{center} \begin{tabular}{|p{3cm}|p{3cm}|p{3cm}|p{3cm}|p{3cm}|}\hline Datum preuzimanje seminara & Datum predaje se\-mi\-nara & 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 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}