Řešení nelineárních rovnic

Řešení nelineárních rovnic Metody sečen (sekantová a regula falsi)

Máme dva body  x 1 a  x 2 mezi nimiž se nachází kořen. Nový bod  x 3 volíme v průsečíku spojnice bodů   x 1 , f  x 1  a   x 2 , f  x 2  (sečny) s osou x.  ERRBIS.PAS  k minulé hodině Sekantová metoda v následujícím kroku vždy používáme body  x 2 , x 3 . Ohraničení kořene tedy nemusí zůstat zachováno a není zaručena konvergence. V blízkosti kořene je ale rychlejší. Pro 1.618 konvergenci platí  lim ∣ k1∣=C∣ k∣ . k ∞

Regula falsi zachovává ohraničení kořene, v následujícím kroku tedy vezme  x 3 a takový z bodů x 1 , x 2 , aby platilo  f  x 3 ⋅f  x 1 0 nebo  f  x 3 ⋅f  x 2 0 . Konvergence je tedy zaručena. Metoda je pomalejší než sekantová, ale je stále superlineární (tzn. ∣ k1∣=C∣ k∣m , kde  m1 ).  Na obrázku nahoře, je naznačen problém, se kterým se mohou metody používající sečnu setkat. Pokud je interval velký a krajní body jsou daleko od kořene, může být konvergence těchto metod velmi pomalá. Brentova metoda založena na přepínání mezi metodou půlení intervalu a superlineární metodou. Pokud jsme daleko od kořene, používá se metoda půlení intervalu ke zmenšení intervalu ohraničujícího kořen. Jako superlineární metoda se používá metoda  Inverzní kvadratické interpolace.

Řešíme rovnici  f  x=0 s ohraničením kořene v intervalu   x 1 , x 2  . K funkci f  x =y uděláme funkci inverzní  x=g  y a tu nahradíme na tomto intervalu Lagrangeovým interpolačním polynomem druhého řádu (tzn. použijeme navíc jeden vnitřní bod intervalu   y 1 , y 2  například hodnotu ve středu intervalu   x 1 , x 2  , y 3 ). Položíme pak  x=L 2 0 (hledáme  x takové, že  f  x =y=0 ) a z této rovnice vyjádříme  x ­ přibližné řešení rovnice. Dále můžeme postupovat např. tak, že nové x zvolíme za jeden z krajních bodů intervalu, ohraničujícího kořen, a jako druhý zvolíme jeden z bodů  x 1 , x 2 tak, aby zůstalo ohraničení kořene zachováno a postupujeme stejně jako na začátku. Lagrangeův polynom na bodech  y1 , y 2 , y3 vyjádříme v bodě  y=0  y−y 2  y−y 3   y−y 1  y−y 3   y−y 1  y−y 2  x=L 2  y=x 1 x 2 x 3  y 1−y 2  y 1−y 3   y 2 −y 1  y 2 −y 3   y 3−y 1  y 3−y 2  x=L 2 0=x 1

y2 y3  y 1−y 2  y 1−y 3 

x 2

y1 y3  y 2 −y 1  y 2 −y 3 

Vztah se dá ještě rozepsat do podoby  x=x 3

x 3

y1 y 2  y 3−y 1  y 3−y 2 

P ( x 3 bylo zvoleno jako střed Q

intervalu   x 1 , x 2  ). R=

y3

, S=

y3

,  T =

y1

,  Q=T −1 R−1S−1 , y2 y1 y2 P=S [T  R−T  x 2 −x 3 −1−R x 3−x 1 ] (ze skript). Příklady v PASCALU DEMZBREN.PAS , DEMZB1.PAS.

Newton-Raphsonova metoda (metoda tečen) Využívá první derivaci funkce, hodí se pokud jsme schopni tuto derivaci rychle počítat. Řešíme  f  x =0 a pohybujeme se u okolí bodu  x ­ řešení rovnice. Pak můžeme  f  x nahradit Taylorovým rozvojem v okolí bodu  x=x i  f  xi f  x = f  x i = f  x i  f ' x i =0 . Z toho tedy plyne, že  =− . f ' x i  f  xi Proto volíme  x i1 =x i =x i − . Pro přesnost řešení se dá odvodit přibližný f ' x i  ' x i  2 f ' vztah  i1 ≃−1  a jde tedy o metodu kvadratickou, velmi rychlo v blízkosti 2 f ' x i 

kořene. Konvergence není u této metody zaručena.

Kořeny polynomů n n−1 Máme polynom  f  x =a n x a n−1 x a1 xa 0 =0 , kde  a n ≠0 .

Ohraničení kořene  ●

●

∣a 0∣

A , kde B∣a 0∣ an A=max {∣a n−1∣,∣a n−2∣,,∣a 0∣} a  B=max {∣a n∣,∣a n−1∣,,∣a1∣} .  pokud  a n 0 a  a n−k je první záporný koeficient v polynomu, platí pro

 všechny kořeny jsou v mezikruží 

≤∣x∣≤1



k všechna  x i 0 (kladné kořeny), že  x i R=1

A=max j , a 0∣a j∣ .

A , kde an

j

Druhý bod lze po substitucích využít i k dalším odhadům: ● ● ●

1 , odhad minimálního kladného kořene x  substituce y=−x omezí v absolutní hodnotě největší záporný kořen 1  substituce  y=− omezí v absolutní hodnotě nejmenší záporný kořen x  substituce  y=

Sturmova věta Sturmova posloupnost polynomů ja následující :  f 0  x = f  x  ,  f 1  x= f ' x  , f  x f i1  x =− zbytek po dělení  i−1 . Poslední člen posloupnosti  f k je f i x  konstantní. Např.  f  x =4 x 3 −2 x 2 −4 x−3=0 f 0  x =4 x 3−2 x 2 −4 x−3 f 1  x=3 x 2 −x−1 f 2  x=26 x−29 f 3  x=−1 Věta: Nechť aglebraická rovnice má pouze jednoduché kořeny. Potom počet reálných kořenů na intervalu  〈 , 〉 je roven  počtu znaménkových změn ve Sturmově posloupnosti

f 0 ,, f k . Pro násobné kořeny dostaneme  f k =0 . Pokud chceme použít Sturmovu větu, dělíme rovcnici polynomem  f k−1 a na novou rovnici už můžeme Sturmovu větu použít. K příkladu nahoře. f 3=−1 , tedy neexistují násobné kořeny.  x

−∞

0

2

∞

sgn f 0  x 

­

­

+

+

sgn f 1  x 

+

­

+

+

sgn f 2  x 

­

+

+

+

sgn f 3  x 

­

­

­

­

n zmen

2

2

1

1

Počet znaménkových změn v bodech  −∞ a  ∞ je jedna. Zadaný polynom má tedy na tomto intervalu jeden reálný kořen. Totéž platí i o intervalu  〈0 , 2〉 . Hledání kořene Mullerova metoda Opět v bodech  x i , x i−1 , x i−2 interpolujeme zadaný polynom polynomem kvadratickým  Lagrangeovým s ekvidistantními uzly. L 2  x =y i−2 t=

x−x i x i −x i−1

t−3t−4 t−2t−3 −y i−1 t−2t−4y 2 , zde volíme 2 2

.

Hledáme  L 2  x =0= A t 2 B tC . Na tuto rovnici nejdříve použijeme substituci 1 u= a dostaneme  AB uC u 2 =0 s kořeny t

[

2C −B± B 2 −4 A C .  x=x i  x i −x i−1 t=x i  x i −x i−1  2 2C B±  B −4 A C volíme + nebo – tak, aby byla maximální absolutní jmenovatele.

u1,2 =

]

, kde

Postup pro počítání koeficientů  A ,  B , C viz. slidy.

Laguerrova metoda Polynom  P n  x= x−x 1  x−x 2 ⋯ x−x n  má logaritmus ln∣P n  x∣=ln∣x−x 1∣⋯ln∣x−x n∣ . P 'n d ln P n  x  1 1 G= = = ⋯ Definujeme , Pn dx x−x 1 x−x n

[ ]

H=

P 'n Pn

2

P ''n d 2 ln P n  x  1 1 − =− = ⋯ 2 2 Pn dx  x−x 1   x−x n 2

Nyní položíme  a=x−x 1 a pro ostatní kořeny přibližně  b~x−x i . Pak  1 n−1 1 n−1 G=  ,  H = 2  2 a pro  a máme tedy vztah  a b a b n a= . G±  n−1nH −G 2  Znaménko ve výrazu pro  a opět volíme tak, aby byl jmenovatel v absolutní hodnotě největší. Můžeme dostat komplexní mezivýsledky. Hledání dalších kořenů polynomů Sníží se stupeň polynomu vydělením. 

Soustavy nelineárních rovnic

Obecně velmi obtížné, pokud je to možné, převedeme na úlohu hledání extrému.  −∂ V x  f x =0 , pokud je  f i = pro všechna  i , hledáme extrém potenciálu. ∂ xi Prostá iterace  x  , tzn.  Soustavu  f x =0 převedeme na tvar  x = f 1  x 1 ,, x n =0 ⋮ f n  x 1 ,, x n =0



x 1 =1  x 1 ,, x n  . ⋮ x n =n  x 1 ,, x n 

Iterační vzorec pro hledání kořene je pak  x k1=  x k  .  bylo kontrahující na okolí Postačující podmínka konvergence je, aby zobrazení   řešení.   v okolí řešení, lze podmínku zapsat Pokud existují všechny parciální derivace     x ∣≤q1 , kde  J je Jakobián. ∣J  PRMNL.PAS Newton­Raphsonova metoda Podobná jako v 1D.  x k1=x  k−[ Jf x k ]−1⋅f x k  . Při dobrém odhadu intervalu metoda konverguje. DEMNEWT.PAS, DEMNEWT2.PAS, DEMNEWTA.PAS