NumMod 1 het 7

date: 2024.03.25

Intervallum felezés

Megoldandó feladat: $f(x)=0$ (1)

Feltevések:

• $f\in C[a,b]$
• $f(a)f(b)<0$
  Ekkor Bolzano tétel szerint $\exists x^{\ast }\in (a,b)$, ahol $f(x^{\ast })=0$
  Miután a Bolzano tétel biztosítja nekünk a gyök létezését, keressük meg, hogy hol van ez a gyök.

Felépítünk egy intervallumsorozatot:
$I_0:=[a,b]$
Felezzük meg ezt az intervallumot, legyen $c=\frac{a+b}{c}$
Ezután vizsgáljuk $f(c)$ előjelét:

• $f(c)=0$ ekkor készen is vagyunk mert találtunk egy gyököt.
• Ha $f(c)\ne 0$, akkor $I_1:=[a,c]$ vagy $I_1:=[c,b]$, azt az intebrallumot választuk melyben az inteballum szélein az $f$ értéke ellentétes előjelű.

Megfelezzük $I_1$-et és folytatjuk az eljárást. Tehát megint megnézzük az intervallum felét és választjuk azt a felet, melyben az intervallum szélein az $f$ értéke ellentétes előjelű.

Az iteráció során mindig marad gyök az aktuálisa vizsgált intervallumban és mindig feleződik az intervallum hossza.

Látszik, hogy nem mindig fogunk olyan esetre találni, ahol $f(c)=0$ ls pontosan megtaláltuk a függvény gyökét, például $f(x)=x-\sqrt{2}$ függvénynek irracionális a gyöke de az iteráció során csak racionális pontokat vizsgálunk.

Tehát érdemes megbeszélni, hogy milyen pontossággal szeretnénk közelíteni a gyököt és mikor álljuk le.

Folytassuk addig az iterációt ameddig az aktuálisan vizsgált intervallum hossza nem éri el az előírt $\epsilon >0$ pontosságot.
Ekkor leállunk és válasszuk az aktuálisan vizsgált intervallum bármelyik pontját közelítő megoldásnak, mert az intervallumban minden pont legfeljebb $\epsilon$ távolságra lesz a valós gyöktől.

Meg lehet mondani előre, hogy hány iteráció után kell majd leállnunk?

Jelölés: $\mathrm{diam}(I_k):=I_k\text{ hossza}$

$\mathrm{diam}(I_k)=\frac{b-a}{2^k}<\epsilon$ ebből következik, hogy $k>\frac{\log \left(\frac{b-a}{\epsilon }\right)}{\log (2)}$
Észrevétel: A lépésszám teljesen független az $f$ függvénytől, de hát miért is függne, mert mindig csak intervallumokkal dolgozunk és az $f$ függvényt csak a következő intervallum kiválasztására használjuk, ami lehetne akár egy pénzérme dobás is.

Érdemes lenne beszélni még a konvergencia sebességéről.

$$|x_k-x^{\ast }|\le \mathrm{diam}(I_k)$$

ezen felsőkorlátok sorozata linárisan konvergens, mert $\mathrm{diam}(I_k)$ mindig feleződik és az előző fejezetben megbeszéltük, hogy ha a hibatag valahanyadrészére csökken akkor a konvergencia lineáris.
($c_k:=\frac{1}{2}\forall k$, láasd első állítás múlt óráról)

Egyszerű iteráció (fixpont-iteráció)

Megoldandó feladat: $f(x)=0$ (1)

Írjuk át a következő alakra:

$$\phi (x)=x\text{(2)}$$

ahol $\phi :\mathbb{R}\to \mathbb{R}$ valamilyen függvény.
Ekkor $f$ gyöke pontosan a $\phi$ fixpontja.

Érvényes a fixponttétel a következő változata:

Tétel

Legyen $H\subset \mathbb{R}$ zárt halmaz, és $\phi :H\to H$ kontrakció, tehát $\exists q\in (0,1)$, melyre $|\phi (x)-\phi (y)|\le q\cdot |x-y|\forall x,y\in H$. Ekkor

• egyértelműen létezik $\phi$-nek fixpontja, azaz $\exists !x^{\ast }$ melyre $\phi (x^{\ast })=x^{\ast }$
• tetszőleges $x_0\in H$ kezdőpontot választva a kovetkező módon definiált sorozat konvergens és tart $x^{\ast }$-hoz

$$x_{k+1}=\phi (x_k)$$

• a következő módon tudjuk becsülni a konvergencia sebességét $|x_k-x^{\ast }|\le \frac{q^k}{1-q}\cdot |x_1-x_0|$

Kérdés: Mikor kontrakció $\phi$?

Vegyük észre, hogy valamilyen módon a ${\phi }^{\prime }$ abszolútértékétől függ, hogy kontrakció-e a $\phi$.

Áll

Tegyük fel, hogy $\phi \in C(I)$ és $\phi \in D(\mathrm{int}(I))$ tehát folytonos az intervallumon és differenciálható a belsejében. Ha $\exists q\in [0,1)$, amely mellett $|{\phi }^{\prime }(x)|\le q\forall x\in \mathrm{int}(I)$, akkor $\phi$ kontrakció $I$-n a $q$ kontrakciószámmal.

Biz.: Legyen $x,y\in I$ két tetszőleges pont, $x<y$
Alkalmazzuk $\phi$-ra $[x,y]$ intervallumon a Lagrange-középérték-tételt:
Létezik $c\in (x,y)$ melyre

$$\phi (y)-\phi (x)={\phi }^{\prime }(c)\cdot (y-x)$$

Vegyünk mindkét oldalt abszolút értéket:

$$|\phi (x)-\phi (y)|=|{\phi }^{\prime }(c)|\cdot |x-y|\le q\cdot |x-y|\forall x,y\in I$$

Az egyenlőtlenség a feltétel miatt áll.

Példa:
$\phi (x)=\frac{1}{2}\cos (x)$ kontrakció-e a $\left[0,\frac{\pi }{2}\right]$ intervallumon? És ha igen mi a $q$ kontrakciószám?
$|{\phi }^{\prime }(x)|=\left|-\frac{1}{2}\sin x\right|\le \frac{1}{2}<1\forall x\in [0,\frac{\pi }{2}]$ (sőt $\forall x\in \mathbb{R}$)
Tehát $\phi$ kontrakció és $q=\frac{1}{2}$ jó választás kontrakciószámra.

Kérdés: Mi a konvergencia rendje?

Áll

Tegyük fel, hogy $\phi \in C^p[a,b]$, azaz $p$-szer folytonosan deriválható, és $\phi$ beleképez $[a,b]$-be és $\phi$ kontrakció $[a,b]$-n. Ha az $x^{\ast }$ fixpontban a következő igazak:

• ${\phi }^{\prime }(x^{\ast })=0$
• ${\phi }^{\prime \prime }(x^{\ast })=0$
• ${\phi }^{\prime \prime \prime }(x^{\ast })=0$
• ${\phi }^{(4)}(x^{\ast })=0$
  $⋮$
• ${\phi }^{(p-1)}(x^{\ast })=0$
• ${\phi }^{(p)}(x^{\ast })\ne 0$

Ekkor tetszőleges $x_0\in [a,b]$ pontból indítva a fixpont iterációt $p$-ed rendben konvergesn.

Biz:
A konvergenciát biztosítja a fixpont tétel, tehát elég a kovergencia rendjét belátni.
Írjuk fel $\phi$-nek $x^{\ast }$ körüli $p-1$-ed fokú Taylor polinomjának a hibáját az $x_k$ pontban
$\exists {\vartheta }_k$ az $x^{\ast }$ és $x_k$ között

$$\phi (x_k)-T_{p-1}(\phi (x_k),x^{\ast })=\frac{{\phi }^{(p)}({\vartheta }_k)}{p!}(x_k-x^{\ast }{)}^p$$ $$\phi (x_k)+\phi (x^{\ast })+0+0+\cdots +0=$$ $$x_{k+1}-x^{\ast }=\frac{{\phi }^{(p)}({\vartheta }_k)}{p!}(x_k-x^{\ast }{)}^p$$

Vegyük ezt abszolút értékben és vizsgáljuk így a konvergencia rendjét

$$|x_{k+1}-x^{\ast }|=\left|\frac{{\phi }^{(p)}({\vartheta }_k)}{p!}(x_k-x^{\ast }{)}^p\right|$$ $$|x_{k+1}-x^{\ast }|=\left|\frac{{\phi }^{(p)}({\vartheta }_k)}{p!}\right|\cdot |e_k{|}^p$$ $$|x_{k+1}-x^{\ast }|=c_k\cdot |e_k{|}^p$$

Kell még: $0<\underline{c}\le c_k\le \overline{c}<+\infty$
$\phi \in C^p[a,b]$ és ${\phi }^{(p)}(x^{\ast })\ne 0$ ekkor $|{\phi }^{(p)}(x)|$ $x^{\ast }$ egy kis környezetében is pozitív. Ha $k$ elég nagy, akkor mivel ${\vartheta }_k$ $x_k$ és $x^{\ast }$ között van

$$\left|\frac{{\phi }^{(p)}({\vartheta }_k)}{p!}\right|$$

beszorítható két pozitív konstans közé.

Newton módszer (érintő módszer)

Megoldandó feladat: $f(x)=0$ (1)

Alapötlet:
Tegyük fel, hogy $f$ differenciálható
Vegyünk fel egy tetszőleges $x_0\in D(f)$ kezdőpontot.
Húzzuk itt meg $f$ érintőjét.
Ennek $x$ tengellyel való metszéspontja legyen $x_1$

Megfelelő feltételekkel $x_1,x_2,\cdots \to x^{\ast }$

Kérdés: Mindig működik ez az eljárás?

A módszer képlete:
$x_k$-beli érintő: $x=f^{\prime }(x_k)(x-x_k)+f(x_k)$
$x$ tengellyel metszésőpontja:

$$0=f^{\prime }(x_k)(x-x_k)+f(x_k)$$ $$-f(x_k)=f^{\prime }(x_k)(x-x_k)$$ $$-\frac{f(x_k)}{f^{\prime }(x_k)}=x-x_k$$ $$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$$

Kérdés: Mit lehet mondani a Newton módszer konvergencia rendjéről?

All

Tegyuk fel, hogy az $x^{\ast }$ gyököt és az egész $(x_k)$ sorozatot tartalmlazó valamely $I$ intervallumban $f\in C^2(I)$, továbbá $\exists m_1,M_1,m_2,M_2>0$ konstansok, amelyekkel

$$m_1\le |f^{\prime }(x)|\le M_1$$

és

$$m_2\le |f^{\prime \prime }(x)|\le M_2$$

Ekkor $\frac{M_2}{2m_1}|e_0|<1$ esetén a Newton módszer másodrendben konvergens.

Biz:
Írjuk fel az $f$ függvény $x_k$ körüli elsőfokú Taylor polinomjának hibáját az $x^{\ast }$ pontban!

$$f(x^{\ast })-f(x_k)-f^{\prime }(x_k)(x^{\ast }-x_k)=\frac{f^{\prime \prime }({\vartheta }_k)}{2!}(x^{\ast }-x_k{)}^2$$

ahol ${\phi }_k$ valamely pont az $x_k$ és $x^{\ast }$ között.
osszunk $f^{\prime }(x_k)$-val mindkét oldalt

$$0-\frac{f(x_k)}{f^{\prime }(x_k)}-(x^{\ast }-x_k)=\frac{f^{\prime \prime }({\vartheta }_k)}{2f^{\prime }(x_k)}(x^{\ast }-x_k{)}^2$$ $$x_{k+1}-x^{\ast }=\frac{f^{\prime \prime }({\vartheta }_k)}{2f^{\prime }(x_k)}(x^{\ast }-x_k{)}^2$$ $$|e_{k+1}|=\left|\frac{f^{\prime \prime }({\vartheta }_k)}{2f^{\prime }(x_k)}\right|\cdot |e_k{|}^2$$ $$|e_{k+1}|=c_k\cdot |e_k{|}^2$$

Kell még, hogy $0<\underline{c}\le c_k\le \overline{c}<+\infty$
De pont a feltétel szerint

$$0<\frac{m_2}{2M_1}\le c_k\le \frac{M_2}{2m_1}<+\infty$$ $$\frac{M_2^{1/2-1}}{2m_1}\cdot |e_0|=\frac{M_2}{2m_1}<1$$

esetén másodrendű a konvergencia.

related: NumMod 1