01NM:Kapitola5

Z WikiSkripta FJFI ČVUT v Praze
Verze z 17. 2. 2010, 16:10, kterou vytvořil Tomas (diskuse | příspěvky) (odkaz na hlavičkovou stránku dokumentu)

Přejít na: navigace, hledání

\section{Iterační metody řešení rovnice tvaru $f(x)=0$} Buď $f$ reálná funkce jedné reálné proměnné. Numerické řešení rovnice $f(x)=0$ sestává ze dvou etap: \begin{enumerate} \item separace kořenů, tj. nalezení intervalů, z nichž v každém leží právě jeden kořen, nebo alespoň nalezení intervalu, v němž leží nějaký kořen, \item výpočet odseparovaného kořene se zadanou přesností. \end{enumerate}

Obecný postup pro separaci kořenů je znám pouze pro algebraické rovnice. Proto se spokojíme s následující větou: \begin{theorem} Buďte \begin{enumerate} \item $f$ funkce spojitá na $\langle a, b\rangle$, \item $f(a)\ne 0\wedge f(b)\ne 0$, \item $\text{sgn} f(a)\ne\text{sgn} f(b)$. \end{enumerate} Potom rovnice $f(x)=0$ má v $(a, b)$ alespoň jeden kořen. Jestliže navíc $f'$ nemění na $(a, b)$ znamení, je to kořen právě jediný. \end{theorem} \begin{dusl} Buďte $\phi, \psi$ dvě funkce spojité v $\langle a, b\rangle$ a nechť je splněna jedna z následujících podmínek: \begin{enumerate} \item $\phi(a)<\psi(a)\wedge\phi(b)>\psi(b)$, \item $\phi(a)>\psi(a)\wedge\phi(b)<\psi(b)$. \end{enumerate} Potom rovnice $\phi(x)=\psi(x)$ má v $(a, b)$ alespoň jeden kořen. \end{dusl} \begin{remark} Smysl právě uvedeného důsledku ihned vyplyne, zvolíme-li v něm za funkci $\psi$ identitu. Kořen rovnice $f(x)=0$ je totiž pevným bodem funkce $\phi:x\mapsto f(x)+x$. Stejně jako iterační metody řešení soustavy lineárních algebraických rovnic budou tedy i metody řešení rovnice tvaru $f(x)=0$ aplikacemi věty o pevném bodě. \end{remark} \subsection{Princip iteračních metod} Rovnici $f(x)=0$ převedeme na tvar $x=\phi(x)$ a konstruujeme iterační posloupnost $(x_n)$ podle vztahu $x_{k+1}=\phi(x_k)$. Provedeme-li v tomto vztahu limitní přechod, získáme následující pozorování: \begin{tvrz} Jestliže iterační posloupnost $(x_n)$ konverguje, potom je její limitou kořen rovnice $x=\phi(x)$. \end{tvrz} \begin{theorem} \label{okonvergenci} Buďte \begin{enumerate} \item $\alpha$ kořen rovnice $x=\phi (x)$, \item $\phi$ diferencovateln\' a na jeho okolí $V = \{ x | \abs{x-\alpha}\leq r \}=\langle\alpha-r, \alpha+r\rangle$, \item $(\forall x \in V)(\abs{\phi '(x)}\leq K<1)$. \end{enumerate} Potom posloupnost $(x_n)$ definovan\' a vztahem $x_{n+1}=\phi (x_n)$ konverguje pro každ\' e $x_0 \in V$. \begin{proof} Matematickou indukcí dokážeme, že platí \[ x_0\in V\Rightarrow(\forall k \in \N)(x_k\in V). \] \begin{enumerate} \item Buď $x_0\in V$. Dokážeme, že $x_1\in V$: \[ \abs{x_1 - \alpha}=\abs{\phi(x_0)-\phi(\alpha)}=\abs{\phi '(\xi)} \abs{x_0 - \alpha}\leq Kr<r, \] neboť $\xi\in(x_0, \alpha)$. \item Buďte $(\forall i\in\hat k_0)(x_i\in V)$. Dokážeme, že $x_{k+1}\in V$: \[ \abs{x_{k+1} - \alpha} = \abs{\phi(x_k) - \phi(\alpha)}=\abs{\phi '(\xi_k)} \abs{x_k - \alpha} \leq K \abs{x_k - \alpha} \leq \] \[ \le K^2 \abs{x_{k-1} - \alpha} \leq ... \leq K^{k+1} \abs {x_0 - \alpha}. \] \end{enumerate} Protože $K<1$, konverguje posloupnost $(K^n)$ k nule, a tak $x_n\rightarrow \alpha$. \end{proof} \end{theorem}

\begin{dusl} Buď $\phi '$ spojitá v okolí bodu $\alpha$ a nechť $\abs{\phi '(\alpha)}<1$. Potom posloupnost $(x_n)$ konverguje, je-li $x_0$ zvoleno dostatečně blízko $\alpha$.

\begin{proof} Stačí zvolit okolí $V$ tak, aby pro všechna $x \in V$ platilo $\abs{\phi '(x)}<1$. \end{proof} \end{dusl}


\begin{define} Řekneme, že iterační metoda dan\' a vzorcem $x_{k+1}=\phi (x_k)$ m\' a ř\' ad konvergence $m$, jestliže $\phi$ m\' a spojit\' e derivace v okolí $\alpha$ do ř\' adu $m$ včetně (tj. $\phi\in\mathcal C^{(m)}(H_\alpha)$) a platí $\phi '(\alpha)=\phi (\alpha)=...=\phi^{(m-1)} (\alpha)=0\wedge\phi^{(m)} \ne 0$. \end{define}


\begin{remark}[vliv ř\' adu konvergence na její rychlost] Nechť je d\' ana iterační metoda, která m\' a ř\' ad konvergence $m$. Potom \[ x_{k+1}-\alpha=\phi(x_k)-\phi(\alpha)=(x_k-\alpha) \phi'(\alpha)+\frac{(x_k-\alpha)^2}{2!} \phi (\alpha)+\hdots+ \] \[ + \frac{(x_k-\alpha)^{m-1}}{(m-1)!} \phi ^{(m-1)} (\alpha) + \frac{(x_k-\alpha)^m}{m!} \phi^{(m)} (\xi)=\frac{(x_k-\alpha)^m}{m!} \phi^{(m)} (\xi). \] Protože je $\phi^{(m)}$ spojit\' a, můžeme ji na omezen\' em intervalu odhadnout konstantou, a proto \begin{equation} \label{rad} \abs{x_{k+1}-\alpha}\leq M_m \abs{x_k-\alpha}^m. \end{equation} \end{remark}

\begin{remark} Je-li v (\ref{rad}) $m=2$, řík\' ame, že metoda konverguje kvadraticky, v případě $m=3$ kubicky, no a s rychlejšíma se setk\' av\' ame tak akor\' at v poh\' adk\' ach. \end{remark}


\begin{remark}[grafick\' a interpretace iteračních metod] Při hled\' aní kořenů rovnice $x=\phi (x)$ konstruujeme lomenou č\' aru, kter\' a se lomí při dosažení grafu funkce $y=\phi (x)$ nebo osy kvadrantu $y=x$. \end{remark}

\subsection{Metoda Regula falsi} Nechť je kořen $\alpha$ rovnice $f(x)=0$ odseparov\' an v intervalu $\langle a, b\rangle$, $f'(\alpha)\ne 0$. Předpokl\' adejme, že $f'$ i $f$ jsou v $\langle a, b\rangle$ spojit\' e a nemění v něm znamení. Zvolme $p \in \{a, b\}$ tak, aby platilo $f(p) f(p)>0$. Za v\' ychozí bod $x_0$ posloupnosti $(x_n)$ zvolme zbyl\' y prvek množiny $\{a, b\}$, takže bude platit $f(x_0) f(x_0)<0$. Další bod $x_1$ získáme jako $x$-ovou souřadnici průsečíku spojnice bodů $[x_0, f(x_0)]$ a $[p, f(p)]$ s osou $x$ atd. Rovnice přímky spojující body $[x_0, f(x_0)]$ a $[p, f(p)]$ je \[ y-f(x_0)=\frac{f(p)-f(x_0)}{p-x_0} (x-x_0). \] Položíme-li $y=0$, získ\' ame $x$-ovou souřadnici průsečíku t\' eto přímky s osou $x$, tj. bod $x_1$: \[ -f(x_0)=\frac{f(p)-f(x_0)}{p-x_0} (x_1-x_0) \Rightarrow x_1=\frac{x_0 f(p)-p f(x_0)}{f(p)-f(x_0)}. \] Obecně pro $k \in \N$ je \begin{equation} \label{fik} x_{k+1}=\frac{x_k f(p)-p f(x_k)}{f(p)-f(x_k)} \stackrel{k\rightarrow\infty}{\Longrightarrow} \phi (x)=\frac{x f(p)-p f(x)}{f(p)-f(x)}. \end{equation} \begin{tvrz} \label{Regula} Konvergence metody Regula falsi je zajištěna splněním těchto předpokladů: \begin{enumerate} \item $(\exists H_\alpha)(f', f \in \mathcal{C}(H_\alpha))$, \item $f'(\alpha)\ne 0$. \end{enumerate} \begin{proof} Zderivov\' aním prav\' e strany (\ref{fik}) dost\' av\' ame \[ \phi '(x)=\frac{[f(p)-p f'(x)][f(p)-f(x)]+f'(x)[x f(p)-p f(x)]}{[f(p)-f(x)]^2}. \] Uv\' ažíme-li, že $f(\alpha)=0$, dozvídáme se \begin{equation} \label{derivacefi} \phi '(\alpha)=\frac{[f(p)-p f'(\alpha)] f(p)+\alpha f'(\alpha) f(p)}{[f(p)]^2}=\frac{f(p)+(\alpha-p) f'(\alpha)}{f(p)}. \end{equation} Poslední v\' yraz teď upravíme tak, abychom se zbavili nepříjemn\' eho $f(p)$. Potom totiž dok\' ažeme, že $\abs{\phi '(\alpha)}\le K<1$, a z věty \ref{okonvergenci} vyplyne konvergence metody. Začneme s čitatelem. Rozviňme funkci $f$ do Taylorova rozvoje se středem v bodě $\alpha$: \[ f(x)=f(\alpha)+\frac{f'(\alpha)}{1!} (x-\alpha)+\frac{f(\xi)}{2!} (x-\alpha)^2. \] Dosadíme-li do tohoto vztahu za $x=p$, dostaneme \[ f(p)+(\alpha - p) f'(\alpha)=\frac{f(\xi)}{2} (p-\alpha)^2. \] To už vypad\' a celkem pěkně, ale ještě je tu jmenovatel. Rozviňme proto opět funkci $f$, ale tentokr\' at jen do prvního ř\' adu: $f(x)=f(\alpha)+f'(\eta)(x-\alpha)$, takže pro $x=p$ m\' ame $f(p)=f'(\eta)(p-\alpha)$. Nyní již můzeme dosadit do rovnice (\ref{derivacefi}): \[ \phi '(\alpha)=\frac{f(\xi) (p-\alpha)^2}{2 f'(\eta) (p-\alpha)}=\frac{f(\xi) (p-\alpha)}{2 f'(\eta)}. \] Z předpokladů 1, 2 vypl\' yv\' a, že podíl $f(\xi)/f'(\eta)$ lze odhadnout konstantou, a proto je-li $p$ dostatečně blízko $\alpha$, můžeme dosáhnout $\abs{\phi '(\alpha)}$ tak mal\' e, jak potřebujeme. \end{proof} \end{tvrz}

\subsection{Newtonova metoda} Nechť je kořen $\alpha$ rovnice $f(x)=0$ odseparov\' an v intervalu $\langle a, b\rangle$, $f'(\alpha)\ne 0$. Předpokl\' adejme, že $f'$ i $f$ jsou v $\langle a, b\rangle$ spojit\' e a nemění v něm znamení. Za v\' ychozí bod $x_0$ posloupnosti $(x_n)$ zvolme $x_0\in\{a, b\}$ tak, aby platilo $f(x_0) f(x_0)>0$. Na rozdíl od metody Regula falsi tedy nem\' ame ž\' adn\' y bod $p$. Místo posloupnosti sečen spojujících body $[x_k, f(x_k)]$ a $[p, f(p)]$ budeme konstruovat posloupnost tečen ke grafu funkce $f$ v bodech $[x_k, f(x_k)]$. Bod $x_{k+1}$ získ\' ame jako $x$-ovou souřadnici průsečíku tečny v bodě $[x_k, f(x_k)]$ s osou $x$.

Rovnice tečny v bodě $[x_0, f(x_0)]$ je $y-f(x_0)=f'(x_0) (x-x_0)$. Položíme-li $y=0$, získ\' ame $x$-ovou souřadnici průsečíku t\' eto přímky s osou $x$, tj. bod $x_1$: \[ -f(x_0)=f'(x_0) (x_1-x_0) \Rightarrow x_1=x_0-\frac{f(x_0)}{f'(x_0)}. \] Obecně pro $k\in\N$ je \begin{equation} \label{Newton} x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)} \stackrel{k\rightarrow\infty}{\Longrightarrow} \phi(x)=x-\frac{f(x)}{f'(x)}. \end{equation} \begin{tvrz} Pro konvergenci Newtonovy metody platí naprostá obdoba tvrzení \ref{Regula}. Je-li navíc $f\in\mathcal C(H_\alpha)$, potom má Newtonova metoda řád konvergence 2. \begin{proof} Konvergence: \[ \phi '(x)=1-\frac{{f'}^2 (x)-f(x)f(x)}{{f'}^2 (x)}=\frac{f(x)f(x)}{{f'}^2 (x)} \Rightarrow \phi '(\alpha)=0. \] Ze spojitosti $\phi '$ plyne existence takového okolí $V$ kořene $\alpha$, že $(\forall x\in V)(\abs{\phi'(x)}\le K<1)$. Nyní stačí použít větu \ref{okonvergenci}.

Druhá část tvrzení: \[ \phi (\alpha)=\frac{{f'}^3 (\alpha) f(\alpha)}{{f'}^4 (\alpha)}=\frac{f(\alpha)}{f'(\alpha)}\ne 0, \] neboť $f$ nemění v $\langle a\, b\rangle$ znamení. Podle definice jde tedy skutečně o metodu 2. ř\' adu konvergence, tudíž $\abs{x_{k+1}-\alpha}\le M\abs{x_k-\alpha}^2$. \end{proof} \end{tvrz} \begin{tvrz} Předpoklad existence $f$ v předchozím tvrzení je nadbytečn\' y, tj. Newtonova metoda konverguje kvadraticky, i když $f$ neexistuje. \begin{proof} Podle prvního vztahu ve (\ref{Newton}) platí \[ x_{k+1}-\alpha=x_k-\alpha-\frac{f(x_k)-f(\alpha)}{f'(x_k)}=x_k-\alpha-\frac{f'(\xi_k) (x_k-\alpha)}{f'(x_k)}= \] \[ =\frac{f'(x_k)-f'(\xi_k)}{f'(x_k)} (x_k-\alpha)=\frac{f(\eta_k)}{f'(x_k)} (x_k-\xi_k)(x_k-\alpha). \] Protože $\abs{x_k-\xi_k}<\abs{x_k-\alpha}$, je $\abs{x_{k+1}-\alpha}\le M\abs{x_k-\alpha}^2$. \end{proof} \end{tvrz}

\subsection{Čebyševova metoda} Nechť je kořen $\alpha$ rovnice $f(x)=0$ odseparov\' an v intervalu $\langle a, b\rangle$, $f'(\alpha)\ne 0$. Předpokl\' adejme, že $f$ m\' a v $\langle a, b\rangle$ $2r+1$ spojit\' ych derivací a $\langle a, b\rangle$ je tak mal\' y, že $\forall x \in \langle a, b\rangle$ platí $f'(x)\ne 0$. Potom na $\langle a, b\rangle$ existuje $F=f^{-1}$, tj. $(\forall x\in\langle a, b\rangle)(F(f(x))=x)$, a platí $f(\alpha)=0 \Leftrightarrow F(0)=\alpha$.

V dalším využijeme existence inverzní funkce $F$. To, že ji ve skutečnosti nezn\' ame, není na z\' avadu, protože nakonec najdeme vhodn\' e vyj\' adření pomocí původní funkce $f$ a jejích derivací. Nejprve funkci $F$ rozvineme pomocí Taylorova vzorce se středem v bodě $y_0$: \[ F(y)=F(y_0)+\sum_{k=1}^r \frac{F^{(k)} (y_0)}{k!} (y-y_0)^k+\frac{F^{(r+1)}(\eta)}{(r+1)!} (y-y_0)^{r+1}. \] Položme $y=0$. Potom \[ F(0)=F(y_0)+\sum_{k=1}^r (-1)^k \frac{F^{(k)}(y_0)}{k!} y_0^k + (-1)^{r+1} \frac{F^{(r+1)}(\eta)}{(r+1)!} y_0^{r+1}, \] kde $\eta \in (0, y_0)$. Po dosazení za $F(0)=\alpha$ a $y_0=f(x)$ m\' ame \[ \alpha=x+\sum_{k=1}^{r}(-1)^k \frac{F^{(k)}(f(x))}{k!} f^k (x) + (-1)^{r+1} \frac{F^{(r+1)}(\eta)}{(r+1)!} f^{r+1} (x), \] kde $\eta \in (0, f(x))$. Poslední sčítanec převeďme na levou stranu a označme \begin{equation} \label{fir} \phi_r(x)=\alpha+(-1)^r\frac{F^{(r+1)}(\eta)}{(r+1)!} f^{r+1} (x). \end{equation} Označíme-li ještě $a_k(x)=F^{(k)} (f(x))$, potom z předchozích dvou rovností vypl\' yv\' a \[ \phi_r (x)=x+\sum_{k=1}^{r}(-1)^{k}\frac{a_k(x)}{k!} f^k (x). \] Z tohoto vztahu nebo již z (\ref{fir}) je zřejmé, že pro $r\in\N$ platí $\phi_r(\alpha)=\alpha$. \begin{tvrz} \label{konvrpj} Iterační metoda dan\' a vzorcem $x_{k+1}=\phi_r(x_k)$ m\' a ř\' ad konvergence alespoň $r+1$. \begin{proof} Máme dok\' azat, že platí $\phi_r '(\alpha)=\phi_r (\alpha)=...=\phi_r^{(r)} (\alpha)=0$. Důkaz provedeme sporem. Předpokládejme existenci takov\' eho $p \in \hat r$, že $\phi_r^{(p)} (\alpha)\ne 0$. (Pokud by takov\' ych $p$ existovalo více, zvolíme nejmenší z nich.) Funkci $\phi_r$ rozvineme do $p$-t\' eho ř\' adu: \[ \phi_r(x)=\phi_r(\alpha)+\frac{\phi_r^{(p)}(\alpha)}{p!} (x-\alpha)^p + \frac{\phi_r^{(p+1)}(\chi)}{(p+1)!} (x-\alpha)^{p+1}. \] (Členy ř\' adů 1 až $p-1$ jsou nulové, a proto je nevypisujeme). Podle Lagrangeovy věty platí \begin{equation} \label{Lag} f(x)=f(x)-f(\alpha)=f'(\xi)(x-\alpha), \end{equation} kde $\xi \in (x, \alpha)$. Poslední dva vztahy dosadíme do (\ref{fir}): \[ \frac{\phi_r^{(p)}(\alpha)}{p!} (x-\alpha)^p+\frac{\phi_r^{(p+1)}(\chi)}{(p+1)!} (x-\alpha)^{p+1}=(-1)^r\frac{F^{(r+1)}(\eta)}{(r+1)!} {f'}^{r+1}(\xi) (x-\alpha)^{r+1}. \] Odtud vyplývá \[ \frac{\phi_r^{(p)}(\alpha)}{p!}=-\frac{\phi_r^{(p+1)}(\chi)}{(p+1)!} (x-\alpha)+(-1)^r\frac{F^{(r+1)}(\eta)}{(r+1)!} {f'}^{r+1}(\xi) (x-\alpha)^{r-p+1}. \] Podle předpokladu je levá strana této rovnice nenulová, ale oba členy vpravo můžeme učinit libovolně malými a to je spor. \end{proof} \end{tvrz} V našem vzorci pro $\phi_r(x)$ vystupují koeficienty $a_k(x)$ a ty se nyní pokusíme vhodně vyjádřit. Opakovaným derivováním rovnice $F(f(x))=x$ dostaneme systém $r$ rovnic \[ \begin{array}{l} F'(f(x)) f'(x)=1,\\ F(f(x)) {f'}^2 (x) + F'(f(x)) f(x)=0,\\ F(f(x)) {f'}^3(x)+3F(f(x)) f'(x)f(x)+F'(f(x))f(x)=0\\ \text{atd.} \end{array} \] Tyto rovnice přepíšeme pomocí $a_k(x)$. Obdržíme troj\' uhelníkovou soustavu pro $a_1(x), a_2(x), ..., a_r(x)$: \[ \begin{array}{l} a_1(x) f'(x)=1,\\ a_2(x) {f'}^2(x)+a_1(x) f(x)=0,\\ a_3(x) {f'}^3(x)+3a_2(x)f'(x)f(x)+a_1(x)f'(x)=0\\ \text{atd.} \end{array} \] \begin{remark} Zvolíme-li nyní $r=1$, dostaneme Newtonovu metodu \[ a_1(x)=\frac{1}{f'(x)}\Rightarrow \phi_1(x)=x-\frac{f(x)}{f'(x)} \] a při volbě $r=2$ obdržíme \[ a_2(x)=-\frac{f(x)}{{f'}^3(x)}\Rightarrow \phi_2(x)=x-\frac{f(x)}{f'(x)}-\frac{f(x)f^2(x)}{2{f'}^3(x)}. \] \end{remark} \begin{remark} Dosud jsme předpokládali, že funkce $f$ má v intervalu $\langle a\, b\rangle$ $2r+1$ spojitých derivací. Má-li mít totiž metoda řád konvergence $r+1$, jak o tom mluví tvrzení \ref{konvrpj}, musí existovat $\phi_r^{(r)}$ a $\phi_r$ závisí na $F^{(r+1)}$, tedy i na $f^{(r+1)}$. Na závěr uvedeme tvrzení, které mluví o rychlosti konvergence (ne tedy o jejím řádu ve smyslu definice) v případě, že tento předpoklad není splněn:

\end{remark} \begin{tvrz} Ke splnění $\abs{x_{k+1}-\alpha}\le M\abs{x_k-\alpha}^{r+1}$ stačí $r+1$ spojitých derivací. \begin{proof} Dosadíme-li vztah (\ref{Lag}) do (\ref{fir}), dostaneme \[ \abs{x_{k+1}-\alpha}=\abs{\phi_r(x_k)-\alpha}=\abs{\frac{F^{(r+1)}(\eta)}{(r+1)!}{f'}^{r+1}(\xi)}\abs{x_k-\alpha}^{r+1}. \] Funkce $\frac{F^{(r+1)}(\eta)}{(r+1)!}{f'}^{r+1}(\xi)$ je spojitá, a proto ji lze na omezeném intervalu odhadnout konstantou $M$. \end{proof} \end{tvrz}


% následující řádky upravují pouze zobrazení stránky na wiki na obsah dokumentu nemají vliv - prosím neměnit ! %\parentlatexfile{01NMskriptum} %\usewikiobsah{01NM:Obsah} %\parentlatexpreamble{01NM:Preamble} .................................. odkaz na hlavičkovou stránku dokumentu, jehož vložení umožní překlad částečného pdf, tj. pdf, které vznikne pouze z této stránky