NumMod 1 het 6

date: 2024.03.18.

Multkor ott fejeztuk be, hogy be akartuk latni hogy az egymast koveto iranyok a gradiens modszerben meroleges egymasra!

Irjuk fel a skalaris szorzatat az egymast koveto iranyoknak!

$$(r_i,r_{i+})\stackrel{?}{=}0$$ $$(r_i,r_{i+1})=\left(r_i,b-A\left(x_i+\frac{(r_i,r_i)}{(r_i,A{r}_i)}\cdot r_i\right)\right)$$ $$=(r_i,r_i)-(r_i,A\frac{(r_i,r_i)}{(r_i,A{r}_i)}\cdot r_i)$$ $$=(r_i,r_i)-\frac{(r_i,r_i)}{(r_i,A{r}_i)}(r_i,A{r}_i)=(r_i,r_i)-(r_i,r_i)=0$$

Megjegyzes: Ha ${\mathrm{cond}}_2(A)$ nagy, akkor lassu a konvergencia.

Konjugalt gradiens-modszer

$m:=2$
Tudjuk: a gradiens modszernel a $p_1$ keresesi irany ($r_0$) $\perp$ $r_1$.
Azaz:

$$0=(p_1,r_1)=(p_1,b-A{x}_1)=(p_1,A{x}^{\ast }-A{x}_1)=(p_1,A(x^{\ast }-x_1))$$

Def.:

Legyen $A\in {\mathbb{R}}^{m\times m}$ szpd. Azt mondjuk, hogy $x$ es $y\in {\mathbb{R}}^m$ vektorok $A$-konjugaltak/ortogonalisak, ha $(x,Ay)=0$.

Tehat olyan keresesi iranyt lenne erdemes valasztani, amely $p_1$-re $A$-ortogonalis!
Keressuk $p_2$-t a kovetkezo alakban:

$$p_2=r_1-{\beta }_1\cdot p_1$$ $$(p_1,A(r_1-{\beta }_1\cdot p_1))=0$$

${\beta }_1=?$

$$(p_1,A{r}_1)-{\beta }_1(p_1,A{p}_1)=0$$ $$⟹{\beta }_1=\frac{(p_1,A{r}_1)}{(p_1,A{p}_1)}$$

Ezen ${\beta }_1$-et valasztva, a $p_2=r_1-{\beta }_1\cdot p_1$ iranyba lepve az $x^{\ast }$ minimum helybe lepunk!
Tehat $m=2$ eseten $2$ lepesben meg tudjuk hatarozni a linearis egyenletrendszer megoldasat.

Megjegyzes: $A\in {\mathbb{R}}^{m\times m}$ eseten is altalanosithato. Ekkor legfeljebb $m$ lepesben megkapjuk a megoldast.

Algebrai egyenletek megoldasa

Egyismeretlenes valos egyenletekkel foglalkozunk.
Egy ilyen egyenlet mindig felirhato a kovetkezo alakban:

$$f(x)=0\text{(1)}$$

ahol $f:\mathbb{R}\to \mathbb{R}$ fuggveny.

Ezzel (1)-nek a megoldasa ugyanaz mint $f$ zerushelye. Ezt keressuk a tovabbiakban!

Gyokok stabilitasa

Q.: Mennyire erzekeny a megoldas $f$ kis megvaltoztatasara?

Tegyuk fel, hogy (1) helyett az
$\tilde{f}(x)=0(2)$
Egyenletet oldjuk meg, es tegyuk fel, hogy (1)-nek es (2)-nek is $\exists !$ megoldasa, melyek $x^{\ast }$ illetve ${\tilde{x}}^{\ast }$ rendre.

A kovetkezo legyen a meroszamunk az elteresre:

$$|x^{\ast }-{\tilde{x}}^{\ast }|\le ?$$

Ha $f$ es $\tilde{f}$ csak kicsit ter el egymastol?
Merje $\underset{[a,b]}{\max }|f-\tilde{f}|$ az $f$ es $\tilde{f}$ eltereset.

Tegyuk fel, hogy $f\in C[a,b]\cap D(a,b)$

Ismetles: (Lagrange-kozepertek tetel)
Tegyuk fel, hogy $f\in C[a,b]\cap D(a,b)$. Ekkor $\exists c\in (a,b)$ ugy, hogy

$$f^{\prime }(c)=\frac{f(b)-f(a)}{b-a}$$

Tovabba tegyuk fel, hogy $x^{\ast }$ es ${\tilde{x}}^{\ast }\in [a,b]$, es $\underset{[a,b]}{\max }|f-\tilde{f}|<\epsilon$.
Alkalmazzuk az LKT-t az $[x^{\ast },{\tilde{x}}^{\ast }]$ intervallumon (felteve, hogy $x^{\ast }<{\tilde{x}}^{\ast }$):

$$\exists c\in (x^{\ast },{\tilde{x}}^{\ast }):f({\tilde{x}}^{\ast })-f(x^{\ast })=f^{\prime }(c)({\tilde{x}}^{\ast }-x^{\ast })$$

Tegyuk fel, hogy $f^{\prime }(x)\ne 0\forall x\in (x^{\ast },{\tilde{x}}^{\ast })$.

$$⟺|{\tilde{x}}^{\ast }-x^{\ast }|=\left|\frac{f({\tilde{x}}^{\ast })}{f^{\prime }(c)}\right|=\frac{|f({\tilde{x}}^{\ast })-\tilde{f}({\tilde{x}}^{\ast })|}{|f^{\prime }(c)|}<\frac{\epsilon }{\underset{[a,b]}{\min }|f^{\prime }|}$$

Def.:

Az $M:=\frac{1}{\underset{[a,b]}{\min }|f^{\prime }|}$ szamot az (1) egyenlet kondicionaltsagi szamanak nevezzuk.

Tehat ha $\underset{[a,b]}{\max }|f-\tilde{f}|<\epsilon$, akkor $|{\tilde{x}}^{\ast }-x^{\ast }|<M\cdot \epsilon$.

Konvergenciasebesseg

Tegyuk fel, hogy ${\lim }_{k\to \infty }{x}_k=x^{\ast }$, es legyen $e_k:=x_k-x^{\ast }$. (${\lim }_{k\to \infty }{e}_k=0$ vagy ${\lim }_{k\to \infty }|e_k|=0$)

Def.:

Azt mondjuk, hogy az $(x_k)$ sorozat konvergencia rendje $p\ge 1$, ha

$$\underset{k\to \infty }{\lim }\frac{\log |e_k|}{\log |e_{k-1}|}=p$$

Ha $p=1$, akkor linearis/elsorendu konvergenciarol beszelunk.
Ha $p=2$, akkor masodrendu/kvadratikus konvergenciarol beszelunk.

Elsorendu:

	$|e_k|$	$\frac{\log |e_k|}{\log |e_{k-1}|}$
$k=1$	$10^{-3}$
$k=2$	$10^{-4}$	$1.33$
$k=3$	$10^{-5}$	$1.25$

Masodrendu:

	$|e_k|$	$\frac{\log |e_k|}{\log |e_{k-1}|}$
$k=1$	$10^{-3}$
$k=2$	$10^{-6}$	$2$
$k=3$	$10^{-12}$	$2$

Allitas: Tegyuk fel, hogy $|e_k|=c_k\cdot |e_{k-1}|,k=1,2,\dots$, ahol $0<\underline{c}\le c_k\le \overline{c}<1$. Valamilyen $\underline{c},\overline{c}$ konstansokra
Ekkor $x_k\to x^{\ast }$ monoton modan es elsorendben.

Biz.:
Monotonan, mivel $0<c_k<1⟹|e_k|<|e_{k-1}|$ $\forall k=1,2,\dots$ $⟹(|e_k|)$ sorozat monoton csokkeno.
Konvergal, mivel $|e_k|=c_k\cdot |e_{k_1}|\le \overline{c}\cdot |e_{k-1}|\le \overline{c}\cdot \overline{c}\cdot |e_{k-2}|\le \cdots \le {\overline{c}}^k\cdot |e_0|$. Mivel $\overline{c}<1$ ezert tenyleg ${\lim }_{k\to \infty }|e_k|=0$.

A feltetelben levo egyenletnek mindket oldalan logaritmust veve:

$$\log |e_k|=\log c_k+\log |e_{k-1}|$$ $$⟹\frac{\log |e_k|}{\log |e_{k-1}|}=\frac{\log c_k}{\log |e_{k-1}|}+1$$

Latszik, hogy $\log |e_{k-1}|\to -\infty$. Mostmar elegendo lenne belatni, hogy $\log c_k$ korlatos.

$$\log \underline{c}<\log c_k\le 0$$

Tehat $\frac{\log c_k}{\log |e_{k-1}|}\to 0⟹$ a jobb oldal $\to 1$ $⟹$ $p=1$ a konvergencia rendje, azaz elsorendu a konvergencia.

Allitas: Tegyuk fel, hogy $|e_k|=c_k\cdot |e_{k-1}{|}^{p}k=1,2,\dots$ , ahol $p>1$ es $0<\underline{c}\le c_k\le \overline{c}<+\infty$. Valamilyen $\underline{c},\overline{c}$ konstansokra. Tovabba ${\overline{c}}^{1/p-1}\cdot |e_0|<1$. Ekkor $(x_k)$ konvergens es a konvergencia rendje $p$.

Megjegyzes: Az utobbi feltetel azt jeletnti, hogy a konvergencia csak akkor kovetkezik, ha $x_0$ eleg kozel van $x^{\ast }$-hoz. Ugyanakkor $\overline{c}<+\infty$, es nem kell teljesulnie, hogy $\overline{c}<1$.

related: NumMod 1