Tài liệu Một số phương pháp song song giải hệ phương trình vi phân

Môc lôc Më ®Çu ..................................................................................................... 1 Ch−¬ng 1 Tæng quan vÒ c¸c ph−¬ng ph¸p Runge-Kutta 1.1. C¸c kh¸i niÖm c¬ b¶n cña ph−¬ng ph¸p Runge-Kutta (RK)................ .8 1.1.1. TÝnh æn ®Þnh cña ph−¬ng ph¸p Runge-Kutta (RK) ................... 10 1.1.2. CÊp chÝnh x¸c cña ph−¬ng ph¸p Runge-Kutta .......................... 12 1.2. C¸c ph−¬ng ph¸p Runge-Kutta hiÓn (ERK)......................................... 13 1.3. C¸c ph−¬ng ph¸p Runge-Kutta d¹ng trïng khíp ................................. 16 1.4. C¸c ph−¬ng ph¸p lÆp song song d¹ng Runge-Kutta (PIRK)................ 19 1.4.1. Sù æn ®Þnh cña c¸c ph−¬ng ph¸p PIRK ..................................... 22 1.4.2. Sù héi tô cña c¸c ph−¬ng ph¸p PIRK ....................................... 23 1.4.3. Mét sè ph−¬ng ph¸p PIRK kh¸c................................................ 23 1.5. KÕt luËn ................................................................................................ 25 Ch−¬ng 2 C¸c ph−¬ng ph¸p lÆp song song dù b¸o-hiÖu chØnh D¹ng Runge-Kutta liªn tôc 2.1. C¸c ph−¬ng ph¸p hiÖu chØnh RK liªn tôc............................................. 28 2.2. C¸c ph−¬ng ph¸p PIRKC ..................................................................... 32 2.2.1. Tèc ®é héi tô.............................................................................. 35 2.2.2. MiÒn æn ®Þnh.............................................................................. 36 2.3. C¸c thö nghiÖm sè ................................................................................ 37 2.3.1. So s¸nh víi c¸c ph−¬ng ph¸p song song.................................... 39 2.3.1.1. Bµi to¸n hai vËt thÓ ............................................................ 40 2.3.1.2. Bµi to¸n Fehlberg................................................................ 41 2.3.1.3. Bµi to¸n chuyÓn ®éng cña vËt thÓ r¾n kh«ng cã t¸c ®éng cña ngo¹i lùc................................................................................................ 41 2.3.2. So s¸nh víi c¸c ph−¬ng ph¸p tuÇn tù......................................... 42 2.4. KÕt luËn ................................................................................................ 43 i Ch−¬ng 3 C¸c ph−¬ng ph¸p lÆp song song Gi¶ Runge-Kutta hai b−íc 3.1. C¸c ph−¬ng ph¸p hiÖu chØnh gi¶ Runge-Kutta hai b−íc (c¸c ph−¬ng ph¸p PTRK)................................................................................................. 45 3.2. C¸c ph−¬ng ph¸p lÆp song song gi¶ RK hai b−íc (c¸c ph−¬ng ph¸p IPIPTRK)..................................................................................................... 50 3.2.1. C¸c ®iÒu kiÖn cÊp cho c«ng thøc dù b¸o ................................... 51 3.2.2. Tèc ®é héi tô.............................................................................. 53 3.2.3. MiÒn æn ®Þnh.............................................................................. 54 3.3. C¸c thö nghiÖm sè ................................................................................ 56 3.3.1. So s¸nh víi c¸c ph−¬ng ph¸p song song.................................... 59 3.3.1.1. Bµi to¸n hai vËt thÓ ............................................................. 60 3.3.1.2. Bµi to¸n Fehlberg................................................................ 60 3.3.1.3. Bµi to¸n chuyÓn ®éng cña vËt thÓ r¾n kh«ng cã t¸c ®éng cña ngo¹i lùc................................................................................................ 61 3.3.2. So s¸nh víi c¸c ph−¬ng ph¸p tuÇn tù......................................... 62 3.4. KÕt luËn ................................................................................................ 63 Ch−¬ng 4 C¸c ph−¬ng ph¸p lÆp song song dù b¸o-hiÖu chØnh D¹ng Runge-kutta hai b−íc mét liªn tôc 4.1. C¸c ph−¬ng ph¸p dù b¸o-hiÖu chØnh d¹ng Runge-Kutta hai b−íc mét liªn tôc ......................................................................................................... 65 4.2. C¸c ph−¬ng ph¸p lÆp song song dù b¸o-hiÖu chØnh d¹ng Runge-Kutta hai b−íc mét liªn tôc ( c¸c ph−¬ng ph¸p TBTPIRKC) ............................... 68 4.2.1. Tèc ®é héi tô.............................................................................. 70 4.2.2. MiÒn æn ®Þnh.............................................................................. 71 4.3. C¸c thö nghiÖm sè ................................................................................ 73 4.3.1. So s¸nh víi c¸c ph−¬ng ph¸p song song.................................... 75 4.3.1.1. Bµi to¸n hai vËt thÓ ............................................................. 75 ii 4.3.1.2. Bµi to¸n Fehlberg ............................................................... 75 4.3.1.3. Bµi to¸n chuyÓn ®éng cña vËt thÓ r¾n kh«ng cã t¸c ®éng cña ngo¹i lùc................................................................................................ 76 4.3.2. So s¸nh víi c¸c ph−¬ng ph¸p tuÇn tù......................................... 77 4.4. KÕt luËn ................................................................................................ 77 KÕt luËn cña luËn ¸n ............................................................. 79 Danh môc c¸c c«ng tr×nh ®· c«ng bè............................. 80 Tµi liÖu tham kh¶o ................................................................... 82 iii Danh môc c¸c ký hiÖu vµ ch÷ viÕt t¾t 1. C¸c ký hiÖu := ®Þnh nghÜa ≈ xÊp xØ sè \d kh«ng gian vÐct¬ thùc d - chiÒu ^ tËp c¸c sè phøc ^− tËp c¸c sè phøc víi phÇn thùc ©m f ( j ) ®¹o hµm bËc j cña hµm f J Jacobian cña f QT ma trËn chuyÓn vÞ cña Q Q −1 ma trËn nghÞch ®¶o cña Q I , I d ma trËn ®¬n vÞ, ma trËn c¸c thµnh phÇn b»ng 1 (cÊp dxd ) ei thµnh phÇn thø i cña vÐct¬ c¬ së 0,0rxs vÐc t¬ kh«ng, ma trËn kh«ng (kÝch th−íc rxs) Q ⊗ A tÝch tenx¬ cña ma trËn Q víi ma trËn A σ ( A) phæ cña ma trËn A ρ ( A) b¸n kÝnh phæ cña ma trËn A ρ (∂f / ∂y ) b¸n kÝnh phæ cña ma trËn Jacobian cña hµm f ( y ), f , y ∈\ d .∞ chuÈn max Re( z ) phÇn thùc cña sè phøc z Im( z ) phÇn ¶o cña sè phøc z 2. C¸c ch÷ viÕt t¾t ERK (Explicit Runge-Kutta method) ph−¬ng ph¸p Runge-Kutta hiÓn IRK (Implicit Runge-Kutta method) ph−¬ng ph¸p Runge-Kutta Èn iv IPIPTRK (Improved parallel-iterated pseudo two-step Runge-Kutta methods) c¸c ph−¬ng ph¸p lÆp song song gi¶ Runge-Kutta hai b−íc c¶i tiÕn IVPs (Initial Value Problems) c¸c bµi to¸n gi¸ trÞ ®Çu (bµi to¸n Cauchy) ODEs (Ordinary differential equations) c¸c ph−¬ng tr×nh vi ph©n th−êng PIRK (Parallel-iterated Runge-Kutta method) ph−¬ng ph¸p lÆp song song d¹ng Runge-Kutta PIRKC (Parallel-iterated Runge-Kutta method with continuous output formulas) c¸c ph−¬ng ph¸p lÆp song song d¹ng Runge-Kutta liªn tôc PTRK (Pseudo Two-step Runge-Kutta method) c¸c ph−¬ng ph¸p gi¶ hai b−íc d¹ng Runge-Kutta PC (Predictor-corrector method) ph−¬ng ph¸p dù b¸o-hiÖu chØnh RungeKutta TBTRKC (Continuous twostep-by-twostep Runge-Kutta method) c¸c ph−¬ng ph¸p d¹ng Runge-Kutta hai b−íc mét liªn tôc TBTPIRKC (Twostep-by-twostep PIRK-type PC methods with continuous output formulas) c¸c ph−¬ng ph¸p lÆp song d¹ng Runge-Kutta hai b−íc mét liªn tôc v Danh môc c¸c b¶ng B¶ng 1.1. CÊp chÝnh x¸c cña c¸c ph−¬ng ph¸p Runge-Kutta hiÓn…………15 B¶ng 1.2. Mét sè ph−¬ng ph¸p Runge-Kutta d¹ng trïng khíp……………20 B¶ng 2.1. C¸c cÆp æn ®Þnh ( β (m) , β re im (m) ) cho c¸c ph−¬ng ph¸p PIRKC cÊp p kh¸c nhau…………….………………………………………..38 B¶ng 2.2. C¸c gi¸ trÞ NCD/ N seq cho bµi to¸n (2.3.2) nhËn ®−îc b»ng c¸c ph−¬ng ph¸p song song PC cÊp p kh¸c nhau ……………………….40 B¶ng 2.3. C¸c gi¸ trÞ NCD / N seq cho bµi to¸n (2.3.3) nhËn ®−îc b»ng c¸c ph−¬ng ph¸p song song PC cÊp p kh¸c nhau …………….…………..41 B¶ng 2.4. C¸c gi¸ trÞ NCD/ N seq cho bµi to¸n (2.3.4) nhËn ®−îc b»ng c¸c ph−¬ng ph¸p song song PC cÊp p kh¸c nhau …………………….….42 B¶ng 2.5. So s¸nh víi c¸c ph−¬ng ph¸p tuÇn tù cho bµi to¸n (2.2.3)………43 B¶ng 3.1. C¸c nh©n tè héi tô cho c¸c ph−¬ng ph¸p song song PC cÊp p kh¸c nhau. ………………………………………………………………….58 B¶ng 3.2. C¸c cÆp æn ®Þnh ( β (m) , β (m) ) cho c¸c ph−¬ng ph¸p IPIPTRK re im cÊp p kh¸c nhau. …………………………………………………….58 B¶ng 3.3. C¸c gi¸ trÞ NCD / N seq cho bµi to¸n (2.3.2) cña c¸c ph−¬ng ph¸p song song PC cÊp p kh¸c nhau víi pr bé xö lý…... ………….…...60 B¶ng 3.4. C¸c gi¸ trÞ NCD / N seq cho bµi to¸n (2.3.3) cña c¸c ph−¬ng ph¸p PC song song cÊp p kh¸c nhau………………………………………61 B¶ng 3.5. C¸c gi¸ trÞ NCD / N seq cho bµi to¸n (2.3.4) cña c¸c ph−¬ng ph¸p PC song song cÊp p kh¸c nhau..……………………. ……………….61 vi B¶ng 3.6. So s¸nh víi c¸c ph−¬ng ph¸p tuÇn tù cho bµi to¸n (3.3.3). …….62 B¶ng 4.1. C¸c cÆp ( β (m), β (m)) cho c¸c ph−¬ng ph¸p TBTPIRKC re im cÊp p ……….…………………………………………………………74 B¶ng 4.2. C¸c gi¸ trÞ NCD / N seq cho bµi to¸n 2.3.2 nhËn ®−îc b»ng c¸c ph−¬ng ph¸p PC song song p ……………….. ………………………75 B¶ng 4.3. C¸c gi¸ trÞ NCD / N seq cho bµi to¸n 2.3.3 nhËn ®−îc b»ng c¸c ph−¬ng ph¸p PC song song p ………………………….…………….76 B¶ng 4.4. C¸c gi¸ trÞ NCD / N seq cho bµi to¸n 2.3.4 nhËn ®−îc b»ng c¸c ph−¬ng ph¸p PC song song cÊp p …………………….….…………..77 B¶ng 4.5. So s¸nh víi c¸c m· tuÇn tù víi bµi to¸n Fehlberg 2.3.3…….. ….78 vii Më ®Çu NhiÒu bµi to¸n trong c¸c lÜnh vùc khoa häc vµ kü thuËt ®−îc qui vÒ viÖc t×m nghiÖm hÖ ph−¬ng tr×nh vi ph©n tháa m·n mét sè ®iÒu kiÖn nµo ®ã (®iÒu kiÖn ban ®Çu, ®iÒu kiÖn biªn, v.v…). §a sè c¸c hÖ ph−¬ng tr×nh vi ph©n m« t¶ nh÷ng hÖ c¬ häc, vËt lý häc, ho¸ häc, sinh häc v.v… rÊt phøc t¹p, kh«ng cã hy väng gi¶i ®óng mµ th«ng th−êng chóng ta ph¶i gi¶i b»ng c¸c ph−¬ng ph¸p gÇn ®óng. C¸c ph−¬ng ph¸p sè lµ c¸c ph−¬ng ph¸p cã hiÖu qu¶ nhÊt khi gi¶i gÇn ®óng c¸c hÖ ph−¬ng tr×nh vi ph©n nµy (xem trong [1, tr. 145-150]. C¸c ph−¬ng ph¸p Runge-Kutta lµ c¸c ph−¬ng ph¸p sè kh¸ hoµn h¶o mµ c¸c ph−¬ng ph¸p kh¸c kh«ng cã nh− cÊp chÝnh x¸c cao, tÝnh æn ®Þnh rÊt tèt, h¬n n÷a nã cã kh¶ n¨ng song song hãa cao. V× thÕ ph−¬ng ph¸p RK ®−îc sù quan t©m nghiªn cøu cña nhiÒu nhµ to¸n häc trong lÜnh vùc gi¶i sè ph−¬ng tr×nh vi ph©n. ChÝnh v× vËy trong khu«n khæ cña luËn ¸n nµy chóng t«i nghiªn cøu vµ x©y dùng c¸c ph−¬ng ph¸p song song d¹ng Runge-Kutta ®Ó gi¶i c¸c bµi to¸n gi¸ trÞ ban ®Çu (IVPs) kh«ng c−¬ng cña hÖ ph−¬ng tr×nh vi ph©n d¹ng y ' (t ) = f (t, y (t )) , y, f ∈ \d , y (t0 ) = y0 , t 0 ≤ t ≤ T0 , (1) hoÆc d¹ng thuÇn nhÊt y ' (t ) = f ( y (t )) , y, f ∈ \d , y (t0 ) = y0 , t 0 ≤ t ≤ T0. Khi xÐt bµi to¸n Cauchy (IVPs) (1) chóng ta th−êng gi¶ thiÕt hµm vÕ ph¶i f (t , y ) lµ Lipschitz liªn tôc. Ta cã ®Þnh nghÜa sau. { } §Þnh nghÜa Ký hiÖu Ω = (t , y ) | t ≤ t ≤ T , y ∈ \d , hµm f (t , y ) ®−îc gäi lµ 0 0 Lipschitz liªn tôc nÕu: i) ∃ L > 0 sao cho ∀(t , y*),(t , y **) ∈Ω, th× f (t , y*) − f (t , y **) ≤ L y * − y ** , ii) Hµm f (t , y ) x¸c ®Þnh vµ liªn tôc víi ∀(t , y ) ∈Ω . §iÒu kiÖn i) ë ®Þnh nghÜa trªn gäi lµ ®iÒu kiÖn Lipschitz. Runge (1895) ®· më réng ph−¬ng ph¸p Euler b»ng c¸ch thªm vµo mét b−íc Euler vµo ®iÓm gi÷a cña ®o¹n tÝch ph©n, trong khi ®ã Kutta (1901) ®· 1 x©y dùng ph−¬ng ph¸p cÊp 3, cÊp 4 næi tiÕng trong ®ã ®¸nh gi¸ thªm hµm vÕ ph¶i t¹i ®iÓm gi÷a vµ ®iÓm cuèi cña b−íc tÝch ph©n (xem trong [7, tr. 45 – 46]) C¸c ph−¬ng ph¸p Runge-Kutta tæng qu¸t s − nÊc ®Ó gi¶i bµi to¸n (1) ®−îc x¸c ®Þnh nh− sau s = y + h ∑ aij f (t + c j h, Y ) , i = 1,...,s , n, i n n n, j Y (2) j =1 s yn + 1= yn + h ∑ b j f (tn + c j h, Yn, j ) , (3) j =1 trong ®ã ma trËn A = (aij ) sxs , c¸c vÐct¬ s − chiÒu c = (c ) vµ b = (b ) lµ i c¸c ma trËn vµ c¸c vÐct¬ tham sè cña ph−¬ng ph¸p. Y n, i i lµ c¸c vÐct¬ nÊc biÓu diÔn xÊp xØ lêi gi¶i chÝnh x¸c t¹i c¸c ®iÓm t + c h, i = 1,..., s , n Y n, i ≈ y(t + c h) , y ≈ y(t ), y n i n n n +1 ≈ y(t n +1 ), h = t n +1 i − t lµ ®é dµi b−íc. n NÕu A lµ ma trËn tam gi¸c d−íi chÆt th× ph−¬ng ph¸p (2)-(3) gäi lµ ph−¬ng ph¸p Runge-Kutta hiÓn (ERK), ng−îc l¹i lµ ph−¬ng ph¸p RungeKutta Èn (IRK). Trong (2)-(3) ®Ó x¸c ®Þnh ®−îc c¸c Y n, i ta ph¶i gi¶i s.d ph−¬ng tr×nh (hÇu hÕt lµ phi tuyÕn) kÝch th−íc s.d , v× thÕ cÇn ph¶i thùc hiÖn mét khèi l−îng tÝnh to¸n rÊt lín, ®Æc biÖt lµ trong tr−êng hîp ph−¬ng ph¸p Runge-Kutta Èn. ChÝnh v× vËy tr−íc ®©y khi c¸c ph−¬ng tiÖn tÝnh to¸n (chñ yÕu lµ m¸y tÝnh ®iÖn tö) ch−a ph¸t triÓn, c¸c ph−¬ng ph¸p Runge-Kutta ch−a ph¶i lµ phæ biÕn vµ ch−a ®−îc quan t©m nghiªn cøu nhiÒu. Sau khi Butcher (1976) x©y dùng ®−îc kü thuËt tÝnh to¸n rÊt hiÖu qu¶ b»ng c¸ch ¸nh x¹ ma trËn Runge-Kutta A vÒ d¹ng chuÈn t¾c Jordan (xem trong [9], [7, tr. 48-50]), th× t×nh h×nh ®· thay ®æi vµ c¸c ph−¬ng ph¸p IRK ®−îc quan t©m nghiªn cøu nhiÒu vµ trë nªn th«ng dông h¬n. Mét CODE tù ®éng viÕt b»ng ng«n ng÷ FORTRAN77 cã cÊp chÝnh x¸c b»ng 5 dùa trªn gi¶i ph¸p cña Butcher vµ ph−¬ng ph¸p IRK Radau IIA cã tªn lµ RADAU5 ®· ra ®êi (xem trong [29]). Khi gi¶i trùc tiÕp bµi to¸n (2)-(3) b»ng ph−¬ng ph¸p lÆp Newton c¶i tiÕn, ®Ó kh¾c phôc c¸c tÝnh to¸n víi chi phÝ cao khi sö dông ph©n tÝch LU , nhiÒu t¸c gi¶ ®· dùa trªn kü thuËt cña Butcher 2 ®Ó x©y dùng c¸c ph−¬ng ph¸p Runge-Kutta hiÖu qu¶ víi c¸c h¹n chÕ kh¸c nhau lªn cÊu tróc cña ma trËn A nh−: ma trËn A cã d¹ng tam gi¸c d−íi (c¸c ph−¬ng ph¸p ®−êng chÐo Èn (DIRKs)), c¸c phÇn tö trªn ®−êng chÐo chÝnh b»ng nhau (c¸c ph−¬ng ph¸p ®−êng chÐo Èn ®¬n (SDIRKs)); ma trËn A chØ cã mét ®iÓm phæ sao cho nã ®ång d¹ng víi ma trËn cã λ trªn ®−êng chÐo chÝnh vµ - λ trªn ®−êng chÐo phô (c¸c ph−¬ng ph¸p Èn ®¬n (SIRKs)), v.v…, (xem trong [7, tr. 49-51]). Mét trong nh÷ng líp ph−¬ng ph¸p Runge-Kutta cã cÊp chÝnh x¸c cao vµ tÝnh æn ®Þnh tèt lµ líp ph−¬ng ph¸p Runge-Kutta d¹ng trïng khíp. Sù trïng khíp lµ kü thuËt cã tõ l©u ®−îc øng dông réng r·i trong gi¶i tÝch sè. ý t−ëng c¬ b¶n cña kü thuËt nµy bao gåm mét hµm ®−îc chän (th−êng lµ ®a thøc) vµ tËp c¸c ®iÓm trïng khíp, sau ®ã yªu cÇu t¹i c¸c ®iÓm trïng khíp hµm ®−îc chän cã d¸ng ®iÖu biÕn ®æi gièng nh− hµm ch−a biÕt mµ chóng ta ®ang cè g¾ng xÊp xØ sè. Sù tù do trong lùa chän vÐct¬ c cho phÐp x©y dùng ®−îc c¸c ph−¬ng ph¸p IRK d¹ng trïng khíp s − nÊc víi cÊp chÝnh x¸c cao vµ tÝnh æn ®Þnh rÊt tèt nh− ph−¬ng ph¸p Gauss-Legendre cña Butcher cã cÊp chÝnh x¸c 2s , Randau IA vµ Randau IIA cña Axelsson vµ Ehle cã cÊp chÝnh x¸c 2s − 1 , ph−¬ng ph¸p Lobatto IIIA, IIIB, IIIC cña Ehle vµ Chipman cã cÊp chÝnh x¸c 2s − 2 víi c¸c thµnh phÇn cña vÐct¬ c lµ c¸c nghiÖm kh¸c nhau cña ®a thøc Legendre (xem trong [2], [28], [29]). Cïng víi sù ph¸t triÓn cña khoa vµ häc c«ng nghÖ, c¸c m« h×nh to¸n häc còng ngµy cµng phøc t¹p do sù phøc t¹p cña d÷ liÖu, do kÝch th−íc d÷ liÖu cña bµi to¸n qu¸ lín, do yªu cÇu vÒ ®é chÝnh x¸c cao vµ tèc ®é xö lý nhanh ®Æc biÖt khi ph¶i gi¶i quyÕt c¸c bµi to¸n trong chÕ ®é thêi gian thùc. ChÝnh v× thÕ c¸c ph−¬ng ph¸p sè kinh ®iÓn tr−íc ®©y ®−îc x©y dùng vµ nghiªn cøu ®Ó sö dông trªn c¸c m¸y tÝnh truyÒn thèng chØ cã mét bé xö lý tá ra kh«ng cßn h÷u hiÖu vµ ®¸p øng ®−îc c¸c yªu cÇu cña khoa häc tÝnh to¸n hiÖn ®¹i. Tõ khi m¸y tÝnh song song xuÊt hiÖn víi mét søc m¹nh tÝnh to¸n lín, t×nh h×nh ®· thay ®æi ®¸ng kÓ, rÊt nhiÒu ph−¬ng ph¸p song song d¹ng RungeKutta cã hiÖu qu¶, ®é chÝnh x¸c cao vµ tÝnh æn ®Þnh tèt ®· ®−îc ra ®êi. 3 ViÖc x©y dùng vµ nghiªn cøu c¸c ph−¬ng ph¸p tÝnh to¸n h÷u hiÖu- c¸c ph−¬ng ph¸p song song trªn c¸c m¸y tÝnh hiÖu n¨ng cao ®· trë thµnh nhu cÇu cÊp thiÕt trong gi¶i tÝch sè nãi chung vµ trong gi¶i tÝch sè cña ph−¬ng tr×nh vi ph©n nãi riªng. HÇu hÕt c¸c ph−¬ng ph¸p song song d¹ng Runge-Kutta ®−îc x©y dùng vµ nghiªn cøu trong nh÷ng n¨m gÇn ®©y ®Òu b¾t nguån tõ c¸c ph−¬ng ph¸p Runge-Kutta Èn (IRK) ®Ó gi¶i bµi to¸n (1). Trong sè c¸c c«ng tr×nh tiªu biÓu ph¶i kÓ ®Õn c¸c c«ng tr×nh cña c¸c nhµ to¸n häc lín nh− Bellen, Burrage, Butcher, Cash, Chu, Houwen, Gear, Jacson, Jacson, Lie, Miranker, Nosett, Iserles, v.v… qua c¸c c«ng tr×nh [3], [4], [5], [6], [7], [8], [11], [12], [13], [30], [31], [32], [33], [35], [36], [37], [38], [39], [42]. ë ViÖt Nam GS NguyÔn H÷u C«ng lµ mét trong nh÷ng ng−êi ®Çu tiªn nghiªn cøu vµ ®· ®¹t ®−îc nhiÒu kÕt qu¶ ®¸ng kÓ trong lÜnh vùc nµy. Chóng ta viÕt l¹i ph−¬ng ph¸p (2)-(3) d−íi d¹ng tÝch tenx¬ nh− sau y n +1 = y + h(bT ⊗ I )F(Y ) , R(Y ) = Y − h( A ⊗ I )F(Y ) − e ⊗ y . n n n n n n (4) Cã hai c¸ch kh¸c nhau ®Ó x©y dùng c¸c ph−¬ng ph¸p gi¶i bµi to¸n (4). Trong c¶ hai tr−êng hîp (4) ®−îc sö dông lµm ph−¬ng tr×nh dù b¸o-hiÖu chØnh (PC) mµ lêi gi¶i cña nã ®−îc xÊp xØ b»ng mét ph−¬ng ph¸p lÆp. Trong c¸ch thø nhÊt, kh«ng gi¶i trùc tiÕp (4) mµ sö dông ph−¬ng ph¸p lÆp tõng b−íc mét víi sè lÇn lÆp cè ®Þnh. Trong c¸ch thø hai, (4) ®−îc gi¶i trùc tiÕp b»ng ph−¬ng ph¸p lÆp Newton c¶i tiÕn, c¸c hÖ ph−¬ng tr×nh (chñ yÕu kh«ng tuyÕn tÝnh) trªn mçi b−íc lÆp Newton ®−îc gi¶i b»ng qu¸ tr×nh lÆp song song. Khi gi¶i ph−¬ng tr×nh hiÖu chØnh (4) b»ng ph−¬ng ph¸p Newton c¶i tiÕn ta x©y dùng l−îc ®å lÆp (xem trong [34, tr 1-14]) nh− sau ( I − A ⊗ hJ )(Y( j ) − Y( j − 1) ) = − R(Y( j − 1) ), j = 1,...,m, n n n n (5) trong ®ã J lµ Jacobian cña hµm vÕ ph¶i f t¹i t vµ Y(0) lµ gi¸ trÞ khëi t¹o n n n cña qu¸ tr×nh xö lý lÆp ®−îc x¸c ®Þnh b»ng c«ng thøc dù b¸o. NÕu ¸p dông c¸c ph−¬ng ph¸p gi¶i trùc tiÕp - ph−¬ng ph¸p Newton c¶i tiÕn th× gi¸ tÝnh to¸n th«ng th−êng qu¸ cao khi sd lín, do gi¸ cña viÖc ph©n tÝch LU cao. Dùa trªn kü thuËt cña Butcher, ®Ó gi¶m gi¸ tÝnh to¸n ph©n tÝch LU trªn mçi b−íc lÆp ta 4 sö dông ¸nh x¹ Y( j ) = (Q ⊗ I )U ( j ) ®Ó nhËn ®−îc hÖ ph−¬ng tr×nh tuyÕn tÝnh n n víi ma trËn hÖ sè cã d¹ng I − Q −1 AQ ⊗ hJ ( Q kh«ng suy biÕn). Tõ ®ã b»ng n c¸ch chän Q sao cho Q −1AQ lµ d¹ng ®−êng chÐo hoÆc d¹ng tam gi¸c, khi ®ã hÖ ph−¬ng tr×nh sau khi thùc hiÖn ¸nh x¹ cã thÓ chia thµnh c¸c hÖ con cã kÝch th−íc nhá h¬n sd vµ cã thÓ gi¶i song song. Trong [28] c¸c ph−¬ng ph¸p RK kiÓu Gauss-Legendre hoÆc kiÓu Radau ®Òu cã ma trËn Butcher víi chØ mét gi¸ trÞ riªng thùc. V× thÕ ta cã thÓ ®−a ®Õn c¸c hÖ ph−¬ng tr×nh phøc kÝch th−íc d hoÆc c¸c hÖ ph−¬ng tr×nh thùc víi kÝch th−íc 2 d. C¸ch thø hai, kh«ng gi¶i trùc tiÕp c¸c ph−¬ng tr×nh trong (4) mµ x©y dùng l−îc ®å lÆp sau ®©y (xem trong [34]) Y( 0 ) = e ⊗ y + h( B ⊗ I ) F (Y(0) ) + h(C ⊗ I ) F (e ⊗ y ) , n −1 n n−1 n Y( j ) = e ⊗ y n −1 n (6) + h( B ⊗ I ) F (Y( j ) ) + h(( A − B ) ⊗ I ) F (Y( j − 1) ), n n (7) j = 1, ..., m, y =y n n −1 + h(bT ⊗ I ) F (Yn( m) ) , (8) trong ®ã B vµ C lµ c¸c ma trËn tù chän hîp lý vµ m lµ sè nguyªn d−¬ng cè ®Þnh. C¸c ph−¬ng ph¸p nµy gäi lµ ph−¬ng ph¸p lÆp víi sè lÇn lÆp cè ®Þnh. Khi nghiªn cøu c¸c ph−¬ng ph¸p (6)-(8) ta th−êng cè g¾ng x©y dùng c¸c dù b¸o Y(0) cã cÊp chÝnh x¸c cao ®Ó gi¶m sè lÇn tÝnh to¸n hµm vÕ ph¶i. n Trong tr−êng hîp B = C = 0 chóng ta nhËn ®−îc líp c¸c ph−¬ng ph¸p lÆp song song d¹ng RK (c¸c ph−¬ng ph¸p PIRK) s.(m + 1) nÊc víi sè lÇn tÝnh to¸n hµm vÕ ph¶i s* = m + 1 . Khi B lµ ma trËn ®−êng chÐo D ta nhËn ®−îc líp c¸c ph−¬ng ph¸p ®−êng chÐo (xem [34, tr. 4-13]). Víi sù ra ®êi cña m¸y tÝnh song song vµ c¸c phÇn mÒm tÝnh to¸n tù ®éng cã hiÖu qu¶, c¸c ph−¬ng ph¸p song song d¹ng Runge-Kutta ®ang trë thµnh c¸c ph−¬ng ph¸p sè cã hiÖu qu¶ trong lÜnh vùc gi¶i tÝch sè cña ph−¬ng tr×nh vi ph©n vµ khoa häc tÝnh to¸n hiÖn ®¹i. 5 X©y dùng c¸c ph−¬ng ph¸p song song d¹ng Runge-Kutta míi cã hiÖu qu¶ ®ang lµ mèi quan t©m lín cña nhiÒu nhµ to¸n häc trong lÜnh vùc gi¶i tÝch sè cña ph−¬ng tr×nh vi ph©n. LuËn ¸n cña chóng t«i còng kh«ng n»m ngoµi môc ®Ých trªn lµ nghiªn cøu vµ x©y dùng c¸c ph−¬ng ph¸p song song d¹ng Runge-Kutta míi cã hiÖu qu¶ nh»m gãp phÇn vµo lÜnh vùc nghiªn cøu thêi sù nµy. Ngoµi 2 phÇn më ®Çu vµ kÕt luËn, luËn ¸n ®−îc tr×nh bµy thµnh bèn ch−¬ng. Ch−¬ng 1 dµnh cho viÖc tr×nh bµy tæng quan c¸c ph−¬ng ph¸p RK, giíi thiÖu c¸c kh¸i niÖm vµ c¸c kÕt qu¶ nghiªn cøu chÝnh vÒ c¸c ph−¬ng ph¸p RK cÇn thiÕt cho c¸c ch−¬ng sau. Ch−¬ng 2 ®Ò xuÊt ph−¬ng ph¸p lÆp song song dù b¸o-hiÖu chØnh d¹ng Runge-Kutta liªn tôc. XuÊt ph¸t tõ viÖc kh¶o s¸t l−îc ®å lÆp song song dù b¸o-hiÖu chØnh dùa trªn ph−¬ng ph¸p hiÖu chØnh Runge-Kutta d¹ng trïng khíp gi¶i bµi to¸n (1), b»ng c¸ch sö dông c¸c xÊp xØ sè liªn tôc lµm c¸c gi¸ trÞ dù b¸o trªn mçi nÊc trong qu¸ tr×nh lÆp, chóng t«i nhËn ®−îc c¸c ph−¬ng ph¸p lÆp song song dù b¸o-hiÖu chØnh d¹ng RK liªn tôc víi c¸c dù b¸o cã cÊp chÝnh x¸c cao (§Þnh lý 2.2). C¸c thö nghiÖm sè cho thÊy ph−¬ng ph¸p míi cña chóng t«i hiÖu qu¶ h¬n so víi c¸c ph−¬ng ph¸p song song vµ c¸c ph−¬ng ph¸p tuÇn tù DOPRI5 vµ DOP853 cã trong c¸c tµi liÖu. Ch−¬ng 3 tr×nh bµy ph−¬ng ph¸p lÆp song song gi¶ RK hai b−íc. Tõ mét ph−¬ng ph¸p s − nÊc gi¶ RK hai b−íc cã cÊp chÝnh x¸c p* víi w nÊc Èn (xem trong [22]), chóng t«i ¸p dông mét xö lý lÆp song song dù b¸o-hiÖu chØnh cÊp chÝnh x¸c cao theo ph−¬ng thøc PE (CE )m E . KÕt qu¶ chóng t«i nhËn ®−îc ph−¬ng ph¸p song song dù b¸o-hiÖu chØnh gäi lµ c¸c ph−¬ng ph¸p lÆp song song gi¶ Runge-Kutta hai-b−íc (IPIPTRK) víi c«ng thøc dù b¸o c¶i tiÕn (cÊp chÝnh x¸c cao). Ph−¬ng ph¸p míi sö dông sè bé xö lý tèi −u b»ng w ≤ p* / 2 . C¸c thö nghiÖm sè cho thÊy ph−¬ng ph¸p lÆp song song gi¶ RK hai b−íc (IPIPTRK) hiÖu qu¶ h¬n c¸c ph−¬ng ph¸p song song vµ tuÇn tù DOPRI5 vµ DOP853 ®· biÕt. Trong ch−¬ng cuèi chóng t«i ®Ò xuÊt ph−¬ng ph¸p lÆp song song dù b¸o-hiÖu chØnh d¹ng RK hai b−íc mét liªn tôc. §iÓm xuÊt ph¸t lµ c¸c ph−¬ng 6 ph¸p lÆp song song dù b¸o-hiÖu chØnh dùa trªn vÐct¬ trïng khíp cña c¸c ph−¬ng ph¸p hiÖu chØnh RK liªn tôc. Trªn b−íc thø n , c«ng thøc tÝnh liªn tôc kh«ng chØ ®−îc sö dông cho viÖc dù b¸o c¸c gi¸ trÞ nÊc trong c¸c ph−¬ng ph¸p lÆp dù b¸o-hiÖu chØnh mµ cßn sö dông ®Ó tÝnh c¸c gi¸ trÞ t¹i b−íc thø n+2 . Trong tr−êng hîp ®ã qu¸ tr×nh tÝnh to¸n cã thÓ thùc hiÖn hai b−íc mét. KÕt qu¶ lµ c¸c ph−¬ng ph¸p lÆp song song d¹ng RK hai b−íc mét liªn tôc (c¸c ph−¬ng ph¸p TBTPIRKC) cho ta qu¸ tr×nh tÝch ph©n nhanh h¬n. C¸c thö nghiÖm sè cho thÊy c¸c ph−¬ng ph¸p TBTPIRKC cã hiÖu qu¶ h¬n so víi c¸c ph−¬ng ph¸p lÆp song song d¹ng RK (PIRK) vµ c¸c ph−¬ng ph¸p RungeKutta tuÇn tù DOPRI5 vµ DOP853 ®· biÕt. C¸c kÕt qu¶ cña luËn ¸n ®· ®−îc tr×nh bµy t¹i c¸c seminar cña 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. C¸c kÕt qu¶ cña nµy ®−îc tr×nh bµy trong ch−¬ng 2, ch−¬ng 3 vµ ch−¬ng 4. LuËn ¸n ®−îc hoµn thµnh t¹i tr−êng §¹i häc Vinh vµ 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, d−íi sù h−íng dÉn cña GS TSKH NguyÔn H÷u C«ng vµ GS TSKH Ph¹m Kú Anh. T¸c gi¶ xin bµy tá lßng biÕt ¬n vµ kÝnh träng s©u s¾c ®èi víi c¸c thÇy gi¸o h−íng dÉn cña m×nh, nh÷ng ng−êi thÇy tËn tuþ vµ cã mét niÒm say mª lín lao dµnh cho khoa häc. T¸c gi¶ còng xin ch©n thµnh c¶m ¬n c¸c thÇy gi¸o, c« gi¸o, c¸c b¹n ®ång nghiÖp trong khoa To¸n- C¬-Tin häc tr−êng §HKHTN, §¹i häc Quèc gia Hµ Néi, Khoa To¸n vµ Khoa CNTT §¹i häc Vinh ®· dµnh cho t¸c gi¶ sù ®éng viªn vµ nhiÒu sù gióp ®ì quÝ b¸u. Cuèi cïng, t¸c gi¶ xin bµy tá lßng biÕt ¬n ch©n thµnh tíi Ban Gi¸m hiÖu, Phßng ®µo t¹o Sau ®¹i häc, Ban chñ nhiÖm khoa To¸n- C¬-Tin häc tr−êng §HKHTN, §¹i häc Quèc gia Hµ Néi, Ban Gi¸m hiÖu vµ c¸c phßng chøc n¨ng cña tr−êng §¹i häc Vinh, ®· t¹o mäi ®iÒu kiÖn thuËn lîi cho t¸c gi¶ hoµn thµnh nhiÖm vô. 7 Ch−¬ng 1 Tæng quan vÒ C¸c ph−¬ng ph¸p Runge-Kutta Trong ch−¬ng nµy chóng t«i tr×nh bµy mét sè kh¸i niÖm c¬ b¶n vµ kÕt qu¶ nghiªn cøu chÝnh cña c¸c ph−¬ng ph¸p Runge-Kutta cÇn thiÕt cho c¸c ch−¬ng sau. Trong phÇn thø nhÊt chóng t«i ®−a ra c¸c kh¸i niÖm c¬ b¶n cña ph−¬ng ph¸p Runge-Kutta tæng qu¸t. PhÇn thø hai tr×nh bµy c¸c kÕt qu¶ nghiªn cøu chÝnh vÒ c¸c ph−¬ng ph¸p Runge-Kutta hiÓn (ERK). PhÇn thø ba tr×nh bµy c¸c kh¸i niÖm c¸c ph−¬ng ph¸p Runge-Kutta Èn d¹ng trïng khíp, c¸c ®iÒu kiÖn cÊp C( s ) , B( s ) vµ mét sè kÕt qu¶ ®· biÕt. C¸c kh¸i niÖm vµ c¸c kÕt qu¶ nghiªn cøu chÝnh vÒ c¸c ph−¬ng ph¸p lÆp song song d¹ng Runge-Kutta ®−îc tr×nh bµy trong phÇn bèn. 1.1 C¸c kh¸i niÖm c¬ b¶n cña ph−¬ng ph¸p Runge-Kutta (RK) C¸c ph−¬ng ph¸p Runge-Kutta tr×nh bµy sau ®©y lµ ®Ó gi¶i sè bµi to¸n gi¸ trÞ ®Çu kh«ng c−¬ng (IVPs) cho hÖ ph−¬ng tr×nh vi ph©n cÊp mét (nh− ®· nãi trong phÇn më ®Çu) d¹ng y ' (t ) = f (t, y (t )) , y , f ∈ \d , y (t0 ) = y0 , t 0 ≤ t ≤ T0 , (1.1.1) hoÆc d¹ng thuÇn nhÊt y ' (t ) = f ( y (t )) , y , f ∈ \d , y (t0 ) = y0 , t 0 ≤ t ≤ T0. (1.1.2) Kh«ng mÊt tæng qu¸t, ®Ó thuËn tiÖn trong tÝnh to¸n, biÓu diÔn vµ chøng minh, nhiÒu khi chóng ta chØ xÐt bµi to¸n gi¸ trÞ ®Çu cho c¸c hÖ ph−¬ng tr×nh vi ph©n th−êng d¹ng thuÇn nhÊt. Ph−¬ng ph¸p sè ®¬n gi¶n nhÊt gi¶i bµi to¸n (1.1.1)-(1.1.2) lµ c¸c ph−¬ng ph¸p Euler. C¸c ph−¬ng ph¸p Euler lµ ph−¬ng ph¸p mét b−íc, cã ®é chÝnh x¸c kh«ng cao. CÊp chÝnh x¸c cña c¸c ph−¬ng ph¸p Euler ®Òu b»ng mét. C¸c ph−¬ng ph¸p Euler Èn lµ A − æn ®Þnh cßn miÒn æn ®Þnh cña c¸c ph−¬ng ph¸p Euler hiÓn lµ rÊt h¹n chÕ. Runge (1895) ®· më réng c¸c ph−¬ng ph¸p Euler b»ng c¸ch thªm vµo 8 ®¸nh gi¸ hµm vÕ ph¶i f kiÓu Euler ë gi÷a ®o¹n lÊy tÝch ph©n, Kutta (1901) ®· x©y dùng c¸c ph−¬ng ph¸p cÊp 3 vµ cÊp 4 næi tiÕng b»ng c¸ch thªm c¸c ®¸nh gi¸ hµm vÕ ph¶i f t¹i ®iÓm gi÷a vµ ®iÓm cuèi cña b−íc lÊy tÝch ph©n. Trong c¸c ph−¬ng ph¸p sè, c¸c ph−¬ng ph¸p Runge-Kutta lµ c¸c ph−¬ng ph¸p cã nhiÒu tÝnh chÊt kh¸ hoµn h¶o nh− cÊp chÝnh x¸c cao, tÝnh æn ®Þnh tèt, ®Æc biÖt chóng tiÒm Èn tÝnh song song ho¸ cao khi xö lý trªn m¸y tÝnh song song mµ c¸c ph−¬ng ph¸p kh¸c kh«ng cã. Chóng ta xÐt ph−¬ng ph¸p Runge-Kutta tæng qu¸t s − nÊc ®Ó gi¶i bµi to¸n (1.1.1), hoÆc (1.1.2) nh− ®· nãi trong phÇn më ®Çu ®−îc x¸c ®Þnh nh− sau s Yn, i = yn + h ∑ aij f (tn + c j h, Yn, j ), i = 1,..., s, (1.1.3) j =1 s yn + 1= yn + h ∑ b j f (tn + c j h, Yn, j ) , (1.1.4) j =1 trong ®ã ma trËn A = (aij ) sxs , c¸c vÐct¬ s − chiÒu c = (ci ) s vµ b = (bi ) s lµ c¸c ma trËn vµ c¸c vÐct¬ tham sè cña ph−¬ng ph¸p. Y n, i lµ c¸c vÐct¬ nÊc biÓu diÔn xÊp xØ lêi gi¶i chÝnh x¸c t¹i c¸c ®iÓm t + c h, i = 1,..., s , n Y n, i ≈ y(t + c h) , y ≈ y(t ), y n i n n n +1 i ≈ y(tn + 1), h = t − t lµ ®é dµi b−íc. n +1 n Ph−¬ng ph¸p (1.1.3)-(1.1.4) ®−îc biÓu diÔn b»ng b¶ng Butcher nh− sau c1 # cs a11 " a1s # # a s1 " a ss c hay A bT b1 " b s Trong c¸c ph−¬ng ph¸p RK d¹ng (1.1.3)-(1.1.4) ®Ó tÝnh c¸c xÊp xØ trung gian Y n, i ta ph¶i gi¶i c¸c hÖ ph−¬ng tr×nh víi ®é phøc t¹p tÝnh to¸n lín. NÕu (1.1.3)-(1.1.4) lµ ph−¬ng ph¸p Runge-Kutta Èn ®Ó x¸c ®Þnh c¸c Yn, i chóng ta ph¶i gi¶i hÖ ph−¬ng tr×nh (th«ng th−êng lµ phi tuyÕn) gåm s.d ph−¬ng tr×nh kÝch th−íc s.d v× thÕ ®èi víi ph−¬ng ph¸p IRK ®é phøc t¹p tÝnh 9 to¸n rÊt lín. §Æt ( n, s ) T Y = YT , . . .,YT n n,1 ( ∈ \ s.d , F (et + ch, Y ) = f (t + c h, Y n n 1 n n,1 )T ,. . ., f (t + c h, Y n s n, s )T ) T . Khi ®ã ta cã thÓ biÓu diÔn ph−¬ng ph¸p (1.1.3)-(1.1.4) d−íi d¹ng tÝch tenx¬ nh− sau Y = e ⊗ y + h( A ⊗ I ) F (et + ch, Y ) , (1.1.5) = y + h(bT ⊗ I ) F (et + ch, Y ) , (1.1.6) n y n +1 n d n d n n n n trong ®ã ⊗ lµ tÝch Kronecker, I lµ ma trËn ®¬n vÞ thuéc Rd . d 1.1.1. TÝnh æn ®Þnh cña ph−¬ng ph¸p Runge-Kutta (RK) §Ó nghiªn cøu tÝnh æn ®Þnh (tuyÕn tÝnh) cña ph−¬ng ph¸p Runge-Kutta (1.1.3)-(1.1.4), ta dùa vµo ph−¬ng tr×nh thö y ' (t ) = λ y (t ) , trong ®ã λ biÕn ®æi trªn nöa mÆt ph¼ng tr¸i ( Re( λ) < 0 ). Gi¶ sö ( I − zA )−1 tån t¹i, khi ®ã sù æn ®Þnh cña ph−¬ng ph¸p Runge-Kutta (1.1.3)-(1.1.4) phô thuéc vµo hµm æn ®Þnh R( z ) := 1 + zbT ( I − zA)−1 e . ThËt vËy ¸p dông ph−¬ng ph¸p RungeKutta (1.1.5)-(1.1.6) vµo ph−¬ng tr×nh thö (xÐt cho tr−êng hîp v« h−íng chØ cã mét ph−¬ng tr×nh) ta cã Yn = eyn + hAλ Yn = eyn + zAYn , z := λ h (1.1.7) y = y + hbT λ Y = y + zbT Y . n n n n (1.1.8) n Tõ (1.1.7) ta cã Y = ( I − zA )−1 y , thay vµo (1.1.8) ta nhËn ®−îc n n yn+1 = y + zbT ( I − zA)−1 ey = (1 + zbT ( I − zA)−1 e) y = R( z ) y , n n n n R( z ) := 1 + zbT ( I − zA)−1 e gäi lµ hµm æn ®Þnh cña ph−¬ng ph¸p kiÓu RungeKutta (1.1.3)-(1.1.4). Ta cã c¸c ®Þnh nghÜa sau: 10 §Þnh nghÜa 1.1.1. Gi¸ trÞ z ∈ C− ®−îc gäi lµ ®iÓm æn ®Þnh cña ph−¬ng ph¸p 0 Runge-Kutta (1.1.3)- (1.1.4) nÕu R( z ) < 1. 0 §Þnh nghÜa 1.1.2. MiÒn æn ®Þnh cña ph−¬ng ph¸p Runge-Kutta (1.1.3)(1.1.4) ®−îc x¸c ®Þnh nh− sau S stab { } := z ∈ ^ − | R( z ) < 1 . §Þnh nghÜa 1.1.3. a) NÕu ^− ⊂ S stab th× ph−¬ng ph¸p Runge-Kutta (1.1.3)-(1.1.4) ®−îc gäi lµ A − æn ®Þnh. b) Ph−¬ng ph¸p Runge-Kutta (1.1.3)-(1.1.4) ®−îc gäi lµ L − æn ®Þnh nÕu nã lµ A − æn ®Þnh vµ R( z ) = 0 khi z = −∞ ( R( −∞) = 0 ). c) Ph−¬ng ph¸p Runge-Kutta (1.1.3)-(1.1.4) ®−îc gäi lµ æn ®Þnh tuyÖt ®èi ( A − æn ®Þnh m¹nh) nÕu nã lµ A − æn ®Þnh vµ R( −∞) < 1. d) Gi¸ trÞ 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 lý 1.1.1. Hµm æn ®Þnh R( z ) cña ph−¬ng ph¸p Runge-Kutta (1.1.3)(1.1.4) ®−îc x¸c ®Þnh nh− sau R( z ) = det( I − zA + zebT ) . det( I − zA) NhËn xÐt nÕu ph−¬ng ph¸p Runge-Kutta lµ hiÓn (ERK) th× det( I − zA) = 1 , khi ®ã hµm æn ®Þnh cña nã lµ mét ®a thøc R( z ) = P( z ) , v× thÕ ®èi víi ph−¬ng ph¸p ERK kh«ng cã æn ®Þnh tuyÖt ®èi, h¬n n÷a cÊp chÝnh x¸c lín nhÊt cña ph−¬ng ph¸p Runge-Kutta hiÓn s − nÊc lµ s (xem trong [7, tr. 87]). NÕu ¸p dông vµo ph−¬ng tr×nh thö ta cã hµm æn ®Þnh cña c¸c ph−¬ng ph¸p Runge-Kutta cã d¹ng y (tn + 1) = (1 + zp z2 z + +...+ ) y(tn ) + O(h p + 1). 1! 2! p! 11 Tõ ®ã ta cã hµm æn ®Þnh R( z ) cã d¹ng R( z ) = (1 + zp z z2 p +1 + +...+ ) ) + O( z 1! 2! p! NÕu ph−¬ng ph¸p Runge-Kutta cã s = p th× zp z z2 R( z ) = 1 + + +...+ . 1! 2! p! (1.1.9) NÕu ph−¬ng ph¸p Runge-Kutta lµ Èn (IRK) th× hµm æn ®Þnh lµ mét ph©n P( z ) , P( z ) vµ Q( z ) lµ c¸c ®a thøc cña z , v× thÕ c¸c ph−¬ng ph¸p thøc d¹ng Q( z ) Runge-Kutta Èn cã tiÒm n¨ng æn ®Þnh tuyÖt ®èi. p ( z) D¹ng tæng qu¸t cña hµm æn ®Þnh lµ R( z ) = k , k , m ≤ s, q ( z) (1.1.10) m trong ®ã p vµ q k m t−¬ng øng lµ c¸c ®a thøc bËc k vµ bËc m cña z . NÕu cÊp cña xÊp xØ nµy so víi e z lµ k + m , th× (1.1.10) ®−îc gäi ( k , m ) cÆp xÊp xØ. Ehle (1969) ®· pháng ®o¸n r»ng mét ph−¬ng ph¸p kiÓu Runge-Kutta cã hµm æn ®Þnh lµ cÆp xÊp xØ ( k , s ) lµ A - æn ®Þnh khi vµ chØ khi s − 2 ≤ k ≤ s ®iÒu nµy ®−îc chøng minh bëi Wanner (1978). Ehle (1969) ®· chøng minh r»ng cÆp xÊp xØ ( s −1, s ) vµ ( s − 2, s ) cho ta c¸c ph−¬ng ph¸p Runge-Kutta L − æn ®Þnh (xem trong [7, tr. 87]). 1.1.2. CÊp chÝnh x¸c cña ph−¬ng ph¸p Runge-Kutta Trong môc nµy chóng ta xÐt cÊp chÝnh x¸c cña c¸c ph−¬ng ph¸p RungeKutta tæng qu¸t. ViÖc x©y dùng ph−¬ng ph¸p cã cÊp chÝnh x¸c cao vµ gi¶m thiÓu sè lÇn tÝnh to¸n hµm vÕ ph¶i lµ thö th¸ch chung khi x©y dùng c¸c ph−¬ng ph¸p RK gi¶i c¸c bµi to¸n (1.1.1). V× vËy viÖc nghiªn cøu cÊp chÝnh x¸c lµ yªu cÇu cÇn thiÕt khi x©y dùng c¸c ph−¬ng ph¸p RK cã hiÖu qu¶. §Þnh nghÜa 1.1.4. Ph−¬ng ph¸p Runge-Kutta (1.1.3)-(1.1.4) cã cÊp chÝnh x¸c p nÕu y(t n +1 )− y n +1 = O(h p + 1) víi y(t n +1 ) lµ nghiÖm chÝnh x¸c cña bµi to¸n (1.1.1). 12 Thay vµo ph−¬ng tr×nh (1.1.4) c¸c gi¸ trÞ xÊp xØ t−¬ng øng b»ng c¸c gi¸ trÞ chÝnh x¸c y = y (t ) , Yn, i = y (tn + ci h ) , ta cã n n s y (tn + 1) − yn + 1 = y (tn + 1) − y (tn ) −h ∑ bi f (tn + ci h, y (tn + ci h )) = O(h p + 1). i =1 §Þnh nghÜa 1.1.5. Ph−¬ng ph¸p Runge-Kutta (1.1.3)-(1.1.4) cã cÊp chÝnh x¸c trung gian (cÊp chÝnh x¸c nÊc) q nÕu y (tn + ci h) − Yn, i = O(hq + 1) víi mäi i = 1, 2, ..., s , ( y = y(t ) ). n n Trong thùc hµnh tÝnh to¸n, cÊp xÊp xØ trung gian (cÊp chÝnh x¸c nÊc) cña ph−¬ng ph¸p lÆp RK cã vai trß rÊt quan träng khi chóng ta cÇn gi¶i c¸c bµi to¸n c−¬ng. CÊp chÝnh x¸c nÊc lín nhÊt cña mét ph−¬ng ph¸p RungeKutta s − nÊc lµ s (xem trong [7, tr. 80]). Trong phÇn 1.4 chóng t«i sÏ tr×nh bµy c¸c ph−¬ng ph¸p RK cã cÊp chÝnh x¸c cao vµ chØ ra r»ng nÕu cÊp chÝnh x¸c nÊc cµng cao th× sè lÇn tÝnh to¸n hµm vÕ ph¶i cµng nhá, ®ã lµ c¸c ph−¬ng ph¸p lÆp song song d¹ng Runge-Kutta ®· ®−îc quan t©m nghiªn cøu cña nhiÒu nhµ to¸n häc trong lÜnh vùc gi¶i sè ph−¬ng tr×nh vi ph©n. 1.2. C¸c ph−¬ng ph¸p Runge-Kutta hiÓn (ERK) C¸c ph−¬ng ph¸p Runge-Kutta hiÓn ®−îc ph¸t triÓn cho ®Õn cuèi nh÷ng n¨m 60, v× trong thêi gian nµy c¸c c«ng cô tÝnh to¸n ch−a ®ñ m¹nh. ViÖc nghiªn cøu vµ x©y dùng c¸c ph−¬ng ph¸p RK Èn (IRK) ch−a ®−îc quan t©m nhiÒu, do ®é phøc t¹p tÝnh to¸n cña c¸c ph−¬ng ph¸p nµy qu¸ lín. Trong c¸c thËp kû ®ã c¸c c«ng tr×nh nghiªn cøu chñ yÕu tËp trung cho c¸c ph−¬ng ph¸p ERK. C¸c ph−¬ng ph¸p ERK lµ c¸c ph−¬ng ph¸p sè cã hiÖu qu¶ nhÊt khi gi¶i bµi to¸n kh«ng c−¬ng (1.1.1). ViÖc x©y dùng c¸c ph−¬ng ph¸p ERK cã cÊp chÝnh x¸c cao lµ qu¸ tr×nh xö lý hoµn toµn kh¸c víi viÖc x©y dùng c¸c ph−¬ng ph¸p RK Èn. Trong tr−êng hîp bé hÖ sè kh«ng x¸c ®Þnh duy nhÊt, c¸c ph−¬ng ph¸p hiÓn cã cÊp chÝnh x¸c nÊc cao nhÊt lµ r , trong khi ®ã ®èi víi c¸c ph−¬ng ph¸p ERK sù h¹n chÕ qu¸ lín khi mµ trong nÊc ®Çu tiªn lµ b−íc tÝnh kiÓu 13