BTL-PPT-final - jjj PDF

Preview

Summary

Download BTL-PPT-final - jjj PDF

Description

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA

…………..o0o………….. BÁO CÁO BÀI TẬP LỚN MÔN PHƯƠNG PHÁP TÍNH Đề tài 2 Giảng viên hướng dẫn: Nguyễn Đình Dương Lớp L07, nhóm 9 Danh sách thành viên 2011255 Đỗ Huỳnh Gia Huy 2014476 Nguyễn Quốc Thái 2012084 Huỳnh Minh Thi 2014693 Nguyễn Trí Thức 2015074 Phạm Quang Vinh

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

CH ỦĐỀỀ 2

MỤC LỤC Lời nói đầu……………………………………………………… 2 Vấn đề 1 I.

Lý thuyết …………………………………………………. 4

II.

Bài toán 1 ………………………………………………… 8

III.

Mở rộng ………………………………………………….. 16

IV.

Kết luận ………………………………………………….. 17

Vấn đề 2 I.

Lý thuyết …………………………………………………. 18

II.

Bài toán 2 ………………………………………………… 19

III.

Mở rộng …………………………………………………... 24

Vấn đề 3 I.

Lý thuyết ………………………………………………….. 27

II.

Bài toán 3 …………………………………………………. 31

III.

Mở rộng …………………………………………………… 33

IV.

Kết luận …………………………………………………… 35

1

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

CH ỦĐỀỀ 2

Lời nói đầu Thân chào Thầy cô và các bạn sinh viên! Đây là báo cáo Bài tập lớn môn học Phương pháp tính do nhóm 09 thực hiện. Chúng ta thấy rằng hầu hết các bài toán trong toán học như giải các phương trình đại số hay siêu việt, các hệ phương trình tuyến tính hay phi tuyến, các phương trình vi phân thường hay đạo hàm riêng,tính các tích phân,... thường khó giải đúng được, nghĩa là khó tìm kết quả dưới dạng các biểu thức. Một số bài toán có thể giải đúng được nhưng biểu thức kết quả lại cồng kềnh, hức tạp khối lượng tính toán rất lớn. Vì những lí do trên, việc giải gần đúng các bài toán là vô cùng cần thiết. Các bài toán trong kĩ thuật thường dựa trên số liệu thực nghiệm và các giả thiết gần đúng. Do vậy việc tìm ra kết quả gần đúng với sai số cho phép là hoàn toàn có ý ghĩa thực tế. Từ lâu người ta đã nghiên cứu phương pháp tính và đạt nhiều kết quả đáng kể. Tuy nhiên để lời giải đạt được độ chính xác cao, khối lượng tính toán thường rất lớn. Với ác phương tiện tính toán thô sơ, nhiều phương pháp tính đã được đề xuất không thể thực hiện được vì khối lượng tính toán quá lớn. Khó khăn trên đã làm phương pháp tính không phát triển được. Ngày nay nhờ máy tính điện tử người ta đã giải rất nhanh các bài toán khổng lồ, phức tạp, đã kiểm nghiệm được các phương pháp tính cũ và đề ra các phương pháp tính mới. Phương pháp tính nhờ đó phát triển rất mạnh mẽ. Nó là cầu nối giữa toán học và thực tiễn. Nó là môn học không thể thiếu đối với các kỹ sư. Ngoài nhiệm vụ chính của phương pháp tính là tìm các phương pháp giải gần úng các bài toán,nó còn có nhiệm vụ khác như nghiên cứu tính chất nghiệm, nghiên cứu bài toán cực trị, xấp xỉ hàm v.v. Trong phần này chúng ta sẽ nghiên cứu một loạt bài toán thường gặp trong thực tế và đưa ra chương trình giải chúng bằng phần mềm MAPLE. MAPLE là một hệ thống tính toán trên các biểu thức đại số và minh họa toán học mạnh mẽ. Từ khi ra đời đến nay Maple đã phát triển qua rất nhiều phiên bản, Maple có cách cài đặt đơn giản, chạy được trên nhiều hệ điều hành, có cấu trúc linh hoạt để sử dụng 2

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

CH ỦĐỀỀ 2

một cách tối ưu cấu hình máy và có trình trợ giúp rất dễ sử dụng. Trải qua nhiều phiên bản, Maple cung cấp ngày càng nhiều các công cụ trực quan, các gói lệnh giúp tính toán toán học phổ thông và đại học. Ưu điểm đó làm cho nhiều người lựa chọn và sử dụng Maple cùng với các phần mềm toán học khác áp dụng trong dạy toán và các công việc tính toán đòi hỏi thực tiễn và sự phát triển của giáo dục. Ngôn ngữ lập trình Maple là một ngôn ngữ kiểu động. Cũng giống như các hệ thống đại số máy tính, các biểu thức hình thức đuợc lưu trữ trong bộ nhớ theo đồ thị không chu trình có huớng (DAG). Ngôn ngữ cho phép các biến có phạm vi nhất định (lexical scoping). Ngôn ngữ có hình thức lập trình hàm, nhưng cũng có hỗ trợ đầy đủ cho lập trình truyền thống, theo kiểu mệnh lệnh. Các tính năng cơ bản của MAPLE 

Người dùng có thể nhập biểu thức toán học theo các ký hiệu toán học truyền

thống. 

Có thể dễ dàng tạo ra những giao diện người dùng tùy chọn.



Maple hỗ trợ cho cả tính toán số và tính toán hình thức, cũng như hiển thị.

Nhiều phép tính số học được thực hiện dựa trên thư viện số học NAG; trong Maple, các chương trình con NAG đã được mở rộng để cho phép độ chính xác ngẫu nhiên lớn. 

Cho phép triết xuất ra các định dạng khác nhau như LaTex, Word, HTML,



Maple cũng có một ngôn ngữ lập trình cấp cao đầy đủ. Cũng có giao diện

… cho những ngôn ngữ khác (C, Fortran, Java, MatLab, và Visual Basic). Cũng có một giao diện dành cho Excel. 

Đáp ứng nhu cầu tính toán của nhiều đối tuợng: nguời dùng có thể nhập

biểu thức toán học theo các ký hiệu toán học truyền thống và thực hiện đuợc hầu hết các phép toán cơ bản trong chương trình đại học và sau đại học.

3

BÀI T Ậ P L ỚN



PH ƯƠ NG PHÁP TÍNH

CH ỦĐỀỀ 2

Là một công cụ biên soạn giáo án và bài giảng điện tử, thích hợp với các lớp

học tương tác trực tiếp; là một trợ giáo hữu ích cho học sinh sinh viên trong việc tự học.

VẤN ĐỀ 1 I.

LÝ THUYẾT

Trong nhiều vấn đề ta cần tìm nghiệm gần đúng p của phương trình f ( x) 0 (1)

Bởi vì trong cuộc sống chúng ta có nhiều hệ với những số gần đúng nên không thể tìm ra được nghiệm chính xác được nên chúng ta có những phương pháp dưới đây để tìm nghiệm gần đúng của hệ (1)



Khoảng phân ly nghiệm

Định lý giá trị trung gian: Giả sử 2 số thực a, b (a < b) thỏa mãn f(a)f(b) < 0 và f(x) liên tục trên [a, b] thì trong [a, b] chứa ít nhất một nghiệm của (1).  Điều kiện để trở thành khoảng phân ly nghiệm của (1): -

f(a) · f(b) < 0

-

f khả vi và không đổi dấu trong [a, b]

4

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

CH ỦĐỀỀ 2

 Phương pháp chia đôi  Dữ liệu đầu vào: Cho phương trình f(x)=0 và [a,b] là khoảng phân ly nghiệm với sai số gần đúng cho trước.  Ý tưởng của phương pháp: chọn c = (a+b)/2 là điểm giữa của [a,b] như vậy sẽ tồn tại một khoảng phân ly nghiệm nhỏ hơn (hoặc [a,c] hoặc [c,b]). Nếu f(a).f(c)0

0,74;0, 75

 f (0,75) f  0, 75 

>0

suy ra h 0,75 là điểm Fourier chọn h0 = 0,75 hn hn 1 

Công thức nghiệm Newton:

f  hn  1  f  hn  1

h0 h1

0,75 0,7400408

h2

932 0,7400152

h3

182 0,7400152

h4

181 0,7400152

h5

181 0,7400152 181 17

CH ỦĐỀỀ 2

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

CH ỦĐỀỀ 2

Suy ra h = 0,7400152181 là điểm bất động

Công thức sai số tổng quát

hn  hđ 



f ( h5 ) 6,8434 10 11



m 15, 53190265

Thế vào (1) ta được

III.

f ( hn ) m

(1)

h5  hđ  4, 406110 11

MỞ RỘNG

Giải một số bài toán tương tự 3 2 0,1 VD1: Phương trình f ( x ) 2 x  6 x  13x  4.5 0 trong khoảng cách ly nghiệm   .

Theo phương pháp chia đôi tìm nghiệm x5 và đánh giá sai số của nó. x5= 0.421875 Sai số theo công thức tổng quát: 0.009524754116 4 VD2: Cho phương trình x  5 x  10 thỏa điều kiện lặp trên đoạn [2,4]. Lấy x0 =3,45,

tìm x3. Tìm số lần lặp nhỏ nhất để được sai số nhỏ hơn 10-3 x3 = 2.1344773372 Sai số theo công thức tiên nghiệm: 0.0031002159 Sai số theo công thức hậu nghiệm: 0.000374926 < 10-3 (Thỏa yêu cầu đề bài)

18

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

VD3: Cho phương trình

ex  2 x2 

CH ỦĐỀỀ 2

sinx  10 0  1, 2 . Sử 6.4 trong khoảng cách ly nghiệm

dụng phương pháp Newton, xác định x0 ở biên và thỏa điều kiện Fourier, tìm nghiệm gần đúng x2 của phương trình trên và đánh giá sai số của nó. x2 Sai số theo công thức tổng quát: 0.0027

3 3 1, 2 VD4: Tìm nghiệm của phương trình x  x  5 0 trong khoảng   với sai số 310

3 Đặt f ( x )  x  x  5 . Hàm f liên tục có f (1) f (2)  3 5  0 . Lần lượt thực hiện các

bước sau

 k 1 a 1, b 2, x1 a 

b a f (a ) 1.375, f ( x1)  1.0254. f (b)  f (a)

f ( x1)  3 10 3, f ( x1). f ( a)  0, a  x1 1.375

 k 2  a 1.375, b 2, x2 a 

b a f (a ) 1.4814, f ( x2 )  0.2679. f (b )  f (a )

f ( x2 )  3 10  3 , f ( x2). f ( a)  0, a  x2 1.4814

…

 k 6  a 1.5155, b 2, x6 a 

b a f (a ) 1.5159, f ( x6 )  0.0009. f ( b)  f ( a)

f ( c)  3 10 3 3 Kết luận x 1.5159 là nghiệm của f ( x ) 0 với sai số 310

19

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

IV. -

CH ỦĐỀỀ 2

KẾT LUẬN

Phương pháp chia đôi là một phương pháp đơn giản nhất và rất dễ sử dụng, nhưng

có hạn chế là độ chính xác không cao và tốc độ hội tụ chậm, không sử dụng được tính chất của hàm số. Nếu khoảng cách ly nghiệm lớn thì ta cần khá nhiều thời gian để tính toán. -

Phương pháp lặp đơn và phương pháp Newton đều có ưu điểm là độ chính xác và

tốc độ hội tụ cao hơn phương pháp chia đôi. Tuy nhiên việc tìm ra hàm lặp có thể sử dụng được hoặc kiểm tra điều kiện để áp dụng phương pháp Newton thì phức tạp hơn việc sử dụng phương pháp chia đôi. Hạn chế nữa là nếu áp dụng phương pháp Newton nhưng chọn điểm xuất phát không thích hợp thì không đạt được kết quả như mong muốn. VẤN ĐỀ 2 I.

LÝ THUYẾT

Phương pháp Nhân tử LU Nội dung của phương pháp nhân tử LU là phân tích ma trận hệ số A thành tích của hai ma trận L và U, trong đó L là ma trận tam giác dưới và U là ma trận tam giác trên. Khi đó việc giải hệ phương trình sẽ đưa về việc giải hai hệ Ly = b và Ux = y mà ma trận hệ số là các ma trận tam giác và nghiệm thu được từ các công thức Bài toán Ax = b ⇐⇒ (LU)x = b ⇐⇒ L(Ux) = b Đặt Ux = y, ta được Ly = b ⇐⇒ y = L−1b Định lý Nếu A là ma trận không suy biến, thì bao giờ cũng tồn tại một ma trận P không suy biến sao cho ma trận PA phân tích được thành tích của ma trận tam giác dưới L và ma trận tam giác trên U, nghĩa là PA = LU 20

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH



CH ỦĐỀỀ 2

Phương pháp Doolittle:

Có rất nhiều phương pháp phân tích A = LU. Ở đây, ta xét ma trận L có đường chéo chính bằng 1 và gọi là phương pháp Doolittle. Khi đó, L và U có dạng:

Trong đó, các phần tử của hai ma trận L và U được xác định theo công thức:

II.

BÀI TOÁN 2 Bài toán

a) Viết hàm phân tích ma trận A thành A = LU bằng phương pháp Doolitle (không sử dụng lệnh tồn tại trong Matlab hoặc Python), hãy sử dụng hàm của bạn để giải quyết vấn đề tiếp theo. b) Một kỹ sư điện giám sát việc sản xuất ba loại linh kiện điện. Ba loại vật liệu kim loại, nhựa và cao su được yêu cầu để sản xuất. Các số lượng cần thiết để sản xuất mỗi thành phần là Thành phần

Kim loại

Nhựa

Cao su

g/thành phần

g/thành phần

g/thành phần

21

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

1 2 3

15 17 19

CH ỦĐỀỀ 2

0.30 0.40 0.55

1.0 1.2 4.5

Nếu tổng số tương ứng là 3,89, 0,095 và 0,282 kg kim loại, nhựa và cao su, mỗi ngày, mỗi ngày có thể sản xuất được bao nhiêu thành phần? (Kết quả sau đây phải là hiển thị: Ma trận L, nghiệm của hệ Ly = B, Ma trận U, nghiệm của hệ thống Ux = y)

2A

22

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

23

CH ỦĐỀỀ 2

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

CH ỦĐỀỀ 2

2B Nhập ma trận A vào chương trình đã viết ở câu a để phân tích A thành A=LU ta được hai ma trận L và U như sau

, Phân tích A thành A=LU

; Giải phương trình tìm x Ax=B 24

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

Đặt Ux  y

  1 0  0.3 1  y  L 1 B   15  1 10   15 9

 0  0   1 

1

 3890   95     282   

   3890   86   y   5     32   9 

Ux=y

1     3890  15 17 19       86   x  0 0.06 0.17   5   2   32  0 0  45     9   90     x  60   80   

25

CH ỦĐỀỀ 2

BÀI T Ậ P L ỚN

III.

PH ƯƠ NG PHÁP TÍNH

CH ỦĐỀỀ 2

MỞ RỘNG

Ví dụ 1: Giải hệ phương trình sau

Giải: Hệ phương trình trên có ma trận hệ số là

B= Áp dụng phương pháp Doolittle phân rã ma trận A ta được

Trước hết ta giải hệ

Ly = B

=

26

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

CH ỦĐỀỀ 2

=

Tiếp theo ta giải hệ

Ux = y

=

= Vậy hệ phương trình đã cho có nghiệm là: x1 = 1; x2 = 1; x3 = 1; x4 = 0

Ví dụ 2: Sử dụng phương pháp Doolittle để giải bài toán thực tế: Một thợ làm bánh đảm nhận việc làm 3 loại bánh ngọt. Ba loại nguyên liệu cơ bản là: Bột mì, Trứng, Sữa tươi. Số lượng cần thiết để sản xuất mỗi loại bánh là:

Thành phần

Bánh Loại Sukem Bánh bông lan Bánh tart

Bột mì (gr/phần)

Trứng (quả/phần)

Sữa tươi (ml/phần)

140 120 400

6 4 3

310 30 200

27

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

CH ỦĐỀỀ 2

Nếu tổng số lượng bột mì, trứng, sữa tươi tương ứng là 3,46kg, 60 quả, 2,84l mỗi ngày thì số lượng bánh mỗi loại có thể chế biến là bao nhiêu?

Số lượng bánh mỗi loại có thể chế biến là 5 phần sukem, 3 phần bánh bông lan, 6 phần bánh tart

28

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

CH ỦĐỀỀ 2

VẤN ĐỀ 3 I.

LÝ THUYẾT 

Mô tả bài toán

Giả sử cần tính gần đúng tích phân trên đoạn [a,b] lớn, thì h = b – a theo công thức

hình thang;

h

b c 2 theo công thức Simpson với độ sai số xấp xỉ tương ứng 0(

) ; hoặc

0( ) còn quá lớn. Để khắc phục được h bé (0 < h < 1) mà vẫn sử dụng được các công thức trên, người ta dựa vào tính chất khả tổng của tích phân xác định, nghĩa là chia đoạn [a,b] thành các đoạn nhỏ rồi áp dụng công thức hình thang hay Simpson trên đoạn nhỏ đó. Có được h nhỏ mà công thức tính toán không phức tạp, thuận lợi cho tính toán và thường sử dụng trong thực tế người ta đã xây dựng nên công thức hình thang và Simpson tổng quát dựa trên công thức hình thang và Simpson. 1. Công thức hình thang và công thức Simpson Giả sử biết giá trị yi  f (xi ) với i 0, n ; trong đó a  x 0  x 1  ...  xn  1  xn b

Hãy tính gần đúng giá trị tích phân b

b

a

a

I  f ( x )dx  y ( x)dx

(2.4)

29

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

Chia đoạn [a,b] thành n phần bằng nhau có bước x0  a; xn b : xi x0  ih

h

CH ỦĐỀỀ 2

b a n bởi các điểm chia:

với i 1, n  1; đồng thời tại các điểm đó ta có bảng số

yi  f (xi ) với i 0, n (2.5)

Từ bảng số (2.5), theo công thức cầu phương gần đúng ta có: b

n

I y( x)dx  i 0 Ai yi a

(2.6), trong đó Ai là số không đổi nào đó

Ta đi tìm biểu thức hiện của các Ai trong công thức (2.6). Nếu sử dụng đa thức nội suy Lagrange thì b

 n1 ( x) Ai   dx  a ( x  xi ) n 1 ( xi )

Do các mốc cách đều nhau bước là

h

b a n và x  x 0  ht , nên

n

(  1)n  i  j 0 (t  j ) Ai   d ( x0  ht ) t i x0 i !( n  i )! xn

(  1) n  i n  j 0 ( t  j) Ai h dt  i n i t i !( )!   0 Hay với i 0, n n

Hay

Ai (b  a) H i

1 ( 1)n  i n  j 0 (t  j ) Hi  dt  n i n i t i !( )!   0 Trong đó với i 0, n n

Vì

h

b a Hi n gọi là hệ số Côtét

30

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

b

Vậy

n

I y( x) dx (b  a)  t0 H i y i

(2.7)

a

Trong đó yt  f (xt )  f (a  ih ) với i 0, n 

Trường hợp (2.7) khi n = 1 thì ta có t  t  1 1 H 0   dt  t 2 0 1

1 t  t  1 1 H1   dt  t 1 2  0 b

Vậy

(b  a ) I f ( x )dx  ( y0  y1 ) 2 a

(2.8)

Công thức (2.8) gọi là công thức hình thang 

Trường hợp (2.7) khi n = 2 thì ta có 2

H0 

11 1 (t  1)(t  2)dt  2 2 6 0 2

H1 

11 2 t (t  2)dt   22 0 3 2

H2 

Do

11 1 t (t  1)dt   220 6

h

b a 2 , nên theo công thức (2.7) ta được

b

ba ( y0  4 y1  y2 ) I f ( x )dx  6 a

(2.9)

Công thức (2.9) gọi là công thức Simpson hay công thức Parabol. 31

CH ỦĐỀỀ 2

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

2.

CH ỦĐỀỀ 2

Công thức hình thang và công thức Simpson tổng quát

Việc dùng công thức hình thang và Simpson tổng quát thay vì công thức hình thang và Simpson đơn thuần sẽ đem lại kết quả tính với độ chính xác cao hơn. a) Công thức hình thang tổng quát

Chia đoạn

 a, b 

thành m phần bằng nhau có độ dài

h

b a m bởi các điểm chia:

x0 a; xt a  ih; xm b

Ký hiệu yt  f (xt ) i 0, n . Áp dụng công thức hình thang (2.8) cho từng đoạn

 x i , x i 1 

i  0, m  1 và cộng lại ta có

b

x1

x2

a

x0

x1

I f ( x )dx f ( x )dx f (x )dx ... 

xm

 f (x )dx

xm  1

h h h  y0  y1    y1  y2   ...  ym 1  ym  2 2 2 h    y 0  ym   2  y 1  y 2  ...  ym  1   2 

b

Hay

Với

h I  f ( x )dx    y 0  y m   2  y1  y 2 ...  y m 1   2 a

h

(2.10)

b a m

Công thức (2.10) được gọi là công thức hình thang tổng quát. b) Công thức Simpson tổng quát

32

BÀI T Ậ P L ỚN

PH ƯƠ NG PHÁP TÍNH

Chia đoạn

 a, b 

thành 2n phần bằng nhau có độ dài

CH ỦĐỀỀ 2

h

b a 2n bởi các điểm chia:

x0 a; xt a  ih( i 1, 2 n  1); x2 n b

Áp dụng công thức Simpson (2.9) dối với từng đoạn

 x 0 , x 2  ,  x2 , x4  ,...,  x2n  2, x2n 

và

cộng lại ta có b

I f ( x )dx  a

h h h  y0  4 y1  y2    y 2  4 y 3  y 4  ...   y 2 n  2  4 y 2 n  1  y 2 n  3 3 3

b

h I f ( x )dx    y 0  y 2 n   4  y1  y 3 ...  y 2n 1   2  y 2  y 4 ...  y 2n 3 a Hay

Với