01NM:Kapitola6

Z WikiSkripta FJFI ČVUT v Praze
Verze z 1. 8. 2010, 10:25, kterou vytvořil Admin (diskuse | příspěvky)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání
PDF [ znovu generovat, výstup z překladu ] Kompletní WikiSkriptum včetně všech podkapitol.
PDF Této kapitoly [ znovu generovat, výstup z překladu ] Přeložení pouze této kaptioly.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01NM

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01NMAdmin 1. 8. 201010:22
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:47
Header editovatHlavičkový souborKlinkjak 1. 9. 201522:49 header.tex
Kapitola1 editovatFinitní metodyAdmin 1. 8. 201010:24 kapitola1.tex
Kapitola2 editovatIterační metody řešení soustav lineárních algebraických rovnicKlinkjak 3. 9. 201519:49 kapitola2.tex
Kapitola3 editovatČástečný problém vlastních číselAdmin 1. 8. 201010:25 kapitola3.tex
Kapitola4 editovatÚplný problém vlastních číselAdmin 1. 8. 201010:25 kapitola4.tex
Kapitola5 editovatIterační metody řešení rovnice tvaru f(x)=0Admin 1. 8. 201010:25 kapitola5.tex
Kapitola6 editovatIterační metody pro řešení systémů nelineárních algebraických a transcendentních rovnicAdmin 1. 8. 201010:25 kapitola6.tex
Kapitola7 editovatLagrangeova interpolaceAdmin 1. 8. 201010:25 kapitola7.tex
Kapitola8 editovatNumerický výpočet derivaceAdmin 1. 8. 201010:25 kapitola8.tex
Kapitola9 editovatNumerický výpočet integrálu Admin 1. 8. 201010:25 kapitola9.tex

Zdrojový kód

%\wikiskriptum{01NM}
 
\section{Iterační metody pro řešení systémů nelineárních algebraických a transcendentních rovnic}
Buďte $f_1\, f_2\, ...\, f_n$ reálné funkce $n$ reálných proměnných. Naším cílem je nalézt řešení soustavy
\begin{equation}
\label{syst}
f_1(x_1\, x_2\, ...\, x_n)=0\,
f_2(x_1\, x_2\, ...\, x_n)=0\,
\hdots\,
f_n(x_1\, x_2\, ...\, x_n)=0
\end{equation}
ve tvaru $\vec a=(a_1\, a_2\, ...\, a_n)^T$. Separaci kořenů v tomto případě vůbec neumíme provést, a proto budeme dále předpokládat, že známe konvexní oblast $G$ s vlastností $\vec a\in G$. 
\subsection{Princip iteračních metod}
Systém (\ref{syst}) převedeme na systém
\begin{equation}
\label{prevedeno}
x_1=\phi_1(x_1\, x_2\, ...\, x_n)\,
x_2=\phi_2(x_1\, x_2\, ...\, x_n)\, ...\,
x_n=\phi_n(x_1\, x_2\, ...\, x_n)
\end{equation}
a konstruujeme posloupnost vektorů $(\vec x^{(k)})$ takto:
\begin{equation}
\label{slozky}
\begin{array}{c}
x_1^{(k+1)} = \phi_1(x_1^{(k)}\, x_2^{(k)}\, ...\, x_n^{(k)})\,\\
x_2^{(k+1)} = \phi_2(x_1^{(k)}\, x_2^{(k)}\, ...\, x_n^{(k)})\,\\
\hdots\, \\
x_n^{(k+1)} = \phi_n(x_1^{(k)}\, x_2^{(k)}\, ...\, x_n^{(k)}).
\end{array}
\end{equation}
\begin{tvrz}
\label{ctyrip}
Buďte
\begin{enumerate}
\item řešení $\vec a$ systému (\ref{prevedeno}) odseparováno v konvexní oblasti $G$,
\item $(\forall i\, j\in \hat n)(\frac{\partial\phi_i}{\partial x_j}$ spojité na $\overline G)$,
\item $(\forall k \in \N_{0})(\vec x^{(k)} \in G)$,
\item $\rho(\mathcal M)<1$, kde $\mathcal M$ je matice definovaná vztahem
\[
[\mathcal M]_{ij}=\max_{\vec x \in \overline G}\abs{\der{i}{j}(\vec x)}.
\]
\end{enumerate}
Potom posloupnost $(\vk x)$ daná předpisem (\ref{slozky}) konverguje k řešení $\vec a$.
\begin{proof}
Vyjděme z $i$-té rovnice v (\ref{slozky}). Podle věty o přírůstku reálné funkce více proměnných existuje vektor $\vk p_i$ ležící ve ,,vnitřku" úsečky spojující body $\vk x\, \vec a$ tak, že
\begin{equation}
\label{vnius}
x_i^{(k+1)}-a_i=\phi_i(\vk x)-\phi_i(\vec a)=\sum_{j=1}^{n}\der{i}{j} (\vk p_i)(\K x_j-a_j).
\end{equation}
To platí $\forall i\in \hat n$, takže máme pro každé $k\in\N$ zaručenu existenci $n$-tice vektorů $\vec p_1^{(k)}\, \hdots\, \vec p_n^{(k)}$ splňujících vztah (\ref{vnius}). Označíme-li
\[
\mathcal M_k=
\left(
\begin{matrix}
\der{1}{1}(\vk p_1) & \hdots & \der{1}{n}(\vk p_1)\\
\vdots & & \vdots\\
\der{n}{1}(\vk p_n) & \hdots & \der{n}{n}(\vk p_n)\\
\end{matrix}
\right) ,
\]
potom podle (\ref{vnius}) zřejmě platí
\[
\vec x^{(k+1)}-\vec a=\mathcal M_k (\vk x-\vec a)=\mathcal M_k\mathcal M_{k-1} (\vec x^{(k-1)} - \vec a)=...=\mathcal M_k \mathcal M_{k-1} ... \mathcal M_0 (\vec x^{(0)}-\vec a).
\]
Z toho plyne, že nutnou a postačující podmínkou pro konvergenci $\vk x\rightarrow\vec a$ za předpokladů 1--3 je
\begin{equation}
\label{kritsoucin}
\lim_{k\rightarrow\infty}\prod_{i=0}^k \mathcal M_i=O.
\end{equation}
Z definice matice $\mathcal M$ vyplývá
$(\forall k\in\N)([\mathcal M]_{ij}\ge\abs{[\mathcal M_k]_{ij}})$. Protože oblast $G$ je konvexní, obsahuje i \' usečku $\langle\vk x, \vec a\rangle$. Odtud, z předchozí nerovnosti a z trojúhelníkové nerovnosti plyne další nerovnost $[\mathcal M^{k+1}]_{ij}\ge\abs{[\mathcal M_k \mathcal M_{k-1} ... \mathcal M_0]_{ij}}$, neboť na obou stranách této nerovnice jsou sumy stejného počtu součinů a vlevo vystupuje místo původního prvku odhad. Z této nerovnosti vyplývá, že konverguje-li posloupnost $(\mathcal M^k)$ k nulové matici, potom je splněno i (\ref{kritsoucin}). Podle věty \ref{nppkgpm} tak dostáváme kritérium konvergence $\rho(\mathcal M)<1$.
\end{proof}
\end{tvrz}
\begin{remark}[důležitá]
Předpoklad 3 v tvrzení \ref{ctyrip} je podstatný. Následující tvrzení říká, že k jeho splnění je třeba zvolit $\vec x^{(0)}$ dostatečně blízko $\vec a$, ale nedozvíme se jak.
\end{remark}
\begin{tvrz}
Za předpokladů 1, 2, 4 tvrzení \ref{ctyrip} existuje takové okolí $V$ bodu $\vec a$, že $x^{(0)}\in V\Rightarrow(\forall k \in \N)(\vk x\in G)$.
\begin{proof}
Podle předpokladu 4 platí $\mathcal M^k\rightarrow O$. Z toho podle definice \ref{poslvek} a podle definice normy $\norm{\text{ }}$ vyplývá existence takového $k \in \N$, že $\norm{\mathcal M^{k+1}}<1$.
Definujme $V=\{\vec x|\norm{\vec x-\vec a}<R\}=B_{\text{I}} (\vec a, R)$, kde $R$ je tak malé, že platí
\begin{equation}
\label{okoli}
\vec x^{(0)}\in V\Rightarrow \vec x^{(1)}, \vec x^{(2)}, ..., \vk x\in G. 
\end{equation}
Vhodné $R$ určitě existuje, protože $k$ je pevné konečné číslo.
Buď $\vec x^{(0)}\in V$. Potom z vlastností normy $\norm{\text{ }}$ plyne
\[
\norm{\vec x^{(k+1)}-\vec a}=\norm{\mathcal M_k \mathcal M_{k-1}\hdots\mathcal M_0 (\vec x^{(0)}-\vec a)}\le
\]
\[
\le\norm{\mathcal M_k \mathcal M_{k-1}\hdots\mathcal M_0}\norm{\vec x^{(0)}-\vec a}\le\norm{\mathcal M^{k+1}}\norm{\vec x^{(0)}-\vec a}.
\]
Protože $\norm{\mathcal M^{k+1}}<1$ a $\norm{\vec x^{(0)}-\vec a}<R$, je i součin $\norm{\mathcal M^{k+1}}\norm{\vec x^{(0)}}<R$, a proto $\vec x^{(k+1)}\in V$. To podle (\ref{okoli}) znamená, že $\vec x^{(k+2)}\, \vec x^{(k+3)}\, \hdots\, \vec x^{(2k+1)}\in G$.
Nyní stejný postup aplikujeme na $\vec x^{(k+2)}\, \vec x^{(k+3)}\, \hdots\, \vec x^{(2k+1)}$, takže se dozvíme, že $\vec x^{(2k+2)}\in V$, atd.
\end{proof}
\end{tvrz}
\subsection{Newtonova metoda}
Přepišme nyní soustavu (\ref{syst}) do vektorové podoby $\vec f(\vec x)=\vec o$, kde $\vec f(x_1, \hdots, x_n)=(f_1 (x_1, \hdots, x_n), \hdots, f_n(x_1, \hdots, x_n))^T$. Budiž řešení $\vec a$ této rovnice odseparováno v konvexní oblasti $G$ a nechť na $G$ existují $\derf{i}{j}$ a jsou spojité. Označme
\[
f_x (\vec x)=
\left(
\begin{matrix}
\derf{1}{1} & \hdots & \derf{1}{n}\\
\vdots & & \vdots\\
\derf{n}{1} & \hdots & \derf{n}{n}\\
\end{matrix}
\right)
\]
a předpokládejme, že matice $f_x (\vec a)$ je regulární. Potom jsou ovšem regulární i všechny matice $f_x (\vec x)$ pro $\vec x\in V_{\vec a}$, kde $V_{\vec a}$ je jisté okolí řešení $\vec a$. Nyní vyjděme z prvního vztahu ve (\ref{Newton}) a vytvořme jeho maticovou obdobu
\begin{equation}
\label{mat}
\vec x^{(k+1)}=\vk x - f_x^{-1}(\vk x)\vec f(\vk x).
\end{equation}
Vektor $\vk x$ převedeme na levou stranu rovnosti a obě její strany vynásobíme zleva maticí $f_x(\vk x)$, takže dostaneme $f_x(\vk x)(\vec x^{(k+1)}-\vk x)=-\vec f(\vk x)$. Označíme-li $\Delta\vk x=\vec x^{(k+1)}-\vk x$, přejde tento vztah ve tvar
\[
f_x(\vk x)\Delta\vk x=-\vec f(\vk x)\, \vec x^{(k+1)}=\vk x+\Delta\vk x.
\]
\begin{theorem}
\begin{enumerate}
\item Nechť konvexní oblast $G$ obsahuje řešení $\vec a$ systému $\vec f(\vec x)=\vec o$.
\item Buď $f_x(\vec a)$ regulární.
\item Buďte $f_1, f_2, \hdots, f_n$ spojité na $G$ včetně svých prvních parciálních derivací.
\end{enumerate}
Potom existuje $\delta$-okolí $R=\{\vec x|\nor{\vec x-\vec a}<\delta\}$ bodu $\vec a$ takové, že pro $\vec x^{(0)}\in R$ posloupnost $(\vk x)$ v Newtonově metodě konverguje k $\vec a$.
\begin{proof}
Buďte $\vec y, \vec z\in G$. Definujme funkci
\[
\Phi_i(t)=f_i(\vec y+t(\vec z-\vec y))=f_i(y_1+t(z_1-y_1)\, \hdots\, y_n+t(z_n-y_n)).
\]
Potom zřejmě $\Phi_i(0)=f_i(\vec y)$ a $\Phi_i(1)=f_i(\vec z)$. Dále $\forall i\in \hat n$ platí
\[
f_i(\vec z)-f_i(\vec y)=\Phi_i(1)-\Phi_i(0)=\intt{\frac{\text{d}\Phi_i(t)}{\text{d}t}}=\intt{\frac{\text{d}f_i}{\text{d}t}\vktr}=
\]
\[
=\intt{\sum_{j=1}^n\frac{\partial f_i}{\partial x_j}\vktr(z_j-y_j)}=\sum_{j=1}^n\underbrace{\left (\intt{\frac{\partial f_i}{\partial x_j}\vktr}\right )}_{\text{ozn. }\mathcal F_{ij} (\vec y, \vec z)}(z_j-y_j).
\]
Označíme-li $F(\vec y, \vec z)=(\mathcal F_{ij}(\vec y, \vec z))$, potom podle předchozí rovnosti $\forall \vec y, \vec z\in G$ platí
\begin{equation}
\label{prir}
\vec f(\vec z)-\vec f(\vec y)=F(\vec y, \vec z)(\vec z-\vec y).
\end{equation}
Položíme-li $\vec y=\vec z=\vec a$, pak
\[
\mathcal F_{ij}(\vec a, \vec a)=\frac{\partial f_i}{\partial x_j}(\vec a)\Rightarrow F(\vec a, \vec a)=f_x(\vec a)\Rightarrow f_x^{-1}(\vec a) F(\vec a, \vec a)=I.
\]
Podle předpokladu 3 proto existuje takové okolí $R\subset G$ řešení $\vec a$, že pro každé $\vec x\in R$ platí $\nor{I-f_x^{-1}(\vec x) F(\vec a, \vec x)}\le K<1$. Matematickou indukcí dokážeme, že
\[
\vec x^{(0)}\in R\Rightarrow(\forall k\in\N)(\vk x\in R).
\]
 
Podle (\ref{mat}) a (\ref{prir}) pro všechna $k\in\N$ taková, že $\vk x\in G$, platí
\[
\vec x^{(k+1)}-\vec a=\vk x-\vec a-f_x^{-1}(\vk x)(\vec f(\vk x)-\vec f(\vec a))=
\]
\[
=\vk x-\vec a-f_x^{-1}(\vk x) F(\vec a, \vk x)(\vk x-\vec a)=(I-f_x^{-1}(\vk x) F(\vec a, \vk x))(\vk x-\vec a).
\]
\begin{enumerate}
\item Buď $\vec x^{(0)}\in R$. Dokážeme, že $\vec x^{(1)}\in R$:
\[
\nor{\vec x^{(1)}-\vec a}=\nor{\vyraz{0}(\vec x^{(0)}-\vec a)}\le
\]
\[
\le\nor{\vyraz{0}}\nor{\vec x^{(0)}-\vec a}<1. \delta=\delta.
\]
\item Buďte $(\forall i\in\hat k_0)(\vec x^{(i)}\in R)$. Dokážeme, že $\vec x^{(k+1)}\in R$:
\[
\nor{\vec x^{(k+1)}-\vec a}\le\nor{\vyraz{k}}\nor{\vk x-\vec a}\le K\nor{\vk x-\vec a}\le
\]
\[
\le K^2\nor{\vec x^{(k-1)}-\vec a}\le\hdots\le K^{k+1}\nor{\vec x^{(0)}-\vec a}.
\]
\end{enumerate}
Protože $K<1$, dostaneme zlimicením posledního vztahu $\vk x\rightarrow\vec a$.
\end{proof}
\end{theorem}
\begin{tvrz}
Charakter konvergence Newtonovy metody je kvadratický, tj.
\[
\nor{\vec x^{(k+1)}-\vec a}\le L\nor{\vk x-\vec a}^2.
\]
\begin{proof}
Přesahuje rámec přednášky. (,,Je dlouhý.'')
\end{proof}
\end{tvrz}