METODY
NUMERYCZNE
Metody Numeryczne
Wykład 2/1
dr inż. Mirosław Dziewoński
e-mail:
Pok. 151
METODY
NUMERYCZNE
Metody Numeryczne
Wykład 2/1
dr inż. Mirosław Dziewoński
e-mail:
Pok. 151
Metody Numeryczne
Wykład 2/2
Aproksymacja funkcji
jednej zmiennej
Aproksymacja funkcji jednej zmiennej
Wykład 2/3
Dana jest
funkcja jednej zmiennej
gdzie
( )
y
f x
[ , ]
x
a b
Funkcja ta podana jest w postaci
wzoru analitycznego
lub w postaci
zbioru punktów
1
1
2
2
( )
,
(
)
, ... ,
(
)
n
n
f x
y
f x
y
f x
y
Celem aproksymacji
jest dobór takiej funkcji
0
( ,
, ... ,
),
[ , ]
k
F x p
p
x
a b
aby w sensie przyjętego kryterium funkcja ta możliwie
dokładnie
odtwarzała przebieg funkcji
f (x).
Aproksymacja funkcji jednej zmiennej
Wykład 2/4
Jeżeli funkcja dana jest w postaci dyskretnej (zbioru punktów) to
aproksymację nazywamy
punktową
, a jeżeli w postaci wzoru
analitycznego, to mówimy o
aproksymacji integralnej
.
Aproksymacja funkcji jednej zmiennej
Wykład 2/5
Kryteria aproksymacji punktowej dla funkcji jednej zmiennej konstruuje
się tak, aby
zminimalizować
różnice pomiędzy wartościami danej funkcji
f (x)
w punktach
(x
i
, y
i
)
,
i = 1, 2 ,…, n
a wartościami funkcji
F (x, p
0
, …, p
k
)
w tych samych punktach.
Wprowadzamy pojęcie odchyłki:
0
( ,
, ... ,
)
min ,
1, 2,...,
i
i
k
i
F x p
p
y
i
n
Należy tak dobrać parametry
p
0
, …, p
k
wzoru empirycznego, aby
spełnione było kryterium minimalizacji odchyłki.
Aproksymacja funkcji jednej zmiennej
Wykład 2/6
Aproksymacja funkcji jednej zmiennej
Wykład 2/7
W literaturze można spotkać następujące
kryteria minimalizacji
odchyłek
• metoda wybranych punktów,
• metoda średnich,
• metoda sumowania bezwzględnych wartości,
•
metoda najmniejszych kwadratów.
Metoda najmniejszych kwadratów
Wykład 2/8
Kryterium tej metody polega na takim doborze współczynników funkcji
F (x, p
0
, …, p
k
)
, aby
2
2
0
0
1
1
(
, ... ,
)
( ,
, ... ,
)
min
n
n
k
i
i
k
i
i
i
S p
p
F x p
p
y
Aproksymacja liniowa funkcji jednej zmiennej
Wykład 2/9
Rozpatrujemy zbiór punktów
1
1
2
2
( ,
), ( ,
), ..., ( ,
)
n
n
x y
x
y
x
y
którego aproksymacją ma być funkcja liniowa
0
1
y
p
p x
Zgodnie z kryterium metody najmniejszych kwadratów
2
0
1
0
1
1
(
,
)
min
n
i
i
i
S p p
p
p x
y
Aproksymacja liniowa funkcji jednej zmiennej
Wykład 2/10
Warunkiem koniecznym dla istnienia ekstremum funkcji dwóch
zmiennych jest zerowanie się odpowiednich pochodnych cząstkowych:
0
1
0
0
1
1
(
,
)
0
(
,
)
0
S p p
p
S p p
p
Otrzymujemy zatem następujący układ równań:
0
1
1
0
0
1
1
1
2
0
2
0
n
i
i
i
n
i
i
i
i
S
p
p x
y
p
S
p
p x
y
x
p
Aproksymacja liniowa funkcji jednej zmiennej
Wykład 2/11
Układ ten można zapisać w następującej postaci:
0
1
1
1
2
0
1
1
1
1
n
n
i
i
i
i
n
n
n
i
i
i
i
i
i
i
p n
p
x
y
p
x
p
x
x y
lub macierzowo:
1
1
0
2
1
1
1
1
n
n
i
i
i
i
n
n
n
i
i
i
i
i
i
i
n
x
y
p
p
x
x
x y
Aproksymacja liniowa funkcji jednej zmiennej
Wykład 2/12
Rozwiązując układ równań dowolną metodą można obliczyć parametry
p
0
i
p
1
np.:
1
X P
Y
P
X
Y
Aproksymacja kwadratowa funkcji jednej zmiennej
Wykład 2/13
Przykład 1:
Dla zbioru punktów
( ,
),
1, 2, ... ,
i
i
i
P x y
i
n
dobrać wzór aproksymujący w postaci:
2
0
1
2
y
p
p x
p x
Aproksymacja kwadratowa funkcji jednej zmiennej
Wykład 2/14
Wykorzystując kryterium metody najmniejszych kwadratów
2
2
0
1
2
0
1
2
1
(
,
,
)
= min
n
i
i
i
i
S p p p
p
p x
p x
y
możemy zapisać następujący układ równań:
2
0
1
2
1
0
2
0
1
2
1
1
2
2
0
1
2
1
2
2
1
0
2
0
2
0
n
i
i
i
i
n
i
i
i
i
i
n
i
i
i
i
i
S
p
p x
p x
y
p
S
p
p x
p x
y
x
p
S
p
p x
p x
y
x
p
Aproksymacja kwadratowa funkcji jednej zmiennej
Wykład 2/15
Zapis macierzowy:
2
1
1
1
0
2
3
1
1
1
1
1
2
2
3
4
2
1
1
1
1
n
n
n
i
i
i
i
i
i
n
n
n
n
i
i
i
i
i
i
i
i
i
n
n
n
n
i
i
i
i
i
i
i
i
i
n
x
x
y
p
x
x
x
p
x y
p
x
x
x
x y
Z powyższego układu równań wyznacza się
p
0
, p
1
, p
2
.
Aproksymacja funkcji jednej zmiennej
Wykład 2/16
Przykład 2:
Dla zbioru punktów
( ,
),
1, 2, ... ,
i
i
i
P x y
i
n
dobrać wzór aproksymujący w postaci:
2
0
1
2
2
1
y
b
b
b x
x
Aproksymacja funkcji jednej zmiennej
Wykład 2/17
Wykorzystując kryterium metody najmniejszych kwadratów
2
2
0
1
2
0
1
2
2
1
1
( , ,
)
= min
n
i
i
i
i
S b b b
b
b
b x
y
x
zapisujemy następujący układ równań:
2
0
1
2
2
1
0
2
0
1
2
2
2
1
1
2
2
0
1
2
2
1
2
1
2
1
0
1
1
2
0
1
2
0
n
i
i
i
i
n
i
i
i
i
i
n
i
i
i
i
i
S
b
b
b x
y
b
x
S
b
b
b x
y
b
x
x
S
b
b
b x
y
x
b
x
Aproksymacja funkcji jednej zmiennej
Wykład 2/18
Zapis macierzowy:
Z powyższego układu równań wyznacza się
b
0
, b
1
, b
2
.
2
2
1
1
1
0
1
2
4
2
1
1
1
2
2
4
2
1
1
1
1
1
1
n
n
n
i
i
i
i
i
i
n
n
n
i
i
i
i
i
i
i
n
n
n
i
i
i
i
i
i
i
n
x
y
x
b
y
n
b
x
x
x
b
x
n
x
x y
Metody Numeryczne
Wykład 2/19
Interpolacja funkcji
jednej zmiennej
Interpolacja - definicja
Wykład 2/20
Dana jest funkcja:
0
( ) ,
,
n
y
f x
x
x x
dla której znamy tablicę jej wartości
0
0
1
1
( )
, ( )
, ..., (
)
n
n
f x
y
f x
y
f x
y
Wartości tworzące
n +1
par punktów
0
0
1
1
( ,
),( ,
), ...,( ,
)
n
n
x y
x y
x y
zwane są
węzłami interpolacji
.
Interpolacja - definicja
Wykład 2/21
Celem interpolacji jest wyznaczenie takiej funkcji
W(x)
, aby:
0
0
1
1
( )
,
( )
,...,
(
)
n
n
W x
y W x
y
W x
y
Funkcja ta nazywana jest
wielomianem interpolacyjnym
i węzłach
interpolacji przyjmuje takie same wartości co funkcja
y = f (x)
.
Interpolacja - definicja
Wykład 2/22
Wielomian interpolacyjny definiuje się jako
kombinację liniową
n + 1
funkcji bazowych i współczynników
a
i
0
( )
( )
n
i
i
i
W x
a
x
a
i
–
współczynniki wielomianu interpolacyjnego
i
(x)
–
przyjęte
funkcje bazowe
Interpolacja - definicja
Wykład 2/23
Definiując:
0
0
1
0
0
0
1
1
1
1
0
1
(
)
(
) ...
(
)
( )
( )
...
( )
...
...
...
...
(
)
(
) ...
(
)
n
n
n
n
n
n
x
x
x
x
x
x
x
x
x
X
0
1
n
y
y
y
Y
0
1
n
a
a
a
A
0
1
2
( ),
( ),
( ),...,
( )
n
x
x
x
x
Φ
1
( )
W x
X Y
wtedy:
XA
Y
Interpolacja naturalna
Wykład 2/24
Funkcje bazowe:
0
2
0
1
2
( )
1,
( )
,
( )
, ...,
( )
n
n
x
x
x
x
x
x
x
x
Postać wielomianu interpolacyjnego:
2
0
1
2
( )
...
n
n
W x
a
a x
a x
a x
Interpolacja naturalna
Wykład 2/25
2
0
1 0
2
0
0
0
2
0
1 1
2 1
1
1
2
0
1
2
...
...
...
n
n
n
n
n
n
n
n
n
n
a
a x
a x
a x
y
a
a x
a x
a x
y
a
a x
a x
a x
y
Opierając się na warunku koniecznym istnienia interpolacji:
można zapisać, że
A X
Y
0
0
1
1
1
...
1
...
...
...
...
...
1
...
n
n
n
n
n
x
x
x
x
x
x
X
0
1
n
y
y
y
Y
0
1
n
a
a
a
A
Interpolacja naturalna
Wykład 2/26
Przykład
Dla podanych węzłów zapisz:
•
macierze układu równań, z których wyznacza się
współczynniki wielomianu interpolacyjnego dla interpolacji
wielomianowej
•
wielomian interpolacyjny
Węzły:
0
0
1
1
2
2
(1,3)
( 2,5)
(4,7)
( ,
)
( ,
)
( ,
)
x y
x y
x y
Interpolacja naturalna
Wykład 2/27
0
1
2
0
0
0
0
0
0
1
1
1
1
1
1
1
0
1
2
2
2
2
2
2
x
x
x
a
y
x
x
x
a
y
x
x
x
a
y
0
1
2
0
0
1
2
1
0
1
2
2
1
1
1
3
( 2)
( 2)
( 2)
5
4
4
4
7
a
a
a
0
1
2
1
1
1
3
1
2
4
5
1
4
16
7
a
a
a
Interpolacja naturalna
Wykład 2/28
1
A
X
Y
0
1
2
1
1
3,
,
3
3
a
a
a
2
0
1
2
( )
W x
a
a x
a x
2
1
1
( )
3
3
3
W x
x
x
Interpolacja Lagrange’a
Wykład 2/29
0
1
2
3
1
0
2
3
1
( )
(
)(
)(
)......................(
)
( )
(
)(
)(
)......................(
)
....................................................................................
( )
(
)
n
n
i
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
2
1
1
1
2
3
1
(
)...(
)(
)...(
)
...................................................................................
( )
(
)(
)(
)....................(
)
i
i
n
n
n
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Dla każdej
i
(x), i = 0, 1, ..., n
brakuje składnika
(x - x
i
) !!!
Funkcje bazowe:
Interpolacja Lagrange’a
Wykład 2/30
Postać wielomianu interpolacyjnego:
0
0
1
1
0
1
2
1
0
2
0
1
1
( )
( )
( ) ...
( )
(
)(
)...(
)
(
)(
)...(
) ...
(
)(
)...(
)
n
n
n
n
n
n
W x
a
x
a
x
a
x
a x
x
x
x
x
x
a x
x
x
x
x
x
a x
x
x
x
x
x
Interpolacja Lagrange’a
Wykład 2/31
Macierz
X
:
0
0
1
1
2
2
(
)
0
0
0
0
( )
0
0
0
0
(
)
0
0
0
0
(
)
n
n
x
x
x
x
X
Dla punktu
x
i
wszystkie funkcje bazowe oprócz
i
(x)
zerują się,
bo występuje w nich składnik
(x - x
i
)
Interpolacja Lagrange’a
Wykład 2/32
Ponieważ macierz
X
ma tylko główną przekątną niezerową to:
0
0
0
0
1
0
2
0
0
0
1
1
1
1
0
1
2
1
1
1
1
2
1
(
)(
)
(
)
(
)
(
)(
)
(
)
( )
(
)(
)
(
)
(
)
n
n
n
n
n
n
n
n
n
n
n
y
y
a
x
x
x
x
x
x
x
y
y
a
x
x
x
x
x
x
x
y
y
a
x
x
x
x
x
x
x
Interpolacja Lagrange’a
Wykład 2/33
Przykład
Dla podanych węzłów zapisz:
•
macierze układu równań, z których wyznacza się
współczynniki wielomianu interpolacyjnego dla interpolacji
wielomianowej
•
wielomian interpolacyjny
Węzły:
0
0
1
1
2
2
( 2,3)
(0,5)
(2, 3)
( ,
)
( ,
)
( ,
)
x y
x y
x y
Interpolacja Lagrange’a
Wykład 2/34
0
0
1
1
2
2
( 2,3)
(0,5)
(2, 3)
( ,
)
( ,
)
( ,
)
x y
x y
x y
0
2
0
1
1
2
0
1
2
0
1
0
2
1
0
0
2
2
0
2
1
(
)(
)
(
)(
)
(
)(
)
( )
(
)(
)
(
)(
)
(
)(
)
x
x
x
x
x
x
x
x
x
x
x
x
W x
y
y
y
x
x
x
x
x
x
x
x
x
x
x
x
( 2) (
2)
( 2) (
0)
(
0)(
2)
( )
3
5
( 3)
( 2 0)( 2 2)
0 ( 2) (0 2)
( 2) (2 0)
x
x
x
x
x
x
W x
x
(
0)(
2)
(
2)(
2)
(
2)(
0)
( )
3
5
3
( 2 0)( 2 2)
(0 2)(0 2)
(2 2)(2 0)
x
x
x
x
x
x
W x