Bài giảng Phương pháp tính: Chương 2 - TS. Nguyễn Quốc Lân

Chia sẻ: Na Na | Ngày: | Loại File: PPT | Số trang:31

Thêm vào BST

Báo xấu

344
lượt xem 65
download

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

Bài giảng Phương pháp tính: Chương 2 trình bày hệ phương trình tuyến tính Ax = b. Các nội dung cụ thể được trình bày trong chương bao gồm: Các phương pháp chính xác, các phương pháp lặp, số điều kiện – hệ điều kiện xấu.

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 Phương pháp tính: Chương 2 - TS. Nguyễn Quốc Lân

BỘ MÔN TOÁN ỨNG DỤNG - ĐHBK ------------------------------------------------------------------------------------- PHƯƠNG PHÁP TÍNH – BG SINH VIÊN CHƯƠNG 2 HỆ PHƯƠNG TRÌNH TUYẾN TÍNH Ax = b TS. NGUYỄN QUỐC LÂN (2/2006)
NỘI DUNG --------------------------------------------------------------------------------------------------------------------------- A- CÁC PHƯƠNG PHÁP CHÍNH XÁC 1- PHƯƠNG PHÁP KHỬ GAUSS (PHẦN TỬ TRỤ) 2- PHÂN TÍCH NHÂN TỬ A = LU 3- PHÂN TÍCH CHOLESKY B- CÁC PHƯƠNG PHÁP LẶP 1- LẶP JACOBI 2- LẶP GAUSS - SEIDEL C- SỐ ĐIỀU KIỆN – HỆ ĐIỀU KIỆN XẤU
TỔNG QUAN -------------------------------------------------------------------------------------------------------------------------------- Hệ n phương trình bậc 1 (tuyến tính), n ẩn → Dạng Ax = b: a11 a12  a1n  b1   x1  a a22  a2n  b  x  A =  21 , b =  2 , x =  2  = [ x1  xn ] T        b  x   an1 an 2  ann   n  n a11 a12  a1n  0 a  a2 n  Đơn giản: Hệ tam giác A =   ⇒ Giải lùi 22 ............................     0 0  ann  Hàng i: hi = [ai1 ai2 … ain]T. Biến đổi sơ cấp trên hàng hi → hi + khj: Nhân hj với k rồi cộng xuống hi (chỉ hi thay đổi)
PHƯƠNG PHÁP KHỬ GAUSS ----------------------------------------------------------------------------------------------------------------------------------- Giải thuật: Biến đổi sơ cấp trên hàng → A: ∆ trên → Giải lùi 2 x1 − 2 x2 + 3 x3 = 1  VD: Giải hệ 6 x1 − 7 x2 + 14 x3 = 5 Xây dựng ma trận mở rộng 4 x − 8 x + 30 x = 14  1 2 3 2 − 2 3 1  Khử cột 1 với hệ số khử A = [ A | b] = 6 − 7 14 5 m1j a1 j aij   m1 j = Toång : mij = quaùt 4 − 8 30 14    a11 aii 6 m21 = = 3 2 − 2 3 1  h2 → h2 − 3h1 2 − 2 3 1  2 ⇒ 6 − 7 14 5 → 0 −1 5 2 4     m31 = = 2 4 − 8 30 14  h3 → h3 − 2h1  0 − 4 24    12 2
GIẢI LÙI & PHẦN TỬ TRỤ ------------------------------------------------------------------------------------------------------------------------------- −4 Khử cột 2 với hệ số m32 = =4 −1 khử:− 2 3 1  2 h3 → h3 − 4h2 2 − 2 3 1  0 − 1 5 2 → 0 − 1 5 2      0 − 4 24 12    0  0 4 4 Giải lùi với hệ tam giác trên thu được: 2 x1 − 2 x2 + 3 x3 = 1  x3 = 4 4 = 1 2   − x2 + 5 x3 = 2 ⇒  x2 = ( 2 − 5 x3 ) ( − 1) = 3 ⇒ x = 3      4 x3 = 4  x = (1 + 2 x − 3 x ) 2 = 2 1    1 2 3   Điều kiện: Khử cột 1: a11(1) ≠ 0 & Khử cột 2: a22(2) ≠ 0 & Giải lùi: a33(3) ≠ 0 ⇒ Phần tử trụ (pivot) akk ≠ 0
KHỬ GAUSS VỚI LỆNH MAPLE -------------------------------------------------------------------------------------------------------------------------------- > with(linalg); # Khởi động gói lệnh Đại số tuyến tính > A := matrix(2,3,[2, 3, 4, 1, 2, 3]); # Nhập ma trận > m21 := A[2,1]/A[1,1]; # Tính hệ số khử > A := addrow(A,1,2,–m21) ; # Cộng hàng h2 → h2 – m21h1 > A := swaprow(A,1,2) ; # Nếu cần thiết, đổi hàng h2 ↔ h1 > x := backsup(A) ; # Hệ đã ở dạng tam giác trên: Giải lùi > AA := gausselim(A); # Lệnh gộp khử Gauss toàn ma trận VD: Giải hệ  x1 − x2 + 2 x3 − x4 = −8 2 x − 2 x + 3 x − 3 x = −20  1 2 3 4   x1 + x2 + x3 = −2  x1 − x2 + 4 x3 + 3 x4 = 4 
KHỬ GAUSS VỚI MA TRẬN “LẺ”: PIVOT ĐƠN VỊ ------------------------------------------------------------------------------------------------------------------------------------- VD: Giải hệ với phép khử 2.08 x1 − 1.3 x2 = 0.608 Gauss, làm tròn 3 chữ số lẻ) − 0.7 x1 + 2.08 x2 − 1.3 x3 = −0.152   − 0.7 x2 + 2.08 x3 − 1.3 x3 = −0.168 − 0.7 x3 + 2.08 x4  = 1.116  2.08 − 1.3 0 0 1.264  − 0.7 2.08 − 1.3 0 − 0.152 ⇒ [ A b] =    0 − 0.7 2.08 − 1.3 − 0.168  0 0 − 0.7 2.08 1.116    1.006  0.636 ⇒y=  0.593 0.736  
THỰC TẾ TÍNH TOÁN: VẤN ĐỀ LÀM TRÒN SỐ --------------------------------------------------------------------------------------------------------------------------------- VD: Giải hệ trên máy tính với phép làm tròn 4 chữ có nghĩa 0.003 x1 + 59.14 x2 = 59.17 (E1 )  Nghiệm chính xác: [10, 1]T 5.291x1 − 6.130 x2 = 46.78 (E 2 ) Quy tắc làm tròn trên máy tính: Làm tròn chữ số có nghĩa 12,34567 = 1,234567 ⋅101 ≈ 1,235 ⋅101 = 12,35 a21 Trụ khử: a11 = 0.003 ≠ 0 ⇒ m21 = = 1763,67 ≈ 1764 a11 Biến đổi cột một: (E2) → (E2) – m21(E1) 0.003 x1 + 59.14 x2 = 59.17  x2 = 1.001  ⇒  : Taïisao???  − 104300 x2 = −104400  x1 = −10
PHÂN TÍCH NHÂN TỬ (MATRIX FACTORIZATIONS) --------------------------------------------------------------------------------------------------------------------------------- Ma trận vuông A phân tích được thành dạng LU ⇔ 1 0 0 0 * * * *  Hệ Ax = b ⇔ (LU)x = b ⇔ * 1 0 0  0 * * * A= ⋅  Ux = y (1) * * 1 0  0 0 * *  : 2 heä giaùc tam * * * 1  0 0 0 * Ly = b ( 2 )                L U Giải hệ đầu ⇔ Giải 2 hệ ∆ : Ly = b (2) tìm y; Ux = y (1) tìm x Nhân A x b y Nhân L Nhân U
VÍ DỤ --------------------------------------------------------------------------------------------------------------------------------- Giả sử ma trận A phân tích được thành dạng LU như sau:  3 −7 −2 2  1 0 0 0 3 − 7 − 2 1  − 3 5 1 0  − 1 1 0 0  0 − 2 − 1 1 A=  = ⋅   6 −4 0 − 5  2 − 5 1 0  0 0 −1 1 − 9 5 − 5 12 − 3 8 3 1  0 0 0 − 1       Sử dụng phân tích LU trên giải hệ Ax = b = [–9 5 7 11]T Giải Ly = b tìm y Giải Ux = y tìm x
PHÂN TÍCH NHÂN TỬ A = LU --------------------------------------------------------------------------------------------------------------------------------- Quan sát: Ma trận khử L và ma trận kết quả U. Xét tích L.U 1 0 0  2 − 2 3 3 1 0  ⋅ 0 − 1 5  =     2 4 1 0 0 4      Kết quả: Nếu quá trình khử Gauss diễn ra bình thường (không đổi hàng), ma trận A của hệ Ax = b phân tích được thành tích LU: A = LU với  L (lower): ma trận tam giác dưới, đường chéo chính bằng 1, chứa các hệ số khử ở vị trí khử  U (upper): ma trận tam giác trên, cũng là ma trận kết quả nhận được sau quá trình khử Gauss
GIẢI THUẬT TÌM LU (CROUT – DOOLITLE) --------------------------------------------------------------------------------------------------------------------------------- Phân tích LU với đường chéo chính L bằng 1 ⇒ Khử Gauss (không đổi hàng). Các hệ số khử tạo L, ma trận kết quả: U 2 − 2 3 m21 = 3 1 0 0  VD: A = 6 − 7 14  : m31 = 2 ⇒ L = 3 1 0      4 − 8 30 m32 = 4   2 4 1   L (hoặc U) có đchéo chính = 1 ⇒ G/thuật Doolitle (Crout) i −1 For j = 1 to n: i = 1 → j uij = aij − ∑ lik ukj k =1 Tự xem j −1 1   i = j +1 → n lij =  aij − ∑ lik ukj  SGK/ 35 u jj  k =1 
MINH HOẠ GIẢI THUẬT DOOLITLE (ĐCHÉO L = 1) ------------------------------------------------------------------------------------------------------------------------------- 2 − 2 3  1 0 0   VD: A = 6 − 7 14  ⇒ L =  1 0 ,U =  0        4 − 8 30     1  0  0   j = 1: i=1 u11 = a11 a a31 i=2 21 = 21 i = 3 31 = u11 u11 j = 2: i=1 u12 = a12 i = 2 u22 = a22 − 21u12 a32 − 31u12 i = 3 32 = u22 j = 3: i = 1 u13 = a13 i = 2 u23 = a23 − 21u13 i=3 i=3 u33 = a33 − 31u13 − 32 u23
PHÂN TÍCH CHOLESKY ---------------------------------------------------------------------------------------------------------------------------- Tương tự phân tích LU nhưng gọn hơn “phân nửa”! Ma trận vuông A (n hàng, n cột) : A = [ aij ] xác định dương n n ∀ x = [ x1 ,  , xn ] ∈ R n , x ≠ 0 : xT Ax = ∑∑ aij xi x j > 0 T i =1 j =1 1 1 0 VD: A = 1  5 − 2  : ma trận (đối xứng) xác định dương vì  0 − 2  2 ∀ x = [ x1 , x2 , x3 ] ∈ R 3 ⇒ xT Ax = x12 + 5 x2 + 2 x3 + 2 x1 x2 − 4 x2 x3 > 0 T 2 2 A: XĐD⇔ n định thức con (hvuông) trên đ/chéo chính đều > 0
GIẢI THUẬT CHOLESKY ------------------------------------------------------------------------------------------------------------------------------- Định lý: Ma trận A đối xứng xác định dương ⇔ Tồn tại ma trận tam giác dưới B thoả mãn : A = BBT i −1 A đối For i = 1 to n do bii = aii − ∑ bik 2 k =1 xứng: 1  i −1  For j = i+1 to n do b ji =  a ji − ∑ b jk bik  bii  k =1  Ax = b ⇔ (BBT)x = b ⇔ BTx = y & By = b: 2 hệ ∆ (như LU) A k0 xác định dương (chỉ đối xứng): A = BBT có thể chứa số phức ⇒ 2 hệ BTx = y & By = b: phức. Nhưng nghiệm x: thực!
MINH HOẠ GIẢI THUẬT CHOLESKY ------------------------------------------------------------------------------------------------------------------------------- 1 1 0  0 0  VD: A = 1 5 −2 ⇒B= 0    0 − 2  2      i=1 b11 = a11 a21 a31 j=2 b21 = j=3 b31 = b11 b11 i=2 b22 = a22 − b21 2 a32 − b31b21 j=3 b32 = b22 i=3 b33 = a33 − b31 − b32 2 2
TỔNG QUAN PHƯƠNG PHÁP LẶP --------------------------------------------------------------------------------------------------------------------------- Chương 1: Phương pháp lặp đơn với phương trình f(x) = 0  x = ϕ ( x) f ( x) = 0 ⇔  ⇒ xn +1 = ϕ ( xn )  ϕ ( x) − ϕ ( y ) ≤ q x − y : ϕ ' ( x ) ≤ q < 1 Hệ Ax = b ⇔ x = Tx + c = ϕ(x), T: ma trận, c: vectơ. Đkiện: ϕ(x) – ϕ(y)≤ qx – y ⇒ Dãy lặp: x(n+1) = Tx(n) + c Chuẩn vectơ, ma trận: x = [x1, x2 … xn]T ∈ Rn, A = [aij ] n  x ∞ = max{ xi } ⇒ A ∞ = max  ∑ aij  1≤i ≤ n 1≤i ≤ n  j =1  n n  x 1 = ∑ xi ⇒ A 1 = max ∑ aij  i =1 1≤ j ≤ n i =1 
VÍ DỤ ---------------------------------------------------------------------------------------------------------------------------  Tính các chuẩn vectơ và ma trận  1 − 1 3 2 − 3  ⇒  x∞= 3  ⇒  A ∞ = 12 x= A = − 2 4 3   x = 6    A = 13  − 2  1 − 5 6 − 1  1      Vectơ nào trong số hai vectơ sau xấp xỉ tốt nhất theo chuẩn ∞ , chuẩn một nghiệm hệ phương trình − 0.1 0.3   x1 + 2 x2 + 3 x3 = 1  ( 2) . ∞  x ≈ x x ( 1) = − 7.4 , x ( 2 ) = − 6.8 2 x1 + 3 x2 + 4 x3 = −1 →     .1  5.2  4.7  3 x + 4 x + 6 x = 2  x ( 1) ≈ x      1 2 3  Tch. chuẩn vectơ, chuẩn ma trận: Chuẩn tích ≤ tích chuẩn Ax ≤ A ⋅ x ⇒ ϕ( x) − ϕ( y ) = T ( x − y) ≤ T ⋅ x − y : T < 1
LẶP JACOBI ----------------------------------------------------------------------------------------------------------------------------------- Với vectơ x(0) = [0, 0, 0]T, tìm vectơ 10 x1 + 3x2 + x3 = 7.5  nghiệm xấp xỉ x(k) của phép lặp − 3x1 + 10 x2 − x3 = 9 − x + 2 x + 8 x = −2.5 Jacobi với hệ sau. Dừng: x(k)  1 2 3 “giống” x(k-1) (khoảng 0.3) . So với nghiệm α = [0.5, 1, -0.5]T 1/ Rút x trên đường chéo chính ⇒ Đưa về dạng x = Tx + c  x = − 3 x − 1 x + 7.5 = −0.3x − 0.1x + 0.75  1 10 2 10 3 10 2 3   3 1 9  x2 = x1 + x3 + = 0.3x1 + 0.1x3 + 0.9 ⇔ x = Tx + c  10 10 10  1 2 2.5  x3 = x1 − x2 − = 0.125 x1 − 0.25 x2 − 0.3125  8 8 8
CÔNG THỨC LẶP JACOBI --------------------------------------------------------------------------------------------------------------------------- 0 −3 −1   10 10  0.75  T= 3 0 1  , T = max  4 , 3 = 4 < 1, c =  0.9     10 10  ∞ 10 8  10   1 −2 0  − 0.3125    8 8   x1(1) = −0.3 x20 ) − 0.1x30 ) + 0.75 = 0.75 ( (  (1) 2/ Từ x tính x :  (0) (1) x2 = 0.3 x1( 0 ) + 0.1x30 ) + 0.9 = 0.9 (  (1)  x3 = 0.125 x1( 0 ) − 0.25 x20 ) − 0.3125 = − 0.3125 (  x1 k +1) = −0.3 x2k ) − 0.1x3k ) + 0.75 ( ( (  ( k +1)  Tổng quát: x ⇒ x :  (k) (k+1) x2 = 0.3 x1 k ) + 0.1x3k ) + 0.9 ( (  ( k +1)  x3  = 0.125 x1 k ) − 0.25 x2k ) − 0.3125 ( ( (k) q Sai số: Như lặp đơn với q = ||T|| x − x * ∞ ≤ x ( 1) − x ( 0 ) 1− q ∞