Mariusz PYRZ
SIMR (PW), Instytut Pojazdów
Metody numeryczne w mechanice
Rozwiązywanie układów równań nieliniowych
4.
Układ równań nieliniowych
f1(x1, x2,..., xn ) = 0
Układ n równań
f2 (x1, x2,..., xn ) = 0
z n niewiadomymi
ï"
x1, x2, ..., xn
(funkcje f1, f2, ..., fn sÄ… znane).
fn (x1, x2,..., xn ) = 0
f1(x1, x1
L L O L
Wprowadzamy
Mf (x1,x2,..., xn )O Mx P M0O
P
x2 ,..., xn)
2 2
M P M P M0P
P
wektory f (x) = x = 0 =
M ï" M M
kolumnowe
Mf (x1, x2 ,..., xn)P Mï"P Mï"0P
P P P
N n Q NxnQ N Q
Układ równań mo\
na wtedy zapisać jako f(x)=0 .
2
M.Pyrz Metody numeryczne w mechanice  Układy równań nieliniowych 10.2011
Rozwiązywanie układu równań nieliniowych
T
* * *
Rozwiązanie układu równań f(x)=0 oznaczmy jako
x* = x1 x2ï"xn
f(x*)=0
Metoda kolejnych przybli\
eń
T
0 0 0
x0 = x1 x2ï"xn
WychodzÄ…c z poczÄ…tkowego wektora
budujemy ciąg wektorów przybli\
ajÄ…cych rozwiÄ…zanie xi (i  numer iteracji).
Dla i dÄ…\
ącego do nieskończoności ciąg xi dą\
y do granicy x*.
3
M.Pyrz Metody numeryczne w mechanice  Układy równań nieliniowych 10.2011
Przykład: metoda Newtona
Stosowana zwykle w celu zwiększenia dokładności rozwiązań wyznaczonych
innymi metodami (poniewa\
napotykamy trudności w dobrym oszacowaniu
wektora poczÄ…tkowego x0).
Zbie\
ność ma charakter kwadratowy, macierz Jacobiego (drugich
pochodnych czÄ…stkowych) jest przeliczana na ka\
dym kroku iteracyjnym.
Oznaczenie: xi to i-ta aproksymacja wektora rozwiązań
Oznaczenie: xi to i-ta aproksymacja wektora rozwiązań
xi+1 = xi- J-1(xi) f(xi)
i i i i
L O L O
x1 f1(x1, x2,ï", xn)
M P M P
i i i i
x2 f2(x1, x2ï", xn )
,
M P M P
xi = f(xi ) =
M P M P
ï" ï"
M P M P
i i i i
xn fn(x1, x2ï", xn )
,
N Q N Q
4
M.Pyrz Metody numeryczne w mechanice  Układy równań nieliniowych 10.2011
Metoda Newtona
Macierz Jacobiego układu równań nieliniowych określonego za pomocą funkcji
f1,f2, ...,fn
L O
"f1(xi ) "f1(xi ) "f1(xi )
ï"
M P
"x1 "x2 "xn
M P
"f2(xi ) "f2(xi ) "f2 (xi )
M P
L O
"f(xi )
ï"
J(xi ) = = M P
M P
"x1 "x2 "xn
"xj
M P M P
N Q
N Q
ï" ï" ï" ï"
ï" ï" ï" ï"i
M P
M P
" " "
"fn(xi ) "fn(xi ) "fn (x )
M P
M P
ï"
M P
"x1 "x2 "xn
N Q
OznaczajÄ…c przez "xi wektor « poprawiajÄ…cy rozwiÄ…zania mo\
na zapisać
"xi = J-1(xi) f(xi).
Wektor "xi jest obliczany w ka\
dej iteracji rozwiązując układ równań liniowych
J(xi) "xi = f(xi)
5
M.Pyrz Metody numeryczne w mechanice  Układy równań nieliniowych 10.2011
Metoda Newtona - algorytm
T
0 0 0
Wybrać początkowe przybli\
enie
x0 = x1 x2ï"xn
Dla ka\
dego przybli\
enia xi+1, i=0,1,2,&
- Oblicz wartości wektora funkcji f(xi) w punkcie xi
- Oblicz składowe macierzy Jacobiego J(xi) w punkcie xi
- Oblicz wektor poprawek "xi korzystając z układu równań liniowych
- Oblicz wektor poprawek "xi korzystając z układu równań liniowych
J(xi) "xi = f(xi)
- Oblicz (i+1) te przybli\
enie rozwiÄ…zania xi+1 = xi-"xi
Kryterium zatrzymania :
Przykład 1
|| xi+1 || - || xi || < µ.
6
M.Pyrz Metody numeryczne w mechanice  Układy równań nieliniowych 10.2011
Metody rozwiązywania układów równań nieliniowych
Metody quasi-newtonowskie
StanowiÄ… modyfikacjÄ™ metody Newtona.
Macierz Jacobiego jest aktualizowana co p iteracji (p jest wybierane przez
u\
ytkownika). Prowadzi to do zmniejszenia liczby wykonywanych operacji
ale tracona jest kwadratowa zbie\
ność.
Metoda siecznych
Uogólnienie metody siecznych (patrz rozwiązywanie równania
nieliniowego) na przypadek n równań nieliniowych
Rysunek 1
7
M.Pyrz Metody numeryczne w mechanice  Układy równań nieliniowych 10.2011
Rozwiązywanie układów równań nieliniowych
Metody wykorzystujÄ…ce techniki minimalizacji
Metody iteracyjne mogą bazować na technikach minimalizacji
« dÅ‚ugoÅ›ci wektora funkcji fi(xi) :
n
Q(x) = Q(x1, x2,ï", ) = fi 2(x1, x2,ï", ) min
ï"xn ï"xn
"
1 2 n " i 1 2 n
i=1
Funkcja Q(x) osiąga minimum równe zero w punkcie x który jest
rozwiązaniem układu równań nieliniowych f(x)=0.
Wykorzystać mo\
na np. metody spadku, gradientów sprzę\
onych, &
8
M.Pyrz Metody numeryczne w mechanice  Układy równań nieliniowych 10.2011
Normy wektorowe i macierzowe
normy wektorowe
1/ 2
n n
îÅ‚ Å‚Å‚
x = xi norma 1 x = xi2 śł norma euklidesowa
" "
ïÅ‚
1 2
i=1 ðÅ‚ i=1 ûÅ‚
1/ p
n
îÅ‚ Å‚Å‚
x = sup xi norma nieskonczona x = xip śł
"
ïÅ‚
" p
1d"id"n
ðÅ‚ i=1 ûÅ‚
normy macierzowe (stowarzyszone z normami wektorowymi)
n
Ax
Ax
L" aij O
1
A = sup Ax = sup A = sup = sup
M P
1
x x
x `"0 x `"0 1d" jd"n
x"Cn
Ni=1 Q
1
x =1
n
Ax Ax L" aij O
1/2
2 "
A = sup = Á(A*A) A = sup = sup
M P
2 "
x x
x `"0 x `"0 1d"id"n
j=1
N Q
2 "
9
M.Pyrz Metody numeryczne w mechanice  Układy równań nieliniowych 10.2011