PA081: Programování numerických
výpočtů
3. Systémy nelineárních rovnic
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
Aleš Křenek
jaro 2016
1/22
Řešený problém
► formulace problému
Fi(xi,.m.,xN) = 0     pro i = 1,...JV
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
2/22
Řešený problém
formulace problému
Fi(xi,.. .,Xn) = 0     pro i = 1,...N
není to jednoduché, neexistuje univerzální řešení
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
Řešený problém
► formulace problému
Fí(xi,...,xn) = 0     pro i = 1,...JV
► není to jednoduché, neexistuje univerzální řešení
► pro dvě dimenze, funkce f(x,y),g(x,y)
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
.v
2/22
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í Fi nulová
► konkrétní Fi jich může vygenerovat několik
► ani nevíme kolik jich je
► bez podrobnější znalosti konkrétního problému se neobejdeme
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
Metoda prosté iterace
► zobecnění metody pro jednu proměnnou
► problém přeformulujeme do podoby
xi = Gi(x) x2 = G2(x)
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
xn = GN(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 Xi+i = G(xí) konverguje k §
Metoda prosté iterace
praktické kritérium konvergence
dGi(x) dx
N
resp. slabší
n 1
J = l
dGi(x) dx
pro všechna í,j = l,...,iVaO<g<l
< q < 1     pro všechna í = 1,..., AT
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
► důkaz uvažuje metriku p(x,y) = maxi<i<^ \xi - yi\
► základem je Taylorův rozvoj G(x + Ax)
► ve více dimenzích vede právě na sumu parciálních derivací
Metoda prosté iterace - příklad
►
reste system rovnic
2 1
(x-iy-y-- = 0
-x2 +y2 - 1 = 0 4
► 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        n 1
x = Gi(x,y) =        - y + iz)
y = G2(x,y) = \{-x2 - 4y2 + 8y + 4)
O
parciální derivace
dGi dGi _ 1
dx ~X dy 2
dG2       1 3G2
—— = --x —— = -y + 1
dx       4 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 dGz/dy porušují podmínky konvergence
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
8/22
Metoda prosté iterace - příklad
► druhý kořen je poblíž (2,0)
► metoda diverguje
► dGi/dx a dGzIdy porušují podmínky konvergence
► stačí použít
1 1
Gi(x,y) = ~^(x2 - 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
►
►
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
Newtonova metoda pro systémy rovnic
Odvození
► Taylorův rozvoj systému
N dF
F;(x + Ax) = Fi(x) + X ^AxJ + 0(Ax2)
► v maticovém vyjádření s Jakobiánem J = (dFi/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
Odhady přesnosti - označení
PA081: Programování numerických
výpočtů
A. Křenek
vypočet F(xí)
et < u||F(xí)|| + qj(F,xuu)
výpočet Jakobiánu a řešení lineárního systému
Et < u4>(¥,Xi,n,u)
► vypočet Xi + <5x
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
€i < udlxíll + llóxll)
10/22
Newtonova metoda pro systémy rovnic
Odhady přesnosti - Tisseurova věta
J(x*) je dobře podmíněná
uk(J(x*)) < 1/8
chyba výpočtu Jakobiánu a lineárních rovnic je malá
^IIJ(Xi)"1|l0(F,Xi,n,u)|| < 1/8 J je lipschitzovsky spojitá funkce
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
IJ(v) - J(w)|| < j8||v- w
počáteční odhad je dostatečně blízko
/JIU(x*)
-i
x0 -x*|| < 1/8
Newtonova metoda pro systémy rovnic
Odhady přesnosti - Tisseurova věta
PA081: Programování numerických
výpočtů
A. Křenek
► pak relativní chyba řešení Newtonovou metodou klesá až dosáhne
Kx*)-1
x
c//(F,x*,u) + u
*
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
Newtonova metoda pro systémy rovnic
Odhady přesností - Tisseurova věta
PA081: Programování numerických
výpočtů
A. Křenek
► pak relativní chyba řešení Newtonovou metodou klesá až dosáhne
IJ(x*)
-i
x
(//(F,x*,u) + u
přesnost závisí na podmíněnosti J
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
12/22
Newtonova metoda pro systémy rovnic
Odhady přesnosti - Tisseurova věta
► pak relativní chyba řešení Newtonovou metodou klesá až dosáhne
IKx*)-1
x
c//(F,x*,u) + u
*
► přesnost závisí na podmíněnosti J
► nezávisí na 4>, tj. nepřesnosti výpočtu J a řešení lineárních rovnic
pouze jsou na ně kladeny jisté podmínky lze použít nepřesné řešení lineárních rovnic Jakobián není třeba počítat v každém kroku
►
►
►
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
Newtonova metoda pro systémy rovnic
Odhady přesnosti - Tisseurova věta
► pak relativní chyba řešení Newtonovou metodou klesá až dosáhne
IKx*)-1
x
c//(F,x*,u) + u
*
► přesnost závisí na podmíněnosti J
► nezávisí na 4>, tj. nepřesnosti výpočtu J a řešení lineárních rovnic
pouze jsou na ně kladeny jisté podmínky lze použít nepřesné řešení lineárních rovnic Jakobián není třeba počítat v každém kroku
► nepřesnosti mají vliv na rychlost konvergence
►
►
►
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
Newtonova metoda pro systémy rovnic
Shrnutí vlastností
► 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\xí\<£x  nebo   ^ |Fí | < eF
►
►
►
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
(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
Shrnutí vlastností
► problém /' — 0 „obohacen" na singularity J
► mnoho řešení - určitě se netrefíme
► žádné řešení - ??
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
<<□► < r3i ► <<!► 4 1 ►
14/22
Newtonova metoda pro systémy rovnic
Shrnutí vlastností
► problém /' — 0 „obohacen" na singularity J
► mnoho řešení - určitě se netrefíme
► zadne reseni - ??
► 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é
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
Newtonova metoda pro systémy rovnic
Shrnutí vlastností
► problém /' — 0 „obohacen" na singularity J
► mnoho řešení - určitě se netrefíme
► zadne reseni - ??
► 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é
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
►
►
► 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?
►
►
►
►
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) = !XF;(x)2
► pouze nezáporné hodnoty
► globální minima (0) v kořenech původního systému F
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
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) = I^F^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á f(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 f(x) = Xfí(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 /
(V/)rAx = (F^JH-J^F) = -FrF < 0
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
17/22
Newtonova metoda s hledáním po přímce
► Newtonovský krok Ax je směrem dolů vůči /
(V/)rAx = (F^M-J-iF) = -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 /
(V/)rAx = (F^M-J-iF) = -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 f(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 /
(V/)rAx = (F^M-J-iF) = -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 f(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) < f(x) nestačí
► je třeba f(x + AAx) < f(x) + a\(\/f)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) = /(x + AAx)
► platí g'(0) = (V/)TAx
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
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í gf(0) = (Vf)TAx
► aproximujeme g (A) polynomem
► nejprve kvadratický procházející g(0) a g(l)
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
a\2 + g'(0)\ + 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í gf(0) = (Vf)TAx
► aproximujeme g (A) polynomem
► nejprve kvadratický procházející g(0) a g(l)
aA2 + #'(0)A + #(0)
minimum je v Ai = -g'(0)/2a
► další kroky kubický polynom procházející g(0) a dvěma nej čerstvějšími A;
aA3 + bA2 +gr(0)A + g(0)
► opakujeme do dosažení g (A) < g(0) + otAg'(0)
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
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
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
Vícerozměrná metoda sečen
jednorozměrná metoda pracuje s aproximací derivace
dí+i =-
Xi+l Xi
analogicky pro více rozměrů
Bi+iAXi = AF;
nedává jednoznačné řešení Broydenova metoda
► rekurentní formule Bí+i na základě B*
► minimální změna, která ještě vyhoví kritériu sečny
jy     _u  , (AFj - BjAXj) 0 Axj
(AXi)TAXi
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    aproximací J
► zpravidla dopředně diference
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen
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    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    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ému 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
►
►
►
►
PA081: Programování numerických
výpočtů
A. Křenek
Metoda prosté iterace
Newtonova metoda
Hledání po přímce
Metoda sečen