PA081: Programování numerických výpočtů
5. Systémy nelineárních rovnic
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Aleš Křenek
jaro 2013
Řešený problém
► formulace problému
Fi(xľ,...,xN) = 0
pro i = 1,.. .N
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledáni po přímce
4 □ ► 4 (5 ► <     ► < ►
Řešený problém
► formulace problému
Fi(xu...,xN) = 0     pro i = 1....JV
► není to jednoduché, neexistuje univerzální řešení
Newtonova metoda
Hledání po přímce
Řešený problém
► formulace problému
Fí(xi,...,xn) = 0 proi=l,...JV
► není to jednoduché, neexistuje univerzální řešení
► pro dvě dimenze, funkce f{x,y),g{x,y)
	noroothere!		two roots nere g pos
	gP"S S"--	f= o        S neg \^	
	/neg '	/pos        \ 11	
			
		g pos	
		x	
Newtonova metoda
Hledání po přímce
2/19
Neřešitelný problém
► funkce nemají obecně nic společného
► řešení celého systému se objevují v podstatě náhodně
► v obecném případě hledáme společné body hyperpovrchů dimenze N - 1
► oblasti, kde je konkrétní Fj nulová
► konkrétní Ft jich může vygenerovat několik
► ani nevíme kolik jich je
bez podrobnější znalosti konkrétního problému se neobejdeme
Metoda prosté iterace
zobecnění metody pro jednu proměnnou problém přeformulujeme do podoby
xi = Gi(x) x2 = G2 (x)
xN = Gjv(x)
potřebujeme nějakou metriku na RN
je-li G(x) kontrakce na nějaké uzavřené omezené podmnožině RN, pak v ní existuje pevný bod G(£)
posloupnost Xj+i = G(Xj) konverguje k ^
Metoda prosté iterace
praktické kritérium konvergence
dGj(x)
B.
N
resp. slabší
SGŕ(x)
jv
I
dxj
pro všechna i, j = 1,... ,N aO < q < 1
< q < 1     pro všechna í = 1,..., N
důkaz uvažuje metriku p(x,y) = maxi<i<jv \xt - yi\ základem je Taylorův rozvoj G(x + Ax)
► ve více dimenzích vede právě na sumu parciálních derivací
Newtonova metoda
Hledání po přímce
Metoda prosté iterace - příklad
řešte systém rovnic
(x-l)2-y - - = 0
\x2 +y2 -1 = 0
v grafu
► parabola s vrcholem (1, -|)
► elipsa se středem v 0 a poloosami 2 a 1
Metoda prosté iterace - příklad
rovnice vyjádříme jako
1    ? 1 x = Gi(x,y) = -(xlL - y + -)
y = G2(x,y) = \{-x2 - 4y2 + 8y + 4)
parciální derivace
3Gi 3Gi _ 1
dx ~X By 2
dG2       1 3G2 ^— = ^— = -y + l dx       A dy
v okolí (0,1) jsou podmínky konvergence splněny metoda najde kořen cca. (-0.222,0.994)
Metoda prosté iterace - příklad
► druhý kořen je poblíž (2,0) metoda diverguje
► dGi/dx a dG2/dy porušují podmínky konvergence
Metoda prosté iterace - příklad
► druhý kořen je poblíž (2,0) metoda diverguje
► dGi/dx a dG2/dy porušují podmínky konvergence
► stačí použít
1    ? 1 Gi(x,y) = -^(* -6x-y + -)
► metoda už konverguje, i když kritérium není zcela splněno
► podmínka byla postačující, nikoli nutná
► při jinak definované metrice už je G kontrakce
Newtonova metoda pro systémy rovnic
► Taylorův rozvoj systému
Fi(x + Ax) = Fdx) + X f^Ax/ + 0(Ax2)
► v maticovém vyjádření s Jakobiánem J = (dFt/dXj)
F(x + Ax) = F(x) + JAx + 0(Ax2)
► položíme F(x + Ax) = 0 a zanedbáním dostáváme
JAx = -F(x)
► Ax použijeme jako iterační krok
► získáme řešením systému lineárních rovnic
► metody probereme v některé z dalších přednášek
Newtonova metoda pro systémy rovnic
► vlastnosti analogické jednodimenzionální verzi
► rychlá (kvadratická) konvergence
► začne stagnovat při dosažení strojové přesnosti v x nebo F
► kritéria kovergence zpravidla
YJ\xi\<ex   nebo ]T|Fr|<ef
(které nastane dříve)
► špatné globální vlastnosti
► při nepřesném odhadu může snadno zabloudit
► nutná kontrola řešení
► potřebné výpočty derivací
► není tolik jiných metod na výběr
► v nouzi má smysl i aproximace konečnou diferencí
► dopředný (recyklace hodnoty funkce) nebo centrální výpočet
Newtonova metoda pro systémy rovnic
► problém /' —■ 0 „obohacen" na singularity J
► mnoho řešení - určitě se netrefíme
► žádné řešení - ??
Newtonova metoda pro systémy rovnic
► problém /' —■ 0 „obohacen" na singularity J
► mnoho řešení - určitě se netrefíme
► žádné řešení - ??
► závažnější numerické potíže
► např. opakované přičtení malé hodnoty by nasměrovalo metodu jinam
► přetečení a podtečení při násobení
► maskovány v maticových operacích - špatně odhalitelné
Newtonova metoda pro systémy rovnic
PA081: Programování numerických
výpočtů
problém /' —■ 0 „obohacen" na singularity J
► mnoho řešení - určitě se netrefíme
► žádné řešení - ??
A. Křenek
Metoda prosté iterace
Newtonova metoda
závažnější numerické potíže
Hledání po přímce
► např. opakované přičtení malé hodnoty by nasměrovalo
metodu jinam
► přetečení a podtečení při násobení
► maskovány v maticových operacích - špatně odhalitelné
► správné škálování
► řádově srovnatelné hodnoty nezávislých proměnných
► dtto. funkční hodnoty, i vůči proměnným
► nejlépe v řádu jednotek
► odpovídající nastavení intervalu pro diference místo derivací
► když to nejde - řeším ten správný problém?
■O0.O
Převedení na optimalizaci
► optimalizační metody (hledání minima)
► numericky a algoritmicky příjemnější
► zdánlivě složitější problém
► zkusíme řešení rovnic převést na optimalizaci
► definujeme funkci
/(x) = |^Pr(x)2
► pouze nezáporné hodnoty
► globální minima (0) v kořenech původního systému F
Převedení na optimalizaci
► optimalizační metody (hledání minima)
► numericky a algoritmicky příjemnější
► zdánlivě složitější problém
► zkusíme řešení rovnic převést na optimalizaci
► definujeme funkci
/(x) = |^Pr(x)2
► pouze nezáporné hodnoty
► globální minima (0) v kořenech původního systému F
► optimalizační metody hledají lokální minimum
► taková /(x) jich má zpravidla příliš mnoho
► nutný ještě přesnější odhad řešení
► využití v kombinovaných metodách
Newtonova metoda s hledáním po přímce
► krok Newtonovy metody pro řešení F(x) = 0
► používá se k minimalizaci funkce /(x) = Y,Fi(x)2
► v případě potřeby se krok zkrátí
► v reálných případech úspěšnější
► exaktní specifikace podmínek konvergence je komplikovaná a v praxi téměř neověřitelná
► metoda může uváznout v lokálním minimu /
► lze snadno detekovat
► je třeba zkusit jiný počáteční odhad
Newtonova metoda s hledáním po přímce
► Newtonovský krok Ax je směrem dolů vůči /
(Vf)rAx = (F^X-J^F) = -FrF < 0
Newtonova metoda s hledáním po přímce
► Newtonovský krok Ax je směrem dolů vůči /
(Vf)rAx = (F^X-J^F) = -FrF < 0
► směr Ax je správně
► při dostatečně krátkém kroku hodnota / poklesne
► celý krok může být příliš
► kvadratická aproximace může být nepřesná
Newtonova metoda s hledáním po přímce
► Newtonovský krok Ax je směrem dolů vůči /
(Vf)rAx = (F^X-J^F) = -FrF < 0
► směr Ax je správně
► při dostatečně krátkém kroku hodnota / poklesne
► celý krok může být příliš
► kvadratická aproximace může být nepřesná
► volíme krok AAx pro vhodné 0 < A < 1
► zdánlivě nejlepší je minimalizovat /(x + AAx) vůči A
► výpočetně náročné (počet vyhodnocení F)
► lze ukázat, že to není nezbytné k dosažení rychlé konvergence
Newtonova metoda s hledáním po přímce
► Newtonovský krok Ax je směrem dolů vůči /
(Vf)rAx = (F^X-J^F) = -FrF < 0
► směr Ax je správně
► při dostatečně krátkém kroku hodnota / poklesne
► celý krok může být příliš
► kvadratická aproximace může být nepřesná
► volíme krok AAx pro vhodné 0 < A < 1
► zdánlivě nejlepší je minimalizovat /(x + AAx) vůči A
► výpočetně náročné (počet vyhodnocení F)
► lze ukázat, že to není nezbytné k dosažení rychlé konvergence
► prosté kritérium f(x + AAx) < /(x) nestačí
► je třeba /(x + AAx) < /(x) + oíA( V/)tAx
► stačí malé a, např. 10~4
Newtonova metoda s hledáním po přímce
► první pokus - plný krok Ax
► ideální by bylo minimalizovat g (A) = f(x + AAx)
► platí g'(0) = (Vf)rAx
Newtonova metoda s hledáním po přímce
► první pokus - plný krok Ax
► ideální by bylo minimalizovat g (A) = f(x + AAx)
► platí g'(0) = (Vf)rAx
► aproximujeme g(A) polynomem
► nejprve kvadratický procházející g(0) a g(l)
a\z + g'(0)A + g(0) minimum je v Ai = -g'(0)/2a
Newtonova metoda s hledáním po přímce
► první pokus - plný krok Ax
► ideální by bylo minimalizovat g (A) = f(x + AAx)
► platí g'(0) = (Vf)rAx
► aproximujeme g(A) polynomem
► nejprve kvadratický procházející g(0) a g(l)
aAz + g'(0)A + g(0)
minimum je v Ai = -g'(0)/2a
► další kroky kubický polynom procházející g(0) a dvěma nej čerstvějšími Ai
aA3 + b\z + g'(0)\ + g(0)
► opakujeme do dosažení g(Á) < g(0) + aÁg'(0)
Newtonova metoda
Hledání po přímce
15/19
Newtonova metoda - shrnutí
rychlá konvergence, špatné globální vlastnosti vyžaduje derivace
globální vlastnosti lze vylepšit řízeným zkrácením kroku i tak není metoda 100% spolehlivá
neobejdeme se bez základní znalosti řešeného problému
Newtonova metoda
Hledání po přímce
Vícerozměrná metoda sečen
jednorozměrná metoda pracuje s aproximací derivace
, f(Xi+1) - f(Xi)
= -
xi+l ~ xi
analogicky pro více rozměrů
Bi+1AXi = AFi
nedává jednoznačné řešení Broydenova metoda
► rekurentní formule Bj+i na základě Bj
► minimální změna, která ještě vyhoví kritériu sečny
„        „  , (AFi - BjAxj) ® Axí
m+i - dí-\--——-~--
(AxiKAxi
Vícerozměrná metoda sečen
► neexistuje jednoznačná analogie separace kořenů
► může zabloudit stejně jako Newtonova metoda
► lze aplikovat stejný princip hledání po přímce
► B není přesně Jakobián
► negarantuje, že Ax směřuje dolů vůči / = ^FF
► základní předpoklad hledání po přímce
► v případě selhání náhrada Bi aproximací J
► zpravidla dopředně diference
Vícerozměrná metoda sečen
► neexistuje jednoznačná analogie separace kořenů
► může zabloudit stejně jako Newtonova metoda
► lze aplikovat stejný princip hledání po přímce
► B není přesně Jakobián
► negarantuje, že Ax směřuje dolů vůči / = ^FF
► základní předpoklad hledání po přímce
► v případě selhání náhrada Bi aproximací J
► zpravidla dopředně diference
► problém singularity B (resp. J v Newtonově metodě)
► nelze určit následující krok
► řeší se umělou modifikací B nebo „krokem stranou"
► de-facto restart z jiného, bližšího bodu
Vícerozměrná metoda sečen
► neexistuje jednoznačná analogie separace kořenů
► může zabloudit stejně jako Newtonova metoda
► lze aplikovat stejný princip hledání po přímce
► B není přesně Jakobián
► negarantuje, že Ax směřuje dolů vůči / = ^FF
► základní předpoklad hledání po přímce
► v případě selhání náhrada Bi aproximací J
► zpravidla dopředně diference
► problém singularity B (resp. J v Newtonově metodě)
► nelze určit následující krok
► řeší se umělou modifikací B nebo „krokem stranou"
► de-facto restart z jiného, bližšího bodu
► existují i komplikovanější metody
► neomezují se jen na hledání po přímce
Shrnutí
řešení systémů nelineárních rovnic je jeden z nej nepříjemnějších problémů
► řešení se vyskytují „náhodně"
► nelze mechanicky separovat kořeny
► vždy je třeba mít základní představu o charakteristice problému
metoda prosté iterace
► dokážeme-li splnit podmínky konvergence
► rychost konvergence neurčitá
Newtonova a Broydenova metoda
► vylepšení globálních vlastností hledáním po po přímce
► nejsou zcela spolehlivé, mohou uváznout v lokálním minimu pomocné funkce
detaily a implementace viz W.H.Press, Numerical Recipes in C
► netřeba se učit vzorce zpaměti
► důležité je znát podstatu problémů a principy metod
Newtonova metoda
Hledání po přímce