Môc lôc
danh môc c¸c b¶ng
viii
C¸c tõ viÕt t¾t
ix
Nh÷ng kÝ hiÖu trong luËn ¸n
xi
më ®Çu
1
1
tæng quan vÒ c¸c ph−¬ng ph¸p song song
1.1 C¸c ph−¬ng ph¸p RKN . . . . . . . . . . . . . . . .
1.1.1 CÊp chÝnh x¸c cña ph−¬ng ph¸p RKN . . . .
1.1.2 TÝnh æn ®Þnh cña c¸c ph−¬ng ph¸p RKN . . .
1.2 C¸c ph−¬ng ph¸p IRKN d¹ng trïng khíp . . .
1.2.1 C¸c ph−¬ng ph¸p IRKN d¹ng trïng khíp gi¸n
tiÕp . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.2 C¸c ph−¬ng ph¸p IRKN d¹ng trïng khíp trùc
tiÕp . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.3 X¸c ®Þnh hÖ sè cña ph−¬ng ph¸p RKN . . . .
1.3 C¸c ph−¬ng ph¸p PIRKN . . . . . . . . . . . . . .
1.3.1 CÊp chÝnh x¸c cña c¸c ph−¬ng ph¸p PIRKN .
1.3.2 Sù héi tô cña c¸c ph−¬ng ph¸p PIRKN . . . .
1.3.3 TÝnh æn ®Þnh cña c¸c ph−¬ng ph¸p PIRKN .
1.3.4 So s¸nh sai sè cña cña c¸c ph−¬ng ph¸p PIRKN
1.4 C¸c ph−¬ng ph¸p IPIRKN . . . . . . . . . . . . . .
1.4.1 CÊp chÝnh x¸c cña ph−¬ng ph¸p IPIRKN . .
1.4.2 X¸c ®Þnh hÖ sè cña ph−¬ng ph¸p dù b¸o . . .
1.4.3 TÝnh æn ®Þnh cña ph−¬ng ph¸p IPIRKN . . .
1.4.4 Sai sè cña c¸c ph−¬ng ph¸p PIRKN . . . . . .
v
5
5
6
7
8
8
9
10
12
13
14
15
16
17
18
19
20
21
1.5
2
1.4.5 So s¸nh c¸c ph−¬ng ph¸p PIRKN vµ IPIRKN
1.4.6 C¸c ph−¬ng ph¸p TRKN . . . . . . . . . . . . .
1.4.7 Chän hÖ sè cña ph−¬ng ph¸p . . . . . . . . .
1.4.8 C¸c ph−¬ng ph¸p PITRKN . . . . . . . . . . .
KÕt luËn . . . . . . . . . . . . . . . . . . . . . . . . . .
Ph−¬ng ph¸p dù b¸o-hiÖu chØnh d¹ng PIRKN
víi c«ng thøc dù b¸o kiÓu adams
2.1 Giíi thiÖu . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 §iÒu kiÖn cÊp chÝnh x¸c . . . . . . . . . . . . . . .
2.3 X¸c ®Þnh hÖ sè cña ph−¬ng ph¸p PIRKNA . . .
2.4
2.5
2.6
TÝnh chÊt æn ®Þnh cña ph−¬ng ph¸p PIRKNA
Thö nghiÖm tÝnh to¸n . . . . . . . . . . . . . . . .
2.5.1 C¸c bµi to¸n thö. . . . . . . . . . . . . . . . .
2.5.2 So s¸nh víi c¸c ph−¬ng ph¸p song song . .
2.5.3 Bµi to¸n kh«ng dõng tuyÕn tÝnh . . . . . . .
2.5.4 Bµi to¸n Fehlberg phi tuyÕn . . . . . . . . .
KÕt luËn . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
21
22
25
27
31
32
32
34
36
37
39
39
41
41
42
42
3
ph−¬ng ph¸p lÆp song song gi¶ RKN hai b−íc 44
3.1 Giíi thiÖu . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Ph−¬ng ph¸p hiÖu chØnh PTRKN . . . . . . . . . 45
3.2.1 §iÒu kiÖn cÊp chÝnh x¸c . . . . . . . . . . . . . 47
3.2.2 Zero-æn ®Þnh . . . . . . . . . . . . . . . . . . . 52
3.3 Ph−¬ng ph¸p IPIPTRKN . . . . . . . . . . . . . . . 53
3.3.1 §iÒu kiÖn cÊp chÝnh x¸c cña c«ng thøc dù b¸o 54
3.3.2 Tèc ®é héi tô cña ph−¬ng ph¸p IPIPTRKN . 56
3.3.3 MiÒn æn ®Þnh . . . . . . . . . . . . . . . . . . . 57
3.4 Thö nghiÖm tÝnh to¸n . . . . . . . . . . . . . . . . . 59
3.4.1 So s¸nh víi c¸c ph−¬ng ph¸p song song . . . 62
3.4.2 So s¸nh víi c¸c ph−¬ng ph¸p tuÇn tù . . . . . 64
3.5 KÕt luËn . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4
Ph−¬ng ph¸p dù b¸o hiÖu chØnh d¹ng RKN
vi
lÆp song song liªn tôc
4.1 Giíi thiÖu . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Ph−¬ng ph¸p RKN liªn tôc (ph−¬ng ph¸p CRKN)
4.3 Ph−¬ng ph¸p CPIRKN . . . . . . . . . . . . . . . .
4.3.1 Tèc ®é héi tô . . . . . . . . . . . . . . . . . . .
4.3.2 MiÒn æn ®Þnh . . . . . . . . . . . . . . . . . . .
4.4 Thö nghiÖm sè . . . . . . . . . . . . . . . . . . . . .
4.4.1 So s¸nh víi ph−¬ng ph¸p song song . . . . .
4.4.2 So s¸nh víi c¸c ph−¬ng ph¸p tuÇn tù . . . . .
4.5 KÕt luËn . . . . . . . . . . . . . . . . . . . . . . . . . .
67
67
68
74
76
77
79
80
82
82
KÕt luËn
84
c¸c c«ng tr×nh ®· c«ng bè liªn quan ®Õn luËn ¸n
86
Tµi liÖu tham kh¶o
87
vii
Danh s¸ch b¶ng
2.1 Biªn æn ®Þnh β(m) cña ph−¬ng ph¸p PIRKNA . . . . . . .
2.2 Gi¸ trÞ NCD/Nseq cña bµi to¸n (testprob1) tÝnh b»ng ph−¬ng
ph¸p PIRKNA, PIRKN vµ IPIRKN . . . . . . . . . . . . . .
2.3 Gi¸ trÞ NCD/Nseq cña bµi to¸n (testprob2) tÝnh b»ng ph−¬ng
ph¸p PIRKN, IPIRKN trùc tiÕp vµ PIRKNA . . . . . . . . .
39
3.1 Nh©n tö héi tô cña mét sè ph−¬ng ph¸p song song PC cÊp p .
3.2 Biªn æn ®Þnh β(m) cña c¸c ph−¬ng ph¸p song song PC cÊp p
3.3 NCD/Nseq cña bµi to¸n (testprob1) tÝnh b»ng ph−¬ng ph¸p
IPIPTRKN vµ c¸c ph−¬ng ph¸p PIRKN . . . . . . . . . . .
3.4 NCD/Nseq cña bµi to¸n (testprob2) tÝnh b»ng ph−¬ng ph¸p
IPIPTRKN vµ c¸c ph−¬ng ph¸p PIRKN . . . . . . . . . . .
3.5 NCD/Nseq cña bµi to¸n (testprob3) tÝnh b»ng ph−¬ng ph¸p
IPIPTRKN vµ c¸c ph−¬ng ph¸p PIRKN . . . . . . . . . . .
3.6 So s¸nh ph−¬ng ph¸p IPIPTRKN6 víi code tuÇn tù gi¶i bµi
to¸n (testprob2) . . . . . . . . . . . . . . . . . . . . . .
60
61
4.1 Gi¸ trÞ NCDp |NCDp∗ cho bµi to¸n (testprob2) víi c¸c ph−¬ng
ph¸p RKN liªn tôc kh¸c nhau . . . . . . . . . . . . . . . .
4.2 Biªn æn ®Þnh βstab (m) cho ph−¬ng ph¸p CPIRKN kh¸c nhau .
4.3 Gi¸ trÞ NCD/Nseq cho bµi to¸n (testprob1) víi p kh¸c nhau
4.4 Gi¸ trÞ NCD/Nseq cho bµi to¸n (testprob2) nhËn ®−îc víi p
kh¸c nhau . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Gi¸ trÞ NCD/Nseq cho bµi to¸n (testprob3) víi p kh¸c nhau
4.6 So s¸nh ph−¬ng ph¸p CPIRKN56 víi code DOPRIN vµ ODEX2
gi¶i bµi to¸n (testprob2) . . . . . . . . . . . . . . . . . .
viii
43
43
63
64
64
65
74
79
81
81
82
83
C¸c tõ viÕt t¾t
CPIRKN
Continuous parallel-iterated RKN
ERKN
..
Explicit Runge-Kutta-Nystro m
NCD
Number of Correct Decimal Digits
..
LÆp song song liªn tôc Runge-Kutta-Nystrom
..
Runge-Kutta-Nystrom hiÓn
Gi¸ trÞ trung b×nh sè c¸c ch÷ sè thËp ph©n ®óng
IPIRKN
..
Improved Parallel Iterated Runge-Kutta-Nystro m
IPIPTRKN
Improved Parallel-Iterated Pseudo Two-step
IRK
Implicit Runge-Kutta
..
LÆp song song c¶i tiÕn Runge-Kutta-Nystrom
..
LÆp song song c¶i tiÕn gi¶ Runge-Kutta-Nystrom hai b−íc
Rungge-Kutta Èn
IRKN
..
Implicit Runge-Kutta-Nystro m
PC
Predictor-Corrector
..
Runge-Kutta-Nystrom Èn
Dù b¸o-HiÖu chØnh
PIPTRKN
..
Parallel-Iterated Pseudo Two-step Runge-Kutta-Nystro m
PIRKNA
..
Parallel Iterated Runge-Kutta-Nystro m with Adams-type predictors
PIRKN
..
Parallel Iterated Runge-Kutta-Nystro m
PISRKN
..
Parallel-Iterated Symetric Runge-Kutta-Nystro m
..
LÆp song song gi¶ Runge-Kutta-Nystrom hai b−íc
..
LÆp song song Runge-Kutta-Nystrom víi dù b¸o kiÓu Adams.
..
LÆp song Runge-Kutta-Nystrom
..
LÆp song song ®èi xøng Runge-Kutta-Nystrom
ix
PITRKN
..
Parallel Iterated Two step Runge-Kutta-Nystro m
PTRKN
..
Pseudo Two-step Runge-Kutta-Nystro m
RK
Runge-Kutta
..
LÆp song song hai b−íc Runge-Kutta-Nystrom
..
Gi¶ Runge-Kutta-Nystrom hai b−íc.
Runge-Kutta
RKN
..
Runge-Kutta-Nystro m
SRKN
..
Symmetric Runge-Kutta-Nystro m
TRKN
..
Two Step Runge-Kutta-Nystro m
..
Runge-Kutta-Nystrom
..
Runge-Kutta-Nystrom ®èi xøng.
..
Runge-Kutta-Nystrom hai b−íc
x
Nh÷ng kÝ hiÖu trong luËn ¸n
Ngoµi nh÷ng kÝ hiÖu th«ng th−êng cña gi¶i tÝch vµ ®¹i sè, trong luËn
¸n nµy chóng t«i cßn dïng mét sè kÝ hiÖu sau:
1. TÝch trùc tiÕp cña hai ma trËn.
Gi¶ sö A lµ ma trËn p × q chiÒu, B lµ ma trËn bÊt k× khi ®ã
a11 B a12 B . . . a1q B
A ⊗ B = [aij B] = a.21. .B a.22. .B .. .. .. a.2q. B
. .
ap1 B ap2 B . . . apq B
2. Luü thõa cña mét vÐc t¬ . Gi¶ sö c = (c1 , c2 , . . . , cs )T , khi ®ã
ck = (ck1 , ck2 , . . . , cks )T .
d
3. To¸n tö exp( dx
).
d
d
d2
dn
+
.
.
.
+ ...
)=1+
+
dx
dx 2!dx2
n!dxn
Khi ®ã khai triÓn Taylor hµm y(t) t¹i l©n cËn ®iÓm t0 sÏ lµ:
exp(
∞
1 dn y(t0 )
d
y(t0 + h) = exp(h )y(t0 ) =
hn
.
n
dt
n!
dx
n=0
4. KÝ hiÖu vÐc t¬ e. VÐc t¬ e lu«n hiÓu cã tÊt c¶ c¸c thµnh phÇn b»ng 1.
5. Gi¶ sö f (x, y) lµ hµm thùc cña hai biÕn thùc x vµ y , nÕu thay
x vµ y t−¬ng øng bëi hai vÐc t¬ v = (v1 , v2 , . . . , vs )T vµ w =
(w1 , w2 , . . . , ws )T , ta ®−îc vÐc t¬ hµm víi s thµnh phÇn:
f (v, w) = [f (v1 , w1 ), f (v2 , w2 ), . . . , f (vs , ws )]T .
NÕu x ∈ R, cßn y thay bëi w = (w1 , w2 , . . . , ws )T ta cã
f (x, w) = [f (x, w1 ), f (x, w2 ), . . . , f (x, ws )]T .
xi
Më ®Çu
HÇu hÕt c¸c hiÖn t−îng tù nhiªn vµ kÜ thuËt ®Òu ®−îc m« t¶ bëi hÖ
ph−¬ng tr×nh vi ph©n. C¸c hÖ ph−¬ng tr×nh vi ph©n thuéc lo¹i nµy th−êng
kh«ng cho nghiÖm ®óng d−íi d¹ng gi¶i tÝch. V× vËy, vÊn ®Ò gi¶i gÇn ®óng
hÖ ph−¬ng tr×nh vi ph©n ®· ®−îc quan t©m tõ l©u. Mét trong nh÷ng h−íng
gi¶i gÇn ®óng ®ã lµ gi¶i sè. Nh−ng khoa häc vµ c«ng nghÖ ngµy cµng ph¸t
triÓn, dÉn ®Õn kÝch th−íc c¸c bµi to¸n ngµy cµng lín, yªu cÇu ngµy mét
cao vÒ ®é chÝnh x¸c, h¬n n÷a l¹i ph¶i cho kÕt qu¶ trong thêi gian thùc (real
time problems) ch¼ng h¹n nh− bµi to¸n dù b¸o thêi tiÕt hay bµi to¸n ®iÒu
khiÓn c¸c chuyÕn bay. CÇn thùc hiÖn khèi l−îng tÝnh to¸n khæng lå, víi
®é chÝnh x¸c cao trong kho¶ng thêi gian h¹n chÕ. C¸c m¸y tÝnh thÕ hÖ cò
kh«ng thÓ ®¸p øng ®−îc nh÷ng yªu cÇu nµy. Tr−íc nhu cÇu bøc xóc ®ã,
mét chñng lo¹i m¸y tÝnh míi ®· ra ®êi, ®ã lµ m¸y tÝnh cã tèc ®é cao víi
nhiÒu bé xö lÝ ®ång thêi lµm viÖc ®ã lµ siªu m¸y tÝnh ( cßn gäi lµ m¸y tÝnh
song song, m¸y tÝnh vÐc t¬ ). Sù ra ®êi cña siªu m¸y tÝnh më ®−êng cho
mét h−íng ph¸t triÓn míi cña gi¶i tÝch sè nãi chung vµ gi¶i sè hÖ ph−¬ng
tr×nh vi ph©n nãi riªng.
V× c¸c ph−¬ng ph¸p sè tr−íc ®©y ®−îc x©y dùng vµ nghiªn cøu nh»m khai
th¸c lo¹i m¸y tÝnh truyÒn thèng, chØ cã mét bé xö lý, c¸c ph−¬ng ph¸p ®ã
cßn ®−îc gäi lµ c¸c ph−¬ng ph¸p tuÇn tù. NÕu chØ sö dông c¸c ph−¬ng
ph¸p tuÇn tù sÏ kh«ng khai th¸c mét c¸ch cã hiÖu qu¶ c¸c siªu m¸y tÝnh.
ViÖc x©y dùng vµ nghiªn cøu c¸c ph−¬ng ph¸p míi nh»m khai th¸c tèt c¸c
siªu m¸y tÝnh ®· trë thµnh nhu cÇu cÊp thiÕt cña to¸n häc tÝnh to¸n nãi
1
chung vµ gi¶i sè c¸c hÖ ph−¬ng tr×nh vi ph©n nãi riªng. Cho ®Õn nay, viÖc
x©y dùng c¸c thuËt to¸n míi ®Ó gi¶i sè c¸c bµi to¸n gi¸ trÞ ®Çu trªn m¸y
tÝnh song song ®· trë thµnh mét h−íng nghiªn cøu quan träng. Cã ba c¸ch
tiÕp cËn chÝnh, ®ã lµ:
1. Song song ho¸ trªn tõng bµi to¸n.
2. Song song ho¸ trªn c¸c b−íc lÊy tÝch ph©n.
3. Song song ho¸ thuËt to¸n.
Trong ba c¸ch tiÕp cËn trªn, c¸ch tiÕp cËn thø ba ®−îc quan t©m nhÊt
v× thuËt to¸n ®−îc x©y dùng ®éc lËp víi bµi to¸n. LuËn ¸n cña chóng t«i
còng kh«ng ra ngoµi sù quan t©m chung ®ã.
..
LuËn ¸n: Mét sè ph−¬ng ph¸p song song d¹ng Runge-Kutta-Nystrom
gi¶i bµi to¸n kh«ng c−¬ng cña chóng t«i nghiªn cøu vµ ph¸t triÓn mét sè
ph−¬ng ph¸p song song ®Ó gi¶i bµi to¸n Cauchy cho mét líp hÖ ph−¬ng
tr×nh vi ph©n cÊp 2 cã d¹ng sau ®©y:
y (t) = f (t, y(t)),
y(t0 ) = y0 ,
y (t0 ) = y0 ,
t0 t T,
y, f ∈ RN .
(1)
ë ®©y, còng nh− trong toµn bé luËn ¸n, hµm vÕ ph¶i f (t, y(t)) lu«n gi¶
thiÕt liªn tôc theo biÕn t vµ Lipschitz theo biÕn y, h¬n n÷a, nghiÖm duy
nhÊt cña bµi to¸n (1) ®−îc gi¶ thiÕt ®ñ tr¬n.
§©y lµ líp ph−¬ng tr×nh quan träng trong VËt lÝ, C¬ häc, Thiªn v¨n häc...v×
nã m« t¶ mèi quan hÖ theo ®Þnh luËt Newton thø hai.
Mét biÖn ph¸p truyÒn thèng ®Ó gi¶i bµi to¸n (1) lµ chuyÓn ®æi nã vÒ
hÖ ph−¬ng tr×nh vi ph©n cÊp 1 víi sè chiÒu gÊp ®«i, sau ®ã ¸p dông c¸c
ph−¬ng ph¸p cña hÖ ph−¬ng tr×nh vi ph©n cÊp 1. Mét trong nh÷ng líp
ph−¬ng ph¸p truyÒn thèng phæ biÕn gi¶i hÖ ph−¬ng tr×nh vi ph©n cÊp 1 lµ
ph−¬ng ph¸p Runge-Kutta (RK) cã l−îc ®å nh− sau (xem [6]):
Un = e ⊗ un + h(A ⊗ IN )F(tn e + hc, Un ),
un+1 = un + h(bT ⊗ IN )F(tn e + hc, Un ).
(2)
víi A, c, b lµ ma trËn vµ c¸c vÐc t¬ t¹o thµnh bé tham sè cña ph−¬ng ph¸p.
Ph−¬ng ph¸p RK (1.1) th−êng ®−îc biÓu diÔn ng¾n gän d−íi d¹ng b¶ng
Butcher nh− sau:
2
A
bT
c
C¸ch gi¶i nh− trªn gäi lµ c¸ch gi¶i gi¸n tiÕp. Mét c¸ch gi¶i kh¸c lµ
kh«ng ®−a hÖ ph−¬ng tr×nh cÊp 2 vÒ hÖ ph−¬ng tr×nh cÊp 1, mµ gi¶i trùc
tiÕp nã (cßn gäi lµ ph−¬ng ph¸p trùc tiÕp). NhiÒu nhµ to¸n häc ®· quan
t©m vµ x©y dùng ®−îc nhiÒu ph−¬ng ph¸p sè h÷u hiÖu ®Ó gi¶i trùc tiÕp bµi
to¸n (1) nhê kh¶ n¨ng khai th¸c d¹ng ®Æc biÖt cña nã lµ hµm vÕ ph¶i kh«ng
phô thuéc ®¹o hµm cÊp mét y . Mét líp ph−¬ng ph¸p thµnh c«ng h¬n
..
c¶ lµ c¸c ph−¬ng ph¸p Runge-Kutta-Nystrom (RKN). Ph−¬ng ph¸p RKN
..
®Çu tiªn ®−îc Nystrom ®Ò xuÊt vµo n¨m 1925. VÒ sau mét sè nhµ to¸n
..
häc kh¸c nh− Hairer, Fehlberg, Graf... tiÕp tôc h−íng nghiªn cøu nµy cña
..
Nystrom vµ ®· x©y dùng ®−îc c¸c ph−¬ng ph¸p RKN hiÓn (explicit RKN
- ERKN) víi cÊp chÝnh x¸c cao h¬n (xem[24, 25, 26, 27, 28]).
Tuy ®· ®−îc nghiªn cøu vµ ph¸t triÓn sím nh−ng c¸c ph−¬ng ph¸p
song song d¹ng RK ®· ®−îc x©y dùng míi chØ dõng ë møc ¸p dông cho
hÖ ph−¬ng tr×nh vi ph©n cÊp 1. ViÖc gi¶i c¸c bµi to¸n hÖ ph−¬ng tr×nh vi
ph©n cÊp cao nãi chung vµ cÊp 2 nãi riªng vÉn ph¶i gi¶i gi¸n tiÕp th«ng
qua viÖc chuyÓn ®æi vÒ hÖ ph−¬ng tr×nh vi ph©n cÊp 1. ChØ tíi n¨m 1993
c¸c ph−¬ng ph¸p song song gi¶i trùc tiÕp hÖ ph−¬ng tr×nh vi ph©n cÊp 2
d¹ng (1) míi ®−îc N.H. Cong, P.J. van der Houwen, B.P. Sommeijer b¾t
®Çu nghiªn cøu vµ x©y dùng trªn c¬ së cña ph−¬ng ph¸p RKN Èn (Implicit
RKN - IRKN) gäi lµ c¸c ph−¬ng ph¸p song song d¹ng RKN.
LuËn ¸n gåm phÇn më ®Çu vµ 4 ch−¬ng néi dung.
Ch−¬ng 1, tr×nh bµy mét sè nÐt c¬ b¶n vÒ c¸c ph−¬ng ph¸p RKN vµ
thèng kª l¹i mét sè líp ph−¬ng ph¸p song song d¹ng RKN ®iÓn h×nh ®·
®−îc x©y dùng.
Ch−¬ng 2, nghiªn cøu mét líp ph−¬ng ph¸p song song víi c«ng thøc
dù b¸o hai b−íc kiÓu Adams (PIRKNA). KÕt qu¶ cña ch−¬ng nµy c«ng bè
trong [3].
3
Ch−¬ng 3, mét líp ph−¬ng ph¸p lÆp song song c¶i tiÕn gi¶ RKN hai
b−íc (IPIPTRKN) ®−îc x©y dùng cã c¸c ®Æc tr−ng tèt vÒ tÝnh æn ®Þnh vµ
tèc ®é héi tô nh−ng chØ cÇn m¸y tÝnh cã Ýt bé xö lÝ. C¸c kÕt qu¶ cña ch−¬ng
nµy ®−îc c«ng bè trong bµi b¸o [22].
Ch−¬ng 4, nghiªn cøu mét líp ph−¬ng ph¸p song song víi c«ng thøc
®Çu ra liªn tôc (CIPIRKN). Ph−¬ng ph¸p ¸p dông tèt trong tr−êng hîp cÇn
nhËn ®−îc gi¸ trÞ cña nghiÖm t¹i nhiÒu ®iÓm kh¸c nhau. C¸c kÕt qu¶ cña
ch−¬ng nµy c«ng bè trong [23].
Néi dung c¬ b¶n cña luËn ¸n ®· ®−îc b¸o c¸o t¹i Bé m«n To¸n häc TÝnh
to¸n, khoa To¸n-C¬-Tin häc, tr−êng §¹i häc Khoa häc Tù nhiªn, §¹i häc
Quèc gia Hµ Néi.
T«i xin bµy tá lßng biÕt ¬n to lín vµ s©u s¾c tíi hai ng−êi thÇy lµ
GS TSKH NguyÔn H÷u C«ng vµ GS TSKH Ph¹m Kú Anh ®· tËn t×nh chØ
b¶o, h−íng dÉn t«i nghiªn cøu ®Ó hoµn thµnh luËn ¸n.
T«i xin c¸m ¬n GS TS NguyÔn H÷u D−, TS Vò Hoµng Linh, TS NguyÔn
ThÞ Hång Minh cïng c¸c thµnh viªn trong Seminar bé m«n to¸n häc tÝnh
to¸n ®· ®äc, nghe tr×nh bµy vµ ®ãng gãp nhiÒu ý kiÕn quý b¸u gióp cho
luËn ¸n ®−îc hoµn thiÖn.
T¸c gi¶ xin ch©n thµnh c¸m ¬n Khoa To¸n C¬-Tin häc-Tr−êng §¹i häc
Khoa häc Tù nhiªn; Tr−êng §¹i häc Kinh tÕ vµ Qu¶n trÞ Kinh doanh; Khoa
Khoa häc Tù nhiªn-§¹i häc Th¸i Nguyªn ®· t¹o ®iÒu kiÖn cho t«i hoµn
thµnh nhiÖm vô.
4
Ch−¬ng 1
tæng quan vÒ c¸c ph−¬ng ph¸p song song
Trong ch−¬ng nµy tr−íc hÕt chóng t«i tr×nh bµy ph−¬ng ph¸p
..
Runge-Kutta-Nystrom (RKN) gi¶i trùc tiÕp bµi to¸n (1) vµ sau ®ã
chän läc mét sè ph−¬ng ph¸p song song d¹ng RKN ®iÓn h×nh ®·
®−îc x©y dùng. Chóng t«i −u tiªn cho viÖc tr×nh bµy c¸c ph−¬ng
ph¸p song song mµ luËn ¸n cã liªn quan.
1.1 C¸c ph−¬ng ph¸p RKN
§Ó gi¶i trùc tiÕp bµi to¸n (1), ta xÐt mét ph−¬ng ph¸p cã nhiÒu −u ®iÓm
gièng ph−¬ng ph¸p RK, ®ã lµ ph−¬ng ph¸p RKN s-nÊc sau ®©y:
Un,i = un +
hci un
2
+h
un+1 = un + hun + h2
s
aij f (tn + cj h, Un,j ),
i = 1, . . . , s,
j=1
s
bj f (tn + cj h, Un,j ),
(1.1)
j=1
un+1 = un + h
s
dj f (tn + cj h, Un,j ).
j=1
Hay d−íi d¹ng ma trËn vÐc t¬ t−¬ng ®−¬ng
Un = e ⊗ un + hc ⊗ u n + h2 (A ⊗ IN )F(tn e + hc, Un ),
un+1 = un + hu n + h2 (bT ⊗ IN )F(tn e + hc, Un ),
u n+1 = u n + h(dT ⊗ IN )F(tn e + hc, Un ),
5
(1.2)
trong ®ã: Un = (UT n,1 , . . . , UT n,s )T ; F(tn e + hc, Un ) = [(f(tn +
c1 h, Un,1 ), . . . , (f(tn + cs h, Un,s )]T ®Òu lµ c¸c vÐc t¬ sN chiÒu, Un
®−îc gäi lµ vÐc t¬ nÊc. b, c, d, e lµ c¸c vÐc t¬ s-chiÒu, IN lµ ma trËn
®¬n vÞ N × N .
Khi N = 1, tøc lµ hÖ ph−¬ng tr×nh vi ph©n chØ cã mét ph−¬ng tr×nh, th×
ph−¬ng ph¸p (1.2) cã d¹ng ®¬n gi¶n h¬n sau ®©y:
Un = un e + hun c + h2 Af (tn e + hc, Un ),
(1.3a)
un+1 = un + hun + h2 bT f (tn e + hc, Un ),
(1.3b)
un+1 = un + hdT f(tn e + hc, Un ),
(1.3c)
ë ®©y, kÝ kiÖu un , un lµ gi¸ trÞ gÇn ®óng cña lêi gi¶i vµ ®¹o hµm cÊp 1 t¹i
®iÓm tn . NÕu ma trËn hÖ sè A cã d¹ng tam gi¸c d−íi chÆt, tøc lµ c¸c phÇn
tö thuéc ®−êng chÐo chÝnh vµ phÝa trªn ®−êng chÐo chÝnh b»ng kh«ng, th×
ph−¬ng ph¸p (1.1), ( hoÆc (1.2), (1.3)) ®−îc gäi lµ ph−¬ng ph¸p RKN hiÓn
(Explicit RKN - ERKN). Trong tr−êng hîp ng−îc l¹i, chóng ®−îc gäi lµ
ph−¬ng ph¸p RKN Èn (Implicit RKN - IRKN).
§Ó ®¬n gi¶n cho tr×nh bµy, trong luËn ¸n nµy, tuú tõng tr−êng hîp cô thÓ,
bµi to¸n IVPs (1) cã thÓ lµ bµi to¸n v« h−íng (N = 1) hoÆc hÖ ph−¬ng
tr×nh (N > 1). Chó ý r»ng, viÖc xÐt bµi to¸n nµo kh«ng ¶nh h−ëng tíi tÝnh
tæng qu¸t cña ph−¬ng ph¸p.
1.1.1 CÊp chÝnh x¸c cña ph−¬ng ph¸p RKN
§Ó hiÓu mét c¸ch thèng nhÊt thÕ nµo lµ cÊp chÝnh x¸c cña mét ph−¬ng
ph¸p RKN chóng ta sö dông c¸c ®Þnh nghÜa sau (cã thÓ xem trong [33]):
§Þnh nghÜa 1.1.1 NÕu y(t) lµ nghiÖm chÝnh x¸c ®Þa ph−¬ng cña (1), tho¶
m·n ®iÒu kiÖn y(tn ) = un , y (tn ) = un vµ
||y(tn+1 ) − un+1 || = O(hp1 +1 ),
||y (tn+1 ) − un+1 || = O(hp2 +1 ),
th× ph−¬ng ph¸p RKN (1.1) ®−îc gäi lµ ph−¬ng ph¸p cã cÊp chÝnh x¸c
(order) p víi p = min(p1 , p2 ).
6
§Þnh nghÜa 1.1.2 Víi gi¶ thiÕt nh− trªn, nÕu
||Un (tn+1 ) − un e − hun c − h2 Af (tn e + hc, Un (tn+1 ))|| = O(hp3 +1 ),
ë ®©y Un (tn+1 ) = [y(tn + c1 h), . . . , y(tn + cs h)]T ,
th× ph−¬ng ph¸p RKN (1.1) ®−îc gäi lµ cã cÊp chÝnh x¸c nÊc (stage order)
b»ng r víi r = min(p, p3 ).
CÊp chÝnh x¸c nÊc cña c¸c ph−¬ng ph¸p IRKN cã vai trß rÊt quan träng
khi chóng ta gi¶i c¸c bµi to¸n c−¬ng. C¸c ph−¬ng ph¸p IRKN d¹ng trïng
khíp (collocation) lµ c¸c ph−¬ng ph¸p cã cÊp chÝnh x¸c nÊc cao (môc 1.2).
1.1.2 TÝnh æn ®Þnh cña c¸c ph−¬ng ph¸p RKN
Còng nh− c¸c ph−¬ng ph¸p sè kh¸c, tÝnh chÊt æn ®Þnh cña c¸c ph−¬ng
ph¸p RKN lµ mét trong nh÷ng ®Æc tr−ng quan träng cña mét ph−¬ng ph¸p
sè. Ng−êi ta nghiªn cøu sù æn ®Þnh (tuyÕn tÝnh) cña ph−¬ng ph¸p RKN
(1.1) b»ng c¸ch ¸p dông nã vµo viÖc gi¶i ph−¬ng tr×nh thö v« h−íng tuyÕn
tÝnh y (t) = λy(t), trong ®ã λ biÕn ®æi trªn phæ cña ma trËn Jacobi ∂f /∂y.
¸p dông ph−¬ng ph¸p (1.3) vµo ph−¬ng tr×nh thö, ta nhËn ®−îc hÖ thøc
truy håi sau:
u
u
n+1
n
hun+1 = M (z) hun ,
T
−1
T
−1
1
+
zb
[I
−
zA]
e
1
+
zb
[I
−
zA]
c
M(z) =
.
zdT [I − zA]−1 e
1 + zdT [I − zA]−1 c
ë ®©y z = λh2 , víi λ < 0. Chó ý lµ ma trËn I − zA lu«n kh¶ nghÞch
víi |z| ®ñ nhá. Sù æn ®Þnh cña ph−¬ng ph¸p RKN (1.3) ®−îc ®Æc tr−ng
bëi ma trËn khuÕch ®¹i M(z). Hµm æn ®Þnh R(z) cña ph−¬ng ph¸p RKN
®−îc x¸c ®Þnh b»ng b¸n kÝnh phæ cña ma trËn khuÕch ®¹i M(z), tøc lµ:
R(z) = ρ(M (z)).
7
§Þnh nghÜa 1.1.3 Ph−¬ng ph¸p RKN ®−îc gäi lµ æn ®Þnh tuyÖt ®èi (A-æn
®Þnh) nÕu R(z) 1 víi mäi z < 0, æn ®Þnh tuyÖt ®èi m¹nh (A-æn ®Þnh
m¹nh) nÕu cã thªm ®iÒu kiÖn R(−∞) < 1, L-æn ®Þnh nÕu æn ®Þnh tuyÖt
®èi vµ cã thªm ®iÒu kiÖn R(−∞) = 0, P-æn ®Þnh nÕu hai gi¸ trÞ riªng
cña ma trËn khuÕch ®¹i kh«ng ph¶i lµ sè thùc vµ cã modul b»ng 1 víi
mäi z < 0.
Gi¸ trÞ d−¬ng lín nhÊt β ®Ó cho R(z) 1 víi mäi z n»m trong kho¶ng
(−β, 0) ®−îc gäi lµ biªn æn ®Þnh cña ph−¬ng ph¸p. Nh− vËy ph−¬ng ph¸p
RKN æn ®Þnh tuyÖt ®èi t−¬ng ®−¬ng víi β = ∞.
1.2 C¸c ph−¬ng ph¸p IRKN d¹ng trïng khíp
Sau ®©y chóng ta nghiªn cøu c¸ch x©y dùng c¸c ph−¬ng ph¸p IRKN
d¹ng trïng khíp. CÇn ph©n biÖt hai líp ph−¬ng ph¸p IRKN d¹ng trïng
khíp, ®ã lµ líp ph−¬ng ph¸p IRKN d¹ng trïng khíp gi¸n tiÕp (indirect
IRKN collocation type) vµ líp ph−¬ng ph¸p IRKN d¹ng trïng khíp trùc
tiÕp (direct IRKN collocation type) mµ chóng ®−îc gäi t¾t t−¬ng øng lµ c¸c
ph−¬ng ph¸p IRKN gi¸n tiÕp vµ ph−¬ng ph¸p IRKN trùc tiÕp.
1.2.1 C¸c ph−¬ng ph¸p IRKN d¹ng trïng khíp gi¸n tiÕp
Ph−¬ng ph¸p IRKN gi¸n tiÕp ®−îc x©y dùng b»ng c¸ch ¸p dông mét
ph−¬ng ph¸p IRK d¹ng trïng khíp vµo bµi to¸n (1) ®· ®−îc chuyÓn thµnh
bµi to¸n t−¬ng ®−¬ng cña hÖ ph−¬ng tr×nh vi ph©n cÊp 1 (xem [32, 1]):
y = u(t), u (t) = f(t, y(t)), y(t0 ) = y0 , u(t0 ) = u0 = y0 .
B¶ng Butcher cña ph−¬ng ph¸p IRKN trïng khíp gi¸n tiÕp:
c
(A)2
bT .A
bT
8
C¸c kÕt qu¶ nghiªn cøu cho thÊy, nÕu ph−¬ng ph¸p IRK gèc cã cÊp
chÝnh x¸c p víi k quan hÖ Èn th× ph−¬ng ph¸p IRKN d¹ng trïng khíp gi¸n
tiÕp còng cã cÊp chÝnh x¸c p vµ còng víi k quan hÖ Èn. B©y giê ta gi¶
sö r»ng ph−¬ng ph¸p IRK gèc lµ ph−¬ng ph¸p d¹ng trïng khíp dùa trªn s
®iÓm mèc ph©n biÖt (s nÊc), khi ®ã:
A = (aij ) = (αj (ci )), d = (di ) = αj (1)
αj (x) =
x
0
s
x − ci
Lj (ξ)dξ, Lj (x) =
, j = 1, ...s
cj − ci
(1.5)
i=1,i=j
ë ®©y Lj (x) lµ ®a thøc Lagrange víi s ®iÓm mèc ci , i = 1, . . . , s, kÕt qu¶
chÝnh vÒ vÊn ®Ò nµy thÓ hiÖn ë ®Þnh lÝ sau:
§Þnh lÝ 1.2.1 Ph−¬ng ph¸p IRKN d¹ng trïng khíp gi¸n tiÕp x¸c ®Þnh
bëi (1.5) cã cÊp chÝnh x¸c toµn côc p = r = s víi mäi vÐc t¬ trïng khíp c
cã c¸c thµnh phÇn ph©n biÖt. Cã thÓ cã p = s + q nÕu ®iÒu kiÖn trùc giao
sau ®©y ®−îc tho¶ m·n
Pj (1) = 0, Pj (x) =
x
ξ
j−1
s
(ξ − ci )dξ, j = 1...q
(1.6)
i=1
0
1.2.2 C¸c ph−¬ng ph¸p IRKN d¹ng trïng khíp trùc tiÕp
Ph−¬ng ph¸p IRKN trïng khíp trùc tiÕp ®−îc x©y dùng mét c¸ch trùc
tiÕp cho hÖ ph−¬ng tr×nh vi ph©n cÊp hai chø kh«ng chuyÓn vÒ hÖ ph−¬ng
tr×nh cÊp mét. ViÖc x¸c ®Þnh bé hÖ sè cña ph−¬ng ph¸p IRKN trùc tiÕp
theo kÜ thuËt trïng khíp (collocation techniques) ®−îc nghiªn cøu mét c¸ch
®Çy ®ñ trong [33] (xem thªm [1]).
C¸c kÕt luËn ®−îc rót ra tõ c¸c kÕt qu¶ nghiªn cøu vµ so s¸nh hai
ph−¬ng ph¸p IRKN gi¸n tiÕp vµ IRKN trùc tiÕp nh− sau:
- TÝnh chÊt héi tô trong c¸c ph−¬ng ph¸p IRKN gi¸n tiÕp vµ trùc tiÕp
®Òu rÊt tèt, chóng ta cã thÓ nhËn ®−îc siªu héi tô (super convergence) tøc
lµ sù héi tô nhanh h¬n b×nh th−êng trong c¶ hai ph−¬ng ph¸p nµy (xem [1]).
9
- Ph−¬ng ph¸p IRKN trùc tiÕp cã cÊp chÝnh x¸c nÊc (stage order) cao
h¬n cÊp chÝnh x¸c nÊc cña ph−¬ng ph¸p IRKN gi¸n tiÕp cã cïng cÊp chÝnh
x¸c.
- TÝnh chÊt æn ®Þnh cña c¸c ph−¬ng ph¸p IRKN trùc tiÕp kÐm h¬n so
víi c¸c ph−¬ng ph¸p IRKN gi¸n tiÕp.
§Ó kh¾c phôc nh−îc ®iÓm thiÕu æn ®Þnh cña ph−¬ng ph¸p IRKN trùc
tiÕp, c¸c t¸c gi¶ cña [33] còng ®· ®−a ra mét sè gi¶i ph¸p nh− kÜ thuËt æn
®Þnh ho¸ (stabilizing) ®Ó chuyÓn c¸c ph−¬ng ph¸p IRKN trùc tiÕp æn ®Þnh
cã ®iÒu kiÖn thµnh ph−¬ng ph¸p æn ®Þnh tuyÖt ®èi. Mét gi¶i ph¸p kh¸c n÷a
lµ kÜ thuËt x©y dùng c¸c ph−¬ng ph¸p IRKN ®a hîp (Composite IRKN) æn
®Þnh tuyÖt ®èi m¹nh (xem cô thÓ trong [33, 1]). Víi c¸c kÜ thuËt nµy chóng
ta cã thÓ x©y dùng ®−îc c¸c ph−¬ng ph¸p IRKN trùc tiÕp æn ®Þnh tèt vµ
cã cÊp chÝnh x¸c nÊc cao - mét tÝnh chÊt rÊt cÇn thiÕt khi gi¶i c¸c bµi to¸n
c−¬ng (stiff problems).
1.2.3 X¸c ®Þnh hÖ sè cña ph−¬ng ph¸p RKN
Ph−¬ng ph¸p RKN hoµn toµn ®−îc x¸c ®Þnh bëi ma trËn A vµ c¸c vÐc t¬
b, c, d. Trong môc nµy ta biÓu diÔn A, b, d qua c. Gi¶ sö (1.3a) cã cÊp
chÝnh x¸c p, thay vµo (1.3a) gi¸ trÞ chÝnh x¸c t−¬ng øng, ta tÝnh ®−îc ma
trËn vµ vÐc t¬ hÖ sè:
TÝnh ma trËn A
||y(etn + ch) − ey(tn ) − hcy (tn ) − h2 Ay (etn + ch)|| = O(hp+1 ).
Khai triÓn Taylor c¸c hµm y(etn + ch), y (etn + ch) t¹i l©n cËn ®iÓm tn ,
ta cã:
p
ck hk
y(etn + ch) =
y (k) (tn )
+ O(hp+1 ).
k!
2
h y (etn + ch) =
k=0
p
k=2
ck−2 hk
Ay (tn )
+ O(hp+1 ).
(k − 2)!
(k)
10
⇒
||
p
ck
k=2
ck−2
(k)
−A
y (tn )|| = O(hp+1 ).
k!
(k − 2)!
¸p dông ®iÒu kiÖn cÊp chÝnh x¸c, ta cã
ck
ck−2
−A
= 0,
k!
(k − 2)!
k = 1, ..., p − 1.
ck+1
Hay lµ:
− Ack−1 = 0, k = 1, ..., p − 1.
(k + 1)k
c2
cs+1
−
, R = e, c, ..., cs−1 , víi p=s+1.
§Æt P =
(k + 1)k (s + 1)s
⇒ P − AQ = O, ⇒ A = P R−1 .
TÝnh c¸c vÐc t¬ b, d
VÐc t¬ b còng ®−îc tÝnh theo ®iÒu kiÖn cÊp chÝnh x¸c
||y(tn+1 ) − yn+1 || = O(hp+1 ). Tõ (1.3b), ta cã
||y(tn+1 − y(tn ) − hy (tn ) − h2 bT y (etn + ch)|| = O(hp+1 ).
Khai triÓn Taylor
y(tn + h) =
p
k=0
⇒
||
p
k=2
hk
y (tn) + O(hp+1 ),
k!
(k)
k−2
1
T c
−b
y (k) (tn )|| = O(hp+1 ).
k!
(k − 2)!
¸p dông ®iÒu kiÖn cÊp chÝnh x¸c, dÉn tíi
1
bT ck−2
1
−
= 0, ⇒
− bT ck−2 = 0, k = 2, ..., p,
k! (k − 2)!
k(k − 1)
1
1
víi p = s + 1, ®Æt g =
, ...,
,
1.2
s(s + 1)
⇒ b = gR−1 .
T−¬ng tù, ta còng tÝnh ®−îc vÐc t¬ d:
1
1
d = kR−1 , víi k = 1, , ..., .
2
s
11
1.3 C¸c ph−¬ng ph¸p PIRKN
Mét trong c¸c ph−¬ng ph¸p song song d¹ng RKN ®Çu tiªn ®−îc x©y
dùng trªn c¬ së phÐp lÆp hiÓn kiÓu dù b¸o-hiÖu chØnh (explicit PC iterations)
víi c«ng viÖc tÝnh to¸n khi thùc hiÖn phÐp lÆp cã thÓ ®−îc tiÕn hµnh song
song trªn c¸c bé xö lÝ kh¸c nhau cña mét siªu m¸y tÝnh. Do ®ã mµ c¸c
ph−¬ng ph¸p nµy cã tªn lµ c¸c ph−¬ng ph¸p lÆp song song d¹ng RKN
(Parallel Iterated RKN methods) vµ viÕt t¾t lµ PIRKN (xem [7]).
XuÊt ph¸t tõ ph−¬ng ph¸p IRKN (1.3), l−îc ®å cña mét ph−¬ng ph¸p
PIRKN ®−îc x©y dùng cã d¹ng nh− sau:
Yn(0) = eyn + hcyn ,
(1.7a)
Yn(j) = eyn + hcyn + h2 Af (tn e + hc, Yn(j−1) ),
(1.7b)
j = 1, . . . , m,
yn+1 = yn + hyn + h2 bT f (tn e + hc, Yn(m) ),
(1.7c)
yn+1
= yn + hdT f (tn e + hc, Yn(m) ).
(1.7d)
VÒ cÊu tróc th× ph−¬ng ph¸p PIRKN lµ mét ph−¬ng ph¸p dù b¸o-hiÖu
chØnh víi cÆp dù b¸o (1.7a) vµ hiÖu chØnh (1.7b). DÔ thÊy r»ng ph−¬ng ph¸p
PIRKN (1.7) chÝnh lµ mét ph−¬ng ph¸p ERKN thùc sù víi b¶ng Butcher
cã d¹ng nh− sau:
0(j = 0)
c(j = 1)
c(j = 2)
.
.
.
c(j = m)
O
A
O
O
A
O
.
O O O
0T 0T 0T
0T 0T 0T
.
.
...
...
...
.
.
.
O A O
0T 0T bT
0T 0T dT
trong ®ã 0 lµ vÐc t¬ s chiÒu víi c¸c thµnh phÇn b»ng 0, O lµ ma trËn s × s
chiÒu còng víi c¸c phÇn tö b»ng 0
Khèi l−îng chÝnh khi gi¶i l−îc ®å trªn lµ tÝnh to¸n vÐc t¬ hµm vÕ
(j)
(j)
(j)
ph¶i f (tn e + hc, Yn ) = [f (tn + hc1 , Yn,1 ), . . . , f (tn + hcs , Yn,s )] víi
12
j = 1, . . . , m. §Ó ý thÊy r»ng t¹i mçi b−íc s thµnh phÇn trªn cã thÓ tÝnh
to¸n song song trªn s bé xö lÝ cña mét siªu m¸y tÝnh, khi ®ã, thêi gian tÝnh
to¸n cÇn thiÕt cña ph−¬ng ph¸p PIRKN t−¬ng ®−¬ng víi m + 1 lÇn tÝnh
to¸n hµm vÕ ph¶i f trªn m¸y tÝnh ”truyÒn thèng” cã mét bé xö lÝ. Chóng
ta gäi l−îc ®å (1.7) lµ ph−¬ng ph¸p PIRKN s qu¸ tr×nh.
1.3.1 CÊp chÝnh x¸c cña c¸c ph−¬ng ph¸p PIRKN
§Ó ý r»ng ph−¬ng ph¸p dù b¸o (1.7a) cã cÊp chÝnh x¸c b»ng 1, tøc lµ
(0)
Un − Yn
∞ = O(h2 ) ta cã c¸c ®¸nh gi¸ sai sè lÆp sau ®©y:
||Un − Yn(m) || = O(h2m+2 ),
un+1 − yn+1 = O(h2m+4 ),
un+1 − yn+1
= O(h2m+3 ).
(1.8a)
(1.8b)
(1.8c)
víi Un , un+1 , un+1 ®−îc tÝnh to¸n b»ng ph−¬ng ph¸p hiÖu chØnh (1.3).
NÕu ph−¬ng ph¸p hiÖu chØnh cã cÊp chÝnh x¸c p th× ta cã c¸c ®¸nh gi¸ sau
vÒ sai sè cña ph−¬ng ph¸p PIRKN (1.7)
y(tn+1 ) − yn+1 = y(tn+1 ) − un+1 + un+1 − yn+1
y (tn+1 ) − yn+1
= O(hp+1 ) + O(h2m+4 ),
= y (tn+1 ) − un+1 + un+1 − yn+1
= O(hp+1 ) + O(h2m+3 ).
(1.9a)
(1.9b)
Tõ c¸c ®¸nh gi¸ sai sè lÆp (iteration error) ë trªn cña ph−¬ng ph¸p
PIRKN ta cã §Þnh lÝ sau vÒ cÊp chÝnh x¸c cña ph−¬ng ph¸p PIRKN
(xem [7]):
§Þnh lÝ 1.3.1 [1, §Þnh lÝ 2.1] Gi¶ sö ph−¬ng ph¸p hiÖu chØnh (1.3) cã cÊp
chÝnh x¸c p. Khi ®ã trªn mét m¸y tÝnh song song s bé xö lÝ, ph−¬ng
ph¸p PIRKN, (1.7) lµ mét ph−¬ng ph¸p ERKN cã cÊp chÝnh x¸c p∗ =
min{p, 2m + 2} víi m + 1 lÇn tÝnh to¸n hµm vÕ ph¶i ë mçi b−íc.
Tõ §Þnh lÝ 1.3.1 ta thÊy cÊp chÝnh x¸c p∗ cña ph−¬ng ph¸p PIRKN (1.7)
kh«ng thÓ nµo v−ît qu¸ cÊp chÝnh x¸c p cña ph−¬ng ph¸p hiÖu chØnh (1.3).
13
- Xem thêm -