Bài giảng Phương pháp tính - Huỳnh Hữu Dinh

GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 1 TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP HCM KHOA KHOA HỌC CƠ BẢN ------------------------------ BÀI GIẢNG PHƯƠNG PHÁP TÍNH GV: HUỲNH HỮU DINH TP HỒ CHÍ MINH 2/2011 GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 2 Chương 0. SỐ XẤP XỈ, SAI SỐ 0.1. Số gần đúng và sai số Trong thực tế, khi muốn biết giá trị đại lượng nào đó người ta tiến hành đo đạc, tính toán bằng một số phương pháp nhất định. Nhiều khi chúng ta không thể nhận được chính xác giá trị thật của đại lượng cần biết mà chỉ nhận được số gần đúng (hoặc xấp xỉ) với giá trị thật. Việc đánh giá độ chính xác của giá trị xấp xỉ và sai số của phép đo hoặc phương pháp tính toán là hết sức cần thiết. Điều đó dẫn tới việc đưa ra khái niệm về số xấp xỉ và sai số nhận được. Nội dung dưới đây sẽ trình bày những khái niệm này. Định nghĩa 0.1.1: Giả sử A là số đúng, a là số gần đúng của A (trong trường hợp A là số vô tỷ như số e hay số  hoặc số hữu tỷ với phần thập phân vô hạn tuần hoàn như số 1 6 ). Ta gọi hiệu số a A a   là sai số xấp xỉ của số gần đúng a . Khi đó các đại lượng ;a a A      ta lần lượt gọi là sai số tuyệt đối và sai số tương đối của a . Rõ ràng ta có: a A a    hoặc A a  Nếu A không phải là số có hữu hạn chữ số thì lẽ đương nhiên ta cần a là số có hữu hạn chữ số và khi đó  sẽ có cùng dạng với A. Chẳng hạn, lấy ; 3,14A a  thì 0,0015926...  Định nghĩa 0.1.2: Sai số tuyệt đối giới hạn của số xấp xỉ a là số không nhỏ hơn sai số tuyệt đối của a . Kí hiệu sai số tuyệt đối giới hạn là a thì: a  Theo định nghĩa này thì sai số tuyệt đối giới hạn không là đơn trị. Từ định nghĩa ta suy ra a aa A a    Trong thực tế, người ta thường chọn sai số tuyệt đối giới hạn a là số nhỏ nhất có thể trong các sai số tuyệt đối giới hạn, và qui ước viết: aA a  Định nghĩa 0.1.3: Sai số tương đối giới hạn của số xấp xỉ a , kí hiệu là a , là số không nhỏ hơn sai số tương đối giới hạn của a . GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 3 Có nghĩa là: a a  hay a A   Từ đây a A   Theo định nghĩa sai số tuyệt đối giới hạn, ta có thể chọn a aA   Nhưng trong thực tế ta không biết được chính xác giá trị A và vì a là số xấp xỉ của A nên người ta thường dùng công thức: a aa   Từ đây ta có công thức  1 aA a   0.2. Sai số làm tròn số Giả sử cho số 1 0 1 2 1... , ... ...m m m n m nA s s s s s s s      . Chữ số thứ n của A là số 1m ns   tính từ trái qua phải. Kí hiệu 1 0 1 2 1... , ...m m m na s s s s s s     là số làm tròn đến chữ số thứ n từ số A . Qui tắc làm tròn như sau: . Nếu 5m ns   thì 1 1 1m n m ns s     ; . Nếu 5m ns   thì 1 1;m n m ns s    . Nếu 5m ns   thì 1 1 1m n m ns s     khi 1m ns   là số lẻ, 1 1m n m ns s    khi 1m ns   là số chẵn Từ qui tắc làm tròn ở trên ta thấy, sai số tuyệt đối giới hạn là: 115.10 10 2 m n m n a      0.3. Số chữ số đáng tin cậy Xét hai số A và a như mục trên. Ta nói tất cả n chữ số của a đều tin cậy, nếu ta có: 115.10 10 2 m n m n aa A a            Chẳng hạn 2,7183a  là số làm tròn đến năm chữ số của số e nên ta có 0,00001... 0, 00005   nên a có năm chữ số tin cậy với số cuối cùng đã được làm tròn. Với số A và a nói trong mục 0.2, ta sẽ thấy 11 1 2 10 n m a s       , do đó có thể lấy: GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 4 11 1 2 10 n a ms       (1) Theo công thức này thì số 2,7183a  có sai số tương đối giới hạn so với số e là: 5 11 1 0, 0025% 2 2 10a       Ví dụ Phải tính 3 29 với bao nhiêu chữ số thập phân để có 0,1%a  . Ta thấy phần nguyên của số này là 3. Do vậy áp dụng (1) ta được: 110 0, 001 4 6 n n     Ta chọn 4n  , nghĩa là phải lấy bốn chữ số thập phân, do đó 3 29 3,072 . Đôi khi người ta nói số a nào đó có q chữ số đáng tin cậy sau dấu phẩy, hàm ý rằng q chữ số phần thập phân là đáng tin cậy. Khi đó đương nhiên tất cả các chữ số phần nguyên của số a cũng là tin cây. Giả sử số a cũng có p chữ số phần nguyên. Khi đó ta có: 1m p  và n p q  . Khi đó ta được 0,5.10 qa   0.4. Sai số thực hiện các phép toán 0.4.1. Sai số của phép cộng Xét tổng 1 2 ... nu x x x    với ix là các số gần đúng với sai số tương ứng là ix . Hiển nhiên là ta phải có: 1 2 ... nu x x x      và do đó: 1 2 ... nu x x x        Từ đây suy ra: 1 2 ... nu x x x       (2) Ta có qui tắc cộng các số có sai số tuyệt đối khác nhau như sau: . Giữ nguyên các số hạng có số chữ số sau dấu phẩy là ít nhất; . Các số hạng khác làm tròn đến một hoặc hai số sau dấu phẩy nhiều hơn các số hạng đã chọn ở bước trên. . Cộng tất cả các số còn lại với nhau rồi làm tròn tổng, bớt đi một chữ số thập phân. Liên quan đến u , trong trường hợp ix cùng dấu thì có thể thấy:  1 2max , ,..., nu x x x    GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 5 Từ đây ta suy ra   1 2 max , ,..., nu x x x     0.4.2. Sai số của phép trừ Về nguyên tắc đánh giá (2) đúng cả cho phép trừ. Tuy nhiên, chúng ta xét riêng trường hợp này để nhấn mạnh một điều rất cần chú ý khi lập trình. Xét hiệu số 1 2u x x  Dễ dàng thấy rằng, khi 1x và 2x cùng dấu và 1 2x x thì 1 2,u x x   do 1 2 1x x  . Hơn thế nữa, trên các máy tính có độ chính xác không đủ cao, u sẽ được đặt bằng không. Trong trường hợp như thế ta cần tránh phép trừ trực tiếp mà thay nó bằng một phép tính tương đương. Chẳng hạn, ta muốn tính hiệu số 10 99, 99 0, 0005000125u    ta phải lấy căn của 99,99 tới 10 chữ số thập phân. 0.4.3. Sai số của phép nhân Xét tích số 1 2... nu x x x với 0ix  . Giả sử 0, 1,ix i n  . Khi đó ta có 1 2ln ln ln ... ln nu x x x    Mặt khác, ta cũng có  ln ln ln ln 1 z zz z z z z z            khi 1 z z   . Do đó ta có thể viết 1 2 1 2 ... n n u x x x u x x x        Từ đây ta có: 1 2 1 2 ... n n u x x x u x x x        Hay là: 1 2 ... nu x x x       Do vậy ta có thể lấy 1 2 ... nu x x x        0.4.4. Sai số trong phép chia Xét thương số 1 2 x u x  . Giả thiết rằng hai số đều dương. Khi đó ta có: 1 2ln ln lnu x x  GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 6 Lí luận như trên, ta nhận được 1 2u x x     0.4.5. Sai số trong trường hợp tổng quát Giả sử ta có mối quan hệ  1 2, ..., nu f x x x , trong đó các sai số tuyệt đối ix đã cho. Ta cần đánh giá sai số tuyệt đối u qua các ix . Coi các ix là các đại lượng nhỏ, ta có thể dùng công thức Taylor để đánh giá:    1 1 1 1 1 ,..., , ..., n n n n n i i i ii i f f u f x x x x f x x x x x x              Từ đây ta có thể lấy: 1 n i i i f u x x    Hoặc là: 1 i n u x i i f x    (3) Cũng từ biểu thức này, ta có thể nhận được 1 lnn i i i u u x x     hay là 1 ln i n u x i i u x     Ví dụ: Một hình cầu có đường kính 12,2d cm . Hãy tính sai số tuyệt đối và tương đối của thể tích hình cầu Giải Trong trường hợp này ta có 0, 05d cm  . Lấy 3,14  , khi đó 0, 0016  . Ta có: 2 310, 5 233,68; 302, 64 6 V V d d d          Sử dụng (3) ta được: 3233, 68 0, 05 302,64 0, 0016 12,2 12,2 1, 3% 950, 3 V V V cm V           0.4.6. Bài toán xác định sai số ngược GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 7 Lại xét mối quan hệ tổng quát  1 2, ..., nu f x x x . Giả sử cho trước u . Ta cần xác định các ix  để đảm bảo có được u như đã cho. Ta có một biểu thức (3) lấy làm phương trình để xác định các ix  nên lời giải không phải là duy nhất. Vì vậy chúng ta sẽ xét ba trường hợp cụ thể, có ý nghĩa ứng dụng thực tế: Trường hợp 1: Giả thiết rằng ; ; , 1,i jx x i j i j n     . Khi đó từ (3) ta dễ dàng có: 1 ; 1, i u x n i i i n u x      Trường hợp 2: Giả sử ta có ; , 1, i jx x i j u u i j n x x       . Khi đó từ (3) ta dễ dàng có: ; 1, i u x i i n u n x      Trường hợp 3: Nếu ; , 1, i jx x i j n     , thay ix i x  vào (3) ta được: 1 1 i u iu xn n i i i ii i x u u x x x x             Ví dụ Một hình trụ có bán kính đáy  2r m , chiều cao  3h m . Cần xác định sai số của r và h để sai số tuyệt đối giới hạn của thể tích là 30,1m . Giải Ta có công thức 2V r h . Ta lấy 3,14  . Do đó: 2 22 37,68; 12,56; 12; 37,68 V V V rh r r h V r h               Sử dụng (5) ta có:  0, 0009 3 V r mV r     Tương tự, ta tính được    0, 0027 ; 0, 0028h m m    GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 8 Chương 1. PHƯƠNG TRÌNH ĐẠI SỐ VÀ SIÊU VIỆT Bài 1. MỞ ĐẦU Trong mục này, ta tìm hiểu những phương pháp giải một số phương trình đại số dạng:   0f x  (*), với  f x là một hàm phi tuyến. Phương trình trên, trừ một vài trường hợp đặc biệt, có công thức giải đúng, còn nói chung không có công thức giải đúng (các công trình của nhà Toán học Abel đã khẳng định điều đó). Ở khía cạnh khác, các hệ số của  f x trong nhiều trường hợp cũng chỉ là các số gần đúng hoặc nghiệm của  f x là một biểu thức rất phức tạp, cho nên vấn đề giải đúng phương trình (*) cũng không thật sự cần thiết. Do đó, chúng ta cần quan tâm đến những phương pháp giải gần đúng, nhất là những phương pháp có thể dùng máy tính hỗ trợ. Để giải gần đúng phương trình (*), ta tiến hành các bước sau: . Thứ nhất là tách nghiệm, nghĩa là tìm một khoảng  ,a b đủ nhỏ sao cho phương trình (*) có nghiệm duy nhất  * ,x a b . . Thứ hai là chính xác hóa nghiệm gần đúng đến độ chính xác cần thiết. Cơ sở để tách nghiệm là những kết quả sau đây mà bạn có thể bắt gặp ở tất cả các cuốn sách về Giải tích. Định lí 1.1.1. Giả sử  f x liên tục trên  ,a b và     0f a f b  . Khi đó phương trình   0f x  tồn tại ít nhất một nghiệm trong khoảng  ,a b . Định lí 1.1.2. Nếu  f x liên tục trên  ,a b và     0f a f b  , hơn nữa, hàm số  f x có đạo hàm  f x liên tục trên đoạn  ,a b và  f x không đổi dấu trên  ,a b thì nghiệm nói trên là duy nhất. Bước tách (li) nghiệm thường được tiến hành nhờ phương pháp chia đôi hoặc phương pháp đồ thị. Nguyên tắc thực hiện phương pháp chia đôi như sau: Xác định     0f a f b  , sau đó chia đôi đoạn  ,a b và gọi  1 1,a b là một trong hai nữa ở trên sao cho    1 1 0f a f b  . Lại chia đôi đoạn  1 1,a b và gọi  2 2,a b là một trong hai đoạn con mà GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 9    2 2 0f a f b  ; quá trình cứ thế tiếp tục, (nếu tại ia mà   0if a  hoặc ib mà   0if b  thì ta nói giá trị đó là nghiệm đúng của phương trình   0f x  ) Nguyên tắc của phương pháp đồ thị như sau: Nghiệm của phương trình   0f x  là hoành độ giao điểm của đồ thị hàm số  y f x với trục hoành; hoặc ta biến đổi   0f x  về dạng    x x  . Khi đó nghiệm của phương trình   0f x  là hoành độ giao điểm của hai đồ thị  y x và  y x . Sau khi đã tách được nghiệm thì công việc tiếp theo là chính xác hóa nghiệm đến độ chính xác cần thiết. Để thực hiện bước này, ta có thể sử dụng một trong các phương pháp sau: phương pháp lặp, phương pháp dây cung, phương pháp tiếp tuyến, phương pháp Muller, phương pháp Laguerre,Tất cả phương pháp được nêu chúng ta đều có thể lập trình bằng ngôn ngữ Matlab hoặc Fortran. Nhưng trong phạm vi bài giảng này, chúng ta sẽ bỏ qua hai phương pháp Muller và Laguerre. Phương pháp Muller cần sử dụng công cụ số phức còn phương pháp Laguerre thì cơ sở toán học chưa thật chặt chẽ. Sau đây chúng ta sẽ đi vào từng nội dung cụ thể. GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 10 Bài 2. PHƯƠNG PHÁP LẶP ĐƠN Xét phương trình   0f x  (1) có khoảng li nghiệm là  ,a b . Ta biến đổi phương trình (1) về dạng tương đương:  x x (2) Với xấp xỉ ban đầu 0x thuộc khoảng  ,a b đã cho, ta xây dựng dãy   0,n nx   nhờ vào hệ thức:  1 , 0n nx x n    . Nếu dãy   0,n nx   có giới hạn *lim nn x x  thì *x chính là nghiệm đúng của phương trình (2) và cũng là nghiệm của (1) Tiếp theo, ta tìm hiểu một số điều kiện để dãy   0,n nx   hội tụ. Định lí 1.2.1. Giả sử hàm số  y x khả vi liên tục trên  ,a b và với mọi  ,x a b thì    ,x a b  . Khi đó, nếu ta có   1x L   với mọi  ,x a b thì dãy số   0,n nx   được xây dựng bởi hệ thức  1 , 0n nx x n    hội tụ đến nghiệm *x của phương trình   0f x  và ta có các ước lượng * * 0 n nx x L x x   * 11n n n L x x x x L     * 0 11 n n L x x x x L    Nhận xét: Phương pháp lặp đơn có tính chất tự điều chỉnh, nghĩa là nếu tại một vài bước tính toán trung gian ta mắc phải sai số thì dãy   0,n nx   vẫn hội tụ đến *x , tất nhiên chỉ một vài bước sai và sai số mắc phải không vượt ra ngoài đoạn. Một tính chất đặc biệt của phép lặp này là có thể đánh giá ngay từ đầu số bước lặp mà ta cần phải làm để có được độ chính xác theo yêu cầu. Thật vậy, từ biểu thức * 0 11 n n L x x x x L    GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 11 nếu ta muốn có nghiệm gần đúng với sai số  thì ta sẽ dừng lại ở bước lặp thứ n sao cho: 0 11 nL x x L   Từ đây ta có đánh giá cho n   1 0 1 ln / ln q n q x x       Từ định lí 1.2.1 cho thấy, nếu L càng nhỏ thì tốc độ hội tụ càng nhanh, và tốc độ hội tụ của phương pháp này rất chậm khi L càng gần 1. Trên đây ta nhắc đến việc chuyển từ (*) sang dạng tương đương (**) sao cho điều kiện    ' 1, ;x L x a b     được thỏa mãn. Về vấn đề này có mấy nhận xét sau: . Giả sử  0 'm f x M   (với trường hợp  ' 0M f x m   ta làm tương tự). . . Ta có thể chuyển từ (*) sang dạng tương đương sau:    x x f x x    với 1 M   (***) . Rõ ràng ta có:        1 1 1 1, ;f x mx f x x a b M M             . Do đó phép lặp được xây dựng trên (***) sẽ hội tụ đến nghiệm cần tìm Ví dụ: Tìm nghiệm lớn nhất của phương trình 3 1000 0x x   (1) Giải Đặt   3 1000f x x x   thì ta thấy    9 . 10 0f f  . Mặt khác    23 1 0, 9,10f x x x      nên ta suy ra  9,10 là khoảng tách (li) nghiệm của phương trình (1). Có ba cách đưa (1) về dạng  x x như sau: . 31000x x  , vậy   31 1000x x   . 2 1000 x x x  , vậy  2 2 1000 x x x   . 3 1000x x  , vậy   33 1000x x   Rõ ràng trong trường hợp 3,   33 1000x x   có GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 12    3 23 1 1 2003 1000 x L x       Chọn 0 310, 9, 9667x x  với độ chính xác không quá 410 , ta có thể coi * 3x x . Bài 3. PHƯƠNG PHÁP NEWTON (PHƯƠNG PHÁP TIẾP TUYẾN) Trong mục này, ta xét lại phương trình   0f x  . Giả sử rằng ta đã tìm được một khoảng li nghiệm của phương trình trên là khoảng  ,a b , đồng thời    ,f x f x  liên tục và không đổi dấu trên đoạn  ,a b . Khi đó, với 0x là xấp xỉ ban đầu được chọn, ta xây dựng dãy   0,n nx   theo công thức:    1 0 n n n n f x x x f x n       Ta có thể chứng minh được, với một số điều kiện thích hợp phương pháp Newton hội tụ, chẳng hạn với điều kiện sau Định lí 1.3.1. Nếu phương trình   0f x  có  ,a b là khoảng li nghiệm, đồng thời    ,f x f x  liên tục và không đổi đấu trên đoạn  ,a b , với  0 ,x a b sao cho    0 0. 0f x f x  ( 0x ,được gọi là điểm Fourier, thường được chọn là một trong hai đầu mút a hoặc b). Khi đó dãy   0,n nx   xây dựng như trên hội tụ đến nghiệm *x của phương trình   0f x  và ta có ước lượng 2* 1 12n n n M x x x x m     với ,m M là hai hằng số thỏa mãn    0 , ,m f x x a b       , ,f x M x a b    Nhận xét: Nếu như việc tính toán  f x tại mỗi điểm quá phức tạp và ta thấy  f x không thay đổi lớn thì ta thay dãy xấp xỉ ở trên như dãy dưới đây, thường được gọi là phương pháp Newton cải tiến: GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 13    1 0 0 n n n f x x x f x n       Định lý 1.3.1 còn cho thấy phương pháp Newton có tốc độ hội tụ bậc hai. Vì thế, nếu phương pháp Newton làm việc thì nó hội tụ đến nghiệm nhanh hơn bất kì phương pháp nào khác. Ví dụ: Dùng phương pháp Newton giải phương trình 3 2 10 0x x   với độ chính xác 310 , biết khoảng li nghiệm là  2, 3 . Giải Đặt   3 2 10f x x x   . Khi đó ta có:     23 2 6 f x x f x x      Dễ thấy rằng    3 3 0f f   nên ta chọn 0 3x  . Ta xây dựng dãy   1,n nx   như sau:     3 1 2 2 10 ' 3 2 0 n n n n n n n n f x x x x x x f x x n           Với 0 3x  , ta tính được  1 12.5600 1.6572x f x   2 12.4662 0, 0668x f x    43 32.4621 1.2501.10x f x   Chọn 10, 18m M  khi đó 2 2* 3 3 3 2 18 0.0041 10 2 20 M x x x x m      Vì thế ta có thể chọn * 3x x . GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 14 Bài 4. PHƯƠNG PHÁP DÂY CUNG (THAM KHẢO) Trong mục này, ta phương trình   0f x  . Giả sử rằng ta đã tìm được một khoảng li nghiệm của phương trình trên là khoảng  ,a b , đồng thời    ,f x f x  liên tục và không đổi dấu trên đoạn  ,a b . Không giảm tổng quát, ta giả sử   0f x  trên  ,a b . Khi đó đồ thị  y f x nằm phía dưới dây cung AB với      , , ,A a f a B b f b . Trường hợp 1: Nếu   0f a  , ta xây dựng dãy   0,n nx   theo hệ thức:         0 1 n n n n n x b f x x x x a f x f a n          Khi đó ta sẽ có dãy   0,n nx   đơn điệu giảm, bị chặn và: * 1 0... ...n na x x x x b       Trường hợp 2: Nếu   0f a  , ta xây dựng dãy   0,n nx   theo hệ thức:         0 1 n n n n n x a f x x x x b f x f b n          Khi đó ta sẽ có dãy   0,n nx   đơn điệu giảm, bị chặn và: * 0 1 1... ...n na x x x x x b        Định lý 1.4.1: Nếu phương trình   0f x  có  ,a b là khoảng li nghiệm, đồng thời  f x liên tục và không đổi đấu trên đoạn  ,a b ,  f x liên tục và dương trên đoạn  ,a b . Khi đó dãy   0,n nx   xây dựng như trên hội tụ đến nghiệm *x của phương trình   0f x  và ta có ước lượng * 1 1n n n M m x x x x m     với ,m M là hai hằng số thỏa mãn GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected] 15    0 , ,m f x M x a b     Ví dụ: Giải phương trình 3 2 1 0x x x    bằng phương pháp dây cung biết khoảng li nghiệm là  0,1 với sai số không quá 310 . Giải Đặt   3 2 1f x x x x    . Khi đó ta có:       23 2 1 6 2 0, 0,1 f x x x f x x x           Từ đây ta suy ra  1 6f x  . Dễ thấy  0 1 0f    . Ta xét dãy   0,n nx   được xây dựng như sau:        0 2 1 2 0 2 1 1 1 2 3 0, n n n n n n n n n x f x x x x x x f x f x x n               Từ đây ta tính được 6 7 80, 5428763, 0,543428, 0, 543605x x x   . Ta đánh giá sai số của 8x so với nghiệ