Bài giảng Phương pháp số: Bài 1 - ThS. 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%

Điểm thi kết thúc môn học: 60%

Kiểm tra giữa kỳ: 15%

- 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 giải trên máy tính bằng cách

 Biết tự giải các bài toán đó

1. Sử dụng phần mềm có sẵn

PHƢƠNG PHÁP SỐ-Bài 1

4

2. Lập trình

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 (Dịch từ cuốn Elementary cách tiếp cận Thuật toán. 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ầ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ế).

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

• Đối với các kỹ sƣ CNTT, điều quan trọng là hiểu các

PHƢƠNG PHÁP SỐ-Bài 1

7

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.

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

giải đƣợc bằng công thức Cramer

• Các hệ phƣơng trình tuyến tính cỡ lớn không dễ

• 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

PHƢƠNG PHÁP SỐ-Bài 1

8

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!

SỰ CẦN THIẾT CỦA MÔN HỌC (3)

Ví dụ 1: Tính tích phân

Tích phân từng phần

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!

PHƢƠNG PHÁP SỐ-Bài 1

9

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

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

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

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) 1. Chuyển các số nguyên hệ nhị phân sang hệ thập phân

Sơ đồ Hoorner

an +

an-2 …. 2bn-1 … bn-2 …

a0 2b1 b0 = pn(2)

(x 2)

bn

(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-1 2bn bn-1 Ví dụ (1101)2 = p3(2) = 1310 1 1 1 0

+ 2 x 1 2 x 3 2 x 6 (x 2)

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)

PHƢƠNG PHÁP SỐ-Bài 1

12

1 3 6 13 = p3(2)

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 1000 111

+ 1010 x 1 1010 x 1 0010

Vậy

1 1 0010 1011 1011= p2(1010)

(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 = 1.0  b3 = 12 c3 = 2 (0.5)F

 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

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 đó

 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

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

PHƢƠNG PHÁP SỐ-Bài 1

15

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)

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.

PHƢƠNG PHÁP SỐ-Bài 1

16

• Độ 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)

• 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

2. Hai cách chuyển một số thực thành một số thực động

• 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

I-----------------I-----I-----I------- 0

0.66 2/3 0.67

PHƢƠNG PHÁP SỐ-Bài 1

17

Ví dụ: với độ dài chuẩn n = 2, xét

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). fl (x) = x(1 + δ) với δ = δ(x) là số phụ thuộc vào x, Nếu ta viết 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

bằng cách làm tròn

–β1–n < δ ≤ 0 bằng cách ngắt bỏ

PHƢƠNG PHÁP SỐ-Bài 1

18

Đơ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)

• 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

4. Phép toán số thực động

 x + y = (0.200000077)101, x * y = (0.154)10–5

x = (0.20)101 = 2, y = (0.77)10–6 và z = (0.30)101 = 3

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à

PHƢƠNG PHÁP SỐ-Bài 1

19

x ω* y ≠ x ω y

SỐ HỌC SỐ THỰC ĐỘNG (5)

x ω* y = fl(x ω y )

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 = (x ω y ) (1 + δ) hay x ω* y = (x ω y ) / (1 + δ) với δ nào đó mà |δ| ≤ u 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. 

PHƢƠNG PHÁP SỐ-Bài 1

20

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)

là sai

• 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 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 – α )

PHƢƠNG PHÁP SỐ-Bài 1

21

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 đó.

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

PHƢƠNG PHÁP SỐ-Bài 1

22

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)

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

Sai số tuyệt đối

Sai số tƣơng đối

Tỉ lệ tăng

Số xấp xỉ

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

.81900082E–03

z* .12210000E–03

|z–z*|

.10E–06 αz

23

PHƢƠNG PHÁP SỐ-Bài 1

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

 Đ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ụ

24

PHƢƠNG PHÁP SỐ-Bài 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

25

PHƢƠNG PHÁP SỐ-Bài 1

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.

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

xn = f(x) )

xi là đầu ra của bƣớc thứ i (x0 = 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)

PHƢƠNG PHÁP SỐ-Bài 1

26

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.

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

i

Điều kiện

Nhận xét

fi

0

xi x0 = x = 12345

1

Tốt

x1 = x0 +1

f1(t) = t +1

2

Tốt

½ < 1

3

Tốt

4

f3(t) = x2 - t

x4 = x2 - x3

Yếu (khi t gần x2 sai số 10% ở trường hợp này)

PHƢƠNG PHÁP SỐ-Bài 1

27

TỔN THÂT ĐÁNG KỂ VÀ SỰ LAN TRUYỀN SAI SỐ (8)

• Sự lan truyền sai số:

Viết lại công thức hàm

Điều kiện

Nhận xét

i

fi

0

xi x0 = x = 12345 x1 = x0 +1

f1(t) = t +1

Tốt

1

Tốt

1/2

2

3

Tốt

4

x4 = x2 +x3

f3(t) = x2+ t

1

5

x5 = 1/x4

Đƣợc, sai số là 0.0003%

PHƢƠNG PHÁP SỐ-Bài 1

28

f4(t)=1/ t

NĂM PHƢƠNG PHÁP ƢỚC LƢỢNG SAI SỐ

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

1. Sử dụng độ chính xác gấp đôi: tổng sai số bằng chênh

nhất và nhỏ nhất mà nó có thể chấp nhận

2. Phép số học khoảng: mỗi số đƣợc thể hiện bằng giá trị lớ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

phân phối các sai số làm tròn địa phƣơng

4. Tiếp cận thống kê: tính độ lệch quân phƣơng, phƣơng sai của

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

5. Phân tích sai số ngƣợc: nghiên cứu xem giá trị (chính xác)

BÀI TẬP

Bài tập tính toán:

PHƢƠNG PHÁP SỐ-Bài 1

30

1.1-1, 1.1-2, 1.2-1, 1.3-1, 1.4-1, 1.4-3