NumMod 1 pset 5

I. Függvényminimalizálás lokális Taylor-közelítéssel

Emlék:

Egy $f:V\to \mathbb{R}$ kétszer folytonosan differenciálható funkcionál adott rendű lokális közelítése egy $x$ pontban:

• nulladrend: $f(x)$,
• elsőrend: $f(x)+⟨f^{\prime }(x),y-x⟩$,
• másodrend: $f(x)+⟨f^{\prime }(x),y-x⟩+\frac{1}{2}⟨f^{\prime \prime }(x)(y-x),y-x⟩$.

Itt $f(x)\in \mathbb{R}$, $f^{\prime }(x)\in V^{\ast }$, $f^{\prime \prime }(x)\in L(V,V^{\ast })\cong V^{\ast }\otimes V^{\ast }$, továbbá $f^{\prime \prime }(x)$ szimmetrikus.

1. Feladat

Tegyük fel, hogy értelmes a függvényt lokálisan elsőrendben közelíteni. Tegyük fel, hogy szeretnénk egy lépést tenni egy $x$ pontból kiindulva, úgy, hogy ezáltal a függvény értékét minél jobban csökkentsük. Mutassuk meg, hogy a modell szerint ehhez $-f^{\prime }(x)$ irányba érdemes lépnünk, amennyiben ez nem nullvektor. Mi a modell szerinti ideális lépéshossz?

Megoldás:

2. Feladat

Tegyük fel, hogy értelmes a függvényt lokálisan másodrendben közelíteni. Tegyük fel, hogy szeretnénk egy lépést tenni egy pontból kiindulva, úgy, hogy ezáltal a függvény értékét minél jobban csökkentsük. Mutassuk meg, hogy a modell szerint, amennyiben $f^{\prime \prime }(x)$ pozitív (szemi)definit, akkor ehhez egy $d$ irányba érdemes lépnünk, mely megoldása az

$$f^{\prime \prime }(x)(d)=-f^{\prime }(x)$$

egyenletnek. Mi a modell szerinti ideális lépéshossz?

Megoldás:

II. A Newton-iteráció hagyományos motivációja

Keressük azt az $r$ pontot, melyben egy $f:V\to V$ folytonosan differenciálható függvénynek gyöke van.
Tegyük fel, hogy egy $x$ pontból indulunk ki, és egy lépést szeretnénk tenni a gyökhely felé.

Ekkor

$$f(x)-f(r)=M(x,r)\cdot (x-r).$$

3.* Feladat

Mutassuk meg, hogy a fenti kontextus mellett

a)

$$M(x,r)=\underset{0}{\overset{1}{\int }}{f}^{\prime }\left(tx+(1-t)r\right)dt;$$

továbbá,

b) amennyiben az $x$ pontból $x+d$ pontba lépünk, akkor az ideális $d=r-x$ vektorra

$$M(x,r)d=-f(x).$$

Megoldás:

Newton-iteráció

Amennyiben az $M(x,r)$ kifejezést az $f^{\prime }(x)$ értékkel közelítjük, akkor megkapjuk a Newton-iterációt, melynek egy lépésének képlete $x\leftarrow x+d$, ahol

$$f^{\prime }(x)d=-f(x).$$

Minderre tehát úgy is gondolhatunk, hogy egy nemlineáris egyenletrendszer megoldását végessok lineáris egyenletrendszer egymásutáni megoldásával közelítjük meg.

4. Feladat

Legyen $f:V\to V$ egy affin függvény, azaz legyen $f(x)=Ax+b$.

a) Mi lesz az $M(x,r)$ kifejezés?

b) Tegyük fel, hogy $A$ invertálható is. Hány lépés alatt fog célbaérni a Newton-iteráció?

Megoldás:

5.* Feladat

Affin-invarianca: Legyen $\phi (x)=Ax+b$, és legyen ez invertálható. Az $f$ függvényre alkalmazott Newton-lépést leíró függvényt jelölje $n(f)$, azaz $n(f)(x)$ legyen az $x$ pontból induló Newton-lépés eredménye (korábbról $x+d$), az $f$ függvény esetén. Ekkor mutassuk meg, hogy

a) teljesül, hogy ${\phi }^{-1}(x)=A^{-1}(x-b);$

b) a Newton-lépés affin-invariáns a következő értelemben:

$$\phi \circ n(f\circ \phi )=n(f)\circ \phi .$$

c) Oldjuk meg az előző feladat b) részét ezen feladat segítségével, azaz mutassuk meg, hogy
$n(\phi )=x\mapsto {\phi }^{-1}(0).$

Megoldás:

III. A Newton-iteráció mint fixpontiteráció

Hogyan készíthetünk az $f(x)=0$ egyenletből fixpontiterációt?

A lineáris egyenletrendszereknél láthattuk, hogy az $Ax=b$ egyenlrendszert eltranszformáltuk például

$${\omega }^{-1}Ax={\omega }^{-1}b,\text{vagy}(I+D^{-1}(L+U))x={Đ}^{-1}b$$

módon. Ez iterációs lépésenként extra műveletek elvégzését jelenti, azonban az eredeti egyenlet megoldásához képest ezek gyorsan végrehajthatók.

Ennek ellenére $\omega$ és $D$ igyekeztek megragadni az eredeti mátrix “lényegét”: SZPD esetben a spektrum középpontja lett az optimális $\omega$; $D$ pedig a mátrix főátlójából képezett diagonális mátrix volt.

Nemlineáris esetben, amennyiben a függvényünk szép (pl. folytonosan differenciálható), akkor a függvény “lényegét” egy pontban a függvény deriváltja ragadhatja meg, így motiválható a következő átalakítás:

$$\begin{array}{rl}f(x)& =0,\\ -[f^{\prime }(x){]}^{-1}f(x)& =0,\\ x-[f^{\prime }(x){]}^{-1}f(x)& =x.\end{array}$$

IV. Lokális kvadratikus konvergencia

Legyen $f:V\to V$ folytonosan differenciálható függvény, melynek gyöke van az $x^{\ast }$ pontban, továbbá tegyük fel, hogy léteznek $m,M$ pozitív konstansok, melyekkel tetszőleges $x$ pontra az $x^{\ast }$ egy gömbi környezetéből
$m\Vert h\Vert \le \Vert f^{\prime }(x)h\Vert \le M\Vert h\Vert \forall h\in V.$

6. Feladat

Legyen a norma a $\Vert \cdot {\Vert }_2$. Teljesülhet-e a fenti feltétel a $0$ körüli zárt egységgömbön, ha

a) $f(x,y)=[2x-y,-x+2y]$;

b) $f(x,y)=[2x^3+x,y^3+y]$;

és ha igen, akkor milyen $M,m$ értékekkel?

Megoldás:

A feltétel mellett tehát amennyiben $d$ a Newton-lépésbeli eltolásvektor, akkor

$$\begin{array}{rl}{f}^{\prime }(x)\cdot (x+d-x^{\ast })& =f^{\prime }(x)\cdot (x-x^{\ast })-f(x)\\ & =f^{\prime }(x)\cdot (x-x^{\ast })-\left(f(x)-f(x^{\ast })\right)\\ & =f^{\prime }(x)\cdot (x-x^{\ast })-\underset{0}{\overset{1}{\int }}{f}^{\prime }(tx+(1-t)x^{\ast })\cdot (x-x^{\ast })dt\\ & =\underset{0}{\overset{1}{\int }}\left(f^{\prime }(x)-f^{\prime }(tx+(1-t)x^{\ast }\right)\cdot (x-x^{\ast })dt\end{array}$$

amiből mindkét oldalon normákat véve és kihasználva az $f^{\prime }$-re vonatkozó feltételeket (a baloldalt alulról, a jobboldalt pedig felülről becsülve) kapjuk, hogy

$$m\Vert x+d-x^{\ast }\Vert \le \left|\underset{0}{\overset{1}{\int }}1-tdt\right|M\Vert x-x^{\ast }{\Vert }^2,$$

azaz egy Newton-lépés végeztével az $x^{\ast }$-tól való távolság felülről becsülhető a lépés előtti távolság négyzetének konstansszorosával.

Emlék: Ha $x^{\ast }$ egy $f$ kontrakció fixpontja, akkor egy lépés során általában csak lineáris becslést kapunk:

$$\Vert f(x)-x^{\ast }\Vert =\Vert f(x)-f(x^{\ast })\Vert \le L\Vert x-x^{\ast }\Vert .$$

7. Feladat

Vizsgáljuk meg, hogy az alábbi $x^{\ast }$-hoz tartó $(x_n{)}_n$ valós számsorozatok esetén melyekre teljesül,

• egy lineáris becslés $\Vert x_{n+1}-x^{\ast }\Vert \le L\Vert x_n-x^{\ast }\Vert ,$ ahol $0<L<1$;

• egy kvadratikus becslés, azaz $\Vert x_{n+1}-x^{\ast }\Vert \le q\Vert x_n-x^{\ast }{\Vert }^2$, ahol $0<q$

a) $2^{-n}$

b) $2^{-n^2}$

c) $2^{-2^n}$

Megoldás:

8.* Feladat

Gondoljuk meg, hogy amennyiben egy $\varphi :V\to \mathbb{R}$ funkcionál kétszer folytonosan differenciálható, és egy $x^{\ast }$ pont körüli gömbi környezetben valamilyen $0<m\le M$ konstansokkal,

$m{h}^{T}h\le h^T{\varphi }^{\prime \prime }(x)h\le M{h}^{T}h\forall h\in V,$

teljesül, valamint ${\varphi }^{\prime }(x^{\ast })=0$, akkor a Newton-iterációt a ${\varphi }^{\prime }$ függvényre alkalmazhatjuk, és a konvergencia lokálisan kvadratikus lesz.

Ekkor egyébként a $\varphi$ függvény lokális minimumhelye $x^{\ast }$, akörül egyenletesen konvex, és valójában a Newton-iterációval ezt minimalizáljuk.

Megoldás:

9. Feladat

Teljesülnek ezek a feltételek az $f(x,y)={\sin }^2(x)+{\sin }^2(y)$ függvényre a $0$ körül?

Megoldás:

P/1. Feladat

Gondoljuk meg, hogy az $x_0=2^{255}$ pontból indulva az

a) $x_0{2}^{-n}$

b) $x_0{2}^{-n^2}$

c) $x_0{2}^{-2^n}$

sorozatok hány lépés alatt érnek be a $0$ pont $\frac{1}{2}$ sugarú, zárt gömbi környezetébe, majd írjunk programot és mérjük is meg, hogy valóban jól gondolkodtunk.

Megoldás:

P/2. Feladat

Alkalmazzuk a Newton-iterációt az $f(x,y)={\sin }^2(x)+{\sin }^2(y)$ függvény $0$-hoz legközelebb eső minimumhelyének meghatározására, ha tudjuk, hogy az a nulla körül konvex, az alábbiak szerint:

a) Számoljuk ki $f$ deriváltját.

b) Az $(\frac{1}{4},\frac{1}{4})$ pontból indítsunk Newton-iterációt az $f^{\prime }$ (egy) gyökének meghatározására.

Megoldás:

P/3. Feladat

Tekinsük az alábbi egyenletrendszert:

$$\{\begin{array}{ll}5x^2-y^2& =0,\\ y-0.25(\sin x+\cos y)& =0.\end{array}$$

Newton-iteráció segítségével keressük ennek a $(\frac{1}{2},\frac{1}{2})$ pont környezetében lévő megoldását!

Megoldás:

related: NumMod 1