PA081: Programování numerických výpočtů A. Křenek PA081: Programování numerických výpočtů 5. Systémy nelineárních rovnic Newtonova metoda Hledání po přímce Aleš Křenek jaro 2011 Řešený problém ► formulace problému Fí(xi,...,xn) = 0 pro í = l,...N PA081: Programování numerických výpočtů A. Kfenek Metoda prosté iterace Newtonova metoda Hledám po přímce 4fl> • 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é ► 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 ► 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 ► 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 f(x) = X-Fí(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 PA081: Programování numerických výpočtů A. Křenek Metoda prosté iterace Newtonova metoda Hledání po přímce 13/19 Newtonova metoda s hledáním po přímce ► Newtonovský krok Ax je směrem dolů vůči / (V/)rAx = (F^H-J-iF) = -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 14/19 Newtonova metoda s hledáním po přímce ► Newtonovský krok Ax je směrem dolů vůči / (V/)rAx = (F^H-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^H-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^H-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\( V/)rAx ► 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) = (V/)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) = (V/)rAx ► aproximujeme g(A) polynomem ► nejprve kvadratický procházející g(0) ag(l) 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í g'(0) = (V/)rAx ► aproximujeme g(A) polynomem ► nejprve kvadratický procházející g(0) ag(l) a\2 + g'{0)\ + 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 Aí a\3 + b\2 +g'(0)\ + g(0) ► opakujeme do dosažení g(A) < g(0) + a\g'(0) 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 Vícerozměrná metoda sečen ► jednorozměrná metoda pracuje s aproximací derivace , f(xi+i) - f(Xi) a-i+i = - xi+l ~ xi ► analogicky pro více rozměrů Bí+iAxí = 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 u u , (AFj -BjAXj) 8> AXj "í+l "Dii--7t-7^-1- (AXí)rAXí 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 Bí 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 Bí 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 Bí 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