Numerikus módszerek 1

Numerikus módszerek 1. 10. előadás: Nemlineáris egyenletek numerikus megoldása

Lócsi Levente ELTE IK

2013. november 18.

Tartalomjegyzék

1 Bolzano-tétel, intervallumfelezés

2 Fixponttételek, egyszerű iterációk

3 Konvergencia rendje

Problémafelvetés, megközelítési módok

Feladat Keressük meg egy f : R → R nemlineáris függvény gyökét, avagy zérushelyét. (∃?, 1, több?) f (x ∗ ) = 0,

x ∗ =?

Ekvivalens módon átfogalmazható (általában): keressük meg egy ϕ : R → R nemlineáris függvény fixpontját. x ∗ = ϕ(x ∗ ),

x ∗ =?

Tartalomjegyzék




Bolzano-tétel

Lásd Analízis. . .

Tétel: Bolzano-tétel Legyen a, b ∈ R, a < b. Ha f ∈ C [a, b] és f (a) · f (b) < 0, akkor ∃x ∗ ∈ (a, b) : f (x ∗ ) = 0. Megjegyzés: • C [a, b]: az [a, b] (zárt) intervallumon folytonos függvények

halmaza • f (a) · f (b) < 0: f (a) és f (b) különböző előjelűek • van gyök az (a, b) (nyílt) intervallumban

Intervallumfelezés Biz. (Bolzano-tétel): az intervallumfelezés módszerével 1 2

3

Kezdetben legyen x0 := a, y0 := b. Ismételjük: • Legyen zk := 12 (xk + yk ), az intervallum fele. • Ha f (xk ) · f (zk ) < 0, akkor xk+1 := xk , yk+1 := zk . • Ha f (xk ) · f (zk ) > 0, akkor xk+1 := zk , yk+1 := yk .

Álljunk meg, ha

• egyenlőség teljesül, ekkor x ∗ = zk , vagy • elértük a kívánt pontosságot, ekkor x ∗ ∈ (xk , yk ), és

yk − xk = teljesül.

b−a 2k

Intervallumfelezés

Megjegyzés: • Általában nem tapasztalunk egyenlőséget. • Az (xk ) és (yk ) sorozatok részletes tárgyalása: Analízis. . . • Hibabecslések:

|xk − x ∗ | <

b−a , 2k

|yk − x ∗ | <

b−a , 2k

|zk − x ∗ | <

b−a . 2k+1

Intervallumfelezés

Példa Közelítsük a p(x) = x 3 + 3x − 2 polinom egyik gyökét 0.1 pontossággal. Hány lépés szükséges? Próbálkozhatunk a [0, 1] intervallummal. . .

Egyértelműség

Tétel: gyök egyértelmű létezéséről Ha f ∈ C [a, b], f (a) · f (b) < 0, valamint f ∈ D(a, b) és f ′ > 0 (vagy < 0), akkor ∃!x ∗ ∈ (a, b) : f (x ∗ ) = 0. Biz.: Van gyök, f szig. mon., ezért egyértelmű is.

Tartalomjegyzék




Emlékeztető, ötlet

Emlékeztető: Iterációs módszerek LER-ek esetén. Ax = b x

(k+1)

⇐⇒

= ϕ(x

(k)

x = Bx + c ) = B · x (k) + c

Ötlet: Most, nemlineáris függvények zérushelyéhez: f (x) = 0

⇐⇒

x = ϕ(x)

xk+1 = ϕ(xk ) = . . .

Emlékeztető: fixpont, kontrakció Emlékeztető: fixpont Az x ∗ ∈ Rn pontot a ϕ : Rn → Rn leképezés fixpontjának nevezzük, ha x ∗ = ϕ(x ∗ ).

Emlékeztető: kontrakció A ϕ : Rn → Rn leképezés kontrakció, ha ∃q ∈ [0, 1), hogy kϕ(x) − ϕ(y )k ≤ q · kx − y k ,

∀x, y ∈ Rn .

Megj.: • kontrakció ≈ összehúzás, q: kontrakciós együttható

• most n = 1, k.k = |.|; R helyett sokszor elég [a, b] ⊂ R

Kontraktív valós függvények

Állítás Legyen ϕ : R → R függvény. Ha ϕ ∈ C 1 [a, b] és |ϕ′ (x)| < 1 (x ∈ [a, b]), akkor ϕ kontrakció. Megj.: C 1 : egyszer folyonosan differenciálható. Biz.: A Lagrange-féle középértéktétel segítségével. q := max ϕ′ (x) < 1 x ∈[a,b]

∀x, y ∈ [a, b] (x < y ) : ∃ξ ∈ (x, y ) :

|ϕ(x) − ϕ(y )| ≤ ϕ′ (ξ) · |x − y | ≤ q · |x − y | .

A Banach-féle fixponttétel Tétel: Banach-féle fixponttétel [a, b]-re Ha a ϕ : [a, b] → [a, b] függvény kontrakció [a, b]-n q kontrakciós együtthatóval, akkor 1

∃x ∗ ∈ [a, b] : x ∗ = ϕ(x ∗ ), azaz létezik fixpont,

2

a fixpont egyértelmű,

3

∀x0 ∈ [a, b] esetén az xk+1 = ϕ(xk ), k ∈ N0 sorozat konvergens és lim xk = x ∗ ,

4

és a következő hibabecslések teljesülnek:

k→∞

• |xk − x ∗ | ≤ q k · |x0 − x ∗ |, • |xk − x ∗ | ≤

qk · |x1 − x0 |. 1−q

Biz.: Már volt, csak most Rn helyett R (n = 1), sőt [a, b].

A Banach-féle fixponttétel

Következmény: iteráció konvergenciájának elégséges feltétele Ha ϕ : [a, b] → [a, b], ϕ ∈ C 1 [a, b] és |ϕ′ (x)| < 1 (x ∈ [a, b]), akkor az xk+1 = ϕ(xk ) iteráció konvergens ∀x0 ∈ [a, b] esetén. Megj.: Attól még lehet konvergens, ha valahol |ϕ′ | ≥ 1. (Nem szükséges feltétel.)

Brouwer-féle fixponttétel

Tétel: Brouwer-féle fixponttétel Ha ϕ : [a, b] → [a, b], ϕ ∈ C [a, b], akkor ∃x ∗ ∈ [a, b] : x ∗ = ϕ(x ∗ ). Biz.: ϕ(a), ϕ(b) ∈ [a, b]; g(x) := x − ϕ(x) • g(a) = a − ϕ(a) ≤ 0, • Egyik sem 0:

g(b) = b − ϕ(b) ≥ 0.

Bolzano: ∃x ∗ ∈ [a, b] : g(x ∗ ) = 0, azaz x ∗ = ϕ(x ∗ ).

• Valamelyik 0:

azaz a vagy b gyöke g-nek, azaz fixpontja ϕ-nek. Szemléletesen?

Egyszerű iterációk

Példa Keressük az x = cos x megoldását a [0, 1] intervallumon az xk+1 := cos xk , x0 ∈ [0, 1] iterációval. Konvergens ez a módszer? Adjunk hibabecslést! Hány lépés után kapjuk a gyököt 10−4 pontossággal?

Egyszerű iterációk

Példa Vizsgáljuk meg az x0 ∈ [0, 1], xk+1 = α · xk (1 − xk ) iterációk (logisztikus leképezés) viselkedését különböző α ∈ [0, 4] paraméterek esetén. Megj.: Általában nem kontrakció. Könnyen eljuthatunk differenciaegyenletek bifurkációinak és a káoszelmélet alapjainak vizsgálatához. . .

Tartalomjegyzék




Konvergencia rendje Definíció: konvergencia rendje Az (xk ) konvergens sorozat – határértékét jelölje x ∗ – p-edrendben konvergens, ha ∃c ∈ (0, +∞) ⊂ R, hogy |xk+1 − x ∗ | p = c. k→∞ |xk − x ∗ | lim

Megjegyzés: • p egyértelmű, p ≥ 1, √ p nem feltétlenül egész (A szelőmódszernél p = 1+2 5 ). • p = 1: elsőrendű vagy lineáris konv. (ekkor c ≤ 1) p = 2: másodrendű vagy kvadratikus konvergencia • Gyakorlatban a legalább p-edrendű konv. megfogalmazása: ∃K ∈ R+ : ∀k ∈ N0 : |xk+1 − x ∗ | ≤ K · |xk − x ∗ |p

Konvergencia rendje

Példa Mennyi a konvergenciarendje a következő nullsorozatoknak?

1 ; n2

1 2n

;

n

(q ) (|q| < 1);

1 22n

;

Konvergencia rendje √ Mit jelent az első- és másodrendű konvergencia számokban? ( 2) 1

p = 1, |xk+1 − x ∗ | < K · |xk − x ∗ |1 1.414184570312500 1.414245605468750 1.414215087890625 Minden lépésben kb. egy újabb tizedesjegy pontos.

2

p = 2, |xk+1 − x ∗ | < K · |xk − x ∗ |2 1.416666666666667 1.414215686274510 1.414213562374690 Minden lépésben kb. kétszer annyi tizedesjegy pontos.

Magasabbrendben konvergens sorozatokról „Aszimptotikus konvergencia tétele”

Tétel: p-edrendben konvergens iterációk Legyen ϕ : R → R, ϕ ∈ C p [a, b] és az xk+1 = ϕ(xk ) sorozat konvergens. Ha ϕ′ (x ∗ ) = · · · = ϕ(p−1) (x ∗ ) = 0, de ϕ(p) (x ∗ ) 6= 0, akkor a konvergencia p-edrendű és hibabecslése: |xk+1 − x ∗ | ≤

Mp |xk − x ∗ |p , p!

ahol Mp = max ϕ(p) (ξ) . ξ∈[a,b]

Biz.: Írjuk fel ϕ függvény x ∗ körüli Taylor-polinomját a p-edfokú maradéktaggal. . . Táblán. Meggondoltuk.

Magasabbrendben konvergens sorozatokról Következmény Ha ϕ : [a, b] → [a, b] kontrakció, és ϕ′ (x ∗ ) = · · · = ϕ(p−1) (x ∗ ) = 0, de ϕ(p) (x ∗ ) 6= 0, akkor 1

∃x ∗ ∈ [a, b] : x ∗ = ϕ(x ∗ ), azaz létezik fixpont,

2

a fixpont egyértelmű,

3

∀x0 ∈ [a, b] esetén az xk+1 = ϕ(xk ), k ∈ N0 sorozat konvergens és lim xk = x ∗ ,

4

és a következő hibabecslés teljesül:

k→∞

|xk+1 − x ∗ | ≤

Mp |xk − x ∗ |p . p!

Biz.: Ez a Banach-féle fixponttétel és az aszimptotikus konvergencia tételének összeházasításaként adódik.

Még egy példa egyszerű iterációra

Példa Írjunk fel fixpont-iteráció(ka)t az x 3 − x − 1 = 0 egyenlet megoldására, bizonyítsuk a konvergenciát. (a) x = x 3 − 1, √ (b) x = 3 x + 1.

Példák Matlab-ban

1

Intervallumfelezés számolása és szemléltetése.

2

Egyszerű iterációk és fixpontok elemzése az x = cos x egyenlet példáján keresztül.

3

A logisztikus leképezés viselkedésének bemutatása érdekességképpen.

Numerikus módszerek 1

Recommend Documents