Giáo trình Phương pháp số

tổng công ty bưu chính viễn thông việt nam học viện công nghệ bưu chính viễn thông Giáo trình PHƯƠNG PHáP Số Biên soạn TS. Phan Đăng Cầu ThS. Phan Thị Hà Hà nội, tháng 10 / 2005 Lời nói đầu Giáo trình "Phương pháp số" này được biên soạn cho sinh viên đại học năm thứ hai các chuyên ngành Công nghệ thông tin (CNTT) và Viễn thông(VT) thuộc Học Viện Công nghệ Bưu chính Viễn thông với thời lượng 30 tiết lý thuyết và 15 tiết thực hành. Tương tự như các giáo trình về phương pháp số của các trường đại học khác, giáo trình này bao gồm các kiến thức cơ bản nhất về phương pháp số như số xấp xỉ và sai số, các phương pháp số trong đại số tuyến tính, phép nội suy và hồi quy, tính gần đúng nghiệm của phương trình phi tuyến, tính gần đúng đạo hàm và tích phân xác định, giải gần đúng phương trình vi phân. Như một phần để sinh viên tự tìm hiểu, chúng tôi bổ sung thêm chương 7 giới thiệu sơ lược về phương pháp Monte-carlo hay thực ra là phương pháp thử ngẫu nhiên để tính toán xấp xỉ các đại lượng tất định, là một lĩnh vực quan trọng và có nhiều ứng dụng trong thực tế, trong đó có nghành Bưu chính Viễn thông. Hiện nay tài liệu về "Phương pháp số" rất phong phú và cách trình bày cũng rất đa dạng. Nhiều tài liệu chỉ giới thiệu thuật toán, phần thực hành trên máy sinh viên tự thực hiện. Cũng có những tài liệu giới thiệu chi tiết các thuật toán cùng các chương trình cài đặt trên máy tính, giúp cho sinh viên có thể thực hành trên máy dễ dàng hơn. Chúng tôi theo hướng thứ hai, nghĩa là sau khi giới thiệu các thuật toán, chúng tôi giới thiệu luôn cả chương trình cài đặt. Điểm khác biệt của giáo trình này so với các tài liệu đã có là thay vì ngôn ngữ Pascal quen thuộc, chúng tôi viết các chương trình bằng C++ và có thêm phần đồ thị minh họa. Chúng tôi nghĩ rằng khi xem các bảng số, nhiều khi rất khó nhìn ra mối quan hệ giữa các đại lượng. Ví dụ trong bài toán hồi quy chẳng hạn, ta cần xác định một đa thức thích hợp xấp xỉ tốt nhất tập số liệu đã cho. Nếu chỉ nhìn vào các bảng với chi chít các con số ta rất khó phân biệt. Còn nếu biểu diễn bằng đồ thị, và thêm chức năng lựa chọn tăng giảm bậc của đa thức, ta có thể nhìn thấy rất rõ đa thức nào xấp xỉ tập số liệu tốt hơn. Lập trình cài đặt các thuật toán về phương pháp số với một vài yêu cầu về chất lượng không phải là một việc quá đơn giản, nhất là đối với sinh viên năm thứ hai, khi kiến thức về lập trình máy tính còn khá hạn chế và các em còn phải dành thời gian cho nhiều môn học khác. Phần lớn các thuật toán trình bày trong giáo trình này đều có chương trình cài đặt kèm theo cùng với đồ thị minh họa nên nói chung khá dài. Trong khi trình bày các thuật toán chúng tôi chỉ giới thiệu đoạn chính của chương trình, bạn đọc có thể tham khảo liệt kê toàn văn các chương trình này trong phần phụ lục. Chúng tôi cũng để lại một số thuật toán như tính giá trị riêng và véc tơ riêng của ma trận, nội suy bằng phương pháp làm trơn, các thuật toán Monte-carlo... để các bạn có thể tự rèn luyện thêm kỹ năng lập trình của mình. Các bạn có thể tự viết chương trình cho mình với một cách trình bày khác (ví dụ không dùng con trỏ hàm để mô tả các hàm mà nhập hàm trực tiếp từ màn hình chẳng hạn) và chỉ xem những chương trình có sẵn là đáp án. Và cũng có thể khi so sánh với đáp án các bạn lại thấy chương trình của mình có nhiều điểm hay hơn chương trình mẫu. Trong những trường hợp đó chúng tôi rất vui mừng nghe ý kiến đóng góp của các bạn. Trong phạm vi của một giáo trình giảng dạy với thời lượng hạn chế, tài liệu này chỉ có khả năng giới thiệu một số thuật toán quen thuộc, chủ yếu ở mức độ giới thiệu thuật toán mà chưa đi sâu vào lý thuyết. Một số chi tiết về thuật toán và chương trình sẽ được giải thích rõ ràng hơn trong bài giảng lý thuyết và thực hành. Với trình độ hạn chế, tài liệu này chắc chắn còn chứa nhiều thiếu sót, chúng tôi mong nhận được ý kiến phê bình đóng góp của bạn đọc. Chúng tôi xin chân thành cảm ơn Lãnh đạo Học Viện Công nghệ Bưu chính Viễn thông và Phòng đào tạo đã tạo điều kiện thuận lợi để chúng tôi biên soạn tài liệu này. Chúng tôi cũng xin chân thành cảm ơn các đồng nghiệp trong Học Viện Công nghệ Bưu chính Viễn thông và ở các Viện hoặc trường đại học khác về những sự khích lệ và giúp đỡ nhiệt tình mà chúng tôi đã nhận được trong quá trình biên soạn giáo trình này. Hà Tây ngày 25 tháng 10 năm 2005 Nhóm tác giả mục lục Chương 1 Số xấp xỉ và sai số 1.1. Tổng quan về phương pháp số 1.1.1. Phương pháp số là gì? Phương pháp số (numerical method) hay đôi khi còn được gọi là Phương pháp tính (Computational method), Toán học tính toán (Computational mathematics) hoặc Giải tích số (Numerical analysis) là một lĩnh vực của toán học chuyên nghiên cứu các phương pháp giải gần đúng các bài toán bằng cách dựa trên những dữ liệu số cụ thể và cho kết quả cũng dưới dạng số. Nói gọn hơn, phương pháp số như bản thân tên gọi của nó, có nghĩa là phương pháp giải các bài toán bằng những con số cụ thể. Trong phương pháp số ta thường quan tâm đến hai vấn đề: Phương pháp để giải bài toán. Mối liên hệ giữa lời giải số gần đúng và lời giải đúng, hay vấn đề sai số của lời giải. Giải gần đúng nghĩa là lời giải của ta so với lời giải đúng có một sai số nào đó. Thông thường sai số do rất nhiều nguồn tạo nên và nhiều lúc rất khó tính toán chính xác là bao nhiêu, thậm chí ngay cả việc đưa ra một ước lượng gần sát với thực tế cũng khó có thể đạt được. Khi áp dụng một công thức lý thuyết vào thực tế, ví dụ áp dụng công thức tính diện tích hình tròn pr2 để tính diện tích đáy của một bể chứa nước chẳng hạn, ta không thể có được số p chính xác. Tùy thuộc vào yêu cầu của bài toán cụ thể , có khi ta chọn số p xấp xỉ bằng 3.14, có khi là 3.14159, hay chính xác hơn nữa 3.141595360... Có thể nói rằng có rất nhiều người đã áp dụng cách tính gần đúng để giải quyết một vấn đề thực tế nào đó, mặc dầu chưa được trang bị những kiến thức cần thiết về phương pháp số. Một nhà kinh tế khi hoạch định chính sách, thực hiện tính toán để dự báo về xu thế phát triển của một ngành kinh tế nào đó chẳng hạn, cũng thực hiện rất nhiều tính toán gần đúng, và có thể nói rằng trong phần lớn các trường hợp họ không đưa ra được một ước lượng là sai số khoảng bao nhiêu; hay một kỹ sư xây dựng khi tính toán để xây dựng một ngôi nhà, anh ta thực hiện rất nhiều phép tính, có khi chỉ bằng máy tính bỏ túi, rất khó xác định sai số tích lũy trong quá trình tính toán. Vậy mà anh ta vẫn hoàn thành công việc, và ngôi nhà xây xong có vẻ đạt tiêu chuẩn kỹ thuật. Có nghĩa là trong thực tế nhiều khi ta phải giải quyết những vấn đề mà ta biết là có sai số, nhưng bằng kinh nghiệm nghề nghiệp ta có cảm giác là sai số như vậy chấp nhận được hay không, và chấp nhận lời giải mà không hề có một đánh giá về sai số. Vậy thì môn học phương pháp số có thực sự cần thiết không? Học nó ta sẽ thu được lợi ích gì? Có thực sự cần thiết cho công việc chuyên môn của ta sau này không? Câu trả lời của chúng tôi là có, nhất là khi ta phải tính toán để giải một bài toán kỹ thuật đòi hỏi độ chính xác cao. Ta biết rằng trong máy tính các số có thể biểu diễn dưới nhiều dạng khác nhau, ví dụ số thực có thể biểu diễn với độ chính xác bình thường (single), độ chính xác gấp đôi (double) hay độ chính xác mở rộng (extended). Nếu ta biết được mối liên hệ giữa lời giải số với lời giải đúng, sẽ biết nên chọn độ chính xác nào để kết quả đáp ứng được yêu cầu thực tế. Ngay cả những lĩnh vực mà ta cảm thấy rằng không cần tính toán chính xác như điều tra nghiên cứu các vấn đề xã hội chẳng hạn, để các kết quả có căn cứ khoa học, ta phải tiến hành tính toán các khoảng tin cậy, khi đó cần tính toán xấp xỉ tích phân các hàm số phức tạp như hàm Gama (G(x)), hàm Bêta (B(x)),... nghĩa là ta cần đến công cụ phương pháp số. Để có thể thấy rõ thêm sự lựa chọn mô hình, và sau đó là lựa chọn phương pháp tính toán, đôi khi có ảnh hưởng lớn như thế nào đến kết quả thu được, ta xét một ví dụ đơn giản sau đây: Giả sử trong bài toán của ta có việc phải tính biểu thức ( - 1)10 . áp dụng công thức nhị thức Newton ta có công thức đúng: ( - 1)10 = 3363 - 2378 (1.1) Giá trị của 2 vế của (1.1) vào khoảng 0.000148676. Trong thực tế, ta không tính được giá trị chính xác của (khoảng 1.41421356240), mà chỉ tính được giá trị gần đúng. Bảng sau đây cho các kết quả của vế trái và vế phải của (1.1) ứng với các giá trị gần đúng của . Vế trái Vế phải 1.4 0.0001048576 33.8 1.41 0.00013422659 10.02 1.414 0.000147912 0.508 1.41421 0.00014866399 0.00862 1.414213563 0.00014867678 0.0001472 Ta có thể thấy rằng cách tính trực tiếp có kết quả khá ổn định, không bị tác động nhiều bởi sai số tính . Trong lúc đó cách tính dùng nhị thức Newton lại bị tác động rất lớn khi sai số thay đổi. Ngay cả khi ta lấy » 1.41421, tức là sai số tính nhỏ hơn 0.000005 thì kết quả của vế phải vẫn còn khác rất xa so với giá trị thật. Vậy rõ ràng khi cần tính biểu thức trên ta nên chọn phương pháp trực tiếp thì sẽ nhận được kết quả chính xác hơn. Còn nếu đã chọn phương pháp dùng khai triển nhị thức Newton thì ta phải chọn giá trị xấp xỉ của với độ chính xác khá cao, nếu không thì kết quả sẽ bị sai lệch rất nhiều. 1.1.2. Những dạng sai số thường gặp Trong thực hành có khi bài toán của ta là tìm cách tính toán xấp xỉ một mô hình toán học đã biết, ví dụ tìm nghiệm của một phương trình đã biết, tính tích phân xác định của một hàm số nào đó trên khoảng [a,b] cho trước. Tuy vậy ta gặp ngày càng nhiều những bài toán thực tế mà ngay cả mô hình toán học cũng chưa biết. Ví dụ, ta phải dự báo về số lượng thuê bao điện thoại trong một vài năm tới, số người truy nhập internet,...Trong những trường hợp này ta phải bắt đầu từ việc thu thập số liệu, xây dựng mô hình rồi tìm phương pháp tính toán... Nói chung khi thực hiện một bài toán bằng phương pháp số ta thường gặp những loại sai số sau đây: Sai số trong việc mô hình hóa bài toán, do ta không thể tính được hết những yếu tố ảnh hưởng đến bài toán, hoặc do ta biết được những yếu tố ảnh hưởng nhưng phải đơn giản hóa mô hình để có thể tính toán được. Ví dụ khi cần tính dung lượng của bể chứa nước hình trụ, ta biết rằng đáy của hình trụ không phải là một hình tròn chính xác, nhưng vẫn giả thiết là hình tròn để việc tính toán được dễ dàng hơn. Hoặc khi cần lập một mô hình biểu diễn các quan hệ kinh tế, ta biết rằng các mối quan hệ đó nói chung rất phức tạp, ví dụ không phải là tuyến tính, nhưng do không thể xác định được các yếu tố đó ảnh hưởng như thế nào nên trong nhiều trường hợp ta vẫn chấp nhận mô hình tuyến tính... Sai số phương pháp – là sai số của mỗi phương pháp dùng để tìm lời giải gần đúng. Trong ví dụ tính nhị thức Newton trên đây ta thấy rằng cùng một giá trị xấp xỉ của nhưng phương pháp tính trực tiếp cho kết quả chính xác hơn phương pháp dùng khai triển nhị thức Newton. Sai số của số liệu – Khi đo đạc bằng máy móc hoặc bằng các dụng cụ chuyên dụng ta chỉ đạt được độ chính xác nhất định. Máy móc hiện đại thường cho kết quả đo chính xác hơn. Sai số tính toán – sai số do ta làm tròn khi tính toán. Những sai số trên đây tổng hợp lại nhiều khi dẫn đến những lời giải quá cách xa so với lời giải đúng và vì vậy không thể dùng được. Chính vì vậy việc tìm ra những thuật toán hữu hiệu để giải các bài toán thực tế là điều rất cần thiết. Các phương pháp số đã được sử dụng có rất nhiều, và nhiều vấn đề hiện nay vẫn còn bỏ ngõ chờ sự nghiên cứu phát triển của các chuyên gia. Trong tài liệu này chúng tôi chỉ giới thiệu một số thuật toán thông dụng để bạn đọc làm quen dần với chuyên nghành này. Chúng tôi cũng chỉ đề cập đến một số loại sai số như sai số số liệu hay sai số tính toán, và đôi khi ta có khảo sát về sai số phương pháp, còn sai số do mô hình hóa thì nằm ngoài khuôn khổ tài liệu này. Để giúp bạn đọc có thể thực hành trên máy tính và nắm sâu hơn bài giảng, chúng tôi giới thiệu các chương trình cài đặt kèm theo viết bằng ngôn ngữ C++, là ngôn ngữ khá thông dụng hiện nay. 1.2. Sai số tuyệt đối và sai số tương đối Có rất nhiều công thức vật lý, toán học mà khi áp dụng vào thực tế ta chỉ có được các giá trị xấp xỉ. Có thể nói rằng trong phần lớn các vấn đề thực tế ta chỉ làm việc với các đại lượng gần đúng mà thôi. Sai số giữa đại lượng thật và đại lượng xấp xỉ nhiều khi rất khác biệt. Độ dài một con đường, độ cao của một ngọn núi hay chiều cao mực nước sông có thể là những số rất lẻ, thậm chí là số vô tỉ. Thế nhưng khi đo đạc ta lại cho các kết quả là những số đã làm tròn. Chiều cao ngọn núi ta chỉ lấy đến m (mét), độ dài con đường thường chỉ lấy đến km, còn chiều cao mực nước sông lại được đo đến mm (milimét). Vậy sai số như thế nào thì có thể chấp nhận được, nghĩa là không làm sai lệch ý nghĩa của các tính toán lý thuyết khi áp dụng vào thực tế? 1.2.1. Sai số tuyệt đối Xét đại lượng đúng A và đại lượng gần đúng của nó là a. Ta nói a xấp xỉ A và viết a A. Trị tuyệt đối Ea = | a-A | được gọi là sai số tuyệt đối của a (khi dùng a để xấp xỉ A). Trong thực tế ta không biết được số đúng A, do đó nói chung sai số tuyệt đối không tính được. Vì vậy ta tìm cách ước lượng sai số tuyệt đối của a bằng số a>0 sao cho | a - A | £ a (1.2) Số dương a được gọi là sai số tuyệt đối giới hạn của a. Rõ ràng nếu a là sai số tuyệt đối giới hạn của a thì mọi > Ea đều là sai số tuyệt đối giới hạn của a. Ta có thể thấy ngay là nếu sai số tuyệt đối giới hạn quá lớn so với sai số tuyệt đối thì nó không còn có ý nghĩa về phương diện sai số nữa. Ví dụ ta phải đo nhiệt độ của một vật mà ta không thể đặt thiết bị đo trực tiếp. Giả sử nhiệt độ thật là 1000 , ta đo được 1010 , sai số tuyệt đối chỉ là 10 nhưng lại đặt sai số tuyệt đối giới hạn là 200 thì rõ ràng sự hình dung của ta về nhiệt độ thật của vật có thể rất sai lệch so với thực tế. Thật vậy nếu chỉ dựa vào thông tin sai số tuyệt đối giới hạn thì ta phải hình dung là nhiệt độ của vật biến động trong khoảng 800 đến 1200 , trong khi thực ra ta đã có được kết quả chính xác hơn nhiều. Vì vậy trong những điều kiện cụ thể người ta cố gắng chọn a là số dương bé nhất có thể được thoã mãn (1.1). Nếu a là sai số tuyệt đối giới hạn của a khi xấp xỉ A thì ta quy ước viết: A = a ± a (1.3) với ý nghĩa của (1.1), tức là a - a £ A £ a + a (1.4) 1.2.2. Sai số tương đối Sai số tuyệt đối không nói lên đầy đủ "chất lượng của một xấp xỉ". Thật vậy giả sử một người phải đo đoạn đường rất dài, ví dụ đoạn đường trên Quốc lộ I từ Bắc đến Nam chẳng hạn, thu được kết quả là 1655 km và sai số tuyệt đối là 1 km. Người thứ hai phải đo mức nước hồ sông Đà chỗ sâu nhất được 21m, sai số tuyệt đối là 1 m. Nếu chỉ nhìn vào sai số tuyệt đối, ta thấy người thứ 2 đo chính xác hơn, thậm chí chính xác hơn 1000 lần so với người thứ nhất. Nhưng bằng cảm giác ta thấy ngay kết luận đó không hợp lý. Thậm chí ta phải kết luận ngược lại: người thứ nhất đo chính xác hơn người thứ hai. Trong thực tế ta có thể gặp rất nhiều trường hợp tương tự. Như vậy bản thân sai số tuyệt đối chưa nói lên độ tin cậy của xấp xỉ, mà ta còn phải so sánh độ lớn sai số đó với giá trị thật của đại lượng cần tính. Gọi Ea là sai số tuyệt đối của a khi dùng a để xấp xỉ A, khi đó đại lượng ea = (1.5) được gọi là sai số tương đối của a. Tuy nhiên một lần nữa ta thấy rằng A thường không biết, vì vậy người ta định nghĩa đại lượng da = (1.6) là sai số tương đối giới hạn của a. Từ đây ta có a = | a| da (1.7) Từ đây người ta thường viết A = a(1 ± da) (1.8) Vì trong thực tế ta chỉ có thể thao tác với các sai số giới hạn, do đó người ta thường gọi một cách đơn giản a là sai số tuyệt đối, da là sai số tương đối. Đôi khi người ta biểu diễn sai số tương đối dưới dạng %. Ví dụ với a =10, a = 0.05, khi đó ta có da = 0.05/10 = 0.5 %. 1.3. Cách viết số xấp xỉ 1.3.1. Chữ số có nghĩa Một số viết dưới dạng thập phân có thể gồm nhiều chữ số, nhưng ta chỉ kể các chữ số từ chữ số khác không đầu tiên tính từ trái đến chữ số cuối cùng khác không phía bên phải là các chữ số có nghĩa. Chẳng hạn số 2.740 có 3 chữ số có nghĩa, số 0.02078 có 4 chữ số có nghĩa. 1.3.2. Chữ số đáng tin Mọi số thập phân đều có dạng a = ± = ± Sas10s Trong đó as là những số nguyên từ 0 đến 9. Giả sử a là xấp xỉ của số A với sai số tuyệt đối là Ea . Nếu Ea £ 0.5*10s thì ta nói rằng chữ số as là đáng tin (và như vậy các chữ số có nghĩa bên trái as đều là đáng tin). Nếu Ea > 0.5*10s thì ta nói rằng chữ số as là đáng nghi (và như vậy các chữ số bên phải as đều là đáng nghi). Ví dụ. Số xấp xỉ a = 4.67329 với Ea = 0.004726. Ta có | Ea | £ 0.5 *10-2 do đó các chữ số đáng tin là: 4,6,7; các chữ số đáng ngờ là 3,2, 9. với Ea = 0.005726. Ta có | Ea | £ 0.5 *10-1 (nhưng | Ea | > 0.5 *10-2 ) do đó các chữ số đáng tin là: 4,6; các chữ số đáng ngờ là 7, 3, 2, 9. 1.3.3. Cách viết số xấp xỉ a. Kèm theo sai số Cách thứ nhất là viết kèm theo sai số như công thức (1.3) A = a ± a b. Mọi chữ số có nghĩa đều đáng tin Cách thứ hai là viết theo quy ước: mọi chữ số có nghĩa đều đáng tin; có nghĩa là sai số tuyệt đối Ea không lớn hơn một nửa đơn vị ở hàng cuối cùng. Nhận xét: Thực ra trong các tài liệu hiện có khi định nghĩa các chữ số đáng tin và chữ số đáng nghi người ta dùng khái niệm sai số tuyệt đối giới hạn chứ không dùng khái niệm sai số tuyệt đối như trên đây. Tuy nhiên theo chúng tôi, nếu hiểu như vậy và cho rằng trong tính toán chỉ nên giữ lại các chữ s