Numerické metody řešení soustav nelineárních rovnic v modelování a simulaci

Tomáš Vogeltanz, Roman Jašek

Univerzita Tomáše Bati ve Zlíně
Fakulta aplikované informatiky
Nad Stráněmi 4511, 760 05 Zlín
Česká republika

vogeltanz@fai.utb.cz, jasek@fai.utb.cz

Abstrakt: Tato práce pojednává o nejčastěji využívaných numerických metodách při řešení soustav nelineárních rovnic vmodelování a simulaci systémů. Vzhledem ktomu, že existuje celá řada úloh, které není možné řešit analyticky, je vtakových případech nutné využít principů numerické matematiky. Nejčastěji se lze vreálné praxi setkat se soustavaminelineárních rovnic, a proto jsou zde zmíněny pouze metody vhodné pro tuto soustavu rovnic. Vzhledem kobecnému vyjádření těchto metod je lze ovšem využití i pro řešení soustav lineárních rovnic.

Klíčová slova: Numerické metody, Soustavy nelineárních rovnic, Nelineární rovnice, Modelování, Simulace

Abstract: This paper discusses the most common numerical methods used to solve systems of nonlinear equations in modeling and simulation. Because of there are a number of tasks which can't be solved analytically, it is necessary to use the principles of numerical mathematics in these cases. In the real world, we can the most often meet with systems of nonlinear equations, and therefore are mentioned only methods suitable for this kind of systems of equations. However, given the general expression of these methods, they can also be used for solving systems of linear equations.

Keywords: Numerical Methods, Systems of Nonlinear Equations, Nonlinear Equations, Modeling, Simulation

Úvod

V této práci je popsáno řešení soustav nelineárních rovnic pomocí numerických metod. Jsou zde uvedeny tři nejčastěji používané metody pro jejich řešení – metoda přímé iterace, zobecněná Newtonova metoda a zobecněná metoda sečen.

Nelineární rovnice se vyskytují vnejrůznějších inženýrských aplikacích, např.: [1]

• Výpočet stacionární simulace systému zařízení
• Výpočet stacionárních stavů dynamických modelů popsaných obyčejnými diferenciálními rovnicemi
• Náhrada parabolických nebo eliptických rovnic metodou konečných diferencí
• Výpočet složité chemické rovnováhy
• Řešení protiproudých separačních zařízení, jako jsou např. rektifikační či absorpční kolony

Velmi častou úlohou, která vzniká při řešení praktických problémů, je nalézt n neznámých x1,x2,...,xn, které vyhovují nelineárním rovnicím (1). Tuto soustavu lze také popsat vektorově (2). [1] [2] [3] [4]

	(1)
.	(2)

Metody pro řešení soustav nelineárních rovnic vypadají velice podobně jako pro jedinou nelineární rovnici. Ve skutečnosti je ale vícedimenzionální případ mnohem složitější, protože je velmi těžké získat dobré informace o poloze kořene. Podmínky konvergence obou uvedených metod se také ověřují mnohem obtížněji. [4]

1 Metoda přímé iterace

Soustavu nelineárních rovnic (1) upravíme na tvar (3), což lze také zapsat vektorově jako (4). [4] [5]

	(3)
.	(4)

Zvolíme počáteční aproximaci x0 a počítáme posloupnost postupných aproximací z iteračního vztahu:

.

(5)

Pro zastavení výpočtu se používá kritérium (6), kde volíme ε vzávislosti na tom, jak přesné řešení potřebujeme. Obecně znamená menší hodnota ε přesnější řešení, ovšem je také potřeba myslet na nepřesnosti při výpočtech, díky kterým přehnaně malá hodnota ε může narušit nalezení správného řešení. [4] [5]

(6)

Většinou bývá obtížné zajistit konvergenci, zvláště u rozsáhlejších soustav rovnic, popř. je konvergence pomalejší než u ostatních metod. Při rychlosti dnešních PC již většinou nebývá problém využít metodu pokusu. V tom případě je však nutno zvláště pečlivě prověřit výsledek. Na začátku výpočtu je vhodné předem stanovit maximální počet kroků metody a je-li překročen, výpočet ukončit s tím, že metoda diverguje. Pak je potřeba zvolit jinou počáteční aproximaci, jiné iterační funkce, nebo jinou metodu. Najít vhodné iterační funkce může být velmi obtížné. [4] [5]

Tato metoda se nedá využít pro všechny soustavy nelineárních rovnic. Lze si však vněkterých případech pomoci v podstatě převedením soustavy nelineárních rovnic na soustavu nelineárních diferenciálních rovnic a využít např. Eulerovu metodu nebo metodu Runge-Kutta kprovedení iterací. Řešení pak získáme ve chvíli, kdy se hodnoty výsledků téměř nemění (dosáhne se ustálení).

2 Zobecněná Newtonova metoda

Newtonova metoda pro systém rovnic je stejně jako pro jednu rovnici, metodou druhého řádu. Metoda není globálně konvergentní, pokud však máme dostatečně dobrý odhad kořene, tak metoda konverguje rychle. Nejprve rozvineme funkce levých stran do řady: [1] [2] [4] [5]

.

(7)

Zavedeme matici derivací - Jacobián Jij:

,	(8)
.	(9)

Budeme uvažovat iterační proces:

.

(10)

Naším cílem je zvolit δx tak, aby . Zrovnice (9) po zanedbání posledního členu dostáváme podmínku:

.

(11)

Celý iterační proces tedy je:

.

(12)

Vztah je tedy podobný původní Newtonově metodě. Namísto dělení derivací nyní však musíme násobit inverzním Jacobiánem. Často se používá tzv. modifikovaná Newtonova metoda, kdy se inverzní Jacobiho matice spočítá pouze pro x0. [1] [2] [4] [5]

Hodnotu λk volíme obvykle rovnou jedné, testujeme však, zda došlo ke snížení reziduí, tj. zda platí (13). Není-li tato podmínka splněna, tak λk zmenšíme. [1]

(13)

Normální a modifikovanou Newtonovu metodu lze kombinovat tak, že ve větší vzdálenosti od řešení používáme metodu (10) - (11) a vblízkosti řešení metodu (12), která má u řešení prakticky stejnou rychlost konvergence jako normální Newtonova metoda. [1]

3 Zobecněná metoda sečen – Warnerovo schéma

V Newtonově metodě bylo nutno počítat derivaci funkcí fi. Jestliže výpočet derivací činí obtíže, potom můžeme použít zobecněné metody sečen, někdy nazývané Warnerovo schéma nebo Wolfeho metoda. [1]

Mějme dány n-rozměrné euklidovské prostory M a N a zobrazení f, které je definováno a spojité na nějaké podmnožině M‘ prostoru M a které tuto podmnožinu zobrazuje do N: . [1]

Předpokládejme, že uvnitř M existuje bod x* takový, že platí (nulový bod zvolen pro jednoduchost výkladu). Naším úkolem je tento bod nalézt, známe-li zobrazení f a neznáme-li (a není možno nalézt) zobrazení inverzní f -1. Zapíšeme si zobrazenou f ve tvaru:

.

(14)

Existuje-li inverzní zobrazení f -1, potom:

.

(15)

Neboli rozepsáno do složek:

(16)

Nechť mají tyto funkce vf(M‘) vlastní a spojité parciální derivace .

Označme si:

.

(17)

ZTaylorova rozvoje pro rovnice (16) plyne, zanedbáme-li členy vyššího než prvního řádu:

.

(18)

Získáme-li nyní pro n+1 různých prvků x1,x2,...,xn+1 M‘ obrazy y1,y2,...,yn+1 podle rovnice (14), dostaneme dosazením do vztahu (18) n soustav lineárních algebraických rovnic řádu n+1 pro neznámé Xi,X’ij; i=1,2,...,n; j=1,2,...,n: (19) pro i = 1,2,...,n. [1]

(19)

Mají-li soustavy (19) řešení (závisí na volbě x1,x2,...,xn+1), potom je možno pro každé i řešit tuto soustavu samostatně. Matice všech soustav (19) jsou, pro i=1,2,...,n, stejné, pouze pravé strany (v (19) levé) jsou rozdílné. Lze tedy vypočítat Xi, i=1,2,...,n, např. pomocí Gaussovy eliminace pro soustavu (n+1)×(n+1) – rovnice (19) – pro n různých pravých stran najednou. Dokonce lze aplikovat pouze přímý chod eliminace, jestliže proměnnou Xi zařadíme jako poslední, neboť proměnné X’ij nepotřebujeme (snad jen pro určení chyby při testování konce iterací). Toto spočtené Xi pro i=1,2,...,n potom přijmeme za novou aproximaci řešení x*. Jestliže nahradíme “nejhorší“ zbodů x1,x2,...,xn+1 tímto novým přiblížením, můžeme postup opakovat znovu. [1]

Je-li f lineární zobrazení, potom je první přiblížení Warnerova schématu přesným řešením. [1]

Konvergence závisí na volbě počátečních n+1 bodů. Je vhodné, jsou-li blízko řešení x*. Stane-li se během výpočtu, že matice soustavy je téměř singulární, je vhodné změnit některý volený bod xi a výpočet provést znovu. Někdy se stává, že nové přiblížení X je “horší“ než n+1 počátečních přiblížení. Podle zkušeností se však nic nestane, nahradíme-li “nejhorší“ zvolených x1,x2,...xn+1 ještě “horším“ X. Tento případ je označován jako lokální divergence. Jestliže však má tato divergence systematický charakter, je lépe změnit původně volené body x1,x2,...xn+1. Je výhodné, jestliže se mezi vyskytují čísla různých znamének. [1]

Pro případ dvou rovnic o dvou proměnných má Warnerovo schéma jednoduchý tvar. Podle Cramerova pravidla totiž platí (20). [1]

.

(20)

Závěr

Vtéto práci byly shrnuty nejpoužívanější metody numerické matematiky vmodelování a simulaci nelineárních systémů. Bylo popsáno řešení soustav nelineárních rovnic, které lze využít pro široký okruh případů jako řešení ustáleného stavu dynamického systému, resp. výpočet počátečních podmínek, výpočet složité chemické rovnováhy, náhrada parabolických nebo eliptických rovnic metodou konečných diferencí apod. Pro řešení těchto rovnic byla uvedena a popsána metoda prosté iterace, zobecněná Newtonova metoda a zobecněná metoda sečen. U všech zmíněných metod může být obtížné zajistit konvergenci.

Nejjednodušší metodou je metoda prosté iterace, ovšem tato metoda může být více náchylná kdivergenci než ostatní a také se nedá využít pro všechny soustavy rovnic. Newtonova metoda konverguje rychle, ovšem jen pokud máme dostatečně dobrý odhad kořene – metoda není globálně konvergentní. Jestliže výpočet derivací u Newtonovy metody činí obtíže, je lepší využít zobecněné metody sečen. Konvergence je ovšem u této metody pomalejší než u Newtonovy metody.

Poděkování

Tento článek vznikl za podpory Interní Grantové Agentury IGA/FAI/2014/006.

Seznam použité literatury

[1] KUBÍČEK, Milan, Miroslava DUBCOVÁ a Drahoslava JANOVSKÁ. Numerické metody a algoritmy. 2. oprav. vyd. Praha: Vydavatelství VŠCHT Praha, 2005, 188 s. ISBN 80-708-0558-7.
[2] VICHER, Miroslav. Numerická matematika. UJEP. Ústí n/L. 7. 1. 2003. ISBN 80-7044-516-5.
[3] JEŘÁBEK, Tomáš. Metody pro řešení soustav nelineárních rovnic [online]. 2009 [cit. 2013-11-27]. Diplomová práce. Masarykova univerzita, Přírodovědecká fakulta. Vedoucí práce: Ivanka Horová. Dostupné z: <http://is.muni.cz/th/77840/prif_m/>.
[4] RŮŽIČKOVÁ, IRENA a Rudolf HLAVIČKA. Numerické metody, Brno, 139s. Dostupné z: http://physics.ujep.cz/~jskvor/NME/DalsiSkripta/Numerika.pdf
[5] BAŠTINEC, Jaromír a Michal NOVÁK. Moderní numerické metody. Brno: 2007. 281s.