Bài giảng Phương pháp số - Bài 1: Giới thiệu chung các hệ thống số & sai số
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
Website:
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%
60%
Điểm thi kết thúc môn học:
- 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)
1
n x1
Ví dụ 1: Tính tích phân
I x e dx (I 0 n)
n
n
0
Tích phân từng phần
1
1
n x1
n1 x1
I x e nx e dx 1 nI
N
n-1
0
0
1
1
1
x1
x1
x-1
-1
I xe dx xe
- e dx e 0,36787
1
0
0
0
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!
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
SỰ CẦN THIẾT CỦA MÔN HỌC (4)
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!
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
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)
1. Chuyển các số nguyên hệ nhị phân sang hệ thập phân
Sơ đồ Hoorner
(anan-1…a0)2 = an2n + an-12n-1 + … + a020 = 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
an
+
an-1 an-2 …. a0
Thuật toán:
bn = an
2bn 2bn-1 … 2b1 (x 2)
bn-1 = an-1 + bn 2
bn-2 = an-2 + bn-1 2
bn-3 = an-3 + bn-2 2
..........................
b0 = a0+ b1 2
bn
bn-1 bn-2 …
b0 = pn(2)
Ví dụ (1101)2 = p3(2) = 1310
1
+
1
1
0
1
2 x 1 2 x 3 2 x 6
(x 2)
Khi đó b0 = pn(2)
PHƢƠNG PHÁP SỐ-Bài 1
3
6
13 = p3(2)
12
CÁC HỆ THỐNG SỐ (2)
2. Chuyển các số nguyên hệ thập phân sang hệ nhị phân
Thuật toán: chuyển số nguyên (anan-1…a0)10 = (bmbm-1…b0)2
Bƣớc 1: chuyển các chữ số an an-1…a0 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.102 + 8.101 + 7.100 = p2(1010)
= 1 x (1010)2 + 1000 x 1010 + 111 x (1010)0
1
+
1
1000
111
1010 x 1
1 0010
1010 x 1 0010
1011 1011= p2(1010)
Vậy (187)10 = (1011 1011)2
PHƢƠNG PHÁP SỐ-Bài 1
13
CÁC HỆ THỐNG SỐ (3)
3. Chuyển phần lẻ thập phân sang phần lẻ nhị phân
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
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 đó
x (b b ) b βk
F
1 2
F
k
k1
(0.1)10 = (0.0 0011 0011 ... )2
PHƢƠNG PHÁP SỐ-Bài 1
14
CÁC HỆ THỐNG SỐ (4)
4. Chuyển phần lẻ nhị phân sang phần lẻ thập phân
Thuật toán: Chuyển xF = (0.anan-1…a0)2= (0.bmbm-1…b0)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
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
PHƢƠNG PHÁP SỐ-Bài 1
15
SỐ HỌC SỐ THỰC ĐỘNG (1)
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
PHƢƠNG PHÁP SỐ-Bài 1
16
SỐ HỌC SỐ THỰC ĐỘNG (2)
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
0
2
(.67)10 làm tròn
fl
I-----------------I-----I-----I-------
0.66 2/3 0.67
0
3
0
(.66)10 ng¾bt á
3
(.84)10 làm tròn
(.83)103 ng¾t bá
fl 838
PHƢƠNG PHÁP SỐ-Bài 1
17
SỐ HỌC SỐ THỰC ĐỘNG (3)
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ỏ
bằng cách làm tròn
1
δ β1n
2
Đơn vị làm tròn u là giá trị lớn nhất có thể của |δ|
PHƢƠNG PHÁP SỐ-Bài 1
18
SỐ HỌC SỐ THỰC ĐỘNG (4)
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
PHƢƠNG PHÁP SỐ-Bài 1
19
SỐ HỌC SỐ THỰC ĐỘNG (5)
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
2n
Ví dụ f(x) = ở điểm x đƣợc tính bằng cách
0
x1 x02, x2 x12,..., xn xn2-1
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ố
2n
2n
~ ~
với |δi| ≤ u với mọi i.
xn x0 (1 δ) f(x0(1 δ))
~
x tính cho f(x0) là giá trị chính xác của f(x) tại đối số
n
đƣợc sửa đổi x = x0 (1+δ).
PHƢƠNG PHÁP SỐ-Bài 1
20
TỔN THÂT ĐÁNG KỂ VÀ
SỰ LAN TRUYỀN SAI SỐ (1)
• 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 – α )
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
Tải về để xem bản đầy đủ
29 trang
15/01/2024
12000
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Phương pháp số - Bài 1: Giới thiệu chung các hệ thống số & sai số", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_phuong_phap_so_bai_1_gioi_thieu_chung_cac_he_thong.pdf
