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}{
- {###{#2\PIPE \PIPE \PIPE
} \newcommand{\begin#1}[1]{
- {###{#2\PIPE ##1\PIPE ##1\PIPE
} \newcommand{\end#1}{###}###}
} }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\maketemplatealg}[2]{
\newcommand{\begin#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}{
} \newcommand{#\#1}[1]{
} }
\newcommand{\makehidersmall}[2]{ \newcommand{\begin#1}{
} \newcommand{#\#1}[1]{
} }
\newcommand{\maketemplate2}[2]{
\newcommand{\begin#1}{
- {###{#2\PIPE \PIPE
} \newcommand{\begin#1}[1]{
- {###{#2\PIPE ##1\PIPE
} \newcommand{\end#1}{###}###}
} \newcommand{#\#1}[1]{
- {###{#2\PIPE \PIPE
- 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}
\EATWS}
\newcommand{\endC}{}
\newcommand{\beginF}{\NOCOMMENT\EATWS}
\newcommand{\endF}{}
\newcommand{\beginoct}{\NOCOMMENT\EATWS}
\newcommand{\endoct}{}
\newcommand{\beginux}{}
\newcommand{\beginmake}{\NOCOMMENT}
\newcommand{\endmake}{}
\newcommand{\beginoutoct}{}
\newcommand{\beginoutux}{}
%\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*{\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{\beginbadquote}{} \newcommand{\endquote}{
}} \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}{}
- {\PIPE border\EQUAL 1
\PIPE + \PIPE - \PIPE \EATWS }
\renewcommand*{\begintabular}[2]{ \TABULARMODE \renewcommand*{\\}{ \PIPE - \PIPE \EATWS } \renewcommand*{\hline}{}
- {\PIPE border\EQUAL 1
\PIPE + Uzupelnij tytul \PIPE - \PIPE \EATWS }
\renewcommand*{\begintabular*}[3]{ \TABULARMODE \renewcommand*{\\}{ \PIPE - \PIPE \EATWS } \renewcommand*{\hline}{}
- {\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.}
