01NM:Kapitola6

Z WikiSkripta FJFI ČVUT v Praze
Verze z 23. 12. 2009, 15:48, kterou vytvořil Radek.Novak (diskuse | příspěvky) (Chybějící index)

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

\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}


% 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}