Metody řešení systémů nelineárních rovnic Tomáš Jeřábek Osnova 1. Soustava nelineárních rovnic 2. Iterační metody 3. Rychlost konvergence 4. Paralelní metoda tětiv 5. Newtonova metoda a její modifikace 6. Broydenova metoda Soustava n nelineárních rovnic o n neznámých Jsou dány funkce niRRf n i .......1,: = Hledáme ( )T nxxx ,.....,1 * = takové, že: ( ) ( ) 0....., 0....., ,1 ,11 = = nn n xxf xxf M Vektorově může psát ( ) 0* =xF Iterační metody * Soustavu rovnic budeme řešit iteračními metodami. * Těmito metodami vytváříme posloupnost iterací takovou, že { }k x kxxk ,* * Budeme se zabývat iteračními metodami tvaru kde nn k RRG : ,.......1,0,1 ==+ kxGx k k k * U každé iterační metody nás bude zajímat kdy bude konvergovat a jakou rychlostí bude konvergovat. Rychlost konvergence I * Označme odchylku od řešení v k ­ té iteraci jako k h tj. * xxh kk -= * Řekneme, že konvergence metody je p ­ řádu, jestliže 0k h a 0, 1 > + pk k h h * Z praktického hlediska jsou důležité v podstatě jen případy pro p = 1 (lineární konvergence), p = 2 (kvadratická konvergence, p = 3 (kubická konvergence) Rychlost konvergence II * Pro každou lineárně konvergentní metodu existuje konstanta 0> tak, že neboli * Obdobně pro metodu s kvadratickou konvergencí platí + 2 1 k k h h =+ 21 kk hOhneboli * A podobně pro metodu s kubickou konvergencí + k k h h 1 ( )kk hOh =+1 Rychlost konvergence III * Řada iteračních metod, které nejsou kvadraticky konvergentní konvergují rychleji než jak to zaručuje lineární konvergence: 0 1 + k k h h neboli ( )kk hoh =+1 * O takových metodách říkáme, že mají superlineární konvergenci Paralelní metoda tětiv I * Nechť nn RRF : a mějme dánu počáteční iteraci 0 x Hledáme iterace ,......, 21 xx takové, že posloupnost těchto iterací konverguje k řešení * x * PMT definujeme předpisem ( )kkk xFAxx 11 -+ -= kde A je regulární matice. * Nyní nás bude zajímat jak vhodně vybrat matici A * Matice A musí být regulární a metoda musí být lokálně konvergentní. Tzn. že pokud počáteční iterace je dostatečně blízko k řešení soustavy pak by mělo platit, že kxxk ,* Paralelní metoda tětiv II * Dostatečnou podmínkou pro lokální konvergenci PMT je splnění Za předpokladu, že existuje. * Nejlepším výběrem bude tedy matice, která se mění v každé iteraci a pro posloupnost těchto matic ( )( ) 1' *1 <-= - xFAI kA platí: ( ) kxFAk ,' * * Pokud položíme ( )k k xFA '´ = dostáváme Newtonovu metodu ( )* ' xF Newtonova metoda * Posloupnost iterací je vytvářena předpisem ( ) ( )kkkk xFxFxx 11 ' -+ -= * Výpočet iterace vyžaduje: - Ohodnotíme - řešíme systém rovnic - Položíme ( )k xF * Pokud zvolíme poč. iteraci dostatečně blízko k řešení a ( )* ' xF je regulární a lipschitzovsky spojitá, pak NM konverguje kvadraticky. ( ) ( )kkk xFpxF -=' kkk pxx +=+1 Newtonova metoda II * Výhodou NM je rychlá konvergence * Nevýhodou je nutnost přehodnocovat jacobián v každé iteraci. Další nevýhodou je nutnost v každé iteraci řešit systém lin. rovnic. * Na základě těchto nevýhod byly vyvinuty modifikace NM, které zmírňují některou z nevýhod, ale za cenu pomalejší konvergence. Příklad Budeme řešit následující soustavu 16 113 432 4 17 4 3 4 2 2 1 4 133221 2 3 2 2 2 1 =++ =++ =++ xxx xxxxxx xxx S počáteční iterací ( )7,1;5,0;3,10 -=x Jako kritérium pro ukončení zvolíme ( ) 6 10-