Tài liệu Giải tích số phạm kỳ anh

THƯ VIỆN ĐẠI IIỢC TIIUY SẢN 519.4 Ph 104 A GIẢI TÍ ( Sweep, method J 1 / -----------I n p u^ t , n , A------------, 2 ? / 1h m 1/n X »= l, 2,...,n-l K ~ i r ~ 5 = 2 +£i^i mi = n, = (2 -M )/5 ; > - 2)/S; = 2/i/5 i c, * a i / ( a 0h - <*ị ); dp « A h /a i I ---------- \ I = 1,2, ...,n 1 m, - f»iC»-i); di = M 3 - n,¡Ci-idi-1 y. - ị 'i + 0icn- ì d n-\)/Ụĩph + 01 -1h 0iCn- i ) I i as n —1 , 1 c ■ T s ^ yi » c»(d» —y»+i) "7 n ~ 7 / P r i n t Í V iĩĩ/ End NHÀ XUẤT BẢN ĐẠI I IỌC QUỐC GIA HÀ NỘI IN LẦN THỨ II NHÀ XUẤT BẢNĐẠI HỌC QUỐC GIA HÀ NỘI -1996 CHỊU TRÁCH NHIỆM XUẤT BẤN: Giám Đốc: Nguyễn Văn Thòa Tổng biên tập: Nghiêm Đỉnh V ỳ Biên tập: N g u y ễ n H ã u D ư Trình bày bìa: N gọc A n h Giải tích số - Phạm Kỳ Anh - H - Đại học Quốc gia Hà Nội 200 trang; 27 cm - Mã số: 01.01-ĐH 96 - 142.96 LÒI NÓIĐẰU Giáo trình Giải tích số (GTS) này được biên soạn theo chưong trình cải cách của Bộ Giáo dục và Đào tạo. Chương trình này đã cắt giảm thòi lượng của môn GTS từ 6 đon vị học trình (đvht) cho sinh viên khoa Toán - Cơ - Tin học truòng Đại học Tổng hộp Hà nội xưống còn 3 đvht cho sinh viên nhóm ngành I và dự định dạy trong giai đoạn I. Tuy nhiên quá trình thử nghiệm giảng dạy giai đoạn I ở trưòng Đại học Tổng hộp Hà nội cho thấy do khối lượng kiến thúc đại cương quá lốn nên GTS phải chuyên sang dạy ỏ giai đoạn II, vổi thòi lượng lớn hon (4 đvht). Vì. vậy mặc dù được giao viết giáo trình GTS vối thòi lượng 3 đvht, song để đáp ứng nhu cầu sủ dụng đa dạng của các đối tượng khác nhau và xu thế nâng cao chất lượng đào tạo của Đại học Quốc gia Hà nội, trong Giáo trình này chúng tôi vẫn trình bày trong khoảng từ 4 đến 6 đvht những vấn đề co bản của GTS. Trong quá trình biên soạn, chúng tôi giữ quan điểm là dù có tinh giản đến đâu, giáo trình GTS ngảy nay phải sử dụng ngôn ngữ của Toán và Tin học đương đại. Nhiều thuật toán được minh hoạ bởi các ví dụ số, các so đồ khối và kết quả chạy máy. Đây ỉà một trong những điểm khác biệt của Giáo trình này so vỏi các giáo trình GTS bàng tiếng Việt hiện có. Kinh nghiệm giảng dạy lý thuyết và huỏng dẫn thực hành máy của tác giả cho thấy so đồ khối chi tiết giúp sinh viên dễ lập trình và hiểu sâu thuật toán hơn. Dĩ nhiên những so đồ khối mà chúng tôi trình bày ỏ đây còn mang tính học thuật. Đ ể áp dụng vào thục tế, học viên cần sáng tạo thêm. Ví dụ để giải phương trình f (x)—0 bằng phương pháp lặp, ta không nên chỉ dừng máy theo một tiêu chuẩn Xn — Xn — 1 < £1 mà nên xét thêm các quy tác dừng khác, như số lần lặp quá lổn n >Nmax hay lượng không khổp đã khá bé Ị f(x) Ị < £2. Do thòi gian và trình độ có hạn, Giáo trình này không tránh khỏi thiếu sót. Chúng tôi rất mong được bạn đọc góp ý và lượng thứ. H à nội 11 - 6 - 1 9 9 5 Tác giả Chương mỏr đầu GIỚI THIÊU VÊ GIẢI TÍCH s ố §1. Giài tích số là gì? Giải tích số (Numerical Analysis) hay còn goi là Phương pháp số (Numerical m eth­ ods), Phương pháp tính (Computational methods), Toán hoc tính toán (Computational mathematics), theo cuốn Bách khoa toàn thư về khoa học và kỹ thuật, NXB Mc.Graw Hill 1992, là một khoa hoc nghiên cứu cách giải gần đúng, chủ yếu là giải số, các phương trình, các bài toán xấp xỉ hàm số và các bài toán tối ưu. Thoạt đầu, toán hoc phát sinh do nhu cầu giải các bài toán thực tế: Tính diện tích đất đai, quỹ đạo sao chổi, đường di của các tàu buôn trên biển V. V. .. Như vậy có thể nói lúc đầu toán học đồng nghĩa với toán học tính toán. Cùng với sự phát triển nội tại cùa toán học và các ngành khoa học khác, toán học chia thành toán lý thuyết và toán ứng dụng. Tuy nhiên, những nhà toán học vĩ đại như Newton, Lagrange, Euler, Lobasepski, Gauss, Chebysev, Hérmitte. v.v... đều có các công trình nền móng trong Giải tích số. T ừ những năm 50 trờ lại đây, nhất là từ những năm 80, Giải tích số đặc biệt phát triển cùng với sự phát triển của Tin hoc. Ngày nay, với sư xuất hiên cúa siêu máy tính (Super Computer) khả năng song song hoá các quá trình tính toán đươc rộng mở. Nhiều thuât toán song song đã được đề xuất và áp dụng giải các bài toán thực tế. Như trên đã nói, 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 tap, hoặc môt hàm cho dưới dạng bảng bằng những hàm số đơn giản hơn. Trong lý thuyết xấp xỉ hàm, người ta thường nghiên cứu các bài toán nôi suy, bài toán xấp xỉ đều và xấp xỉ trung bình phương. 2. Giải gần đúng các phương trình: Phương trình đại số và siêu việt, hệ phương trình đai số tuyến tính, hê phương trình phi tuyến, bài toán tìm vector riêng, giá trị riêng của một ma trận, giải phương trình vi phân thường, phương trình đạo hàm riêng, phương trình tích phân và phương trình vi - tích phân. 3. Giải gần đúng các bài toán tối ưu: quy hoạch tuyến tính, quy hoach lồi, quy hoạch toàn phương, quy hoạch nguyên, điều khiển tối ưu, trò chơi vi phân v.v... Tuy nhiên, trong các giáo trình Giải tích số truyền thống, người ta chỉ đề cập đến hai nhiệm vụ đầu của Giải tích số, còn nhiệm vụ thứ ba dành cho các giáo trình về Quy hoach. §2. Sự khác biêt giữa toán lý thuyết và toán học tính toán (toán tính). Nếu toán lý thuyết chỉ quan tâm đến việc chứng minh tồn tại nghiệm, khảo sát dáng điệu và một số tính chất định tính của nghiệm thì toán tính đề xuất thuật toán giải trên máy. Giải tích số đặc biệt quan tâm đến các vấn đề: thời gian máy, bộ nhớ cần sử dụng để giải bài toán, tốc độ hội tụ và sự ổn định của thuât toán. Sau đây là một số ví dụ về sự khác biệt giữa toán tính và toán lý thuyết. V í diu 1. Giả sử ta cần tính tích phân In = f (n > 1). x ne x~ ì dx Jo Tích phân từng phần, ta được n Ị Xn 1ex 1 dx = 1 —n / n_ i . Jo Ngoài ra I\ = J x e x ỉ dx = x e x 1|q —J ex l dx = - 0,367879 Đến đây, người lảm lý thuyết cho rằng có thể tính được I n theo công thức truy hồi In = 1 — ư /n - i; /i = - — 0,367879. Thực ra không phải như vậy vì /9 ~ —0,068480, kết quả hoàn toàn không chính xác vì Vn, I n > 0. Cho dù ta có tính e 1 chính xác đến như thế nào chăng nữa thì ta vẫn nhận đươc I n < 0 với N đủ lớn. Nguyên nhân của sự thiếu chính xác này là do sai số ban đầu mắc phải khi tính e_ 1 tuy rấ t nhỏ nhưng bị khuếch đại sau mỗi bước. Để khắc phục hiện tượng này, ta tính theo công thức truy hồi ngược In-Ĩ = n *(1 - In). Đề ý rằng 0 > 1, cond(A) = 0 ( e n ). Qua những ví dụ trên, ta thấy trong quá trình giải số một bài toán, có thể nảy sinh nhiều vấn đề m à toán lý thuyết không quan tâm và không giải quyết được. Như vậy, cần phải có m ột khoa học riêng, chuyên nghiên cứu việc giải số các bài toán - đó chính là toán học tính toán. §3. Quan hệ giữa toán tính và tin học. Để giải số một bài toán thực tế, người ta phải lần lượt thực hiện các công đoạn của quá trình mô phỏng số sau: 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 giữa mô hình với hiện tượng thực tế. v ấ n đề tồn tại (và có thể duy nhất) của lời giải. Phương hướng tính toán. 3. Rời rạc hoá mô hình: Người ta thường dùng các phương pháp sai phân phần tử hữu hạn v.v... để quy 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. Ở công đoạn này, người ta còn chú ý đến các vấn đề: độ phức tap của thuât toán, tính hội tụ, ổn định của phường pháp giải bài toán. 5. Cài đặt và khai thác tin học. Giữa toán tính và tin học có mối liên hệ m ật thiết và sư tác đông qua lại. Do việc tăng tốc độ tính toán ciia máy gặp nhiều khó khăn về kỹ thuật, hơn nữa lai đòi hỏi chi phí lớn, nên để tính toán nhanh người ta thiên về cải tiến các phương pháp giải bài toán. T ừ đó xuất hiện phép biến đổi nhanh Fourier, các thuật toán song song v.v... Cùng với sự ra đời cùa các siêu máy tính: Máy tính song song, máy tính vector v.v..., xuất hiện nhiều phương pháp song song. Hiện nay ta được chứng kiến xu thế song song hoá đang diễn ra trong tấ t cả các lĩnh vực của Giải tích. Để tiết kiệm bộ nhớ trong máy tính, người ta đã đề xuất những phương pháp hữu hiệu xử lý hệ lớn, thưa: như kỹ thuật nén ma trận, kỳ thuật tiền xử lý m a trận V . V. . .. §4. Một Số khái niệm cơ bán của Giải tích hàm. 4.1. K hôn g gian m etric. Hàm số d đ ư a mọi cặp phần tử {x,y} của tập X vào ]R'} được goi là khoảng cách (hay metric) nếu với mọi x , y , z € X ta có: 8 V í d ụ 2. Cho hệ phương trình đại số tuyến tính: Ax = b, trong đó A là ma trận vuông cấp n X n; b là vector n tắc, có thể giải hệ (2.1) theo quy tắc Cramer: _ ( 2. 1) - chiều và detrì / 0. Ve nguyên / • _ ĩ-----X X l= A ( 2.2 ) = 1 ’n ' trong đó A = detA, còn Aj là định thức của ma trân, nhận đươc từ A bằng cách thav cột thứ i bằng cột b. Đe tìm nghiệm theo (2.2), ta phải tính (n + 1) định thức. Mỗi định thức có n! số hạng. Mỗi số hạng có n thừa số, do vậy để tính mỗi số hang phải thưc hiên (n — 1 ) phép nhân. Như vậy, riêng số phép nhân phải thực hiện trong (2.2) đã là n\(n + 1)(?1 — 1 ). Giả sử n = 20 (trong thực tế, đôi khi ta phải giàihê cho n = O(103)), và máy tính cùa ta thực hiện được 105 phép nhân trong một giây. Kh dó để thực hiên hết các phép nhân theo (2.2) cũng phải mất 3 X 108 năm! V í d u 3. Xét hệ (2.1) với ma trận A = diag(0.1,0.1,..., 0.1) và n — 100. Khi đó detrì = 1 0 ~ 100 ~ 0 , và theo quan điểm lý thuvết thì ma trân A rất suy biến. Thực ra hoàn toàn không phải như vậv, A ~ ì = 10.E, trong đó E là ma trận đơn vị. Trong toán học tính toán, người ta (lùng một đặc trưng khác, goi là số điều kiện cond(A) của A để kiểm tra tính suy biến của nó. Nếu cond(A) càng lớn thì ma trận A càng gần suy biến. Trong ví dụ này cond(A) = 1 , và A được coi là ma trận điều kiện - tốt (well conditioned). V í d u 4. Hê (2.1) với ma trân Hilbert thường gặp trong oài toán xấp xí trung bình phương bằng đa thức đại số. Ma trận A khả nghịch và V' 1 = (rtij), trong đó Tuy nhiên, cho đến nay việc giải hệ này vẫn còn là một thách thức đối với những người làm ứng dụng. Đe thấy được khó khăn trong việc giải số hệ (2.1) với ma trận Hilbert, ta xét trường hơp đơn giản n — 3. Ta có hệ: ( 1 . 1 //Z 2 \l/3 1/2 1/Ó 1/3 1/4 1/3 i/ 1/4 l/ 5 i Xị 11/6 •i'3 13/12 47/60 (2.3) Nghiệm đúng của ( 2 . 3 ) là X * = ( 1, 1, 1) T . Nếu thay 1/3 ~ 0,333 và tìm nghiệm theo những phương pháp s ố tố t nhất, ta nhận được X ~ ( 1 , 090 ; 0 , 4880 ; 1 , 491 ) T . Kết quả hoàn toàn không chính xác. Nguyên nhân là do m a trận Hilbert rấ t điều kiện xấu: Khi n > > 1 . cond(rì) = 0 (en ). Qua những ví dụ trên, ta thấy trong quá trình giải số một bài toán, có the nảy sinh nhiều vấn đề m à toán lý thuyết không quan tâm và không giải quyết được. Như vậy, cần phải có một khoa học riêng, chuyên nghiên cứu việc giải số các bài toán - đó chính là toán hoc tính toán. §3. Quan hệ giữa toán tính và tin học. Để giải số một bài toán thực tế, người ta phải lần lượt thực hiện các công đoạn của quá trình mô phỏng số sau: 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 giữa mô hình với hiện tượng thưc tế. v ấ n đề tồn tại (và có thể duy nhất) của lời giải. Phương hướng tính toán. 3. Rời rac hoá mô hình: Người ta thường dùng các phương pháp sai phân phần tử hữu hạn v.v... để quy 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, ơ công đoạn này, người ta còn chú ý đến các vấn đề: độ phức tạp của thuật toán, tính hội tụ, ổn định của phường pháp giải bài toán. 5. Cài đặt và khai thác tin học. Giữa toán tính và tin học có mối liên hệ m ật thiết và sự tác động qua lại. Do việc tăng tốc độ tính toán của máy gặp nhiều khó khăn về kỹ thuật, hơn nữa lại đòi hỏi chi phí lớn, nên để tính toán nhanh người ta thiên về cải tiến các phương pháp giải bài toán. T ừ đó xuất hiện phép biến đổi nhanh Fourier, các thuật toán song song v.v... Cùng với sự ra đời của các siêu máy tính: Máy tính song song, m áy tính vector v.v..., xuất hiện nhiều phương pháp song song. Hiện nay ta được chứng kiến xu thế song song hoá đang diễn ra trong tấ t cả các lĩnh vực của Giải tích. Để tiết kiệm bộ nhớ trong máy tính, người ta đã đề xuất những phương pháp hữu hiệu xử lý hệ lớn, thưa: như kỹ thuật nén ma trận, kỳ thuật tiền xử lý ma trận V . V . . . . §4. Một Số khái niêm cơ bán của Giải tích hàm. 4.1. K h ô n g gian m etric. Hàm so d đ ư a mọi cặp phần tử {x,y} ctỉa tập X vào IR'} đươc goi là khoảng cách (hay metric) nếu với mọi x , y t z e X ta có: 8 a) d(x, y ) > 0. Dấu bằng xảy ra khi và chỉ khi X = y. b) d(x,y) = d(y,x). c) d(x,z) < d(x,y) + d(y,z) (bất đằng thức tam giác). Cặp (X, d) gồm tập nền X , metric d xác định trong X, được gọi là không gian metric. Nếu không sợ nhầm lẫn, ta có thể dùng ký hiệu X để chỉ không gian metric (X ,d). Với mỗi Xo 6 X cố định, tập S ( x 0, R ) := {x € X : d( x , x 0) < R} được gọi là hình cầu mở tâm x0, bán kính R. Tương tự như vậy các tập S ( x 0, R ) := {x 6 X : d( x , x 0) < R}vkS°(x0,R) = {x e X : d ( x , x 0) = R} được gọi là hình cầu đóng hoặc mặt cầu tâm x0, bán kính R. Ta nói dãy (x „ Ị c X hội tụ đến phần tử X 6 X (ký hiệu: x n —*■x) nếu d(xn,x) —> 0(n —►oo). Ánh xạ A đưa không gian metric X vào không gian metric Y liên tục tại điểm X € X khi và chỉ khi mọi dãy X n —>X suy ra A ( x n) —>A(x). Dãy {xn} là dãy Cauchy, hay dãy cơ bản, nếu: Ve > 0 3N(e) Vn, m > N(e) d(xn, x m) < £ Không gian metric X là đầy đủ, nếu mọi dãy cơ bản hội tụ đến một phần tử nào đó thuộc X. Ánh xạ A đưa không gian metric (X, d) vào trong nó được gọi là ánh xạ co nếu tồn tại hằng số q € [0,1) sao cho với mọi X, y e X , d(A(x), A(y)) < qd(x, y). Hằng số q được gọi là hệ số co của A. Dễ thấy mọi ánh xạ co đều liên tục. Nguyên lý ảnh xạ CO (Banach). Cho A là ánh xạ co trong không gian metric đủ (X, d). Khi đó: a) Tồn tại duy nhất X* € X sao cho A(x*) = X * . Phần tử X* gọi là điểm bất động của ánh xạ A. b) Mọi dãy lặp X n + 1 = A ( x n) (n > 0) xuất phát từ x0 bất kỳ đều hội tụ. Ngoài ra, ta có các ước lưcmg sau d(xn,x*) < qn(l - q)~ỉ d(x0,Xị) d(xn,x*) < q(ỉ - g)~1 d(xn_1 ,x n) Chứng minh. 1. Vi d(xn+1, x n) — d(A(xn), A(xfị—I )) 5; qd(x n,x n—i) nên (n > 1) (n > 1 ) (4 .2 ) ... ^ qnd(x0ìx j) d(xfi, x n-ị-m) ^ d(xn, Xn-Ị-X) "b d(xn-ị-1 , xn_|_2 ) T ••• 4" ^(í-n+m—1J 9 (4.1) )— < qnd(Kx 0lx i){ l + q + ... + qm —?) ^ d ( x0, X\). Từ đây suy ra dãv |x „ Ị là cơ bản. Do X đầy đủ nên x n —> X * . Qua giới han trong biểu thức X n + 1 = A ( x n) ta được X * = A(x*). 2. Giả sử £, là hai điểm bất động của A. Ta có 0 < d(Z,q) = d(A(£),A(q) < qd(£,q). T ừ đây suy ra d(C c) = 0 hay £ — q. 3. Cho m —>oo trong biểu thức d(xn, x n+m) < qn{1 - q)~l d(x0, x i ) ta đươc d(xn,x*) < qn(1 - ợ)- 1 . Để nhân đươc (4.2) ta đánh giá d(xn,x n+m) < gd(xn_ i ,x n){ l + q + ... + < q( 1 - ạ)_1d(xn_ i , x„). Qua giới hạn khi m —Vco, ta có (4.2). (đpcm) H ệ quả. Giả sử Vx, y € S ( x 0,r) c X , trong đó X là không gia.11 metric đủ, d(A(x), A(y)) < qd(x, y) với hằng số q e (0,1). Nếu d(A(x0) , x 0) < (1 - q)r thì A có duy nhất với một điểm bất động trong S ( x 0,r). Chứng minh. Tập z := S ( x 0, r) với metric d cũng là môt không gian metric đù. Đe áp dung nguyên lý ánh xa co, chỉ cần chứng tỏ A đưa tâp z vào z . T hật vậy, Vx e z d(A(x), x 0) < d ( A ( x ) , A ( x 0)) + d( A ( x 0), X o ) < qr + (1 - q)r = r, nghĩa là A(x) 0. Dấu bằng xảy ra khi và chỉ khi X = y. b) d(x,y) = d(y, x). c) d(x,z) < d(x,y) +d ( y , z ) (bất đẳng thức tam giác). Cặp (X , d) gồm tập nền X , metric d xác định trong X , được gọi là không gian metric. Nếu không sợ nhầm lẫn, ta có thể dùng ký hiệu X để chỉ không gian metric (X, d). Với mỗi X o e X cố định, tập S ( x 0, R ) := {x e X : d(xì x 0) < R} được gọi là hình cầu mở tâm x0, bán kính R. Tương tự như vậy các tập S ( x 0, R) := {x G X : d(x,Xo) < R}vkS°( x0, R) = {x € X : d ( x , x 0) = R} được gọi là hình cầu đóng hoặc mặt cầu tâm x 0, bán kính R. Ta nói dãy {xn } c X hội tụ đến phần tử x £ X (ký hiệu: x n —►x) nếu d(xn,x) —►0(n —►oo). Anh xạ Ả đưa không gian metric X vào không gian metric Y liên tuc tại điểm X € X khi và chỉ khi mọi dãy x n —* X suy ra A ( x n) —* A(x). Dãy {Xn} là dãy Cauchy, hay dãy cơ bản, nếu: Ve > 0 3N(e) Vn, m > N(e) d(xn, x m) < £ Không gian metric X là thuộc X . * đầy đủ, nếu mọi dãy cơ bản hội tụ đến một phần tử nào đó Anh xạ A đưa không gian metric (X, d) vào trong nó đươc goi là ánh xạ co nếu tồn tại hằng số q e [0,1) sao cho với mọi X , y e X , d(A(x), A(y)) < qd(x, y). Hằng số q được gọi là hệ số co của A. Dễ thấy mọi ánh xạ co đều liên tục. Nguyên lý ánh xạ CO (Banach). Cho A là ánh xạ co trong không gian metric đủ (X, d). Khi đó: a) Tồn tại duy nhất x* G X sao cho A(x*) = X * . Phần tử X* goi là điểm bất đông của ánh xạ A. b) Mọi dãy lặp £ n+1 = A ( x n) (n > 0) xuất phát từ x 0 bất kỳ đều hội tụ. Ngoài ra, ta có các ước lượng sau d(xn,x*) < qn(l - q)~1d(x0, x ì ) d(xn,x*) < q(ì - q ) - 1d(xn^.u x n) Chứng minh. 1. Vi d(xn^-i,xn) nên d(A(xn), A ( x n—1 )) V ợd(xn,x n_ i) (n > 1) (n > 1) ... ^ ợnd(x0,x i) dịxịi, xn+m) V d(xn, xn+i) + d(xn+i, xn-|-2) + ••• + địxn+m- i , xn+m) < 9 (4.1) (4.2) <■ qnd(x0, Xị ) { l q A qm 1} ^ q n(l —q) 1c?(xo, Xi). T ừ đây suy ra dãv {xn} là cơ bản. Do X đầy đủ nên x n —>X * . Qua giới hạn trong biểu thức x n+\ — A { x n ) ta được X * — A(x*). 2. Giả sử £, q là hai điểm bất đông của A. Ta có 0 < d (£ ,ọ = d(A({),A(q) < qd(£,q). T ừ đây suy ra d(£, q) = 0 hay £ = c. 3. Cho rn —> oo trong biểu thức d(xn, x njrJn ) ^ q ( 1 q) d(x o, XỊ) ta đươc d(xn,x*) < qn( 1 - q)~l . Để nhận đươc (4.2) ta đánh giá d( xn , x n+m) < qd(xn- i , x n){ 1 + q + ... + qm_1} < q( 1 - q)- 1 d (x „ -i, x n ). Qua giới hạn khi m —* co, ta có (4.2). (đpcm) H ê quả. Giả sử Vx,y € S ( x 0,r) c X , trong đó X là không gian metric đủ, d(A(x), A(y)) < qd(x,y) với hằng số q £ (0,1). Nếu d( A(x 0) , x 0) < ( 1 — q)r thì A cố duy nhất với môt điểm bất động trong S ( x 0,r). Chứng minh. Tập z := S ( x 0,r) với metric d cũng là môt không gian metric đủ. Đe áp dụng nguyên lý ánh xa co, chỉ cần chứng tỏ A đưa tập z vào z . T hật vây, 'ix £ z d(A(x), x 0) < d(A(x), A ( x 0)) + d(A(x0), x 0) < qr + ( 1 - q)r = r, nghĩa là A(x) £ z . ( đ p c m ) 4.2. K h ôn g gian tu y ế n tính. Ta nói trên X xác đinh một cấu trúc tuyến tính A, nếu với mọi x , y £ X , với moi t £ M 1 (hoặc t £ C ) xác định phép cộng X + y £ X và phép nhân tx £ X , thoả mãn các tính chất sau: a) X + y = y + X (giao hoán) b) (x + y) 4- z = X + (y + z)\ s(tx) — (st)x (kết hợp) c) (5 + t)x = sx + tx\ t(x -f y) = tx + ty (phân phối) d) Tồn tại phần tử không: X + 9 = X VT £ X e) Tồn tại phần tử đối: X -Ị- (—x) = 9 \fx £ X , f) l.x = X, 10 trong đó x , y , z là các phần tử bất kỳ thuộc X , s,t là hai số thực (phức) bất kỳ. Không gian tuyến tính (X, A) là tập nền X được trang bị cấu trúc tuyến tính A. Sau này, nếu không sợ nhầm lẫn có thể dùng ký hiệu X để chỉ không gian tuyến tính (X, A). Tâp F c X là không gian con của không gian tuyến tính X , nếu F kín đối với phép cộng và phép nhân với đại lượng vô hướng: Va, ậ G JR}{C)\ Vx , y ( z F = > a x - ị - Ọ y € : F Bao tuyến tính của tập hợp M n ^ ^ tịX i, trong đó tị € IR1, Xi c X , ký hiệu là Span(M), là tập các phần từ có dạng e M, (i = 1, n), n e IV. 1=1 n Hệ {x,}-!.! là độc lập tuyến tính nếu từ đẳng thức ^T^tịXi = 0 suy ra t\ = ... — i=1 t n = 0. Ngược lại, ta nói hê {xi}" phụ thuộc tuyến tính. Không gian X là n chiều, nếu tồn tại hệ n vector độc lập tuyến tính trong X , còn mọi hệ (n + 1 ) vector đều phụ thuộc tuyến tính. Nếu trong X có vô hạn các vector độc lập tuyến tính thì ta nói không gian X vô hạn chiều. Ánh xạ A đưa không gian tuyến tính X vào không gian tuyến tính Y được gọi là toán tử tuyến tính, nếu với mọi X , y 6 X , và a,/3 £ ]Rl (C), ta có A( ax -f /3y) = oiAx + /8Ay. Auli xạ / đưa không gian tuyến tính X vào iR1 gọi là phiếm hàm. Nếu / là toán tử tuyen tính đưa X vào ]R} ta nói / là phiếm hàm tuyến tính Tập M c X là tập hợp lồi, nếu với mọi x, y e M, ta có [z, y} := {tx + ( 1 - t)y : t e [0,1]} c M. 4.3. K hông gian tu y ến tính đinh chuẩn. Ta nói trêu không gian tuyến tính X xác định một cấu trúc chuẩn nếu với mọi X € X, Aấc định một số ||x||, gọi là chuẩn của X, thoả mãn 3 tính chất sau: a) Xác định dương: ||x|| > 0, dấu bằng xảy ra khi và chỉ khi X — 9. b) Thuần nhất dương: ||tx|| = |í|||x|Ị V.T e X Ví € JRl . c) Bất đẳng thức tam giác: ||x + y II < Ịị;cII + \\y\\ Vx,y € X. Moi không gian tuyến tính định chuẩn là không gian metric với khoảng cách (l(x. y) := ||x - y ||. Dãy {x„} c X hội tụ đến X € X khi và chỉ khi ||xn - x|| —>0 (n —> oo). Không gian Banac.h là không gian tuyến tính định chuẩn đầy đù. Hai chuẩn ||.||i và ỊI. II2 xác định trong không gian tuyến tính X gọi là tương dương, nếu tồn tại hai hằng số C \ , C2 > 0 sao cho Vx € X Ci||x||i < |Ịx ||2 < c2 ||j||i 11 Trong không gian hữu han chiều, mọi chuẩn đều tương dương. Toán tử tuyến tính A đư a không gian tuvến tính định clmẩn X vào không gian tuyến tính định chuẩn y gọi là giới nôi (bị chặn) nếu tồn tại liằng số M > 0, sao cho VxeX \\Ax \\y < M\\x\\x Toán từ tuyến tính là liên tục khi và chỉ khi nó giới nội. Gọi C(X, F ) là tập hợp các toán từ tuyến tính liên tuc đưa không gian tuyến tính định chuẩn X vào không gian tuyến tính định chuẩn Y. Cấu trúc tuyến tính trong £ { X , Y ) được xây dtmg như sau: VA, B e £ ( X ,F ) ; Ví € í ? 1; Vx e X (.4 +' B)x := Ax -f B x ; ( t A) x := t{Ax). Đặt Dê dàng kiểm tra các tính chất của chuẩn, do dó £(.Y, y ) trờ thành không gian tuyến tính định chuẩn. £ ( X , Y ) đầy dù nếu Y - đầy đù. Không gian liên hợp X * cùa không gian X là £ ( X , 2R1 ). Như vậy X* := £{ X , M 1) luôn dầy đii. Trong không gian hữu hạn chiều X — IRn, khi có một cơ sở cố dịnh, toán tử tuyến tính A đươc cho bời m a trân («ij)"j=iChuẩn trong M n có thể xác định như sau , vớil < p < -Ị-oo. Ba chuẩn thường dùng là: 1/2 Ba chuẩn tương ứng cùa m a trận Ả là n \\A\\2 = { max Xi(AT A ) } l /2, trong đó Aj( A1 A) là các giá trị riêng của ma trận dối xứng A TA , n IMIIoo = 1max <1< 11V 1 0. Đằng thức cảy ra khi và chỉ khi X = 9 fc>) (x,y) = (y,x) c) (ax + fiý; z) = a(x, z) + /3{y, z) Vx, y, z £ H; V», ¡3 £ ỈR1 Cặp (H , (.,.)) gọi là không gian có tích vô hướng hay không gian tiền Hilbert. Mọi không gian có tích vô hựớng là không gian định chuẩn, với chuẩn ||x|| = (x, x) 1 / 2 . Không gỉan Hilbert là không gian tiền Hilbett đầy đủ. Với mọi x,y £ ỉ ĩ ta có bất đằng thức CBS (Cauchy-Buniakovski-Schwartz): l(x>y)l < IMIIIyllHai phần tử X, y là trực giao nếu ( x , y ) = 0 . Hê {éi}^ trực giao nếu trực chuẩn nếu (en ,e m) = Snm (n , m £ ]N). Hệ {£n}i° đầỳ đủ nếu Span({x„}^°) = H , nghĩa là: (en, em ) = 0 (n ỹí m ) , Ve > 0, Vx e H , 3Sn — Ỵ 2 cix i (ci € .iR1; n = n(e) € IV) : IISn - x|| < £ 1 Giả sử { e ijf3 là hệ trực chuẩn trong không gian Hilbert. Với mỗi n Fourier Sfi = Cịtị, với a = (x, e ì ) . ¿=1 Ta nói chuỗi Fourier hội tụ đến X nếu IISn — XII —>0 (n —> o ó) . Trong không giần Hilbert, 4 mệnh đề sau tương đường. X £ H, ta lập tổng oo (a) X = y > , . 6j)ej i=1 (b) |[x||2 = 'ix £ H |(x,e;)|2 (đẳng thức Parseval) í '= i (c) Hệ đầy đủ (d) Nếu X trực giao với mọi ti (i £ JN) thì X = 0 Tròng giáo trình này chúng tôi đứa ra khá nhiều sơ đồ khối để mô tả các thuật toán. Sau đây là một số ký hiệu thường gặp trong các sơ đồ khối: / Input / Compute - Nhập số liệu - Tính toán Kiểm tra điều kiên 13 ^ i= /p r in t/ Ç End ) - Chu trình - In kết quả - Kết thúc chưcmg trình Ví dụ. Thuật toán tìm ’’epsilon” của máy được mô tả bằng sơ đồ khối sau 14 Chương I SỐ G Ầ N Đ Ú N G VÀ SAI s ố §1. Khái niêm về số gần đúng 1.1. Sai số tu y êt đối, sai số tưo'ng đối Trong tính toán, ta thường phải làm việc với các giá trị gần đúng của các đại lượng. •Ta nói O là số gần đúng của o*, nếu a không sai khác a* nhiều. Đai lượng A := \a — a*\ gọi là sai số thật sư của a. Do không biết o* nên ta cũng không biết A. Tuy nhiên, ta có thể tìm đươc Aa > 0, gọi là sai số tuyêt đối cùa a, thoả mãn điều kiện: I« —0*1 < Ao, (1.1) hav a — A a < a* < a + A a. Đương nhiên, A a thoà mãn điều kiên (1.1) càng nhỏ càng tốt. Sai số tương đối cùa o là ỗa := ——. Ịo| V í du 1. Giả sử o* = 7r; o = 3.14. Do 3.14 < 0* < 3.15 = 3.14 + 0.01 nên ta có the lấy Ao = 0.01. Mặt khác, 3.14 < 7T < 3.142 = 3.14 + 0.002 do đó có thể coi Ao = 0.002 V í d u 2. Đo đô dài hai đoạn thẳng AB, CD ta được a — lOcin và b — lem với Ao = Ab = O.Olcm. Khi đó ta có ốa = —— = 0.1% còn ỗb = —— = 1% hay ốb = 10.ốa. 10 1 Hiên nhiên rằng phép đo a chính xác hơn hẳn phép do b mặc dù A a = Ab. Như vậy dộ chính xác cùa môt phép đo phản ánh qua sai số tương đối. 1.2. Sai số thu gon Môt số thâp phân o có dang tông quát nlur sau: 0 = ±(/%10p + /íp-ilOP- 1 + ... + ỊỈp-slOp~s ) trong đó 0 < ß i < 9 (i — p —1, p —$)', ftp > 0 là những số nguyên. Nếu p — .s > 0 thì a là số nguyên; p —s = —m (m > 0) thì a có phần lẻ gồm rn chữ số. Nếu s = + 00, a là số thập phán vô hạn. Thu gọn một số o là vứt bỏ một số các chữ số bên phải a để được môt số ã ngắn gon hơn và gần đúng nhất với o. Qui t,ắc thu gọn: Giả sử o = ßplO“ + ... + ß j W + ... + ß p . s 1 0 p-* và ta giữ lại đến hạng thứ j . Gọi phần vứt bò là /í, ta đặt a = ßplQ1 + ... + ßj+11 0 J+1 + ßjlOJ, 15 trong đó: ßj + 1 nến 0.510J < ỊI < 10J ßj nếu 0 < /U < 0.5 10J Nếu //. = 0.510J thì íij = iij nếu ßj là chẵn và ßj = ßj nếu chăn -lẻ vì tính toán với số lợi hơn. V í dụ. 7T ~ 3.141592 ~ 3.14159 ~ 3.1416 ~ 3.1412 ~ 3.14 ~ 3.1 ~ 3. Sai số thu gọn r<í > 0 là mọi số thoà mãn điều kiện: tu'11 a — a\ 5/9. Ta sẽ gọi chừ số chắc theo nghĩa hep (rông) nếu LO = 0.5 lu.’ — 1). Khi viết số gần đúng, chỉ nên giữ lại một hai chữ số không chắc de khi tính toán số chỉ tác động dến các chữ số không chắc thôi. LO SỈI1 1.4. Q uan hê giữ a sai số tư ư n g đ ố i và ch ữ số chắc Gọi 7 „ là số chữ số chắc (theo nghĩa rộng) của a. Quan hệ giữa 7 a và A a đả xét trong mục 1.3. Ớdâv chúng ta nghiên cứu mối quan hê giữa 7 a và òa Xét một số gồm toàn số chắc «Ị = 314 X 10 1+1 (i = 1,2,...) vứi Aa¿ = 10~Ỉ+I Kỉii đó ốa, = 1/314 ( /• > ! ) 16