Giáo trình Giải tích số: Phần 1

Chia sẻ: Lê Na | Ngày: | Loại File: PDF | Số trang:96

Thêm vào BST

Báo xấu

397
lượt xem 89
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần 1 giáo trình "Giải tích số" gồm nội dung các chương: Chương mở đầu - Giới thiệu về Giải tích số, chương 1 - Số gần đúng và sai số, chương 2 - Phép nội suy, chương 3 - Xấp xỉ đều, chương 4 - Xấp xỉ trung bình phương, chương 5 - Tính gần đúng đạo hàm và tích phân.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Giải tích số: Phần 1

ĐẠI HỌC VINH THƯ VIÊN 515.071 PH-A/96 DT. 004600 ? GIAI TICH SỔ ^ Sweep, method^ / Input a o . a i , 0 0 , 0 i , n , A,B I km 1/n I l,2,...,n- 1 5 = 2 + jjjh; m, m 2(gX - 2)/S; m = (2-p k)/S; /, = 2/,/S i Co = ai/(a h a — 0tị)\ do = Ah/otị 1 2,...,n / 1 — J c , = l / ( m , - n . C j - i ) ; dị — fth? - n,c _id,_i t • 1 ,)/(>.* + A ' + ftc-l) = n rK ' " _ i Ki = c,(d, - Sf,+ i) / Print ị ( End ~) . Ị « NHA XUẤT BAN ĐAI H(|c QUÕC GIA HÀ NỘI
PHẠM KỲ ANH GIẢI TÍCH SÔ *JHiÀ XUẤT BẢN ĐẠI HỌC QUỐC GIA HÀ NỘI 1996
LÒI NÓI ĐÂU G i á o trình Giải tích số (GTS) này được biên soạn theo chương trình cải cách của Bộ G i á 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 đơn vị học trình (đvht) cho sinh viên khoa T o á n - Cơ - T i n học trường Đ ạ i học Tổng hộp H à nội xuống còn 3 đvht cho sinh viên n h ó m ngành ì và dự định dạy trong giai đoạn ì. Tuy nhiên quá trình thử nghiệm giảng dạy giai đ o ạ n ì ể 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 q u á l ố n n ê n GTS phải chuyển sang dạy ể giai đoạn l i , vói thòi lượng lển hơn (4 đ v h t ) . 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 k h á c nhau và xu t h ế nâng cao chất lượng đ à o tạo của Đ ạ i học Quốc gia H à nội, trong G i á 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 đ ề cơ bản của GTS. Trong q u á 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 T o á n và T i n học đương đ ạ i . N h i ề u thuật t o á n đuộc minh hoa bói các ví dụ số, các so đ ồ k h ố i và k ế t quả chạy máy. Dây là một trong những điểm khác biệt của G i á o trình này so vói các giáo trình GTS bằng tiếng V i ệ t hiện có. Kinh nghiệm giảng dạy lý thuyết và huống dẫn thục h à n h máy của tác giả cho thấy sơ đồ k h ố i chi tiết giúp sinh viên dễ lập trình và h i ể u sâu thuật toán hơn. D ĩ nhiên những sơ đồ 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 t h ê m . Ví dụ đ ể giải phương trình f(x)=0 bằng p h ư ơ n g p h á p lặp, ta không nên chỉ dừng máy theo một tiêu chuẩn Xít — X/t — Ì < £1 mà nên xét thêm các quy tác dừng khác, như số lần l ặ p q u á lớn n >Nmax hay lượng k h ô n g k h ớ p đ ã k h á b é I f{x) I < £2. Do thòi gian và trình độ có hạn, Giáo trình này không t r á n h 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 - 1995 Tác giả
Chương mờ đầu G I Ớ I T H I Ệ U VÈ G I Ả I TÍCH s ố §1. Giải tích số là gì? Giải tích số (Numerical Analysis) hay còn gọi là P h ư ơ n g p h á p số (Numerical meth ods), P h ư ơ n g p h á p tính (Computational methods), Toán học tính toán (Computational mathematics), theo cuốn Bách khoa toàn t h ư về khoa học và kỹ thuật, NXB Mc.Graw Hill 1992, là mót khoa hoe nghiên cứu cách giải gần đúng, chủ yếu là giải số, các p h ư ơ n g trinh, 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 học 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 đi cùa các tàu buôn trên biền V. V . . . Như vậy có t h ể nói lúc đầu toán học đụng nghĩa với toán hoe tính toán. Cùng với sự phát t r i ể 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 p h á t triển cùng với sư phát t r i ể n cùa T i n hoe. 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 hoa 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 tạp, 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ỉ trang bình phương. 2. Giải gần đúng các phương trình: P h ư ơ n g 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á t r i 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, p h ư ơ n g 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 hoạch lụi, quy hoạch toàn phirơ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ụ t h ứ ba dành cho các giáo trình về Quy hoach. 5
§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 t o á n lý t h u y ế t chỉ quan t â m đ ế n việc c h ứ n g m i n h t ồ n t ạ i n g h i ệ m , k h ả o s á t d á n g đ i ệ u v à m ộ t số t í n h c h ấ t đ ị n h t í n h của n g h i ệ m t h ì t o á n t í n h đ ề x u ấ t t h u ậ t t o á n g i ả i t r ô n m á y . G i ả i t í c h số đặc b i ệ t quan t â m đ ế n các v ấ n đ ề : t h ờ i gian m á y , b ộ n h ớ cần sự d ụ n g đ ể g i ả i b à i t o á n , tốc đ ộ h ô i t ụ v à sự ô n đ ị n h của t h u ậ t t o á n . Sau đ â y l à m ộ t số ví d ụ v ề sự k h á c b i ệ t g i ữ a t o á n t í n h v à t o á n lý t h u y ế t . V í d u 1. G i à sự t a cần t í n h t í c h p h â n n x ì In = í x e - dx (n > 1). Jo T í c h p h â n t ừ n g p h ầ n , ta được x x In=x r ^ x-iịi_e n ị x ~ t ~ dx n x = Ì - nin-] Jo N g o à i ra h= Ị Jo xt - dx x x = xt*- \\- x ị Jo x t ~ dx= l - ~ 0,367879 e Đ ế n đ â y , n g ư ờ i l à m lý t h u y ế t cho r ằ n g có t h ể t í n h đ ư ợ c In theo c ô n g t h ứ c t r u y h ồ i In = Ì - nin-!', J j = - a 0,367879. T h ự c r a k h ô n g p h ả i n h ư v ậ y vì / 9 2í -0,068480, e k ế t q u ả h o à n t o à n k h ô n g c h í n h x á c vì V n , I n > 0. - 1 Cho d ù t a có t í n h é c h í n h x á c đ ế n n h ư t h ế n à o c h ă n g n ự a t h ì ta v ầ n n h ậ n đ ư ợ c IN < 0 v ớ i N đ ù l ớ n . N g u y ê n n h â n c ù a sự t h i ế u c h í n h x á c n à y l à do sai số ban đ ầ u mắc - 1 phải khi tính e t u y r ấ t n h ổ n h ư n g bị k h u ế c h đ ạ i sau m ỗ i b ư ớ c . Đ ể k h ắ c p h ụ c h i ệ n t ư ợ n g n à y , t a t í n h theo c ô n g t h ứ c t r u y h ồ i n g ư ợ c 1 /„_! = n " ( l -/„). Để ý rằng n 1 0 < /„ < / x dx = (n + 1 ) - . Jo nen l i m In = 0. N ế u cho I 0 ^ 0 t h ì sai số m ắ c p h ả i l à £20 < — • K h i đ ó i i 9 ~ — v ớ i sai số £19 < — X — . 2 - 8 Đ ế n / i 5 , sai số chỉ còn £ 1 5 < 4 X lo và/ 9 ~ 0,091623. • 6
V í du 2. C h o h ệ p h ư ơ n g t r ì n h đ ạ i s ố t u y ế n t í n h : Ax = b, (2.1) t r o n g đ ó A l à m a t r ậ n v u ô n g c ấ p n X n ; ò l à v e c t o r n - c h i ề u v à detA Ạ 0. về nguyên tắc, có t h ể g i ả i h ệ (2.1) theo quy t ắ c Cramer: * í = ^ (i = M ) (2.2) trong đ ó A = detA, còn A , là định thức c ù a m a t r ậ n , n h ậ n đ ư ợ c t ừ A b ằ n g cách thay cột t h ứ i b ằ n g c ộ t ò. Đ e t ì m n g h i ệ m t h e o ( 2 . 2 ) , t a p h ả i t í n h (n + 1) đ ị n h t h ứ c . M ỗ i đ ị n h t h ứ c c ó ni số h ạ n g . M ỗ i s ố h ạ n g c ó n t h ừ a số, d o v ậ y đ ể t í n h m ỗ i s ố h a n g p h ả i t h ự c h i ệ n (li — 1) p h é p n h â n . N h ư vậy, riêng số p h é p n h â n p h ả i t h ự c h i ệ n trong (2.2) đ ã l à n ! ( n + l ) ( n — 1). G i ả s ọ n = 20 ( t r o n g t h ự c t ế , đ ô i k h i t a p h ả i g i ả i h ê (2.1) 3 5 cho n = O ( 1 0 ) ) , v à m á y t í n h c ủ a t a t h ự c h i ệ n đ ư ợ c lo p h é p n h â n trong m ộ t giây. Khi đ ó đ ể t h ự c h i ê n h ế t c á c p h é p n h â n t h e o ( 2 . 2 ) c ũ n g p h ả i m ấ t 3 X lo 8 năm! Ví dụ 3. X é t h ệ ( 2 . 1 ) v ớ i m a t r ậ n A = d i a g ( 0 . 1 , 0 . 1 , 0 . 1 ) v à ri = 100. Khi đó - 1 0 0 detA — l ũ ~ 0, v à t h e o q u a n đ i ể m l ý t h u y ế t t h ì m a t r ậ n Ả r ấ t suy b i ế n . T h ự c ra x h o à n t o à n k h ô n g p h ả i n h ư v ậ y , A~ = 10..É, t r o n g đ ó E là m a t r ậ n đ ơ n v i . T r o n g t o á n h ọ c t í n h t o á n , n g ư ờ i t a d ù n g m ộ t đ ặ c t r ư n g k h á c , g ọ i l à số đ i ề u k i ệ n c o n d ( A ) c ù a A để k i ể m tra t í n h suy b i ế n của n ó . Nếu cond(A) c à n g l ớ n t h ì m a t r â n A c à n g g ầ n suy b i ế n . T r o n g v í d ụ n à y c o n d ( A ) = Ì, v à A đ ư ợ c coi l à m a t r ậ n đ i ề u k i ệ n - t ố t ( w e l l c o n d i t i o n e d ) . í Ì V Ví du 4. H ê (2.1) với ma trân Hilbert A = Ị 7 1 thường găp trong bài t o á n x ấ p x ì t r u n g b ì n h p h ư ơ n g b ằ n g đ a t h ứ c đ ạ i số. Ma trận A k h ả nghịch và A~~ = (ttjj), trong đ ó n i 1 a- Uịj • — — (^— L) ì v + j r u- i - i _ j UC ~ n + i r ỉ + J _ uc}~ - _ L /ni„ 1 i + J 2 T u y n h i ê n , cho đ ế n n a y v i ệ c g i ả i h ệ n à y v ẫ n c ò n l à m ộ t t h á c h t h ứ c đ ố i v ớ i n h ữ n g n g ư ờ i làm ứng dụng. Đ e t h ấ y đ ư ợ c k h ó k h á n t r o n g v i ệ c g i ả i số h ệ ( 2 . 1 ) v ớ i m a t r ậ n Hilbert, t a x é t t r ư ờ n g h ợ p đ ơ n g i ả n n = 3. T a c ó h ệ : Ì 1/2 1/3 \ / x , \ / 11/6 \ 1/2 1/3 1/4 xa = 13/12 (2.3) 1/3 1/4 1/5/ V^3/ V47/60/ 7
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 p h á p số tốt nhất, ta nhận được X ~ ( Ì , 090; 0,4880; Ì, 4 9 1 ) . Kết quả 1 hoàn toàn không chính xác. Nguyên nhân là do nia trận Hilbert r ấ t điều kiện xấu: Khi n » Ì, cond(À) = ( ) ( ( " ) . 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 hoe tính toán. §3. Quan h ệ giữa t o á n t í n h v à t i n học. Đe giải số một bài toán thực tế, người ta phải lần ìưat thực hiện các công đoạn cùa quá trình mô phừng số sau: 1. Xây chmg mô hình toán hoe của bài toán thực tế. 2. P h â 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ê duv nhất) của lời giải. P h ư ơ n g hướng tính toán. 3. Rời rạc hoa mô hình: Người ta thường dùng các phương p h á 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 đoan 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 p h á 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à t i n học có mối liên hệ mật thiết và sự tác đông qua l ạ i . Dí) 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 p h ư ơ n g p h á p giai 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 p h á p so. I g song. Hiện nay ta được chứng kiến xu thế song song hoa đang điền ra trong t ấ t cả các lĩnh vực cùa Giải tích. Đe tiết kiệm bộ nhớ trong máy tính, người ta đ ã đề xuất những phương p h á p hữu hiệu xử lý hệ lớn, t h ư a : n h ư 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 G i ả i tích h à m . 4.1. K h ô n g g i a n m e t r i c . 1 Hàm số ả đ ư a mọi cặp phần t ừ {x,y} của tập X vào 2R được gọi là khoảng cách (hay metric) nếu với moi x,y,z G X ta có: s
a) d(x, y) > 0. D ấ u b ằ n g x ả y ra k h i v à chỉ k h i 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 , ã) g ồ m t ậ p n ề n X , metric d x á c đ ị n h trong X , đ ư ợ c g ọ i l à k h ô n g gian m e t r i c . N ế u k h ô n g sợ n h ầ m l ẫ n , t a có t h ể d ù n g ký h i ệ u X đ ể chỉ k h ô n g gian metric {X,d). V ớ i m ở i Xo € X cố đ ị n h , t ậ p S(x ,JỈ) 0 { x € X : d(x,x ) 0 < R} đ ư ợ c gọi l à h ì n h cầu m ở t â m Xo, b á n k í n h Ì?. T i r ơ n g t ự n h ư v ậ y các t ậ p S(X ,R) 0 : = {.r € X : d(x,x ) 0 < R}vkS°(x ,R) 0 = {x G X : d ( x , a : ) = i?} 0 d ư ợ c gọi là h ì n h cầu đ ó n g hoặc m ặ t cầu t â m Xo, b á n k í n h / ỉ . Ta nói d ã y c X hội tụ đ ế n phần t ử X e X (ký h i ệ u : £ „ —> x ) n ế u d(x ,x) n —> 0(?2 —> oo). Anh xạ Ẩ đ ư a k h ô n g gian metric X v à o k h ô n g gian metric K liên tục t ạ i đ i ể m X € X k h i v à chỉ k h i m ọ i dãy ;r n —* X suy ra A(x ) n —> A ( x ) . D ã y { # „ } là d ã y Cauchy, hay d ã y cơ b à n , n ế u : Ve > 0 3N(e) Vn,.m > N(e) d(x ,x )n m < £ K h ô n g gian metric X l à đ ầ y đ ù , n ế u m o i d ã y c ơ b ả n h ộ i t ụ đ ế n m ộ t p h ầ n t ừ n à o đ ó thuộc X. A n h x ạ A đ ư a k h ô n g gian metric ( X , ã) v à o trong n ó đưcrc gói là á n h x ạ co n ế u t ồ n t ạ i h ằ n g số q G [0,1) sao cho v ớ i m ọ i x,y e X , d(A(x),A(y)) < qd(x,y). H ằ n g số (ị đ ư ợ c gọi là h ệ số co của Ầ. D ể t h ấ y m ọ i á n h x ạ co đ ề u liên tục. Nguyên lý ánh xạ co (Banach). Cho A l à á n h x ạ co t r o n g k h ô n g gian m e t r i c đ ủ (X,(ỉ). Khi đó: a) T ồ n t ạ i duy n h ấ t X* e X sao cho A(x*) = X * . P h ầ n t ử X * gọi là đ i ể m b ấ t đ ộ n g cua á n h x ạ Ả. b) M ọ i d ã y l ặ p £ n + J = A(x ) n (n > 0) x u ấ t p h á t t ừ x„ b ấ t kỳ đ ề u h ộ i t ụ . N g o à i ra, ta có các ư ớ c l ư ợ n g sau n 1 d(x ,x*) 1) (4.1) 1 rf(.T„,x*) < 5(1 - g ) - d ( x „ _ , a : „ ) 1 ( n > 1) (4.2) Chứng minh. n 1. Vì d ( a : „ i , a r ) = d ( A ( z „ ) , A ( x „ _ i ) ) < ? d ( x „ , x _ ! ) < ... < ợ ư(:r , X j ) + B n 0 nên •E n ì 3- n + 1 £ n + l ) 2"'n+2 ) + ••• + d(x -ị. n m — ĩ , x -ị. n m ) < 9
n m 1 n < q d ( x , x ) { l + q+ 0 1 ... + q - } < q (l - q)-' d(x , X,). 0 T ừ đ â y suy ra d ã y { x n } l à cơ b ả n . Do X đ ầ y đ ủ n ê n £ „ — > £ * . Qua g i ớ i h ạ n t r o n g biêu thức X n + 1 = A ( x n ) ta đ ư ợ c X* = A(x*). 2. G i ả sử l à hai đ i ể m b ấ t đ ô n g của Ả. Ta có 0
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ó t h ể dùng ký hiệu X đ ể chỉ không gian tuyến tính (X, X). 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,/3 e SỨ{C); Vx,y € F => ax + 0y € F Bao tuyến tính cùa tập hợp M c X, ký hiệu là Span(M), là tập các phần t ừ có dạng ^ J i j X j , trong đó ti e M , 1 Xi e M, (i = ĩ~n), n 6 IV. i=l n Hệ {Xi}?=! l à đ 9 c lập tuyến tính nếu t ừ đẳng thức y j j X j = 0 suy ra tị = ... = t„ = 0. Ngược l ạ i , ta nói hệ { x j } j 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 G X, và a,Ị3 E i R ^ C ) , ta có Ẩ(ax + /Jy) = aAx + /?Ay. 1 Ánh xạ / đ ư a không gian tuyến tính X v ào 2R gọi là phiếm h à m . Nếu / là toán t ử tuyến tính đ ư a X vào m} 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ó [*, v] : = { < * + ( Ì - í ) y : t e [0,1]} CAT 4.3. K h ô n g gian t u y ế n t í n h đ ị n h chuẩn. Ta nói trên 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 I Ễ X , xác định một số ||x||, gọi là chuẩn của X, thoa mãn 3 tính chất sau: a) Xác định dương: > 0, dấu bằng xảy ra khi và chỉ khi X = 6. 1 b) Thuần nhất dương: ị|tx|| = |t|||x|| Vx € X Ví 0 (n —> oo). n n Không gian Banach là không gian tuyến tính định chuẩn đầy đù. Hai chuẩn ||.||] và ||.||2 xác định trong không gian tuyến tính X gọi là tương đương, nếu tồn t ạ i hai hằng số í" Ì , c2 > 0 sao cho V X Ễ I c, 11*11, < \\x\\ < c \\x\u 2 2 li
Trong không gian hữu hạn chiều, moi chuẩn đ ề u tương đương. Toán t ử tuyến tính A đ ư 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 gọi là giới nội (bị chặn) nếu tồn t ạ i Hằng số M > 0, sao cho Vrex \\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 , Y ) là t á p hạp các toán t ừ tuyến tính liên túc đ ư a không gian tuyến tính đinh 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 C ( X , Y ) đươc xây dựng n h ư sau: vi, J9 € £(A". r ) ; Ví € i R ; v.r € X ! (A +,B)x := A r + Bx; (Íi4);r : = t{Ax). Đặt = s u p IWI I F I I w= .||I||
4.4 K h ô n g g i a n c ó t í c h v ô h ư ớ n g 1 H à m số ( . , . ) đ ư a m ọ i c ặ p x,y t r o n g k h ô n g gian t u y ế n t í n h H v à o 1R g ọ i l à t í c h v ô h ư ớ n g c ù a x,y, k ý h i ệ u l à (x,y) n ế u n ó thoa m ã n các t í n h c h ấ t sau: a) (x, x) > 0. Đ ằ n g t h ứ c cày r a k h i v à chỉ k h i X = 9 b ) (x,y) = (y,x) X c) ( o i + 0y, z) = a(x, z) + P(y, z) Var, y,z € H; Va, ạ € JR Cặp (H, ( . , . ) ) g ọ i l à k h ô n g gian có tích v ô h ư ớ n g hay k h ô n g gian t i ề n H i l b e r t . M ọ i k h ô n g 1 gian c ó t í c h v ô h ư ớ n g l à k h ô n g gian đ ị n h chuẩn, v ớ i c h u ẩ n = (x, x) / 2 . K h ô n g gian H i l b e r t l à k h ô n g gian t i ề n H i l b e r t đ ầ y đ ủ . V ớ i m ọ i x,y £ H t a có b ấ t đ ẳ n g t h ứ c CBS (Cauchy-Buniakovski-Schwartz): |(x,y)| 0, Vx e H , 3 S n = cịXị (cị 1 € iR ; n = n(e) G JV): ||5„ - x|| < c i=l 3 G i ả sử { e , } ^ l à h ệ t r ự c c h u ẩ n t r o n g k h ô n g gian H i l b e r t . V ớ i m ỗ i X £ H, ta, l ậ p t ỗ n g n Fourier Su = c,e,-, v ớ i Cj = T a nói chuỗi Fourier h ộ i t ụ đ ế n X n ế u ||S„ — x|| —> 0 ( n —> oo). T r o n g k h ô n g gian H i l b e r t , 4 m ệ n h đ ề sau t ư ơ n g đ ư ơ n g . So ( a ) X = 5^(x,-,e;)ej Vx € H 1=1 (b) li re li 2 = J^K^e,-)! 2 ( đ ẳ n g t h ứ c Parseval) 1=1 (c) H ệ { e i } ~ đầy đ ù (d) N ế u ;c t r ự c giao v ớ i m ọ i e, ( i 6 W ) t h ì X = 0 T r o n g g i á o t r ì n h n ả y c h ú n g tôi đ ư a r a k h á n h i ề u s ơ đ ồ k h ố i đ ể m ô t ả c á c t h u ậ t t o á n . Sau đ â y l à m ộ t số k ý h i ệ u t h ư ờ n g g ặ p t r o n g các s ơ đ ồ k h ố i : / Input / - N h ậ p số Hệ lêu Compute - Tính toán Cond K i ể m t r a đ i ề u kiên 13
^ 1= 1 , 2 , n ^ - Chu trình /print/ - In kết quả ( End ) - K ế t thúc chương trình Ví dụ. Thuật toán tìm "epsilon" của máy được mô t ả bằng sơ đ ồ khối sau eps = Ì eps = eps/2 5 = 1 + eps ¥1 tua Ị Prdnt eps ỵ ( End ) 14
trong đó: 0j + Ì n ế u 0.5KP 0 l à m ọ i số thoa m ã n đ i ề u k i ệ n : \ă — a\ < Ta. Yia = ạ ìOP p + ... + ạ j w + fi, j + 1 3 còn ã = Ppio? +... + ạ j + iio + PjlO , j nên \a-ã\ = - Pj)10 + ụ\ < 0.5 w Sau k h i t h u g ọ n , sai số t u y ệ t đ ố i t ă n g lên: |a* - ã | < \a* - a\ + \a - ã\ < Aa + Ta. 1.3 C h ữ s ố c h ắ c C h ữ số có nghĩa l à m ọ i c h ữ số k h á c "0" v à cả "0", n ế u n ó k ẹ p g i ữ a hai c h ữ số có nghĩa hoặc n ó đ ạ i d i ệ n cho h à n g đ ư ợ c g i ữ l ạ i . V í d ụ . a = 0.0030140. B a c h ữ số " 0 " đ ầ u k h ô n g có nghĩa p M ọ i c h ữ số Ọ, c ù a a — ±(Ị3plO + ... + / 9 p _ 1 0 ~ ) g ọ i l à c h ữ số chắc, n ế u s p s A o < w x 1(T t r o n g đ ó LO- l à t h a m số cho t r ư ớ c . T h a m số LO được chọn đ ể m ộ t c h ữ số v ố n đ ã chắc sau k h i t h u g ọ n v ẫ n l à c h ữ số chắc. G i ả sụ c h ữ số chắc cuối c ù n g của a t r ư ớ c k h i t h u g ọ n l à ộ{. Đ ể v à c á c c h ữ số t r ư ớ c n ó v ẫ n chắc, p h ả i có í + 1 í + 1 + 1 Aa + Ta < cư X 1 0 . S u y ra Ui X 10* + 0.5 X 1 0 < LO X 1 0 ' hay Lú > 5/9. T a sẽ g ọ i c h ữ số chắc theo nghĩa h ẹ p ( r ô n g ) n ế u Ui = 0.5 (u; = 1). K h i v i ế t số g ầ n đ ú n g , chỉ n ê n g i ữ l ạ i m ộ t h a i c h ữ số k h ô n g chắc đ ể k h i t í n h t o á n sai số chỉ t á c đ ộ n g đ ế n c á c c h ữ số k h ô n g chắc t h ô i . 1.4. Q u a n h ê g i ữ a s a i s ố t ư ơ n g đ ố i v à c h ữ s ố c h ắ c G ọ i 7 a l à số c h ữ số chắc (theo nghĩa rộng) của a. Q u a n h ệ g i ữ a 7 a v à Aa đ ã xét t r o n g mục 1.3. Ở đ â y c h ú n g t a n g h i ê n c ứ u m ố i quan h ê g i ữ a 7
Ta n h ậ n t h ấ y : a) Sai số t ư ơ n g đ ố i k h ô n g p h ụ thuộc v à o vị t r í d ấ u c h ấ m t h ậ p p h â n trong m ộ t số. N h ư v ậ y Sa = Ì /a° t r o n g đ ó a° l à số a g ồ m t o à n c h ữ số chắc v à c h ữ số chắc cuối c ù n g ở h à n g đ ơ n vị. b) N ế u a° > b° ( > 0) t h ì a c h í n h x á c h ơ n b. Đ i ề u k h ẳ n g đ ị n h n à y còn đ ú n g n ế u •ya > ~fb. B i ế t sai số t ư ơ n g đ ố i của m ộ t số có t h ể t ì m đ ư ợ c số chữ số chắc của n ó v à n g ư ợ c l ạ i . C ụ t h ể h a n ta xét hai b à i t o á n sau: Bài toán 1. B i ế t 7a t ì m Sa 1 Giả sừ a = J7. (ạ > 1), a = s, ta có: {/no*- < a° < (p + 1)10*-» < lo*, do đó 7 (ạ+ 1)10^ - 6 ( 1 - ặ ĩ õ ^ ' N ế u k h ô n g b i ế t /3 ta l ấ y Bài toán 2. B i ế t Sa t ì m 7a; _ m _ m G i ả sừ a = ~Ẹ~. (ậ > 1), còn Sa = A l 0 (0.1 < A < 1). Ta có A a = A | a | 1 0 . Tạm t h ờ i d ờ i vị t r í d ấ u c h ấ m t h ậ p p h â n c ù a a đ ể có số a m v ớ i m + Ì chừ số trvrớc d ấ u c h ấ m t h ậ p p h â n . Ta có m _ m am < ( / i + l ) 1 0 =• A o = a r o ốa m = a 6a m = a AlO m < A ( / i + 1). Vì 0.2 < X(ậ + 1) < 10 n ê n ta có t h ể k ế t l u ậ n : a) N ế u \ ( p + 1) < Ì , t h ì A « m < Ì , do đ ó o m có m + Ì c h ữ số chắc v à k h ô n g n h i ề u h ơ n (v ì Aa m > 0.2). b ) N ế u xụi + 1) t h ì Ì < A o m < 10, n h ư v ậ y a m có ĨÌI c h ừ số chắc v à k h ô n g ít h ơ n (vì Aa m < 10). Do lý l u ậ n t r ê n k h ô n g p h ụ thuộc v à o vị t r í của d ấ u c h ấ m t h ậ p p h â n n ê n ta có qui m tắc sau: G i à s ư a = ạ... (ậ > 1), v à Sa = A l ( T (0.1 < A < 1). K h i đ ó a có m + Ì chữ số chắc n ế u X(fi + 1) < 1. N g ư ợ c l ạ i , n ế u \{P + 1) > Ì thì a có m c h ừ số chắc. N ế u k h ô n g b i ế t 0 t h ì a có ít n h ấ t ra c h ữ số chắc. §2. Sai S ố tính toán T r o n g t í n h t o á n ta t h ư ờ n g gặp 4 loại sai số sau: a) Sai số g i ả t h i ế t - Do m ô h ì n h hoa, lý t ư ở n g hoa b à i t o á n t h ự c t ế . Sai số n à y k h ô n g loại t r ừ đ ư ơ c . 17
b) Sai số p h ư ơ n g p h á p - C á c b à i t o á n t h ư ờ n g gặp r ấ t p h ứ c t ạ p , k h ô n g t h ể g i ả i đ ú n g đ ư ư c m à p h ả i sử d ụ n g các p h ư ơ n g p h á p g ầ n đ ú n g . Sai số n à y sẽ đ ư ợ c n g h i ê n c ứ u cho t ừ n g p h ư ơ n g p h á p cụ t h ể . c) Sai số các số l i ệ u - C á c số l i ệ u t h ư ờ n g t h u đ ư ợ c b ằ n g t h ự c n g h i ệ m do đ ó có sai số. Sai số cữa các số l i ệ u g ầ n đ ú n g đ ã đ ư ợ c n g h i ê n c ứ u t r o n g §1 d) Sai số t í n h t o á n - C á c số v ố n đ ã có sai số, còn t h ê m sai số t h u g ọ n n ê n k h i t í n h t o á n sẽ x u ấ t h i ệ n sai số t í n h t o á n . G i ả sử p h ả i t ì m đ ạ i l ư ợ n g y theo công t h ứ c : y = f(xi,X2,...,x ) n G ọ i X*, y* (i = Ì , n ) v à Xi, y (i = Ì , n ) là các g i á trị d ù n g v à g ầ n đ ú n g c ù a đ ố i số v à h à m số. N ế u f k h ả v i liên t ụ c t h ì n \y-y*\ = l / O i , . . . , * » ) - / ( s ĩ , . . . , O I = Y^\ft\\xt - X - I i=ì t r o n g đ ó J ị là đ a o h à m —— t í n h t ạ i các đ i ể m t r u n g gian. Do -jj- liên t ụ c , Axị k h á bé ta 1 Ox ị có t h ể coi n Áy = ^ |/-(XỊ , x n ) \ A x i , 1=1 do đ ó Áy /S.Xị. ơXi 1=1 Sau đ â y là sai số c ù a c á c p h é p t í n h c ơ b ả n a) S a i s ố c á c p h é p t í n h c ô n g t r ừ Vì ày dxị nên Áy = Ax t 1=1 G i ả sử Ax m — max Axi Ki Axm = 10*, vì v ậ y k h i l à m p h é p cộng đ ạ i số, n ê n qui t r ò n các Xi đ ế n m ứ c g i ữ l ạ i Ì hoặc 2 chữ số b ê n p h ả i h à n g t h ứ k. 18