NGUYỄN CHÍ TRUNG
NGUYỄN TÂN ÂN
NGUYỄN THỊ THU THỦY

PHƯƠNG PHÁP TÍNH
VÀ BÀI TOÁN TỐI ƯU
HÀ NỘI - 2010
NCT-FIT-HNUE Computional methods and Optimization Problems
MỤC LỤC
MỞ ĐẦU 5
Chương 1 TÍNH GẦN ĐÚNG VÀ SAI SỐ 8
1. Số gần đúng và sai số của nó 8
1.1. Số gần đúng và sai số 8
1.2. Chữ số có nghĩa và chữ số đáng tin 9
1.3. Cách viết số gần đúng 10
1.4. Sai số làm tròn 10
2. Sự lan truyền sai số 11
2.1. Mở đầu 11
2.2. Sai số của tổng 11
2.3. Sai số của tích 12
2.4. Sai số của thương 13
2.5. Sai số của hàm bất kỳ 14
3. Các loại sai số 14
3.1. Các loại sai số mắc phải khi giải một bài toán thực tế 14
3.2. Các loại đánh giá sai số phương pháp 15
BÀI TẬP 15
Chương 2. TÍNH GIÁ TRỊ VÀ XẤP XỈ HÀM SỐ 16
1. Tính giá trị hàm số 16
1.1. Thuật toán Hoocner tính giá trị đa thức 16
1.2. Tính hàm nhờ chuỗi lũy thừa 17
2. Bài toán nội suy hàm số 18

BÀI TẬP 44
Chương 4 PHƯƠNG PHÁP SỐ TRONG ĐẠI SỐ TUYẾN TÍNH 46
1. Đại số ma trận 46
1.1. Vectơ cột và vectơ hàng 46
1.2. Ma trận 47
2. Hệ phương trình đại số tuyến tính 50
2.1. Giới thiệu 50
2.2. Giới thiệu phương pháp Cramer 51
2.3. Phương pháp khử Gauss 52
2.4. Phương pháp Gauss-Seidel 55
2.5. Phương pháp giảm dư 59
2.6. Vấn đề ổn định của nghiệm của hệ phương trình 62
3. Tính gần đúng giá trị riêng và véc tơ riêng của ma trận 63
3.1. Giới thiệu 63
3.2. Ma trận đồng dạng 64
3.3. Tìm giá trị riêng bằng phương pháp Đa-nhi-lép-ski 64
3.4. Tìm vectơ riêng bằng phương pháp Đan-nhi-lep-ski 67
BÀI TẬP 69
Chương 5 TÍNH GẦN ĐÚNG ĐẠO HÀM VÀ TÍCH PHÂN 71
1. Tính gần đúng đạo hàm 71
1.1. Đạo hàm cấp 1 71
1.2. Đạo hàm cấp hai 71
2. Tính gần đúng tích phân 72
2.1. Giới thiệu bài toán 72
2.2. Công thức hình chữ nhật trung tâm 72
2.3. Công thức hình thang 74
2.4. Công thức Simpson (hay công thức Parabol) 76
2.5. Các thuật toán “hcn, ht, sim” tính gần đúng tích phân xác định 78
Chương 6 BÀI TOÁN QUI HOẠCH TUYẾN TÍNH 79
1. Giới thiệu bài toán tối ưu tổng quát 79

ết
Toán lí thuyết quan tâm đến các vấn đề định tính của bài toán: tồn tại, duy nhất, tính chất nghiệm
của các bài toán.
Toán tính quan tâm đến xây dựng phương pháp, thuật toán để để tìm nghiệm bài toán trên máy
tính.
Thuật toán được xây dựng phải thỏa mãn yêu cầu về tính khả thi và tính ổn định.
Một thuật toán là khả thi nếu nó thực hiện được trên máy tính. Một thuật toán gọi là ổn định nếu
sai số tính toán (do máy tính làm tròn số) không b
ị khuếch đại trong quá trình tính.
Ví dụ 1 (tính ổn định). Giả sử cần tính tích phân
)1(
1
1
0
≥=
−
∫
ndxexI
xn
n
.
Tích phân từng phần: đặt u=x
n
thì du = nx
n-1
dx; đặt dv=e
x-1
dx thì v = e
x-1
ta được

e
xedxexI
xx

Như vậy, để tính
ta thu được công thức truy hồi tính được In về mặt lý thuyết:
n
I
.3679.0
,2,1
1
1
=
≥−=
−
I
nnII
nn

Về mặt thực tế tính trên máy tính không cho kết quả mong muốn khi n lớn. Cụ thể là tính trên
máy tính với n=25 ta được bảng kết quả sau (liệt kê theo từng hàng)
0.3679 0.2642 0.2073 0.1709 0.1455
0.1268 0.1124 0.1009 0.0916 0.0839
5
NCT-FIT-HNUE Computional methods and Optimization Problems
0.0774 0.0718 0.0669 0.0627 0.0590
0.0555 0.0572 -0.0295 1.5596 -30.1924
635.0403 -13969.8864 321308.3881 -7711400.3133 192785008.8325
Kết quả giảm dần từ 0.3679 (khi n=1) đến 0.0555 (khi n=16)
Kết quả sau đó kết quả thay đổi thất thường và giá trị tuyệt đối tăng rất nhanh.

Nguyên nhân: thay vì
e
I
1
1
= ta thu được
, trong đó
δ
+=
11
~
II
δ
là sai số. Giả sử các tính toán
tiếp theo không mắc phải sai số. Với n = 2 ta được
.22)21()(21
~
21
~
21112
δδδ
−=−−=+−=−= IIIII

Thu được
2
~
I với sai số
δ
2|
~

=
i
i
x , (i =1, , n), (2)
trong đó
, còn nhận được từ Adet=∆
i
∆
∆
do việc thay cột thứ i bởi cột tự do b. Nhưng việc
tính toán ra nghiệm bằng số cụ thể lại là một việc không đơn giản. Theo công thức (2) cần phải
tính n +1 định thức cấp n. Mỗi định thức là tổng của n! số hạng, mỗi số hạng là tích của n thừa
số. Do vậy, để tính mỗi số hạng cần thực hiện n – 1 phép nhân. Như vậy, tất cả
số phép tính nhân
cần thực hiện trong (2) là Q = n!(n+1)(n-1).
Giả sử n = 20. Khi đó
. Nếu tốc độ của máy tính là 100 triệu phép tính/giây thì
thời gian để thực hiện khối lượng tính toán trên là
giờ = năm. Một thời
gian lớn vô cùng! Và như vậy, thuật toán nêu trên là hoàn toàn không khả thi dù máy tính có
tăng tốc độ lên gấp hàng nghìn, hàng vạn lần.
20
10*7073.9≈Q
9
10*2.6965
5
10*0782.3
6
NCT-FIT-HNUE Computional methods and Optimization Problems
Ở trên ta mới chỉ xét việc giải một hệ cỡ 20, mà thực tế khoa học và công nghệ đòi hỏi phải giải

.
Thí dụ: Đối với số 2A = thì
1
1, 41a
=
là xấp xỉ thiếu, còn
2
1, 42a
=
là xấp xỉ thừa vì
2 1,4142135623 = ; đối với số 3,1415926535
π
=
thì 3,14 là xấp xỉ thiếu, còn 3,15 là xấp xỉ
thừa.
Định nghĩa 1-1.1 Số
||
A
a
∆
=−
được gọi là sai số tuyệt đối của số gần đúng a .
Thông thường số đúng
không biết nên ta cũng không biết chính xác sai số tuyệt đối của số
gần đúng
, mà chỉ có thể đánh giá nó. Vì thế ta có thể xem đánh giá tốt nhất của ∆ là sai số
tuyệt đối giới hạn
của , đó là số bé nhất có thể biết được, thỏa mãn điều kiện
A
a

≤ .
Sai số tuyệt đối không phản ánh đầy đủ mức độ chính xác của phép đo hoặc tính toán. Chẳng
hạn, đo chiều dài của hai thanh sắt bằng cùng một thước đo ta nhận được các kết quả sau:
1
±=

nhưng rõ ràng là phép đo thứ
Định nghĩa 2-1.1. Sai số tương đối của số gần đúng , ký hiệu bở
cmcml
2
±=
Tuy sai số tuyệt đối của hai phép đo trên là như nhau (= 0,1 cm)
cmcml
1,05,7
1,06,115
nhất chính xác hơn. Để thể hiện điều đó ta đưa vào khái niệm sau.
a i
δ
, là
A
aA
A
−
=
∆
=
δ
(3-1.1)
ết
nhận sai số tương đối của số

.
Trở lại phép đo chiều dài của các thanh sắt ta thấy rằng sai số tương đối của
là
1
l
1
0,1
100% 0,09%
115,6
δ
=×= , của là
2
l
2
0,1
100% 1,33%
7,5
δ
=× = . Rõ ràng là
1
δ
nhỏ hơn rất nhiều
so với
2
δ
và phép đo thứ nhất chính xác hơn nhiều so với phép đo thứ hai.
1.2. Chữ số có nghĩa và chữ số đáng tin
Một số viết ở dạng thập phân có thể gồm nhiều chữ số. Chẳng hạn số 20,15 có 4 chữ số; số
3,1412 có 5 chữ số.
Định nghĩa 1-1.2. Những chữ số có nghĩa của một số là những chữ số của số đó kể từ chữ số

a
10.
)10 10.10.10 10.10.(
1
1
0
01
1
1
α
αααααα
(1-1.2)
trong đó
s
α
là những số nguyên từ 0 đến 9, gọi là chữ số hàng thứ s của số a.
Định nghĩa 2-1.2. Gọi là sai số tuyệt đối của số , chữ số hàng thứ s của số a được gọi là
chữ số đáng tin (hay chữ số đúng) nếu sai số tuyệt đối của số a không vượt quá một nửa đơn vị
của hàng thứ s (tức là
a
∆
a
s
a
10.
2
1
≤∆ ), và gọi là chữ số nghi ngờ nếu sai số tuyệt đối của số a
không vượt quá một nửa đơn của hàng thứ s (tức là
s

Cách này thường dùng để viết các kết quả đo đạc, thực nghiệm, trong đó là sai số của thiết
bị đo.
a
∆
Ví dụ 1-1.3. 150 cm ± 0.1 cm; 65 kg ± 0.1 kg
Cách 2: Viết theo quy ước: mọi chữ số có nghĩa đều đáng tin, có nghĩa là sai số tuyệt đối
a
∆

không lớn hơn một nửa đơn vị ở hàng cuối cùng.
Ví dụ 2-1.3. Theo cách này ta viết a = 23.54 nếu
2
1
10 0.005
2
a
−
∆≤ × = .
1.4. Sai số làm tròn
Khi thực hiện các tính toán nếu số có quá nhiều chữ số trong biểu diễn thập phân, chẳng hạn
=3.14151926535, thì để cho thuận tiện người ta thu gọn số này bằng cách bỏ bớt một số chữ
số cuối để được một số

a
a
'a

ngắn gọn hơn và gần đúng nhất với . Việc làm này được gọi là quy
tròn hoặc làm tròn số. Số
a

2
×
10
-4
,
1
2
×
10
-3
và
1
2
×
10
-2
.
Ví dụ 2-1.4. Số 12.25 ta làm tròn thành 12.2 với sai số là 0.05 =
1
2
×
10
-1
.
Bây giờ giả sử a là xấp xỉ của A với sai số tuyệt đối là
a
∆
. Giả sử ta làm tròn a thành a' với
sai số làm tròn là
'a

2
×
10 . Vì thế chữ số 4 trong a’ là
đáng ngờ. Trong trường hợp này không nên quy tròn số
a .
-1
2. Sự lan truyền sai số
2.1. Mở đầu
Trên đây ta đã định nghĩa các loại sai số của một số gần đúng. Trong thực tế tính toán các đại
lượng gần đúng thường xuất hiện trong một biểu thức phức tạp. Thí dụ thể tích của hình cầu
được tính bằng V = (1/6)πd
3
, trong đó ta chỉ biết xấp xỉ của số π và đường kính d. Vấn đề đặt
ra là biết sai số của π và d, liệu ta có thể tính được sai số của V không. Một cách tổng quát,
vấn đề đặt ra là sai số của các dữ liệu đầu vào lan truyền và dẫn đến sai số của kết quả tính toán
như thế nào?
Để giải quyết vấn đề này xét hàm số u của 2 biến số
x và y:
u = f(x,y)
Giả sử x là xấp xỉ của giá trị đúng X, y là xấp xỉ của giá trị đúng Y và ta coi u là xấp xỉ của giá
trị đúng u = f(X,Y). Biết sai số về x và y, hãy tính sai số của u.
Ký hiệu ∆x = x - X là số gia của x, còn dx là vi phân của biến x.
Theo định nghĩa về sai số tuyệt đối, ta có | ∆x | ≤
∆
x
.
Theo công thức vi phân của hàm nhiều biến ta có:
du =
x
u

+∆
∂
∂
=∆
|||| (1-2.1)
Chú ý:
Công thức (1-2.1) là công thức quan trọng để tính sai số của hàm hai biến u = f(x,y) bất
kỳ dựa vào đạo hàm riêng của từng biến. Công thức (1-2.1) được sử dụng trong việc chứng minh
các công thức tính sai số của tổng, hiệu, tích thương biểu diễn hàm hai biến.
2.2. Sai số của tổng
Cho u = x y.±
Ta có
11
NCT-FIT-HNUE Computional methods and Optimization Problems
x
u
∂
∂
= 1, 1
u
y
∂
=±
∂
.
Do đó, từ (1.6) suy ra

(1-2.2)
yx
u ∆+∆=∆

)(
δ

Ta thấy rằng nếu | x -y | rất bé thì sai số tương đối rất lớn.
Ví dụ 2-2.2. Giả sử x = 15.29 và y = 15.14 là hai số đã được làm tròn. Xác định sai số tương đối
của x, y và của hiệu hai số trên.
Giải. Ta có hiệu u = x - y = 15.29 -15.14 = 0.15. Do x và y đã được làm tròn đến 2 chữ số sau
dấu chấm thập phân nên sai số tuyệt đối của chúng là
∆
x
=
∆
y
= 0.005. Vì thế sai số tuyệt đối
của hiệu là
∆
u
=
x
∆ + ∆
y
= 0.01. Do đó sai số tương đối của hiệu là δ
u
=∆
u
/ |u| = 0.01/ 0.15 =
0.066 trong khi sai số tương đối của x và y tương ứng là
000327.0
29.15
005.0

+
+−
=u
2.3. Sai số của tích
Giả sử u = xy. Ta có

x
y
u
=
∂
∂
.
Từ (1-1.2) suy ra
12
NCT-FIT-HNUE Computional methods and Optimization Problems

yxu
xy ∆+∆=∆
Do đó
yx
u
u
y
y
x
x
u
δδδ
+=

yx
δδ
. Theo (3-1.2) sai số tương đối của tích là
0093.00061.00032.0
=
+=
u
δ
. Vì u = x * y =15.6 * 8.2 =127.92 nên sai số tuyệt đối của u là
19.10093.0*92.127|| ===∆
uu
u
δ
. Do đó, 19.192.127*
±
=
YX , tức là giá trị thực sự của
diện tích của hình chữ nhật nằm trong khoảng từ 126.73 đến 129.11.
2.4. Sai số của thương
Cho . Ta có: yxu /=
x
u
∂
∂
=
y
1
,
y
u

⎟
⎠
⎞
⎜
⎜
⎝
⎛
∆+∆=∆=
∆
111
||
2
.
Suy ra:

yxyx
δ
δ
δ
+=
/
(1-2.4)
Ta có quy tắc sau:
Sai số tương đối của một thương bằng tổng các sai số tương đối của số chia và số bị chia.
13
NCT-FIT-HNUE Computional methods and Optimization Problems
2.5. Sai số của hàm bất kỳ
Cho hàm . Theo công thức vi phân của hàm nhiều biến ta có: ), ,,(
21 n
xxxfu =

∂
∂
∆x
1
+
2
x
u
∂
∂
∆x
2
+ +
n
x
u
∂
∂
∆x
n

Suy ra
n
x
n
xxu
x
u
x
u

δ
d
= 0.05/3.7 = 0.0135
Suy ra δ
V
= 0.0005 + 3 * 0.0135 = 0.04
Giá trị gần đúng của thể tích là V = (1/6)πd
3
= 26.5 cm
3
. Do đó, ta tính được sai số tương đối
của nó là ∆
V
= |V|*δ
V
= 26.5*0.04 = 1.06 ≈ 1.1 cm
3
. Vì thế
V = 26.5 ± 1.1 cm
3
.
3. Các loại sai số
3.1. Các loại sai số mắc phải khi giải một bài toán thực tế
Như đã biết, để nghiên cứu một đối tượng thực tế, chẳng hạn một đối tượng vật lý như dòng chảy
trong sông, hiện tượng dẫn nhiệt trong một thanh vật chất, hay một đối tượng kinh tế-xã hội,
người ta thường xây dựng mô hình toán học của đối tượng và nghiên cứu đối tượng thông qua
mô hình. Do tính chất phức tạp của đối tượng nên người ta không thể đư
a hết tất cả các yếu tố
liên quan vào mô hình, mà buộc phải loại bỏ những yếu tố không quan trọng và ảnh hưởng ít đến
đối tượng. Kết quả là người ta chỉ nhận được mô hình toán học phản ánh gần đúng đối tượng cần

q
xx
n
n
−
−
≤− ,
trong đó 0< q< 1, x* là nghiệm đúng, x0 là xấp xỉ ban đầu.
Đánh giá sai số hậu nghiệm là đánh giá sai số nhận được sau khi tính toán được nghiệm. Thí
dụ, sau khi tính được x
n
theo phương pháp lặp đơn (xem Chương 3) ta có đánh giá hậu nghiệm
1
*
1
−
−
−
≤−
nnn
xx
q
q
xx
BÀI TẬP
1. Khi xác định hằng số khí của không khí, nhận được R =29.25. Hãy xác định các giới hạn
của R biết sai số tương đối giới hạn của R là 1%.
2. Đo trọng lượng của 1 dm
3
nước ở 0

n-1
x + a
n
(a
0
≠ 0)
Để tính giá trị p(x
0
) cần 2n-1 phép nhân và n phép cộng. Hơn nữa các số hạng của đa thức
thường lớn nên bất lợi trong tính toán.
Nếu ta phân tích đa thức thành
p(x) = (b
0
x
n-1
+ b
1
x
n-2
+ … + b
n-2
x + b
n-1
) ( x - x
0
) + b
n
(1-1.1)

Ta có ngay p(x

n-1
x
n-1
x
0
+ b
n-2
x
2
– b
n-2
xx
0
+ b
n-1
x – b
n-1
x
0
x
0
+ b
n
=

b
0
x
n
+ (b

0
)

+

(b
n-1
x - b
n-2
xx
0
) + (b
n

– b
n-1
x
0
)
=

kn
kk
n
k
n
xxbbxb
−
−
=

- b
k-1
x
0
= a
k
, ∀ k = n,1 hay
b
k
= a
k
+ b
k-1
x
0
, hay b
k
= a
k
+ c
k
với c
k
= b
k-1
x
0
Thuật toán Hoocner tính giá trị các hệ số của đa thức trong (1-2.1) như sau :
⎪
⎩

x
0
c
1
… c
n

b
0
b
1
… b
n
p(x
0
)=b
n
Ví dụ 1-1.1
Tính f(x) = 2x
5
- 3x
4
+ x
3
- 4x
2
+ 7x + 8 tại x = 2 như sau
2 -3 1 -4 7 8 2
4 2 6 4 22
2 1 3 2 11 30 p(2)=30

!
)(
)(
k
k
k
xx
k
xf
xf (1-1.2)
thì ta có thể tính gấn đúng

∑
=
−≈
n
k
k
k
xx
k
xf
xf
0
0
0
)(
)(
!
)(

0
= π/6, suy ra x – x
0
= π/30
Áp dụng công thức 2-1.2 với n = 1 và x
0
= π/6 ta có:
và
)()()()(
!1
)(
)(
!0
)(
)(
0
'
00
1
0
0
)1(
0
0
0
)0(
xfxxxfxx
xf
xx
xf

⎛
=
π
c
R
2. Bài toán nội suy hàm số
Một trong các bài toán cơ bản của giải tích số là nội suy hàm số. Bài toán này thường gặp trong
các trường hợp sau :
i) Cần phục hồi hàm số ) đối với mọi điểm x thuộc khoảng [a, b] nếu chỉ biết giá trị của nó
tại một số điểm
. Những giá trị này thường là các giá trị quan sát, hoặc đo đạc
được.
(xf
],[, ,,
10
baxxx
n
∈
ii) Khi hàm cho bởi công thức quá phức tạp chẳng hạn )(xf
∫
+
+
=
2
)cos(
2
3
)sin(
)(
)(

ii
= . Hàm g(x) được gọi là hàm nội suy. Các điểm nút x
i
( ni ,0= ) gọi là các
mốc nội suy.
Một số dạng hàm thường được dùng để nội suy hàm số là: )(xg
- Đa thức đại số
- Hàm hữu tỉ, tức là phân thức đại số
- Đa thức lượng giác
- Hàm ghép trơn (spline), tức là hàm đa thức từng mẩu.
Trong chương này chúng ta chỉ tập trung vào nội suy bởi đa thức đại số - một công cụ nội suy
kinh điển và một phần về nội suy bởi hàm ghép trơn - công cụ nội suy hiện đại. Các dạng nội
suy khác sẽ chỉ được giới thiệu qua. Nếu không nói rõ hơn ta sẽ ngầm định hiểu đa thức là đa
thức đại số.
2.1. Đa thức nội suy Lagrange trên mốc không đều
2.1.1. Thiết lập đa thức nội suy Lagrange
Đa thức nội suy Lagrange của hàm y = f(x) tại các điểm mốc x
i
∈ [a, b] ( ),0 ni = cho bởi công
thức sau:
18
NCT-FIT-HNUE Computional methods and Optimization Problems
∑
=
=
n
i
iin
xlxfxL
1

110
110
)) ()() ((
)) ()() ((
)(

(2-2.1)
(Tử số khuyết nhân tử (x - x
i
), mẫu số khuyết nhân tử (x
i
- x
i
))
Ta thấy L
n
(x) thỏa mãn điều kiện nội suy
),0(),()( nixfxL
iin
==
(3-2.1)
Thật vậy, dễ thấy rằng
⎩
⎨
⎧
≠
=
==
ji
ji

1
10
1
01
)()()(
xx
xx
xf
xx
xx
xfxL
−
−
+
−
−
=

(5-2.1)
b) Nội suy Lagrange bậc hai
Khi n = 2 ta có ba nút nội suy và
2
x vµ
10
, xx
))((
))((
)(
))((
))((

−
−
= (6-2.1)
trong đó
i =0, 1, 2.
),(
ii
xfy =
Ví dụ 1-2.1. Xây dựng đa thức nội suy cho hàm
xy
π
sin
=
tại các nút

6
1
,0
10
== xx và .
2
1
x
2
=
Giải. Ta có bảng giá trị của hàm
x 0 1/6 1/2
y 0 1/2 1
Áp dụng công thức (6-2.1) ta được
19

)(0(
.
2
1
)
2
1
0)(
6
1
0(
)
2
1
)(
6
1
(
.0)(
2
2
xx
xx
xx
xx
xL −=
−−
−−
+
−−

6
)1(
)01)(11(
)0)(1(
.3
)1.(1
)1)(1(
.1
)11.(1
)1(
.
3
1
)(
2
2
++=
+
+−+−
−
=
−+
−
+
+
−
−
+
+
−−−

n
Định lý 4.2.1 Giả sử hàm số , tức là có đạo hàm liên tục đến cấp n+1 trên [a,
b] chứa tất cả các nút nội suy

)(xf
],[
)1(
baC
n+
∈
i
x ),0( ni = . Khi đó sai số nội suy )()()( xLxfxR
nn
−
=
có dạng
),(
)!1(
)(
)(
1
)1(
x
n
f
xR
n
n
n +
+

1
1
x
n
M
xLxf
n
n
n +
+
+
≤−
ω
(8-2.1)

trong đó
bxa
n
n
xfM
≤≤
+
+
= ).(max
)1(
1
và
∏
=
+

)
4
(
.1
)
24
(
4
)
2
(
.707,0)(
2
πππ
π
πππ
π
−
−
+
−
−
=
xxxx
xL
Ta có
.851,0)
3
(
3

3
===
≤≤≤≤
xxyM
xx
ππ

.
21623
.
433
)
3
(
3
3
πππππππ
ω
=−−=
Do đó
024,0
2166
1
)
3
(
3
sin
3
2

2
x 0,xx là đa thức
2
2
)( xxL = .
Để đánh giá sai số
)()(
2
xLxf − ta không thể áp dụng công thức (8-2.1) vì hàm không có
đạo hàm tại x = 0. Nhưng ta có thể đánh giá được sai số nội suy trên đoạn [-1, 1] như sau
)(xf
4
1
maxmax)()(max
2
1
2
1
2
1
=−=−=−
≤≤≤
xxxxxLxf
xxx

21
NCT-FIT-HNUE Computional methods and Optimization Problems
2.1.2. Thuật toán nội suy Lagrange
Bài toán:
Cho bảng các giá trị ( , ),

, y
i

),0( ni =

output: y là giá trị của hàm tại x
Algorithm:
1. Khởi tạo y = 0
2. for i = 0 Æ n
2.1. P = 1;
/* P chính là đa thức l
i
*/
2.2. for j = 0 Æ n
if (j ≠ i)
P = P * (x - x
j
) / (x
i
- x
j
)
2.3. y = y + y
i
*P
3. return y
2.2. Đa thức nội suy Lagrange với mốc cách đều
Giả sử hàm f(x) nhận các giá trị y
i
tại các điểm tương ứng x

−=−
+−=−
−−=−
−=−
=−
+
−

)()1(
.
1
1
1
0
inhxx
hxx
hxx
ihxx
ihxx
ni
ii
ii
i
i
−−=−
−=−
=−

0
)1()!(!)(
)) (1(
)(
−
−−−
−−
=+
n
i
iniit
nttt
htxl (2-2.2)
22
NCT-FIT-HNUE Computional methods and Optimization Problems
Vậy công thức nội suy Lagrange (1-2.1) trong trường hợp mốc cách đều một khoảng h có dạng :
∑
=
−
−−
−
−−=+
n
i
i
n
n
iniit
xf
nttthtxL

)()1(
!
)) (1(
)(
(4-2.2)
Ví dụ 1-2.2. Tìm hàm nội suy cho hàm f(x) thỏa mãn :
x
i
0 2 4
f(x
i
) 5 -2 1
Giải: Áp dụng công thức (4-2.2.2) ta có
5125)102410(
2
1
2
1
1
45
2
)2)(1(
2
.1
1
2
0
5
!2
)2)(1(

−
+
−
−
−
−
−−
=
tttt
ttt
ttt
t
C
t
C
t
C
ttt
tL

2.3. Đa thức nội suy Newton trên mốc không cách đều
Đa thức nội suy Lagrange (1-2.1), như ta đã thấy rất đơn giản và dễ tính nếu các nút nội suy đã
được cố định. Nhưng nếu như ta bổ sung thêm nút nội suy thì quá trình tính lại phải thực hiện lại
từ đầu. Đây là nhược điểm rất lớn của đa thức nội suy Lagrange. Để khắc phục nhược điểm này
người ta tính đa thức nội suy theo một cách khác hiệ
u quả hơn. Đó là công thức nội suy Newton.
Để xây dựng công thức này, ta cần đến khái niệm tỷ sai phân đối với các mốc không đều và khái
niệm sai phân đối với mốc cách đều.
2.3.1. Khái niệm tỷ sai phân
Giả sử ) là một hàm số xác định và liên tục trong đoạn (xf

=
)()(
),(
- Tỷ sai phân bậc 2 của hàm
tại , , là
)(xf
i
x
j
x
k
x
ki
kjji
kji
xx
xxfxxf
xxxf
−
−
=
),(),(
),,(
- Một cách tổng quát, tỷ sai phân bậc k của f tại
là
110
, ,,
+k
xxx
23

ijk
xxxf
, ,
)., ,,(), ,,(
0110
xxxfxxxf
kkk −
=

ii) Nếu là đa thức bậc n thì tỷ sai phân bậc nhất là một đa thức bậc n-1, tỷ sai
phân bậc hai
là một đa thức bậc n-2, , tỷ sai phân bậc n của P
)(xP
n
),(
0
xxP
n
),,(
10
xxxP
n
n
(x) là đa thức bậc 0,
và tỷ sai phân bậc n + 1 của P
n
(x) là đa thức = 0. Kết luận này dễ chứng minh
dựa vào định lý Bezout.
), ,,,(
10 nn

),(),(
),,(
xx
xxPxxP
xxxP
−
−
=
),,,().(),,(),,(
210221010
xxxxPxxxxxPxxxP
nnn
−
−=
. . . . . . . . . .
), ,,().(), ,(), ,,(
10111,010 −−−−
−
−
=
nnnnnn
xxxPxxxxxPxxxP
), ,,().(), ,,(), ,,(
01010 nnnnnnn
xxxPxxxxxPxxxP
−
+
=
−


là đa thức nội suy của hàm tại các nút tức là

)(xP
n
)(xf
n
xxx , ,,
10
),()(
iin
xfxP = ),0( ni = thì công thức (4.3.1) có thể viết thành
), ,,()) ()((
) ,,())((),()()()(
10110
210101000
nn
n
xxxfxxxxxx
xxxfxxxxxxfxxxfxP
−
−−−+
−
−
+
−+=

(2-2.3)
hay
24
NCT-FIT-HNUE Computional methods and Optimization Problems

), ,()(),,()(),()()()(
30221011000
+
−
+
−
+−+= xxfxxxxxfxxxxfxxxfxP
2.3.3. Đánh giá sai số của nội suy Newton mốc không đều
Từ định nghĩa của các tỷ sai phân viết cho hàm , tương tự như trong tiểu mục trước, có thể
thu được
)(xf
), ,,,()) ((), ,,()) ((
) ,,())((),()()()(
1001010
210101000
nnnn
xxxxfxxxxxxxfxxxx
xxxfxxxxxxfxxxfxf
−−+−−+
−
−
+
−
+
=
−

Để ý đến (2-2.3) ta viết được
), ,,,()()()(
101 nnn

x f(x) T.s.pbậc 1 T.s.p bậc 2 T.s.p bậc 3 T.s.p bậc 4
x
0
f(x
0
) f(x
o
,x
1
) f(x
0
,x
1
,x
2
) f(x
0
,x
1
,x
2
,x
3
) f(x
0
,x
1
,x
2
,x

2
) f(x
2
,x
3
) f(x
2
,x
3
,x
4
)
x
3
f x
3
) f(x
3
,x
4
)
x
4
f(x
4
)
25