Eötvös Loránd Tudományegyetem Természettudományi Kar
Heged¶s Dávid
Nemlineáris egyenletrendszerek numerikus megoldása BSc Szakdolgozat
Témavezet®:
Dr. Gergó La jos
Numerikus Analízis Tanszék
Budapest, 2014
Köszönetnyilvánítás
Szeretném megköszönni Dr. Gergó Lajos tanár úrnak, hogy elvállalta a konzulensi feladatkört, valamint ötleteivel, tanácsaival nagy mértékben segítette a munkámat. Köszönettel tartozom a családomnak és a barátaimnak, akik kitartóan támogattak az egyetemi éveim alatt.
2
Tartalomjegyzék
1. Nemlineáris egyenletek numerikus megoldása 1.1.
A Newton-módszer 1.1.1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Konvergencia tétel
5 5
. . . . . . . . . . . . . . . . . . . . . . . .
6
1.2.
A csillapított Newton-módszer . . . . . . . . . . . . . . . . . . . . . .
8
1.3.
A szel®módszer
9
1.4.
Monoton konvergencia
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2. Nemlineáris egyenletrendszerek numerikus megoldása 2.1.
10
12
A többdimenziós Newton-módszer . . . . . . . . . . . . . . . . . . . .
12
2.1.1.
. . . . . . . . . . . . . . . . . . . . . . .
14
2.2.
A csillapított Newton-módszer algoritmusa . . . . . . . . . . . . . . .
19
2.3.
A Broyden-módszer . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.4.
A folytatás módszere . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.5.
Alkalmazások
25
Konvergencia tételek
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3. Útmutatás a programok használatához
33
Irodalomjegyzék
34
3
Bevezetés
Az alkalmazott matematika számos területén (pl. zika, robotika, irányítástechnika) sokszor találkozhatunk olyan problémákkal, amelyekben több változó szerepel és közöttük több összefüggés is fennáll. Ha a változók legfeljebb az els® hatványon szerepelnek, akkor lineáris egyenletrendszert kapunk, azonban a természettudományos, technológiai és gazdasági folyamatok matematikai modelljei sokszor nemlineárisak, tehát magasabb hatványkitev®k is lehetnek. Sok esetben arra vagyunk kíváncsiak, hogy milyen feltételek mellett lesz a megadott függvényünk nulla. Ekkor az
f (x) = 0
nemlineáris egyenletrendszer megoldásait közelíthetjük különböz® numerikus módszerekkel. A szakdolgozatomban ezt a feladatot a Newton-módszerrel és annak változataival fogom megoldani. Ezen iterációs módszereknek az az el®nye, hogy gyorsabban mint lineárisan konvergálnak, viszont általában nem minden kezd®vektorra. El®fordulhat, hogy már a futtatáshoz szükséges információk megszerzése is nehézkes (kezd®pont, derivált), ekkor csillapítással vagy a Broyden-módszerrel próbálkozhatunk. Magasabb dimenzióban fontos a konvergencia globalizálása akár a futási id® kárára is, ezt fogjuk látni a folytatás módszerénél. A dolgozat végén alkalmazásokat tekinthet meg az Olvasó, melyekhez MATLAB segítségével készítettem programokat. A programok M-fájljai a CD-mellékleten találhatók, az utolsó fejezetben segítséget nyújtok a használatukhoz.
4
1. fejezet
Nemlineáris egyenletek numerikus megoldása
1.1. Legyen ha
f
A Newton-módszer f :R→R
el®jelet vált
a
függvény, amely folytonos az és
b
[a, b]
intervallumon,
a < b.
között, akkor az
f (x) = 0 egyenletnek van gyöke melynek során egy
x0
[a, b]-ben.
(1.1)
A Newton-módszer egy olyan iterációs eljárás,
kezd®pontból szeretnénk közelíteni (1.1) egyenlet egyik gyö-
két. Ehhez keressünk egy
f (x)
Ekkor
δx javítást, melyre x0 + δx már gyök lesz. Tegyük fel, hogy
kétszer folytonosan dierenciálható és tekintsük a Taylor-sorát:
0 = f (x0 + δx) = f (x0 ) + f 0 (x0 )δx + O(δx2 ). Legyen
x1 := x0 + δx
és hanyagoljuk el a másodrend¶ tagot. Ekkor a
0 = f (x0 ) + f 0 (x0 )(x1 − x0 ) egyenlet adódik. Feltéve, hogy
f 0 (x0 ) 6= 0, x1 x1 = x0 −
Értelemszer¶en folytatva, adott
x0
(1.2)
átrendezéssel kiszámítható:
f (x0 ) . f 0 (x0 )
esetén a következ® iterációs eljárást kapjuk:
xk+1 = xk − (f 0 (xk ))−1 f (xk ), 5
k = 0, 1, . . . .
(1.3)
Egy dimenziós esetben jól látható a Newton módszer mértani jelentése. Húzzunk a függvény
f (x0 )
pontjához érint®t. Az érint® egyenlete a következ®:
y = f (x0 ) + f 0 (x0 )(x − x0 ). Bizonyos feltételek mellett azt várjuk, hogy ennek az egyenesnek a gyöke az kének egy jobb közelítése lesz. Ha az érint® zérushelyét
x1
f
gyö-
jelöli, akkor
0 = f (x0 ) + f 0 (x0 )(x1 − x0 ), ez pedig megegyezik az (1.2) egyenlettel, tehát az eljárást folytatva következik az (1.3) iteráció.
1.1.1. De níció. Tegyük fel, hogy egy iterációs eljárás az xk ∈ Rn sorozatot állítja el®, ez a sorozat konvergál a k.k normában, lim xk = x∗ , x0 6= x∗ . Azt mondjuk, hogy az xk sorozat x0 -ból kiindulva, (legalább) κ-rendben konvergál, ha κ ≥ 1, és van olyan nemnegatív C konstans, hogy érvényes kxk+1 − x∗ k 6 Ckxk − x∗ kκ ,
k = 0, 1, . . .
.
A κ > 1 renddel való konvergenciát szuperlineáris konvergenciának nevezzük.
1.1.2. De níció. Egy iterációs eljárásról akkor mondjuk, hogy lokálisan konvergál az x∗ megoldáshoz, ha van olyan pozitív δ sugarú G(x∗ , δ) gömb, amely a következ® tulajdonságokkal rendelkezik: tetsz®leges x0 ∈ G(x∗ , δ) esetén az iteráció által el®állított xk sorozat konvergál x∗ -hoz; G(x∗ , δ)-n kívül viszont van olyan x0 vektor, amelyre ez nem igaz. G(x∗ , δ) az x∗ vonzási gömbje. 1.1.3. De níció. Egy iterációs eljárásról akkor mondjuk, hogy globálisan konvergál az x∗ megoldáshoz, ha tetsz®leges x0 kezd®vektor esetén az iteráció által el®állított xk sorozat konvergál x∗ -hoz. 1.1.1.
Konvergencia tétel
1.1.4. Tétel. (A Newton-módszer konvergenciája) Legyen I := (a, b), f : I → R olyan függvény, hogy a deriváltja Lipschitz-folytonos I -ben L Lipschitz állandóval, azaz: |f 0 (x) − f 0 (y)| 6 L|x − y| ∀x, y ∈ I ; 6
továbbá létezzék egy α > 0, melyre |f 0 (x)| ≥ α1 , ∀x ∈ I . Ha az f (x) = 0 egyenletnek I -ben van x∗ gyöke, akkor létezik olyan δ > 0, hogy x0 ∈ I -b®l és |x0 − x∗ | < δ -ból következik, hogy: 1. a
(1.3)
sorozat jól de niált;
2. limk→∞ xk = x∗ ; 3. |xk+1 − x∗ | 6 C|xk − x∗ |2 , C :=
Bizonyítás.
Kezdetben legyen
fk0 := f 0 (xk ) 6= 0.
Lα . 2
k = 0, fk := f (xk ).
A feltételb®l következik, hogy
Végezzük el a következ® átalakításokat:
xk+1 −x∗ = xk −x∗ −(fk0 )−1 fk = xk −x∗ −(fk0 )−1 (fk −f∗ ) = −(fk0 )−1 (fk −f∗ −fk0 (xk −x∗ )), ahol
f∗ := f (x∗ ) = 0.
általános
x, y ∈ I -re.
Legyen
r(xk , x∗ ) := (fk − f∗ − fk0 (xk − x∗ ),
és külön becsüljük
A Newton-Leibniz formula felhasználásával az
Z
0
x
f 0 (z) − f 0 (x) dz
r(x, y) = f (x) − f (y) − f (x)(x − y) = y
z = y + t(x − y) helyettesítéssel következik, hogy Z 1 r(x, y) = (x − y) f 0 (y + t(x − y)) − f 0 (x) dt t ∈ [0, 1] .
azonosság adódik. A
0 Most használjuk ki, hogy
f0
Lipschitz-folytonos:
2
1
Z
|r(x, y)| 6 L(x − y)
(1 − t)dt = 0
Ezt a becslést, valamint az
|fk0 | ≥
L (x − y)2 . 2
1 feltételt felhasználva kapjuk a következ®t: α
|xk+1 − x∗ | 6
Lα |xk − x∗ |2 . 2
A konvergencia belátásához válasszunk olyan
|xk − x∗ | 6 δ -t,
hogy
xk ∈ I
Lα|xk − x∗ | 6q<1 2 teljesüljön, hiszen ekkor igaz a következ®:
|xk+1 − x∗ | 6 q|xk − x∗ | 6 |xk − x∗ |, 7
k = 0, 1, . . .
.
és
Alkalmas
δ -val
elérhetjük, hogy
|xk+2 − x∗ | 6
xk+1 ∈ I .
Ilyenkor már
xk+2
is de niálva van, és
Lα |xk+1 − x∗ |2 6 q|xk+1 − x∗ | 6 q 2 |xk − x∗ | 6 |xk − x∗ | 6 δ, 2
xk+2 ∈ I . Folytatva az eljárást láthatjuk, hogy ez pont a konvergenciát jelenti.
tehát
Az (1.1.4) tételben látjuk, hogy a Newton-módszer másodrendben (másnéven négyzetesen vagy kvadratikusan) konvergens. Továbbá az is kiderül, hogy ehhez közel kell legyen
x0
elég
x∗ -hoz, tehát (általában) csak lokálisan konvergens. A kés®bbiekben
lesz még szó szuperlineárisan konvergens módszer globalizálásáról.
1.2.
A csillapított Newton-módszer
A Newton-módszer alkalmazása során különböz® problémák merülhetnek fel. Például, ha a kezd®pontban a függvény deriváltja nulla, akkor nem tudjuk meghatározni a következ® pontot. Ha pedig a választott kezd®pont nincs elég közel a gyökhöz, akkor el®fordulhat, hogy az iteráció lassabban vagy egyáltalán nem fog konvergálni, esetleg végtelen ciklusba kerül. A továbbiakban azt az esetet fogom megvizsgálni, amikor kor ugyanis
0
f (x∗ ) = 0,
x∗
többszörös gyök. Ek-
és az ilyen esetet eddig kizártuk a tárgyalásból. Legyen
elegend®en sokszor dierenciálható, és rendelkezzen
t-szeres
gyökkel
f
x∗ -ban, t ≥ 1.
Ekkor Taylor-sorfejtésének eleje a következ®:
f (x) = (x − x∗ ) Legyen
Ezek
ek := xk − x∗ .
t
1 (t) x − x∗ (t+1) f (x∗ ) + f (x∗ ) + . . . , t! (t + 1)!
f (t) (x∗ ) 6= 0.
Ekkor az alábbi egyenleteket kapjuk:
ek (t+1) (ek )t (t) 2 f (xk ) = f (x∗ ) + f (x∗ ) + O(ek ) , t! t+1 i (ek )t−1 h (t) ek f 0 (xk ) = f (x∗ ) + f (t+1) (x∗ ) + O(e2k ) . (t − 1)! t f (xk ) felhasználásával az ek+1 = ek − -ból elegend®en kicsi ek -ra f 0 (x(k) )
hogy
ek (t) ek (t+1) 2 ek+1 = ek − f (x∗ ) + f (x∗ ) + O(ek ) ∗ t t+1 ek (t) −1 (t+1) 2 ∗ f (x∗ ) 1 − (t) f (x∗ ) + O(ek ) , tf (x∗ ) 8
következik,
,mert
ek f (t+1) (x∗ ) + O(e2k ) 1 + (t) tf (x∗ )
−1
= 1−
ek (t+1) 2 f (x∗ ) + O(ek ) . tf (t) (x∗ )
Tehát:
ek+1
ek ek (t) (t+1) 2 = ek − (t) f (x∗ ) − f (x∗ ) + O(ek ) = tf (x∗ ) t(t + 1) =
Láthatjuk, hogy
1 1− t
ek + e2k
f (t+1) (x∗ ) + O(e3k ). t2 (t + 1)f (t) (x∗ )
t = 1-re négyzetes a konvergencia, azaz a klasszikus Newton-módszer
hajtódik végre. Viszont ha
t > 1,
akkor csak els® rendben, vagyis lineárisan konver-
gens. Ha
t ismert, akkor a Newton eljárás következ® módosítása biztosítja újra a négyzetes
konvergenciát:
x0
adott,
xk+1 = xk − t(f 0 (xk ))−1 f (xk ),
k = 0, 1, . . . .
Tehát ebben az esetben az eredeti Newton-lépést hosszabbítani kellett ahhoz, hogy javuljon a konvergencia. Általános esetben viszont fordítva érdemes eljárni:
t<1
esetén ugyanis a Newton-módszer lokális konvergenciáját globálissá terjeszthetjük ki, ugyanakkor a konvergencia sebessége csökken. Ezt nevezzük csillapított Newtonmódszernek. A gyakorlatban ez az eljárás általában eléri azt a gyök-közelítést, amelyet a klasszikus módszernek adtunk meg, onnantól kezdve pedig
1.3.
t=1
teljesül.
A szel®módszer
A Newton-módszer másik gondja a derivált kiszámítása, amely fokozottan jelentkezik egyenletrendszerek esetében. Ez nagy jelent®séggel bír, hiszen az alkalmazás során el®fordulhat, hogy a deriváltfüggvény nem áll a rendelkezésünkre, nem tudjuk kiszámítani, esetleg
f -re
nem is létezik zárt képlet. A feladatunk tehát az, hogy ki-
küszöböljük az iterációs képletb®l a deriváltat, és helyettesítsük annak valamilyen közelítésével. Erre egy lehet®ség a dierenciahányadossal való helyettesítés:
f 0 (xk ) ≈
f (xk + h) − f (xk ) =: Ak h 9
Így az iterációt a következ® alakban írhatjuk fel:
x0 Amennyiben
f
xk+1 = xk −
adott,
f (xk ) , Ak
k = 0, 1, . . . .
kétszer folytonosan dierenciálható (ezzel némileg megszorítva a kon-
vergencia tétel feltételeit), akkor a dierenciaképlet els® renddel approximálja a deriváltat. Legyen
M2 := max[a,b] |f 00 (x)|.
Ekkor tehát:
1 |f 0 (xk ) − Ak | 6 M2 |h|. 2 Belátható, hogy létezik olyan
h-kiválasztás, hogy az iteráció konvergenciája továbbra
is másodrend¶ marad, annak ellenére, hogy Egy másik lehet®ség, ha az
f 0 (xk )-t
az
x∗
ismeretlen.
[xk−1 , xk ]f
osztott dierenciával helyettesít-
jük. Ennek el®nye, hogy ebben az esetben nincs szükség külön
x0
és
x1 6= x0
adott,
xk+1 = xk −
f (xk ) , [xk−1 , xk ]f
f -érték kiszámítására:
k = 0, 1, . . . .
1.3.1. Tétel. (A szel®módszer konvergenciája) Teljesüljenek a Newton-módszer konvergencia tételének feltételei, legyen f ∈ C 2 [a, b]. Ekkor a szel®módszer vagy véges √ 1 k -ra megáll az f (x) = 0 megoldásán vagy (lokálisan) konvergens (1 + 5) renddel. 2
1.3.2. Megjegyzés.
Vegyük észre, hogy a Newton-módszer egy függvényértéket
és egy deriváltértéket követel meg egy iterációs lépésben. Ugyanakkor a szel®módszer esetében csak egyetlen függvénykiértékelésre van szükségünk. Feltehetjük, hogy ugyanannyi id®be kerül kiszámítani
f -et
és
f 0 -t.
Ekkor egy Newton-lépés alatt két
lépést lehet végrehajtani a szel®módszerrel, tehát az utóbbi egyértelm¶en gyorsabb eljárás.
1.4.
Monoton konvergencia
Igazolható, hogy létezik olyan függvényosztály (a konvex vagy konkáv függvények osztálya), amelyre a Newton-módszer monoton és globális konvergenciája egyaránt teljesül. Ekkor nincs szükségünk arra, hogy hogy csillapított módszert használjunk.
10
x0
elég jó közelítés legyen, és arra sem,
1.4.1. Tétel. Legyen f ∈ C 2 [a, b], f 0 (x) 6= 0 és f 00 (x) 6= 0 az [a, b] intervallumon, amely végtelen is lehet. Létezzen x∗ ∈ (a, b), melyre f (x∗ ) = 0. Ekkor az (1.3)-ban de niált iterációban xk → x∗ monoton módon, ha f (x0 )f 00 (x0 ) > 0 és x0 ∈ [a, b]. 1.4.2. Megjegyzés.
f 0 (x) 6= 0
A tétel lényeges feltételei az
Ugyanis, ha megengednénk, hogy az
és az
f 00 (x) 6= 0.
f 0 (x) = 0 legyen valamely x-ekre, akkor ezeken
a helyeken a függvényhez húzott érint®k párhuzamosak lennének az hát az iteráció nem tudna továbblépni. Ha pedig az (azaz sérül a konvexitás vagy a konkávitás), akkor
f 00 (x) 6= 0
{xk }
x-tengellyel, te-
feltétel nem teljesül
sorozat bonyolultan visel-
kedhet, esetleg végtelen ciklusba kerülhet. Kevésbé fontos az
f (x0 )f 00 (x0 ) > 0
ton lesz a konvergencia
x1 -t®l
feltétel, mivel a nem teljesülése esetén is mono-
kezdve.
Lássunk erre egy példát: legyen
f 00 (x) > 0
és
f (x0 ) < 0.
Ekkor
f 0 (x) > 0
az alábbiak:
f (x) ≥ f (x0 ) + f 0 (x0 )(x − x0 ), f (x1 ) ≥ f (x0 ) + f 0 (x0 )(x1 − x0 ) = 0. Tehát
x0 < x∗ 6 x1 ,
azaz
x1 -re
már teljesül az
11
f (x1 )f 00 (x1 ) > 0
feltétel.
és igazak
2. fejezet
Nemlineáris egyenletrendszerek numerikus megoldása
2.1.
A többdimenziós Newton-módszer
Nemlineáris egyenletrendszerek megoldása gyakran bizonytalan kimenetel¶, fordulatokban gazdag vállalkozás. Megoldásukra szinte kizárólag a Newton-módszer változatait használjuk, mivel már az els® deriváltak meghatározása se mindig könny¶ feladat, továbbá a magasabbrend¶ módszerek még az egydimenziós esetben sem feltétlenül hatékonyabbak. Ebben a fejezetben a fels® indexek nem hatványkitev®ket, hanem vektorok komponenseit fogják jelölni. Legyen
f : Rn → Rn .
A feladat a következ®: keressük az
f (x) =
f1 (x1 , . . . , xn ) . . .
fn (x1 , . . . , xn )
rendszernek egy megoldását. Tegyük fel, hogy oldása és
x0
az
x∗ -nak
f
=0
dierenciálható,
(2.1)
x∗
az
f
egy meg-
egy közelítése. Ekkor a másodrend¶ tagok elhanyagolásával
kapott Taylor-polinom a következ®:
0 = f (x∗ ) ≈ f (x0 ) + Df (x0 )(x∗ − x0 ),
12
,ahol
∂f1 ∂f1 ∂x1 . . . ∂xn . . . . Df (x0 ) = , . . ∂fn ∂fn ... 1 ∂x ∂xn x=x0 Ha a
Df (x0 )
x ∗ − x0 =
x1∗ − x10 . . .
xn∗ − xn0
.
Jacobi-mátrix reguláris, akkor az
f (x0 ) + Df (x0 )(x1 − x0 ) = 0 egyenletb®l
x1 -et
kifejezve a következ®t kapjuk:
x1 = x0 − (Df (x0 ))−1 f (x0 ), ,ahol (bizonyos feltételek teljesülése mellett) közelítése lesz
x1
az
x0
javítását adja, tehát jobb
x∗ -nak.
Így a (2.1) egyenletrendszer megoldására szolgáló iterációs
adott,
xk+1 = xk − (Df (xk ))−1 f (xk ),
eljárás:
x0
2.1.1. Megjegyzés.
Ha a
Df (x0 )
k = 0, 1, 2, . . . .
Jacobi-mátrix szinguláris, akkor más
x0
kezd®-
vektort kell megadnunk.
2.1.2. Megjegyzés.
Valójában az iteráció minden lépésében egy lineáris egyenlet-
rendszert oldunk meg, ezért célszer¶ a következ® alakban megadni:
x0
adott,
Df (xk )δxk = −f (xk ),
xk+1 = xk + δxk ,
k = 0, 1, 2, . . . .
Láthatjuk, hogy ilyenkor az inverz mátrixot nem számítjuk ki, helyette alkalmazzuk például a Gauss-elimináció megfelel® változatát.
A Newton-módszer minden lépésében meg kell határoznunk a Jacobi-mátrixot, vagyis
n2
függvényértéket. Ez problémát jelenthet az alkalmazások során, ezért (az egydi-
menziós eset mintájára) dierenciaképletekkel közelíthetjük a deriváltakat. Többdimenziós esetben diszkretizált Newton-módszerr®l beszélünk, ha minden az
Df (xk )
k.
lépésben
Jacobi-mátrix elemeit az alábbi els®rend¶ közelítéssel számoljuk ki:
fi (xk + hij ej ) − fi (xk ) ∂fi ≈ , ∂xj hij 13
i, j = 1, . . . , n,
(2.2)
, ahol
ej a j . koordináta-egységvektor és hij alkalmas nemnulla lépéstávolság. Könnyen
láthatjuk, hogy ilyenkor
2n2
függvényérték meghatározására van szükségünk, tehát
romlik a futási id®. Gyakori eset azonban, hogy a nemlineáris egyenletrendszerekhez tartozó Jacobi-mátrix ritkamátrix, ekkor pedig a közelítés m¶veletigénye jelent®s mértékben csökkenthet®. Például ha a mátrix tridiagonális, akkor csupán
3n − 2
nemzérus elem van, tehát ennyi függvényérték kiszámítása elegend®.
2.1.1.
Konvergencia tételek
A következ®kben belátom, hogy a többdimenziós Newton-módszer kvadratikusan konvergens. Ennek a speciális esetét már láttuk az els® fejezetben. Mindenekel®tt következzen két de níció és egy lemma, melyre szükség lesz a bizonyítás során.
2.1.3. De níció. Legyen f : Rn → Rn , és tekintsük az f (x) = 0 egyenletrendszert. Az f függvényr®l azt mondjuk, hogy dierenciálható egy x0 ∈ Rn pontban, ha létezik A : Rn → Rn lineáris operátor, melyre lim
x→x0
kf (x) − f (x0 ) − A(x − x0 )k = 0, kx − x0 k
,ahol k.k norma Rn -en. Esetünkben A megegyezik a Df (x0 ) Jacobi-mátrixszal.
2.1.4. De níció. Legyen C ⊆ Rn tartomány. Azt mondjuk, hogy C konvex, ha minden x, y ∈ C -re és t ∈ [0, 1]-re az [x, y] := {z = tx + (1 − t)y} halmaz is eleme C -nek.(Tehát x és y összeköt® szakasza benne van C -ben.) 2.1.5. Lemma. Legyen C0 ⊆ Rn konvex tartomány, f : Rn → Rn . Ha f dierenciálható C0 -on és létezik γ , melyre kDf (x) − Df (y)k 6 γkx − yk (∀x, y ∈ C0 )
teljesül, akkor minden x, y ∈ C0 -ra igaz a következ® becslés: kf (x) − f (y) − Df (y)(x − y)k 6
Bizonyítás.
De niáljuk a
ϕ : [0, 1] → Rn
γ kx − yk2 . 2
függvényt a következ®képpen:
ϕ(t) := f (y + t(x − y))
14
Ekkor
ϕ
ϕ
dierenciálható minden
t ∈ [0, 1]
helyen (x, y
∈ C0 ).
Most határozzuk meg
deriváltját a láncszabály alkalmazásával:
ϕ0 (t) = Df (y + t(x − y))(x − y). A lemma feltételét felhasználva a következ® egyenl®tlenség írhaó fel:
kϕ0 (t) − ϕ0 (0)k = k(Df (y + t(x − y)) − Df (y))(x − y)k 6 6 kDf (y + t(x − y)) − Df (y)kkx − yk 6 6 γtkx − yk2
(0 6 t 6 1).
Vezessünk be egy újabb jelölést! Legyen:
∆ := f (x) − f (y) − Df (y)(x − y) = ϕ(1) − ϕ(0) − ϕ0 (0) = Z 1 (ϕ0 (t) − ϕ0 (0))dt. = 0 Mindezek felhasználásával könnyen adódik a lemma állítása:
Z
1
Z
1
kϕ0 (t) − ϕ0 (0)kdt 6 (ϕ (t) − ϕ (0))dtk 6 0 0 Z 1 γ 6 γkx − yk2 t dt = kx − yk2 . 2 0
k∆k = k
0
0
2.1.6. Tétel. Legyen C ⊆ Rn nyílt halmaz, C0 ⊆ C egy konvex halmaz, valamint f : C → Rn függvény, amely dierenciálható minden x ∈ C0 pontban és folytonos C -n. Legyen x0 ∈ C0 , továbbá r, α, β, γ, h pozitív konstansok és teljesüljenek az alábbiak: Sr (x0 ) := {x : kx − x0 k < r} ⊆ C0 , αβγ h := < 1, 2 α r := , 1−h
és f (x)-re legyenek igazak a következ® tulajdonságok: a) kDf (x) − Df (y)k 6 γkx − yk (∀x, y ∈ C0 ) b) Df (x)−1 létezik és teljesül, hogy kDf (x)−1 k 6 β , ∀x ∈ C0 -ra 15
c) kDf (x0 )−1 f (x0 )k 6 α. Ekkor 1. az alábbi sorozat jól de niált: x0 adott, xk+1 = xk − Df (xk )−1 f (xk ),
k = 0, 1, . . .
és xk ∈ Sr (x0 ) minden k ≥ 0-ra, 2. limk→∞ xk = x∗ , x∗ ∈ Sr (x0 ) és f (x∗ ) = 0, 3. minden k ≥ 0-ra
k
h2 −1 kxk − x∗ k 6 α . 1 − h2k
Mivel 0 < h < 1, ezért a Newton-módszer legalább másodrendben konvergens.
Bizonyítás. az
xk+1
(1.): A (b) feltétel szerint minden
sorozat jól de niált, ha
xk ∈ Sr (x0 )
és (c)-szerint
k = 1-re.
állítás, tehát
xi ∈ Sr (x0 ), ∀i = 2, . . . , k .
x ∈ C0 -ra
minden
létezik a
k ≥ 0-ra.
Df (x)−1 ,
Ez teljesül
Teljes indukciót alkalmazunk: tegyük fel, hogy Be kell látnunk, hogy
ezért
k = 0-ra
k -ig
igaz az
xk+1 ∈ Sr (x0 ),
ehhez
tekintsük (b)-t és a következ® egyenl®tlenséget:
kxk+1 − xk k = kDf (xk )−1 f (xk )k 6 βkf (xk )k = = βkf (xk ) − f (xk−1 ) − Df (xk−1 )(xk − xk−1 )k, ,ahol de níció szerint
f (xk−1 ) + Df (xk−1 )(xk − xk−1 ) = 0.
(2.3)
Most használjuk fel a (2.1.5)-ös lemmát:
kxk+1 − xk k 6
βγ kxk − xk−1 k2 . 2
Ezután vizsgáljuk meg a következ® becslést: k −1
kxk+1 − xk k 6 αh2
Jól látható, hogy a (c) tulajdonság miatt ez teljesül alkalmazunk, feltesszük, hogy
kxk+1 − xk k 6
k -ig
.
(2.4)
k = 0-ra.
igaz és belátjuk, hogy
Ismét teljes indukciót
k + 1-re
is igaz marad:
βγ βγ 2 2k −2 k kxk − xk−1 k2 6 α h = αh2 −1 . 2 2 16
Felhasználva az el®bbi becslést azonnal adódik az (1.) állítás:
kxk+1 − x0 k 6 kxk+1 − xk k + kxk − xk−1 k + . . . + kx1 − x0 k 6 1 k 6 α(1 + h + h3 + h7 + . . . + h2 −1 ) < α = r, 1−h xk+1 ∈ Sr (x0 ).
ami azt jelenti, hogy
(2.): A (2.4) becslést felhasználva belátjuk, hogy hogy
∀ε > 0-hoz ∃nε ,
hogy
{xk }
egy Cauchy sorozat, tehát
∀m ≥ n > nε -ra kxm − xn k < ε:
kxm+1 − xn k 6 kxm+1 − xm k + kxm − xm−1 k + . . . + kxn+1 − xn k 6 6 αh2 ,mivel
x∗ ,
n −1
n
n
n
(1 + h2 + (h2 )2 + . . . + (h2 )2
(m−n) −1
(2.5)
2n −1
)<
αh < ε, 1 − h2n
h ∈ (0, 1). Vegyük észre, hogy ez éppen a konvergenciát jelenti, vagyis létezik
hogy
lim xk = x∗ ∈ Sr (x0 ),
k→∞
,ahol a tartalmazás (1.)-b®l következik. Még azt kell megmutatni, hogy minden
k ≥ 0-ra,
x∗
az
f
zérushelye
Sr (x0 )-ban.
Mivel
xk ∈ Sr (x0 )
valamint teljesül (a), ezért
kDf (xk ) − Df (x0 )k 6 γkxk − x0 k < γr teljesül. De niáljuk
K -t
a következ®képpen:
kDf (xk )k 6 γr + kDf (x0 )k =: K. Átrendezve a (2.3) egyenletet azt kapjuk, hogy
f (xk ) = −Df (xk )(xk+1 − xk ). Ebb®l és (2.6)-ból mindkét oldal normáját véve
kf (xk )k 6 Kkxk+1 − xk k → 0 (k → ∞) adódik, tehát:
lim kf (xk )k = 0.
k→∞ Végezetül mivel
f
folytonos
x∗ -ban,
ezért
lim kf (xk )k = kf (x∗ )k = 0,
k→∞
17
(2.6)
vagyis
x∗
az
f
zérushelye.
(3.): Ha (2.5)-ben
m → ∞,
akkor az állítás azonnal látható: n
αh2 −1 lim kxm − xn k = kx∗ − xn k 6 . m→∞ 1 − h2n
A feltételeket némileg er®sítve igazolható, hogy a
Sr (x0 )-ban.
x∗
az egyetlen zérushelye
f -nek
Err®l szól az alábbi tétel:
2.1.7. Tétel. (Newton-Kantorovich) Legyen C ⊆ Rn nyílt halmaz, C0 ⊆ C egy konvex halmaz, valamint f : C → Rn függvény, amely folytonosan dierenciálható C0 -on és teljesüljenek az alábbi feltételek: a) kDf (x) − Df (y)k 6 γkx − yk (∀x, y ∈ C0 ), b) kDf (x0 )−1 f (x0 )k 6 α, c) kDf (x)−1 k 6 β ∀x ∈ C0 . Legyenek továbbá: h := αβγ, r1,2 := α
Ha h 6
1∓
√
1 − 2h . h
1 és Sr1 (x0 ) ⊂ C0 , akkor az 2 xk+1 := xk − Df (xk )−1 f (xk ),
k = 0, 1, . . .
módon de niált sorozat Sr1 (x0 )-ban marad és az f egyetlen megoldásához konvergál C0 ∩ Sr2 (x0 )-on.
18
2.1.8. Megjegyzés.
Többdimenziós esetben a Newton-módszer alkalmazása során
fontos a konvergencia globalizálása, például csillapítással, vagy a folytatás módszerével. Ugyanis a dimenzió növekedésével együtt csökkennek a gyököket körülvev® vonzási gömbök átmér®i. Ekkor a konvergencia sebessége csökken, viszont nem lesz szükségünk arra, hogy elég jó kezd®vektort adjunk meg.
2.2.
A csillapított Newton-módszer algoritmusa
A (2.1.6) tétel biztosítja számunkra, hogy amennyiben elég közeli juk az iterációt, úgy a Newton-módszer konvergálni fog az
x∗
x0
pontból indít-
megoldáshoz. Annak
érdekében, hogy ne legyen szükség ilyen feltételre a kezd®vektor kiválasztásakor, globalizálhatjuk a módszert. Erre egy lehet®ség a csillapított Newton-módszer alkalmazása, melyet már egydimenziós esetben láttunk az 1. fejezetben. Most következzen az általános algoritmus. Legyenek adottak az alábbiak: a)
x0 :
b)
δx: maximális lépéstávolság (pl. annak a gömbnek a sugara, amelyben szerintünk
kezdeti vektor,
a gyök van), c)
maxit:
d)
ε:
e) az
az iterációk maximális száma,
pontosság,
f (x)-et
és a
Df (x)-et
kiszámító eljárások,
f ) a f®elemválasztásos LU-felbontás meghatározására szolgáló program (Ennek a programnak az outputjai:
L, U , sing ,
ahol az utóbbi egy logikai változó, mely
akkor igaz, ha a mátrix szinguláris).
19
1. t := 1; 2. fk := f (x0 ), nfk := kfk k∞ , nf0 := nfk
;
while k < maxit do 4. if nfk 6 ε then 3.
STOP (sikeres kiszállás), output:
xk , nfk , k ;
else Dfk := Df (xk ), Dfk → [L, U, sing]
5.
if sing=igaz then STOP (sikertelen kiszállás), output:
sing , xk , nfk ;
else t := min(δx ∗ kDfk k∞ /nfk , t)
if t < 10−6 then
6.
STOP (sikertelen kiszállás), output:
xk , nfk , k ;
else
LU y := fk → y , l := 1, p := 0
while l < 10 do
7.
z := xk − t ∗ y , fz := f (z), nfz := kfz k∞
if nfz < nfk then
8.
k := k + 1, xk+1 := z , fk := fz , nfk := nfz
if l = 1 then
9.
t := min(1, t ∗ 1.5)
end l := 10
else
t := t/2, l := l + 1, p := p + 1;
end end if p = 9 then
10.
STOP (sikertelen kiszállás), output:
xk , nfk , k , l;
end end end end end STOP (k
= maxit,
sikertelen kiszállás), output:
20
xk , nfk , k .
Az algoritmusból való kilépést sikeresnek tekintjük, ha a Ekkor ugyanis az
xk
4.
lépés feltétele teljesül.
helyen a függvény normája elegend®en kicsi lesz, ami azt jelenti
a felhasználó számára, hogy megoldotta a nemlineáris egyenletrendszert. Sikertelenségnek vesszük, ha:
•
a Jacobi-mátrix LU-felbontását végz® program szingularitást tapasztal;
•
a
t értéke túlságosan kicsi lesz, ugyanis ekkor nagy mértékben lassul a konver-
gencia;
•
az l -ciklusban a
t csökkentése nem hoz eredményt (nem teljesül az ún. leeresz-
kedési kritérium);
Az
•
a
5.
lépésben érjük el azt, hogy a
k -ciklusban
túl nagy az iterációk száma.
t 6 δx ∗
kDfk k∞ nfk
teljesüljön. Ellenkez® esetben
ugyanis a Newton-lépés gyanusan nagy lenne, ellentmondva ezzel Az l -ciklusban csökkentjük a
δx
választásának.
t értékét, ha a már említett leereszkedési kritérium nem
teljesül. Ezen a ponton azt használjuk ki, hogy a keresett gyök egyben az
kf (x)k
minimuma is, hiszen:
⇐⇒
f (x) = 0 Tehát, minden
x
kf (x)k = 0.
vektor, amely lokális minimumhelye
globális minimumhelye is
kf (x)k-nak,
kf (x)k-nak
valamint zérushelye
és
f (x) = 0,
az
f (x)-nek.
Amennyiben a kritérium teljesül, a lépést sikeresnek tekintjük és közelebb jutunk a gyökhöz. Ha ez próbálkozás nélkül (l el nem éri az
1
= 1) sikerül, akkor óvatosan növeljük t-t, amíg
értéket.
21
2.3.
A Broyden-módszer
Nemlineáris rendszerek megoldása során gyakran el®fordul, hogy problémás a parciális deriváltak meghatározása. Ebben az esetben alkalmazhatjuk a Broyden-módszert, amely a szel®módszer általánosítása. El®nye, hogy csak az
f (xk ) vektorokat használja
a Jacobi-mátrix közelítéséhez, ezek pedig egyébként is a rendelkezésünkre állnak. Az iteráció els® lépésében megadjuk a
Df (x)
mátrixnak egy
hetjük például (2.2) szerint, és így megkapjuk
x1 -et.
J0
közelítését. Ezt megte-
Általános lépésben az alábbi
képletet használja a Broyden-módszer:
xk+1 = xk − Jk−1 fk , Jk := J(xk )
,ahol
és
fk := f (xk ).
k = 1, 2, . . . ,
Ez az egydimenziós esetben a szel®módszert
eredményezi, ahol a deriváltat közelíthetjük osztott dierenciával a következ®képpen:
(Jk =)fk0 :=
fk − fk−1 . xk − xk−1
Ehhez hasonlót írunk fel magasabb dimenzióban is:
Jk :=
fk − fk−1 . xk − xk−1
Ebb®l adódik az úgynevezett kvázi-Newton-egyenlet, amely
Jk
n
darab feltételt ad a
meghatározásához:
Jk (xk − xk−1 ) = fk − fk−1 =: zk . Azonban nekünk és
Jk−1
n2
feltételre lenne szükségünk, ezért még követeljük meg, hogy
Jk
csupán egy egyrangú mátrixszal különbözzenek egymástól. Ez formálisan így
fogalmazható meg:
(Jk − Jk−1 )y = 0, Alkalmas
uk -val
∀y ⊥ vk ,
vk := xk − xk−1 .
ez a feltétel teljesül az alábbi egyenletben:
Jk − Jk−1 = uk vkT . Az
uk
(2.7)
vektor meghatározásához szorozzuk mindkét oldalt
vk -val, majd rendezzük át
az egyelnetet:
(Jk − Jk−1 )vk = uk kvk k2 A kapott
xk+1
uk -t
=⇒
uk =
(Jk − Jk−1 )vk zk − Jk−1 vk = . 2 kvk k kvk k2
(2.7)-be helyettesítve megkapjuk
Jk -t,
és így már mindent ismerünk
kiszámításához, amely a keresett megoldás egy újabb közelítése.
22
2.3.1. Megjegyzés.
A gyakorlatban a módszer minden lépésében elkészítjük az
éppen aktuális Jacobi-mátrix QR-felbontását, vagy felírjuk az LU-felbontást és invertálunk. Az el®bbi akkor el®nyös, ha a alkalmazzuk különösen akkor, ha
2.3.2. Megjegyzés.
J
J
rosszul kondícionált, különben az utóbbit
nagyméret¶ ritkamátrix.
A Broyden-módszer konvergenciarendje
1+
1 . A lokális kon2n
vergenciát próbálkozhatunk csillapítással globalizálni, de nincs garancia arra, hogy elég kicsi
t-re
teljesülni fog a leereszkedési kritérium. Ha
sem hoz eredményt, akkor érdemes új közelítést adni
2.4.
t
többszörös csökkentése
Df -re.
A folytatás módszere
A (2.1.8)-as megjegyzésben láttuk, hogy a dimenziószám növekedésével egyre fontosabb a Newton-módszer konvergenciájának globalizálása. Ezt ebben a részben a folytatás módszerével fogjuk elérni, amely a csillapítás általánosítása. Az eljárás lényege, hogy az eredeti
f (x) = 0 rendszerünkhöz hozzáveszünk egy t paramétert úgy,
hogy az alábbi két feltétel teljesüljön: a) ha
t = 0,
akkor a megoldás ismert legyen;
b) ha
t = 1,
akkor az eredeti feladat megoldásához jussunk.
Ezt a következ® függvénnyel valósítjuk meg:
g(x, t) := f (x) + (t − 1)f (x0 ) = 0, Így egy
n+1
x0
adott.
dimenziós feladatot kapunk. Vegyük észre, hogy
f (x0 ) = 0, tehát t = t0 = 0 esetén a g
g(x0 , 0) = f (x0 ) −
x0 . Ezért a módszer els® lépésében 1 , ahol k elegend®en nagy. válasszuk x0 -t kezd®vektornak, továbbá legyen t = t1 = k (Amennyiben nem konvergál a Newton-módszer, úgy növekjük k -t.) Innen megkap2 juk az x1 vektort, melynek segítségével és t = t2 = -val ki tudjuk számítani x2 -t, k és így tovább. Az utolsó lépésben pedig g(xk−1 , 1) = f (xk−1 ) = 0-t kapunk, ahol az xk−1
az
x∗ -nak
zérushelye
közelítése.
Igazolható, hogy bizonyos feltételek teljesülése esetén a gyöke, minden elegend®en kicsi
g(x, t) függvénynek van x(t)
|t| értékre, továbbá x(t) minden t-re dierenciálható
és eleget tesz a következ® dierenciálegyenletnek:
f 0 (x)
dx = −f (x0 ). dt 23
Tehát adott
x(0) = x0 esetén x(t) egyértelm¶en meghatározott. Ezzel visszavezettük
a feladatot egy közönséges dierenciálegyenlet kezdetiérték feladatára. Így is megoldhatjuk az egyenletrendszerünket, de most térjünk vissza a fenti algoritmusra, és fogalmazzuk meg a következ®képpen: Legyen
k≥1
és
x0 ∈ Rn
m = 0, . . . , k − 1-re
adott,
az
g(x, tm+1 ) − g(xm , tm ) = 0,
tm+1 := tm + ∆t,
egyenletrendszer megoldásához ményét
xm+1 -gyel
l
1 , k
∆t :=
iterációt végzünk Newton-módszerrel, ennek ered-
jelöljük, majd továbblépünk.
2.4.1. Tétel. (A folytatásos módszer elégséges konvergencia tétele) Legyen x∗ az f (x) = 0 rendszer gyöke és teljesüljön az egész Rn -en, hogy kf 0 (x)k 6 M1 ,
kf 0 (x) − f 0 (y)k 6 Lkx − yk,
kf 0 (x)−1 k 6 α.
Ha a folytatásos módszer k lépésszámára igaz k ≥ Lα2 kf0 k,
f0 := f (x0 ),
akkor minden ε > 0-hoz létezik olyan l = l(ε, L, α, M1 , kf0 k), a közbüls® Newtonlépések száma, hogy érvényes a következ®: kxk − x∗ k 6 ε.
2.4.2. Megjegyzés.
A folytatás módszerével tehát úgy érhetjük el a globális kon-
vergenciát, hogy egy esetlegesen rosszul megválasztott
x0 -ból
egy olyan
xk−1 -et
ál-
lítunk el®, amely benne lesz a lokális konvergencia vonzási gömbjében, tehát jó lesz a Newton-módszer kezd®vektorának.
2.4.3. Megjegyzés.
Nem minden esetben célszer¶ használni a folytatásos mód-
szert. El®fordulhat például, hogy túl sok id® megy el a közbüls® egyenletrendszerek megoldására, vagy az
f0
Jacobi-mátrixa szinguáris. Ezek az esetek jelen®sen megne-
hezíthetik a dolgunkat, viszont vannak olyan feladatok, amelyeket máshogyan nem tudunk megoldani.
24
2.5.
Alkalmazások
A feladatok megoldásához használt programok a CD-mellékleten találhatók. 1. feladat Hány megoldása van a következ® egyenletrendszernek a
[−10, 10]×[−10, 10] négy-
zet belsejében és melyek ezek?
x21 − 10x1 + x22 + 8 = 0
(2.8)
x1 x22 + x1 − 10x2 + 8 = 0
(2.9)
Megoldás: Ábrázoljuk MATLAB segítségével az egyenleteket külön-külön implicit függvényként a megadott tartományon, és rajzoljuk ki ®ket egy koordinátarendszerbe a pelda1.m segítségével:
2.1. ábra. Pirossal a (2.8), kékkel a (2.9) ábrázolása
A gra konról leolvashatjuk, hogy a
[−10, 10] × [−10, 10]
tartományon kett® da-
rab gyöke van az egyenletrendszernek. Ezek megkeresésére indítsuk el különböz® kezd®pontokból 'A Newton-módszer' mappában található Newton.m-et:
25
2.2. ábra. A Newton.m eredménye a
[0.5, 0.5]
és a
A program tehát megtalálja a két gyököt, ezek az
[3, 3]
[1, 1]
kezd®pontokból
és a
[2.1934, 3.0205].
Nézzünk most egy példát arra az esetre, amikor m¶ködésbe lép a csillapított módszer t-stratégiája: 2. feladat Oldjuk meg az alábbi rendszert a
[0, 1.4, 1]
kezd®pontból!
−x21 + x3 + 3 = 0 −x1 + 2x22 − x23 − 3 = 0 x2 − 3x23 + 2 = 0 Megoldás: A 'Csillapított Newton-módszer' mappából a Csillapitas.m fájl segítségével oldjuk meg az egyenletrendszert:
26
2.3. ábra. A Csillapitas.m eredménye a
Az eredményben szerepl® az egyes lépésekben a
t
p
[0, 1.4, 1]
kezd®pontból
jelenti azt a számot, hogy hányszor volt szükség
csillapítási paraméter csökkentésére (a leereszkedési-
kritérium nem teljesülése miatt). Azt látjuk, hogy az els® lépésben hétszer kellett csökkenteni, így ekkor marad a
p
t = 0.0078
lett. Viszont a második lépést®l mindig nulla
(els®re teljesül a kritérium), tehát óvatosan növelhetjük
lépést®l újra megtalálja a
t = 1
t-t.
A
13.
lesz, innent®l kezdve négyzetes a konvergencia. A program
[−2, 1, 1]
gyököt, és a maradékvektor normája igazolja, hogy ez va-
lóban gyök lesz. 3. feladat Keressük meg a következ® egyenletrendszer gyökeit a
[−3, 3] × [−3, 3]
négyzeten
és ábrázoljuk a konvergenciatarományt!
arctan(x1 − x22 ) = 0
(2.10)
arctan(x21 − x2 ) = 0
(2.11)
Megoldás: Ismét ábrázoljuk MATLAB-ban implicit függvényként a két egyenletet (pelda2.m)! Ekkor az alábbi ábra adódik:
27
2.4. ábra. Pirossal a (2.10), kékkel a (2.11) ábrázolása
Jól látszik, hogy a
[0, 0]
és az
[1, 1]
lesznek a gyökök. Az els® feladat mintájára
indítsuk el különböz® kezd®pontokból a Newton.m-et! Azt fogjuk tapasztalni, hogy a gyököknek csak egy kis környezetéb®l konvergál a Newton-módszer:
2.5. ábra. A Newton.m eredménye a
[0.1, 0.1]
28
és a
[−1, −1]
kezd®pontokból
2.6. ábra. A Newton.m eredménye a
A program megtalálja a
[1, 1]
gyököt. Viszont a
[0.1, 0.1] [2, 1]
és a
[2, 1]
pontból a
[10, 10]
és a
[10, 10]
[0, 0],
a
kezd®pontokból
[−1, −1]
pontból pedig az
pontokból a Jacobi-mátrix szingula-
ritására hivatkozva kilép, tehát nem konvergál. Most a 'Konvergenciataromány ábrázolása' mappában található kirajzol.m segítségével a következ® ábrát kapjuk:
2.7. ábra. Az
[arctan(x1 − x22 ) = 0; arctan(x21 − x2 ) = 0]
egyenletrendszer konver-
genciatartománya
A ga konon piros szín jelöli azokat a pontokat, amelyekb®l indítva konvergált, kék szín pedig azokat, amelyekb®l divergált a Newton-módszer. 4. feladat Tekintsük a 3. feladat egyenletrendszerét és indítsuk el a folytatásos módszer programját egy konvergenciatartományon kívül es® kezd®pontból!
29
Megoldás: A folytatás módszere globalizálja a konvergenciát, erre látunk most egy példát. Nyissuk meg 'A folytatás módszere' mappából a Folytatas.m-et, és adjuk meg a
[10, 10]
kezd®vektort:
2.8. ábra. A Folytatas.m eredménye a
[10, 10]
kezd®pontból
Tehát a folytatás módszere egy olyan kezd®vektorból is megtalálta az
[1, 1]
gyö-
köt, amelyb®l a Newton-módszer nem konverált. 5. feladat Ábrázoljuk, hogy hogyan konvergál a folytatás módszere a kezd®pontból a gyökhöz az
arctan(x − 2) = 0
egyenlet esetén!
Megoldás: El®ször rajzoljuk ki a függvényt (pelda3.m), majd azt az intervallumot, amelyb®l indítva a Newton-módszer konvergál ('Konvergenciatartomány ábrázolása' arctg.m):
2.9. ábra. Az
f (x) = arctan(x − 2) 30
függvény
→
2.10. ábra. Az
f (x) = arctan(x − 2)
Az els® ábráról leolvashatjuk, hogy az
függvény konvergenciaintervalluma
x=2
lesz a függvény zérushelye. A máso-
dik ábrán nulla a függvényérték azokon a helyeken, amelyekb®l nem konvergált, egy pedig azokon, amelyekb®l konvergált a Newton-módszer. Indítsuk el a folytatásos módszert például az
x = 10
pontból:
2.11. ábra. A Folytatas.m eredménye az
x = 10
pontból
A folytatás módszere ismét megtalálta a gyököt egy olyan pontból, amely kívül esik a konvergenciaintervallumon. Most 'A folytatás módszere' mappából indítsuk el a folyt− gyokok.m-et! Ekkor megkapjuk, hogy hogyan jutott el a módszer a
10
pontból a
2-be:
31
2.12. ábra. A zérushelyek változása
Ez az ábra a folytatás módszerénél de niált meg a
1 k t = 0, , . . . , k k
helyeken.
32
g(x, t) függvény zérushelyeit mutatja
3. fejezet
Útmutatás a programok használatához
A CD-mellékleten öt mappát, három M-fájlt és egy text dokumentumot talál az Olvasó. Az M-fájlok a fenti feladatok implicit függvényeit, valamint az
arctan(x − 2)
f (x) =
függvényt rajzolják ki. A text dokumentumban találhatók az egyes
módszerek utasításai a példafeladatokra. A mappákban a módszerek M-fájljai vannak az összes 'segédprogrammal' együtt. Például a Newton-módszer mappájában benne van a Jacobi-mátrixot kiszámító fájl is, mivel ezt használja az iteráció. A programok lefutása érdekében nagyon fontos, hogy mindig az a mappa legyen megnyitva a MATLAB-ban, amelyik eljárást éppen használni szeretnénk. Ekkor már csak az utasítást kell megadnunk a text dokumentum mintájára. Az input paraméterek száma és jelentése módszerenként eltérhet, ezekhez a programok kódjában leírás található. A folytatás módszerének és a konvergenciatartomány ábrázolásának mappájában további szkriptek találhatók, ezek is a fenti feladatokhoz tartoznak. Megemlítem még, hogy a Converge.m egy
0 − 1 mát-
rixot eredményez, amely a pontok nem konvergál-konvergál tulajdonságát jelentik. Ezt a mátrixot a
pcolor
paranccsal rajzoltathatjuk ki a kirajzol.m segítségével.
33
Irodalomjegyzék
[1] Gergó Lajos,
Numerikus módszerek, ELTE Eötvös Kiadó, 2010, 157-178
[2] J. Stoer, R. Bulirsch,
Introduction to Numerical Analysis, Springer-Verlag New
York Inc., 1980, 244-270 [3] Stoyan Gisbert, Takó Galina,
Numerikus módszerek I., ELTE-Typotex Kiadó,
1993, 322-363 [4] Stoyan Gisbert,
Numerikus matematika, Typotex kiadó, 2007, 133-158
34
