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ố - 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