Ugrás a tartalomhoz

Numerikus módszerek 1.

Stoyan Gisbert (1942–), Takó Galina (195?–) (2005)

Typotex

6.4. A Newton-módszer és változatai

6.4. A Newton-módszer és változatai

6.4.1. Leírás, konvergencia

A konvergencia tulajdonságok minőségileg változnak, ha a (6.4) megoldására (6.5)-ben a függvényt választjuk, azaz a Newton-módszer esetén.

Ezt a módszert akkor kapjuk, ha a (6.4) egyenlet gyökének közelítéséből kiindulva olyan javítást szeretnénk meghatározni, hogy már gyök legyen. Ilyenkor kétszeres folytonos differenciálhatóságát feltételezve, a Taylor-sorfejtés a

egyenlőséget adja. A másodrendű tag elhanyagolása után, jelöléssel, a

egyenletet kapjuk. Értelemszerűen folytatva a következő alapvető iterációs eljárás keletkezik:

(6.8)

17. ábra - A Newton-módszer mértani jelentése

A Newton-módszer mértani jelentése

Ez a Newton-módszer. Konvergenciáját biztosítja az alábbi eredmény.

6.1. Tétel (Newton-módszer konvergenciája).

Legyen , olyan függvény, hogy Lipschitz-folytonos -ben, Lipschitz-állandóval; létezzék egy olyan , amelyre , .

Ha a (6.4) egyenletnek -ben van gyöke , akkor létezik olyan , hogy -ből és -ból következik, hogy

a) a (6.8) sorozat jól definiált;

b) ;

c) izolált gyök: -ban -nek nincs más gyöke -on kívül;

d) érvényes a következő becslés:

(6.9)

Bizonyítás.

Legyen először , . A feltételünkből következik, hogy , továbbá

(6.10)

Az utolsó zárójelben álló kifejezést jelöljük -gal, és külön becsüljük általános -re. Ehhez induljunk ki az

azonosságból. A helyettesítéssel következik, hogy

és ebből a Lipschitz-folytonosság miatt azt kapjuk, hogy

Térjünk vissza most a (6.10)-hez! Az előbbi becslést és az egyenlőtlenséget felhasználva látjuk, hogy (6.9) igaz minden olyan -re, amelyre a Newton-lépés kivitelezhető, mint pl.  -ra. Ha most -ra teljesül az a kettő feltétel, hogy egyrészt

és másrészt , akkor -re is kivitelezhető a Newton-lépés, és ekkor

de megelégszünk azzal is, hogy

Így bizonyára közelebb van -hoz mint , tehát , így a következő (és induktíve minden további) Newton-lépés is jól definiált. Hasonlóan, mint -re, -re is teljesül a

becslés, ahonnan következik a konvergencia.

Megjegyzések. 1. A tétel feltételeit úgy lehet módosítani, hogy maga az megoldás bennük nem szerepel, hanem csak az kezdeti érték. Így kapjuk a Kantorovics-tételt (amelyben eredetileg az is feltételként szerepelt, hogy második deriváltja folytonos). Mivel a Kantorovics-féle feltételek elvileg mind ellenőrizhetők, és a tétel a létezését mondja ki, ez konstruktiv létezési tétel, amely a Banach-tétellel függ össze.

Ez utóbbi összefüggést a fenti bizonyításban is felhasználtuk az , , becslés alapján, ld. az 1. feladatot is.

A valóságban a Lipschitz-állandó (vagy az felső becslésének) megszerzése általában nagyobb probléma, mint a gyökmeghatározás, ezért az előbb említett konstruktivitás gyakorlatilag ritkán használható.

2. Az -ra vonatkozó második feltételre azért volt szükségünk, mert -n kívül nincs információnk -ről. Amennyiben -n kívül is érvényesek a feltételezett tulajdonságok, és csak az az intervallum, amiről tudjuk, hogy a gyököt tartalmazza, akkor kimondhatjuk a 6.1. tételt úgy is, hogy esetén a Newton-módszer konvergál.

6.4.2. Konvergenciarend, lokális konvergencia

Tegyük fel, hogy egy iterációs eljárás az sorozatot állítja elő, ez a sorozat konvergál a normában, , .

Definíció.

Azt mondjuk, hogy az sorozat -ból kiindulva, (legalább) -rendben konvergál, ha , és van olyan nemnegatív konstans, hogy érvényes

(6.11)

Megjegyzések. 1. Ha érvényes (6.11), akkor esetén az

jelöléssel azt írhatjuk, hogy , .

2. Az előbbi egyenlőtlenségből kiindulva más módon is lehet konvergenciarendet definiálni, ld. a 6.4.3. pontban a 6.2. tétel utáni megjegyzést.

Eszerint a definíció szerint a felezési módszer és az egyszerű iteráció első rendben, vagyis lineárisan konvergens; a (6.9) becslés mutatja, hogy a Newton-módszer másodrendben, avagy négyzetesen konvergens (míg 3.6.1-ben már köbösen konvergens módszerrel is találkoztunk). Ha egyszer beindult ez a gyors konvergencia, néhány lépés alatt elérjük az elfogadható pontosságú megoldást: amennyiben

nagyságrendű lesz. Ehhez a 6.1. tétel szerint viszont az szükséges, hogy elég közel legyen az megoldáshoz, azaz a Newton-módszer (általában) csak lokálisan konvergens.

Definíció.

Egy iterációs eljárásról akkor mondjuk, hogy az lokálisan konvergál az megoldáshoz, ha van olyan pozitív sugárú gömb, amelyik a következő tulajdonságokkal rendelkezik: tetszőleges esetén az iteráció által előállított sorozat konvergál -hoz; -on kívül viszont van olyan vektor, amelyre ez nem igaz. az vonzási gömbje.

A renddel való konvergencia („szuperlineáris konvergencia”) és a lokális konvergencia jelenségek között szoros összefüggés van. Ha ugyanis egy iterációs eljárás olyan sorozatot állít elő, amelyre érvényes a (6.11) becslés -gyel, akkor a fenti 1. megjegyzésben bevezetett mennyiségekre az becslést kapjuk -re. Ebből csak akkor következik, ha , vagyis ha igaz

Így a szuperlineárisan konvergens eljárás általában csak lokálisan konvergál. Ha viszont , akkor

amiből a konvergencia csak esetén következik, de nem keletkezik korlát -ra. Tehát a lineárisan konvergens módszer esetén remélhetjük, hogy az globálisan konvergál. Lejjebb, a 6.4.3. és 6.4.8. pontokban, mutatunk néhány lehetőséget szuperlineárisan konvergens módszer „globalizálására”.

Befejezésül ehhez a ponthoz megjegyezzük, hogy harmadrendű módszereket csak -edfokú polinomok gyökeinek meghatározására szoktak alkalmazni. Ilyen a Laguerre-módszer:

ahol .

Amennyiben összes gyöke valós, a Laguerre-módszer globálisan konvergens; ebben az esetben az -t közrefogó két gyök egyikéhez tart. Egyébként az eljárás lokálisan konvergens és egyszeres gyökök esetén harmadrendű; ezenkívül komplex gyökök meghatározására is alkalmas.

A Laguerre-módszerre hasonlít a Müller-módszer, amely abból áll, hogy három közelítő érték segítségével másodfokú interpolációt készítünk, és annak azon gyökét választjuk következő közelítésnek, amely a legközelebb van az addig legjobb közelítéshez; ezután továbblépünk.

Sajátérték feladatok megoldására inkább a 3. fejezetben tárgyalt módszereket használjuk, pl. a QR-módszert; ezen feladatok megoldása a karakterisztikus polinomon keresztül nem ajánlatos, ld.  3.2.2. De polinomok gyökei más alkalmazott problémáknál is érdekesek, pl. átviteli függvények pólusainak meghatározása miatt (Laplace-transzformációval kapcsán) vagy integrációs képletek kiszámítása során, ld.  5.8. (valamint 5.13.-ban a 18., 19., 23., 24. feladatot).

6.4.3. A Newton-módszer változatai; gyakorlati szempontok

Már egyszerű polinomiális függvényeken is elég bonyolult lehet a Newton-módszer viselkedése (  ld. a 6. feladatot!). Az ott kiemelt egyik esetben többszörös gyök van jelen, és ez érezhetően lelassítja a konvergenciát. Az ilyen esetet eddig kizártuk a tárgyalásból; legyen tehát most elegendően sokszor differenciálható, és

18. ábra - A Newton-módszer viselkedése: A Newton-módszer viselkedése: , , : gyök; A: a Newton-lépés nem definiált; B: végtelen ciklus; a , a , a : az egyes gyökök vonzási tartománya; b: szabálytalan viselkedés, A Newton-módszer viselkedése: , , : gyök; A: a Newton-lépés nem definiált; B: végtelen ciklus; a , a , a : az egyes gyökök vonzási tartománya; b: szabálytalan viselkedés, A Newton-módszer viselkedése: , , : gyök; A: a Newton-lépés nem definiált; B: végtelen ciklus; a , a , a : az egyes gyökök vonzási tartománya; b: szabálytalan viselkedés: gyök; A: a Newton-lépés nem definiált; B: végtelen ciklus; a A Newton-módszer viselkedése: , , : gyök; A: a Newton-lépés nem definiált; B: végtelen ciklus; a , a , a : az egyes gyökök vonzási tartománya; b: szabálytalan viselkedés, a A Newton-módszer viselkedése: , , : gyök; A: a Newton-lépés nem definiált; B: végtelen ciklus; a , a , a : az egyes gyökök vonzási tartománya; b: szabálytalan viselkedés, a A Newton-módszer viselkedése: , , : gyök; A: a Newton-lépés nem definiált; B: végtelen ciklus; a , a , a : az egyes gyökök vonzási tartománya; b: szabálytalan viselkedés: az egyes gyökök vonzási tartománya; b: szabálytalan viselkedés

A Newton-módszer viselkedése: , , : gyök; A: a Newton-lépés nem definiált; B: végtelen ciklus; a , a , a : az egyes gyökök vonzási tartománya; b: szabálytalan viselkedés

Ekkor, az jelöléssel,

Innen és -ből következik elegendően kicsi -re

azaz

(6.12)

Ezért esetén a Newton-módszer csak első rendben, vagyis lineárisan konvergens. A multiplicitást pl. abból lehet meghatározni, hogy

Amikor ismert, a Newton-eljárás következő módosítása biztosítja megint a négyzetes konvergenciát:

(6.13)

(ld. a 6.8. pontban a mintafeladatot is). (6.13)-ban tehát az eredeti Newton-lépést hosszabbítani kellett ahhoz, hogy javuljon a konvergencia. Általános esetben viszont nem előnyös a lépés növelése, ellenkezőleg, ajánlatos a kicsinyítése:

A (lokális) konvergencia akkor változtatható globálisra, ha (6.13)-ban nem egész, hanem elég kicsi pozitív szám, ld. a 4. feladatot. A feladat feltételei szerint nem vált előjelet, és ha , , , akkor , elegendően kicsi esetén, így ekkor valójában monoton konvergenciáról van szó.

Az elegendően kicsi feltétel kézenfekvővé teszi a (6.13) iteráció

alakjának értelmezését: itt nem a (6.7), hanem az differenciálegyenlet approximációjáról van szó; az fiktív idő lépéstávolsága.

A (6.13) eljárást esetén csillapított Newton-módszernek hívjuk. A 4. feladat ismeretében ajánlható ismeretlen viselkedésű függvény esetén a következő algoritmus:

Adott az kezdeti érték, a maximális lépéstávolság (pl. annak az intervallumnak a hossza, amelyben elvárásunk szerint a gyök van), az iterációk maximális száma és az pontosság; álljanak rendelkezésünkre és .

1. ,

2. ? ? [stop [eredmények: , ]]

3. ? ? [ ? ? [ 5.]]

4. ? ? [ 6.]

5. stop [információ: , , ]

6.

7. ? ? [ 10.]

8. , ? ? [ , 7.]

9. stop [információ: , , , , ]

10.

11. ? ? [ , ? ? [ ], 2.]

12. , ? ? [ , 10.]

13. stop [információ: , , , ]

Az algoritmus 2–5. lépése szolgálja a kilépést a gyökkeresésből, amennyiben elég kicsi lett a függvényérték (2. lépés, a reguláris befejezés), ill. ha túl lassan változnak a függvényértékek vagy az túl kicsi (3. lépés) vagy túl nagy az iterációk száma (4. lépés). Ez utóbbi jelenségek lehetnek egymásnak következményei is.

A 7–8. lépésben azért csökkentjük elég gyorsan a csillapítási) paramétert, mert a Newton-javítás gyanúsan nagy lenne, a 10–12. lépésben azért, mert a 11. lépésbeli teszt („leereszkedési kritérium”) nem teljesül. Tehát itt azt használjuk, hogy a keresett gyök egyben az minimumát is kell, hogy adja. Amennyiben viszont ez a kritérium teljesül, akkor a lépés sikeresnek minősül, és ha ez próbálkozás nélkül megtörtént , akkor óvatosan növeljük a paramétert, míg el nem éri az 1 értéket.

A fenti algoritmus csak akkor értelmes, ha elegendően kicsi csillapítási paraméterre a leereszkedési kritérium teljesül. Ilyen paraméter létezését a 4. feladat megoldása biztosítja. Így a csillapítás segítségével végeredményben a Newton-módszer gyors, de bizonytalan (lokális) konvergenciája lassú, de biztosra (globálisra) változtatható; megfelelő körülmények között viszont a csillapított módszer az eredetibe megy át (azaz lesz 1). Tapasztalati tény az, hogy a legtöbb munkába a Newton-módszerben feltételezett elég jó kiindulási közelítés megszerzése kerül.

A Newton-módszer alkalmazásának másik gondja a derivált kiszámítása, amely fokozottan jelentkezik az egyenletrendszerek esetében (ld.  6.4.6.).

Általában a legegyszerűbb az, ha a deriváltat differenciaképlettel helyettesítsük, tehát az egydimenziós esetben:

Ezután (6.8) helyett az iteráció:

Amennyiben az kétszer folytonosan differenciálható (vagyis , ezzel a konvergencia tétel feltételeit némileg szigorítva), a differencia képlet első renddel approximálja a deriváltat,

Vizsgáljuk ennek kihatását az iteráció konvergenciájára, a konvergencia tétel bizonyítását követve. Először is a -t elegendően kicsire kell választanunk, úgy hogy , mert csak akkor biztos, hogy , és így . Ezután (6.10) helyett most azt írhatjuk, hogy

és ebből ugyanúgy, mint korábban következik az, hogy

(6.14)

Innen látjuk, hogy esetén továbbra is másodrendű a konvergencia. A 11. feladatból belátható, hogy ilyen -kiválasztás megvalósítható, annak ellenére, hogy ismeretlen.

Másik lehetőség az, hogy szerint választjuk a lépéstávolságot, azaz az osztott differenciát (ld.  4.2. pont) alkalmazzuk gyanánt. Ennek előnye az, hogy ilyenkor nincs szükség külön -érték kiszámítására:

19. ábra - A szelőmódszer mértani jelentése

A szelőmódszer mértani jelentése

Szelőmódszernek hívjuk ezt az eljárást. Ebben az esetben (6.14) így folytatható alapján:

vagyis, a és jelölésekkel,

(6.15)

Ezen egyenlőtlenség segítségével vizsgáljuk a szelőmódszer konvergenciarendjét.

6.2. Tétel (szelőmódszer konvergenciája).

Teljesüljenek a Newton-módszer konvergencia tételének feltételei, legyen . Ekkor a szelőmódszer vagy véges -re megáll az megoldásán vagy (lokálisan) konvergens renddel.

Bizonyítás.

Csak a tétel második esetét vizsgáljuk: , (ha -re, akkor és már nem definiált). Legyen és valamilyen -re. Ekkor (6.15)-ből az következik, hogy

(6.16)

tehát . Ezért (6.16) igaz minden -re, ha (azaz a szelőmódszer lokálisan konvergens). A (6.15) és (6.16) egyenlőtlenségekből következik az egyenlőtlenség. Ezt felhasználva bizonyítsuk be, hogy esetén érvényes

(6.17)

Ugyanis triviális, hogy , továbbá , mivel és . Az indukció kezdetét ezzel már megtárgyaltuk; (6.17) teljesül -re és -ra. Legyen most (6.17) igaz -re. Ekkor

mivel . (6.17) értelmében (ahol -et vehetünk) érvényes az állítás a konvergencia rendjéről.

Megjegyzések. 1. A (6.17) becslés megfelel a 6.4.2-ben definiált -rendű konvergencia következményének, de nem magának a definíciónak. A különbség hangsúlyozásának érdekében az eredetileg definiált konvergenciarendet Q-rendnek is hívjuk, az angol „quotient” szó után; az viszony véges marad, ha Q-rendje (legalább) . A (6.17) becslésnek megfelelő konvergenciarendet viszont R-rendnek is hívjuk, az angol „root” után; az sorozatról azt mondjuk, hogy R-rendje (legalább) , ha az -nek a következő gyökei maradnak végesek, amikor megy végtelenbe:

2. A bizonyítás során fellépő egyenlőtlenséget rövidebb úton, (6.14) megkerülésével úgy vezethetjük le, hogy belátjuk: a szelőmódszer sorozatára igaz a

rekurzió, majd – hivatkozva az első- és másodrendű osztott differenciák középérték tételére (ld.  (4.24) a 4.2 pontban) – definiáljuk , ahol , ill.  az , ill.  felső korlátja -ben.

A szelőmódszer értékelésével kapcsolatban ld. a 12. feladatot;  a „Nemlin” program különböző módszereinek gyakorlati összehasonlításához ld. a 10. feladatot.

A Newton-módszer (ill. változatainak) használatával kapcsolatos további gyakorlati szempontokat 6.4.5– 6.4.7-ben tárgyaljuk.

6.4.4. Monoton konvergencia

Ezután azt fogjuk belátni, hogy van olyan függvényosztály (a konvex vagy konkáv függvények osztálya), amelyre a Newton-módszer monoton módon és globálisan konvergens, azaz ilyenkor nincs szükségünk a konvergencia tétel azon feltételére, hogy elég jó közelítés legyen, ill. arra sem, hogy a csillapított módszert használjuk.

6.3. Tétel (Newton-módszer monoton konvergenciája).

Legyen , és az intervallumon (amely végtelen is lehet); létezzen , .

Ekkor a (6.8) iterációval előállított sorozatra érvényes monoton módon, hogyha és .

Bizonyítás.

Induljunk ki abból, hogy esetén

ahol a érték és között fekszik. Így esetén és , továbbá

mert kizárja, hogy . Legyen most , akkor innen következik és , hiszen .

Ezért és , . Folytathatjuk tehát a gondolatmenetet. Eredményül azt kapjuk, hogy , tetszőleges -re. Tehát létezik

Ekkor és ( miatt) . Viszont alapján csak egy pontban lehet , azaz . Ezzel az eset tárgyalását lezártuk, az sorozat monoton módon csökken felé.

Tükrözéssel az tengelyen kapjuk az előbbiből az állítást esetén; ekkor monoton módon növekszik.

Az , eseteket pedig az tengelyen való tükrözéssel vezetjük vissza az előbbiekre.

Megjegyzések. 1. A tétel lényeges feltételei az , ; kevésbé fontos az . Legyen pl.  és , . Akkor

és

Tehát ha , akkor , és -től kezdve monoton csökkenő módon konvergál az sorozat, mint fent. Ugyanakkor az feltételtől függ az, vajon jól definiált-e a módszer, és az feltételt elhagyva nagyon bonyolultan viselkedő sorozatot kaphatunk, esetleg végtelen ciklusba kerül az algoritmus (ld. a 6. feladat).

2. Ha teljesülnek a 6.3. tétel feltételei, akkor az előjele szerint monoton módon csökken a sorozat (+ esetén), ill. növekszik ( esetén).

3. A tétel és az első megjegyzés egyik ismert alkalmazása: a Heron-algoritmus a négyzetgyökvonásra:

Itt , az intervallum , és érvényes

6.4.5. Egyenletrendszerek megoldása Newton-módszerrel

Egyenletrendszerek megoldására szinte kizárólagosan a Newton-módszer változatait használjuk. Ennek magyarázata az, hogy már az első deriváltak megszerzése sem problémamentes (ld.  6.4.6-ot); ugyanakkor a magasabb rendű módszerek még az egydimenziós esetben sem feltétlenül hatékonyabbak (ld. a 12. feladatot).

Legyen differenciálható, az Jacobi-mátrixa, azaz

Ekkor a (6.8) iteráció minden lépésében lineáris egyenletrendszert kell megoldanunk:

Erre az 1. fejezetben tárgyalt módszereket alkalmazzuk, pl. a Gauss-elimináció megfelelő változatát. (Megjegyezzük, hogy itt és a következőkben mindig alsó indexszel jelöljük az iterációs sorozat vektorait: , ill.  . Csak kivételes helyeken fordulnak elő az -vel, ill. -vel jelölt koordináták.)

A 6.1. lokális konvergencia tétel bizonyítása lényeges változás nélkül az -dimenziós esetben is érvényes (ld. a 15. feladat); ennek érdekében fent mindenütt már -et is írtunk. Az egydimenziós esetben létezett olyan intervallum , amelyből választva a kezdeti közelítést a Newton-módszer konvergált; ehelyett most a gyököt körülvevő vonzási gömbök lépnek.

A 6.3. tétel a globális monoton konvergenciáról is érvényes a többdimenziós esetben. Ehhez csupán az helyett azt követeljük, hogy

a vizsgált tartomány minden és pontjában, ahol a konvexitás ezen – vektorokra vonatkozó – megfogalmazását (és a további, 6.4.4-ben található egyenlőtlenséget is) komponensenként értelmezzük.

A Newton-módszer gyakorlati megvalósításánál a többdimenziós esetben fokozottan fontos a módszer „globalizálása”, pl. csillapítás alkalmazásával (egy másik, általánosabb lehetőséget 6.4.8-ban tárgyalunk, a folytatás módszerét). Ugyanis a dimenzió növekedésével együtt csökkennek a megoldásokat körülvevő vonzási gömbök átmérői. Közben a Newton-módszernél kevésbé hatékony módszerek közelítései egyre távolabb maradnak a megoldásoktól, tehát ez utóbbi közelítésekből már nem fog konvergálni a Newton-módszer.

Itt is célszerű (ld. a 6.4.3. pontban tárgyalt algoritmust) a csillapítás mértékét aszerint változtatni, vajon az leereszkedési kritérium teljesül-e; ezt a kritériumot úgy lehet megszigorítani, hogy túl lassú csökkenését sem fogadjuk el, pl. felezzük a csillapítási paramétert, ha nem teljesül

(6.18)

A paraméterre – a próbálkozások helyett – a következő egyszerű módon lehet becslést kapni.

Legyen az euklideszi norma, , (6.18) ne teljesüljön. Célunk az, hogy -re mint függvényére másodfokú közelítést nyerjünk; ezt -vel fogjuk jelölni, a Newton-javítás. Ekkor

-re kapjuk a értéket, így

Ennek minimuma ; szolgálhat (kiindulási) csillapítási paraméterként akkor is, ha -et közelítő Newton-módszerrel számítottuk ki.

Megemlítjük, hogy a (6.18) követelése az egész eljárás folyamán, különösképpen az elején, nem célszerű. Ajánlatos a következőképpen eljárni: A

-hoz tartozó minimumhelyet mindig megőrizzük; megengedjük, hogy (6.18) az első iterációk során néha nem teljesül; amennyiben a mindenkori néhány nagyságrendben eltér -tól, akkor újraindítjuk a módszert -től oly módon, hogy a végtelen ciklusba kerülést lehetőleg elkerüljük, pl. a Jacobi-mátrix újbóli kiszámítását alkalmazva stb. Végül, mielőtt befejeznénk az eljárást, még egyszer összevetjük és értékeit.

Az iteráció befejezése is megfontolandó kérdés. Folytonos esetén kiindulhatunk a középértéktételből,

Emiatt, ha invertálható, érvényes

aminek alapján

(6.19)

biztosítja az

egyenlőtlenséget. Elméleti szempontból a probléma az, vajon a maximum létezik-e, ill. milyen ( -et és -ot tartalmazó) halmazra vonatkozólag kellene azt kiszámítani (v.ö. a 6.1. tétellel, ahol a halmaz és a maximum ). Gyakorlatilag az a kérdés, vajon a számítás alatt nagyobb ráfordítások nélkül úgy becsülhetjük ezen maximum értékét, hogy az egyenlőtlenség ne legyen túl pesszimista. Az alábbiakban felsorolunk néhány olyan a gyakorlatban használható leállási kritériumot, amely ezeket a kérdéseket megkerüli.

a) , pl. 

(amely kritérium magában veszélyes a lassan konvergáló eljárások esetén, ld. az 1.6.1. pontot és az 1.8. pontban a 2. feladatot);

b) (6.18) teljesül -gyel, pl. 

(még a gyorsan konvergáló eljárások is ilyen helyzetbe kerülnek, amikor elérik a kerekítési hibák szintjét, és ekkor már nem érdemes folytatni – de lásd a (6.18) alatti megjegyzéseket);

c)

A maradékvektor kicsi normája a felhasználó szempontjából a döntő bizonyítéka lehet annak, hogy megoldottuk a nemlineáris rendszert, v.ö. (6.19)-cel, valamint a lineáris rendszerek esetével is, ld. az (1.47) a-poszteriori becslést 1.3.7-ben, valamint a 3. feladatot 1.8-ban. Az -t a rendszer hozott, modell- és mérési hibaszintjéhez kell igazítani, pontosabban: valamivel ez alatt tartani, kivéve, ha ettől elfogadhatatlanul növekedne a számítási idő: ne a számítási pontatlanság legyen a döntő. A számítási tapasztalat szerint ebben a c) kritériumban az -t elég kicsinek kell választani, nehogy túl korán fejeződjék be a számítás;

d) itt is ajánlatos, maximális iterációszámot megadni.

A többértelmű megoldás lehetősége a nemlineáris rendszerek tipikus tulajdonsága; az itt vázolt módszerek keretén belül a következőt tehetjük.

Gyakorlati feladatoknál arra számíthatunk, hogy adott olyan tartomány, amely szűkebb az értelmezési tartományánál; ez lehet az illető modell érvényességi tartománya vagy olyan tartomány, amelyen kívül viselkedése nem érdekes (a (6.2) példában – az vektor ottani értelmezése szerint – elképzelhető, és , ).

Erre a tartományra ráborítunk egy pontrácsot, amelynek minden pontját használjuk kezdeti közelítésként.

Másik lehetőség az, hogy (a szélsőérték feladatoknál szokásos eljárás mintájára, ld. a 6.5.3. pontot) az első megoldás (legyen ez ) meghatározása után úgy fogalmazzuk át a feladatot, hogy ezt már nem oldja meg az . Például az egyenletek helyett vesszük , , ahol elég kicsi. Ezután -tól távol újra indítjuk a gyökmeghatározási módszert, és amennyiben gyököt találunk, ezt csökkentésével próbáljuk átvinni az eredeti rendszerbe.  Mindkét lehetőség segíthet a 23. feladat megoldásánál.

6.4.6. A Jacobi-mátrix közelítéséről

Az alábbiakban részletezzük azt a – nemcsak itt, hanem pl.  10.4. pontban is – fontos gyakorlati kérdést, hogy milyen szempontok vannak a Jacobi-mátrix kiszámításával kapcsolatban.

a) A Jacobi-mátrix kiszámításának problémáját át lehet ruházni a Newton-program felhasználójára: programozza ő maga a deriváltakat. De ilyenkor is tartalmaz a jó program olyan részt, amely közelítő differenciaképletek segítségével ellenőrzi a programozott deriváltak hihetőségét. Jobb az, ha a deriváltakat a programon belül formulamanipulációval számítjuk ki, és ez elvileg és gyakorlatilag megoldott feladat, de nem egészen problémamentes a képletek deriválása során duzzadó hossza miatt. Speciális alkalmazási területekre (pl.  (6.2) alakú egyenletekre) viszont mégis leginkább ezt az utat lehet ajánlani.

b) Ha a deriváltak pontos értékei rendelkezésünkre állnak – akár mi számítottuk ki a deriváltakat, vagy ezt valamilyen formulamanipulációs rendszer tette meg helyettünk – akkor csak arra kell figyelnünk, hogy a megfelelő tárolási struktúrát és megoldási módszert válasszuk ki. Ugyanis nagy -re a nemlineáris egyenletrendszerek Jacobi-mátrixai tipikusan ritkák (ld.  1.3.9.); ehhez kapcsolódó tapasztalati tény, hogy legtöbbször a mátrix főátlójának minden eleme nemzérus.

c) Egyszerű és biztos út az, ha a deriváltakat differenciaképletekkel közelítjük, v.ö. a 6.4.3. ponttal. A többdimenziós esetben akkor beszélünk diszkretizált Newton-módszerről, ha minden iterációs lépésre az Jacobi-mátrix elemeit az

(elsőrendű) közelítéssel számítjuk ki. Itt a -edik koordináta egységvektor, a alkalmas, nullától különböző számok, amelyeknek kiválasztásánál figyelembe kell venni az és az nagyságát, valamint az kiszámításának pontosságát (ld.  0.4.3). A fenti képletek használata azt jelenti, hogy a Newton-módszer minden lépésében általában további függvényértékre van szükségünk. Ezért alig célszerű, ha másodrendű képleteket használunk, mert ez egyrészt azt jelenti, hogy helyettesítési érték kell, másrészt az elmélet (v.ö. 6.4.3.) szerint már az elsőrendű közelítés ís hozhatja a másodrendű konvergenciát, ha . Ez utóbbi kritérium a kiválasztására egyébként az előbbiekkel ellentmondásba kerülhet, ugyanis: ha kiszámítása pontatlanul történik, akkor csökkenni fog a megoldás megközelítésének sebessége, és várható, hogy a közelítések soha be nem jutnak a megoldás körüli vonzási gömb belsejébe.

Ha a Jacobi-mátrix ritkasági struktúrája eleve ismert, akkor közelítésének műveletigénye lényegesen csökkenthető. Így pl. a (6.1) rendszer Jacobi-mátrixa tridiagonális, de a mellékátlókban álló elemek mind ismertek . Így a Jacobi-mátrix közelítéséhez csak az , függvényértékeket kell meghatároznunk, ahol alkalmas számok. Általános esetben a tridiagonális Jacobi-mátrix helyettesítési értékkel közelíthető, hiszen annyi nemzérus eleme van ilyenkor. De akkor is megtakarítható sok felesleges művelet, ha az függvényeket nem lehet külön-külön kiszámítani, hanem csak az vektorművelet kivitelezhető. Ilyenkor dolgozhatunk a következőképpen: Alkalmas számokkal és az koordináta egységvektorokkal definiálunk három vektort, , , , azaz

Ekkor számítsuk ki az

vektorokat! A rendelkezésre álló vektort kivonva ezekből, megfelelő osztások után előáll a közelítő Jacobi-mátrix minden eleme. Például csak az , , ismeretlenektől függ; -ben ezeknek megfelelő irány csak az . Így harmadik komponense , negyedik komponense pedig közelítőleg , ötödik komponense viszont közelítőleg , stb. Végeredményben a tridiagonális közelítő Jacobi-mátrix 3 vektorművelettel számítható ki, vektorművelet helyett.

Ugyanezt a gondolatmenetet (fél-)sávszélességű Jacobi-mátrixra alkalmazva, a közelítő Jacobi-mátrixot vektorművelettel kapjuk.

Ha nem sávos a mátrix, hanem általánosabb ritkasági struktúrájú, akkor színezési problémára juthatunk a következőképpen: A Jacobi-mátrix minden oszlopához hozzárendelünk egy színt; két oszlop ugyanazt a színt kaphatja akkor, ha nincsen nemzérus, egyenlő sorszámú elemük. (Így pl. a tridiagonális mátrix első, negyedik, hetedik stb. oszlopának nincsenek ilyen megegyező sorszámú nemzérus elemei, tehát ugyanazzal a színnel kiszínezhetők.) Ezután a megegyező színű oszlopok elemei egy-egy vektorművelettel számíthatók ki. Ezért a legjobb az, ha a minimális színszámmal kiszínezzük az összes oszlopot.

De nem érdemes ezt az optimális színezést megkeresni (mert ez túl költséges lenne); viszont hasznos a kézenfekvő szekvenciális színezést (az iteráció kezdete előtt) alkalmazni: Az első oszlopot kiszínezzük; átfutjuk a többi oszlopot, vajon kiszínezhető-e ugyanazzal a színnel. Ha igen, pl. a -edik oszlop, akkor a továbbiakban már csak az 1. és . oszlop közös foglaltsági struktúrára nézve keresünk kiszínezhető oszlopot stb.; amennyiben ilyen nincs, kiszínezzük az első megmaradt oszlopot a második színnel stb.

Befejezésül ehhez a ponthoz arra hívjuk fel a figyelmet, hogy reguláris Jacobi-mátrix esetén a pontos deriváltak használata nemcsak a megoldás pontosságát növeli, hanem annak esélyeit is, hogy egyáltalán meg tudjuk oldani a rendszert. Ha a Jacobi-mátrix viszont szinguláris a megoldáson vagy közelében, akkor a mátrix diszkretizációja mint regulárizáció hat, és ez javítja a módszer megbízhatóságát.

6.4.7. A Broyden-módszer

A szelőmódszer általánosítása a következő, Broyden nevéhez fűződő igen hatékony módszer, amelynél csakis az amúgy is rendelkezésünkre álló vektorok segítségével közelítjük meg a Jacobi-mátrixot. Az iteráció kezdetén a 6.4.6. pont c) részében bemutatott módon számítjuk ki a Jacobi-mátrix közelítését (vagy pedig választjuk , ill.  ), majd ezen közelítés QR-felbontását számítjuk ki, pl. Givens-módszerrel: . Ezzel kapjuk -et. Az -edik lépésnél figyelembe vesszük a következő információt:

A célunk az előállítása, majd az kiszámítása. Ehhez követeljük azt, hogy az

lineáris függvény nemcsak az pontot interpolálja (ezt megteszi), hanem az pontot is:

(6.20)

Ez a feltétel az úgynevezett „kvázi-Newton-egyenlet”, amely az egydimenziós esetben a szelőmódszert eredményezi, a többdimenziós esetben kevés az meghatározásához. Egészítsük ki azzal a követeléssel, hogy minél közelebb legyen -hez a következő értelemben:

(6.21)

Ez azt jelenti, hogy és olyan mátrixszal különböznek egymástól, amelynek rangja 1. Az

választással a (6.21) feltétel teljesül. Ezután

és (6.20)-ból következik

(6.22)

Ezzel az vektor – és vele együtt az mátrix– meg vannak határozva.

Most azt mutatjuk meg, hogy -ből és -ből művelettel közvetlenül ki tudjuk számítani a és mátrixokat, ami azt is jelenti, hogy nagyságrendileg ugyanennyi műveletbe kerül. Legyen

és kiszámítandó .

Ezek után és lesz. Itt lényeges, hogy felső háromszög mátrix és rangja 1. Az mátrix QR-felbontására használjuk a Givens-eljárást, alkalmazva a forgatási mátrixokat, ld. a 2.7.2. pontot.

Először forgatást ( , , választással) alkalmazzuk az -ra úgy, hogy kinullázzuk a mátrix összes sorát, kivéve az elsőt. Így ebből egy felső háromszög mátrix keletkezik. Eközben viszont -ben megjelenik a főátló alatt egy nemzérus elemekből álló mellékátló (tehát a transzformált és vele együtt a transzformált mátrix Hessenberg-alakú lesz). Ezután további forgatással ( , , választással) kinullázhatjuk ezt az új mellékátlót. Az mátrix felső háromszögalakra hozásával egyidejűleg már a szorzatot is kiszámítjuk.

Itt bemutattuk – a Broyden-módszer tárgyalása során – a numerikus lineáris algebra egy speciális műveletét: az mátrix elsőrangú változtatása után, hogyan kapjuk meg a megváltozott mátrix QR-felbontását. Hasonló létezik az inverz mátrixra nézve, ill. az LU-felbontásra nézve is, ld. a 16. és 17. feladatot. Emlékezzünk arra, hogy az mátrix QR-felbontása akkor előnyös az LU-felbontásával és invertálásával szemben, ha rosszul kondicionált. Egyébként viszont az LU-felbontás alkalmasabb és különösen akkor, ha nagyméretű ritka mátrix – és a nemlineáris egyenletrendszerek Jacobi-mátrixai is gyakran ilyenek.

Az mátrix QR-felbontásának birtokában kiszámítjuk az vektort, az nemlineáris rendszer keresett megoldásának következő közelítését. Ha reguláris lineáris rendszer, akkor Broyden módszere véges sok lépésben megáll a megoldáson, ld. Leary cikkét, valamint a 4. megjegyzést a 6.8. lemmához. Egyébként nem feltétlenül igaz, hogy , . A Broyden-módszer konvergenciarendjéről említjük, hogy az , ha a Newton-módszer feltételei teljesülnek.

A Broyden-módszer lokális konvergenciáját próbálkozhatunk csillapítással globálissá tenni:

Emiatt (6.22)-ben nem alkalmaztuk az egyszerűsítést; most viszont

és így (6.22) változik -re; a többi képlet megmaradt.  A Broyden-módszer ezen változata szerepel a „Nemlin” programban.

A csillapítást előnyös azzal kombinálni, hogy akkor számítjuk ki teljesen új közelítést a Jacobi-mátrixhoz differenciaképletek segítségével, ha a csillapítási paraméter többszörös csökkentése ellenére sem teljesül a leereszkedési kritérium. A csillapított Broyden-módszer esetén ugyanis nincs garancia (a csillapított Newton-módszer egydimenziós esetében a 4. feladat megoldása ilyen garanciát jelentett) – hogy elég kicsi -re teljesül a kritérium.

6.4.8. A folytatás módszere

A növekvő dimenziószámmal fokozottan szükséges a globalizálás; ennek általános lehetősége a folytatás módszere. Beágyazzuk a egyenletrendszerünket egy -dimenziós feladatba, bevezetve egy paramétert úgy, hogy -ra ismert a rendszer megoldása, -nél viszont az eredeti feladathoz kell jutnunk. A csillapítás ennek egy speciális esete. Kézenfekvő a paramétert így bevezetni:

(6.23)

Feltételezhetjük, hogy . Amikor , zérushelye . Ezért ez jó kezdeti vektor a rendszer megoldására, amikor és a lépésszám elég nagy (amennyiben a választott -ra a Newton-módszer nem konvergál, úgy a -t növeljük). Legyen . Ezután számítjuk ki zérushelyét -re, kiindulva -ből, stb., végül meghatározzuk megoldását.

20. ábra - A folytatás módszere

A folytatás módszere

Ha differenciálható környezetében, Jacobi-mátrixa ott reguláris, akkor az implicit függvényről szóló tételből következik, hogy az (esetleg: kisebb) környezetében és minden elegendően kicsi értékre -nek van gyöke, , továbbá az függvény ott egyértelműen meghatározott és -ben Lipschitz-folytonos. Végül, az függvény az pontban differenciálható t szerint, és , esetén deriváltjára igaz

(6.24)

Amennyiben az -ről felsorolt feltételek érvényesek az egész -ben, akkor minden -re differenciálható, és eleget tesz a (6.24) differenciálegyenletnek. Ezáltal és által egyértelműen meghatározott.

Ezzel a gyökmeghatározási feladatot visszavezettük egy közönséges differenciálegyenlet kezdetiérték feladatára, amelyet meg kell oldani -tól -ig. Ugyanis az egyenlet gyöke.

Lehetséges (de nem célszerű) ezt a feladatot közvetlenül a 10. fejezetben tárgyalásra kerülő módszerekkel megoldani, mert az egyenlet (6.23) integráljával is rendelkezünk.

Konvergencia bizonyítás levezetése érdekében a következőképpen fogalmazzuk meg a folytatásos módszert.

Legyen és adott, és az -hoz tartozó (6.23) függvény.

(6.25)

egyenletrendszer megoldásához iterációt végzünk Newton-módszerrel; ennek eredményét -gyel jelölve továbblépünk.

6.4. Tétel (folytatásos módszer elégséges konvergencia feltétele).

Legyen az rendszer gyöke, teljesüljön az egész -ben

Ha a (6.25) folytatásos módszer lépésszámára igaz

(6.26)

akkor minden -hoz létezik olyan , a közbülső Newton-lépések száma, hogy érvényes

Bizonyítás.

Ha , akkor -val igaz a tétel. Legyen . Elsőnek lássuk be, hogy tetszőleges pont távolsága a (6.23) megoldásai által meghatározott görbétől

(6.27)

Ugyanis

tehát

Ezután rögzített -re és tetszőleges -re vizsgáljuk a (6.25) módszer -edik közbülső rendszerének megoldását:

tehát

és így

Az -mel beindított Newton-módszer (6.25) megoldásához konvergál, mivel (v.ö. a 6.1. tétellel és a tétel utáni 2. megjegyzésével)

meghatározása miatt; a 6.1. tétel bizonyításában szereplő szám értéke itt . Így az iteráció után kapott -re igaz

Az iterációszámot úgy választhatjuk, hogy . Az közelítő megoldással nem teljesül, hanem

ahol . Ezért a folytatás utolsó, -adik lépésében érvényes

Ennek alapján és most (6.27)-ből és -ból következik .

Megjegyzések. 1. A folytatásos módszert ezután úgy is felfoghatjuk, hogy az esetleg kedvezőtlenül megválasztott -ból kiindulva végül is olyan kezdeti vektort gyárt a Newton-módszer beindítására, amely a lokális konvergencia vonzási gömbjében fekszik. (6.26) szerint az ehhez befektetendő munka lineárisan nő értékével, választása miatt ehhez jön még a szorzó.

2. Gyakorlatilag célszerűbb, nem rögzített -t, hanem a helyi viszonyoktól (pl. a Newton-iteráció sikerétől) függően változó -t választani. Megemlítjük, hogy a (6.25) egyenletrendszerek megoldásának első Newton-lépése, ha nulladik közelítésként az utolsó közelítő megoldást vesszük, az

egyszerűbb alakot ölti, amely a (6.24) egyenlet approximációjaként is értelmezhető. Ezen képlet használata akkor is bevált, ha nem a (6.25), hanem a (6.23), , közbülső rendszerekkel dolgozunk. Ebben az esetben szerepe analóg a közönséges differenciálegyenletek megoldása során szokásos, úgynevezett prediktor- (javaslattevő) képletekkel (ld. a 10.2. pontot).

A folytatásos módszer alkalmazása nem mindig ésszerű. Lehetséges, hogy sok számítási időnk megy el olyan közbülső egyenletrendszerek megoldására, amelyek egyáltalán nem érdekesek; a folytatás közepette esetleg olyan helyzetekkel találkozunk, amelyeket a fenti elméleti tárgyalásnál kizártunk (pl.  szingularitása), és amelyek leküzdése speciális fogásokat igényel. Viszont vannak feladatok, amelyeknél másképpen nem jutunk megoldáshoz.

A módszer feltétlenül akkor ajánlott, ha természetes paraméter van a feladatban, amelynek bizonyos értékére ismerünk megoldást. Mechanikai feladatokban a rendszer terhelése lehet ilyen paraméter: nullából kiindulva – amikor nyugalmi helyzetben van a rendszer – emelhetjük a kívánt értékre, és ilyenkor az összes közbülső állapot is fontos. Ekkor szingularitásai különösen érdekesek: ott a megoldási görbe esetleg szétágazik (bifurkáció történik), azaz több különböző állapotba kerülhet a rendszer vagy instabilitások lépnek fel.

A (6.2) egyenletek pontos nemtriviális megoldása általában nem ismert, de lényegesen egyszerűbben előállítható, ha a számok (aktiválási energiák) kicsik. Ennek alapján itt is javasolható a folytatás módszere oly módon, hogy az összes -t helyettesítjük -vel és a paramétert változtatjuk nulláról egyre.

 A „Nemlin” programban a folytatásos módszert megvalósíthatjuk úgy, hogy egy-egy közbülső rendszer megoldása után megváltoztatjuk a folytatás paraméterét és az utolsó megoldást kezdeti vektornak adjuk be.