Projekt: Inovace výuky optiky se zaměřením na získání
experimentálních dovedností
Registrační číslo: CZ.1.07/2.2.00/28.0157
Numerické metody a programování
Lekce 7
Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem
České republiky.
Řešení (soustav) nelineárních rovnic
hledáme řešení x problému
f x  = 0
strategie: ● odhad řešení
● iterační proces postupného zpřesňování řešení ● výpočet skončen pokud je splněno kritérium přesnosti
Kořeny funkce (1D problém)
kořen je uzavřen na intervalu a , b  pokud f a  a f b  mají opačná znaménka
●
kořen existuje pokud je funkce spojitá
●
nemusí být změna znaménka v okolí dvojnásobného kořene
●
patologický případ: uzavření singularity
●
počáteční interval je zvětšován až dojde k uzavření kořene
Metody nevyžadující derivace
metoda bisekce
●
interval uzavírající kořen je rozpůlen
●
středový bod intervalu nahradí krajní bod stejného znaménka
●
tolerance  n 1 = n /2 (lineární konvergence)
●
konverguje k případné singularitě uvnitř intervalu
metoda sečen (regula falsi)
●
rychlejší konvergence pro dobře se chovající funkce (superlineární)
●
lineární aproximace funkce v okolí kořene
●
metoda sečen konverguje rychleji ale nové intervaly nemusí uzavírat kořen
●
příklad funkce obtížné pro obě metody:
Riddersova metoda
●
odstraňuje “ohyb” funkce pomocí exponenciálních faktorů
f  x 1   f x 2  e
2
2Q
= f x 3 e Q Q
●
aplikace metody regula falsi na hodnoty f x 1 , f x 3 e , f  x 2 e
●
zachovává uzavření kořene
●
superlineární konvergence (řád  2 )
●
robustní
2Q
Brentova metoda
●
fit (interpolace) třech bodů inverzní kvadratickou funkcí x = P x  (Lagrange)
●
hodnota v y = 0 dává nový odhad
x = b  P /Q
P = S [T R −T c −b  − 1 −R b −a ],
R ≡ f b /f c ,
S ≡ f b /f a  ,
Q = T −1 R −1 S −1 
T ≡ f a /f c 
●
v případě problému (nový odhad je mimo uzavírací interval nebo pomalé zmenšování intervalu) je použit jeden krok bisekce
●
kombinuje jistotu bisekce s rychlostí kvadratické metody
Newtonova – Raphsonova metoda využívající derivace
rozvoj funkce v řadu
f x   = f  x   f ' x    f ' '  x 
2
⋯
2
požadujeme
f x   = 0
pro malé  a dobře se chovající funkce  =−
●
f x 
'
f x 
(extrapolace derivace)
může selhat (např. výskyt lokálních maxim/minim v blízkosti kořene):
●
jiný příklad selhání: iterace v cyklu
●
hlavní výhoda: velmi rychlá konvergence v blízkosti kořene
n 1 = −2n
''
f x 
2 f ' x 
●
počet platných cifer se každým krokem přibližně zdvojnásobí
●
možno kombinovat s bisekcí k dosažení lepší globální konvergence
Kořeny polynomů
●
problémy s uzavíráním kořenů
●
pomalá konvergence iteračních metod kvůli násobnosti kořenů
Laguerrova metoda
●
najde jeden kořen
●
zjednodušení polynomu (faktorizace): P  x  =  x −r  Q  x 
●
nakonec iterační vyhlazení kořenů
P n  x  =  x −x 1 x −x 2 ⋯ x −x n 
derivace
'
Pn
d l n∣P  x ∣
1
1
1
=

 ⋯
=
≡G
dx
x −x 1
x −x 2
x −x n
Pn
2
−d l n∣P  x ∣
d x2
předpoklad:
=
1
 x −x 1 2

1
x −x 2 2
 ⋯
1
 x −x n 2
=
2
 
P 'n
Pn
−
P 'n '
Pn
≡H
x −x 1 = a ,
x −x i = b , i = 2 ,3 , 
dostaneme
1
n −1

=G
a
b
1
n −1
 2 =H
2
a
b
získáme odhad kořene x −a
a =
n

G ± n −1 n H − G 2 
opakujeme dokud není a dostatečně malé
postupy založené na vlastních číslech
●
vlastní čísla matice A  kořeny charakteristického polynomu P  x  = d e t[A −x I ]
●
výpočet kořenů polynomu převeden na výpočet vlastních čísel speciální matice
Nelineární systémy rovnic
●
chybí efektivní metody řešení soustav více nelineárních rovnic
●
obvykle je nutno něco vědět o existenci a poloze kořenů
př. kořeny soustavy
f x , y  = 0
g x , y  = 0
Newtonova­Raphsonova metoda pro soustavy rovnic
soustava
F i x 1 , x 2 ,, x N  = 0 , i = 1 , 2 ,, N
Jacobián
J ij ≡
∂F
∂x
i
j
rozvoj v okolí x
F x   x  = F x   J ⋅ x
požadujeme F x   x  = 0
dostaneme
J ⋅ x = −F
LU dekompozice
nový odhad kořene: x   x
●
proces se opakuje
●
kontrola konvergence
●
problém s globální konvergencí
vylepšení globální konvergence
●
●
●
požadujme, aby  x vždy zmenšovalo f ≡∣F ∣2 = F ⋅F /2
 x je směr poklesu f : ∇ f⋅ x = F ⋅J ⋅−J −1⋅F  = −F ⋅F  0
postup:
−
provést plný krok a zkontrolovat, zda došlo zmenšení hodnoty f – kvadratická konvergence v blízkosti kořene
−
pokud f roste, zkrátit délku kroku
Download

Numerické metody a programování Lekce 7