Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
EKSTRAPOLACJA ITEROWANA RICHARDSONA
Do obliczenia pewnej wielkości stosuje się metodę numeryczną z
parametrem h. Wynikiem jej działania jest F(h). Wartością dokładną jest
F(0). Trudności obliczeniowe rosną, gdy h maleje.
Zakładamy, że znamy postać rozwinięcia ( p1 < p2 < p3 ....)
1 2 3
F( h ) = a0 + a1hp + a2hp + a3hp ....
F(0) ekstrapolujemy na podstawie kilku obliczonych wartości
F(h0), F(q-1h0), F(q-2h0), F(q-3h0)... q>1
Ekstrapolacja iterowana Richardsona pozwala na utworzenie ciągu
funkcji F1( h ),F2( h ),F3( h ),...., którego n-ty wyraz ma rozwinięcie:
pn pn+1 pn+ 2
Fn ( h ) = a0 + an ,nh + an ,n+1h + an ,n+2h .....
W3-1
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
Sposób obliczeń: dana wartość początkowa h0 i liczba q>1, stosuje się
wzór rekurencyjny:
Am ,0 = F( q-mh0 ),m = 0,1,2...
Am ,k -1 - Am-1,k -1
Am ,k = Am ,k -1 + ,k = 1,2,3...,Fn ( h0 ) = An-1,n-1 ,n = 2,3,4....
pk
q - 1
W3-2
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
Schemat obliczeń: " = Am ,k -1 - Am-1,k -1
k 0 1
"
m
p1
q - 1
A0,0 =
0
F( h0 )
A1,0 = A1,1 =
1 A1,0 - A0,0
+ =
F2( h0 )
F( q-1h0 ) p1
q - 1
A2,0 = A2 ,1 =
2 A2,0 - A1,0
+ =
F( q-2h0 ) p1 F2( q-1h0 )
q - 1
A3 ,0 = A3 ,1 =
3 A3,0 - A2,0
+ =
F( q- 3h0 ) p1 F2( q- 2h0 )
q - 1
W3-3
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
k 0 1 2 3
" " "
m
p1 p2 p3
q - 1 q - 1 q - 1
A0,0 =
0
F(h0)
A1,0 = A11 =
,
A1,0 - A0,0
1
+ =
F2(h0)
F(q-1h0) p1
q - 1
A2,0 = A2,1 =
A2,0 - A1,0
A2,2 =
A2,1 - A1,1
2
+ =
F(q-2h0) p1 F2(q-1h0)
q - 1
+ =
F2( h0 )
p2
q - 1
A3,0 = A31 =
,
A3,0 - A2,0
A3,2 =
A3,1 - A2,1 A3,2 - A2,2 A3,3 =
3
+ =
F(q-3h0) p1 F2(q-2h0)
q - 1
+ = + =
F4( h0 )
p2 F3( q-1h0 ) p3
q - 1 q - 1
W3-4
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
Zastosowanie do różniczkowania numerycznego
h2 h3 ( 3 )
f ( x0 + h ) = f ( x0 ) + hf' ( x0 ) + f'' ( x0 ) + f ( x0 ) + L
2! 3!
Różnica progresywna
f ( x0 + h ) - f ( x0 ) h h2 ( 3 )
DP ( h ) = = f' ( x0 ) + f'' ( x0 ) + f ( x0 ) + L
h 2! 3!
p1 = 1, p2 = 2, p3 = 3, ...
W3-5
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
Różnica centralna
f ( x0 + h )- f ( x0 - h )
DC ( h ) = =
2h
1 ż# h2 h3 ( 3 )
�#
= f ( x0 )+ hf' ( x0 )+ f'' ( x0 )+ f ( x0 )+Lś# -
ś# ź#
�#
2h 2! 3!
�# #
�#
h2 h3 ( 3 ) �#
�#
- f ( x0 )- hf' ( x0 )+ f'' ( x0 )- f ( x0 )+Lś#Ź# =
ś# ź#
2! 3!
�# #
�#
h2 ( 3 ) h4 ( 5 )
= f' ( x0 )+ f ( x0 )+ f ( x0 )+L
3! 5!
p1 = 2, p2 = 4, p3 = 6, ...
W3-6
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
d d e1+h - e
x
e = ? ex H" h=10-n
dx dx h
x=1 x =1
1
0
-1
-2
-3
-4
-5
-6
-7
-8
-9
-12 -10 -8 -6 -4 -2 0
n
W3-7
log10(blad)
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
d e1+h - e1-h
x
e H" h=10-n
dx 2h
x=1
0
-2
-4
-6
-8
-10
-12
-12 -10 -8 -6 -4 -2 0
n
W3-8
log10(blad)
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
Z Ekstrapolacji Richardsona
-2
-4
-6
-8
-10
-12
-14
0.2 0.4 0.6 0.8 1
h
W3-9
log10(blad)
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
Całkowanie numeryczne
b
n
Kwadratura: f ( x )dx = Ak f ( xk )
"
+"
k =0
a
KWADRATURY NEWTONA-COTESA
uzyskane przez interpolację wielomianem z węzłami
równoodległymi
b - a
xi = a + ih, i = 0,...,n, h =
n
b b
n
b - a
f ( x )dx H" Pn( x )dx =
"� fi , fi = f ( xi ) = Pn( xi )
i
+" +"
ns
i =0
a a
W3-10
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
n ns błąd nazwa
�i
1 1 1 2 1 wzór trapezów
( 2 )
h3 f (� )
12
2 1 4 1 6 1 wzór Simpsona
( 4 )
h5 f (� )
90
3 1 3 3 1 8 3 wzór "trzech ósmych"
( 4 )
h5 f (� )
80
4 7 32 12 32 90 8 wzór Milne'a
( 6 )
h7 f (� )
7
945
5 19 75 50 50 288 275 -
( 6 )
h7 f (� )
75 19
12096
6 41 216 27 272 840 9 wzór Weddle'a
( 8 )
h9 f (� )
27 216 41
1400
h- długość przedziału, �- punkt pośredni
W3-11
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
Obliczenie współczynników kwadratur Newtona-Cotesa:
Dane są węzły x0,x1,..,xn. Chcemy, by kwadratura całkowała dokładnie (na przedziale [ 1
1])stałą:
1
1
Ą# ń#
x1 1- ( -1)
0 0 0
w0x0 + w1x1 + L + wnxn = x0dx = =
ó# Ą#
+"
1 1
Ł# Ś#-1
-1
oraz funkcje x, x2, & xn:
1
1
Ą# ń#
x2 12 - ( -1)2
1 1
w0x0 + w1x1 + L+ wnx1 = x1dx = =
n
ó# Ą#
+"
2 2
Ł# Ś#-1
-1
& & & & & & & & & & & & &
1
1
Ą# ń#
xn+1 1- ( -1)n+1
n n n
w0x0 + w1x1 +L+ wnxn = xndx =
ó#n +1Ą# =
+"
n +1
Ł# Ś#-1
-1
W postaci macierzowej:
W3-12
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
1- ( -1)
Ą# ń#
0 0 0
ó# Ą#
w0
Ą# ń#
x0 x1 L xn
Ą# ń#
1
ó#
ó#x1 x1 K x1 Ą#
ó#w Ą#
1 1
1- ( -1)2 Ą#
1 ó# Ą#
0
ó# Ą#
ó# Ą#
=
2
ó# Ą#
ó# Ą#
ó# Ą#
M
M M M M
M
ó# Ą#
ó# Ą#
ó#w Ą#
n n n
x1 L xn Ś#Ł# n Ś#
1- ( -1)n+1
ó# Ą#
Ł#x0
ó# Ą#
Ł# n +1 Ś#
transponowana macierz Vandermode a
W3-13
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
Kwadratura Newtona-Cotes a o n+1 węzłach obliczy dokładnie całkę wielomianu
stopnia n. Można zmienić układ węzłów, tak by zwiększyć stopień wielomianu
całkowanego dokładnie przez kwadraturę korzystającą z n węzłów.
Kwadratury Gaussa pozwalaja na dokładne całkowanie wielomianów stopnia do
2n-1 przy n węzłach.
W3-14
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
b - a
Kwadratury złożone xi = a + ih, i = 0,...,n, h =
n
b
n-1
h
Wzór prostokątów f ( x )dx H"h f ( xi + ) = R( h )
"
+"
2
i =0
a
b
n-1
h
Wzór trapezów f ( x )dx H"
"[ f ( xi ) + f ( xi )]= T( h )
+1
+"
2
i =0
a
f ( a ) f ( b )
ń#
T( h ) = hĄ# + f ( a + h ) + L+ f ( b - h ) +
ó# Ą#
2 2
Ł# Ś#
Oszacowanie błędu obcięcia:
b
1
f ( x )dx - R( h ) d" (b - a)h2 f'' (� )
+"
24
a
b
1
f ( x )dx - T( h ) d" (b - a)h2 f'' (� )
+"
12
a
W3-15
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
b
T( h ) = f ( x )dx + a1h2 +a2h4 + a3h6 + L
+"
a
Metoda Romberga=
=złożona kwadratura trapezów+ekstrapolacja Richardsona
q=2, pi=2i
W3-16
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
Kwadratury adaptacyjne
W3-17
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 3
W3-18