Tài liệu Khoá luận tốt nghiệp Ứng dụng phương pháp Newton và phương pháp dây cung giải gần đúng phương trình phi tuyến

TRƯỜNG ĐẠI HỌC s ư PHẠM HÀ NỘI 2 KHOA TOÁN v ũ TH Ị HUỆ ỨNG DỤNG PHƯƠNG PHÁP NEWTON VÀ PHƯƠNG PHÁP DÂY CUNG GIẢI GÀN ĐÚNG PHƯƠNG TRÌNH PHI TUYẾN KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC • • • • Chuyên ngành: Giải tích HÀ NỘI - 2015 TRƯỜNG ĐẠI HỌC s ư PHẠM HÀ NỘI 2 KHOA TOÁN VŨ T H Ị H U Ệ ỨNG DỤNG PHƯƠNG PHÁP NEWTON VÀ PHƯƠNG PHÁP DÂY CUNG GIẢI GẦN ĐÚNG PHƯƠNG TRÌNH PHI TUYẾN KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC • • • • Chuyên ngành: Giải tích Nguòi huóng dẫn khoa học PGS.TS. Khuất Văn Ninh HÀ NỘI - 2015 LỜI CẢM ƠN Trong thời gian học tập, nghiên cún tại khoa Toán Trường Đại Học Sư Phạm Hà Nội 2, được sự dạy dỗ và chỉ bảo tận tình của các thầy cô, em đã tiếp thu được nhiều kiến thức khoa học, kinh nghiệm và phương pháp học tập mới, bước đầu làm quen với việc nghiên cứu khoa học. Qua đây em xin gửi lời cảm ơn sâu sắc toàn thể các thầy các cô trong khoa Toán trường Đại Học Sư Phạm Hà Nội 2 - những người đã luôn chăm lo, dìu dắt chúng em trưởng thành như ngày hôm nay. Đặc biệt em xin cảm ơn thầy giáo PGS.TS. KHUẤT VĂN NINH, người đã tận tình hướng dẫn, chỉ bảo và đóng góp nhiều ý kiến quý báu trong thời gian em thực hiện khóa luận này. Em xin chân thành cảm ơn! Hà Nội, thảng 05 năm 2015 Sinh viên thực hiện Vũ Thị Huệ LỜI CAM ĐOAN Khóa luận này được hoàn thành dưới sự hướng dẫn tận tình của thầy giáo PGS.TS. KHUẤT VĂN NINH cùng với sự cố gắng của bản thân em. Trong quá trình nghiên cứu em đã kế thừa những thành quả nghiên cứu của các nhà khoa học, các nhà nghiên cún với sự trân trọng và biết ơn. Em xin cam đoan những kết quả trong khóa luận này là kết quả nghiên cứu của bản thân, không trùng với khóa luận của tác giả nào. Hà Nội, thảng 5 năm 2015 Sinh viên thực hiện Vũ Thị Huệ MỤC LỤC LỜI CẢM ƠN LỜI CAM ĐOAN LỜI NÓI Đ Ầ U ........................................................................................................ 1 NỘI DƯNG............................................................................................................ 3 CHƯƠNG 1. CÁC KIẾN THỨC LIÊN QUAN.................................................3 1.1 Số gần đúng, sai số tuyệt đối, sai số tương đối......................................... 3 1.1.1 Số gần đúng...........................................................................................3 1.1.2 Sai số tuyệt đối..................................................................................... 3 1.1.3 Sai số tương đối.................................................................................... 3 1.2 Làm tròn số và sai số của phép làm tròn số .............................................. 4 1.2.1 Làm tròn s ố .......................................................................................... 4 1.2.2 Sai số của phép làm tròn số................................................................. 5 1.3 Cách viết số xấp x ỉ...................................................................................... 5 1.3.1 Chữ số có nghĩa, chữ số chắc.............................................................. 5 1.3.2 Chữ số đáng tin .................................................................................... 5 1.3.3 Cách viết số xấp x ỉ............................................................................... 6 1.4 Sự tồn tại nghiệm thực và khoảng tách nghiệm của phương trình......... 6 1.4.1 Sự tồn tại nghiệm thực của phương trình........................................... 6 1.4.2 Khoảng tách nghiệm (khoảng phân li nghiệm)..................................7 1.5 Đạo hàm và vi phân của toán tử................................................................ 8 CHƯƠNG 2. PHƯƠNG PHÁP NEWTON........................................................9 2.1 Mô tả phương pháp.................................................................................... 9 2.2 Mô tả phương pháp bằng hình h ọ c ..........................................................11 2.3 Bậc hội t ụ ................................................................................................... 12 2.4 Tốc độ hội tụ của phương pháp Newton................................................12 2.5 Sai số của phương pháp Newton.............................................................. 14 2.6 Một số ví d ụ ...............................................................................................14 CHƯƠNG 3. PHƯƠNG PHÁP DÂY CUNG................................................... 32 3.1 Mô tả phương pháp.................................................................................... 32 3.2 Mô tả phương pháp bằng hình h ọ c ...........................................................34 3.3 Tốc độ hội tụ của phương pháp dây cung............................................... 34 3.4 Sai số của phương pháp dây cung...........................................................36 3.5 Một số ví d ụ ...............................................................................................37 KẾT LUẬN............................................................................................................57 TÀI LIỆU THAM KHẢO LỜI NÓI ĐẦU 1. Lý do chọn đề tài Toán học bắt nguồn từ nhu cầu giải quyết các bài toán có nguồn gốc từ thực tiễn. Cùng với thời gian, Toán học ngày càng phát triển chia làm hai lĩnh vực: Toán học lý thuyết và Toán ứng dụng. Nói đến Toán học ứng dụng không thể không nói đến Giải tích số, đó là một môn khoa học nghiên cún cách giải gần đúng các phương trình, các bài toán xấp xỉ, bài toán tối ưu. Việc giải các phương trình phi tuyến f(x) = 0, trong nhiều trường hợp không có công thức giải chính xác nên hầu hết các phương trình cần giải gần đúng. Do vậy, một vấn đề đặt ra là tìm cách để xác định nghiệm gần đúng của phương trình đó. Phương pháp Newton và Phương pháp dây cung là công cụ hữu hiệu để giải gần đúng phương trình f(x) = 0. Vì nhờ hai phương pháp này phương trình phi tuyến f(x) = 0 được thay thế bởi phương trình tuyến tính xấp xỉ và nghiệm gần đúng của phương trình tuyến tính thay thế sẽ hội tụ đến nghiệm của phương trình phi tuyến nói trên. Dưới góc độ của một sinh viên sư phạm chuyên ngành Toán và trong phạm vi của một khóa luận tốt nghiệp em xin mạnh dạn trình bày hiếu biết của mình về vấn đề: “ứng dụng phương pháp Newton và phương pháp dây cung giải gần đúng phương trình phi tuyến” 2. Mục đích nghiên cún Hiểu và lắm vững hai phương pháp giải gần đúng phương trình phi tuyến, tìm nghiệm của phương trình với độ chính xác cần thiết hoặc sai số cho phép. Áp dụng phần mềm Toán học như: Maple và Pascal vào đế giải quyết một số bài toán. 1 3. Nhiệm vụ nghiên cún. Nghiên cứu Phương pháp Newton và phương pháp dây cung giải phương trình f(x) = 0 , tro n g /là hàm số một biến số thực; ứng dụng các phương pháp đó giải một số phương trình phi tuyến cụ thể. 4. Đối tượng nghiên cứu. Phương trình phi tuyến tính. Các cách giải và bài tập áp dụng. Giải toán trên Maple và trên Pascal. 5. Phương pháp nghiên cứu. Tra cứu và tham khảo tài liệu. Viết thuật toán chạy chương trình. Đưa ra và giải các ví dụ minh họa cho từng phương pháp. 2 N01 DUNG CHUÖNG 1. CÄC KIEN THÜC LIEN QU AN Trong chuong näy chüng ta trinh bay mot so kien thuc ca bän ve so gän düng, sai so tuyet döi, sai so tuang döi, läm trön so vä sai so cüa phep läm trön so, cäch viet so xäp xi, su tön tai nghiem thuc vä khoäng täch nghiem cüa phuong trinh, dao häm vä vi phän cüa toän tü. 1.1 So gän düng, sai so tuyet döi, sai so tiro’ng döi 1.1.1 So gän düng Ta nöi rang q lä so gän düng cüa q* neu q khöng sai khäc q* nhieu, hieu so A = q* - q goi lä sai so thuc su cüa q. Neu A > Othi q \ä giä tri gän düng thieu cüa q* Neu A < 0 thi q lä giä tri gän düng thüa cüa <7* 1.1.2 Sai so tuyet döi Trong tinh toän, thu’öng ta khöng biet so düng q* mä chi biet so gän düng cüa nö lä q. Khi dö ta nöi “q xäp xi <7* ” vä viet lä “q xäp xi <7* lech Do h = q* - q duoc goi lä sai so thuc cüa q*. Do khöng biet q* nen ta cüng khöng biet h. Tuy nhien, ta cö the tim duoc so duang Aq > h sao cho: q - A q < q * < q +ACJ So Aqbe nhät mä ta xäc dinh dugc goi lä sai so tuyet döi cüa q Neu so xäp xi cüa g* cö sai so tuyet döi lä Aq ta viet: q* = q ± A q (1.1.1) vöi nghTa: q - Aq 0 thì là số nguyên Nếu p - s = -k (k > 0) thì q có phần lẻ gồm к chữ số Neu p - s—>>00 thì q là số thập phân vô hạn. Làm tròn số q là bỏ đi một số các chữ số bên phải của q đế được q gọn hon và gần đúng với số q Quy tắc làm tròn số như sau: Xét số q ở dạng (1.2.1 ) và ta sẽ giữ lại đến bậc thứ ỉ, phần bỏ đi là |Hthì : q = ±(qp. l ơ ’ +... + q i+Ị.ỈOi+ỉ +...+ qi.lớ) Trong đó: r qt, 0 <ụ < Ợi = 10' 9 , + 1 , 1U > J .1 0 ‘ Nếu Ц = - . 10' thì Qi = \ ^ ^ 2 [qi + 1 nếu 4 = 2iạ.M ) = 21 + 1 (/E N) 1.2.2 Sai số của phép làm tròn số Ta kí hiệu sai số của phép làm tròn số là Гц, như vậy r q > ớ là số thỏa mãn điều kiện: \q -q \< rq Vì q = qp.lơ ’ +...+ qi.ìớ +Ц Còn q = qp. l ơ ’ +...+ qi+,.ÌỚ+' + ...+ ^ .1 0 ! nên I q - q I = I (qt - + |Л I < —. 10‘ sau khi thu gọn sai số tuyệt đối tăng lên: I q* - q I < I ợ* - q I + I q -~q I < A4+ Tq tức là sau khi làm tròn số thì sai số tuyệt đối tăng thêm r q 1.3 Cách viết số xấp xỉ 1.3.1 Chữ số có nghĩa, chữ số chắc + Xét số q có dạng (1.2.1) nghĩa là được viết dưới dạng số thập phân. Khi đó, chữ số có nghĩa là một số khác 0 và những số không bị kẹp giữa hai chữ số khác 0 hoặc nó là những số 0 hoặc nó là những số 0 ở hàng được giữ lại. + Xét số q ở dạng ( 1.2.1 ). q = ± (qp-l(y + ...+ qị.lớ + ...+ qp.s.lơ }'s) , chữ số CỊi ở ( 1.2.1 ) của chữ số q là chữ số chắc nếu: Лч < (ở. ì ơ {(ở là tham số cho trước). Tham số Củsẽ được chọn sao cho một chữ số vốn là chắc thì sau khi làm tròn vẫn là chữ số chắc. 1.3.2 Chữ số đáng tin Mọi số thập phân q đều có thể viết dưới dạng: q = ± Y .q s- 10* (1.3.1) Trong đó: qs là những số nguyên ớ—» 9 5 Ví dụ: 34.214 = 3 . 10 ' + 4.l ể + 2.10'1 + ì. l ơ 2 + 4. l ơ 3 Tức là q có dạng (1.3.1) với a ] = 3, a0= 4, a.Ị= 2, a.2 = ỉ, cc-3 = 4 là các chữ số qs ở (1.3.1). Giả sử q là xấp xỉ của q* với sai số tuyệt đối giới hạn là Áq. Ta chu ý là chữ số đứng ở hàng thứ s của q. Nếu Ац< 0.5.10S thì nói CỊS là chữ số đáng tin, ngược lại thì nói qs là chữ số đáng nghi. Như vậy ta đã gắn khái niệm sai số tuyệt đối với khái niệm chữ số đáng tin. Ví dụ: Cho q = 6.8274 với Aq = 0.0043 thì các chữ số 6, 5, 8, 2 là đáng tin, còncác chữ số 7, 4 là đáng nghi. Neu cho Лч = 0.0067 thì các chữ số 6, 5, 8 là đáng tin, còn các chữ số 2, 7, 4 là đáng nghi. 1.3.3 Cách viết số xấp x ỉ Cho các số q là xấp xỉ của ợ* với giá trị tuyệt đối Áq. Có hai cách viết số xấp xỉ q Cách 1: Viết kèm sai số theo công thức (1.1.1) Cách 2: Viết theo quy ước mọi chữ số có nghĩa đáng tin Một số viết theo cách viết thứ 2 có nghĩa là nó có sai số tuyệt đối không lớn hơn một nửa đơn vị hàng cuối cùng. 1.4 Sự tồn tại nghiệm thực và khoảng tách nghiệm của phương trình. 1.4.1 Sự tồn tại nghiệm thực của phương trình Xét phương trình: f(x) = о ( 1.4.1 ) *Đinh lí (1.4.1) Neu có hai số thực a và b (a < b) sao cho f(a).f(b) < 0, đồng thờỉf(x) liên tục trên [a, b] thì tồn tại ít nhất một nghiệm thực của phương trình ụ . 4. ỉ) ở trong khoảng [a, b]. 6 1.4.2 Khoảng tách nghiệm (ikhoảng phân li nghiệm ) Định nghĩa: Khảng [a, b] nào đó được gọi là khoảng phân li nghiệm của phương trình (1.4.1) nếu nó chứa một và chỉ một nghiệm của phương trình đó. Đe tìm khoảng phân li nghiệm (khoảng tách nghiệm) ta có các định lí sau: K*Đinh lí (1.4.2). Hàm f(x) liên tục, đơn điệu trên [a, b] vàf(a).f(b) < 0 thì [a, b] là khoảng tách nghiêm của phương trình ụ . 4.1) *Đinh lí (1.4.3). Hàm f(x) xác định trên [a, b] có f (x) không đổi dấu trên [a, b] và f(a).f(b) < 0 thì (a, b) là khoảng tách nghiệm của phương trình ụ . 4.1). Ví dụ Cho phương trình: X3 - X - 2 = 0, chứng tỏ phương trình có nghiệm thực và tìm khoảng tách nghiệm của phương trình. Giái Đặt f(x ) = X3 - X - 2 Ta cóf(x) xác định và liên tục với mọi Jt, đồng thời / (x) = 3x2- 1 = 0 ,1 tai x= ±-7= V3 X 1 1 "V 3 V3 -OC f'( x ) + 0 - 0 + 00 + ^ Jừ> Trong đó: -00 m ^ — +00 Vậy đồ thị cắt trục hoành tại một điểm duy nhất. Mặt khác/(7) < 0, f(2) > 0 nên phương trình đã cho có một nghiệm thực và phân li trong [1 ,2 ]. 1.5 Đạo hàm và vi phân của toán tử Giả sử X và Y là hai không gian định chuẩn F: X —>■Y, xác định trên tập con mở В nào đó của không gian X, ta nói ánh xạ đó khả vi tại JC e в nếu tồn tại toán tử tuyến tính bị chặn L{x) E L (X, Y) sao cho F(x + h )~ F(x) = Lự)h + a(x, h), heY (1.5.1) Trong đó II«(*.*) Il lift II Q khi ||Л||0 "1 Cũng có thể viết tắt là: F(x + h ) - F(x) = L(x)h + 0(\\h\\) Từ (1.5.1 ) suy ra một ánh xạ khả vi tại X sẽ liên tục tại điểm đó. Biếu thức L(x)h (rõ ràng là phần tử của không gian Y với mọi h thuộc X được gọi là vi phân mạnh hay vi phân Frechet) của ánh xạ F tại điểm Jt. Toán tử L(x) được gọi là đạo hàm chính xác hơn là đạo hàm mạnh của ánh xạ F tại Jt kí hiệu: F (*). Neu F khả vi tại điểm Jt thì đạo hàm tương ứng được xác định duy nhất. Thật vậy, đắng thức: \\L1h - L 2h\\= 0(h) đối với toán tử Li e L(X, Y); i = 1, 2 chỉ xảy ra khi L/ = L2 Một số tính chất: • Nếu F(x) = yo= const thì F (x)= 0 (F (jf) là toán tử không) • Đạo hàm của ánh xạ tuyến tính liên tục L chính là ánh xạ đó L(x) = L. Thật vậy, theo định nghĩa ta có L (x+h) - L(x) = LỌÌ). CHƯƠNG 2. PHƯƠNG PHÁP NEWTON Trong chương này, em trình bày phương pháp Newton giải gần đúng phương trình phi tuyến. Đồng thời em cũng giải mẫu một số ví dụ bằng phương pháp Newton, lập trình trên Maple, trên Pascal và đưa ra các bài tập áp dụng. 2.1 Mô tả phương pháp Xét phương trình: f(x) = 0 (2 . 1. 1) với giả thiết / E c 2 [a , b] và thỏa mãn: i)f(a).f(b)< 0 ii) Các đạo hàm / ( x), f M không đổi dấu trên [a, b] Định nghĩa: Điểm Xo được gọi là điểm Fourier của f(x ) nếu f(x0) / M > 0 Ý chủ đạo của phương pháp Newton là tìm cách thay phương trình (2.1.1), phi tuyến đối vói X, bằng một phương trình gần đúng, tuyến tính đối với X. Ta có công thức Taylor. Cho hàm P(x) xác định và có đạo hàm đến cấp n + I tại Xo và lân cận x0. Khi đó công thức sau đây gọi là khai triển Taylor bậc n của P(x) tại x0: P(x ) = P(x0) + ( x - x 0).P'(x0 ) + — 2! + ni .pụ,) (Jt0) + (X~*o)— .P(/,+1) (c) n+\ c = Xọ + 6{x - Xo), 0 < 6 < ì ( c là số trung gian giữa Jt và Xo) Xét phương trình (2.1.1), giả thiết nó có nghiệm thực a duy nhất ở trong [a, b]. Giả sử hàm / c ó đạo hàm / (x) ^ 0 tại X E [a, b] và đạo hàm cấp 9 hai / U) tại Jte(a, b ). Ta chọn Xo £ [a, b] rồi viết khai triển Taylor bậc nhất của f(x ) tại xỏ. f(x ) = f Oo ) + - Xo) + - Xo)2 X e (a , b), c = Xo + 6{x - Xo) e (a , b ) Như vậy phương trình (2.1.1) viết lại được: 0 = /O o ) + - xo) + f- ^ k x - Xo)2, với X đủ gần x0 thì X —Xọ là một đại lượng nhỏ nên (x - XoÝ rất nhỏ, bỏ qua số hạng cuối cùng ta được phương trình: f(x 0) + ( x - Xo) f (*o) = 0 (2.1.2) Như vậy, ta đã thay phương trình (2.1.1) bằng phương trình (2.1.2) đơn giản hơn nhiều và (2 . 1.2 ) tuyến tính đối với Jt. Gọi X ị là nghiệm của (2.1.2) do đó ta cỏ:f(x0) + (JC/ —Xo). f (*o) ^ Xỉ 1 =x0 0 0 ^ f (xo) Từ X] ta tính được bằng cách tương tự ra *2,... và một cách tổng quát khi đã biết x n ta tính Xn + 1 theo công thức: xn+l= x „ - ụ ^ ; n = 0,1,2,.. / On) Xo chọn trước thuộc [a, b] (2.1.3) (2.1.4) và xem xn là một giá trị gần đúng của nghiệm a. Phương pháp tính xntheo (2.1.3) và (2.1.4) gọi là phương pháp Newton. Chú v: Phương trình (2.1.2) dùng để thay cho phương trình (2.1.1) là tuyến tính đối với X và là phương trình tiếp tuyến với đường cong y = fix) tại điểm (xo,f(xo)) nên phương pháp Newton cũng là phương pháp tuyến tính hóa và là phương pháp tiếp tuyến. Nhìn vào (2.1.3), (2.1.4) ta thấy phương pháp Newton thuộc loại phương pháp lặp với hàm lặp là: 10 2.2 Mô tả phương pháp bằng hình học Giả sử hàm sốf(x) liên tục trên [a, b] có đồ thị là cung AB + N euf ( x). f (x)> 0 thì qua điểm B(b,f(b)) dựng tiếp tuyến với đồ thị У =ЛХ)>tiếp tuyến cắt Ox tại X]. TÙX/ dựng đường thẳng song song với Oy , đường thẳng này cắt đồ thị у =f(x) tại Kjixiflxj)). Qua Kị dựng tiếp tuyến với đồ thị và nó cắt Ox tại x2. Tiếp tục quá trình này ta được dãy {xn }. + N ếu/ ( x) . f (x)< 0 thì qua điểm A(a,f(a)) dựng tiếp tuyến với đồ thị у = f(x) và làm hoàn toàn tương tự như trên. Từ đó có các trường họp được mô tả như sau: K| В А О О А f ’ > 0, f ’ > 0 f ’ < 0 , f ’ <0 н.2-а H.2-b 11 A a О а Xị X2 f'> 0,f"< 0 f < 0, f IỈ.2-C Iỉ. 2 -d В >0 2.3 Bậc hội tụ Định nghĩa Số a e R , a > 0 gọi là bậc hội tụ của dãy xn đến giới hạn X* nếu tồn tại hằng số с ^ 0 sao cho: X n +l ~ X lim =с xn - x 2.4 Tốc độ hội tụ của phương pháp Newton Cho r là nghiệm của phương trình f(x) = 0 và xn là giá trị xấp xỉ thứ n của r, ta xác định một số Çt như sau: Çn - r - xnNeu với n đủ lớn thì chúng ta có mối quan hệ xấp xỉ như sau: kr„+il=*kr«r. với к là hằng số dương thì ta nói tốc độ hội tụ của phương pháp bằng p, p càng lớn thì dãy x„ hội tụ càng nhanh đến r. Theo phương pháp Newton ta có: xn+l = xn - f(x„) f CO Lấy r trù’ cả hai vế của phương trình ta có: 12 f ( x„) x= r - x n + + -p ^f (Xn) r-x hay ỉ n+i= ỉn + 1 ^ f ( x n) (2.4.1) Ta sử dụng khai triển Taylor trong lân cận của nghiệm r,f(r) = 0. Ta có: f (x„) = f ( r ) + ịxn - r ) f ( r ) + ^ ( x „ - r ) 2f (r)+ ..„ = - U \ r ) + ị ỉ n 2f \ r ) + --, ! I " 1 111 f (xn) = f (r) + (xn - r ) f (r) + ^ ( x n - r ý f (r)+..„ (2.4.2) = f \ r ) - u \ r ) + ụ n2f" \r )+ ..., Ta sử dụng công thức khai triển Maclaurin của hàm —— , ta được: =1+C + C2+~; 1 1- í (2.4.3) Với khoảng hội tụ là 1^1< 1. Từ (2.4.1), (2.4.2) và sử dụng (2.4.3) ta được: 00 thì &= — 2 /V) ? / O) điều kiện / (/*) > 0 Vậy bậc hội tụ của phương pháp Newton là p = 2. 2.5 Sai số của phương pháp Newton Ta có: l/(* n )l m 0 < m > | / ’(x ) |,a < X < b Ngoài ra ta có công thức đánh giá sai số khác là: \ a - x n \ < ^ - \ x n - x n+1\2 , với | / " 0 ) | 2 M Vì đạo hàm / , / không đổi dấu trên [a, b] nên ta có: m = m in \\f \à ) \. \ f (fr)|Ị 2.6 Một số ví dụ a) Ví dụ Ví dụ 2.6.1: Giải phương trình bằng phương pháp Newton: X2 — e x — 1 = 0 Giải Đặt f ( x ) = X2 — e x — 1 =>f ’(x) = 2x — e x 14 (2 .6 .1)