Numerikus módszerek 2. Nemlineáris egyenletek közelítő megoldása
Egyenletmegoldás intervallumfelezéssel A Banach-fixpont-iterációs módszer A Newton-módszer és változatai Általánosított Newton-módszer
1
Egyenletmegoldás intervallumfelezéssel Legyen f : [a, b] R folytonos, f (a) 0,
f (b) 0 , és keressük az
f ( x) 0 egyenlet egy [a, b] -beli megoldását. Bolzano tétele: Legyen f folytonos a véges, zárt [a,b] intervallumon. Tegyük fel, hogy f (a) és f (b) különböző előjelűek, pl. f (a) 0, f (b) 0 . Akkor f-nek van (legalább egy) zérushelye ebben az intervallumban. Felezzük szisztematikusan az [a, b] intervallumot úgy, hogy a két fél-intervallumból mindig azt tekintjük, melyre a végpontokon felvett függvényértékek különböző előjelűek. Jelölje xn az nedik lépésben nyert részintervallum középpontját. Akkor az így definiált sorozat a fenti egyenlet (egyik) gyökéhez konvergál. A konvergencia sebessége legalább egy 1/2 kvóciensű mértani sorozat konvergenciájának sebessége.
2
Egyenletmegoldás intervallumfelezéssel Az intervallumfelezés algoritmusa szemléletesen:
Hibabecslés. Legyen x0 :
ab , akkor nyilván 2 xn x *
ba 2n 3
Numerikus módszerek 2. Nemlineáris egyenletek közelítő megoldása
Egyenletmegoldás intervallumfelezéssel A Banach-fixpont-iterációs módszer A Newton-módszer és változatai Általánosított Newton-módszer
4
A Banach-fixpont-iterációs módszer Legyen X Banach-tér, f : X X egy leképezés, és keressük az
x f (x) egyenlet egy megoldását (ezt az f függvény egy fixpontjának nevezzük). Banach-féle fixponttétel: Legyen X Banach-tér, f : X X kontrakció X-en, azaz alkalmas 0 q 1 számra || f ( x) f ( y) || q || x y || teljesül minden x, y X mellett. Akkor f-nek egyetlenegy x X fixpontja van, és ez előáll az alábbi iterációs sorozat limeszeként:
x0 X tetsz.,
xn 1 : f ( xn ) (n 0,1,2,...)
A valós függvények speciális esete. Ha f : R R olyan, hogy max | f ' ( x) | 1, akkor f kontrakció, mert a Lagrange-középértéktétel miatt | f ( x) f ( y) | | f ' () | | x y | (max | f '|) | x y |
5
Bizonyítás: Két egymást követő tag eltérése:
|| xn 1 xn || || f ( xn ) f ( xn 1 ) || q || xn xn 1 || q || f ( xn 1 ) f ( xn 2 ) || q 2 || xn 1 xn 2 || ... q n || x1 x0 || Ezt felhasználva megmutatjuk, hogy az ( xn ) sorozat Cauchy-sorozat X-ben:
|| xn k xn || || xn k xn k 1 xn k 1 xn k 2 ... xn 1 xn || || xn k xn k 1 || || xn k 1 xn k 2 || ... || xn 1 xn || (q n k 1 q n k 2 ... q n ) || x1 x0 || (q q n
n 1
q
n2
qn ...) || x1 x0 || || x1 x0 || 0 1 q
Ezért a sorozat konvergens, xn x X . Megmutatjuk, hogy a limesz fixpontja f-nek. A rekurzív definíció szerint: xn 1 f ( xn ) A bal oldal nyilván x-hez tart. A jobb oldal f folytonossága miatt f (x)-hez. Innen x = f (x). Végül igazoljuk, hogy csak egy fixpont van. Ha x, y két különböző fixpont volna, akkor
0 || x y || || f ( x) f ( y) || q || x y || || x y || volna, ami lehetetlen. 6
A Banach-fixpont-iterációs módszer, példák:
1 1. Oldjuk meg az x cos x egyenletet. 2
1 1 1 Az f ( x) : cos x függvény kontrakció, mert | f ' ( x) | | sin x | . Ezért egyetlenegy 2 2 2 1 fixpont létezik, és pl. az x0 : 0 , xn 1 : cos xn sorozat ide konvergál. A sorozat első 2 néhány eleme (4 tizedesjegy pontossággal): 0.0000, 0.5000, 0.4387, 0.4526, 0.4496, 0.4502, 0.4501, 0.4501, 0.4501, ... 2. Legyenek B M N N , g R N adottak, és oldjuk meg az x Bx g egyenletet. Ha || B || 1, akkor az f ( x) : Bx g leképezés kontrakció, mert || f ( x) f ( y) || || Bx g By g || || B || || x y ||
Ezért ekkor egyetlenegy fixpont létezik, és pl. az x0 : 0 , xn 1 : Bxn g vektorsorozat ide konvergál. 7
Numerikus módszerek 2. Nemlineáris egyenletek közelítő megoldása
Egyenletmegoldás intervallumfelezéssel A Banach-fixpont-iterációs módszer A Newton-módszer és változatai Általánosított Newton-módszer
8
A Newton-módszer egyváltozós függvényekre Legyen f : (a, b) R adott függvény. Keressük az
f x 0 egyenlet egy (a, b) -beli megoldását. A Newton-módszer: Ha xn a megoldás egy közelítése, akkor legyen a következő közelítés az xn -beli érintő egyenes zérushelye. Az érintő egyenlete: y f ( xn ) f ' ( xn ) ( x xn ) , innen:
xn 1 xn
f xn (n 0,1,2,...) f xn
( x0 (a, b) : kezdeti közelítés)
9
A Newton-módszer egyváltozós függvényekre A módszer szemléletes jelentése ( x * : pontos megoldás):
Ha f kétszer folytonosan differenciálható, f-nek van gyöke (a,b)-n, és erre f ( x* ) 0 teljesül, akkor a Newton-módszer kvadratikusan konvergál minden, az x * pontos megoldáshoz elég közeli x0 kezdeti közelítés esetén, azaz alkalmas C 0 szám mellett:
| xn 1 x* | C | xn x* |2 10
Bizonyítás: A Lagrange-középértéktételt használjuk (kétszer is):
f ( xn ) f ( x * ) f (t )( xn x* ) * xn 1 x xn x xn x f ( xn ) f ( xn ) f ( xn ) f (t ) f ( s ) ( xn x * ) ( xn t ) ( xn x * ) f ( xn ) f ( xn ) *
*
Mivel f ( x* ) 0 , azért a deriváltfüggvény x* egy egész (zárt) környezetében is zérustól különböző marad. Itt pedig:
| xn 1 x* |
max | f | max | f | | xn t | | xn x * | | xn x * | 2 C | xn x * | 2 min | f | min | f |
11
A Newton-módszer, példa: Legyen A rögzített pozitív szám, és f ( x) : x 2 A . ( Ekkor az f ( x) 0 egyenlet egyetlen (pozitív) megoldása: x
f ' ( x) 2 x )
A.
Kiindulva egy tetszőleges x0 0 kezdeti közelítésből (pl. x0 : A ), a Newton módszer:
xn2 A 1 A xn1 : xn x n 2 xn 2 xn A sorozat nagyon gyorsan
A -hoz tart.
12
A Newton-módszer, példa: Legyen A rögzített pozitív szám, és f ( x) : x 2 A . ( Ekkor az f ( x) 0 egyenlet egyetlen (pozitív) megoldása: x
f ' ( x) 2 x )
A.
Kiindulva egy tetszőleges x0 0 kezdeti közelítésből (pl. x0 : A ), a Newton módszer:
xn2 A 1 A xn1 : xn x n 2 xn 2 xn A sorozat nagyon gyorsan
A -hoz tart.
Megjegyzés: hasonlóan lehet bármely (egész kitevős) gyökvonás közelítésére a Newtonmódszert használni.
13
A Newton-módszer változatai Probléma: a derivált számítása. A szelőmódszer: itt f ' ( xn )
f ( xn ) f ( xn 1 ) . Legyenek tehát x0 , x1 kezdő közelítések, és xn xn 1 xn 1 : xn
( xn xn 1 ) f ( xn ) f ( xn ) f ( xn 1 )
Ha f kétszer folytonosan differenciálható, f-nek van gyöke (a,b)-n, és erre f ( x* ) 0 teljesül, akkor a szelőmódszer minden, az x * pontos megoldáshoz elég közeli x0 , x1 kezdeti közelítések esetén legalább egy mértani sorozat sebességével konvergál, azaz alkalmas C 0, 0 q 1 mellett: | xn x * | C q n
14
A Newton-módszer változatai
A Steffensen-módszer: Legyen az f : R R kétszer folytonosan differenciálható függvénynek pontosan egy x * zérushelye. Tegyük fel, hogy f ( x* ) 0 . Akkor minden, x * -hoz elég közel levő valós kezdeti x 0 közelítésből kiindulva, az
f ( xn ) 2 xn 1 : xn f ( xn f ( xn )) f ( xn )
(n 0,1,2,...)
sorozat kvadratikusan konvergál x * -hoz.
15
Bizonyítás: A Lagrange-középértéktételt használjuk:
f ( xn f ( xn )) f ( xn ) f ' (t ) ( xn f ( xn ) xn ) f ' (t ) f ( xn ) ezért
f ( xn ) f ( xn ) f ( x * ) f ' (s) * xn 1 x xn x xn x xn x * ( xn x * ) f (t ) f (t ) f ' (t ) f (t ) f ( s ) f ( w) ( xn x * ) (t s ) ( xn x* ) f (t ) f (t ) *
*
Mivel f ( x* ) 0 , azért a deriváltfüggvény x* egy egész (zárt) környezetében is zérustól különböző marad. Itt pedig:
| xn 1 x* |
max | f | max | f | | t s | | xn x * | | xn x * | 2 C | xn x * | 2 min | f | min | f |
16
Numerikus módszerek 2. Nemlineáris egyenletek közelítő megoldása
Egyenletmegoldás intervallumfelezéssel A Banach-fixpont-iterációs módszer A Newton-módszer és változatai Általánosított Newton-módszer
17
Differenciálás Banach-terek közt értelmezett leképezésekre Legyenek X,Y Banach-terek. Az F : X Y leképezés az x X pontban differenciálható, deriváltja pedig az A : X Y folytonos lineáris leképezés, ha a 0 egy alkalmas környezetéből választott h vektorokra teljesül, hogy
F ( x h) F ( x) Ah o(h) ahol o(h) olyan kifejezés, hogy
o( h) 0 (h 0) . || h ||
A derivált lineáris leképezést még így is jelöljük: F (x) vagy DF (x) . Példa: F : R N R , F ( x) : Ax, x (ahol A M N N önadjungált mátrix). Akkor:
F ( x h) A( x h), x h Ax, x 2 Ax, h Ah, h F ( x) 2 Ax, h O(h 2 ) ezért F ' ( x) 2 Ax R N .
18
Általánosított Newton-módszer A Newton-módszer az F ( x) 0 egyenletre: xn 1 xn ( DF ( xn ))1 F xn (n 0,1,2,...)
Másképpen felírva:
xn 1 xn wn
(n 0,1,2,...)
ahol a wn javító tag az alábbi lineáris egyenlet megoldása:
DF ( xn ) wn F xn Ha F kétszer folytonosan differenciálható, F-nek van gyöke X-ben, és DF ( x* ) reguláris (azaz invertálható, és az inverze is folytonos), akkor a Newton-módszer kvadratikusan konvergál minden, az x * pontos megoldáshoz elég közeli x0 kezdeti közelítés esetén, tehát alkalmas C 0 mellett: || xn 1 x* || C || xn x* || 2
19
Általánosított Newton-módszer, példa Mátrixinverzió. Legyen A M N N egy reguláris mátrix. Tetszőleges X M N N reguláris mátrixra jelölje: F ( X ) : X 1 A Akkor F : M N N M N N , és az F ( X ) 0 egyenlet egyetlen megoldása: X A1 . Alkalmazzuk a mátrixegyenletre a Newton-módszert. Az F leképezés deriváltját számítva:
F ( X H ) ( X H )1 A ( X ( I X 1H ))1 A ( I X 1H )1 X 1 A Ha most H elég kis normájú (tetszőleges mátrixnormában), akkor || X 1H || || X 1 || || H || 1. Felhasználva a || B || 1 esetén fennálló ( I B) 1 I B B 2 B 3 B 4 ... egyenlőséget, (melyből ( I B)1 I B (|| B ||2 ) következik): F ( X H ) ( I X 1H ) 1 X 1 A ( I X 1H o( H )) X 1 A X 1 X 1HX 1 o( H ) A F ( X ) X 1HX 1 o( H )
ahonnan
DF ( X ) H X 1HX 1
DF ( X ) 1W XWX 20
Általánosított Newton-módszer, példa Így a Newton-módszer algoritmusa:
X n 1 : X n ( DF ( xn )) 1 ( X n1 A) X n X n ( X n1 A) X n X n (2 I AX n )
.
A közelítés hibájára: || A1 X n || || A1 ( I AX n ) || || A1 || || I AX n || . Ugyanakkor || I AX n || nagyon gyorsan tart 0-hoz (ha a kezdeti közelítés elég jó volt), mert: I AX n 1 I AX n (2 I AX n ) I 2 AX n AX n AX n ( I AX n ) 2 ,
ahonnan || I AX n 1 || || I AX n ||2
21
