Giải Tích Số - 123doc

Đó là khoa học tính toán mà giải tích số là một môn học 1.3 CÁC BƯỚC GIẢI MỘT BÀI TOÁN CỦA GIẢI TÍCH SỐ Để giải quyết một bài toán, người ta phải thực hiện quá trình mô phỏng sau đây:

TRƯỜNG ĐẠI HỌC THỦY LỢI 

GIẢI TÍCH SỐ 

[Tài liệu giảng dạy ở bậc đại học] 

Nguyễn Thị Vinh

HÀ NỘI 2010

1 CHƯƠNG 1: MỞ ĐẦU 4

1.1 GIẢI TÍCH SỐ LÀ GÌ 4

1.2 SỰ KHÁC BIỆT GIỮA TOÁN HỌC LÍ THUYẾT VÀ TOÁN HỌC TÍNH TOÁN 4 1.3 CÁC BƯỚC GIẢI MỘT BÀI TOÁN CỦA GIẢI TÍCH SỐ 5

1.4 THUẬT TOÁN VÀ ĐỘ PHỨC TẠP 6

1.4.1 Thuật toán 6

1.4.2 Độ phức tạp thuật toán 7

1.5 SỐ XẤP XỈ VÀ SAI SỐ 10

1.5.1 Số xấp xỉ, sai số tuyệt đối và sai số tuong đối 10

1.5.2 Cách viết số xấp xỉ 11

1.5.3 Qui tròn số và sai số qui tròn 11

1.5.4 Các công thức tính sai số 12

1.6 BÀI TẬP CHƯƠNG 1 13

2 CHƯƠNG 2: GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH 14

2.1 PHƯƠNG PHÁP KHỬ GAUSS - JORDAN 14

2.1.1 Thuật toán 14

2.1.2 Ưu, nhược điểm của phương pháp 14

2.1.3 Các ví dụ 14

2.1.4 Sơ đồ khối và chương trình 16

2.1.5 Đánh giá độ phức tạp thời gian 17

2.1.6 Ứng dụng phương pháp khử Gauss vào việc tính định thức 17

2.2 GIẢI HỆ PTTT DẠNG BA ĐƯỜNG CHÉO 18

2.2.1 Đặt vấn đề 18

2.2.2 Áp dụng phương pháp khử Gauss–Jordan: 18

2.2.3 Phương pháp truy đuổi (nắn thẳng) giải hệ ba đường chéo 19

2.3 PHƯƠNG PHÁP LẶP SEIDEL 21

2.3.1 Thuật toán 21

2.3.2 Điều kiện hội tụ và đánh giá sai số của phương pháp 21

2.3.3 Ví dụ 22

2.3.4 Sơ đồ khối và chương trình 24

2.3.5 Sử dụng Solver trong EXCEL giải hệ PTTT 26

2.4 TÍNH MA TRẬN NGHỊCH ĐẢO 26

2.4.1 Ứng dụng phương pháp Gauss tính ma trận nghịch đảo 26

2.4.2 Tính ma trận nghịch đảo A –1 bằng phương pháp lặp Newton 27

2.4.3 Sử dụng hàm MINVERSE trong EXCEL tìm A -1 29

2.5 BÀI TẬP CHƯƠNG 2 31

3 CHƯƠNG 3: PHÉP NỘI SUY VÀ ĐƯỜNG CONG PHÙ HỢP 32

3.1 KHÁI QUÁT VỀ BÀI TOÁN NỘI SUY 32

3.1.1 Đặt vấn đề 32

3.1.2 Đa thức nội suy 32

3.1.3 Sơ đồ Horner tính giá trị của đa thức 33

3.2 ĐA THỨC NỘI SUY LAGRANGE 33

3.2.1 Lập công thức 33

3.2.2 Ví dụ: Tìm giá trị gần đúng của f(2,6) từ bảng số liệu 34

3.2.3 Sai số: Người ta đã chứng minh rằng nếu hàm f(x) khả vi liên tục đến cấp N+1 trên đoạn [a,b] chứa tất cả các mốc nội suy x k , k = 0, , N thì sai

số của nội suy Lagrange là 34

3.2.4 Sơ đồ khối và chương trình 35

3.3 ĐA THỨC NỘI SUY NEWTON VỚI BƯỚC CÁCH ĐỀU 36

3.3.1 Bảng sai phân hữu hạn 36

Bảng sai phân hữu hạn 36

3.3.2 Đa thức nội suy Newton tiến 37

3.3.3 Đa thức nội suy Newton lùi 38

3.3.4 Công thức nội suy Newton với mốc quan sát bất kỳ 41

3.4 NỘI SUY SPLINE 43

3.4.1 Đặt vấn đề 43

3.4.2 Bài toán 43

3.4.3 Xây dựng công thức 43

3.4.4 Các bước giải bài toán nội suy Spline bậc ba 45

3.4.5 Ví dụ 45

3.4.6 Chương trình tính 45

3.5 PHƯƠNG PHÁP BÌNH PHƯƠNG BÉ NHẤT LÀM KHỚP DỮ LIỆU 46 3.5.1 Đặt vấn đề: 46

3.5.2 Lập công thức 47

3.5.3 Các ví dụ: 47

3.5.4 Các bước giải và chương trình 49

3.6 BÀI TẬP CHƯƠNG 3 50

4 CHƯƠNG 4: TÍNH ĐẠO HÀM VÀ TÍCH PHÂN XÁC ĐỊNH 51

4.1 TÍNH GẦN ĐÚNG ĐẠO HÀM 51

4.1.1 Xấp xỉ giá trị đạo hàm dựa vào bảng sai phân 51

4.1.2 Xấp xỉ đạo hàm bằng công thức nội suy 52

4.2 TÍNH GẦN ĐÚNG TÍCH PHÂN XÁC ĐỊNH 55

4.2.1 Lập công thức chung sử dụng đa thức nội suy Newton tiến 55

4.2.2 Quy tắc làm tăng độ chính xác của việc tính tích phân 59

4.3 BÀI TẬP CHƯƠNG 4 61

5 CHƯƠNG 5: GIẢI PHƯƠNG TRÌNH f(x) = 0 62

5.1 ĐẶT VẤN ĐỀ 62

5.1.1 Bài toán 62

5.1.2 Các bước giải 62

5.1.3 Tách nghiệm 62

5.2 CÁC PHƯƠNG PHÁP KIỆN TOÀN NGHIỆM 63

5.2.1 Phương pháp chia đôi 63

5.2.2 Phương pháp lặp đơn 64

5.2.3 Phương pháp dây cung 65

5.2.4 Phương pháp tiếp tuyến (Newton) 67

5.3 GIẢI HỆ PHƯƠNG TRÌNH PHI TUYẾN 69

5.3.1 Lập công thức: 69

Cho hệ phi tuyến 69 5.3.2 Các bước giải hệ phi tuyến bằng phương pháp lặp Newton-Raphson

70

5.3.3 Sơ đồ khối và chương trình 73

5.4 PHƯƠNG PHÁP LẶP SEIDEL 74

5.5 Sử dụng Solver trong EXCEL giải hệ phương trình phi tuyến 76

5.6 BÀI TẬP CHƯƠNG 5 77

6 CHƯƠNG 6: CÁC PHƯƠNG PHÁP SỐ GIẢI PHƯƠNG TRINH 78

VI PHÂN 78

6.1 ĐẶT VẤN ĐỀ 78

6.1.1 Bài toán Cauchy (bài toán giá trị đầu) 78

6.1.2 Bài toán biên hai điểm tuyến tính đối với PTVP cấp hai: 79

6.1.3 Các phương pháp số giải bài toán Cauchy 79

6.2 CÁC PHƯƠNG PHÁP SỐ GIẢI BÀI TOÁN CAUCHY 79

6.2.1 Phương pháp Euler 79

6.2.2 Phương pháp Euler cải tiến 81

6.2.3 Phương pháp Runge-Kutta 83

6.2.4 Giải bài toán Cauchy của hệ PTVP cấp một 86

6.3 PHƯƠNG PHÁP SAI PHÂN GIẢI BÀI TOÁN BIÊN TUYẾN TÍNH 87

6.3.1 Xét bài toán biên hai điểm tuyến tính đối với PTVP cấp hai: 87

6.3.2 Ví dụ: Tìm hàm y(x) trên [0; 1] với bước h = 0,1 là nghiệm của 6.3.3 Sơ đồ khối 89

6.4 BÀI TẬP CHƯƠNG 6 90

1 CHƯƠNG 1: MỞ ĐẦU

Giải tích số (Numerical Analysis) hay còn gọi là Phương pháp số (Numerical

Methods) hay Phương pháp tính (Calculating Methods) là một khoa học nghiên cứu

các lời giải số của các bài toán của toán học

Ba nhiệm vụ chính của giải tích số là:

1 Xấp xỉ hàm số: Thay một hàm có dạng phức tạp bằng một hàm hoặc nhiềa hàm

có dạng đơn giản hơn Các bài toán thường gặp là nội suy và xấp xỉ hàm

2 Giải gần đúng các phương trình: Bao gồm các phương trình đại số và siêu việt, các hệ phương trình đại số tuyến tính và phi tuyến, giải các phương trình và hệ phương trình vi phân thường và vi phân đạo hàm riêng, …

3 Giải các bài toán tối ưu

Tuy nhiên trong các giáo trình Giải tích số, người ta chỉ đề cập đến hai nhiệm vụ đầu, còn nhiệm vụ thứ ba dành cho các giáo trình về Qui hoạch toán học hay Tối ưu hoá

“An approximate answer to the right problem is worth a great deal more than a precise answer to the wrong problem.”

(John W Turkey 1915-2000)

1.2 SỰ KHÁC BIỆT GIỮA TOÁN HỌC LÍ THUYẾT VÀ TOÁN HỌC TÍNH TOÁN

Chứng minh sự tồn tại nghiệm Tốc độ hội tụ của nghiệm

Khảo sát dáng điệu của nghiệm Sự ổn định của thuật toán

Một số tính chất định tính của nghiệm Thời gian tính toán trên máy và dung lượng b

nhớ cần sử dụng

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

1) (n dx e x

0

1 x n

Tích phân từng phần ta được

I x e n x e dx 1 - nIn-1

1 0

1 x 1 n 1

0 1 x n 1

− (1.1)

0,36787 e

dx e - e x dx xe

1 0

1 - x 1 0 1 x 1

0

1 x

Vậy ta có thể tính tích phân trên và để ý rằng In ≥ 0 với mọi n Trên thực tế không phải như vậy! Công thức trên cho kết quả không chính xác, khi n = 9 I9 ≈ =0,068480 < 0

dù ta tăng độ chính xác của e-1 dế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

Để khắc phuc, ta biến đổi công thức (1.1)

In-1 = n-1 (1 – In)

và để ý rằng

I

limn)

(1dxxI

n

1 - 1

Để tính nghiệm theo (1.3), ta 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ố, do đó phải thực hiện n-1 phép nhân Vậy riêng số

phép nhân phải thực hiện đã là (n+1) n! (n-1) Giả sử n = 20, và máy tính thực hiện

được 5000 phép nhân trong 1 giây thì để thực hiện số phép nhân trên phải mất 300 000

000 năm!

Ví dụ 3: Xét hệ (1.2) với

100 n , 1 0 0

0

0 1

0 0

0 0

1 0

Theo quan điểm lí thuyết thi A bị suy biến nên không giải được Tuy nhiên ta có thể

nhẩm ra ngay A-1 = 10 E, với E là ma trận đơn vị cấp n và dễ dàng tính được nghiệm

của hệ bằng phương pháp ma trận nghịch đảo!

Kết luận: Trong quá trình giải các bài toán, có thể nảy sinh nhiều vấn đề mà toán học

lí thuyết không quan tâm hoặc không giải quyết được Vậy cần có một khoa học riêng

chuyên nghiên cứu các phương pháp số giải các bài toán Đó là khoa học tính toán mà

giải tích số là một môn học

1.3 CÁC BƯỚC GIẢI MỘT BÀI TOÁN CỦA GIẢI TÍCH SỐ

Để giải quyết một bài toán, người ta phải thực hiện quá trình mô phỏng sau đây:

1 Xây dựng mô hình toán học của bài toán thực tế

2 Phân tích mô hình: tính tương thích của mô hình với bài toán thực tế, sự tồn tại

nghiệm của bài toán

3 Rời rạc hoá mô hình: dùng các phương pháp tính toán để qui bài toán liên tục

về bài toán với số ẩn hữu hạn

4 Xây dựng thuật toán: chú ý đến độ phức tạp thuật toán, tính hội tụ, tính ổn định

của thuật toán

5 Cài đặt chương trình và chạy thử, kiểm tra kết quả, sửa lỗi và nâng cấp chương trình

1.4 THUẬT TOÁN VÀ ĐỘ PHỨC TẠP

1.4.1 Thuật toán

¾ Khái niệm thuật toán

Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện, để giải quyết một vấn đề

Năm đặc trưng của thuật toán:

• Input Mỗi thuật toán cần có một số (có thể bằng không) dữ liệu vào (input) Đó

là các giá trị cần đưa vào khi thuật toán bắt đầu làm việc Các dữ liệu này cần được lấy từ các tập hợp giá trị cụ thể nào đó

• Output Mỗi thuật toán cần có một hoặc nhiều dữ liệu ra (output) Đó là các giá

trị có quan hệ hoàn toàn xác định với các dữ liệu vào và là kết quả của sự thực hiện thuật toán

• Tính xác định Mỗi bước của thuật toán cần phải được mô tả một cách chính

xác, chỉ có cách hiểu duy nhất

• Tính khả thi Tất cả các phép toán có mặt trong các bước của thuật toán phải đủ

đơn giản

• Tính dừng Mọi bộ dữ liệu vào thoả mãn các điều kiện của dữ liệu vào (tức là

được lấy ra từ tập giá trị của các dữ liệu vào), qua xử lí bằng thuật toán phải dừng sau một số hữu hạn bước thực hiện

¾ Các vấn đề liên quan đến thuật toán

• Tính đúng đắn của thuật toán

Khi thuật toán được tạo ra chúng ta cần phải chứng minh rằng thuật toán được thực hiện sẽ cho ta kết quả đúng với mọi dữ liệu vào hợp lệ Điều này gọi là chứng minh tính đúng đắn của thuật toán

• Các vấn đề nảy sinh

Khi giải một bài toán người ta có thể xét nhiều thuật toán khác nhau xem độ phức tạp của chúng ra sao, dùng ngôn ngữ lập trình nào hay cài đặt phần mềm nào để chạy chương trình, cấu trúc dữ liệu nào phù hợp?

• Các yêu cầu cơ bản khi giải một bài toán

1 Hiểu đúng bài toán

(n) O(f (n)

T

q q

1 1

1.4.2 Độ phức tạp thuật toán

¾ Định nghĩa

Độ phức tạp thuật toán là một công cụ đo, so sánh, lựa chọn các thuật toán khác nhau

để tìm ra thuật toán tốt nhất cho lời giải bài toán

¾ Hai tiêu chuẩn để đánh giá độ phức tạp thuật toán

- Độ phức tạp về thời gian tính toán

- Độ phức tạp về phạm vi bộ nhớ dùng cho thuật toán (dung lượng của không gian nhớ cần thiết để lưu trữ dữ liệu vào, các kết quả tính toán trung gian và các kết quả của thuật toán)

Chúng ta sẽ chỉ quan tâm đến thời gian thực hiện thuật toán, vì vậy một thuật

toán có hiệu quả được xem là thuật toán có thời gian chạy ít hơn các thuật toán khác

¾ Cách đánh giá thời gian thực hiện thuật toán

- Cỡ của các dữ liệu vào

- Chương trình dịch để chuyển chương trình nguồn thành mã máy

- Thời gian thực hiện các phép toán của máy tính được sử dụng để chạy chương trình

Thời gian chạy chương trình phụ thuộc vào rất nhiều nhân tố, nên ta không thể biết được chính xác thời gian chạy là bao nhiêu đơn vị thời gian chuẩn(bao nhiêu giây)

Thời gian thực hiện thuật toán như là hàm số của cỡ dữ liệu vào n

Cỡ của dữ liệu vào là một tham số đặc trưng cho dữ liệu vào, nó ảnh hưởng quyết định đến thời gian thực hiện chương trình Cỡ dữ liệu phụ thuộc vào thuật toán cụ thể,

thường là số nguyên dương n Ta sử dụng hàm T(n), trong đó n là cỡ dữ liệu vào để

biểu diễn thời gian thực hiện một thuật toán

Khi đánh giá thời gian thực hiện bằng phương pháp toán học, chúng ta sẽ bỏ qua

nhân tố phụ thuộc vào cách cài đặt chỉ tập trung vào xác định độ lớn của thời gian

thực hiện T(n) Kí hiệu toán học ô lớn được sử dụng để mô tả độ lớn của hàmT(n)

Giả sử n > 0 (n ∈ Z), T(n),f(n) > 0 Ta viết T(n) = O(f(n)), nếu và chỉ nếu tồn tại các hằng số dương c và n0 sao cho T(n) ≤ c f(n), với mọi n > n0 Ta có thể xem rằng O(f(n)) là cận trên của T(n) Thông thường thời gian chạy một thuật toán tỉ lệ với 1, logn, n, nlogn, nk, hoặc an với a là hằng số

¾ Các quy tắc để đánh giá thời gian thực hiện thuật toán

• Chia độ phức tạp thuật toán ra thành nhiều đoạn mà mỗi đoạn có độ phức tạp

⇒ T1(n) + … + Tq(n) = O(max(f1(n), … ,fq(n))) Thật vậy vì T1(n), … ,Tq(n) là ô lớn của f1(n), … , fq(n) tương ứng do đó tồn tại hằng số c1, …, cq, n1, … , nq sao cho

T1(n) ≤ c1 f1(n) với mọi n > n1 và

T2(n) ≤ c2 f2(n) với mọi n > n2,

Đặt n0 = max(n1,n2, …, nq), khi đó với mọi n > n0, ta có

T1(n) +T2(n) + … + Tq(n) ≤ (c1+c2+ … + cq) max (f1(n),f2(n), …, fq(n))

• Các loai lệnh

- Các phép gán, đọc, in, goto là câu lệnh Các lệnh này được gọi là lệnh đơn và có

độ phức tạp thời gian là T(n) = O(C) = O(1)

- Nếu S1, S2, Sn là câu lệnh thì

{ S1; S2; ; Sn }

là câu lệnh hợp thành (câu lệnh ghép khối)

- Nếu S, S1, S2, …, Sn là các câu lệnh và E1, E2, … là biểu thức logic thì

- Nếu S1, S2, Sn là câu lệnh, E là biểu thức có kiểu thứ tự đếm được, và v1, v2 ,

vn là các giá trị cùng kiểu với E thì

lệnh này đựoc gọi là câu lệnh case

- Nếu S là câu lệnh và E là biểu thức logic thì

Nhờ định nghĩa đệ quy các lệnh, chúng ta có thể phân tích một chương trình xuất phát từ các lệnh đơn, rồi từng bước đánh giá các lệnh phức tạp hơn, cuối cùng đánh giá

được thời gian thực hiện chương trình

Giả sử lệnh gán không chứa lời gọi các hàm có thời gian thực hiện Khi đó để đánh

giá thời gian thực hiện một chương trình, ta có thể áp dụng phương pháp đệ quy sau đây:

- Thời gian thực hiện các lệnh đơn: gán, đọc, viết, goto là O(1)

- Lệnh hợp thành Thời gian thực hiện lệnh hợp thành được xác định bởi luật tổng

- Lệnh if: Giả sử thời gian thực hiện các lệnh S1, S2 là O(f1(n)) và O(f2(n)) tương ứng Khi đó thời gian thực hiện lệnh if là O(max(f1(n),f2(n)))

- Lệnh case được đánh giá như lệnh if

- Lệnh while: Giả sử thời gian thực hiện lệnh S (thân của lệnh while) là O(f(n) Giả sử g(n) là số tối đa các lần thực hiện lệnh, khi thực hiện lệnh while Khi đó thời gian thực hiện lệnh while là O(f(n)g(n))

- Lệnh for được đánh giá tương tự lệnh while

Nếu lệnh gán có chứa các lời gọi hàm thì thời gian thực hiện nó không thể xem là

O(1) được, vì khi nó thực hiện lệnh gán còn phụ thuộc vào thời gian thực hiện các hàm

có trong lệnh gán việc đánh giá các hàm không đệ quy được tiến hành bằng cách áp dụng các quy tắc trên (việc đánh giá thời gian thực hiện các hàm đệ quy sẽ khó khăn hơn nhiều)

Chú ý:

- Nếu thuật toán được chia thành nhiều đoạn thì trong trường hợp

Đoạn chia có chu trình lồng thắt: độ phức tạp tính là tích

Đoạn rời rạc: độ phức tạp tính là max

- Người ta chia các bài toán thành 3 lớp, có

Độ phức tạp là hàm đa thức (của cỡ dữ liệu vào n)

Độ phức tạp là hàm mũ

Độ phức tạp là NP - đầy đủ

- Hai loại bài toán sau là không khả thi, đối với loại đầu nên giảm bậc của đa thức

về càng gần 1 càng tốt Để hạ bậc của đa thức, người ta thường sử dụng cấu trúc dữ liệu đầu vào (input) Các dữ liệu đầu vào là bình đẳng với nhau

if(a[i]>a[j]) if (a[j]>max) max=a[j]; { tg=a[i];

Định nghĩa 1: Số a được gọi là số xấp xỉ của số A nếu a sai khác A không đáng kể và

được dùng thay A trong tính toán

Ví dụ: 3,14 và 3,15 là 2 số xấp xỉ của số π

¾ Sai số tuyệt đối và sai số tương đối

Định nghĩa 2: |A - a| gọi là sai số tuyệt đối của số xấp xỉ a

Nhận xét 1: Do không bết số đúng A nên không biết được |A – a|, người ta đưa thêm

vào khái niệm sai số tuyệt đối giới hạn như sau:

Định nghĩa 3: Sai số tuyệt đối giới hạn của số a là số Δa: |A-a | ≤ Δa Vậy

a – Δa ≤ A ≤ a + Δa hay A = a ± Δa (1.4)

Ví dụ: Ta biết rằng 3,14 ≤ π ≤ 3,15 nên ta cố thể chọn Δπ ≤ 0,01

Nếu đê ý rằng 3,14 < π < 3,15 thì ta nhận được giá trị tốt hơn Người ta thường chọn

Δπ là số nhỏ nhất thỏa mãn (1.4)

Nhận xét 2: Sai số tuyệt đối không thể hiện mức độ chính xác của phép đo hoặc tính

toán Để thể hiện điều đó, người ta đưa vào khái niệm sau:

Định nghĩa 4: Sai số tương đối của số xấp xỉ a là số

|A

|

|a-A

|

Δa

δa ≥ Δ ≤ a A δ a (1.5)

Nhận xét 3: Do không biết số đúng A và vì a ≈ A nên thay vì dùng (1.5), ta dùng

∆a = |a| δa hay

A = a (1 ± δa) (1.6)

Ví dụ:

Mảnh vải A đo được chiều dài a = 6 m với sai số tuyệt đối giới hạn ∆a = 0,2m

Mảnh vải B đo được chiều dài b = 3 m với sai số tuyệt đối giới hạn ∆b = 0,2m Rõ ràng 2 mảnh vải có cùng sai số tuyệt đối giới hạn là 0,2m và

16

2,0a

¾ Chữ số có nghĩa của một số: Chữ số có nghĩa của một số là những chữ số của

số đó kể từ chữ số khác không đầu tiên tính từ trái sang phải

đều đáng tin và số này có sai số tuyệt đối ∆a ≤ 0,5.10-2

1.5.3 Qui tròn số và sai số qui tròn

Qui tròn một số là vứt bỏ một vài chữ số sao cho số nhận được a1 được gần đúng nhất với số a ban đầu

Vậy ta có thể chọn được ∆a1 = ∆a+ Өa1 điều đó có nghĩa là sau qui tròn, sai số

tuyệt đối tăng lên

Ví dụ: Số a = 3,141 được qui tròn thành 3,14, còn số 3,1415 được qui tròn

thành 3,142

1.5.4 Các công thức tính sai số

¾ Công thức chung

Bài toán: Cho hàm u = f(x1, x2, … , xn) khả vi và biết các sai số tuyệt đối giới hạn

∆xi của các đối số xi và giá trị gần đúng u Hãy tính sai số tuyệt đối ∆u và sai số tương đối δu

Giải: Sử dụng các định nghĩa về sai số và công thức toán ta có

i x Δ n

n1i

ulnix

Áp dụng công thức (1.7) cho các hàm số học ta có các công thức tính sai số sau

¾ Sai số của tổng đại số:

Nếu u = x1 + x2 + … + xn thì

nx

x1

2x1

xu

u u

Δ++Δ+

Δ

=

Δ

=δ

¾ Sai số của tích:

Nếu u = x1 x2 … xn thì

u u

n 2

2 1

u =δ +δ , Δ = uδδ

Ví dụ: Tính các sai số tuyệt đối và tương đối của thể tích hình cầu , biết

0,00163δ

δ

V V

d π

1.6 BÀI TẬP CHƯƠNG 1

1> Giải hệ phương trình

0,461x1 + 0,311x2 = 0.150 0,209x1 + 0,141x2 = 0.068 Bằng cách sử dụng phép toán số học làm tròn đến ba chữ số thập phân Nghiệm

chính xác là x1 = 1, x2 = –1; Bạn có so sánh gì giữa hai kết quả?

2> Xét thuật toán tạo nhiễu y cho đại lượng x:

A = x × 10n

B = A + x

y = B – A Tính y khi x = 0,123456 và n = 3 bằng cách sử dụng phép toán số học làm tròn

đến sáu chữ số thập phân Sai số x – y bằng bao nhiêu?

3> Một hình vuông có cạnh a đo được bằng 12,04 (m) với độ chính xác của thước

đo là ∆a = 0,005 (m) Đánh giá sai số tương đối, sai số tuyệt đối của diện tích

của hình vuông S = a2 và tính ra diện tích này (chỉ giữ lại các chữ số có nghĩa)

4> Giả sử z = 0,180 × 102 là nghiệm gần đúng của phương trình ax = b với

a = 0,111 × 100, b = 0,200 × 101 Hãy sử dụng phép tính số học với ba chữ số

thập phân để tính sai số ∆ = |b – az| Sau đó tính sai số trên bằng phép tính số

học chính xác và so sánh các kết quả

2 CHƯƠNG 2: GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH

2.1 PHƯƠNG PHÁP KHỬ GAUSS - JORDAN

2.1.1 Thuật toán

¾ Bước khử xuôi: Đưa hệ

⎪

⎪

⎩

⎪

⎪

⎨

⎧

= +

+ +

= +

+ +

= +

+ +

n n

n n n

2 n 1 1

2 n

n 2

22 1

21

1 n

n 2

12 1

11

b x

a x

a x a

b x

a

x a x a b x a x a x a

(2.1) về hệ dạng tam giác trên bằng các phép biến đổi tương đương qua n lần tác động lên A

⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ = = + + = + + + ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (

n n n n nn n 2 n n n 2 n 22 n 1 n n n 2 n 12 1 n 11 b x a

b x a x a

b x a x a x a (2.2) Các phép biến đổi trên thực hiện được ở lần tác động thứ i lên ma trận A nếu n 1, i 1) (i ii a − ≠ ∀ = và là phần tử có trị tuyệt đối lớn nhất trên cột i, cụ thể ta có công thức biến đổi

n i, k ; n 1, i j n;

1, i 1)

(i ii

1)

(i ji

1)

(i jk

(i)

−

=

¾ Bước quét ngược: Giải lần lượt xn, xn-1, … , x1 từ hệ tương đương đã được chéo hóa (2.2)

2.1.2 Ưu, nhược điểm của phương pháp

Phương pháp lặp Gauss-Jordan đơn giản, dễ lập trình, tuy nhiên nếu a(i 1) 0

ii − ≈ thi kết quả có thể không chính xác Do vậy ở ma trận biến đổi thứ i ta phải tìm phần tử

trội trên cột i và thực hiện phép đổi chỗ 2 hàng nếu cần thiết để đảm bảo hàng thứ i là hàng chứa phần tử trội

2.1.3 Các ví dụ

Ví dụ 1: Giải hệ

⎪

⎩

⎪

⎨

⎧

= +

−

−

−

= +

−

= +

−

1 x

4 x

x 2

2 x

x 4 x

6 x

2 x

x 5

3 2

1

3 2

1

3 2

1

Bước khử xuôi: Đưa hệ đã cho về hệ tương đương

Bước quét ngược: Giải ra ta được x3 = 1; x2 = 1; x1 = 1

0

0,6 3,8 0

2 1 5

2.1.4 Sơ đồ khối và chương trình

// Buoc khu xuoi

for(i = 0; i < n; i++) // Tim phan tu max cua cot i {

max = i;

for(j = i + 1; j < n; j++)

if (fabs(a[j][i]) > fabs(a[max][i])) max = j;

if (max != i) // Doi cho 2 hang max va i neu can for(k = i; k <= n; k++)

if(a[n–1][n]) printf(" HE VO NGHIEM");

else printf(" HE VO SO NGHIEM");

Bắt đầu Nhập A

Cấu tạo ma trận tam giác

(khử xuôi)

Tìm nghiệm (khử ngược)

In KQ Dừng

for (i = 0; i<n; i++) printf("x[%d]= %8.4f\n",i,x[i]);

}

}

2.1.5 Đánh giá độ phức tạp thời gian

Thời gian chạy của bước khử ngược là O(n2) nên hầu hết công việc được làm ở bước khử xuôi Với mỗi giá trị của vòng lặp theo i, vòng lặp theo k lặp n – i + 2 lần và vòng lặp theo j lặp n – i lần Vậy số lần lặp tổng cộng là

2in

2.1.6 Ứng dụng phương pháp khử Gauss vào việc tính định thức

¾ Thuật toán: Sử dụng bước khử xuôi, ta biến đổi định thức đã cho về định thức dạng tam giác trên Từ đó giá trị của định thức chính là tích các phần tử trên đường chéo chính của ma trận vế phải sau n lần tác động, nhân với phần dấu là (–1)p, trong đó p là số lần đổi chỗ 2 hàng

1204

1321

2101A

Sau bước khử xuôi ta đưa được A về dạng tam giác trên với p = 2 lần đổi chỗ các hàng

75,15,100

25,15,220

1204

Lấy tích các phần tử trên đường chéo chính với (–1)2 ta được det(A) = 30

¾ Sử dụng hàm MDETERM trong EXCEL tìm det(A)

2.2 GIẢI HỆ PTTT DẠNG BA ĐƯỜNG CHÉO

2 n

3 2 1

n n

n 1 n 1 n

2 n 2 n

3 3

3

2 2

2

1 1

e 1ee

eee

cb

00

00

dc

b0

00

0

0d

c0

00

0

00

0d

cb

0

00

00

dc

b

00

00

0d

for (i = 0; i < n–1; i++)

{

a[i+1][i+1]–=a[i][i+1]*a[i+1][i]/a[i][i]; a[i+1][n]-=a[i][n]*a[i+1][i]/a[i][i]; }

for (i = n–1; i >= 0; i )

Vậy nếu giải hệ ba đường chéo bằng phương pháp Gauss-Jordan thì độ phức tạp thời gian là tuyến tính

2.2.3 Phương pháp truy đuổi (nắn thẳng) giải hệ ba đường chéo

Dung lượng đòi hỏi để chứa mảng hai chiều có thể được thay thế bằng bốn mảng một chiều, mỗi mảng cho một đường chéo và một mảng cho vec tơ cột vế phải Sau đó dùng phương pháp truy đuổi giải hệ, độ phức tạp thuật toán là thời gian tuyến tính

;fdc

bf

i i i

i 1

i i i 1

h d e h

n

n 1 n n

n n

n 1 n n n

ex

c

bx

exbx

hay

c

b f

n

n 1

n− = − ;

n

n 1 n

c

e

h − = rồi thay vào (2.8) tính ngược lên

Tính x1: xét phương trình đầu tiên của (2.6)

c1 x1 + d1 x2 = e2

mà

x2 = f1 x1 + h1 Giải ra ta được

1 1 1

1 1 1 1

f d c

h d e x

¾ Sơ đồ khối và chương trình

// Tinh cac vec to f va h

printf("\n\rTinh cac vecto he so f va h cua nghiem x: \n"); f[n-2]=-b[n-1]/c[n-1];

printf("\n\r Nghiem cua he la: \n");

Tính các hệ số fi và hi (i = n–1, … , 1)

Tìm nghiệm xi (i = 1, … , n)

In KQ Dừng

=+

++

=+

++

n n

n n n

2 n 1 1

2 n

n 2

22 1

21

1 2 12 2

12 1

11

bx

a x

axa

bx

a

xaxa

bx

ax

ax

+

=

+ +

+ +

=

+ +

n 1 n n 1

1 n

2 n

n 3

23 1

21 2

1 n

n 2

12 1

b x

c x

c x

b x

c

x c x

c x

b x

c x

c x

+

=

+ +

+ +

=

+ +

1 1 1

1

n

1

0 n n

0 3 23

1 1 21

1

2

1

0 n n

0 2 12

1

1

b x c x

c x

b x c x

c x c x

b x c x

c x

(2.11)

Ta sử dụng các x1(1), , xi(1) được tính ở các hàng trên để tính các xi+1(1), ,xn(1) , với

i = 1, , n –1 ở các hàng dưới

tương ứng xi(0) bởi xi(1) ,xi(1) bởi xi(2) , i=1, ,n

Tiếp tục như vậy cho đến bước lặp thứ i = M cho trước hoặc đến khi số bước lặp i thoả mãn

0ε ε,

*X

X(i) − ≤ >

∞ cho trước (2.12)

2.3.2 Điều kiện hội tụ và đánh giá sai số của phương pháp

• Điều kiện đủ để phương pháp lặp Gauss-Seidel hội tụ:

Nếu ma trận A có tính chất đường chéo trội, tức là

a n a i 1 n

i j 1

thì nghệm X(n) hội tụ đến nghiệm duy nhất X* mà không phụ thuộc vào việc chọn véc

tơ X(0) ban đầu

• Đánh giá sai số của phương pháp:

Người ta chứng minh được rằng

X

μμ

trong đó

, x max

2, 1, i , p 1

q max

1 i

114

215

−+

nên A thoả mãn tính chất đường chéo trội, vì vậy phép lặp Seidel hội tụ

Bước 1: Đưa hệ đã cho về hệ tương đương

−

−

−

= +

−

= +

−

1 x

4 x x

2

2 x

4x x

6 2x

x 5x

3 2

1

3 2

1

3 2

=

++

0,5x3

x

0,530,25x1

0,25x2

x

1,23

0,4x2

0,2x1

x

Bước 2: Thay xấp xỉ ban đầu, chẳng hạn X(0) = (0 0 0) của nghiệm

vào vế phải tìm xấp xỉ thứ nhất X(1) = (x1(1),x2(1),x3(1)) của nghiệm theo (2.11) với n=3

; 8 , 0 ; 2 , 1 ( max

(0) i x

(1) i

(1)ix

(2)i

xi

Vậy X(2)−X* ≤1,5*0,26=0,39

0,012)

0 ;0,0120,01 (max

(2)ix

(3)i

xi

Vậy X(3) −X* ≤1,5*0,012=0,018 < ε

2.3.4 Sơ đồ khối và chương trình

enum BOOLEAN Hoitu (int m,matran a)

if ((s/fabs(a[i][i])) >= 1.) KT = false;

KTH[i] = KTH[i] && KT;

} else KTH[i] = false;

In KQ Dừng

s

đ

Bắt đầu

// Lay vec to ve phai lam vec to nghiem ban dau

for (i = 0;i <= m –1; i++) xt[i] = b[i][m];

if (s <= epsilon) {

t = true ; printf("\n");

printf("PHEP LAP HOI TU SAU %d BUOC\n" , k);

} else

printf("Sai so o lan lap thu %d la %12.2E" ,k,s);

for (i = 0; i < m –1;i++) xt[i] = xs[i] ;

} while((!t) && (k<=lanlap));

}

2.3.5 Sử dụng Solver trong EXCEL giải hệ PTTT

• Nhập các giá trị đoán nhận ban đầu cho x1, x2, …, x n

• Nhập các vế trái của các phương trình f1, f2, …, f n vào các ô riêng được liên kết với giá trị của các ẩn

• Chọn công cụ Solver (Data Tab Æ Solver)

a Đặt “Target Cell” cho ô có công thức = 0

b Chọn “Equal to Value of 0”

c Đối với “By Changing Cells,” trỏ tới các ô chứa giá trị ban đầu của x1,

x2, …, x n

d Thêm các ràng buộc (các phương trình)

e Nhấn nút “Options” , chọn “Assume linear model”

f Nhấn nút “Solve”

2.4 TÍNH MA TRẬN NGHỊCH ĐẢO

2.4.1 Ứng dụng phương pháp Gauss tính ma trận nghịch đảo

Để tính ma trận nghịch đảo A-1 của ma trận A, ta dựa vào định nghĩa A A–1 = E hay

0

01

0

00

1

xx

x

xx

x

xx

x

aa

a

aa

a

aa

a

nn 2

1

n 22

21

n 12

11

nn 2

1

n 22

21

n 12

111A

Các cột của A–1 lần lượt là nghiệm của các hệ phương trình ĐSTT sau đây với cùng

010

001 121

132

111

101

111

( x x1x

1

a x)f'(x

)f(xx

2 n

n n

n

n n

A-1 – Xk = A-1 (E – AXk) = A-1Gk = A-1 G02k

Vậy nếu xấp xỉ đầu X0 được chọn gần với A-1, cụ thể lànếu

E− 0 = 0 <

thì từ (2.20) dãy {Xk} hội tụ về A-1 rất nhanh

¾ Sơ đồ khối và chương trình

} else

{

y[i][j]=g[i][j];

} }

// Kiem tra dieu kien hoi tu cua ma tran lap

t=0.;

for (i = 0; i <= n−1; i++)

Bắt đầuNhập ACấu tạo ma trận lặp

Tính lặp ma trận nghịch đảo

In KQ Dừng

Kiểm tra đ/k hội tụ

đ

s

2 Nhập hàm MINVERSE tính A-1 với các tham số là các ô chứa ma trận A

3 Nhấn phím F2, rồi nhấn tiếp CTRL+SHIFT+ENTER

2.5 BÀI TẬP CHƯƠNG 2

1> Giải các hệ phương trình tuyến tính sau bằng phương pháp Gauss-Jordan

2x1 + 5x2 – 2x3 = 3 3x1 + 6x2 + 9x3 = 39

x1 + 3x2 – x3 = 2

xl + 2x2 – x3 = 2 2x1 + 4x2 + x3 = 7 3x1 + 6x2 – 2x3 = 7 2>Sử dụng chương trình con Gauss để giải hệ phương trình tuyến tính sau

0,21 x1 + 0,32 x2 + 0,12 x3 + 0,31x4 = 0,96 0,10 x1 + 0,15 x2 + 0,24 x3 + 0,22x4 = 0,71 0,20 x1 + 0,24 x2 + 0,46 x3+ 0,36x4 = 1,26 0,61 x1 + 0,40 x2 + 0,32 x3 + 0,20x4 = 1,53 Kiểm tra đáp án của bạn bằng cách thay lại vào hệ phương trình ban đầu, và đánh giá độ chính xác Nghiệm đúng là [l l l l]T

3> Sử dụng chương trình con Tridiagonal để giải hệ phương trình tuyến tính sau

Sử dụng chương trình này, tính định thức của ma trận sau

0,508 0,809 0,376 0,795 0,886 0,338

3 CHƯƠNG 3: PHÉP NỘI SUY VÀ ĐƯỜNG CONG PHÙ HỢP

3.1 KHÁI QUÁT VỀ BÀI TOÁN NỘI SUY

3.1.1 Đặt vấn đề

Nhiều bài toán đòi hỏi tìm hàm f(x) từ tập các điểm (xi, yi) cho trước, chẳng hạn như việc thiết kế hệ thống tính toán điều khiển năng lượng cho một toà nhà cao tầng, đòi hỏi số liệu về sự biến đổi nhiệt độ ở đó trong mỗi ngày Mẫu nhiệt độ thường được đo tại các thời điểm rời rạc Tuy nhiên khi tính toán lại cần đến các giá trị nhiệt

độ không có trong mẫu đo Một trong các cách khắc phục vấn đề trên là tìm hàm đơn giản, thường là đa thức, đo đúng mẫu và nội suy những giá trị nằm giữa các điểm mẫu Cũng có trường hợp biểu thức giải tích của f(x) đã biết nhưng quá phức tạp Khi đó dùng phép nội suy ta có thể tính được giá trị của f(x) tại điểm x bất kì trên [a,b] mà độ chính xác không kém bao nhiêu

Phép nội suy thường dùng trong các ứng dụng của khoa học, công nghệ và kinh

tế Cơ sở của mọi phép nội suy là sự phù hợp của kiểu đường cong hay hàm nội suy đối với tập các điểm mẫu cho dưới dạng bảng

3.1.2 Đa thức nội suy

¾ Bài toán: Cho tập các điểm thực nghiệm (x0,y0), (x1,y1), ,(xn,yn), hãy xây dựng một đa thức

Pn(x) = a0 + a1x + … + an-1xn–1 + anxn (3.1) thoả mãn

Pn(xi) = yi i = 0, 1, 2,…, n (3.2) Các điểm xi, yi i = 0, 1, 2,…, n gọi là các mốc nội suy hay các điểm nút nội suy Về mặt hình học, bài toán nội suy đa thức là tìm một đường cong y = Pn(x) đi qua các điểm M0(x0,y0), M1(x1,y1), … , Mn(xn,yn) cho trước

Sau đó dùng đa thức này để tính các giá trị Pn(x) tại các giá trị x nằm giữa x0 vàxn

¾ Giải: n+1 hệ số ai được xác định từ hệ phương trình ĐSTT

a xj yi i 0,n

i n

xx

x1

xx

x1

xx

x1D

n j i

n n

2 n n

n 1

2 1 1

n 0

2 0 0

nên hệ tồn tại duy nhất nghiệm

¾ Nhận xét: Phương pháp này có 2 nhược điểm

- Số phép tính cần thực hiện cỡ n (logn)2, chủ yếu là phép nhân

- Nếu n lớn thì bậc của đa thức nội suy là quá cỡ!

3.1.3 Sơ đồ Horner tính giá trị của đa thức

¾ Bài toán: Cho đa thức (1), cần tính giá trị của đa thức tại x = c

Pn(c) = a0 + a1c + … + an-1cn-1 + ancn (3.4)

¾ Giải: Cách tính Pn(c) tiết kiệm nhất về số phép tính là viết lại (3.4) dưới dạng

Pn(c) = (…(((anc + an-1)c + an-2)c + an-3)c + … + a1)c + a0 (3.5) Vậy để tính Pn(c) ta chỉ cần tính lần lượt các số sau theo công thức truy hồi

bn bn-1 bn-2 b0 = Pn(c)

¾ Ví dụ:

Tính giá trị của P3(x) = 3x3 + 2x2 – 5x + 7 tại x = 3

Giải: Lập sơ đồ Horner

Đa thức nội suy Lagrange được cho như sau

( ) ( )

x(L)x

N

k j 0 j

jxxx

,

(3.7) Kiểm tra điều kiện đường cong đa thức đi qua các điểm cho trước

( )

x)

( )( )( )

3 0 2 0 1 0

3 2

xxxxxx

xxxxxx)

x(

3 2

xxxxxx

xxxxxx

3 2 1 2 0 2

3 1

xxxxxx

xxxxxx

2 3 1 3 0 3

2 1

xxxxxx

xxxxxx

Thừa số thứ nhất là phân số mà tử số có N thừa số không có xk,

mẫu số cũng có N thừa số như tử số khi thay x bởi xk

3.2.2 Ví dụ: Tìm giá trị gần đúng của f(2,6) từ bảng số liệu

) ,

(

( 1 4)( 1 2)( 1 5)( 1 8)( 1 11) 3

11 6 2 8 6 2 5 6 2 2 6 2 4 6 2

( )( )( )( )( )

(2 4)(2 1)(2 5)(2 8)(2 11) 5

11 6 2 8 6 2 5 6 2 1 6 2 4 6 2

−

−

− + +

−

−

− +

−

−

− + +

−

−

− +

−

−

− + +

−

−

− +

+

( )( )( )( )( ) ( )( )( )( )( )

5,3494

25811511211111411

82,652,622,612,642,6

=

−

−

−++

−

−

−+

++

3.2.3 Sai số: Người ta đã chứng minh rằng nếu hàm f(x) khả vi liên tục đến cấp N+1

trên đoạn [a,b] chứa tất cả các mốc nội suy xk, k = 0, , N thì sai số của nội suy

1N

fxLxfx

(

| )

3.2.4 Sơ đồ khối và chương trình

f = 0 k=0,1,…,N

L = 1

i=0,1,…, N

- Khi các mốc nội suy cách đều, tức là xk+1 = xk + h = … = x0 + kh, h là hằng số, đặt

u = (x – x0) / h với u = 0, 1, … , N

thì công thức nội suy Lagrange (3.6) có dạng

k N

0 k

k N 0

N

)!

kN(k

)Nu) (

1ku)(

1ku) (

1u(u)1()uhx(L)

−

−

−

=+

3.3 ĐA THỨC NỘI SUY NEWTON VỚI BƯỚC CÁCH ĐỀU

3.3.1 Bảng sai phân hữu hạn

Với các mốc quan sát xk = x0 + k.h, h là hằng số, ta có các gía trị quan sát tương ứng fk = f(xk), k = –m, , n Sau đây ta sẽ trình bày khái niệm về sai phân hữu hạn

¾ Sai phânhữu hạn

Sai phân hữu hạn bậc một ∆fk = fk+1 – fk

Sai phân hữu hạn bậc hai ∆2fk =∆fk+1 – ∆fk

Sai phân hữu hạn bậc ba ∆3fk =∆2fk+1 – ∆2fk

* Để thuận tiện cho cho việc tra cứu các số liệu, các giá trị chuẩn đặt trong khung

* Giá trị cột thứ 3 trở đi được tính bằng cách lấy giá trị dưới trừ giá trị trên tương ứng của cột trước

≈

1!

Δf f

−

− 1)(u 2)

u(u 3!

f

Δ3 0

1) n 1) (u u(u

0 1

1 n 1 n

1 n

f h x

+

=

+ +

ξ

ξ

), (

) ( )!

(

) ( )

(

) (

(3.12)

¾ Ví dụ Từ bảng số liệu

xk –4 –2 0 2 4 6

fk –64 –8 0 8 64 216

hãy tính gần đúng giá trị f(–3 ) Ở đây ta thấy rằng x k là các mốc cách đều với h = 2

và x = –3 ở đầu bảng giá tri x k nên ta chọn x0 = –4 Vì vậy u = (–3 – (–4 )) / 2 = 0,5

Bảng sai phân hữu hạn tiến tương ứng

+ 0.0,5.(0,5 – 1)(0,5 – 2)(0,5 – 3)(0,5 – 4) / 5! = –27

Lưu ý: Đây là bảng số liệu của f(x) = x3 cho nên giá trị đúng f(-3) = –27

Theo công thức (3.12) thì f(6)(x) = 0 vì vậy quả là sai số R5(–3) = 0

3.3.3 Đa thức nội suy Newton lùi

Trường hợp mốc quan sát cách đều xếp theo thứ tự giảm dần xn > xn-1 > … > x0,

xk = x0 + kh, h là hằng số, các giá trị quan sát tương ứng fk = f(xk), k = 0, , n

¾ Lập công thức

Đặt x = xn + uh, tìm đa thức nội suy dưới dạng

Pn(x) = a0 + a1(x – xn) + a2(x – xn)(x – xn-1) + … + an(x – xn) … (x – x1) (3.13) Cho x = xn ta được a0 = fn;

x = xn-1 ta được a1 = ∆fn-1 / h;

…

x = xi ta được ai = ∆ifn-I / (i! hi)

Đổi biến u = (x – xn) / h ta được

++

≈

1!

Δff

!1n

ξfhx

+

=

+ +

ξ

, )