Bài giảng Phương pháp số trong tính toán cơ khí - Bài 3: Hệ Phương trình Đại số Tuyến tính - Trường Đại học Công nghệ Thành phố Hồ Chí Minh

x =( xxx1,,,, 2 3 x n ) = ? Ôn tập về ma trận 4 Cột 3 a11 a 12 a 13⋯ a 1 m    a a a a Hàng 2 A = 21 22 23 2 m  n× m   ⋮ ⋮    an1 a n 2 a n 3 ⋯ a nm  Ôn tập về ma trận 5 1) Ma trận hàng: 2) Ma trận cột: B = [bbb1 2 3 b m ] c1  1×m c  2  3) Ma trận vuông: n=m C = c3  n×1   ⋮  aaa11 12 13⋯ a 1 n    c  aaa a n  A = 21 22 23 2 n  n× n ⋮ ⋮    aaan1 n 2 n 3 ⋯ a nn  Ôn tập về ma trận 6 4) Ma trận đối xứng: aij = aji 6) Ma trận đơn vị: 5− 1 7 1 0 0 0        0 1 0 0 A = − 1 2 4 I =   3× 3   n× n 0 0⋱ 0  7 4 6      0 0 0 1  5) Ma trận đường chéo: 7) Ma trận tam giác trên a a a a  a11 0 0 0  11 12 13 14     0a 0 0 0 a22 a 23 a 24 A = 22  A =   4× 4 n× n 0 0⋱ 0  0 0 a33 a 34      0 0 0 0 0 0 ann  a44  Ôn tập về ma trận 7 8) Ma trận tam giác dưới: a11 0 0 0  a a 0 0  A = 21 22  4× 4 a31 a 32 a 33 0    a41 a 42 a 43 a 44  9) Ma trận dải: a11 a 12 0 0  a a a 0  A = 21 22 23  4× 4 0 a32 a 33 a 34    0 0 a43 a 44  Ôn tập về ma trận 8 1) Cộng ma trận: aa11 12 a 1m  bb 11 12 b 1 m  abab 11+ 11 12 + 12 ab 1m + 1 m  aa a  bb b  abab+ + ab +  21 22 2m + 21 22 2 m  = 21 21 22 22 2m 2 m  ⋮⋮⋮⋮   ⋮ ⋮      aann12 a nm  bb nn 12 b nm  abab nnnn 1122+ + ab nmnm +  2) Tính chất giao hoán cộng: ABBA+ = + n× m n × m n × m n × m 3) Tính chất kết hợp cộng: ABCABC+ + = + + ( nmnm××) nm× nm ××( nm nm × ) Ôn tập về ma trận 9 aa11 12 a 1m  gaga⋅ 11 ⋅ 12 ga ⋅ 1 m  4) Nhân cho số thực: aa a  gaga⋅ ⋅ ga ⋅  g ⋅21 22 2m  = 21 22 2 m  ⋮⋮  ⋮ ⋮     aann12 a nm  gaga⋅ n 12 ⋅ n ga ⋅ nm  5) Nhân hai ma trận: a11 a 12 a 1 m  bb11 12 b 1p  cc 1112 c 1 p      a a a  bb b cc c 21 22 2 m  ⋅21 22 2p  = 2122 2 p  ⋮ ⋮  ⋮ ⋮  ⋮ ⋮  ABC⋅ = ⇔      n× m m × p n× p bb b cc c an1 a n 2 a nm  mm12 mp  nn 12 np   n  cij= ∑ a ik b kj  k=1 Ôn tập về ma trận 10 6) Tính chất kết hợp nhân: ABCABC⋅ ⋅=⋅ ⋅ ( nmmp××) pq× nmmp ××( pq × )  ABCABAC⋅ + =⋅+⋅ 7) Tính chất phân phối: nmmp××( mp×) nmmpnm ××× mp ×   ABCACBC+ ⋅ =⋅+⋅ ()nmnm××mp× nm × mp × nm × mp × Ôn tập về ma trận 11 8) Định thức: a11 a 12  a. Bậc 2: AA= ⇒det =aa11 22 − aa 12 21 22×  () 22 × a21 a 22  b. Bậc 3: Ôn tập về ma trận 12 9) Ma trận ngược:   detA det  A  det  A   11  21   31   a22− a 12  22×  22 ×   22 ×  a a a      11 12 13 1 a11 a 12  −1 −a21 a 11    −1         A=a21 a 22 a 23 ⇒ A = det AAA12  det  22  det  32  A=  ⇒ A = 33×   33×   22×a a 22 × det A 22×   22 ×  2× 2  21 22  det A a a a  ()3× 3   ()2× 2 31 32 33  detA det  A det  A  13  23  33   22×  22 ×  22 ×  aa   aa   aa  AAA=22 32 = 32 12 = 12 22 10) Tính chất Ma trận ngược: 11  21   31   22×aa23 33  22 ×  aa 33 13 2× 2  aa 13 23  aa23 33   aa 33 13  a13 a 23  −1 − 1 AAA12=  22 =   32 =   AA⋅ = A ⋅ A = I 22×aa21 31  22 ×  aa 31 11  2× 2 a11 a 21  nnnn×× nnnn ×× nn × aa21 31   aa 31 11  a11 a 21  AA13=  23 =   A33 =   22×aa22 32  22 ×  aa 32 12  2× 2 a12 a 22  Phát biểu bài toán ở dạng ma trận 13 axax111+ 122 + ax 133 ++ ax 1n n = b 1 aaa11 12 13 a 1 n  x1   b 1         axaxax211222+ + 233 ++ axb 2n n = 2 aaa 21 22 23 a 2n  x 2   b 2   ⇔  ⋅  =   ⋮ ⋮ ⋮ ⋮  ⋮   ⋮         axaxaxn11+ n 22 + n 33 ++ ax nnnn = b aaan1 n 2 n 3 a nn  xn   b n  ⇔A ⋅ x = b (2) n× n n × 1 n×1 Nhân hai vế của (2) cho ma trận ngược của ma trận A: ()2 ⇔AAxAb−1 ⋅⋅= − 1 ⋅⇔( AAxAb − 1 ⋅⋅=) − 1 ⋅ nnnnn××××1 nnn×1 nnnnn ×××× 1 nn n × 1 I n× n ⇔⋅=⋅IxAb−1 ⇔ xAb =⋅ − 1 (3) nnn×××1 nnn×1 n ×× 1 nn n × 1 x n×1 Hệ phương trình ít ẩn (≤3) 14 Hệ 2 phương trình Ví dụ: ax11 1+ ax 12 2 = b 1 3x+ 2 x = 18  1 2 ax+ ax = b   211 222 2 −x1 +2 x 2 = 2 ⇓ ⇓  a  b  3 11 1 x2= − x 1 + 9 x2= −  x 1 +  2 a12 a 12     1  x= x + 1 a  b 2 1 x= −21 x + 2  2  2  1  a22  a 22 f1 = @(x,y) 3*x + 2*y - 18; f2 = @(x,y) -x + 2*y - 2; fimplicit(f1,[0 6 0 9], 'm-','Linewidth' ,2),grid on hold on fimplicit(f2,[0 6 0 9], 'k-','Linewidth' ,2),grid on Hệ phương trình ít ẩn (≤3) 15 ax111+ ax 122 = b 1 Các tình huống nghiệm:  ax211+ ax 222 = b 2 a a b a a b a a 11= 12 ≠ 1 11= 12 = 1 11≠ 12 a21 a 22 b 2 a21 a 22 b 2 a21 a 22 Hai đường thẳng song song Hai đường thẳng trùng nhau Hai đường thẳng cắt nhau
Vô nghiệm
Vô số nghiệm
Một nghiệm Hệ phương trình ít ẩn (≤3) 16 4x1+ x 2 − x 3 =− 2 Hệ 3 phương trình  5x1+ x 2 + 2 x 3 = 4 ax+ ax + ax = b 111 122 133 1 6x+ x + x = 6   1 2 3 ax211+ ax 222 + ax 233 = b 2  ax31 1+ ax 32 2 + ax 33 3 = b 3 Ba mặt phẳng f1 = @(x,y,z) 4*x + y - z + 2; f2 = @(x,y,z) 5*x + y + 2*z - 4; f3 = @(x,y,z) 6*x + y + z - 6; interval = [0 10 -15 -10 -5 5]; fimplicit3(f1,interval, 'FaceColor' ,'m' ,'EdgeColor' ,'k' ,'FaceAlpha' ,.9), hold on fimplicit3(f2,interval, 'FaceColor' ,'g' ,'EdgeColor' ,'k' ,'FaceAlpha' ,.9), hold on fimplicit3(f3,interval, 'FaceColor' ,'y' ,'EdgeColor' ,'k' ,'FaceAlpha' ,.9), hold on scatter3(3,-13,1,100, 'filled' ,'MarkerEdgeColor' ,'k' ,'MarkerFaceColor' ,[0 .75 .75]) (3;− 13;1 ) aaa11 12 13 a 1 n 17 Quy tắc Cramer aaa a D = 21 22 23 2 n ⋮ ⋮ ⋮⋮ ⋮ aaa11 12 13 ab 1n 1    aaan1 n 2 n 3 a nn aaa21 22 23 ab 2 2 A b  = n  baa a     1 12 13 1 n n×() n + 1 ⋮ ⋮ ⋮ ⋮ ⋮⋮   baa2 22 23 a 2 n aaa ab Dx = n1 n 2 n 3 nn n  1 ⋮ ⋮ ⋮ ⋮ ⋮ D  xi 1) Vô nghiệm: baan n2 n 3 a nn xi = D = 0 ; D aba a  11 1 13 1 n  Dx ≠0; i = 1.. n i=1.. n  i aba a  D = 21 2 23 2 n 2) Vô số nghiệm: x2 ⋮ ⋮ ⋮ ⋮ ⋮ D = 0 aban1 nn 3 a nn  D=0; i = 1.. n  xi 3) Một nghiệm: aaa11 12 13 b 1 aaa b D = 21 22 23 2 D ≠ 0 xn ⋮ ⋮ ⋮ ⋮⋮ aaannn1 2 3 b n Quy tắc Cramer 18 4 1− 1 D =512 = 4 6 1 1 −2 1 − 1 D x =x1 = 3 D =4 1 2 = 12 1 x1 D 4x1+ x 2 − x 3 =− 2  6 1 1 D 5 2 4 x2  x1+ x 2 + x 3 = x2 = = − 13  4− 2 − 1 D 6x1+ x 2 + x 3 = 6 Dx =5 4 2 = − 52 D 2 x =x3 = 1 6 6 1 3 D 4 1− 2 D =514 = 4 x3 6 1 6 Tính định thức bằng MATLAB 19 format long D = [4 1 -1; 5 1 2; 6 1 1] D_x1 = [-2 1 -1; 4 1 2; 6 1 1] D_x2 = [4 -2 -1; 5 4 2; 6 6 1] D_x3 = [4 1 -2; 5 1 4; 6 1 6] det_D = det(D) det_Dx1 = det(D_x1) det_Dx2 = det(D_x2) det_Dx3 = det(D_x3) x1 = det(D_x1)/det(D) x2 = det(D_x2)/det(D) x3 = det(D_x3)/det(D) Các phương pháp để giải hệ phương trình tuyến tính 20 Đưa hệ PT (2) về dạng tương - Phương pháp đương đơn giản hơn: Jacobi - Ma trận tam giác trên Phương pháp khử - Phương pháp - Ma trận tam giác dưới Gauss Gauss-Seidel - Ma trận đường chéo Phương pháp khử Gauss-Jordan Các phương pháp trực tiếp (Direct Methods) 21 Ví dụ hệ 4 PT-4 ẩn Tổng quát: a11 a 12 a 13 a 14  x1   b 1  axax111+ 122 + ax 133 ++ ax 1n n = b 1        0 a22 a 23 a 24 x2   b 2  axax+ ++ ax = b   ⋅  =    222 233 2n n 2 0 0 a33 a 34  x3 b 3       ax333+ + ax 3n n = b 3       0 0 0 a44  x4   b 4    ⋮ ⋮ ⋮ b 4  x4 = ; annn−−−1, 1 x 1+ axb nnn − 1, = n − 1 a44  a x= b b− a x  nnn n x = 3 34 4 ; 3 a b 33 x = n ; n a b2−() ax 23 3 + ax 24 4 nn x = ; 2 j= n a22 bi− ∑ a ij x j b1−() ax 12 2 + ax 13 3 + ax 14 4 j= i + 1 x1 = x=; inn =−− 1, 2, ,1 a i 11 aii Các phương pháp trực tiếp (Direct Methods) 22 Ví dụ hệ 4 PT-4 ẩn Tổng quát: 0 0 0 x b a11  1   1  a11 x 1 = b 1 0 0  x   b   a21 a 22 2   2  axax+ = b   ⋅  =    12 1 22 2 2 a a a 0  x b  31 32 33 3   3  axaxax+ + = b        311 322 333 3 a41 a 42 a 43 a 44  x4   b 4   ⋮ ⋮ ⋮ b1  x1 = ; axaxn11+ n 22 + ax n 33 ++ ax nnnn = b a11  b− a x b x = 2 21 1 ; x = 1 ; 2 a 1 22 a11 b3−() ax 31 1 + ax 32 2 j= i − 1 x = ; 3 b− a x a33 i∑ ijj x=j=1 ; i = 2,3, , n b4−() ax 41 1 + ax 42 2 + ax 43 3 i x4 = aii a44 Các phương pháp trực tiếp (Direct Methods) 23 Ví dụ hệ 4 PT-4 ẩn Tổng quát: a11 0 0 0  x1   b 1        a11 x 1 = b 1 0a22 0 0 x2   b 2    ⋅  =    0 0a 0  x b a22 x 2= b 2 33 3   3         0 0 0 a44  x4   b 4   a33 x 3= b 3  b1 ⋮ ⋮ ⋮ x1 = ;  a11  ann x n= b n b2 x2 = ; a22 bi b3 x = ; xi =; i = 1.. n 3 a a33 ii b4 x4 = a44 Các phương pháp trực tiếp (Direct Methods) 24 aaa11 12 13 a 1 n  x1   b 1        aaa21 22 23 a 2n  x 2   b 2  A⋅=⇔ x b   ⋅=    n× n n × 1 n×1 ⋮ ⋮  ⋮   ⋮        aaan1 n 2 n 3 a nn  xn   b n  aaa11 12 13 ab 1n 1    aaa ab A b  = 21 22 23 2n 2    ⋮ ⋮ ⋮ ⋮ ⋮⋮  n×() n + 1   aaan1 n 2 n 3 ab nn n  Các phương pháp trực tiếp (Direct Methods) 25 Quá trình aaa11 12 13 ab 1n 1  aaa11 12 13 ab 1n 1    xuôi   aaa21 22 23 ab 2n 2 0 aa′′ ab ′′ A b  =   22 23 2n 2      n×() n + 1 ⋮ ⋮ ⋮ ⋮ ⋮⋮ ⋮ ⋮ ⋮ ⋮ ⋮⋮      aaan1 n 2 n 3 ab nn n  0 0 0 ′ ′    ann b n   j= n ′ ′  bi− a ij x j b′ ∑ x=n ; x =j= i + 1 ; inn =−− 1, 2, , 2  na′ i a ′ nn ii Quá trình  j= n  ngược bi− ∑ a1 j x j  j=2 x1 =  a11 Các phương pháp trực tiếp (Direct Methods) 26 −x1 +2 x 2 + 3 xx 34 + = 3 −1 2 3 13     24x1− xx 23 + + 2 x 4 = − 1 2− 41 21 −    −384x + x + xx − = 6 −3 8 4 − 16   1 2 34    1 4 7− 24 − x1+4 x 2 + 7 x 3 − 2 x 2 = − 4   x1    x2  x =  = ? n×1 ⋮    xn  27 2  −3  × −  × −  −1 2 3 13  −1 2 3 1 3  −1  −1 2 3 1 3  −1 2 3 1 3  −1      2 4 1 2 1    0 07 45 2− 41 21 −  − −  0 0 7 4 5    −3 8 4 − 16  −3 8 4 − 16  −38 4 − 16  −3 8 4 − 1 6          1 47− 24 − 1 4 7− 24 −  1 4 7− 2 − 4  1 47− 2 − 4    1  −12 3 13  12 3 1 3 12 3 13 × −  12 3 13 −  −  −1 −            0 0 7 4 5  0 0 7 4 5  00 7 4 5  0 0 7 4 5  0 2 −5 − 4 − 3  0 2 −5 − 4 − 3  0 2− 5 − 4 − 3  0 2− 5 − 4 − 3          0 6 10 −1 − 1  0 6 10− 1 − 1  1 4 7 −2 − 4  1 47 −2 − 4  −12 31 3  −12 3 13  −12 3 13  −123 13      6      0 2 −5 −4 − 3 0 2−5 − 4 −3 × −  0 2 −5 −4 − 3 0 2− 5 − 4 − 3   2        25    × −  0 0 7 4 5  0 0 7 4 5  0 0 7 4 5  0 0 7 4 5 7          0 6 10 −1 − 1  0 6 10− 11 −  0 0 25 11 8  0 0 25 11 8  28 −69 7 x = ⋅ = 3 4 7− 23 −123 1 3  5− 4 ⋅ 3 x1  1    x3 = = − 1 0 2− 5 − 4 − 3       7 x2  2  007 4 5  −−−3 43 ⋅−− 5 − 1 x =  =   ()()() 4× 1 x −1   x2 = = 2 3    −23 − 69  2 0 0 0 x  3  7 7   3133−⋅−⋅−() 1 −⋅ 22 4    x = = 1 1 −1 Các phương pháp trực tiếp (Direct Methods) 29 Quá trình aaa11 12 13 ab 1n 1  1 a′ a ′ a ′ b′  xuôi 12 13 1 n 1     aaa21 22 23 ab 2n 2 0 1 a′ a ′ b′ A b  =   23 2 n 2      n×() n + 1 ⋮ ⋮ ⋮ ⋮ ⋮⋮ ⋮⋮ ⋮ ⋮ ⋮ ⋮      aaan1 n 2 n 3 ab nn n  ′   000 1 bn  xn= b n′  Quá trình  j= n ′ ; 1, 2, ,1 ngược xbi= i −∑ ax ij j in = − n −  j= i + 1 Các phương pháp trực tiếp (Direct Methods) 30 −x1 +2 x 2 + 3 xx 34 + = 3 −1 2 3 13     24x1− xx 23 + + 2 x 4 = − 1 2− 41 21 −    −384x + x + xx − = 6 −3 8 4 − 16   1 2 34    1 4 7− 24 − x1+4 x 2 + 7 x 3 − 2 x 2 = − 4   x1    x2  x =  = ? n×1 ⋮    xn  ×( − 1) ×( − 2) 31 ×( − 1) ×3 1 × 2 32 ×( − 6) x4 = 3 5 4 x = − ⋅3 =− 1 3 7 7 3 5  x2 =− −−()23 ⋅−−  () − 12 = 2 2  x1 =−−−3()()()()() 13 −− 31 −−−⋅= 221 x1  1      ×( − 25 ) x2  2  x =  =   4× 1 1 x3  −  −7  ×      23  x4  3  Các phương pháp trực tiếp (Direct Methods) 33 - Các phần tử xoay (pivot) = 0. Ta có thể hoán đổi vị trí của các hàng. Tuy nhiên có thể làm cách khác. - Khi các phần tử xoay rất bé, gần đến 0 thì sẽ có sai số do các phép tính làm tròn các con số sau dấu chấm thập phân Các phương pháp trực tiếp (Direct Methods) 34 −1 2 3 13  1) Véctơ tỉ lệ: Các phần tử có trị tuyệt đối lớn nhất   trong mỗi hàng: 2− 41 21 −   S =3 − 487 x1 [ ] −3 8 4 − 16  2) Véctơ chỉ số:   1 4 7− 24 − L = 1 2 3 4   x1 [ ] i. Quá trình thuận a  Li ,1 −1 2 − 31  ηx =;1..4i =  = , , ,  1. Khử x −1 2 3 13  1 3− 4 8 7 1 SL      i  2− 41 21 −  −3 8 4 − 16  Lớn nhất ở L2
Phương trình 2 là PT pivot đầu   tiên. Hoán đổi L và L 1 4 7 24 1 2 L = 2 1 3 4 − −  x1 [ ] −1  −3  2 −4 1 2 − 1  2 4 1 2 1 × −  × −  − −  2  2 −4 12 − 1  2 −4 1 2 − 1  2  1 2 3 13        −  −1 2 3 1 3  0 0 3 .5 2 2. 5  0 0 3. 5 22. 5  −3 8 4 − 1 6  −3 8 4 − 1 6  −38 4 − 16  −3 8 4 − 1 6          1 47 −2 − 4  1 4 7 −2 − 4  1 4 7 −2 − 4  1 47 − 2 − 4  1  −2 41 2 − 1 2− 41 2 − 1  2− 41 21 −  × −  2− 41 21 −        2    0 0 3.5 2 2.5  0 0 3.5 2 2.5  0 0 3.5 2 2.5  0 0 3.5 22. 5  0 2 5.5 2 4.5  0 2 5.5 2 4.5  0 2 5.5 2 4.5  0 2 5.5 24.5          0 6 6.5− 3 − 3.5  0 6 6.5− 3 − 3.5  14 7− 24 −  14 7− 24 −  2. Khử x a  2 Li ,2 0 2 6  ηx =;i = 2..4  = ; ;  2 S 3.5 5.5 6.5 −2 41 2 − 1 Li    Sx = [3.5 5.5 6.5 ]   0 0 3.5 2 2.5  2   Lớn nhất ở L
Phương trình 4 là PT pivot đầu 0 2 5.5 2 4.5  L = 2 3 4 4 x2 [ ]   tiên. Hoán đổi L2 và L4 0 6 6.5− 3 − 3.5  L = 4 3 2 x2 [ ] 35 −2 41 2 − 1 36 −2 41 2 − 1 −2 41 2 − 1   2  0 6 65. 335.     × − − − 0 6 6.5− 3 − 3 .5 0 6 6.5− 33 − .5 6          10 17  0 2 5.5 2 4.5  0 2 5.5 2 4. 5  0 0 3      3 3  0 0 3.5 2 2.5  0 0 3.5 2 2.5     0 0 3. 5 2 25.  10  −2 41 2 − 1 −2 41 2 − 1 S = 3.5   3. Khử x3   x3 0 6 6.5− 3 − 3.5 0 6 6.5− 3 − 3.5 3      10 17  10 17  0 0 3  0 0 3  3 3 3 3 Lx = [3 4 ]     2 0 0 3.5 2 2.5 0 0 3.5 2 2.5    10  Như nhau nên có thể để như cũ a    Li ,3 3 3.5  η =;i = 3..4 = ; x3    S 10 3.5 Lx = [3 4 ] Li   2 3  37 2 41 2 1 −241 2 − 1 − − −2 4 1 2 −1       0 6 6.5− 3 − 3 .5  0 6 6.5− 3 − 3.5  0 6 6 .5− 3 − 3.5     10 17  3.5  0 0 3 10 17  10 17  × −   10  3 3 0 0 3  0 0 3      3 3  3 3  3  −23 − 69  0 03.5 2 2 .5 0 0 0 0 0 3.5 2 2.5    202 0  −69 20 ii. Quá trình ngược x = ⋅ = 3 4 20− 23 17 x  1 −3 ⋅ 3 1   3     x3 = = − 1 x2  2  10 x =  =   4× 1 1 x3  −  3     x4 3  −3.5 −−()()() 3 3 − 6.5 ⋅− 1   x = = 2 2 6 −−⋅1231()()() −⋅− 1 −− 42 ⋅ x = = 1 1 2 Các phương pháp trực tiếp (Direct Methods) 38 aaa ab  11 12 13 1n 1 1 a12′ a 13 ′ a 1 ′ n b1′      aaa21 22 23 ab 2n 2 0 1 a′ a ′ b′ A b  =   23 2 n 2      n×() n + 1 ⋮ ⋮ ⋮ ⋮ ⋮⋮ ⋮⋮ ⋮ ⋮ ⋮ ⋮      aaan1 n 2 n 3 ab nn n  ′   000 1 bn  Phương pháp khử Gauss- b′′  1 100 0 b1′′  Jordan thực chất     b2′′  010 0 b′′ là khử thêm 1 x =   2  n×1 lần nữa thay cho ⋮  ⋮⋮⋮ ⋮ ⋮ ⋮    b′′  ′′ quá trình ngược n  000 1 bn  Các phương pháp trực tiếp (Direct Methods) 39 −x1 +2 x 2 + 3 xx 34 + = 3 −1 2 3 13     24x1− xx 23 + + 2 x 4 = − 1 2− 41 21 −    −384x + x + xx − = 6 −3 8 4 − 16   1 2 34    1 4 7− 24 − x1+4 x 2 + 7 x 3 − 2 x 2 = − 4   x1    x2  x =  = ? n×1 ⋮    xn  Khử Gauss : Cách 2 4  × −  7  ×1 ×2 Slide sau 40 41 5  ×3 ×  2  ×2 x1  1      x2  2  x =  =   4× 1 1 x3  −      x4  3  Các phương pháp lặp (iteractive Methods) 42 Xuất phát từ phương trình: A⋅ x = b (2) n× n n × 1 n×1 Tách ma trận A thành hiệu của 2 ma trận: AQP= − (3) nn×n× n nn × Với điều kiện ma trận Q không được đặc biệt để tồn tại ma trận đảo Q−1 ngược của nó: n× n   ⇒()2 ⇔Q − P ⋅ x = b ⇔ Q ⋅ x = P ⋅ x + b (4) nn×nnn××  1n×1 nn × n ××× 1 nnn 1 n × 1 ()()k+1 k Q⋅ x = P ⋅ x + b (5) n× n n×1 nnn × × 1 n×1 Các phương pháp lặp (iteractive Methods) 43 ()5 ⇔Q−1 ⋅ Q ⋅ x()()k+1 = Q − 1 ⋅ P ⋅ x k + b 1( 1 ) nnnn× ×n× nn × nnn × × n×1 ()()k+1 −1 k − 1 ⇔x =⋅⋅+⋅ Q P x Q b (6) n×1nn× nnn × × 1 nn × n×1 k=0; 1; 2; - số vòng lặp Nhìn vào công thức (6) ta thấy ma trận [Q] cần phải tồn tại ma trận đảo ngược của nó là [Q]-1 Các phương pháp lặp (iteractive Methods) 44 Phân tách ma trận [A] như sau: A= Q − P QD= nn×n× n nn × n× n n× n ⇒    =DLU + +  PLUAD=− +  =− −  nn× nn × n× n  nn× nn ×n× n   nnnn ××  aaa11 12 13 a 1n  a 11 00 0  000 0  0 a12 a 13 a 1 n  aaaa 0 a 0 0  a 00 0  0 0 a a  212223 2n = 22  + 21  + 23 2n  ⋮⋮⋮⋮⋮  ⋮⋮⋮⋮⋮  ⋮⋮⋮⋮⋮  ⋮⋮ ⋮ ⋮ ⋮        aaa a000 aaaa 0 000 0 n1 n 2 n 3 nn  nn  n1 n 2 n 3    A D L U n× n n× n n× n n× n a11 00 0  0 aaa12 13 1 n  0a 00  aaa 0  =22  + 21 23 2 n  ⋮⋮⋮⋮⋮  ⋮⋮⋮⋮⋮     000a aa a 0 nn  n1 n 2 n 3  D   n× n −P = L + U nn× nn × n× n  Các phương pháp lặp (iteractive Methods) 45 x()()k+1 = Q−1 ⋅⋅ P x k + Q − 1 ⋅ b ()6 n×1nn× nnn × × 1 nn × n×1 −1 − 1 ⇔x()k+1 =− D ⋅−⋅+ A D  x()k  D ⋅ b n×1  nn × nnnnn ×××× 1  nn n×1 −1 − 1 − 1 ()()k  k =−D ⋅⋅+ A x  D ⋅⋅+ D  x  D ⋅ b nn× nnn ××1  nn × nn ××× n 1  nn n×1   = I n× n −1 ⇒x()()k+1 =+ x k  D  ⋅ b −A ⋅ x ()k (7) k=0; 1; 2; - số vòng lặp n×1 n × 1  nn ×  ()n×1 n× n n × 1 Các phương pháp lặp (iteractive Methods) 46 Để thuật toán hội tụ thì Norm củamatrậnMphải< 1:  M <1 - Ma trận vòng lặp Jacobi a12 a13 a 1 n   J 0  n× n ∞   a11 a 11 a 11  −1 − 1    −1      MQPDADDLUJ = ⋅=− ⋅− =− ⋅+ a21 a23 a 2 n   n× n n× n nn× nn × nnnn ××   nn × nn × n× n  0 a a a  22 22 22  M J = a3132 a a 3 n  n n× n 0  a a a a< a; i = 1,2,3,.., n 33 33 33  ∑ ij ii (8) ⋮ ⋮ ⋮⋱⋮  j=1   j≠ i a a a n1 n 2 n 3 0  Ma trận thống trị đường chéo   ann a nn a nn  (diagonally dominant matrix) Các phương pháp lặp (iteractive Methods) 47 15xx+− 8 x − 4 x = 1 15 1 −− 8 4 1  12 3 4 x1     −11 38 12 11 2 −+11x 38 x + 12 x + 11 x = 2      1 2 3 4 x2  A b  = ⇔  x =  = ?     4× 1 4× 5 2−− 51343 2x1 −−+= 5 x 2 13 x 3 4 x 4 3 x3     10 3 12 30 4  x  − −  −10xx12 ++ 3 12 x 3 − 30 x 4 = 4 4  1) Bước 1: Kiểm tra hội tụ: 4 4 a3 j =++=2 5 4 11 < 13 = a 33 a1 j =++=1 8 4 13 < 15 = a 11 ∑ Thỏa mãn ∑ j=1 j=1 3 j≠1 j≠ điều kiện 4 4 hội tụ 11 12 11 34 38 a4 j =10 ++ 3 12 = 25 < 30 = a 44 ∑ a2 j =++= < = a 22 ∑ j=1 j=1 j≠2 j≠4 Các phương pháp lặp (iteractive Methods) 48 2) Bước 2: Xây dựng hệ phương trình (7) 1 0 0 0  15    15 0 0 0  1 −1   0 0 0    0 38 0 0 −1 38  ()7 ⇔=+x x D ⋅−⋅ bAx D=  ⇒ D  =   n×××1 n 1 nn  ( n×1 nnn ×× 1 ) 4× 4 00130−  4× 4  − 1   0 0 0  0 0 0− 30  13  −1  0 0 0  30  1 0 0 0  15    x1   x 1  1 1 15 1− 8 − 4  x 1   0 0 0        2 11 38 12 11    x2 x 2 38   − x 2  =+  ⋅−   ⋅  x x −1 3 2 − 5134 −  x  3 3 0 0 0    3  13       x4   x 4  4− 10 3 12 − 30  x 4   −1  0 0 0  30  Các phương pháp lặp (iteractive Methods) 49 1184   k+1 1184 kkk −xxx + + x() = − xxx() +() + () 15 15234 15 15   1 15 15 234 15 15 x     1 1 11 6 11   ()k+1 1 11() kkk 6() 11 ()   +xxx134 − − x 2 = + xxx 134 − − x2  19 38 19 38   19 38 19 38 =  ⇒  x 32 5 4 32 5 4 3 − +x − x + x   x ()k +1 = − +x()k − x() k + x ( k ) 13 131 13 2 13 4   3 13 131 13 2 13 4 x4  21 1 2   21 1 2 − −x + x + x  x()k+1 = − − xxx() kkk +() + ( ) 15 31 10 2 5 3   415 3 123 10 5  T 50 f1(x ) =15 xxxx 1234 +− 8 − 4 −= 10 Excel  10   xT 11 38 12 11 2 0    f2() =− xxxx 1234 + + + −= 10 A b  ⇔      T x0 =   4× 5 x 2 5 13 4 30 10  f3() = xxxx 1234 − − + −= 4× 1    fxT =−10 xxxx + 3 + 12 − 30 −= 40 10   4() 1234 i x 1i x 2i x 3i x 4i f 1 f 2 f 3 f 4 ||Δx i || || f (x i )|| 1 10 10 10 10 39 498 -123 -254 - - 2 7.4 -3.105263158 0.538461538 1.533333333 96.4537112 -178.0717949 26.45964912 -126.854251 18.43130698 706.3131239 3 0.969752587 1.580836707 2.573819163 -2.6951417 5.317139001 48.64378767 -53.20489429 102.7850652 9.237439879 344.654153 4 0.615276653 0.300737032 -1.518865013 0.731027141 17.75669837 -7.525117593 19.39622187 -49.4077498 5.50027318 178.1663929 5 -0.568503238 0.498766442 -0.026847945 -0.915897853 -5.150407154 12.80960868 -9.945406808 30.33609195 2.525673641 90.32302059 6 -0.225142761 0.161671477 -0.791879238 0.095305212 1.738343118 -1.834107046 6.417008041 -13.62526518 1.356220465 49.62079031 7 -0.341032302 0.209937451 -0.298263235 -0.358870294 -2.083960026 2.202246425 -2.289810981 7.227085374 0.682416397 23.27082662 8 -0.202101634 0.151983598 -0.474402541 -0.117967448 0.387549213 -0.991977723 1.531241986 -3.676839919 0.334244844 12.23958571 9 -0.227938248 0.178088275 -0.356614696 -0.240528779 -0.425952761 0.349482261 -0.672441936 1.750134314 0.173908715 6.063791925 10 -0.199541397 0.168891373 -0.408340999 -0.182190968 0.171262278 -0.291365076 0.336129451 -0.932274845 0.083485775 2.996645834 −0.208730794  11 -0.210958883 0.176558875 -0.382484887 -0.213266796 -0.074878078 0.094031567 -0.185475793 0.447450698 0.042701231 1.544289563   0.175117843  12 -0.205967011 0.174084361 -0.396752256 -0.198351773 0.052004342 -0.062053759 0.082016412 -0.228550688 0.021378909 0.754315406 x∗ =   4× 1 −0.392829414  13 -0.209433967 0.175717354 -0.390443301 -0.205970129 -0.018365219 0.030042055 -0.045572306 0.115275999 0.010607955 0.384615634 14 -0.208209619 0.174926774 -0.393948863 -0.202127596 0.011883782 -0.013266705 0.021771731 -0.056681964 0.005401673 0.192081782 −0.203345842   15 -0.209001871 0.175275898 -0.392274115 -0.204016995 -0.005491269 0.008028369 -0.010887719 0.029066875 0.002669112 0.095785572 16 -0.208635786 0.175064625 -0.393111632 -0.203048099 0.002613278 -0.003419278 0.005664117 -0.014344867 0.001348647 0.048531175 17 -0.208810005 0.175154606 -0.39267593 -0.203526261 -0.001482981 0.001885035 -0.002710991 0.007240544 0.000675961 0.024103682 18 -0.20871114 0.175105 -0.392884468 -0.20328491 0.00065329 -0.000935106 0.001411168 -0.003639926 0.0003376 0.012161154 19 -0.208754692 0.175129608 -0.392775917 -0.203406241 -0.000358479 0.000447056 -0.000695469 0.001811967 0.000170314 0.006090575 20 -0.208730794 0.175117843 -0.392829414 -0.203345842 0.000174621 -0.000240468 0.000348216 -0.000916252 8.49681E-05 0.003047842 Các phương pháp lặp (iteractive Methods) 51 Phân tách ma trận [A] như sau: A= Q − P    nn× nn × QDLAU= + = − n× n  nn× nn × nn × n× n  ⇒ n× n =DLU +  +  PU= − nn× nn ×  n× n n× n n× n ()4 ⇔DL + ⋅ x =−⋅+ Uxb ( nnnnn×××) 1n× n n × 1 n × 1 −1 − 1 −1 ⇔D ⋅+⋅= DLxD  ⋅−⋅+ Uxb ⇔=+ xDL ⋅−⋅+ Uxb (9’) nn×××××() nnnnn1  nn()n× n n × 1 n ×1 n ××× 1() nnnn()n× n n × 1 n × 1 −1 − 1 ⇔D ⋅⋅= Dx  D ⋅−⋅−⋅ bLxUx nn× nnn ×××1  nn()n×1 nnn ×× 1 n × n n × 1 −1 ⇔=x D  ⋅− b L ⋅x − U ⋅ x (9) n×1  nn ×  ()n×1 n × n n×1n× n n × 1 Các phương pháp lặp (iteractive Methods) 52 Minh họa cho hệ 4 phương trình −1 x= DL + ⋅−⋅+ Uxb (9’) n×××1() nnnn()n× n n × 1 n × 1 a11 0 0 0  0a 0 0  D  = 22  4× 4  ⋮ ⋮⋮⋮ ⋮    1 0 0 0 a − nn  x1  a11 0 0 0  0 a12 a 13 a 14  x1   b 1   0 0 00 x     1  x  a a 0 0  0 0 a a  x   b  0 0 0    2  21 22 23 24 2   2   a21 x2  =  i −  i + L=  ; x =         44× a a 0 0  41× x a a a 0  0 0 0 a  x b  31 32 x3  3  31 32 33 34 3   3           a41 a 42 a 43 0  x4         x4  a41 a 42 a 43 a 44  00 0 0  x4   b 4   0 a12 a 13 a 14  b1      0 0 a23 a 24 b2  U=  ; b =   44× 0 0 0  41× a34 b3    00 0 0 b  −1   4  x()k+1 = DL + ⋅−⋅ Uxb()k + (11) n×××1() nnnn()n× n n × 1 n × 1 Các phương pháp lặp (iteractive Methods) 53 Minh họa cho hệ 4 phương trình 1  −1 0 0 0   a  x= D ⋅−⋅−⋅ bLxUx (10) 11  41×× 44  ( 41× 4441 ×× 44 × 41 × ) 1  0 0 0  1  −1 a 0 0 0   22  a11  D = x  b 0  ax ++ ax ax  4× 4  1  1 1  1 122 133 144 0 0 0  0 0 0         a x2 a22   b 2 a21 x 1 ax233+ ax 24 4   33  =  i  −  −  1   1  x3 0 0 0   b 3 ax31 1+ ax 32 2 a34 x 4  0 0 0 a     x33    b ax+ ax + ax 0   a44  4  4 41 1 42 2 43 3     0 0 0 1  a  0 0 00  x1  44      a21 0 0 0 x2  L=  ; x =   44× 0 0  41× −1 a31 a 32 x3  k+1 k + 1 k   ()()()  0   x= D ⋅−⋅ bLx −⋅ Ux a41 a 42 a 43  x4  n××1 nn  ( n×1 nnn ×× 1 n × n n × 1 ) (12) 0 a12 a 13 a 14  b1      0 0 a23 a 24 b2  i−1 n U=  ; b =   ()k+11 ()() k + 1 k  44× 0 0 0  41× x=− bax − axi; = 1,2,3, , n a34 b3  i i∑ ijj ∑ ijj  (13)     aii j=1 j = i + 1  00 0 0  b4  Các phương pháp lặp (iteractive Methods) 54 Để thuật toán hội tụ thì Norm củamatrậnMphải< 1:  M 1 - Ma trận vòng lặp Gauss-Seidel  GS <  n× n ∞  −1  −1   MQPDLUGS = ⋅=− + ⋅  n× n n× n nn× nn × nn ×  n× n Vì phương pháp Gauss – Seidel là một sự cải tiến của phương pháp Jacobi, nó hội tụ bất cứ khi nào phương pháp Jacobi thực hiện và thường nhanh hơn. Nhớ lại rằng nếu ma trận A thống trị đường chéo, thì phép lặp Jacobi được đảm bảo hội tụ về vectơ nghiệm. Điều này có nghĩa rằng nếu A thống trị đường chéo, thì phép lặp Gauss – Seidel cũng được đảm bảo hội tụ và nhanh hơn Jacobi. Nếu A không thống trị đường chéo, thì sự hội tụ của phương pháp Gauss – Seidel dựa vào một lớp ma trận đặc biệt khác được gọi là xác định đối xứng, xác định dương. Các phương pháp lặp (iteractive Methods) 55 aaa a  11 12 13 1 n 1) a =a – ma trận đối xứng aaa a  ij ji A = 21 22 23 2 n  2) Ma trận xác định dương n× n ⋮ ⋮ ⋮⋮ ⋮    a > 0 aaa a 11 n1 n 2 n 3 nn   a a  11 12 > 0  a a  21 22  a11 a 12 a 13 n  0 ; 1,2,3,..,  a21 a 22 a 23 > ∑ aaiij< ii = n j=1  a a a j≠ i  31 32 33  Ma trận thống trị đường chéo  (diagonally dominant matrix) detA > 0  ()n× n  Các phương pháp lặp (iteractive Methods) 56 15xx+− 8 x − 4 x = 1 15 1 −− 8 4 1  12 3 4 x1     −11 38 12 11 2 −+11x 38 x + 12 x + 11 x = 2      1 2 3 4 x2  A b  = ⇔  x =  = ?     4× 1 4× 5 2−− 51343 2x1 −−+= 5 x 2 13 x 3 4 x 4 3 x3     10 3 12 30 4  x  − −  −10xx12 ++ 3 12 x 3 − 30 x 4 = 4 4  1) Bước 1: Kiểm tra hội tụ: 4 4 1 8 4 13 15 a3 j =++=2 5 4 11 < 13 = a 33 ∑ a1 j =++= < = a 11 ∑ Ma trận 1 j=1 j= 3 j≠1 j≠ thống trị 4 4 đường a=++=11 12 11 34 < 38 = a a4 j =10 ++ 3 12 = 25 < 30 = a 44 ∑ 2 j 22 ∑ chéo j=1 j=1 j≠2 j≠4 Các phương pháp lặp (iteractive Methods) 57 1   k+1 1 kkk 1084−−−−()()xxx  x() =−−−− 10() xxx()()() 84  15 234    115 () 234     x1  1 1 211 1211   ()k+1 211() k + 1 12()() kk 11    −−−+()()xxx134  x 2 =−−() x 1 −+() xx 34 x2  38   38   =  ⇒  x −1 −1 3 32−()()x − 5 x − 4 x   x()k+1=32 − xxx()() kkk + 1 − 5 + 1 − 4 ()  13 1 2 4    313 () 124()  x4  −1   −1 4−−()() 10x + 3 x + 12 x − 0   x()k+1=4 −− 10 xxx()()() kkk +++ 111 + 3 + 12 − ( 0 )  30 1 2 3    430 () 123   T 58 f1(x ) =15 xxxx 1234 +− 8 − 4 −= 10 Excel  10   xT 11 38 12 11 2 0    f2() =− xxxx 1234 + + + −= 10 A b  ⇔      T x0 =   4× 5 x 2 5 13 4 30 10  f3() = xxxx 1234 − − + −= 4× 1    fxT =−10 xxxx + 3 + 12 − 30 −= 40 10   4() 1234 i x 1i x 2i x 3i x 4i f 1 f 2 f 3 f 4 ||Δx i || || f (x i )|| 1 10 10 10 10 39 498 -123 -254 - - 2 7.4 -3.857894737 5.468421053 -0.798421053 65.58842105 -173.1615789 -43.19368421 0 18.32873022 722.5301774 −0.208738779  3 3.027438596 -0.566752539 0.207304283 -1.116233073 46.65132444 -66.62933346 -1.271248081 0 7.598109261 116.0397501   0.175122207  4 -0.082649699 0.286362256 -0.697080228 -0.355979299 5.047175791 -2.489822627 3.041015094 0 3.434581664 76.57269519 x∗ =   4× 1 −0.392811814  5 -0.419128085 0.254482266 -0.502660361 -0.169239889 -2.334196566 4.387171913 0.746957639 0 0.432324797 10.34603361   −0.203366245  6 -0.263514981 0.184076272 -0.394182375 -0.184760329 -0.876148122 1.131010994 -0.062081759 0 0.202930529 3.658282924 7 -0.205105106 0.171220946 -0.385027405 -0.201853832 -0.01772108 -0.078168881 -0.06837401 0 0.062872682 1.482920277 8 -0.203923701 0.173620008 -0.391027905 -0.204407928 0.06061945 -0.100101061 -0.010216383 0 0.007048449 0.100002844 9 -0.207964997 0.175084397 -0.392998746 -0.203702726 0.014410305 -0.015892865 0.002820807 0 0.004781008 0.096934378 10 -0.208925684 0.175224537