NumMod 1 het 8

date: 2024.04.08

Megj.: $(x_k)\subset I$ mikor teljesül?
Négy eset amikor $x_0$-t jól megbálaszta, az egész $(x_k)$ sorozat monoton módon tart $x^{\ast }$-hoz, es így $(x_k)$ minden eleme $x_0$ és $x^{\ast }$ között lesz:

1. $f$ konkáv és szigorúan monoton nővő
   vegyük fel $x_0$-t balra $x^{\ast }$-tól ($x_0<x^{\ast }$)
   

   Transclude of f-konkáv-és-szig-mon-nő

2. $f$ konkáv és szigorúan monoton szökken
   vegyük fel $x_0$-t jobbra $x^{\ast }$-tól ($x_0>x^{\ast }$)

3. $f$ konvex és szigorúan monoton nő
   vegyük fel $x_0$-t jobbra $x^{\ast }$-tól ($x_0>x^{\ast }$)

4. $f$ konves és szigorúan monoton csökken
   vegyük fel $x_0$-t balra $x^{\ast }$-tól ($x_0<x^{\ast }$)

Egyenletrendszerek megoldása

Feladat: $f:{\mathbb{R}}^m\to {\mathbb{R}}^m$ és $f(x)=0$

1. Egyszerű iterációt alkalmazzuk

$$f(x)=0⟹F(x)=x$$

Fixpont-iterációt alkalmazzuk:

$$x_{t+1}=F(x_t)$$

ahol $x_0$ valamilyen kezdővektor.

2. Newton-módszer
   Skaláris esetben: $x_{t+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$
   Ennek analógiájára felírható a következő:

$$x_{t+1}=x_t-J_f^{-1}(x_t)\cdot f(x_t)$$

Megfelelő feltételek esetén másodrendben konvergál.
Az invertálás miatt nagyon költséges.
Lehet ezt a költséget csökkenteni, ha nem minden lépésben számoljuk újra a Jacobi-mátrix inverzét. Szokás például azt használni, hogy minden lépésben az $x_0$-beli Jacobi-mátrix inverzét használjuk. Ilyenkor csak elsőrendű konvergencia áll fent! Vagy lehet minen $k$ lépésenként újraszámolni a Jacobi-mátrix inverzét.

Interpolációs feladatok

1. Alapprobléma

Adott $f:\mathbb{R}\to \mathbb{R}$ függvényt csak diszrkét pontokban ismerjük. Például csak diszrkét pontokban vannak méréseink egy adatról.

Transclude of interpolációs-alapfeladat

$x_0,x_1,\dots ,x_n$ - interpolációs alappontok, ($x_0<x_1<\cdots <x_n$)
$f_k=f(x_k),k=0,\dots ,n$ - interpolált értékek

Cél: olyan folytonos függvényt keresünk, amely átmegy az összes ponton.
(Megj.: Azért keresünk folytonos függvényt, mert a legtöbb analízisbeli tétel és állítás folytonos függvényekre szól.)

Q.: Milyen típusú függvényt illeszünk?
Különösen kedvező tulajdonságúak a polinomok, tehát illesszünk polinomot.

Q.: Hanyadfokú polinomot illesszünk?
Legfeljebb $n$-ed fokú polinomot illesszünk.

Jel.: $P_n$ jelöli a legfeljebb $n$-ed fokú polinomok halmazát.

$n:=1$
$\exists !p\in P_1$ melyre $p(x_0)=f_0$ és $p(x_1)=f_1$

$n:=2$
$\exists p\in P_2$ melyre $p(x_0)=f_0$ és $p(x_1)=f_1$ és $p(x_2)=f_2$

Tétel

$\exists !p\in P_n$ melyre $p(x_k)=f_k\forall k=0,1,\dots ,n$

Bizonyítás:

1. Létezés (konstruktívan)
   Keressünk először olyan $l_m\in P_n$ függvényt, amelyre

$$l_m(x_k)=\{\begin{array}{l}1,\text{ ha }k=m\\ 0,\text{ ha }k\ne m\end{array}$$

Mivel $x_m$-en kívül az alappontokban el kell tűnnie, tartalmaznia kell az $(x-x_k),k\ne m$ gyöktényezőket, vagyi sa következő alakúnak kell lennie $l_m(x)$-nek

$$l_m(x)=c_m\cdot (x-x_0)(x-x_1)\cdot \dots \cdot (x-x_n)\cdot \frac{1}{x-x_m}=c_m\cdot \prod _{\stackrel{k=0}{k\ne m}}^n(x-x_k)$$

Már csak tudnunk kéne, hogy $c_m$ micsoda.
$l_m(x_m)=1$ tehát legyen

$$c_m\cdot \prod _{\stackrel{k=0}{k\ne m}}^n(x_m-x_k)=1⟹c_m=\frac{1}{{\prod }_{\stackrel{k=0}{k\ne m}}^n(x_m-x_k)}$$ $$⟹l_m(x)=\frac{1}{{\prod }_{\stackrel{k=0}{k\ne m}}^n(x_m-x_k)}\cdot \prod _{\stackrel{k=0}{k\ne m}}^n(x-x_k)$$ $$l_m(x)=\prod _{\stackrel{k=0}{k\ne m}}^n\frac{x-x_k}{x_m-x_k}$$

Mindegyik $x_m$ alapponthoz tartozik egy ilyen $l_m$ függvény.
Ezekből készítsük el a következő $p$ függvényt:

$$p(x):=\sum _{m=0}^n{f}_m\cdot l_m(x)$$

Ellenőrízzük, hogy ezen $p$ függvény tényleg az amit kerestünk:

$$p(x_k)=\sum _{m=0}^n{f}_m\cdot l_m(x_k)=f_k\cdot l_k(x_k)=f_k\cdot 1=f_k$$

Kell még, hogy $p\in P_n$
Ez igaz, mert $l_m\in P_n$ és $P_n$ vektortér, tehát a lineáris kombinációjuk is eleme $P_n$-nek

2. Egyértelműség
   Tegyük fel, hogy $p$ és $q$ függvények is teljesítik a kívánt tulajdonságokat, azaz:

• $p,q\in P_n$
• $p(x_k)=f_k=q(x_k),k=0,\dots ,n$

Legyen $d:=p-q$
Ekkor $d\in P_n$ és $d(x_k)=0\forall k=1,\dots ,n$
Így $d$ egy legfeljebb $n$-ed fokú polinom, melynek van $n+1$ darab különböző zéruzhelye, tehát $d\equiv 0$. Mert egy legfeljebb $n$-edfokú polinomnak legfeljebb $n$ zérushelye lehet, kivéve ha az azonosan a $0$ függvény.

Elnevezések:

• $l_m$ függvényeket Lagrange-féle interpolációs alappolinomok-nak nevezzük
• $p$ függvényt interpolációs polinomnak nevezzük
• $\sum f_m\cdot l_m$ alakot az interpolációs polinomnak a Lagrange-féle alak-jának nevezzük

Hátrány: Ha új adatpont ékezik, akkor az összes eddigi munkánk megy a kukába és újra kell kezdeni az interpolációt.

Kiküszöblése ennek a hátránynak megoldható Newton-féle alakkal.

2.

Tegyük fel, hogy egy $f:I\to \mathbb{R}$ folytonos függvényt az egész $I$ intervallumon ismerjük.
Szeretnénk polinommal közelíteni ezt a függvényt, hogy könnyebben tudjunk vele számolni.

Ötlet: Vegyünk fel adatpontokat ezen a függvényen és illesszünk interpolációs polinomot a felvett adatpontokra.

Q.: Mennyire halad közel az interpolációs polinom az eredeti függvényhez?

Tétel

Legyen $f\in C^{n+1}(I)$, és $x_0,x_1,\dots ,x_n\in I$ alappontok, $p$ pedig az $(x_k,f(x_k))$ pontokon átmenő interpolációs polinom.
Ekkor az $x\in I$ pontot és az összes $x_k$ alappontot tartalmazó legszűkebb intervallumban van olyan $\xi$ pont, amelyre

$$f(x)-p(x)=\frac{1}{(n+1)!}{\omega }_n(x)\cdot f^{(n+1)}(\xi )$$

ahol ${\omega }_n(x)=\prod (x-x_k)$ az úgynevezett alappont polinom.

Bizonyítás:

• Ha $x=x_k$ (valamelyik alappontra).
  Akkor mindkét oldalon $0$ van és bármilyen $\xi$-re fenn áll az egyenlőség

• Ha $x\ne x_k$ (bármelyik alappontra).
  Tekintsük a következő segédfüggvényt:

$$g(t)=f(t)-p(t)-c\cdot {\omega }_n(t)$$

ahol $c$ egy tetszőleges állandó.

$$g(x_k)=f(x_k)-p(x_k)-c\cdot {\omega }_n(x_k)=0\forall k=0,1,\dots ,n$$

Válasszuk meg a $c$ konstanst úgy, hogy $g(x)=0$ legyen.

$$g(x)=f(x)-p(x)-c\cdot {\omega }_n(x)=0$$ $$⟹c=\frac{f(x)-p(x)}{{\omega }_n(x)}$$

Ezen $c$ mellett $g$-nek van legalább $n+2$ zérushelye ($x_0,x_1,\dots ,x_n$ és $x$)

Rolle-tétel emék:
$f\in C[a,b]\cap D(a,b)f(a)=f(b)$ ekkor $\exists c\in (a,b)$ melyre $f^{\prime }(c)=0$

Rolle-tétel értelmében $g^{\prime }$-nek van legalább $n+2-1=n+1$ darab zérushelye.
Hasonló módan $g^{(n+1)}$-nek van legalább $n+1-n=1$ darab zérushelye.
Jelölje az egyik ilyen zérushelyet $\xi$

Deriváljuk $g(t)$ függvényt $(n+1)$-szer:

$$g^{(n+1)}(t)=f^{(n+1)}(t)-p^{(n+1)}(t)-c\cdot (n+1)!=f^{(n+1)}(t)-0-c\cdot (n+1)!=f^{(n+1)}(t)-c\cdot (n+1)!$$

$t=\xi$ pontban:

$$0=f^{(n+1)}(\xi )-\frac{f(x)-p(x)}{{\omega }_n(x)}\cdot (n+1)!$$ $$⟹f^{(n+1)}(\xi )=\frac{f(x)-p(x)}{{\omega }_n(x)}\cdot (n+1)!$$

related: NumMod 1