\documentclass[10pt,a4paper]{article}

%% Polonizacja
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{polski}
\usepackage{indentfirst}

%% Wzorki matematyczne
\usepackage{amsmath,amsfonts}

%% Twierdzenia
\newtheorem{thm}{Twierdzenie}[section]
\newtheorem{df}{Definicja}[section]

\DeclareMathOperator{\sign}{sign}

\newcommand*{\abs}[1]{\lvert #1 \rvert}

\begin{document}

\newcounter{seria}
\setcounter{seria}{8}
% 1 - wstęp, dokładność numeryczna
% 2 - wielomiany
% 3 - interpolacja wielomianowa
% 4 - współczynniki wielomianu interpolującego
% 5 - splines
% 6 - kwadratury Gaussa
% 7 - całkowanie: metoda trapezów, Romberga, całkowanie wielowymiarowe
% 8 - rozwiązywanie równań nieliniowych
\newcommand*{\preparedby}{Jakub Narębski}
\input{naglowek.tex}


\section{Znajdowanie miejsc zerowych}
\label{sec:glowna}

\subsection{Wstęp}
\label{sec:wstep}

Chcemy znaleźć rozwiązanie równania danego w~postaci
\begin{equation}
  \label{eq:rownanie}
  f(x) = 0
\end{equation}
(każde równanie jednej zmiennej możemy zapisać w~tej postaci).

Algorytmy znajdowania miejsc zerowych możemy podzielić na dwa
rodzaje.  Metody pierwszego rodzaju zaczynają od \emph{przedziału},
o~którym wiadomo że zawiera pierwiastek (rozwiązanie) równania.
W~kolejnych iteracjach przedział ten jest zmniejszany aż do osiągnięcia
pożądanej dokładności.  Mamy zatem ścisłe oszacowanie błędu.

Metody drugiego rodzaju \emph{poprawiają} odgadnięte (lub obliczone)
przybliżenie rozwiązania równania.  Zazwyczaj wymagają one spełnienia
dodatkowych warunków (np. bliskości pierwiastka), ale są szybciej
zbieżne.  Część metod tego typu oprócz $f(x)$ wymaga obliczania
wartości pochodnej $f'(x)$.

\begin{df}
  \label{def:wykladnik-zbieznosci}
  Niech \(\epsilon_k = \abs{x^\ast - x_k}\) oznacza błąd danego
  algorytmu w~$k$--tym kroku ($f(x^\ast) = 0$).  Mówimy, że $p$ jest
  \textbf{wykładnikiem zbieżności} danej metody, jeżeli
  \begin{equation}
    \label{eq:def:wykladnik-zbieznosci}
    \epsilon_{k+1} <= K \epsilon_k^p.
  \end{equation}
  Jeżeli $p = 1$ to mówimy, że metoda jest \emph{zbieżna liniowo}.
  Natomiast gdy $p > 1$ to metoda jest \emph{zbieżna ponadliniowo}.
\end{df}

\begin{thm}[Bolzano -- Cauchy'ego]
  \label{thm:Cauchy}
  Niech funkcja $f(x)$ będzie kreślona i~ciągła na przedziale
  domkniętym $[a, b]$ i~niech na końcach tego przedziału przyjmuje
  wartości różnych znaków: $f(a)f(b) < 0$.  Wówczas istnieje punkt $c
  \in [a, b]$, w~którym funkcja się zeruje: $f(c) = 0$.
\end{thm}


\subsection{Metody używające tylko wartości funkcji}
\label{sec:f}


\subsubsection{Metoda bisekcji}
\label{sec:bisekcja}

Pomysł jest prosty.  Wiemy, że w~jakimś przedziale $[a, b]$ funkcja
zmienia znak.  Dzielimy ten przedział na pół (stąd nazwa) i~wybieramy
ten z~podprzedziałów, w~którym znajduje się pierwiastek (na którego
końcach funkcja ma przeciwne znaki).  Jeśli oznaczymy przez $[x^L_k,
x^R_k]$ przedział otrzymany w~$k$--tym kroku, zaś przez $c = (x^L_k +
x^R_k)/2$ środek przedziału, to
\begin{equation}
  \label{eq:bisekcja}
  x^L_{k+1} = 
  \begin{cases}
    x^L_{k+1} &\text{jeżeli\ } f(x^L_k)f(c) < 0 \\
    c         &\text{jeżeli\ } f(x)f(x^R_k) < 0
  \end{cases}.
\end{equation}

Metoda ta jest zbieżna \emph{liniowo}, dla tej metody
\(\varepsilon_{k+1} = \frac{1}{2} \varepsilon_k\).  Metoda ta działa
\emph{zawsze}, jeśli mamy przynajmniej jeden pierwiastek w~zadanym
przedziale.


\subsubsection{Metoda fałszywej pozycji (regula falsi)}
\label{sec:regula-falsi}

W~metodzie tej zamiast środka przedziału jako przybliżenie pierwiastka
bierzemy pierwiastek interpolacji liniowej na krańcach przedziału,
czyli punkt przecięcia \emph{siecznej} z~osią $x$.  
\begin{equation}
  \label{eq:regula-falsi}
  c = x^L_k - \frac{x^L_k - x^R_k}{f(x^L_k) - f(x^R_k)} f(x^L_k)  
\end{equation}
Nastepnie tak jak w~metodzie bisekcji bierzemy ten przedział, który
zawiera pierwiastek.  Można ją także traktować jako metodę Newtona
(patrz~\ref{sec:Newtona}) z~pochodną zamienioną przez iloraz różnicowy
oparty o~krańce przedziału.

Metoda ta jest zbieżna \emph{liniowo}, ale zazwyczaj jest szybsza od
metody bisekcji. 


\subsubsection{Metoda fałszywej pozycji bez pamięci}
\label{sec:regula-falsi-bezpamieci}

W~tej modyfikacji metody fałszywej pozycji zawsze przeprowadzamy
sieczną przez jeden ustalony punkt
\begin{equation}
  \label{eq:regula-falsi-bezpamieci}
  x_{k+1} = x_k - \frac{x_k - a}{f(x_k) - a} f(x_k).
\end{equation}

Metoda ta jest zbieżna \emph{liniowo} o~ile $a$ leży dostatecznie
blisko pierwiastka.


\subsubsection{Metoda secant}
\label{sec:secant}

Metoda secant różni się od metody fałszywej pozycji tym, że jako
następne przybliżenie bierzemy \emph{zawsze} punkt przecięcia siecznej
z~osią $x$.
\begin{equation}
  \label{eq:secant}
  x_{k+1} = x_k - \frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})} f(x_k).
\end{equation}

Metoda ta jest zbieżna z~wykładnikiem $p = (1 + \sqrt{5})/2 \approx
1.618$, ale nie mamy gwarancji zbieżności metody.


\subsection{Metody używające funkcji i jej pochodnej}
\label{sec:f-df}

\subsubsection{Metoda Newtona}
\label{sec:Newtona}

Kolejne przybliżenie miejsca zerowego otrzymujemy jako punkt
przecięcia \emph{stycznej} do funkcji w~poprzednim punkcie z~osią
$x$.
\begin{equation}
  \label{eq:Newton}
  x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}.
\end{equation}

Metoda ta jest zbieżna \emph{kwadratowo}, tzn. wykładnik zbieżności 
$p = 2$.  Metodę tę można uczynic pewną, łącząc ją z~metodą bisekcji
(podobnie jak w~metodzie Brendta~\ref{sec:Brendt}).

Zwana czasami metodą Newtona--Rhapsona.

\subsection{Metody interpolacyjne}
\label{sec:metody-interpolacyjne}

\subsubsection{Metoda Riddersa}
\label{sec:Ridders}

Jest to jeden z~wariantów metody fałszywej pozycji.  Niech miejsce
zerowe znajduje się pomiędzy punktami $x_1$ i~$x_2$.  Metoda Riddersa
najpierw oblicza wartość funkcji pośrodku przedziału $x_3 = (x_1 +
x_2)/2$.  Nastepnie szukamy czynnika $e^Q$ spełniającego równanie
\begin{equation}
  \label{eq:Ridders:1}
  f(x_1) - 2 f(x_3) e^Q + f(x_2) e^{2 Q} = 0.
\end{equation}
Jest to równanie kwadratowe.  Jego rozwiązanie można zapisać w~postaci
\begin{equation}
  \label{eq:Ridders:2}
  e^Q = \frac{f(x_3) + \sign[f(x_2)] \sqrt{f(x_3)^2 - f(x_1)f(x_2)}}{f(x_2)}.
\end{equation}
Stosujemy nastepnie metodę fałszywej pozycji do punktów \(f(x_1),
f(x_3)e^Q, f(x_2)e^{2 Q}\) (zamiast do \(f(x_1), f(x_3), f(x_2)\)).
Pełne rozwiązanie dane jest wzorem
\begin{equation}
  \label{eq:Ridders}
  x_4 = x_3 + (x_3 - x_1)
  \frac{\sign[f(x_1) - f(x_2)]f(x_3)}%
       {\sqrt{f(x_3)^2 - f(x_1)f(x_2)}}.
\end{equation}

Metoda ta jest zbieżna \emph{kwadratowo}, a~biorąc pod uwagę fakt
potrzeby dwukrotnego obliczania wartości funkcji z~rzędem $p =
\sqrt{2}$.  $x_4$ zawsze należy do przedziału $[x_1, x_2]$, a~więc
metoda ta jest pewna.  Metoda ta ,,intepoluje'' funkcję za pomocą
czynników wykładniczych.


\subsubsection{Metoda Brenta--Dekkera}
\label{sec:Brendt}

Metoda ta łączy w~sobie odwrotną interpolację kwadratową z~algorytmem
bisekcji.  W~każdej iteracji metoda Brendta przybliża funkcję za
pomocą krzywej interpolacyjnej.  W~pierwszym kroku jest to liniowa
interpolacja oparta o~krańce przedziału.  W~następnych krokach używamy
odwrotnej (tzn. na wielomian jako funkcję od $y$) interpolacji
kwadratowej opartej na ostatnich trzech punktach.  Jeżeli punkt
przecięcia krzywej interpolacyjnej z~osią $x$ leży wewnątrz przedziału
zawierającego na pewno pierwiastek, to jest używany do zmniejszenia
przedziału zawierającego na pewno pierwiastek.  W~przeciwnym przypadku
stosujemy jeden krok metody bisekcji.

Metoda ta jest pewna, w~większości przypadków zbieżna
\emph{kwadratowo}.


\subsection{Szacowanie błędu rozwiązania}
\label{sec:szac-bledu}

Niech $\mathit{epsabs}$ oznacza błąd bezwzględny, a~$\mathit{epsrel}$
błąd względny.  Jeżeli $0 \notin [a, b]$ to jako warunek zatrzymania
dla metod \emph{zmniejszających przedział} możemy wziąść
\begin{equation}
  \label{eq:test_interval}
  \abs{a - b} < \mathit{epsabs} + \mathit{epsrel} \min(\abs{a}, \abs{b}).
\end{equation}
Dla metod \emph{iteracyjnych} jako warunek zakończenia możemy wziąść
\begin{equation}
  \label{eq:test_delta}
  \abs{x_k - x_{k-1}} < \mathit{epsabs} + \mathit{epsrel} \abs{x_k}.
\end{equation}
Możemy też sprawdzać, czy wartość w~znalezionym punkcie (dla metod
ograniczających przedział bierzemy jako wynik środek przedziału) jest
mniejsza niż ograniczenie błędu, t.j. czy \(\abs{f} <
\mathit{epsabs}\).  Możemy także sprawdzać, czy
\begin{equation}
  \label{eq:fx_fxx}
  \left\lvert 
    f\left(\frac{x_k + x_{k-1}}{2}\right)
    \frac{x_k + x_{k-1}}{f(x_k) + f(x_{k-1})}
  \right\rvert < \mathit{eps},
\end{equation}
dla metod ograniczających przedział.

\section{Zadanie domowe}
\label{sec:zadanie}

Napisać funkcję znajdujący zera zadanej (jako parametr) funkcji jednej
zmiennej metodą \textbf{bisekcji}.  Funkcja jako parametry powinna
przyjmować \emph{przynajmniej} początkowe przybliżenie na przedział
zawierający pierwiastek, [wskaźnik na] funkcję, dokładność jaką chcemy
osiągnąć oraz maksymalną ilość iteracji.  Funkcja powinna sprawdzać,
czy funkcja ma na końcach podanego przedziału różne znaki.

Jako funkcję do testowania można wziąść jakąś funkcję z~problemu
fizycznego.  Można też użyć jednej z~poniższych funkcji:
\begin{center}
  \begin{tabular}{|l|l|}
    \hline
    funkcja & pierwiastki\\
    \hline
    $x^{20} - 1$ & $1, -1\vphantom{\Big|}$ \\
    $x \exp(-x)$ & $0\vphantom{\big|}$ \\
    $\sin(x)$    & $0, \pi, 2 \pi, \dots\vphantom{\Big|}$ \\
    \hline
  \end{tabular}
\end{center}
%%% 
\input{podpis.tex}

\end{document}
