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

Nội dung text: 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

1. 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: [email protected] Website:
2. 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
3. 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
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
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
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
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
8. SỰ CẦN THIẾT CỦA MÔN HỌC (3) 1 n x 1 Ví dụ 1: Tính tích phân In x e dx (In 0 n) Tích phân từng phần 0 1 n x 1 1 n 1 x 1 IN x e n x e dx 1 nIn-1 0 0 1 1 x 1 x 1 1 x-1 -1 I1 xe dx xe - e dx e 0,36787 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
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
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
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 n n-1 0 (anan-1 a0)2 = an2 + an-12 + + a02 = 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: an an-1 an-2 . a0 bn = an + 2bn 2bn-1 2b1 (x 2) bn-1 = an-1 + bn 2 bn bn-1 bn-2 b0 = pn(2) bn-2 = an-2 + bn-1 2 Ví dụ (1101) = p (2) = 13 bn-3 = an-3 + bn-2 2 2 3 10 1 1 0 1 b0 = a0+ b1 2 + 2 x 1 2 x 3 2 x 6 (x 2) Khi đó b0 = pn(2) 1 3 6 13 = p3(2) PHƢƠNG PHÁP SỐ-Bài 1 12
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 2 1 0 Ví dụ (187)10 = 1.10 + 8.10 + 7.10 = 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 PHƢƠNG PHÁP SỐ-Bài 1 13
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 Thuật toán: Ví dụ 1: x F = 0.625 ta có c0 = x F c = 2 (0.625) = 1.25 b = 1 Cho số xF giữa 0 và 1 và 1 F 1 2 c = 2 (1.25) = 0.5 b = 0 chọn cơ số β = 2. Tạo 2 F 2 2 c3 = 2 (0.5)F = 1.0 b3 = 12 các số b1, b2, b3, theo bk = 0 khi k > 3 vì c3 nguyên phép đệ quy sau đây (0.625)10 = (0.101)2 c = x –1 0 F Ví dụ 2: x F = 10 = 0.1 ta có c0 = x F c1 = β(c0)F b1 = [c1] c1 = 2(0.1) F = 0.2 b1 = 02 c = 2(0.2) = 0.4 b = 0 c2 = β(c1)F b2 = [c2] 2 F 2 2 c = 2(0.4) = 0.8 b = 0 c = β(c ) b = [c ] 3 F 3 2 3 2 F 3 3 c = 2(0.8) = 1.6 b = 1 4 F 4 2 Khi đó c5= 2(1.6) F = 1.2 b5 = 12 trở về phần thập phân của 0.2 nên k x F (b1b2 )F bkβ các chữ số quay lại chu kì 0011 k 1 (0.1)10 = (0.0 0011 0011 )2 PHƢƠNG PHÁP SỐ-Bài 1 14
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
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ố e x = ±(0.d1d2d3 dn)β β 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
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 2 (.67)100 làm tròn fl I I I I 0 3 (.66)10 ng¾tbá 0 0.66 2/3 0.67 (.84)103 làm tròn fl 838 3 (.83)10 ng¾t bá PHƢƠNG PHÁP SỐ-Bài 1 17
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ỏ 1 δ β1 n bằng cách làm tròn 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
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
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) = x ở điểm x0 đƣợc tính bằng cách 2 2 2 x1 x0, x2 x1 , , xn xn-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 δ)) ~ xn 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+δ). PHƢƠNG PHÁP SỐ-Bài 1 20
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
21. TỔN THÂT ĐÁNG KỂ VÀ SỰ LAN TRUYỀN SAI SỐ (2) • 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 22 x* 3.1428 là một xấp xỉ của π với năm chữ số có nghĩa 7 PHƢƠNG PHÁP SỐ-Bài 1 22
22. TỔN THÂT ĐÁNG KỂ VÀ SỰ LAN TRUYỀN SAI SỐ (3) • 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 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ó PHƢƠNG PHÁP SỐ-Bài 1 23
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 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ụ 1 x 1 f'(x)x 2 x 1 f (x) x f '(x) 2 x f(x) x 2 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 PHƢƠNG PHÁP SỐ-Bài 1 24
24. 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 10 f (x) 1 x2 f'(x)x [20x/(1 x2 ) 2 ]x 2x 2 f(x) 10/(1 x22 ) |1 x | 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. PHƢƠNG PHÁP SỐ-Bài 1 25
25. TỔN THÂT ĐÁNG KỂ VÀ SỰ LAN TRUYỀN SAI SỐ (6) • 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. PHƢƠNG PHÁP SỐ-Bài 1 26
26. TỔN THÂT ĐÁNG KỂ VÀ SỰ LAN TRUYỀN SAI SỐ (7) • Sự lan truyền sai số: Ví dụ xét hàm sau với x lớn, chẳng hạn x = 12345 f(x) x 1 x i xi fi Điều kiện Nhận xét 0 x0 = x = 12345 t 1 1 x1 = x0 +1 f1(t) = t +1 t 1 Tốt 2 x2 x1 f2 (t) t ½ < 1 Tốt 3 x3 x 0 Tốt t Yếu (khi t gần x2 sai số 4 x4 = x2 - x3 f3(t) = x2 - t x 2 t 10% ở trường hợp này) PHƢƠNG PHÁP SỐ-Bài 1 27
27. TỔN THÂT ĐÁNG KỂ VÀ SỰ LAN TRUYỀN SAI SỐ (8) • Sự lan truyền sai số: 1 Viết lại công thức hàm f(x) x 1 x i xi fi Điều kiện Nhận xét 0 x0 = x = 12345 t x1 = x0 +1 f1(t) = t +1 1 1 t 1 Tốt 2 x2 x1 f2 (t) t 1/2 Tốt 3 x3 x 0 t 1 4 x4 = x2 +x3 f3(t) = x2+ t Tốt x 2 t 2 Đƣợc, sai số là 5 x5 = 1/x4 f4(t)=1/ t 1 0.0003% PHƢƠNG PHÁP SỐ-Bài 1 28
28. 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
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