Phương pháp tính_Chương 1+2

Chia sẻ: Hoàng Danh Long | Ngày: | Loại File: PPT | Số trang:85

Thêm vào BST

Báo xấu

405
lượt xem 157
download

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

Chương 1: Một số phương pháChương 1: Một số phương pháp tính toán trong đại số tuyến tính. Định lý: nhân 1 hàng hoặc 1 cột của ma trận A với 1 số khác 0, sau đó đem cộng các thành phần tương ứng vào một hàng hoặc một cột khác của ma trận đó thì giá trị của định thức không thay đổi

Chủ đề:

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

Lưu

Nội dung Text: Phương pháp tính_Chương 1+2

Phương pháp tính 1
Chương 1: Một số phương pháp tính toán trong đại số tuyến tính 1.1. Ma trận và định thức 1. Định thức của một ma trận  a11 a12 ... a1n  a a22 ... a2n  Ma trận A= (1.1)  21   . . ... .     am1 a m 2 ... amn  n ∑ aij Aij det A= , với j bất kỳ, 1 ≤ j ≤ n (1.2a) i =1 n det A= , với i bất kỳ, 1 ≤ i ≤ n (1.2b) ∑ aij Aij j =1 2
• Định lý: nhân 1 hàng hoặc 1 cột của ma trận A với 1 số khác 0, sau đó đem cộng các thành phần tương ứng vào một hàng hoặc một cột khác của ma trận đó thì giá trị của định thức không thay đổi b11 b12 ... b1n  B = (1.3)   0 b22 ... b2 n    . . ... .    0 0 ... bnn  Áp dụng CT (1.2a) với j = 1 ta được det A = det b22 b23 ... b2n  b11 0 b33 ... b3n     . . ... .    0 0 ... bnn  Tiếp tuc ⇒det A = det b33 b34 ... b3n  b11 b22 0 b  44 ... b4n    . . ... .    0 0 ... bnn  = det = −1,n  bn −1, n −1 bn b11...bn − 2, n − 2  0  bn, n   b11...bn, n 3
Các bước chuyển từ ma trận A về ma trận B Xét 2 hàng đầu của ma trận A : a11 a12 ... a1n a21 a22 ... a2 n Nhân hàng đầu với 1 số rồi cộng kết quả đó vào hàng thứ 2 sao cho b21= 0 a21a11 a21 / a11 − b21 = a21 ( ≠ 0) ⇒ số đó là – = 0 a11 a11 • Các thành phần còn lại của hàng thứ 2 sẽ là: a a , j = 1,2,…n b2 j = a2 j − 21 1 j a11 • Tiếp tục với hàng thứ 3, 4, …cho đến hàng thứ i a a , j = 1,2,…n (1.4) bij = aij − i1 1 j a11 4
• Theo (1.2), với j = 1 b22 b23 ... b2 n  a11 a12 ... a1n  b b33 ... b3n  0 b   32  det A = ⇒ det A = det 22 ... b2 n  a11  . . ... .    . . ... .      bn 2 bn3 ... bnn   0 0 ... bnn  b22 b23 ... b2 n  b22 b23 ... b2 n  0 b c33 ... c3n  b ... b3n  Lặp lại với ⇒ det A = a11 det    32 33   . . ... .   . . ... .      0 cn3 ... cnn  bn 2 bn3 ... bnn  bi 2b2 j ở hàng thứ i: cij = bij − , j = 2,.., n b22 bij , cij Thay cho ký hiệu và công thức (1.4) ta dùng aill −1) aljl −1) ( ( aijl ) = aijl −1) − ( ( , a1 0) = a1 ( (1.5) j j alll −1) ( l = 1,2,.., n; i = l + 1,..., ; j = i + 1,..., n 5
a11 a12 ... a1n   0 a (1) ... a21)  ( ⇒ det A = det  22 n  = a11 ) × a22) × ... × ann−1) (0 (1 (n  . . ... .    0 0 ... ann−1)  (n 6
2. Ma trận nghich đảo 1là ma trận nghich đảo của ma trận A A− ⇔ A−1 A = AA−1 = 1 Cách tìm mt nghich đảo C1: tính giá trị phần bù đại số , i,j=1,2,…,n Aij  A11 A21 ... An1   ... An 2  −1 1  A12 A22  A = det A  . . ... .  (1.6)    A1n A2 n ... Ann  C2: Viết thêm mt I vào bên phải ma trận A  a11 a12 ... a1n 1 0 ... 0 a  21 a22 ... a2 n 0 1 ... 0 [ A, I ] =   . (1.7) . ... . . . ... .     an1 an 2 ... ann 0 0 ... 1 7
1 0 ... 0 c1, n +1 c1, n + 2 ... c1, 2 n  0 1 ... 0 c  Sau khi biến đổi (1.8)c2, 2 n  c2, n + 2 ... [ A, I ] =  2, n +1  . . ... . . . ... .     0 0 ... 1 cn, n +1 cn, n + 2 ... cn, 2 n   c1, n +1 c1, n +1 ... c1, 2 n  c ... c2, 2 n  −1  2, n +1 c2, n + 2  A =  . . ... .    cn, n +1 cn, n + 2 ... cn, 2n  cij Cách tìm ta áp dụng công thức (1.5) B1: chia hàng đầu của (1.7) cho a11  1 a12 / a11 ... a1n / a11 1 / a11 0 ... 0 a a22 ... a2 n 0 1 ... 0 [ A, I ] =  21   . . ... . . . ... .     an1 an 2 ... ann 0 0 ... 1 8
B2: nhân hàng 1 với rồi cộng vào hàng 2 ⇒ − a21 a21j) = a2 j − a21 / a11 ( j=2,3,…,n+1 Tiếp tục áp dụng với hàng thứ l Vậy có 2 bước tìm mt nghich đảo aljl −1) ( alll −1) Với mỗi hàng thứ l, chia tất cả cho ,j=l,…,n+l ( aijl −1) ( Với mỗi i=1,2,…,n; i ≠ l ta thay bằng aill −1) aljl −1) ( ( aijl ) = aijl −1) − ( ( , l = l ,.., n + l alll −1) ( −1 aljl ) = aljl −1) / alll −1) ( ( ( ⇒ Tìm trở thành tìm (1.9) A 9
1.2. Hệ phương trình đại số tuyến tính Công thức Kramer a11x1 + a12 x2 + ... + a1n xn = b1 Cho hệ pt sau: a21x1 + a22 x2 + ... + a2 n xn = b2 .......... .......... .......... .......... ...... (1.10) an1x1 + an 2 x2 + ... + ann xn = bn Hệ pt này có thể viết dưới dạng:  a11 a12 ... a1n   x1   b1  a a22 ... a2 n  x  b   21   2  2 A= x= b=  . . ... .  . .        an1 a n 2 ... ann   xn  bn  det A≠ 0 thi (1.10) có nghiệm tính theo CT x = A−1b b1 A11 + b2 A21 + ... + bn An1 x1 = det A b A + b A + ... + bn An 2 x2 = 1 12 2 22 det A .......... .......... .......... .......... ....... b1 A1n + b2 A2 n + ... + bn Ann xn = 10 det A
Có thể viết cách khác:  b1 a12 ... a1n   ... a2 n  1 b2 a22  x1 = det A  . . ... .    bn an2 ... ann   a11 a12 ... a1, j −1 b1 a1, j +1 ... a1n   a2, j +1 ... a2 n  1 a21 a22 ... a2 n b2  xj = det A  . . ... . . . ... .     an1 a n 2 ... an, j −1 bn an, j +1 ... ann   a11 a12 ... a1, n −1 b1  a ... a2, n −1 b2  1  21 a22  xn = det A  . . ... . .    an1 a n 2 ... an, n −1 bn  11
1. Phương pháp trực tiếp a) Phương pháp khử dùng ma trận nghịch đảo Ý tưởng: Thêm ma trận I vào bên phải của ma trận A ta được ma trận [A,I] dạng (1.7). Áp dụng các phép biến đổi sơ cấp lên các hàng của ma trận [A,I] cho đến khi [A,I] ở dạng (1.8). Khi đó nghiệm của phương trình (1.10): x1 = b1c1, n +1 + b2c1, n + 2 + ... + bnc1, 2 n x2 = b1c2, n +1 + b2c2, n + 2 + ... + bnc2, 2 n .......... .......... .......... .......... .......... ...... x1 = b1cn, n +1 + b2cn, n + 2 + ... + bncn, 2 n n xi = ∑ ci , n + j b j ,i = 1,2,..., n ⇒ j =1 12
b) Phương pháp khử Gauss Cho hệ pt đại số tuyến tính sau: a11x1 + a12 x2 + ... + a1n xn = a1, n +1 a21x1 + a22 x2 + ... + a2n xn = a2, n +1 (1.11) .......... .......... .......... .......... ...... an1x1 + an 2 x2 + ... + ann xn = an, n +1 G/sử ta áp dụng CT (1.5) cho TH l=1 lên (1.11) ta được a11 ≠ 0 a11x1 + a12 x2 + ... + a1n xn = a1, n +1 a (1) x2 + ... + a (1 xn = a (1) 2 , n +1 (1.12) 22 2n .......... .......... .......... ......... a (1) x2 + ... + a (1) xn = a (1) n2 nn n , n +1 Tiếp tục, nếu thì (1.12) được đưa về dạng (1) a22 ≠ 0 a11x1 + a12 x2 + a13 x3 + ... + a1n xn = a1, n +1 a (1) x2 + a (1) x3 + ... + a (1) xn = a (1) 22 23 2n 2 , n +1 a ( 2) x3 + ... + a ( 2) xn = a ( 2) 33 3n 3 , n +1 .......... .......... .......... .......... ... a ( 2) x3 + ... + a ( 2) xn = a ( 2) 13 n3 3n 3 , n +1
Tiếp tục cho đến n1 lần: a11x1 + a12 x2 + a13 x3 + ... + a1n xn = a1, n +1 a (1) x2 + a (1) x3 + ... + a (1) xn = a (1) 22 23 2n 2 , n +1 a ( 2) x3 + ... + a ( 2) xn = a ( 2) 33 3n 3 , n +1 .......... .......... .......... .......... ... a ( n −1) xn = a (n) nn n , n +1 Nghiệm của hệ pt là: ( −1) annn +1 , xn = ann−1) (n n 1 xi = aiii −1) ( ( i −1) (a i , n +1− ∑ aiji −1) x j ) ( (1.14) j = i +1 j = n − 1,...,1 14
c) Phép khử Jordan Tương tự phép khử Gauss chỉ khác là ở bước thứ l các thành (l −1) all phần bên trên và bên dưới đều được đưa về 0. Kết quả ta có hệ pt aiii −1) xi = ai(,n −1) ( n +1 ⇒ Nghiệm của hệ pt là: ai(,n −1) n +1 xi = aiii −1) ( 15
d) Phương pháp Cholesky (giải pt 1.10) Đk:  a11 a12 a13   a11 a12  a11 ≠ 0 det  ≠ 0 ; det a21 a22 a23  ≠ 0 ... det A ≠ 0 a21 a22      a31  a32 a33   Ma trận A=LU 1 0 0 ... 0 u11 u12 u13 ... u1n  l 0 ... 0 0 u ... u2 n   21 1   22 u23  L = l31 l32 1 ... 0 U = 0 0 u33 ... u3n  Ma trận ; Ma trận      . . . ... .   . . . ... .  ln1 ln 2 ln3 ... 1   0  0 0 ... unn  Đặt Ux=y ⇒ Ly=b. Do đó ta có 2 hệ pt cần giải 16
1 0 0 ... 0  y1  b1  Hệ thứ nhất: l 1 0 ... 0  y  b   21   2  2 l31 l32 1 ... 0 ×  y3  = b3        . . . ... .  ..  ..  ln1 ln 2  ln 3 ... 1  yn  bn      nghiệm của hệ này là: y1 = b1 i −1 yi = bi − ∑ lij y j i = 2,3,..., n j =1 Hệ thứ 2: u11 u12 u13 ... u1n   x1   y1  0 u u23 ... u2 n  x   y   22   2  2 0 0 u33 ... u3 n  ×  x3  =  y3         . . . ... .  ..  ..  0  0 0 ... unn   xn   y n      nghiệm của hệ này là: xn = yn / unn n 1 xi = ( yi − uii ∑ uij x j ) i = 2,3,..., n j = i +1 17
 Tìm lij , uij 1 0 0 ... 0 u11 u12 u13 ... u1n   a11 a12 ... a1n  LU=A ⇔ x = l 0 ... 0  0 u22 u23 ... u2 n  a ... a2 n  1  21    a22 l31 l32 1 ... 0  0 0 u33 ... u3n   21       . . ... .  . . . ... .   . . . ... .    ln1 ln 2 ln3 ... 1  0    0 0 ... unn   an1 a n 2 ... ann  Nhận thấy u1 j = a1 j , j = 1,2,..., n Cột thứ nhất của L: li1u11 = ai1 , i = 2,3,..., n ⇒ li1 = ai1 / u11 Hàng thứ 2 của U: l21u1 j + u2 j = a2 j ⇒ u2 j = a2 j − l21 u1 j i = 2,3,..., n Cột thứ 2 của L: 1 li1u12 + li 2u22 = ai 2 ⇒ li 2 = ( ai 2 − li1u12 ) i = 3,4,..., n u22 18
Hàng thứ i của U và cột thứ j của L i −1 uij = aij − ∑ lik ukj i≤ j k =1 j −1 1   lij =  aij − ∑ lik ukj  i> j uij   k =1   19
2. Phương pháp lặp -Tính chéo trội: n aij > ∑ aij i = 1,2,...n j =1, j ≠ i a) Phương pháp lặp Gauss-Seidel Cho hệ phương trình Biến đổi x1 = (−a12 / a11 ) x2 + (− a13 / a11 ) x3 + ... + (−a1n / a11 ) xn + a1n +1 / a11 x2 = (− a21 / a22 ) x1 + (−a23 / a22 ) x3 + ... + (− a2 n / a22 ) xn + a2 n +1 / a11 .......... .......... .......... .......... .......... .......... .......... .......... ........ xn = (− an1 / ann ) x1 + (−an 2 / ann ) x2 + ... + (− an, n −1 / ann ) xn −1 + ann +1 / ann 20