MN02

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%% makrodefinicje latex2mediawiki %%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% \lstoct{..} zamiast \lstoct!...! %% \\lstC!([^!]*)! %% \\lstC\{\1\}

%% co z algorytmami?

%% Dla niektorych dokumentow moze byc konieczne dostosowanie %% ponizszych makr.

\newcommand{\gdef}{\def} \newcommand{\newenvironment}[3]{\newcommand{\begin#1}{ #2 }\newcommand{\end#1}{ #3 }} \newcommand{\begin}[1]{\begin#1 } \newcommand{\end}[1]{\end#1 }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\maketemplate3}[2]{ \newcommand{\begin#1}{

1. 1. 1. {###{#2\PIPE \PIPE \PIPE

} \newcommand{\begin#1}[1]{

1. 1. 1. {###{#2\PIPE ##1\PIPE ##1\PIPE

} \newcommand{\end#1}{###}###}

} }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\maketemplatealg}[2]{ \newcommand{\begin#1}{

1. 1. 1. {###{#2\PIPE \PIPE \PIPE

\EATWS}
\newcommand{\begin#1}[1]{

###{###{#2\PIPE ##1\PIPE \PIPE 
<pre>\EATWS}
\newcommand{\end#1}{

###}###}

} }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\makeexe}[2]{ \newcommand{\begin#1}{

#2

} \newcommand{\begin#1}[1]{

#2: ##1

}

\newcommand{\end#1}{

} }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\makesol}[2]{ \newcommand{\begin#1}{

#2

} \newcommand{\begin#1}[1]{

#2: ##1

}

\newcommand{\end#1}{

} }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\makehider}[2]{ \newcommand{\begin#1}{

#2

} \newcommand{\end#1}{

} \newcommand{#\#1}[1]{

#2

##1

} }

\newcommand{\makehidersmall}[2]{ \newcommand{\begin#1}{

#2

} \newcommand{\end#1}{

} \newcommand{#\#1}[1]{

#2

##1

} }

\newcommand{\maketemplate2}[2]{ \newcommand{\begin#1}{

1. 1. 1. {###{#2\PIPE \PIPE

} \newcommand{\begin#1}[1]{

1. 1. 1. {###{#2\PIPE ##1\PIPE

} \newcommand{\end#1}{###}###}

} \newcommand{#\#1}[1]{

1. 1. 1. {###{#2\PIPE \PIPE
   2. 1
      1. }###}

} }

%% UWAGA UWAGA UWAGA %% Koniecznie prosze dopisac tutaj swoje srodowiska %% tworzone za pomoca \newtheorem. \maketemplate3{definicja}{definicja} \maketemplate3{definition}{definicja} \maketemplate3{def}{definicja} \maketemplate3{defin}{definicja} \maketemplate3{dfn}{definicja} \maketemplate3{df}{definicja} \maketemplate3{twierdzenie}{twierdzenie} \maketemplate3{theorem}{twierdzenie} \maketemplate3{theor}{twierdzenie} \maketemplate3{thm}{twierdzenie} \maketemplate3{tw}{twierdzenie} \maketemplate3{stwierdzenie}{stwierdzenie} \maketemplate3{stw}{stwierdzenie} \maketemplate3{proposition}{stwierdzenie} \maketemplate3{prop}{stwierdzenie} \maketemplate3{lemat}{lemat} \maketemplate3{lem}{lemat} \maketemplate3{lemma}{lemat} \maketemplate3{uwaga}{uwaga} \maketemplate3{uwa}{uwaga} \maketemplate3{obserwacja}{uwaga}%NOWE \maketemplate3{remark}{uwaga} % \maketemplate3{rem}{uwaga} \maketemplate3{wniosek}{wniosek} \maketemplate3{wn}{wniosek} \maketemplate3{corollary}{wniosek} \maketemplate3{corol}{wniosek} \maketemplate3{conjecture}{wniosek} \maketemplate3{cor}{wniosek} \maketemplate3{con}{wniosek} \maketemplate3{fakt}{fakt} \maketemplate3{fa}{fakt} \maketemplate3{fact}{fakt} \maketemplate3{dowod}{dowod} \maketemplate3{dw}{dowod} \maketemplate3{proof}{dowod} \maketemplate3{prf}{dowod} \maketemplate3{przyklad}{przyklad} \maketemplate3{prz}{przyklad} \maketemplate3{kontrprzyklad}{kontrprzyklad}%NOWE \maketemplate3{counterexample}{kontrprzyklad}%NOWE % \maketemplate3{example}{przyklad} \maketemplate3{exa}{przyklad} \maketemplate3{exm}{przyklad} \maketemplate3{cwiczenie}{cwiczenie} \maketemplate3{zadanie}{cwiczenie} \maketemplate3{zadan}{cwiczenie} \maketemplate3{zad}{cwiczenie} \maketemplate3{exercise}{cwiczenie} % \maketemplate3{exe}{cwiczenie} \makeexe{exe}{Ćwiczenie} % \makesol{sol}{Rozwiązanie} \makesol{example}{Przykład} \makesol{rem}{Uwaga}

%\maketemplate3{ex}{cwiczenie} \maketemplate3{ex}{przyklad}

\maketemplate3{EX}{cwiczenie} \maketemplate3{cw}{cwiczenie} \maketemplate3{zad}{cwiczenie} \maketemplate3{zd}{cwiczenie} \maketemplate3{obserwacja}{obserwacja} \maketemplate3{obserwacje}{obserwacje} \maketemplate3{obs}{obserwacja} \makehidersmall{wskazowka}{Wskaz�wka} \makehidersmall{hint}{Wskazówka} \makehidersmall{wsk}{Wskaz�wka} \maketemplate2{pytanie}{pytanie}%NOWE \maketemplate2{question}{pytanie}%NOWE \maketemplate3{odpowiedz}{odpowiedz} \maketemplate3{odp}{odpowiedz} \makehider{ans}{Odpowied�} \maketemplate3{problem}{problem} \makehider{rozwiazanie}{Rozwi�zanie} \makehider{rozw}{Rozwi�zanie} \makehider{solution}{Rozwi�zanie} \makehider{sol}{Rozwiązanie} \makehider{slv}{Rozwi�zanie}

%\maketemplate3{algorithm}{algorytm} \maketemplate3{algorithmic}{algorytm}

\maketemplatealg{alg}{algorytm} % \maketemplatealg{C}{kod} % \maketemplatealg{F}{kod} % \maketemplatealg{ux}{kod} % \maketemplatealg{make}{kod} % \maketemplatealg{oct}{kod} % \maketemplatealg{outoct}{wyniki} % \maketemplatealg{outux}{wyniki}

\newcommand{\beginC}{\NOCOMMENT

\EATWS}
\newcommand{\endC}{

\NOCOMMENT

}

\newcommand{\beginF}{\NOCOMMENT

\EATWS}
\newcommand{\endF}{

\NOCOMMENT

}

\newcommand{\beginoct}{\NOCOMMENT

\EATWS}
\newcommand{\endoct}{

\NOCOMMENT

}

\newcommand{\beginux}{

\EATWS} \newcommand{\endux}{

}

\newcommand{\beginmake}{\NOCOMMENT

}
\newcommand{\endmake}{

\NOCOMMENT

}

\newcommand{\beginoutoct}{

\EATWS} \newcommand{\endoutoct}{

}

\newcommand{\beginoutux}{

\EATWS} \newcommand{\endoutux}{

}

%\newcommand{\beginalgorithmic}{ %} %\newcommand{\endalgorithmic}{ %} \newcommand{\STATE}{} \newcommand{\STATE}[1]{ #1 } \newcommand{\FOR}[1]{{\bf for} #1 } \newcommand{\ENDFOR}Szablon:\bf endfor \newcommand{\IF}[1]{{\bf if} #1 } \newcommand{\ELSE}Szablon:\bf else \newcommand{\ELSEIF}[1]{{\bf else if} #1 } \newcommand{\ENDIF}Szablon:\bf endif \newcommand{\WHILE}[1]{{\bf while} #1 } \newcommand{\ENDWHILE}Szablon:\bf endwhile \newcommand{\END}Szablon:\bf end \newcommand{\RETURN}Szablon:\bf return \newcommand{\RETURN}[1]{{\bf return } #1 }

\newcommand{\section}[1]{\EQUAL #1\EQUAL

} \newcommand{\section*}[1]{\EQUAL #1\EQUAL

} \newcommand{\cwiczenia*}[1]{\EQUAL #1\EQUAL

} \newcommand{\subsection*}[1]{\EQUAL \EQUAL #1\EQUAL \EQUAL

} \newcommand{\subsubsection*}[1]{\EQUAL \EQUAL \EQUAL #1\EQUAL \EQUAL \EQUAL

} \newcommand{\subsection}[1]{\EQUAL \EQUAL #1\EQUAL \EQUAL

} \newcommand{\subsubsection}[1]{\EQUAL \EQUAL \EQUAL \EQUAL #1\EQUAL \EQUAL \EQUAL \EQUAL

} \newcommand{\paragraph}[1]{

} \newcommand{\subparagraph}[1]{

} \newcommand{\part}[1]{

}

%% TEGO SIE POZBYWAMY \newcommand{\documentclass}[1]{} \newcommand{\usepackage}[1]{} \newcommand{\usepackage}[2]{} \newcommand{\maketitle}{} \newcommand*{\vspace}[1]{ } \newcommand*{\color}[1]{ } \newcommand{\pagestyle}[1]{} \newcommand{\tableofcontents}{} \newcommand{\theoremstyle}[1]{} \newcommand{\documentenvironment}[]{} \newcommand{\begindocument}[]{} \newcommand{\enddocument}[]{} \newcommand*{\rm}[0]{} \newcommand{\Proof}[1]{ #1 } \newcommand*{\bee}{} \newcommand*{\ep}{} \newcommand*{\hspace*}{} \newcommand*{\fill}[1]{} \newcommand*{\index}[1]{} \newcommand*{\medskip}{

} \newcommand*{\bigskip}{

} \newcommand{\index}[1]{ }

%\newcommand{\newtheorem}[3]{ %\newcommand{\begin#1}{ % %$\EQUAL \EQUAL \EQUAL \EQUAL #3\EQUAL \EQUAL \EQUAL \EQUAL % %} % %\newcommand{\end#1}{ % %} %} % %\newcommand{\newtheorem*}[2]{ %\newcommand{\begin#1}{ % %\EQUAL \EQUAL \EQUAL \EQUAL #2\EQUAL \EQUAL \EQUAL \EQUAL % %} % %\newcommand{\end#1}{ % %} %}

%% FORMATOWANIE \newcommand*{\it}[1]{\QUOTE \QUOTE #1\QUOTE \QUOTE } \newcommand*{\sl}[1]{\QUOTE \QUOTE #1\QUOTE \QUOTE } \newcommand*{\em}[1]{#1} \newcommand*{\bf}[1]{\QUOTE \QUOTE \QUOTE #1\QUOTE \QUOTE \QUOTE } \newcommand*{\tt}[1]{#1} \newcommand*{\textrm}[1]{#1} \newcommand*{\underline}[1]{#1} \newcommand*{\textnormal}[1]{#1} \newcommand*{\textsf}[1]{#1} \newcommand*{\texttt}[1]{#1} \newcommand*{\textmd}[1]{#1} \newcommand*{\emph}[1]{#1} %\newcommand*{\textsc}[1]{ #1 } \newcommand*{\textsc}[1]{\QUOTE \QUOTE #1\QUOTE \QUOTE } \newcommand*{\textbf}[1]{\QUOTE \QUOTE \QUOTE #1\QUOTE \QUOTE \QUOTE } \newcommand*{\textup}[1]{#1} \newcommand*{\textit}[1]{\QUOTE \QUOTE #1\QUOTE \QUOTE } \newcommand*{\textsl}[1]{\QUOTE \QUOTE #1\QUOTE \QUOTE }

\newcommand*{\\}{
} \newcommand*{\newline}{
} % \newcommand*{\mbox}[1]{#1}

\newcommand*{\rysunek}[2]{Plik:MN} \newcommand*{\wikirysunek}[2]{[[Image:#1\PIPE thumb\PIPE 400px\PIPE \PIPE #2]]} \newcommand*{\rysunekmaly}[2]{Plik:MN}

\newcommand*{\flash}[2]{

<flash>file\EQUAL #1\PIPE width\EQUAL 550\PIPE height\EQUAL 300</flash>

#2

}

\newcommand*{\href}[2]{[#1 #2]} \newcommand*{\url}[1]{#1} \newcommand*{\link}[3]{#1\PIPE #3} \newcommand{\thmlink}[3]{#1###2\PIPE #3} \newcommand*{\wikilink}[2]{#1\PIPE #2} \newcommand*{\lstC}[1]{#1} \newcommand*{\lstF}[1]{#1} \newcommand*{\lstCs}[1]{#1} \newcommand*{\lstFs}[1]{#1} \newcommand*{\lstoct}[1]{#1} \newcommand*{\lstux}[1]{#1} \newcommand*{\ang}[1]{\QUOTE \QUOTE #1\QUOTE \QUOTE } \newcommand*{\CHECK}[1]{ } % \newcommand*{\cite}[1]{\QUOTE \QUOTE \QUOTE (Uzupe�nij: #1)\QUOTE \QUOTE \QUOTE } \newcommand*{\cite}[1]{}

\newcommand*{\biografia}[3]{[[grafika:#2.jpg\PIPE thumb\PIPE right\PIPE \PIPE #1 #2
#3 Biografia #2\PIPE Zobacz biografię]]}

\newcommand{\ksiazka}[3]{

• #1, #2, #3}

\newcommand{\literatura}[1]{\EQUAL\EQUAL Literatura\EQUAL\EQUAL

W celu dogłębnego zapoznania się z omawianym na wykładzie materiałem, przeczytaj rozdział #1 w

• D. Kincaid, W. Cheney Analiza numeryczna, Wydawnictwa Naukowo-Techniczne, Warszawa 2006, ISBN 83-204-3078-X.

}

% z dane.tex

\newcommand{\Dane}{F} \newcommand{\Alg}Szablon:\bf ALG \newcommand{\Info}{N} \newcommand{\Wyniki}{G} \newcommand{\Oprozw}{S} \newcommand{\dana}{f} \newcommand{\wynik}{g} \newcommand{\R}{R} \newcommand{\rd}{rd_\nu} \newcommand{\flo}{fl_\nu} \newcommand{\cond}{\mbox{cond}} \newcommand{\macheps}{\epsilon_{\mbox{mach}}} \newcommand{\CHECK}[1]{({\bf Do sprawdzenia: #1})}

%% SYMBOLE

\newcommand*{\ldots}{...} \newcommand*{\copyright}{(c)} %\newcommand*{\pounds}{$} \newcommand*{\LaTeXe}{LaTeX2e} \newcommand*{\LaTeX}{LaTeX} \newcommand*{\TeX}{TeX}

%% LISTY

%% IMPLEMENTACJA STOSU \newcommand{\FIRST}[2]{#1} \newcommand{\STACK}[1]{#1{}{}} \newcommand{\APPEND1}[3]{\renewcommand{\STACK}[1]{##1{#1#3}{{#1}{#2}}}} \newcommand{\APPEND}[1]{\STACK[\APPEND1][#1]} \newcommand{\POP1}[2]{\renewcommand{\STACK}[1]{##1#2}} \newcommand{\POP}{\STACK[\POP1]} \newcommand{\TOP}{\STACK[\FIRST]} \newcommand{\HASH}[1]{##} % potrzebne, bo hashe so redukowane przy instancjalizacji

\newcommand{\beginenumerate}{\APPEND[\HASH{}]} \newcommand{\endenumerate}{\POP} \newcommand{\beginitemize}{\APPEND[*]} \newcommand{\enditemize}{\POP} \newcommand{\begindescription}{\APPEND[:]} \newcommand{\enddescription}{\POP} \newcommand{\item}[1]{ \POP\TOP; #1 \TOP:\APPEND[:] } \newcommand{\item}{ \TOP }

%% ROWNANIA \newcommand{\beginequation}{

$$\EATWS } \newcommand{\endequation}{$$

}

\newcommand{\begincomment}{ }

\newcommand{\beginlatexonly}{ }

\newcommand{\beginequation*}{

$$\EATWS } \newcommand{\endequation*}{$$

}

\newcommand{\begindisplaymath}{

$$\EATWS } \newcommand{\enddisplaymath}{$$

} \newcommand{\beginmath}{$\EATWS } \newcommand{\endmath}{$}

\newcommand{\beginquote}{

} \newcommand{\endquote}{

} \newcommand{\beginbadquote}{

} \newcommand{\endbadquote}{

}

\newcommand{\begineqnarray*}{

$$\aligned \EATWS } \newcommand{\endeqnarray*}{\endaligned$$

} \newcommand{\begineqnarray}{

$$\aligned \EATWS } \newcommand{\endeqnarray}{\endaligned$$

} \newcommand{\beginalign*}{

$$\aligned \EATWS } \newcommand{\endalign*}{\endaligned$$

} \newcommand{\beginalign}{

$$\aligned \EATWS } \newcommand{\endalign}{\endaligned$$

} \newcommand{\[}{

$$\EATWS } \newcommand{\]}{$$

} \newcommand{\(}{ $\EATWS } \newcommand{\)}{ $ }

%% LINKI %\newcommand*{\label}[1]{{{kotwica\PIPE #1\PIPE }}} \newcommand{\label}[1]{} \newcommand{\kotwa}[1]{ } \newcommand{\ref}[1]{#####1\PIPE Uzupelnic: #1 }

%% TABELKI

\renewcommand*{\begintabular}[1]{ \TABULARMODE \renewcommand*{\\}{ \PIPE - \PIPE \EATWS } \renewcommand*{\hline}{}

1. {\PIPE border\EQUAL 1

\PIPE + \PIPE - \PIPE \EATWS }

\renewcommand*{\begintabular}[2]{ \TABULARMODE \renewcommand*{\\}{ \PIPE - \PIPE \EATWS } \renewcommand*{\hline}{}

1. {\PIPE border\EQUAL 1

\PIPE + Uzupelnij tytul \PIPE - \PIPE \EATWS }

\renewcommand*{\begintabular*}[3]{ \TABULARMODE \renewcommand*{\\}{ \PIPE - \PIPE \EATWS } \renewcommand*{\hline}{}

1. {\PIPE border\EQUAL 1

\PIPE + Uzupelnij tytul \PIPE - \PIPE \EATWS }

\renewcommand*{\endtabular}{ \TABULARMODE \renewcommand*{\\}{
} \PIPE #} \renewcommand*{\hline}{

---

} }

\newcommand*{\hline}{

---

}

\newcommand{\MATHEMBEDDEFSTRUE}{\renewcommandM{\textnormal}[1]{ $ #1 $ }\renewcommandM{\textrm}[1]{ $ #1 $ }\renewcommandM{\mbox}[1]{ \BACKSLASH mbox{#1} }\renewcommandM{\hbox}[1]{ $ #1 $ }} \newcommand{\MATHEMBEDDEFSFALSE}{\renewcommandM{\textnormal}[1]{\BACKSLASH textnormal{#1}}\renewcommandM{\textrm}[1]{\BACKSLASH textrm{#1}}\renewcommandM{\mbox}[1]{\BACKSLASH mbox{#1}}\renewcommandM{\hbox}[1]{\BACKSLASH hbox{#1}}} \newcommandM{\beginarray}{\MATHEMBEDDEFSFALSE\BACKSLASH begin{array}} \newcommandM{\endarray}{\MATHEMBEDDEFSTRUE\BACKSLASH end{array}} \newcommandM{\beginpmatrix}{\MATHEMBEDDEFSFALSE\BACKSLASH begin{pmatrix}} \newcommandM{\endpmatrix}{\MATHEMBEDDEFSTRUE\BACKSLASH end{pmatrix}} \MATHEMBEDDEFSTRUE

\newcommand{\enablenowiki}{\renewcommand{\beginnowiki}{}\renewcommand{\endnowiki}{}} \newcommand{\disablenowiki}{\renewcommand{\beginnowiki}{}\renewcommand{\endnowiki}{}} \enablenowiki

\newcommand*{\EQUALREAD}{\EQUAL}

\newcommand{\%}{%} %%% zamienia znak \% na taki, ktory da sie przezyc

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{comment} Konwertowane z pliku LaTeX przez latex2mediawiki, zob. http://www.ii.uj.edu.pl/~pawlik1/latex2mediawiki.php. Niezb�dne rozszerzenia i modyfikacje oryginalnego latex2mediawiki wprowadzi� przykry@mimuw.edu.pl \end{comment} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Równania nieliniowe} \label{MN02}

W wielu zadaniach, m.in. matematyki stosowanej, spotykamy się z problemem rozwiązania skalarnego równania nieliniowego postaci $f(x) = 0$. Oto kilka przykładów:

\begin{example} Równanie Keplera \[ f(x) \equiv x - \epsilon \sin(x) - M = 0 \] jest bardzo ważne w astronomii, jego rozwiązanie pozwala wyznaczyć przyszłe położenie planety. Parametr $\epsilon$ odpowiada ekscentryczności orbity i przyjmuje wartości z przedziału $[0,1]$. Poza paru prostymi przypadkami, w ogólności równanie Keplera nie daje się rozwiązać w terminach funkcji elementarnych.

\biografia{Johann}{Kepler}{}

\end{example}

\begin{example} Znajdowanie miejsc zerowych wielomianu \[ f(x) \equiv a_nx^n + \ldots + a_1x + a_0 = 0. \] Bardzo wiele modeli matematycznych wymaga rozwiązania równania z wielomianową nieliniowością. Piękne \link{MN14}{MN14}{kwadratury} (Gaussa) opierają się na węzłach będących zerami pewnego wielomianu. Wielomiany są bardzo szczególnymi funkcjami i dla nich istnieje szereg wyspecjalizowanych metod znajdowania ich pierwiastków, m.in. metoda Laguerre'a, metoda Bairstow'a (o nich tu nie będziemy mówić), a także zaskakujące metody sprowadzające zadanie poszukiwania miejsc zerowych wielomianu do zupełnie innego zadania matematycznego --- o nich jednak będzie mowa dopiero w wykładzie dotyczącym \link{MN13}{MN13}{znajdowania wartości własnych macierzy}. \end{example}

\begin{example} Obliczanie pierwiastka kwadratowego z zadanej liczby $a$, czyli sposób na implementację funkcji ,,\lstC{sqrt()}. Można to zadanie wyrazić, jako rozwiązywanie równania \[ f(x) \equiv x^2 - a = 0. \] Szybkie algorytmy wyznaczania pierwiastka kwadratowego były znane już starożytnym. W wykładzie zrozumiemy, dlaczego \emph{metoda Herona},

%\biografia{}{Heron}{}

$$ x_{k+1} = \frac{1}{2}\left(x_k + \frac{a}{x_k}\right) $$ daje bardzo dobre przybliżenie $\sqrt{a}$ już po kilku iteracjach. \end{example}

\begin{example} Implementacja wyznaczania odwrotności liczby $a$ (\emph{bez} dzielenia!) jest możliwa, gdy odpowiednią metodą będziemy poszukiwać rozwiązania równania \[ f(x) \equiv \frac{1}{x} - a = 0. \] To zadanie jest ważne praktycznie, np. tak można poprawić precyzję \href{http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/21928.pdf}{funkcji wektorowych stosowanych w niektórych procesorach AMD}. Okazuje się, że instrukcja procesora służąca do równoległego obliczania odwrotności sekwencji liczb umieszczonych w 128-bitowym rejestrze wektorowym daje wynik z małą precyzją (oczywiście po to, by wykonywała się szybciej!). Jeśli taka dokładność wyniku nie odpowiada nam, możemy ją --- zgodnie z manualem procesora --- poprawić, rozwiązując właśnie takie równanie jak powyżej, metodą korzystającą wyłącznie z (wektorowych) operacji mnożenia i dodawania. \end{example}

\subsection{Bisekcja}

\emph{Metoda bisekcji}, czyli \emph{połowienia}, często stosowana w innych działach informatyki, jest dość naturalną metodą obliczania zer skalarnych funkcji ciągłych określonych na danym przedziale $[a,b]$ i zmieniających znak. Dokładniej, rozpatrzmy klasę funkcji

\begin{equation} \label{dfkl}

 F\,=\,\{\,f\in C([a,b])\,:\;f(a)\cdot f(b) < 0\,\},

\end{equation}

to znaczy $f \in F$ przyjmują w krańcach przedziału wartości przeciwnego znaku. Oczywiście, każda funkcja $f\in F$ ma, na mocy twierdzenia Darboux, co najmniej jedno zero w $[a,b]$. Startując z przedziału $[a,b]$, w kolejnych krokach metody bisekcji obliczamy informację o wartości $f$ w środku przedziału, co pozwala nam w następnym kroku zmniejszyć o połowę przedział, w którym na pewno znajduje się zero funkcji.

Bisekcję realizuje następujący ciąg poleceń, po wykonaniu którego $x$ jest przybliżeniem zera funkcji $f$ z zadaną dokładnością $\epsilon$. \begin{C}[Metoda bisekcji] lewy = a; prawy = b; flewy = f(lewy); fprawy = f(prawy); x = (a+b)/2; /* przybliżenie rozwiązania */ e = (b-a)/2; /* przedział lokalizujący rozwiązanie dokładne */ while (e > $\epsilon$) { fx = f(x); /* reszta */ if ( signbit(fx) != signbit(flewy) ) { prawy = x; fprawy = fx; } else { lewy = x; flewy = fx; } x = (lewy+prawy)/2; e = e/2; } \end{C}

(funkcja języka C \lstC{signbit} bada znak liczby rzeczywistej).

Z konstrukcji metody łatwo wynika, że po wykonaniu $k$ obrotów pętli \lstC{while} (czyli po obliczeniu $k+2$ wartości funkcji) otrzymujemy $x$, które odległe jest od pewnego rozwiązania $x^*$ o co najwyżej \begin{equation} \label{blbis}

 |x-x^*|\,\le\,\Big(\frac 12\Big)^k
                 \Big(\frac{b-a}{2}\Big).

\end{equation} Metoda bisekcji jest więc zbieżna \emph{liniowo} z ilorazem $1/2$. Choć ta zbieżność nie jest imponująca, bisekcja ma kilka istotnych zalet. Oprócz jej prostoty, należy podkreślić fakt, że bisekcja jest w pewnym sensie uniwersalna. Jeśli tylko dysponujemy dwoma punktami $a$ i $b$ takimi, że $f$ przyjmuje w nich wartości przeciwnych znaków, to metoda bisekcji z pewnością znajdzie miejsce zerowe funkcji, choćby początkowa długość przedziału $|b-a|$ była bardzo duża: zbieżność metody bisekcji jest \emph{globalna}. Co ważniejsze, dla zbieżności metody bisekcji wystarcza jedynie \emph{ciągłość} funkcji. Poza tym możemy łatwo kontrolować \emph{błąd bezwzględny aproksymacji miejsca zerowego}. Konsekwencją powyższego oszacowania błędu jest bowiem następujący wniosek.

\begin{cor} Dla znalezienia zera $x^*$ z dokładnością $\epsilon>0$, wystarczy obliczyć w metodzie bisekcji \[

  k\,=\,k(\epsilon)\,=\,
   \Big\lceil{\log_2\frac{(b-a)}{\epsilon}}\Big\rceil - 1 

\] wartości funkcji. \end{cor}

\subsection{Iteracja prosta Banacha}

Zupełnie inne, i jak się okaże --- przy odrobinie sprytu bardzo skuteczne --- podejście do wyznaczania miejsca zerowego jest oparte na \emph{metodzie Banacha}. Dla większej ogólności, będziemy zakładać teraz, że $f: D\rightarrow R^N$ i $D$ jest otwartym, niepustym podzbiorem $R^N$.

Najpierw nasze równanie nieliniowe

$$ f(x) = 0 $$

przekształcamy (dobierając odpowiednią funkcję $\phi$) do równania równoważnego (tzn. mającego te same rozwiązania) \begin{equation}\label{rrw}

  x\,=\,\phi( x). 

\end{equation}

Taki $x$, dla którego zachodzi powyższa równość, nazywamy \emph{punktem stałym} odwzorowania $\phi$.

Następnie, startując z pewnego przybliżenia początkowego $x_0 \in D$, konstruujemy ciąg kolejnych przybliżeń $x_k$ według wzoru \[

  x_k\,=\,\phi( x_{k-1}),\qquad k\ge 1.

\]

\biografia{Stefan}{Banach}{}

\begin{thm}[Banacha, o kontrakcji]\label{twit} Niech $D_0$ będzie domkniętym podzbiorem dziedziny $D$, \[

  \overline D_0\,=\,D_0\subset D, 

\] w którym $\phi$ jest odwzorowaniem zwężającym. To znaczy, $\phi(D_0)\subset D_0$, oraz istnieje stała $0\le L<1$ taka, że \[

 \|\phi( x)-\phi( y)\|\,\le\,L\,\| x- y\|,
    \qquad\forall x, y\in D_0.  

\] Wtedy równanie \begin{equation}\label{rrw}

  x\,=\,\phi( x). 

\end{equation}

ma dokładnie jedno rozwiązanie $ x^*$, oraz \[

  x^*\,=\,\lim_{k\to\infty} x_k, 

\] dla dowolnego przybliżenia początkowego $ x_0\in D_0$. \end{thm}

\begin{proof}Wobec \begin{eqnarray*} \| x_k- x_{k-1}\| &=& \|\phi( x_{k-1})-\phi( x_{k-2})\| \,\le\,L\,\| x_{k-1}- x_{k-2}\| \\ &\le &\cdots\;\le\;L^{k-1}\| x_1- x_0\|, \end{eqnarray*} dla $k\ge s$ mamy \begin{eqnarray*} \| x_k- x_s\| &&\le \sum_{j=s+1}^k\| x_j- x_{j-1}\| \,\le\,\sum_{j=s+1}^k L^{j-1}\| x_1- x_0\| \\ &&= L^s(1+L+\cdots+L^{k-s-1})\| x_1- x_0\| \,\le\,\frac{L^s}{1-L}\| x_1- x_0\|. \end{eqnarray*} Ciąg $\{ x_k\}_k$ jest więc ciągiem Cauchy'ego. Stąd istnieje granica $\alpha=\lim_{k\to\infty} x_k$, która należy do $D_0$, wobec domkniętości tego zbioru. Ponieważ lipschitzowskość $\phi$ implikuje jej ciągłość, mamy też \[

 \phi(\alpha)\,=\,\phi\Big(\lim_{k\to\infty} x_k\Big) 
  \,=\,\lim_{k\to\infty}\phi( x_k)
  \,=\,\lim_{k\to\infty} x_k\,=\,\alpha,

\] tzn. $\alpha$ jest punktem stałym odwzorowania $\phi$. Dla jednoznaczności zauważmy, że jeśliby istniał drugi, różny od $\alpha$, punkt stały $\beta$, to mielibyśmy \[

 \|\alpha-\beta\|\,=\,
  \|\phi(\alpha)-\phi(\beta)\|
  \,\le\,L\,\|\alpha-\beta\|. 

\] Stąd $1<L$, co jest sprzeczne z założeniem, że $\phi$ jest zwężająca. \end{proof}

Z powyższych rozważań otrzymujemy natychmiastowy wniosek dotyczący zbieżności iteracji prostych.

\begin{cor} Przy założeniach \link{#Banacha, o kontrakcji}{twit}{twierdzenia Banacha}, metoda iteracji prostych jest zbieżna co najmniej liniowo z ilorazem $L$, tzn. \[

 \| x_k- x^*\|\,\le\,L^k\,\| x_0- x^*\|.

\] \end{cor}

\begin{example} Dla ilustracji, rozpatrzmy równanie Keplera, gdy $\epsilon < 1$: \begin{equation}\label{itp}

 x\,=\,M+\epsilon\sin(x), \qquad\mbox{dla}\qquad x\in R. 

\end{equation}

\rysunek{rownaniekeplera.png}{Graficzna ilustracja równania Keplera dla $M=1$ i $\epsilon = \frac{1}{4}$.}

W tym przypadku $\phi(x)=M+\epsilon\,\sin(x)$. Zauważmy, że w funkcja $\phi$ jest zwężająca ze stałą \[

 L \leq \max_{x} |\phi'(x)| \leq \epsilon < 1.

\] Ponieważ obrazem prostej przy przekształceniu $\phi$ jest odcinek $D = [M-\epsilon, M+\epsilon]$, to znaczy, że $\phi$ --- ograniczona do $D$ --- spełnia założenia \link{#Banacha, o kontrakcji}{twit}{twierdzenia Banacha o kontrakcji}. Stąd istnieje dokładnie jedno rozwiązanie naszego równania w przedziale $D$. Rozwiązanie to może być aproksymowane z dowolnie małym błędem przy pomocy iteracji prostych, startując z dowolnego przybliżenia początkowego $x_0\in D$. Jednak, gdy $\epsilon \approx 1$, zbieżność może być bardzo powolna... (Wkrótce przekonasz się, że są szybsze metody). \end{example}

Zaletą iteracji prostych jest fakt, że zbieżność nie zależy od wymiaru $n$ zadania, ale tylko od stałej Lipschitza $L$ (jednak w praktyce czasem sama stała Lipschitza może zależeć od wymiaru zadania...). Metoda Banacha ma szczególne zastosowanie w przypadku, gdy funkcja $\phi$ jest zwężająca na całym zbiorze $D$, tzn. $D_0=D$. Jeśli ponadto $D$ ma skończoną średnicę, $\mbox{diam}(D) < +\infty$, to dla osiągnięcia $\epsilon$-aproksymacji zera funkcji $f$ wystarczy wykonać \[

 k\,=\,k(\epsilon)\,=\,\Big\lceil\frac
 {\log(\| x_0- x^*\|/\epsilon)}{\log(1/L)}\Big\rceil 
  \,=\,\Big\lceil\frac
  {\log(\mbox{diam}(D)/\epsilon)}{\log(1/L)}\Big\rceil 

\] iteracji, niezależnie od $x_0$. Metody zbieżne dla dowolnego przybliżenia początkowego nazywamy \emph{zbieżnymi globalnie}. Obie przedstawione dotychczas metody: bisekcji i Banacha, przy rozsądnych założeniach, są zbieżne globalnie.

Okazuje się, że metoda iteracji prostej może być --- w bardzo szczególnych przypadkach --- zbieżna szybciej niż liniowo. Z taką sytuacją będziemy mieli do czynienia, gdy rozpatrzymy metodę Newtona.

\subsection{Metoda Newtona}

Zarówno metoda Banacha, jak i bisekcja, są zbieżnie liniowo, co w praktyce może okazać się zbieżnością dość powolną (np. dla metody zbieżnej liniowo z ilorazem $1/2$ dopiero po piątej iteracji dostajemy kolejną dokładną cyfrę wyniku). Wykorzystując więcej informacji o funkcji $f$, której miejsca zerowego poszukujemy, możemy istotnie przyspieszyć zbieżność metody. Ceną, jaką przyjdzie nam zapłacić, będzie utrata globalnej zbieżności.

\biografia{Isaac}{Newton}{}

W dalszych rozważaniach będziemy zakładać dla uproszczenia, że dziedzina $D=\R$.

Idea \emph{metody Newtona} opiera się na popularnym wśród inżynierów pomyśle {\em linearyzacji}: zamiast szukać miejsca zerowego skomplikowanej $f$, przybliżmy ją linią prostą, a dla niej już umiemy znaleźć miejsce zerowe!

\begin{latexonly} Przypisywanie metody stycznych Newtonowi jest pewną przesadą. Metodę Newtona taką, jaką znamy (z pochodną w mianowniku), zaproponował w 1740 roku Simpson (ten od kwadratury), kilknaście lat po śmierci Newtona. Żeby było jeszcze zabawniej, odkrywcą metody siecznych zdaje się być... Newton! Więcej na ten temat przeczytasz w artykule T.Ypma w SIAM Review 37, 1995. \end{latexonly} Startując z pewnego przybliżenia początkowego $x_0$, w kolejnych krokach metody, $k$-te przybliżenie $x_k$ jest punktem przecięcia stycznej do wykresu $f$ w punkcie $x_{k-1}$. Ponieważ równanie stycznej wynosi $y(x)=f(x_{k-1})+f'(x_{k-1})(x-x_{k-1})$, otrzymujemy wzór

\begin{alg}[Metoda Newtona (stycznych)] for k = 1,2,... $x_k\,=\,x_{k-1}\,-\,\frac{f(x_{k-1})}{f'(x_{k-1})}$; \end{alg}

Oczywiście, aby metoda Newtona była dobrze zdefiniowana, musimy założyć, że $f'(x_{k-1})$ istnieje i nie jest zerem.

\begin{latexonly} \rysunek{newtononestep.png}{Metoda Newtona: pierwszy krok} \end{latexonly}

\flash{Newtononestep.swf}{Postęp iteracji Newtona}

Zauważmy, że metodę Newtona można traktować jako szczególny przypadek iteracji prostych, gdzie \[

 \phi(x)\,=\,x-\frac{f(x)}{f'(x)}. 

\] Widać też, że nie jest ona zbieżna globalnie.

Metoda Newtona i jej podobne należą do grupy metod \emph{zbieżnych lokalnie}. Znaczy to, że zbieżność ciągu $\{x_k\}_k$ do zera danej funkcji $f$ jest zapewniona jedynie wtedy, gdy przybliżenia początkowe zostały wybrane dostatecznie blisko $x^*$.

Nawet jeśli pochodna w $x_{k-1}$ się nie zeruje, ciąg $\{x_k\}_k$ może nie zbiegać do zera funkcji $f$. Okazuje się jednak, że jeśli wystartujemy dostatecznie blisko rozwiązania $x^*$, to metoda Newtona jest zbieżna. Dokładniej, załóżmy najpierw, że \[ f(x^*)=0\quad \mbox{ oraz }\quad f'(x^*)\,\ne\,0. \] Ponadto załóżmy, że $f$ jest dwukrotnie różniczkowalna w sposób ciągły, $f\in C^2(D)$. Rozwijając $\phi$ w szereg Taylora w punkcie $x^*$, otrzymujemy \[

 x_k-x^*\,=\,\phi(x_{k-1})-\phi(x^*)\,=\,
 (x_{k-1}-x^*)\phi'(x^*)+(x_{k-1}-x^*)^2\phi(\xi_k)/2, 

\] gdzie $\min(x^*,x_{k-1})\le\xi_k\le\max(x^*,x_{k-1})$. Wobec tego, że $\phi'(x^*)=f(x)f(x)/(f'(x))^2=0$ i $\phi(\xi_k)=f(\xi_k)/f'(\xi_k)$, mamy \begin{equation}\label{nrpdst}

 x_k-x^*\,=\,(x_{k-1}-x^*)^2\frac{f(\xi_k)}{2f'(\xi_k)}.

\end{equation} Zdefiniujmy liczbę \[

 R_f\,=\,\sup_{r\ge 0}\sup_{\{x:|x-x^*|\le r\}}
  \Big|\frac{2(x-x^*)f(x)}{f'(x)}\Big|\,<\,1. 

\] Oczywiście $R_f>0$. Dla $x_{k-1}$ spełniającego $|x_{k-1}-x^*|\le R<R_f$, mamy z poprzedniej równości \[

 |x_k-x^*|\,\le\,q\,|x_{k-1}-x^*|,

\] gdzie $q<1$ i $q$ zależy tylko od $R$.

Niech teraz $x^*$ będzie zerem $m$-krotnym, \[

 f(x^*)=f'(x^*)=\cdots =f^{(m-1)}(x^*)=0\ne f^{(m)}(x^*),

\] gdzie $m\ge 2$, oraz niech $f$ będzie $m$-krotnie różniczkowalna w sposób ciągły. Wtedy \begin{eqnarray}

 x_k-x^* &=& (x_{k-1}-x^*)\,-\,\frac{(x_{k-1}-x^*)^m
  \frac{f^{(m)}  (\eta_k^{(1)})}{m!}}{(x_{k-1}-x^*)^{m-1}
  \frac{f^{(m-1)}(\eta_k^{(2)})}{(m-1)!}} \nonumber \\
  &=& (x_{k-1}-x^*)\left(1-\frac 1m\frac
      {f^{(m)}(\eta_k^{(1)})}{f^{(m)}(\eta_k^{(2)})}\right) \nonumber \\

&\approx & (x_{k-1}-x^*)\Big( 1-\frac 1m\Big),\label{nrtp} \end{eqnarray} o ile $x_{k-1}$ jest ``blisko $x^*$.

Metoda Newtona jest więc zbieżna lokalnie. Gdy $x_0$ jest zbyt daleko od rozwiązania może zdarzyć się, że iteracja Newtona zacznie nas oddalać od miejsca zerowego, co ilustruje poniższy przykład:

\begin{latexonly} \rysunek{newtononestepdiv.png}{Metoda Newtona: jeśli startujemy zbyt daleko od miejsca zerowego $f$, zamiast przybliżać się do niego, zaczynamy się oddalać! (gdzie będzie $x_3$?...)} \end{latexonly}

\flash{Newtononestepdiv.swf}{Metoda Newtona: jeśli startujemy zbyt daleko od miejsca zerowego $f$, zamiast przybliżać się do niego, zaczynamy się oddalać! (gdzie będzie $x_3$?...)}

Z powyższego można też wywnioskować, jaki jest charakter zbieżności metody Newtona. Dla zera jednokrotnego $x^*$ oraz $f(x^*)\ne 0$ mamy bowiem \[

 |x_k-x^*|\, \approx \,|x-x_{k-1}|^2 \frac{|f(x^*)|}{2|f'(x^*)|}.

\]

Mówimy, że zbieżność metody Newtona, gdy $f(x^*)\neq 0$ jest \emph{kwadratowa}.

\begin{prop} Jeśli $f(x^*)\neq 0$ oraz $f(x^*)=0$ to zbieżność jest nawet szybsza. Z kolei dla zera $m$-krotnego (tzn. $f(x^*) = f'(x^*)= \ldots f^{(m)}(x^*)= 0$, $m>1$) zbieżność jest liniowa z ilorazem $(1-\frac{1}{m})$. \end{prop}

Metoda Newtona jest pierwszą poznaną tutaj metodą iteracyjną, która jest (dla zer jednokrotnych) zbieżna szybciej niż liniowo. Dla takich metod wprowadza się pojęcie \emph{wykładnika zbieżności}, który jest zdefiniowany następująco.

\rysunek{stycznebisekcja.png}{Porównanie zbieżności metody bisekcji i stycznych dla równania $e^x - 1 = 0$. Błąd kolejnych przybliżeń wyświetlany jest w skali logarytmicznej, dzięki czemu lepiej widać różnicę między zbieżnością liniową a kwadratową.}

Powiemy, że metoda iteracyjna $\phi$ jest w klasie funkcji $F$ \emph{rzędu co najmniej $p\ge 1$}, gdy spełniony jest następujący warunek. Niech $f\in F$ i $f(x^*)=0$. Wtedy istnieje stała $C<\infty$ taka, że dla dowolnych przybliżeń początkowych $x_0,\ldots,x_{s-1}$ dostatecznie bliskich $x^*$, kolejne przybliżenia $x_k=\phi(x_{k-1},\ldots,x_{k-s})$ generowane tą metodą spełniają \[

 |x_k-x^*|\,\le\,C\,|x_{k-1}-x^*|^p.

\] Ponadto, jeśli $p=1$ to dodatkowo żąda się, aby $C<1$.

\begin{dfn} \emph{Wykładnikiem zbieżności} metody iteracyjnej $\phi$ w klasie $F$ nazywamy liczbę $p^*$ zdefiniowaną równością \[

 p^*\,=\,\sup\,\{\,p\ge 1:\,\phi 
   \mbox{ jest rzędu co najmniej  } p\,\}.

\] \end{dfn}

Możemy teraz sformułować następujące twierdzenie, które natychmiast wynika z poprzednich rozważań.

\begin{thm}[O rzędzie zbieżności metody Newtona] Wykładnik zbieżności metody Newtona (stycznych) wynosi $p^*=2$ w klasie funkcji o zerach jednokrotnych, oraz $p^*=1$ w klasie funkcji o zerach wielokrotnych. \end{thm}

\rysunek{multiplezeros.png}{Zbieżność metody Newtona dla zer wielokrotnych $f(x) = (x-1)^5$ jest liniowa z ilorazem $\frac{4}{5}$ (końcowe załamanie wykresu spowodowane jest przypadkowym trafieniem w dokładne miejsce zerowe). Metoda bisekcji nie jest na to czuła i dalej zbiega z ilorazem $\frac{1}{2}$.}

\subsection{Metoda siecznych}

Inną znaną i często używaną metodą iteracyjną, opartą na podobnym pomyśle linearyzacyjnym co metoda Newtona, jest \emph{metoda siecznych}, w której zamiast przybliżenia wykresu $f$ przez styczną, stosuje się przybliżenie sieczną.

Metoda ta wykorzystuje więc do konstrukcji $x_k$ przybliżenia $x_{k-1}$ i $x_{k-2}$. Musimy również wybrać dwa różne punkty startowe $x_0$ i $x_1$. Ponieważ sieczna dla $f$ w punktach $x_{k-1}$ i $x_{k-2}$ ma wzór \[

 y(x)\,=\,\frac{x-x_{k-2}}{x_{k-1}-x_{k-2}}f(x_{k-1})+
          \frac{x-x_{k-1}}{x_{k-2}-x_{k-1}}f(x_{k-2}),

\] otrzymujemy \begin{alg}[Metoda siecznych] for k = 1,2,... $x_k\,=\,x_{k-1}\,-\,\frac{x_{k-1}-x_{k-2}} {f(x_{k-1})-f(x_{k-2})}\,f(x_{k-1})$; end \end{alg}

Zauważmy, że jeśli $x_{k-1}$ i $x_{k-2}$ są blisko siebie, to $x_k$ jest podobny do tego z metody Newtona, bowiem wtedy iloraz różnicowy \link{MN14#Różniczkowanie}{MN14}{przybliża pochodną} $f$, $$ \frac{f(x_{k-1})-f(x_{k-2})}{x_{k-1}-x_{k-2}} \approx f'(x_{k-1}). $$

Nie wystarcza to jednak, aby osiągnąć zbieżność z wykładnikiem $2$. Można pokazać, że przy podobnych założeniach o funkcji, wykładnik zbieżności metody siecznych dla zer jednokrotnych i dostatecznie gładkich funkcji wynosi $p^*=\frac{1+\sqrt{5}}{2}=1.618\ldots$. Jako wariant metody Newtona, metoda siecznych jest również zbieżna lokalnie.

\rysunek{stycznesiecznebisekcja.png}{Porównanie zbieżności metody bisekcji, stycznych i siecznych dla równania $e^x - 1 = 0$. Błąd kolejnych przybliżeń wyświetlany jest w skali logarytmicznej.}

Niewątpliwą zaletą metody siecznych jest jednak to, że \emph{nie wymaga obliczania pochodnej funkcji} (bywa, że dokładne wyznaczenie pochodnej jest niemożliwe, gdy np. funkcja jest zadana zewnętrzną procedurą, do której kodu źródłowego nie mamy dostępu; zwykle też koszt obliczenia wartości pochodnej jest wyższy od kosztu obliczenia wartości funkcji). Jest to również istotne w pakietach numerycznych, gdzie czasem nie chcemy wymagać od użytkownika czegokolwiek, oprócz podania wzoru na funkcję i przybliżonej lokalizacji miejsca zerowego.

Ponadto, często zdarza się, że wyznaczenie wartości pochodnej, $f'(x_k)$, jest tak samo, albo i bardziej kosztowne od wyznaczenia wartości $f(x_k)$. W takim wypadku okazuje się, że metoda stycznych --- choć wolniej zbieżna niż metoda stycznych --- dzięki temu, że jej iteracja wymaga jedynie wyznaczenia jednej wartości $f$, jest \emph{bardziej efektywna} od metody Newtona: koszt osiągnięcia zadanej dokładności jest w takim przypadku mniejszy od analogicznego kosztu dla metody Newtona.

Jednak gdy żądane przez użytkownika dokładności są bardzo wielkie, a sama funkcja ,,złośliwa, metoda siecznych może cierpieć z powodu redukcji cyfr przy odejmowaniu.

\subsection{Metoda Brenta}

Naturalnie, uważny student zaczyna zadawać sobie pytanie, czy nie można w jakiś sposób połączyć globalnej zbieżności metody bisekcji z szybką zbieżnością metody siecznych tak, by uzyskać metodę zbieżną globalnie, a jednocześnie istotnie szybciej niż liniowo.

Okazuje się, że można to zrobić, wprowadzając metodę opartą na {\em trzech} punktach lokalizujących miejsce zerowe: dwóch odcinających zero tak jak w metodzie bisekcji i trzecim, konstruowanym np. jak w metodzie stycznych. W kolejnej iteracji wymieniamy jeden z punktów albo wedle metody siecznych (i wtedy zapewne szybciej zbliżamy się do zera), albo wykonując bisekcję (aby zagwarantować sobie, że w wiadomym przedziale miejsce zerowe rzeczywiście się znajduje).

Ten prosty pomysł \emph{metody hybrydowej} wymaga jednak subtelnego dopracowania. Zostało to zrobione w 1973 roku przez \href{http://www.rpbrent.com}{Richarda Brenta}. %\biografia{Richard}{Brent}{} Funkcja MATLABa (i Octave'a) \lstoct{fzero} implementują właśnie metodę Brenta. Autorem implementacji w Octave jest ówczesny student \href{http://www.mimuw.edu.pl}{matematyki} na Uniwersytecie Warszawskim, Łukasz Bodzon. Fortranowski kod metody Brenta można znaleźć także w \href{http://www.netlib.org/go/zeroin.f}{Netlibie}. Inną funkcją Octave'a służącą rozwiązywaniu równań nieliniowych jest \lstoct{fsolve}:

\begin{outoct} octave:1> [X, MSG, INFO] = fsolve ('cos', 1) X = 1.5708 MSG = 1 INFO = solution converged within specified tolerance

octave:2> cos(X) ans = 6.1230e-17 \end{outoct}

\subsection{Metody dla układów równań nieliniowych}

Niektóre z poznanych metod można łatwo rozszerzyć na przypadek układu $N$ równań z $N$ niewiadomymi, to znaczy \[ F(x) = 0, \] gdzie $F: R^N \rightarrow R^N$.

\subsubsection{Metoda Banacha}

Jak pamiętamy, \link{#Banacha, o kontrakcji}{twit}{metodę Banacha} sformułowaliśmy od razu dla zagadnienia wielowymiarowego. Analiza i własności metody są zatem już \link{#Banacha, o kontrakcji}{twit}{omówione}.

\subsubsection{Wielowymiarowa metoda Newtona} \label{sec:multinewton}

Okazuje się, że metodę Newtona można uogólnić na przypadek układu $N$ równań nieliniowych z $N$ niewiadomymi. Zapiszmy wzór na skalarną metodę Newtona odrobinę inaczej: \[ x_{k+1} = x_k - [F'(x_k)]^{-1}\, F(x_k). \]

Niezwykłe jest, że taki wzór nie tylko ma sens w przypadku, gdy $F: R^N \rightarrow R^N$ (wtedy $F'(x_k)$ jest macierzą Jakobianu $F$ w punkcie $x_k$), ale dodatkowo ta metoda zachowuje wszystkie własności metody stycznych dla przypadku skalarnego:

\begin{thm}[O zbieżności wielowymiarowej metody Newtona] Załóżmy, że $F: R^N \rightarrow R^N$ i istnieje $x^* \in R^N$ taki, że \[ F(x^*) = 0. \] Załóżmy ponadto, że $F$ jest różniczkowalna, a jej pochodna $F': R^N \rightarrow R^{N\times N}$ jest lipschitzowska i dodatkowo \[ F'(x^*) \mbox{ jest nieosobliwa}. \] Wówczas, jeśli tylko $x_0$ jest dostatecznie blisko rozwiązania $x^*$, to ciąg kolejnych przybliżeń $x_k$, generowany wielowymiarową metodą Newtona, jest zbieżny do $x^*$. Co więcej, szybkość zbieżności jest kwadratowa. \end{thm}

\subsubsection{Implementacja wielowymiarowej metody Newtona}

Implementując wielowymiarową metodę Newtona, musimy dysponować nie tylko funkcją obliczającą $N$ współrzędnych wektora wartości $F$, ale także funkcją wyznaczającą $N^2$ elementów macierzy pochodnej $F$ w zadanym punkcie $x \in R^N$. Zwróćmy uwagę na to, że w implementacji metody nie trzeba wyznaczać $F'(x_k)^{-1}$, tylko rozwiązać układ równań:

\begin{alg}[Wielowymiarowa metoda Newtona] while (!stop) { rozwiąż (względem $s$) układ równań liniowych $F'(x_k)\, s = -F(x_k)$; $x_{k+1}$ = $x_k$ + $s$; } \end{alg}

O tym, \link{MN05}{MN05}{jak skutecznie rozwiązywać układy równań liniowych}, dowiesz się z kolejnych wykładów. Dowiesz się także, dlaczego \textit{nie należy} w implementacji korzystać z wyznaczonej \textit{explicite} macierzy odwrotnej do macierzy Jakobianu.

\literatura{3}

Rozdziały 3.5 i 3.6 nie są obowiązkowe.

Wiele wariantów metod rozwiązywania \emph{układów} równań nieliniowych jest przedstawionych w znakomitej monografii \ksiazka{C.T.Kelley}{Iterative Solution of Systems of Linear and Nonlinear Equations}{SIAM, 1995.}

Opis metody Brenta znajdziesz w książce \ksiazka{R. Brent}{Algorithms for Minimization Without Derivatives}{Prentice-Hall, 1973.}