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


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


( 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

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


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



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


), 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ử)
cha phát triển, các phơng pháp Runge-Kutta cha phải là phổ biến và cha
đợ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

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

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])


+ 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

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

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

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

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



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



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

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


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 cha đủ mạnh. Việc

A

c
y

n +1

bT

là biểu diễn của một phơng pháp kẹp đôi, khi đó

c

c

A

s +1

T

y

n +1

trong đó T = ( a

, . . ., a

s + 1,1


s




= h (b b ) f (Y ) + b
f (Y )
j
j
j
s +1
s +1

j =1


là đánh giá sai số địa phơng theo phơng pháp có cấp chính xác thấp hơn.
Các cặp kẹp đôi này thờng đợc biểu diễn dới dạng bảng sau

c

c

A

s +1

T



6

7

8

9

s lý thuyết 1

2

3

4

6

7

9

11

12 13

s thực tế

2

IIIA, IIIB, IIIC của Ehle và Chipman (xem trong [2, tr. 13], [28]). Mặc dầu
các phơng pháp IRK có những tính chất tốt nh vậy nhng trớc đây vì quá
phức tạp khi phải tính toán lớn trong mỗi bớc để xác định các véctơ xấp xỉ
trung gian (các công cụ tính toán chính nh máy tính cha phát triển) nên
chúng vẫn cha phải là các phơng pháp đợc dùng phổ biến nh những
phơng pháp dạng Adams hoặc công thức sai phân lùi BDF. Sau khi Butcher
(1976, [9]) đa ra một giải pháp khá hữu hiệu để khắc phục tình trạng này thì
các phơng pháp IRK mới bắt đầu trở nên thông dụng hơn. Một chơng trình
máy tính viết bằng ngôn ngữ FORTRAN77 tự động tính toán cho các phơng
pháp 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 Randau IIA có tên là RADAU5 đã ra đời (xem trong [28], [29]). Sau đây
chúng tôi chỉ trình bày về một lớp các phơng pháp Runge-Kutta ẩn là các
phơng pháp IRK dạng trùng khớp. Các phơng pháp Runge-Kutta ẩn cũng có
thể xem xét tuỳ theo chúng có phải là các phơng pháp trùng khớp hay
không. Lớp các phơng pháp IRK dạng trùng khớp đã đợc quan tâm nghiên
cứu và đạt đợc nhiều kết quả, (xem trong [14], [20]). Sự trùng khớp là ý
tởng có từ lâu đợc ứng dụng rộng rãi trong giải tích số và nó 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ó hành vi biến đổi giống nh
hàm cha biết mà chúng ta đang cố gắng xấp xỉ số (xem trong [41, tr.194197]).
Thật vậy chúng ta xây dựng một đa thức P( t ) cấp s và tập các điểm

{

}

trùng khớp tn + ci h, i = 1,...,s sao cho
16



c
i

1

0

0

aij := L j ( x)dx , i = 1,...,s , b j := L j ( x)dx , j = 1,...,s ,

(1.3.1)

trong đó L ( x ), j = 1,...,s là các đa thức nội suy Lagrange của P'( t ) .
j

Bằng cách đó ta nhận đợc phơng pháp Runge-Kutta ẩn s nấc với
các thành phần của véctơ c là các điểm trùng khớp, véctơ b và ma trận A xác
định bởi (1.3.1). Các phơng pháp Runge-Kutta ẩn có thể nhận đợc bằng
cách này thuộc lớp các phơng pháp Runge-Kutta dạng trùng khớp. Giả sử
bây giờ ta xét phơng pháp RK (1.1.3)-(1.1.4) cho bài toán (1.1.1) với

f (t , y ) = f (t ) . Quan hệ (1.1.3) có thể hiểu nh là công thức cầu phơng
t +c h
n i



f (t )dt , i = 1, ..., s . Khi đó mỗi một công thức cầu phơng sẽ là chính


i
n

s



j =1

aij (tn + c j h)r , r = 1, . . ., s 1 .

So sánh các hệ số theo luỹ thừa của h ta dễ dàng nhận đợc các quan hệ sau
s

aij cj 1 = cj / ,

= 1, . . . , s.

(1.3.2)

j =1

17


Nhận xét nếu = 1 , khi đó (1.3.2) chính là điều kiện tổng của hàng.
Điều kiện (1.3.2) là cần và đủ để một phơng pháp IRK là dạng trùng khớp
(xem trong [41, tr. 195-196]). Các phơng pháp: Gauss, Radau IIA và
Lobatto IIIA là các phơng pháp dạng trùng khớp; Radau IA, Lobatto IIIB và
Lobatto IIIC không phải là các phơng pháp dạng trùng khớp.

j!
1!
j d
d
= exp h f ( x0 ) = h
f (x ) .
0


dt
dt
j = 0


Bây giờ nếu thay Yn bằng giá trị chính xác của véctơ xấp xỉ trung gian

y (etn + ch) vào (1.3.3) ta có
y (etn + ch) - y (etn ) - hAy' (etn + ch) = O(hq + 1) .
Bằng khai triển Taylor tại t theo luỹ thừa h và nhóm các hệ số ta có
n

điều kiện cấp C (q ) nh sau
Ac

j 1

cj
= ,
j