Bài giảng Phương pháp số - Bài 1: Giới thiệu chung các hệ thống số và sai số - Nguyễn Thị Vinh

PHƢƠNG PHÁP SỐ
BÀI 1
GIỚI THIỆU CHUNG
CÁC HỆ THỐNG SỐ & SAI SỐ
Giảng viên: ThS. Nguyễn Thị Vinh
Email: vinhnt@wru.vn
Website: 
https://sites.google.com/site/phphapso/home/bai-giang
GIỚI THIỆU CHUNG VỀ MÔN HỌC
- Số tín chỉ: 4 
- Số giờ: 60 (45LT+15TH )
- Chƣơng trình đào tạo ngành: CNTT
- Đánh giá: 
Điểm chuyên cần, bài tập, lập trình 25% 
Kiểm tra giữa kỳ: 15% 
Điểm thi kết thúc môn học: 60% 
- Môn tiên quyết: Toán I, II, III, Tin Đại cƣơng; 
- Môn học trƣớc: Cấu trúc Dữ liệu và Giải thuật;
Toán rời rạc. 
PHƢƠNG PHÁP SỐ-Bài 1 2
TÓM TẮT NỘI DUNG
- Nội dung:
Khảo sát các phƣơng pháp số cơ bản đƣợc sử
dụng để giải các bài toán trong Toán học, Khoa học
và Kỹ thuật.
– Yêu cầu
Biết tự giải các bài toán đó
Biết giải trên máy tính bằng cách
1. Sử dụng phần mềm có sẵn
2. Lập trình
PHƢƠNG PHÁP SỐ-Bài 1 4
CÁC CHỦ ĐỀ
1. Các hệ thống số và sai số
2. Nghiệm của các phƣơng trình phi tuyến 
3. Giải hệ phƣơng trình tuyến tính
4. Nội suy và xấp xỉ hàm 
5. Tính đạo hàm và tích phân 
6. Giải các bài toán của phƣơng trình vi 
phân thƣờng
PHƢƠNG PHÁP SỐ-Bài 1 5
TÀI LIỆU
- Giáo trình chính:
Conte, S.D. & Boor, C. de. Cơ sở Giải Tích Số - Một
cách tiếp cận Thuật toán. (Dịch từ cuốn Elementary
numerical analysis. McGraw-Hill, 3rd Ed.)
- Tài liệu tham khảo
[1]. Shampine, L.F., Allen, R.C. Jr & Pruess, S. (1997).
Fundamentals of numerical computing. Wiley.
[2]. S.C. Chapra and R.P. Canale (2002). Numerical
Methods for Engineers, Fourth Edition. McGraw-Hill
[3]. Dƣơng Thủy Vỹ, Giáo trình phương pháp tính,
NXBKH & KT, 2002
PHƢƠNG PHÁP SỐ-Bài 1 6
SỰ CẦN THIẾT CỦA MÔN HỌC (1)
• Trong chƣơng trình đào tạo kỹ sƣ CNTT, chúng ta đã
học ba môn Toán 1, Toán 2, Toán 3. Các môn học này
tập trung chủ yếu vào việc tìm các lời giải đúng cho
các bài toán
• Hầu hết các chƣơng trình máy tính đƣợc sử dụng trong
KHKT và Kinh tế đều tìm các lời giải bằng số cho các
bài toán này (vì các lời giải đúng bị hạn chế).
• Đối với các kỹ sƣ CNTT, điều quan trọng là hiểu các
khái niệm cơ bản của các phƣơng pháp số để có thể sử
dụng một cách hiệu quả các phần mềm có sẵn và tự
phát triển các chƣơng trình tính toán của mình. 
PHƢƠNG PHÁP SỐ-Bài 1 7
SỰ CẦN THIẾT CỦA MÔN HỌC (2)
• Các phƣơng trình đại số bậc cao và các phƣơng
trình phi tuyến thƣờng không có công thức nghiệm
đúng
• Các hệ phƣơng trình tuyến tính cỡ lớn không dễ
giải đƣợc bằng công thức Cramer
• Việc tính tích phân xác định bằng công thức
Newton-Leibnitz phụ thuộc vào sự tồn tại nguyên
hàm của hàm dƣới dấu tích phân
• Các bài toán về phƣơng trình vi phân dựa trên các
công thức nghiệm đúng là không khả thi
Các phƣơng pháp số giải các bài toán trên có thể 
cho lời giải gần đúng với độ chính xác mong muốn!
PHƢƠNG PHÁP SỐ-Bài 1 8
SỰ CẦN THIẾT CỦA MÔN HỌC (3)
Nguyên nhân là do sai số ban đầu mắc phải khi tính e-1 bị
khuếch đại lên sau mỗi lần tính
PHƢƠNG PHÁP SỐ-Bài 1 9
Ví dụ 1: Tính tích phân )n0(I dxexI n
1
0
1xn
n  
Tích phân từng phần
 nI1 dxexnexI 1-n
1
0
1x1n
1
0
1xn
N 
 0,36787edxe-exdxxeI 1-
1
0
1-x
1
0
1x
1
0
1x
1 
Khi n = 9, I9 ≈ -0,068480 < 0. dù ta tăng độ chính xác của
e-1 đến bao nhiêu đi nữa!
SỰ CẦN THIẾT CỦA MÔN HỌC (4)
Các lời giải đúng không luôn luôn có tính thực tiễn!
PHƢƠNG PHÁP SỐ-Bài 1 10
Ví dụ 2: Xét việc giải hệ phƣơng trình tuyến tính
Ax = b, An x n (detA ≠ 0), bn x 1
Theo qui tắc Cramer:
xi = ∆i / ∆ , i = 1,  , n 
Trong đó ∆ = detA, ∆i = detAi với Ai suy từ ma trận A bằng
cách thay cột thứ i bởi cột b
 Phải tính (n+1) định thức cấp n. Mỗi định thức có n! số hạng,
mỗi số hạng có n thừa số (nên phải thực hiện n-1 phép nhân.)
 Tổng số phép nhân phải thực hiện là (n+1) n! (n-1).
 Với n = 20, và máy tính thực hiện đƣợc 5000 phép nhân
1 giây thì phải mất 300 000 000 năm!
KHÁI NIỆM PHƢƠNG PHÁP SỐ
• Phương pháp số (Numerical Methods hay Numerical
Analysis) nghiên cứu lời giải bằng số trên máy tính
của các bài toán
• Ba giai đoạn giải bài toán của Phƣơng pháp số
1. Lập mô hình toán (công thức hóa) bài toán
2. Tìm thuật toán thích hợp để cải thiện:
- Độ chính xác của lời giải (các loại sai số)
- Sự hội tụ (số lần lặp, xử lí khi không hội tụ)
3. Lập trình / sử dụng chƣơng trình có sẵn.
PHƢƠNG PHÁP SỐ-Bài 1 11
CÁC HỆ THỐNG SỐ (1)
PHƢƠNG PHÁP SỐ-Bài 1 12
Sơ đồ Hoorner
(anan-1a0)2 = an2
n + an-12
n-1 +  + a02
0 = pn(2)
= ((((an2 + an-1)2 + an-2)2 + an-3)2 +  + a1)2 + a0
trong đó các hệ số ak là 0 hoặc 1 
Thuật toán:
bn = an
bn-1 = an-1 + bn 2
bn-2 = an-2 + bn-1 2
bn-3 = an-3 + bn-2 2
..........................
b0 = a0+ b1 2
Khi đó b0 = pn(2)
an an-1 an-2 . a0
+ 2bn 2bn-1  2b1 (x 2)
bn bn-1 bn-2  b0 = pn(2)
Ví dụ (1101)2 = p3(2) = 1310
1 1 0 1 
+ 2 x 1 2 x 3 2 x 6 (x 2)
1 3 6 13 = p3(2) 
1. Chuyển các số nguyên hệ nhị phân sang hệ thập phân
CÁC HỆ THỐNG SỐ (2)
PHƢƠNG PHÁP SỐ-Bài 1 13
Thuật toán: chuyển số nguyên (anan-1a0)10 = (bmbm-1b0)2
Bƣớc 1: chuyển các chữ số an an-1a0 thành các số nguyên 
nhị phân.
Bƣớc 2: sử dụng sơ đồ Hoorner để tính pn(x) tại x=10=(1010)2
Ví dụ (187)10 = 1.10
2 + 8.101 + 7.100 = p2(1010)
= 1 x (1010)2 + 1000 x 1010 + 111 x (1010)0
1 1000 111
+ 1010 x 1 1010 x 1 0010
1 1 0010 1011 1011= p2(1010)
Vậy (187)10 = (1011 1011)2
2. Chuyển các số nguyên hệ thập phân sang hệ nhị phân
CÁC HỆ THỐNG SỐ (3)
PHƢƠNG PHÁP SỐ-Bài 1 14
Thuật toán:
Cho số xF giữa 0 và 1 và 
chọn cơ số β = 2. Tạo 
các số b1, b2, b3, ... theo 
phép đệ quy sau đây
c0 = x F
c1 = β(c0)F b1 = [c1]
c2 = β(c1)F b2 = [c2]
c3 = β(c2)F b3 = [c3]
.......................................
Khi đó
3. Chuyển phần lẻ thập phân sang phần lẻ nhị phân

1k
k
kF21F βb)b(bx 
Ví dụ 1: x F = 0.625 ta có c0 = x F
c1 = 2 (0.625)F = 1.25 b1 = 12
c2 = 2 (1.25)F = 0.5 b2 = 02
c3 = 2 (0.5)F = 1.0 b3 = 12
 bk = 0 khi k > 3 vì c3 nguyên
 (0.625)10 = (0.101)2
Ví dụ 2: x F = 10
–1 = 0.1 ta có c0 = x F
c1 = 2(0.1) F = 0.2 b1 = 02
c2 = 2(0.2) F = 0.4 b2 = 02
c3 = 2(0.4) F = 0.8 b3 = 02
c4 = 2(0.8) F = 1.6 b4 = 12
c5= 2(1.6) F = 1.2 b5 = 12
 trở về phần thập phân của 0.2 nên
các chữ số quay lại chu kì 0011
 (0.1)10 = (0.0 0011 0011 ... )2
CÁC HỆ THỐNG SỐ (4)
PHƢƠNG PHÁP SỐ-Bài 1 15
Thuật toán: Chuyển xF = (0.anan-1a0)2= (0.bmbm-1b0)10
Trong công thức trƣớc, chọn β = 10 rồi sử dụng phép toán số 
học nhị phân tìm các bi theo phép đệ quy
4. Chuyển phần lẻ nhị phân sang phần lẻ thập phân
Ví dụ Cho xF = (0.101)2 với β = 10 = (1010)2 ta có 
c0 = xF = 0.101 βc0 =1010 x 0.101 = 110.01
 b1 = [βc0] = 110 = 610
c1 = (βc0)F = 0.01 βc1 = 1010 x 0.01 = 10.10 b2 = 10 = 210
c2 = (βc1)F = 0.1 βc2 =1010 x 0.1 = 101 b3 = 101 = 510
c3 = (βc2)F = 0 Dừng vì c3 nguyên
Vậy (0.101)2 = (0.625)10
SỐ HỌC SỐ THỰC ĐỘNG (1)
PHƢƠNG PHÁP SỐ-Bài 1 16
1. Một số khái niệm:
• Một số thực động n chữ số trong hệ cơ số β là số
x = ±(0.d1d2d3 ... dn)β β
e
trong đó phần lẻ-β, (.d1d2d3 ... dn)β gọi là phần định trị, và số
nguyên e (m < e < M) gọi là số mũ. Đối với hầu hết các máy
tính, β =2, M = -m = 27.
• Số thực động nhƣ thế đƣợc coi là chuẩn hóa khi d1 ≠ 0,
hoặc d1 = d2 = ... = dn = 0.
• Độ dài n của các số thực động thƣờng đƣợc xác định bằng 
độ dài một từ (word)của máy tính. Có hai loại độ dài: Loại 
ngắn gọi là độ chính xác đơn – single, loại dài (gấp đôi về 
dung lƣợng lƣu trữ) gọi là độ chính xác gấp đôi – double
SỐ HỌC SỐ THỰC ĐỘNG (2)
PHƢƠNG PHÁP SỐ-Bài 1 17
2. Hai cách chuyển một số thực thành một số thực động
• Làm tròn: fl(x) đƣợc chọn nhƣ một số thực động đƣợc 
chuẩn hóa gần x nhất
• Ngắt bỏ: fl(x) đƣợc chọn nhƣ số thực động đƣợc chuẩn 
hóa gần nhất nằm giữa x và 0
Ví dụ: với độ dài chuẩn n = 2, xét
(.66)10
 trònlàm(.67)10
3
2
0
0
bá ng¾t 
fl
làm tròn
838fl
3
3
(.84)10 
(.83)10 ng¾t bá
I-----------------I-----I-----I-------
0 0.66 2/3 0.67
SỐ HỌC SỐ THỰC ĐỘNG (3)
PHƢƠNG PHÁP SỐ-Bài 1 18
3. Sai số làm tròn
• Định nghĩa: Sai số làm tròn là sự khác biệt giữa x và fl(x)
(phụ thuộc vào kích thƣớc của x).
Nếu ta viết fl (x) = x(1 + δ) với δ = δ(x) là số phụ thuộc vào x,
thì fl (x) có thể chênh lệch với x một giá trị không vƣợt quá
biên của δ một cách độc lập với x
–β1–n < δ ≤ 0 bằng cách ngắt bỏ
n1β
2
1
δ bằng cách làm tròn
Đơn vị làm tròn u là giá trị lớn nhất có thể của |δ|
SỐ HỌC SỐ THỰC ĐỘNG (4)
PHƢƠNG PHÁP SỐ-Bài 1 19
4. Phép toán số thực động
• Khi một phép toán số học đƣợc áp dụng cho hai số thực
động, kết quả thƣờng sai lệch đối với một số thực động cùng
độ dài.
Ví dụ: cho các số thực động có hai chữ số lẻ thập phân
x = (0.20)101 = 2, y = (0.77)10–6 và z = (0.30)101 = 3
 x + y = (0.200000077)101, x * y = (0.154)10–5
Nếu kí hiệu ω là một trong các phép toán số học (cộng, trừ,
nhân hoặc chia) và ω* là phép toán số thực động cùng tên do
máy tính cung cấp, thì tuy rằng máy tính có thể đƣa ra kết
quả x ω* y đối với hai số thực động x và y, thƣờng là
x ω* y ≠ x ω y 
SỐ HỌC SỐ THỰC ĐỘNG (5)
PHƢƠNG PHÁP SỐ-Bài 1 20
4. Phép toán số thực động
Phép toán số thực động ω*, tƣơng ững với phép toán số học
thông thƣờng ω (+ - * / ) thƣờng đƣợc xây dựng sao cho
x ω* y = fl(x ω y )
 x ω* y = (x ω y ) (1 + δ) với δ nào đó mà |δ| ≤ u
hay x ω* y = (x ω y ) / (1 + δ) với δ nào đó mà |δ| ≤ u
Ví dụ f(x) = ở điểm x0 đƣợc tính bằng cách
với f(x0) = xn. 
Trong các phép tính số học động, ta tính tuần tự các số
với |δi| ≤ u với mọi i. 
n2x
δ))(1f(xδ)(1~~ 0
22
0 
nn
xxn
2
1-nn
2
12
2
01 x x..., ,x x,xx 
nx
~ tính cho f(x0) là giá trị chính xác của f(x) tại đối số 
đƣợc sửa đổi x = x0 (1+δ).
TỔN THÂT ĐÁNG KỂ VÀ 
SỰ LAN TRUYỀN SAI SỐ (1)
Mọi phép toán số thực động trong quá trình tính toán có
thể nảy sinh sai số, sai số này có thể bị khuyếch đại
hay thu nhỏ trong các phép toán sau đó.
PHƢƠNG PHÁP SỐ-Bài 1 21
• Khái niệm sai số:
- Cho x* là một xấp xỉ của số đúng x, hiệu x – x* gọi là sai
số theo x*, vậy số đúng = số xấp xỉ + sai số
- Sai số tuyệt đối theo x* là số |x – x*|
- Sai số tương đối theo x* là số α = (x – x*) / x. 
Nhận xét :
1. α gần với số (x – x*) / x* nếu nó nhỏ.
2. Nếu α = (x – x*) / x thì (x – x*) / x*= α / (1 – α )
TỔN THÂT ĐÁNG KỂ VÀ 
SỰ LAN TRUYỀN SAI SỐ (2)
PHƢƠNG PHÁP SỐ-Bài 1 22
• Tổn thất đáng kể:
Một trong những nguyên nhân chung nhất làm tăng sai số là
làm mất các chữ số có nghĩa (các chữ số của số đó kể từ
chữ số khác không đầu tiên tính từ trái sang phải)
Nếu x* là một xấp xỉ của x và sai số tuyệt đối |x – x*| lớn
nhất bằng 0.5 chữ số có nghĩa thứ r của hệ cơ số β của x,
thì ta nói rằng x* xấp xỉ x đến r chữ số có nghĩa hệ cơ số β,
|x – x*| ≤ βs–r+1/2
với s là số nguyên lớn nhất mà βs ≤ |x|.
Ví dụ, x* = 3 là xấp xỉ x = π với một chữ số có nghĩa, trong khi
1428.3
7
22
*x là một xấp xỉ của π với năm chữ số có nghĩa
TỔN THÂT ĐÁNG KỂ VÀ 
SỰ LAN TRUYỀN SAI SỐ (3)
Việc mất đi các chữ số có nghĩa chỉ nguy hiểm khi ta muốn 
giữ sai số tƣơng đối nhỏ và có thể tránh đƣợc bằng cách 
đoán trƣớc sự xuất hiện của nó
• Tổn thất đáng kể:
Cho x* = (0.76545421)101 và y* = (0.76544200)101 là các xấp 
xỉ của x và y tƣơng ứng, chính xác đến bảy chữ số
 z* = x* – y* = (0.12210000)10–3
chỉ còn chính xác đến ba chữ số
Số xấp xỉ Sai số tuyệt đối Sai số tƣơng đối Tỉ lệ tăng
x* .76545421E+01 |x–x*| .50E–07 αx .65320694E–08 αz/αx 125382
y* .76544200E+01 |y–y*| .50E–07 αy .65321706E–08 αz/αy 125380
z* .12210000E–03 |z–z*| .10E–06 αz .81900082E–03
PHƢƠNG PHÁP SỐ-Bài 1 23
TỔN THÂT ĐÁNG KỂ VÀ 
SỰ LAN TRUYỀN SAI SỐ (4)
• Sự lan truyền sai số:
Điều kiện của hàm f tại x mô tả sự nhạy cảm của hàm f(x) 
đối với sự thay đổi của đối số x, nó đƣợc đo bằng
PHƢƠNG PHÁP SỐ-Bài 1 24
f(x) f(x*) x x* f'(x) x
max / sao cho |x x*|"nho"
f(x) x f(x)
  
 
 
 Điều kiện của f tại x càng lớn bao nhiêu thì hàm f càng
đƣợc coi là có điều kiện yếu bấy nhiêu. Ví dụ
x2
1
)x('fx)x(f 
2
1
x
x
f(x)
(x)xf' x2
1
là xấp xỉ của điều kiện của f tại x. việc lấy các căn bậc hai là
một quá trình có điều kiện tốt, vì nó làm giảm sai số tương đối
TỔN THÂT ĐÁNG KỂ VÀ 
SỰ LAN TRUYỀN SAI SỐ (5)
• Sự lan truyền sai số:
Ví dụ: Tính điều kiện của hàm
PHƢƠNG PHÁP SỐ-Bài 1 25
Số này có thể rất lớn khi |x| gần 1. Vậy, với x gần 1 hoặc –1, 
hàm này có điều kiện rất yếu. Nó khuyếch đại các sai số 
tƣơng đối rất nhanh theo đối số x.
2x1
10
(x)f
2 2 2
2 2
f'(x)x [20x/(1 x ) ]x 2x
f(x) 10/(1 x ) |1 x |
TỔN THÂT ĐÁNG KỂ VÀ 
SỰ LAN TRUYỀN SAI SỐ (6)
PHƢƠNG PHÁP SỐ-Bài 1 26
• Sự lan truyền sai số:
Tính không ổn định mô tả sự nhậy cảm của quá trình tính
toán bằng số f(x) theo x, đã mắc phải các sai số làm tròn
không thể tránh khỏi khi thực hiện phép tính số học có độ
chính xác hữu hạn.
Có thể đánh giá thô các ảnh hƣởng này bằng cách lần lƣợt
xét các sai số làm tròn.
Giả sử có n bƣớc nhƣ vậy. Gọi
xi là đầu ra của bƣớc thứ i (x0 = x, xn = f(x) )
fi là hàm mô tả sự phụ thuộc của kết quả cuối cùng vào
các kết quả trung gian xi. (f0 = f)
Quá trình này là không ổn định khi mà một hay vài fi có điều
kiện lớn hơn nhiều so với điều kiện mà f = f0 có được.
i xi fi Điều kiện Nhận xét
0 x0 = x = 12345
1 x1 = x0 +1 f1(t) = t +1 Tốt
2 ½ < 1 Tốt
3 Tốt
4 x4 = x2 - x3 f3(t) = x2 - t
Yếu (khi t gần x2 sai số
10% ở trường hợp này)
TỔN THÂT ĐÁNG KỂ VÀ 
SỰ LAN TRUYỀN SAI SỐ (7)
1
1t
t
12 x x t(t)f2 
03 x x
tx
t
2 
PHƢƠNG PHÁP SỐ-Bài 1 27
• Sự lan truyền sai số:
Ví dụ xét hàm sau với x lớn, chẳng hạn x = 12345
x1xf(x) 
i xi fi Điều kiện Nhận xét
0 x0 = x = 12345
1 x1 = x0 +1 f1(t) = t +1 Tốt
2 1/2 Tốt
3
4 x4 = x2 +x3 f3(t) = x2+ t Tốt
5 x5 = 1/x4 f4(t)=1/ t 1
Đƣợc, sai số là
0.0003%
TỔN THÂT ĐÁNG KỂ VÀ 
SỰ LAN TRUYỀN SAI SỐ (8)
1
1t
t
12 x x t(t)f2 
03 x x
2
1
tx
t
2
PHƢƠNG PHÁP SỐ-Bài 1 28
• Sự lan truyền sai số:
x1x
1
f(x)
 Viết lại công thức hàm
NĂM PHƢƠNG PHÁP 
ƢỚC LƢỢNG SAI SỐ
1. Sử dụng độ chính xác gấp đôi: tổng sai số bằng chênh 
lệch kết quả của lời giải độ chính xác đơn so với độ chính xác gấp 
đôi 
2. Phép số học khoảng: mỗi số đƣợc thể hiện bằng giá trị lớn 
nhất và nhỏ nhất mà nó có thể chấp nhận
3. Phép số học chữ số có nghĩa: chỉ những chữ số có nghĩa 
mới đƣợc giữ lại, các chữ số khác đều bị bỏ đi
4. Tiếp cận thống kê: tính độ lệch quân phƣơng, phƣơng sai của 
phân phối các sai số làm tròn địa phƣơng
5. Phân tích sai số ngƣợc: nghiên cứu xem giá trị (chính xác) 
của hàm f(x) thay đổi thế nào khi đối số x bị sửa đổi
PHƢƠNG PHÁP SỐ-Bài 1 29
BÀI TẬP
Bài tập tính toán: 
1.1-1, 1.1-2, 1.2-1, 1.3-1, 1.4-1, 1.4-3
PHƢƠNG PHÁP SỐ-Bài 1 30