intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng chuyên đề Phương pháp tính Phần 6

Chia sẻ: Leslie Nguyen | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST
Báo xấu
209
lượt xem 50
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Các phương pháp số gắn liền với việc ứng dụng trên máy tính số. Ma trận được ứng dụng rât thích hợp ở đây, như giải hệ phương trình vi phân, biểu diễn các vectơ ở dạng ma trận.Khi giải hệ đại tuyến A.X = B, ma trận A có thể là ma trận dày hoặc thưa; khi A là ma trận thừa, trong nhiêu trường hợp đã có thuật toán để lưu trữ tiêt kiệm bo nhớ và thời gian tính như lưu trữ dạng BAND bình thường hoặc dạng BAND ép lại, hay kỹ thuật lưu trữ Skyline (frontal...

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng chuyên đề Phương pháp tính Phần 6

  1. Khoa Xây D ng Th y L i Th y i n B môn Cơ S K Thu t Chương 5 CÁC PHƯƠNG PHÁP S C A I S TUY N TÍNH NUMERICAL METHODS FOR LINEAR ALGEBRA Các phương pháp s g n li n v i vi c ng d ng trên máy tính s . Ma tr n ư c ng d ng r t thích h p ây, như gi i h phương trình vi phân, bi u di n các vectơ d ng ma tr n. Khi gi i h i tuy n A.X = B, ma tr n A có th là ma tr n y ho c thưa; khi A là ma tr n thưa, trong nhi u trư ng h p ã có thu t toán lưu tr ti t ki m b nh và th i gian tính như lưu tr d ng BAND bình thư ng ho c d ng BAND ép l i, hay k thu t lưu tr Skyline (frontal method), v i nhi u thu t gi i r t hi u qu . 5.1 Ma tr n 5.1.1 Các nh nghĩa Ma tr n là t p h p g m m × n ph n t , chia thành m hàng và n c t.  a11 a12 ......a1n   a a ....a  Kí hi u: A m,n = [ai , j ]m,n =  21 22 2n   .......... .....    am1 am 2 ....amn  Có th coi ma tr n hàng(c t) là bi u di n i s c a m t vectơ (hình h c). V t (trace) c a ma tr n A ư c tính: Tr(A) = a11 + a22 +.....+ ann M i m t ma tr n vuông A u ư c g n v i m t s , kí hi u det(A) ho c A , ư c g i là nh th c. Ma tr n A ư c g i là suy bi n n u det(A) = 0 và ngư c l i là không suy bi n. 5.1.2 Phép bi n i tuy n tính trong không gian n chi u Gi a ma tr n và các phép bi n i tuy n tính trong không gian ( i s ) có m t m i liên h m t thi t. M t ph n t c a không gian n chi u có th ư c mô t b ng m t vectơ, hay vi t dư i d ng ma tr n c t. [ ] Xét hai vectơ: X n1= x1 , x 2 , x3 ,..., x n , Y n1= [ y1 , y 2 , y 3 ,..., y m ] T T V i phép bi n i: A.X=Y V i A là ma tr n c m × n ư c g i là phép bi n i tuy n tính t vectơ n chi u sang vectơ m chi u. Khi m=n ơn gi n là ta có m t phép chuy n t a . N u trong không gian 2 ho c 3 chi u v i các t a Descartes thì A chính là các ma tr n chuy n i. Ơ trư ng h p ơn gi n, A có th là ma tr n cosine ch phương khi th c hi n phép quay gi a hai h t a , có th là ma tr n cosine ch phương khi th c hi n phép Bài Gi ng Chuyên Phương Pháp Tính Trang 38
  2. Khoa Xây D ng Th y L i Th y i n B môn Cơ S K Thu t quay gi a hai h t a , có th là ma tr n v i m t ph n t duy nh t khác không (các ma tr n cơ b n) khi th c hi n các phép t nh ti n các h t a theo các tr c. M t h cơ s c a không gian n chi u là m t t p h p úng n vectơ c l p tuy n tính. Ví d : Ta có th ch n các vectơ ơn v ei làm h cơ s v i vectơ X b t kỳ: X=c1e1 + c2e2+....+ cne n e1 = [1,0,0,......... ]T 0  e2 = [0,1,0,......... ] T 0  .......... .......... ........ e = [0,0,0,......... ]T 1  1 X= [x 1 , x 2 ,..., x n ] T Tích vô hư ng c a hai vectơ: Y= [y 1 , y 2 ,..., y n ] T n ư c nh nghĩa: XT.Y = YT.X = ∑x y 1 i i (trong không gian Euclide) dài hay Module c a vectơ X ký hi u X ư c tính: T X = x .x Kho ng cách d và góc ϕ gi a hai vectơ: d = x − y = ( x − y) T .(x − y) xT.y = x . y . cos ϕ Hai vectơ x, y ư c g i là tr c giao v i nhau n u: x T.y = 0 M t t p h p các vectơ tr c giao v i nhau t ng ôi m t ư c g i là m t H tr c giao. M t ma tr n tr c giao s có các hàng và các c t là các vectơ tr c giao. nh lý: Các vectơ c a m t h tr c giao là c l p tuy n tính. Chu n c a vectơ, ký hi u là X , ư c nh nghĩa là m t s không âm, thõa mãn các tính ch t sau: 1. X ≥ 0 và X khi và ch khi X=0 2. αX = α . x v i m i α th c 3. X + Y ≤ X + Y b t ng th c tam giác Có 3 chu n sau ây hay s d ng trong các bài tóan ng d ng: V i vectơ X = [x 1 , x 2 ,..., x n ] T n X 1 = x 1 + x 2 +....+ x n = ∑x 1 i thư ng g i chu n tuy t i Bài Gi ng Chuyên Phương Pháp Tính Trang 39
  3. Khoa Xây D ng Th y L i Th y i n B môn Cơ S K Thu t n X 2 = x 2 1 + x 2 2 + ... + x 2 n = ∑x i =1 2 i g i là chu n Euclide X = maxi x i g i là chu n c c i. ∞ M r ng khái ni m cho chu n các ma tr n. Chu n c a các ma tr n A và B ký hi u là A và B ; ư c nh nghĩa là các s không âm thõa mãn các i u ki n sau: 1. A ≥ 0 và A = 0 khi và ch khi A = 0 2. αA = α . A v i m i α th c 3. A + B ≤ A + B 4. A • B ≤ A • B ây, nêu 3 nh nghĩa chu n hay dùng: A 1 = maxj ( ∑ a i j ) g i là chu n c t. i A 2 = ∑a i, j 2 ij g i là chu n Euclide. A ∞ = maxi( ∑ ai j ) g i là chu n hàng. j Chu n c a ma tr n là khái ni m h t s c quan tr ng i v i các phương pháp s . Chúng hay s d ng khi xét tính h i t c a các phương pháp l p ho c khi xét s n nh c a các h phương trình vi phân. Liên h chu n c a ma tr n và vectơ: Trong không gian n chi u V n chu n c a ma tr n tương ng v i chu n c a vectơ n u: A.X ≤ A . X v i m i A và X thu c Vn. 5.1.3 Các phép tính ma tr n V i ma tr n và cách i s hóa các vectơ ta có th nh nghĩa các phép tính m t cách hòan ch nh và y hơn. Ta nh c l i m t s phép tính cơ b n: Ma tr n B g i là ma tr n chuy n v c a A (AT=B), n u hàng c a ma tr n A là c t c a ma tr n B. [aji]= [b ij ]=> bij = aji m× n n× m Ma tr n ngh ch o: A-1 A.B = E => B = A-1 => A.A-1 = A-1.A = E (v i E là ma tr n ơn v ) Chú ý m t s tính ch t: A.B ≠ B.A (AT)T = A , (k.A)T = k.AT (A+B)T =AT+BT , (A.B)T = BT.AT (A-1)-1 = A , (A.B)-1 =B-1.A-1 T -1 -1 T (A ) = (A ) , det(A.B) = det(A).det(B) T det(A) = det(A ) Bài Gi ng Chuyên Phương Pháp Tính Trang 40
  4. Khoa Xây D ng Th y L i Th y i n B môn Cơ S K Thu t a11 0 0 −1 1 / a 11 0 0  0  0   a 22 0  =  0 1 / a 22  , 0  0 a 33    0  0 1 / a 33   • Ma tr n A là suy bi n, det (A)=0 thì các hàng ho c các c t c a nó là các vectơ ph thu c tuy n tính. • H ng c a ma tr n vuông A là s l n nh t các hàng (ho c các c t) c l p tuy n tính v i nhau. • Ma tr n B có ư c t ma tr n A b ng cách i ch hai hàng cho nhau thì: det(B) = - det(A). • N u A, B là các ma tr n vuông tr c giao thì AT, A-1, A.B cũng là các ma tr n tr c giao. • N u A, B là các ma tr n vuông i x ng thì α A, A+B cũng là nh ng ma tr n vuông i x ng. N u A không suy bi n thì A-1 cũng i x ng. C n chú ý r ng: Tích c a hai ma tr n i x ng nói chung không ph i là ma tr n i x ng. n N u A = [aij] là ma tr n vuông c p n tho a kk > ∑ a ks , v i s ≠ k, k=1...n , s =1 thì det(A) ≠ 0. Ma tr n A ư c g i là có ph n t trên ư ng chéo chính aii tr i. Hơn n a n u akk > 0, k=1,2,..,n thì det(A)>0 nh th c xác nh dương. 5.1.4 Vectơ riêng, tr riêng và các d ng toàn phương c a ma tr n Cho A là ma tr n vuông c p n; s λ ư c g i là tr riêng và vectơ khác không X là vectơ riêng c a A n u chúng thõa mãn i u ki n: A.X = λ .X hay (A- λ E).X = 0 => A − λ.E =0, Ta tìm ư c phương trình b c n cho λ , sao cho: f( λ ) = 0. f( λ ) ư c g i là a th c c trưng c a A có n tr riêng λ 1, λ 2,.., λ n . T p h p λ 1, λ 2,.., λ n ư c g i là ph và maxi ( λ i ) là bán kính ph c a ma tr n A. V i m i λ i có vô s X i. Các vectơ riêng cùng tương ng v i m t λ i rõ ràng là ph thu c tuy n tính và ch khác nhau m t h ng s α . Do ó ta có th ch n m t vectơ duy nh t làm cơ s . T p h p n vectơ riêng, ng v i n tr riêng khác nhau t o thành m t h vectơ c l p tuy n tính. Ma tr n g m các c t là các vectơ riêng c a ma tr n A, g i là ma tr n d ng riêng c a A. nh lý: • N u A là ma tr n th c, i x ng thì các tr riêng là th c. Các vectơ riêng ng v i các tr riêng khác nhau là các vectơ th c tr c giao và c l p tuýên tính. • N u A là ma tr n xác nh dương thì các giá tr riêng là nh ng s dương. nh lý Sylvester: Bài Gi ng Chuyên Phương Pháp Tính Trang 41
  5. Khoa Xây D ng Th y L i Th y i n B môn Cơ S K Thu t N u nh th c A và t t c các t th c n m trên ư ng chéo chính u là dương thì A là xác nh dương. T ng quát hơn, khái n êm xác nh dương c a ma tr n A ư c nh nghĩa nh d ng toàn phương là a th c: Q(X) = XT.A.X N u Q xác nh dương, t c Q(X) > 0 v i m i s th c X và Q(X) = 0 khi và ch khi X=0, thì A ư c g i là xác nh dương. 5.2 GI I H I TUY N Bài toán cơ b n: Cho h g m n phương trình i s tuy n tính v i n n: a11x1+ a12x2+...+ a1nxn = b1 a21x1+ a22x2+...+ a2nxn = b2 ... ... ... an1x1+ an2x2+...+ annx n = bn Vi t dư i d ng matrix: A.X = B G a thi t det(A) ≠ 0: H này có nghi m duy nh t. Ta có th tìm nghi m theo quy t c CRAMER ho c s d ng ma tr n ngh ch o nhưng cách n y òi h i phép tính khá l n và không thu n l i khi ma tr n A x u. Chúng ta ch nghiên c u các phương pháp tri n khai h u hi u trên máy tính. Có th phân lo i chúng thành hai nhóm chính: + Các phương pháp tr c ti p: Gauss, Gauss Jordan, phân tích LU,... + Các phương pháp l p: L p ơn, Jacobi, Gauss - Seidel, l p Gradient liên h p… 5.2.1 PHÂN TÍCH LU VÀ PHÂN TÍCH CHOLESKY Trong phép phân tích LU, ma tr n A có th phân tích: A = L.U V i L là ma tr n tam giác dư i, v i các ph n t n m trên ư ng chéo chính b ng 1, U là ma tr n tam giác trên. Phép phân tích LU này bao gi cũng th c hi n ư c n u các tr (các ph n t chính a11, a22, a33, ...) khác không. Nó s duy nh t n u các ph n t trên ư ng chéo chính c a ma tr n L b ng 1. V i phân tích LU vi c gi i h phương trình: A.X = b Tr thành gi i l n lư t hai h phương trình: Ly = b Và UX = Y Thu t gi i c a phép phân tích LU thư ng dùng là c a Crout. Trong trư ng h p ma tr n A là i x ng, khi ó phép phân tích tr nên ơn gi n hơn r t nhi u, không òi h i các ph n t trên ư ng chéo chính c a ma tr n L b ng 1 n a. Thay vào ó ta s d ng i u ki n: U = LT A = L.LT Bài Gi ng Chuyên Phương Pháp Tính Trang 42
  6. Khoa Xây D ng Th y L i Th y i n B môn Cơ S K Thu t Lúc ó L và U có các ph n t trên ư ng chéo chính gi ng nhau, các ph n t n y có th là th c hay ph c: và g i phép này là phân tích Cholesky. (chúng ta không i sâu vào thu t toán, vì nó ph c t p và ã có các source code listing ã công b trong nhi u n ph m khoa h c phương pháp s ). 5.2.2 PHƯƠNG PHÁP L P ƠN H PHƯƠNG TRÌNH Mô t phương pháp: Phương pháp Gauss thu c lo i phương pháp úng hay còn g i là phương pháp tr c ti p. Ngoài ra còn có 1 lo i phương pháp khác là phương pháp l p, ây ta xét phương pháp l p ơn, h cho d ng vector: Ax = f Ta chuy n h này v d ng tương ương: x = Bx + g b11 b12 K b1n b 21 b 22 K b 2 n Gi s : B= K K K K b n1 b n 2 K b nn Sau ó ta xây d ng công th c tính l p:  (m) x = Bx ( m −1) +g  ( 0) (5.2.1) x  n Trong ó: (Bx)i = ∑b x j=1 ij j , x(0) cho trư c. Phương pháp tính theo (5.2.1) g i là phương pháp l p ơn. S h it : Gi s α = (α1 , α2 , . . . . ., αn)T là nghi m c a h x = Bx + g , n u xi(m) → αi khi m → ∞ , v i i = 1, 2, 3 , . . . , n thì ta nói phương pháp l p (5.2.1) h i t . Ta ưa vào các ký hi u: z = ( z1 , z2 , . . . , zn )T thì m i i lư ng sau: z0 = max{z i }   z1 = z1 + z 2 + K + zn  z 2 = z1 + z 2 + K + z 2 2  2 n  G i là dài m r ng c a vector z, ngư i ta còn g i nó là chu n c a z. Bài Gi ng Chuyên Phương Pháp Tính Trang 43
  7. Khoa Xây D ng Th y L i Th y i n B môn Cơ S K Thu t  n r0 = max ∑ b ij i  j=1   n r1 = max ∑ b ij j i v i ma tr n B = ( bi j), ta t:  i =1  n n  r2 = ∑ .∑ b ij   i =1 j=1 Ngư i ta ch ng minh ư c nh lý sau ây v i u ki n h i t : + N u r0 < 1 ho c r1 < 1 ho c r2 < 1 thì phương pháp l p (5.2.1) h i t v i b t kỳ x p x ban u x(0) nào, ng th i ta có sai s ánh giá: rm  x ( m ) − α ≤ P x (1) − x ( 0)  P 1 − rP P  m  (m) rP (m) ( m −1)  x −α ≤ x −x 1 − rP P  P Trong ó: p = 0 n u r0 < 1, p = 1 n u r1 < 1, p = 2 n u r2 < 1. 5.2.3 PHƯƠNG PHÁP L P SEIDEN (hay còn g i là GAUSS-SEIDEN) Là phương pháp c i ti n phương pháp l p ơn m t chút: khi tính x p x th (k+1) c a n x i ta s d ng các x p x th (k + 1) ã tính c a n x 1 , . . . , xi -1 . n Gi s cho h : A x = b ⇔ xi = βi + ∑α j =1 ij x j v i i = 1, 2,. . . , n L y x p x ban u là x1(0) , x2(0) , . . . , xn(0) Ti p theo, gi s ta ã bi t x p x th k là xi(k) theo Seiden, ta s tìm x p x th ( k+1) c a nghi m theo công th c:  ( k +1) n  x1 = β1 + ∑ α1 j x (jk )  j =1  ( k +1) n  x2 = β 2 + α 21 x1 + ∑ α 2 j x j ( k +1) (k )  j =2    i −1 n  xi( k +1) = β i + ∑ α ij x (jk +1) + ∑ α ij x (jk )  j =1 j =i  n−1  x ( k +1) = β + α x ( k +1) + α x ( k )  n n ∑ ij j nn n  j =1 (Thông thư ng l p Seiden h i t nhanh hơn l p ơn) Bài Gi ng Chuyên Phương Pháp Tính Trang 44
  8. Khoa Xây D ng Th y L i Th y i n B môn Cơ S K Thu t Ví d : Tìm nghi m g n úng c a h phương trình sau b ng phương pháp l p ơn. 4 x1 + 0,24 x 2 − 0,08 x3 = 8  0,09 x1 + 3 x2 − 0,15 x3 = 9 0,04 x − 0,08 x + 4 x = 20  1 2 3 Gi i: H phương trình ã cho có d ng ư ng chéo tr i, d dàng ưa v d ng X= αX + β ; Trong ó: 0 − 0,06 0,02  2 − 0,03 0 α =  ; β = 3  0,05   − 0,01 0,02 0    5    α x = 0,08 < 1 quá trình l p Seiden h i t Ch n x p x u X0= β =(2,3,5) K X1 X2 X3 0 2 3 5 1 1,92 3,1924 5,044648 2 1,9093489 3,194952 5,0448056 3 1,909199 3,1949643 5,0448073 5.2.4 PHƯƠNG PHÁP GRADIENT LIÊN H P (Conjugate gradient method) Phương pháp này r t thích h p v i bài toán ph thu c th i gian. gi i h phương trình: ∑ {P(I, J ) × F(J )} = G(I) Gía tr ban u ư c lư ng là: F0(J) gây ra ph n dư U(I), ta bi u di n: U(I) = G(I) - ∑ {P(I, J ) × FO (J )} . t: V(I) = U(I) UU = ∑ {U(I).U(I)} Vòng l p: W(I) = ∑ {P (I, J ).V (J)} VW = ∑ {V (I).W (I)} AA = UU/VW F(I) = F(I) + AA.V(I) U(I) = U(I) - AA.W(I) WW = ∑ {U(I).U(I)} BB = WW/UU V(I) = U(I) + BB.V(I) UU = WW UU ≤ ε ? Qúa trình này ư c l p l i mãi n khi UU ≤ ε (sai s cho phép c a bài toán) thì d ng. Bài Gi ng Chuyên Phương Pháp Tính Trang 45
  9. Khoa Xây D ng Th y L i Th y i n B môn Cơ S K Thu t Câu h i: 1. Hãy cho ví d v bài toán nào ó trong th c t k thu t có ma tr n thưa (d ng BAND hay d ng b t kỳ) ? 2. Hãy trình bày m t thu t toán lưu tr ti t ki m b nh trong máy tính và gi i nó khi ma tr n thưa ? 3. Hãy cho m t ví d c th v ma tr n A xác nh dương ? 4. Hãy nêu ưu như c i m c a các phương pháp gi i h i tuy n (tr c ti p và l p) ? Bài t p: 1) Gi i h phương trình: − 8 1 1  1  1  X= 16 −5 1     1  1 − 4  7    a) B ng phương pháp l p ơn b) B ng phương pháp l p Day en. ( i v i m i phương pháp, tính n X3 v i X0 = β ) 2) Gi i h phương trình: 24,21x1 + 2,42 x2 + 3,85 x3 = 30,24  2,31x1 + 31,49 x 2 + 1,52 x3 = 40,95 3,49 x + 4,85 x + 28,72 x = 42,81  1 2 3 B ng phương pháp l p ơn, tính cho t i khi -4 X k − X k −1 ≤ 10 3) Gi i h phương trình sau b ng phương pháp l p ơn sao cho X k − X k −1 ≤ ε là s dã cho trư c. 1,02 − 0,25 − 0,30  0,515  − 0,41  X= 1,555  ; ε = 10 −3 1,13 − 0,15     − 0,25  − 0,14 1,21 2,780   áp s :  x1 = −0,9618359 1) a)  x2 = −3,9448436   x = −2,9398827  3  x1 = −0,9922021 b)  x2 = −3,9937418   x = −2,9964857  3 Bài Gi ng Chuyên Phương Pháp Tính Trang 46
  10. Khoa Xây D ng Th y L i Th y i n B môn Cơ S K Thu t  x1 = 0,9444  -4 2)  x 2 = 1,1743 X k − X k −1 ≤ 0,5.10  x = 1,1775  3 3) X=(2,0; 2,5; 3) TÀI LI U THAM KH O 1. Ph m Kỳ Anh, Gi i tích s , NXB HQG, Hà N i 1996 2. Phan V ăn H p, Các phương pháp gi i g n úng, NXB H-THCN, Hà N i 1981. 3. Nguy n Th Hùng, Giáo trình Phương pháp s , i h c à N ng 1996. 4. Nguy n Th Hùng, Phương pháp ph n t h u h n trong ch t l ng, NXB Xây D ng, Hà N i 2004. 5. inh Văn Phong, Phương pháp s trong cơ h c, NXB KHKT, Hà N i 1999. 6. Lê Tr ng Vinh, Gi i tích s , NXB KHKT, Hà N i 2000. 7. BURDEN, RL, & FAIRES, JD, Numerical Analysis, 5th ed., PWS Publishing, Boston 1993. 8. CHAPRA S.C, Numerical Methods for Engineers, McGraw Hill, 1998. 9. GURMUND & all, Numerical Methods, Dover Publications, 2003. 10.HOFFMAN, J., Numerical Methods for Engineers scientists, McGrawHill, Newyork 1992. 11.JAAN KIUSAALAS, Numerical Methods in Engineering with Mathlab, Cambridge University Press, 2005. 12.OWEN T. et al., Computational methods in chemical engineering, Prentice Hall, 1995. 13.STEVEN T. KARRIS, Numerical Analysis, Using Matlab and Excell, Orchard Publications, 2007. Website tham kh o: http://ocw.mit.edu/index.html http://ebookee.com.cn http://www.info.sciencedirect.com/books http://db.vista.gov.vn http://dspace.mit.edu http://ecourses.ou.edu http://www.dbebooks.com The end Bài Gi ng Chuyên Phương Pháp Tính Trang 47
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí
65 tài liệu
2431 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2