Metody Numeryczne w Budowie
Samolotów/Śmigłowców
Wykład I
dr inż. Tomasz Goetzendorf-Grabowski
([e-mail])
Dęblin, 11 maja 2009
1
Organizacja wykładu
" 5 dni x 6 h = 30 h
" propozycja zmiany:

6 h + 3 x 7 h + 3 h = 30 h
" 11.05  6h
" 18.05, 25.05, 1.06  7h (8:15  15)
" 8.06  3h (8:15  11)
" Wykład + ćwiczenia (baza, znajomość
pakietów)
" zaliczenie  projekt (aerodynamika lub
stateczność)
2
Zawartość wykładu (1/4)
" Wstęp

pojęcie metod numerycznych

definicje błędów
" Obliczanie wartości funkcji  błędy
 algorytm Hornera
" Aproksymacja vs. Interpolacja

teoria

praktyczne wykorzystanie

pakiety
3
Zawartość wykładu (2/4)
" Interpolacja wielomianami
" Metody przybliżone znajdowania zer
funkcji nieliniowej

zbieżność

Metoda Newtona
4
Zawartość wykładu (3/4)
" Metody całkowania
" Rozwiązywanie równań różniczkowych
" Wartości i wektory własne macierzy
" Układy równań liniowych

dekompozycja macierzy
5
Zawartość wykładu (4/4)
" zastosowanie w aerodynamice

metody potencjalne (pakiet PANUKL)

model Eulera
" zastosowanie w badaniach własności lotnych

modele liniowe  stateczność

modele nieliniowe  symulacja

metody numeryczne vs. siła obliczeniowa komputerów
" programy międzynarodowe - SimSAC
6
Literatura
" Stoer J., Bulirsch R., Introduction to Numerical Analysis, Springer-
Verlag, New York 1983 (wyd. polskie: Wstęp do analizy
numerycznej, PWN, Warszawa 1987)
" Björck Å., Dahlquist G., Numerical Methods, Practice Hall, 1974
(wyd. polskie: Metody numeryczne, PWN, Warszawa 1983)
" Fortuna Z., Macukow B., WÄ…sowski J., Metody Numeryczne, WNT,
Warszawa 1982
" Krupowicz A., Metody numeryczne zagadnień początkowych równań
różniczkowych zwyczajnych, PWN, Warszawa 1986
" Ralston A., A First Course in Numerical Analysis, McGraw-Hill, Inc,
London 1965 (wyd. polskie: Wstęp do analizy numerycznej, wyd.III,
PWN 1983)
" Press W.H., Vetterling W.T., Teukolsky S.A., Flannery B.P.,
Numerical Recipes in FORTRAN - The Art of Scientifing Computing,
2nd Edition, Cambridge University Press, 1992
" Forsythe G.E., Malcolm M.A., Moler C.B., Computer Methods for
Mathematical Computation, Prentice-Hall, Englewood Cliffs 1977
7
Pojęcia wstępne
" Metody numeryczne (metody obliczeniowe,
przybliżone,  Numerical Methods )

skończone
" dokładne w sformułowaniu teoretycznym (schemat
Hornera, metoda eliminacji Gausa, itp..)
" przybliżone

nieskończone
" metody kolejnych przybliżeń, metody iteracyjne
8
Pojęcia wstępne  błędy
" Błędy danych
" Błędy reprezentacji liczb
" Błędy zaokrągleń
" Błędy metody
" Przenoszenie się błędów zaokrągleń
" Stabilność algorytmów
9
Stabilność - przykład
10
Stabilność - przykład
11
Obliczanie wartości funkcji
" Jeżeli bezpośrednie obliczenie wartości funkcji
jest niemożliwe lub zbyt pracochłonne, powstaje
zagadnienie aproksymacji, czyli najlepszego w
sensie nałożonych wymagań przybliżenia funkcji
" Funkcję f(x) można rozwinąć w zbieżny szereg
funkcyjny
"
f (x) H" aiui (x) dla x " < a,b >
"
i= k
12
Schemat Hornera do obliczania wartości wielomianu
13
Schemat
Hornera do
obliczania
wartości
wielomianu
14
Aproksymacja wielomianem (1/12)
Aproksymacja wielomianem jest jednÄ… z najbardziej efektywnych
technik znajdowania minimum lub zerowania siÄ™ funkcji jednej
zmiennej.
UWAGA !
Aproksymacja funkcji o dużej nieliniowości może powodować
powstawanie dużych rozbieżności pomiędzy rzeczywistym
przebiegiem, a funkcjÄ… aproksymujÄ…cÄ…
15
Aproksymacja wielomianem (2/12)
Generalne zasady:
-
Oszacowanie położenia punktu w którym badana funkcja osiąga
minimum;
-
Aproksymacja funkcji wielomianem w tym punkcie;
-
Porównanie rozwiązania ścisłego i rozwiązania za pomocą
wielomianu aproksymujÄ…cego;
-
Jeżeli różnica pomiędzy rozwiązaniami jest w granicach
zakładanego błędu to można powiedzieć że aproksymacja
została dokonana poprawnie;
16
Aproksymacja wielomianem (3/12)
Przykład: Znalez
ć minimum funkcji opisanej wzorem
;
Znajdujemy pierwszÄ… pochodna danej funkcji
;
Zakładamy aproksymacje funkcji za pomocą wielomianu drugiego
rzędu
;
Znajdujemy pierwszÄ… pochodna wielomianu aproksymujÄ…cego
;
17
Aproksymacja wielomianem (4/12)
Zakładamy punkty na podstawie których powstanie wielomian:
np. X=0 i X=0,5
Powstaje układ równań z którego wyznaczamy współczynniki
wielomianu
Wartość pochodnej w punkcie
X=0 wyznaczona z równania
oryginalnego
Po rozwiązaniu układu równań otrzymujemy:
18
Aproksymacja wielomianem (7/12)
W rezultacie otrzymujemy wielomian aproksymujÄ…cy
;
Przy założeniu aproksymacji wielomianem trzeciego stopnia
otrzymujemy równanie
;
19
Aproksymacja wielomianem (8/12)
Dokładne rozwiązanie
Aproksymacje funkcji F(X)
Wielomian 2-go stopnia
za pomocą wielomianów
Wielomian 3-go stopnia
Porównanie dwóch
zastosowanych wielomianów
o różnym stopniu
20
Aproksymacja wielomianem (9/12)
Porównanie aproksymacji przy zastosowaniu różnego
stopnia wielomianu
Wartości funkcji
Współrzędne punktu minimum aproksymującej
w minimum
21
Aproksymacja wielomianem (10/12)
Dane niezbędne do przeprowadzenia aproksymacji
Zadajemy wartosci
w punktach 1,2,3,4
oraz pochodna w
punkcie 1 (wszystko
w zaleznosci od typu
aproksymacji)
3
2
F = a0 + a1 X + a2 X + a3 X
22
Aproksymacja wielomianem (11/12)
UWAGI DO APROKSYMACJI WIELOMIANOWEJ:
Øð
Interpolacja pomiędzy dwoma punktami jest lepszym
rozwiązaniem niż ekstrapolacja;
Øð
Korzystne jest rozpocząć aproksymację stosując wielomian
niższego stopnia (mniejsza liczba niezbędnych danych), a
następnie zastosować wielomian wyższego rzędu uzyskując
poprawÄ™ wyniku; (bazowanie na poprzednich rozwiÄ…zaniach)
Øð
Użycie pochodnych wyższego rzędu nie gwarantuje
zwiększenia dokładności obliczeń;
23
Aproksymacja wielomianem (12/12)
WNIOSKI:
Aproksymacja wielomianem takiego stopnia
jaki jest możliwy stosując minimum
dostępnych danych. Następnie stopniowe
zwiększanie stopnia wielomianu (bazując na
wynikach uzyskanych za pomocÄ… wielomianu
niższego stopnia) w celu poprawy rozwiązania.
24
Współczynniki Wielomianu (1/7)
Definicja współczynników wielomianu w zależności od stopnia
wielomianu i liczby punktów użytych do aproksymacji
Wzór ogólny wielomianu:
2 3
F(X)= a0 + a1 X + a2 X + a3 X
Aproksymacja liniowa jedno-punktowa:
a3 = 0
Dane:
(X1 , F1 , F1')
a2 = 0
a1 = F1'
a0 = F1 - F1'X1
25
Współczynniki Wielomianu (2/7)
Aproksymacja liniowa dwu-punktowa:
Dane: (X1 , F1) ,(X2 , F2)
a3 = 0
a2 = 0
F2 - F1
a1 =
X2 - X1
a0 = F1 - a1X1
26
Współczynniki Wielomianu (3/7)
Aproksymacja dwu-punktowa równaniem kwadratowym :
Dane:
(X1 , F1 , F1') ,(X2 , F2)
a3 = 0
( F2 - F1) /( X2 - X1) - F1'
a2 =
X2 - X1
a1 = F1' - 2a2X1
2
a0 = F1 - a1X1 - a2X1
27
Współczynniki Wielomianu (4/7)
Aproksymacja trzy-punktowa równaniem kwadratowym :
Dane: (X1 , F1) ,(X2 , F2) ,(X3 , F3)
a3 = 0
( F3 - F1) /( X3 - X1) - ( F2 - F1) /( X2 - X1)
a2 =
X3 - X2
F2 - F
a1 = - a2( X1 + X2)
X2 - X1
2
a0 = F1 - a1X1 - a2X1
28
Współczynniki Wielomianu (5/7)
Aproksymacja trzy-punktowa równaniem 3-go stopnia :
Dane:
(X1 , F1, F1') ,(X2 , F2) ,(X3 , F3)
F3 - F1 F2 - F1 F1'
a3 = - +
( X2 - X1)( X3 - X1)
( X3 - X2)( X3 - X1)2 ( X3 - X2)( X3 - X1)2
( F2 - F1) /( X3 - X1) - F1'
a2 = - a3(2X1 + X2)
X2 - X1
2
a1 = F1' - 2a1X1 - 3a3X1
2 3
a0 = F1 - a1X1 - a2X1 - a3X1
29
Współczynniki Wielomianu (6/7)
Aproksymacja cztero-punktowa równaniem 3-go stopnia :
( )
(X1 , F1) ,(X , F2) , X3 , F3 , (X , F4)
Dane: 2 4
30
Współczynniki Wielomianu (7/7)
Aproksymacja cztero-punktowa równaniem 3-go stopnia
(cd):
( )
(X1 , F1) ,(X , F2) , X3 , F3 , (X , F4)
Dane: 2 4
31
Zera wielomianu (1/8)
Wyznaczenie punktu X w którym funkcja F(X)=0
~
2 3
F(X)= a0 + a1 X + a2 X + a3 X = 0
Równanie reprezentuje wielomian trzeciego stopnia
32
Zera wielomianu (2/8)
Aproksymacja liniowa :
a3 = 0
a2 = 0
~
F(X)= a0 + a1 X
- a0
*
RozwiÄ…zaniem jest jeden
X =
pierwiastek
a1
33
Zera wielomianu (3/8)
Aproksymacja równaniem kwadratowym :
~
2
a3 = 0
F(X)= a0 + a1 X + a2 X
b = a12 - 4a0a2
b > 0 - dwa pierwiastki rzeczywiste
b = 0 - jeden pierwiastek podwójny
- a1 + b
X1* =
RozwiÄ…zania oczekiwane
2a2
b < 0 - rozwiÄ…zanie w postaci liczb
zespolonych
- a1 - b
X2* =
RozwiÄ…zanie pomijane
34
2a2
Zera wielomianu (4/8)
Aproksymacja równaniem 3-go stopnia :
~
2 3
F(X)= a0 + a1 X + a2 X + a3 X
Aproksymacja dajÄ…ca wielokrotne pierwiastki
35
Zera wielomianu (5/8)
Aproksymacja równaniem 1-go stopnia :
Metoda Newton a wyznaczania zera wielomianów wyższych stopni
Metoda pierwszego rzędu wykorzystująca funkcję oraz jej pochodną
(
F H" F0 + F0' X - X0 )
Gdzie:
2 3
XO  wartość początkowa;
F0 = a0 + a1 X0 + a2 X0 + a3X0
2
F0' = a1 + 2a2 X0 + 3a3 X0
FO  wartość funkcji w punkcie XO;
F0  wartość pochodna w punkcie XO;
36
Metoda Newtona  Raphsona (6/8)
Jest to połączenie metody iteracyjnej z lokalną aproksymacją
za pomocÄ… stycznej
df
= g(x)
dx
y = g(x0)x + C(x0)
dla x = x0 mamy
g(x0)x0 + C(x0) = f (x0)
C(x0) = f (x0) - g(x0)x0
dla x = x1 mamy
g(x0)x1 + C(x0) = 0
C(x0) f (x0)
x1 = - = x0 -
g(x0) g(x0)
Jeżeli x0 jest dobrym przybliżeniem początkowym,
to proces Newtona-Raphsona jest bardzo
f (xi )
37
xi+ 1 = xi -
szybko zbieżny
g(xi )
Zera wielomianu (7/8)
Aproksymacja równaniem 1-go stopnia :
F0 + F0'( X - X0) = 0
F0
Gdzie:
X1 = X0 -
X1  pierwsza iteracja
F0'
rozwiÄ…zania;
FN - 1
XN  N-ta iteracja
X = X -
N N - 1
' rozwiÄ…zania;
FN - 1
38
Zera wielomianu (8/8)
Algorytm wyznaczania pierwszego
 zera wielomianu n-tego rzędu
przy użycie metody Newton a
n  stopień wielomianu
Kmax= maksymalna liczba iteracji
39
Zadanie iteracyjne (1/2)
Rozważmy metodę iteracyjną na przykładzie
prostego równania nieliniowego x = F(x), które
można graficznie zinterpretować jako
3
X
F(x)
2
y
1
0
0 1 2 3
X=Ä…
40
X
Zadanie iteracyjne (2/2)
Zakładamy x0 i budujemy ciąg:
x1 = F(x0 ) ; x2 = F(x1) ; ... xn+ 1 = F(xn )
Ciag jest zbiezny do Ä… gdy Ä… = F(xn ) = F(Ä… )
lim
n "
Zauważmy, że każde równanie nieliniowe można doprowadzić
do postaci x=F(x). Niech np. będzie równanie G(x)=0.
Możemy wtedy podstawić x = G(x) + x = F(x)
41
Algorytmy zbieżne (1/2)
2
0 < Åš (¾ ) < 1
F(xi)
42
Algorytmy zbieżne (2/2)
2
- 1 < Åš (¾ ) < 0
43
Algorytmy rozbieżne (1/2)
2
Åš (¾ ) > 1
44
Algorytmy rozbieżne (2/2)
2
Åš (¾ ) < - 1
45
Kryterium zbieżności
2
Niech xn+ 1 - xn = F(xn ) - F(xn- 1) = F (¾ )(xn - xn- 1)
n
Z twierdzenia
o wartości średniej
Bo kolejny przyrost xn-xn-1
musi być mniejszy od
poprzedniego
xn+ 1 - xn
2
= F (¾ ) < 1
Mamy więc:
n
xn - xn- 1
2
F (¾ ) < 1
Tak więc zbieżność jest zapewniona, gdy w każdym punkcie
n
xn , x1 , x2 , x3 ,..., xn
przedziału otoczenia ą, które zawiera
46
Przykład-obliczenie pierwiastka kwadratowego (1/4)
x2 = c
Algorytm nr 1 - rozbieżny
x = x2 + x - c F(x) = x2 + x - c
Niech c = 2 ; x0 = 1.5
x1 = F(1.5) = 2.25 + 1.5 - 2 = 1.75
x2 = F(1.75) = 1.752 + 1.75 - 2 = 2.8125
x3 = F(2.8125) = 8.7226563
Proces jest rozbieżny, gdyż:
dF
= 2x + 1> 1 gdy x > 0
dx
47
Przykład-obliczenie pierwiastka kwadratowego (2/4)
x2 = c
Algorytm nr 2 - niezbieżny
c
x =
x
Niech c = 2 ; x0 = 1.5
2
x1 = = 1.33333
x
2
x2 = = 1.5
1.33333
2
Tak więc nie w każdym punkcie
x3 = = 1.33333
x
otoczenia Ä… pochodna dF/dx jest
dF
= - 1.1250
mniejsza od 1
dx
x= 1.33333 ; c= 2
48
Przykład-obliczenie pierwiastka kwadratowego (3/4)
x2 = c
Algorytm nr 3 - zbieżny
x2 + c 1 2
x2 = c 2 x2 = x2 + c x = = x +
2 x 2 2x
1 c
ëÅ‚ öÅ‚
F(x) = x +
ìÅ‚ ÷Å‚
2 x
sqrt 2 = 1.4142136
íÅ‚ Å‚Å‚
Niech c = 2 ; x0 = 1.5
1 2
ëÅ‚ öÅ‚
x1 = 1.5+ = 1.4166667
ìÅ‚ ÷Å‚
2 1.5
íÅ‚ Å‚Å‚
1 2
ëÅ‚ öÅ‚
x2 = 1.4166667 + = 1.4142157
ìÅ‚ ÷Å‚
2 1.4166667
íÅ‚ Å‚Å‚
dF 1 c
ëÅ‚ öÅ‚
= 1-
ìÅ‚ ÷Å‚
dx 2 x2
íÅ‚ Å‚Å‚ 49
Przykład-obliczenie pierwiastka kwadratowego (4/4)
x2 = c
Algorytm nr 3  zbieżny - cd
x 1 Sqrt(2) 1.5 2
dF/dx -1/2 0 0.0555 0.25
Powyższy algorytm jest podstawą
obliczania pierwiastków
kwadratowych
we wszystkich komputerach
Czyli jest to przypadek nr I
50