Bài giảng phương pháp tính

Chương 3 GIẢI GẦN ĐÚNG PHƯƠNG TRÌNH ĐẠI SỐ VÀ SIÊU VIỆT I.Tìm nghiệm thực của một phương trình. a. Nghiệm thực của phương trình một ẩn – Ý nghĩa hình học. f – hàm cho trước của đối số x - Vẽ đồ thị y = f(x) b. Sự tồn tại của nghiệm thực. c. Khoảng phân ly nghiệm (tách nghiệm) Định nghĩa. Khoảng [a, b] nào đó gọi là khoảng phân ly nghiệm của phương trình f(x) = 0 nếu nó chứa một và chỉ một nghiệm của phương trình đó. Muốn thế: trong [a, b] : - hàm f(x) đơn điệu II. Các phương pháp xác định gần đúng nghiệm thực của một phương trình. 1. Phương pháp đồ thị 2. Phương pháp thử. Ví dụ : Tìm nghiệm của phương trình: f(x) = xlogx – 1,2 = 0; - [2, 3] - khoảng phân ly nghiệm; - tiếp tục chia nhỏ khoảng [a, b]; - Lặp lại các bước trên cho đến khi đạt độ chính xác cần thiết. Định lý. Nếu hàm số f(x) liên tục và đơn điệu trên khoảng [a, b], đồng thời f(a) và f(b) trái dấu thì [a, b] là khoảng phân ly nghiệm của phương trình f(x) = 0. 3. Phương pháp chia đôi. Cho phương trình f(x) = 0; - Giả sử [a, b] là khoảng phân ly nghiệm α của phương trình. - Tính f(c) Xét dấu f(c).f(a) và f(c).f(b); . . . . . . . . . . . . . . . . . . . . . . . . . Với an ≤ α ≤ bn. - Lấy an hoặc bn làm giá trị gần đúng của nghiệm; - Sai số: Ví dụ: Tìm nghiệm của phương trình f(x) = x4 + 2x3 –x – 1 = 0; f(0) = -1; f(1) = 1 f(0,5) = -1,9 f(0,75) = -0,59 f(0,875) = +0,05 f(0,8125) = -0,304 f(0,8438) = -0,135 f(0,8594) = -0,043 Sai số mắc phải: Các bước tính: Cho phương trình f(x) = 0; - Ấn định sai số cho phép; - Xác định khoảng phân ly nghiệm (p2 đồ thị, p2 thử . . .); - Giải theo sơ đồ: Nhận xét: - Thuật toán đơn giản; - Hội tụ chậm. 4. Phương pháp lặp. Cho phương trình f(x) = 0 có nghiệm thực trong khoảng [a, b]; - Viết lại x + f(x) – x = 0; Đặt φ(x) = x + f(x); ( 6 ) x1 = φ(xo); x2 = φ(x1); . . . . . . . . . xn = φ(xn-1); n = 1, 2, . . . ( 7 ) - Hàm φ(x) gọi là hàm lặp. Quá trình tính cũng có thể phân kỳ, xn ngày càng đi xa khỏi nghiệm. Sự hội tụ của quá trình tính. Định lý về sự hội tụ. Giả sử: - [a, b] là khoảng phân ly nghiệm α của phương trình f(x) = 0; - Hàm φ(x) có đạo hàm hạng nhất thoả mãn điều kiện: q - hằng số; ( 9 ) Sai số của phép tính: Chú ý: - Nếu φ’(x) 0 Với sai số cho phép ε =10-3 2. Tìm gần đúng nghiệm bằng phương pháp chia đôi. 1, 2, 1,5 -1 5 0,875 0 1,25 1,5 1,375 -0,29687 0,875 0,22461 0 1,3125 1,375 1,34375 -0,0515 0,22461 0,08261 0 1,3203 1,32812 1,3242 -0,0187 0,01456 -0,0022 >0 1,3242 1,32812 1,3261 -0,0022 0,01456 0,0059 0 trong khoảng [1, 2] f”(x) = 6x > 6 trong khoảng [1, 2] f(1) = -1; f(2) = 5; Lập bảng tính: Lập bảng tính: x f(x)=x3-x-1 2,0 5,0 11,0 1,5454545 1,5454545 1,145755 6,165288 1,3596148 1,3596148 0,153704 4,545657 1,3258015 1,3258015 0,004625 4,273245 1,3247190 1,3247190 0,0000034 4,264641 1,3247182 1,3247182 0,0000010 α = 1,3247182 5/ Phương pháp dây cung 1,0 2,0 -1 5 1,17 -0,568 > 0 1,17 2,0 -0,568 5 1,255 -0,2796 > 0 1,255 2,0 -0,2796 5 1,2945 -0,1253 1,2945 2,0 -0,1253 5 > 0 1,3117 -0,0548 > 0 1,3117 2,0 -0,0548 5 1,3192 -0,023 > 0 1,3192 2,0 -0,023 5 1,3223 -0,0103 > 0 1,3223 2,0 -0,0103 5 1,3237 -0,004 > 0 1,3237 2,0 -0,004 5 1,3242 -0,002 > 0 1,3242 2,0 -0,002 5 1,3245 -0,00098 > 0 1,3245 2,0 -0,00098 5 1,3246 -0,00037 > 0 1,3246 2,0 -0,00037 5 1,3247 -0,00011 > 0 1,3247 2,0 -0,00011 5 1,324715 -0,000013 Có thể lấy α = 1,324715 với sai số < ε = 10-3. (4) Cộng (4) theo từng vế: cos( α – φ ) Chia cho 2r2r4: Đặt Giải bài toán cho trường hợp cụ thể: r1 = 10; r2 = 6; r3 = 8; r4 = 4; α = 40o. A = 5/3; B = 5/2; C = 11/6 1/ Tìm khoảng phân ly nghiệm: Từ nhận xét trên hình vẽ, thử với khoảng [φa,φb] = [30o, 40o] Kiểm tra điều kiện phân ly nghiệm: Hàm số liên tục và đơn điệu trong khoảng [φa,φb] [φa,φb] là khoảng phân ly nghiệm. Chương 4 TÌM NGHIỆM CỦA HỆ PHƯƠNG TRÌNH A. Nghiệm của hệ phương trình đại số tuyến tính. I. Khái niệm chung. Xét hệ n phương trình có n ẩn số: a11x1 + a12x2 + . . . +a1nxn = f1; a21x1 + a22x2 + . . . +a2nxn = f2; an1x1 + an2x2 + . . . +annxn = fn; . . . . . . . . . . . . . . . . . . . . . . . . . ( 20 ) Ma trận hệ số của phương trình: ( 21 ) Vectơ vế phải và véctơ ẩn: Hay II. Tìm nghiệm theo quy tắc Crame và phương pháp Gaoxơ. Sự tồn tại và duy nhất của nghiệm của hệ. Δ = det (A) - Δi – suy ra từ Δ : thay cột thứ i bằng vế phải. a/ Định lý Crame: Nếu Δ ≠ 0 thì hệ ( 20 ) không suy biến và có nghiệm duy nhất được tính bởi công thức: Nhận xét: - Công thức đẹp, gọn; - Khi n lớn phải thực hiện một số lượng rất lớn các phép tính. NC(n) - số lượng phép tính cần làm khi hệ có n ph/trình. NC(n) = (n+1)!n b/ Phương pháp Gaoxơ. Ví dụ: a11x1 + a12x2 + a13x3 = a14 ; a21x1 + a22x2 + a23x3 = a24 ; a31x1 + a32x2 + a33x3 = a34 ; x1 + b12x2 + b13x3 = b14 ; x2 + b23x3 = b24 ; x3 = b34 ; ( 25 ) ( 26 ) Quá trình giải (26): quá trình ngược. Khối lượng phép tính: Với n = 15; NG(15) = 2570; nhỏ hơn nhiều so với ph/pháp trên. c/ Tìm đúng dần nghiệm của hệ phương trình đại số tuyến tính bằng phương pháp lặp đơn. Nội dung phương pháp: - Cho hệ phương trình Ax = f ; - Biến đổi về dạng tương đương: suy ra từ A; g suy ra từ f. Chọn x(0) nào đó làm nghiệm gần đúng đầu tiên và tính các gần đúng tiếp theo: x(1), x(2) . ., x(m) theo công thức lặp: ( 29 ) xo – cho trước; ( 30 ) trong đó ( 28 ) Sự hội tụ và sai số của phương pháp. Định nghĩa về sự hội tụ. Giả sử [ α1, α2, . . ., αn ]T - nghiệm của (20) tức (23), nếu Định lý về sự hội tụ (của phương pháp lặp đơn). Đối với ma trận B nếu: Các bước tính: 1/ Cho hệ phương trình Ax = f ; 2/ Ấn định sai số cho phép ε ; 4/ Kiểm tra thoả mãn điều kiện hội tụ ( 31 ); 5/ Chọn x(0) tuỳ ý; 6/ Tính m = 1, 2, 3, . . . Ví dụ. Xét hệ phương trình Tìm nghiệm gần đúng với độ chính xác ε = 1.10-3 bằng phương pháp lặp đơn. Giải. - Đưa ( a ) về dạng x = Bx + g - Kiểm tra điều kiện hội tụ ( 31 ) r0 = max (0,08; 0,08; 0,03) = 0,08 <1. Phương pháp lặp hội tụ với mọi x(0) cho trước. Chọn x(0) = (0, 0, 0)T . Kết quả tính ghi trong bảng: 0 0 0 2 3 5 1,92 3,19 5,04 1,9094 3,1944 5,0446 1,90923 3,19495 5,04480 0,08 0,19 0,04 0,0106 0,0044 0,0046 0,00017 0,00055 0,0002 Với m = 4: Sai số: α1 = 1,90923 ± 0,00004 α2 = 3,19495 ± 0,00004 α3 = 5,04480 ± 0,00004 Ví dụ 2. Tìm gần đúng nghiệm của hệ phương trình sau bằng phương pháp lặp đơn: Giải. - Chọn sai số cho phép ε = 0,5.10-3. - Đưa hệ về dạng x = Bx + g; ( a ) ( b ) r0 = max (0,147; 0,1553; 0,2207) = 0,2210 < 1 - Chọn x(0) = ( 0, 0, 0 )T - Kiểm tra điều kiện hội tụ - Tính lặp theo ( b ), kết quả cho trong bảng sau: 0 0 0 0,7790 0,8243 1,3440 0,9510 0,9727 1,5209 0,9767 0,9997 1,5566 0,9805 1,0040 1,5624 0,9813 1,0047 1,5634 0,9814 1,0049 1,5635 0,172 0,1484 0,1769 0,0257 0,0270 0,0357 0,0038 0,0043 0,0058 0,0008 0,0008 0,0010 0,0001 0,0002 0,0001 - Đánh giá sai số ( i = 1, 2, 3) = 0,0000567 d/ Phương pháp ZAYDEN (SEIDEL) - Cho hệ phương trình Ax = f ; - Ta đã biến đổi về dạng tương đương: Để tăng nhanh tốc độ hội tụ, phân tích ma trận B thành tổng hai ma trận: B = B1 + B2 .Trong đó: Phương trình (27) sẽ có dạng x = B1x + B2x + g ; Tiến hành lặp theo công thức: Chú ý: - Điều kiện hội tụ cũng như trên; - Hội tụ nhanh hơn phương pháp lặp đơn; - Tiết kiệm tính toán vì các thành phần vừa tính trước được sử dụng ngay để tính các thành phần tiếp theo. Ví dụ: Giải hệ phương trình sau bằng phương pháp Zayden: Đưa về dạng x = Bx + g: Trong đó Kiểm tra điều kiện hội tụ C. Nghiệm của hệ phương trình phi tuyến. 1. Phương pháp Niutơn. a. Hệ hai phương trình: Đặt bài toán: - Cho các hàm liên tục f(x, y) và g(x, y); - Tìm các giá trị x = x* và y = y* sao cho f(x*, y*) = 0; và g(x*, y*) = 0. Cơ sở của phương pháp: Khai triển các hàm f(x, y) và g(x, y) theo chuỗi Taylo hai biến: x*, y* - nghiệm của hệ phương trình. ( 36 ) Dùng chuỗi (36) để khai triển f(x, y) và g(x, y) tại x(i) , y(i) và đánh giá chuỗi tại x*, y*, bỏ qua các đạo hàm hạng hai trở lên: ( 37 ) ( 38 ) ( 39 ) ( 39 ): hệ hai phương trình đại số tuyến tính chứa 2 ẩn Δx(i) , Δy(i) , Quá trình tính: - Chọn sơ bộ x(i) , y(i). - Lặp lại cho đến khi một hoặc cả hai tiêu chuẩn hội tụ dưới đây được thoả mãn: */ */ ( 41 ) b. Trường hợp tổng quát. Hệ phương trình: F( X ) = f1( X ), f2( X ), . . ., fn( X ); X = ( x1, x2, . . ., xn ) trong đó: ( 43 ) Trường hợp không tồn tại các đạo hàm riêng bằng giải tích, có thể xác định gần đúng bằng phương pháp số: Chú ý: - Nếu Δxi nhỏ quá thì sai số lấy tròn có thể làm hỏng lời giải; - Δxi quá lớn, tốc độ hội tụ sẽ giảm. Ví dụ: Xác định vị trí của cơ cấu bản lề 4 khâu. Biết: α – góc quay của khâu 4; Tìm góc quay các khâu còn lại theo α. Đặt ( 49 ) Quá trình giải: - Cho θ2, θ3 một giá trị gần đúng ban đầu: θ20, θ30 nào đó; Hay - Tiếp tục lặp lại cho đến khi đạt điều kiện ( 41 ). θ*2, θ*3 là nghiệm của hệ phương trình (47). trong đó: Δθ2 = θ*2 – θ2 ; Δθ3 = θ*3 – θ3 . Cho r1 = 10; r2 = 6; r3 = 8; r4 = 4; α = 400 Tìm các giá trị tương ứng của θ2, θ3. ( c ) Sơ bộ chọn các giá trị ban đầu θ20 = 300; θ30 = 00. f1 = 0,131975; f2 = 0,428850. - Bước 1. cosθ21 = 0,8431989 ; cosθ31 = 0,996625. sinθ21 = 0,537602; sinθ31 = - 0,082087. f1 = - 0,319833 ; f2 = - 0,0022345 - 0,056297.Δθ2 + 0,0114959.Δθ3 = 0,319833 0,0882989.Δθ2 + 0,1391288.Δθ3 = 0,0022345 ( d ) - Đặt θ22 = θ21 + Δθ2 ; θ32 = θ31 + Δθ3 ; Và tiếp tục quá trình giải. - Kết quả ghi vào bảng - Bước 2. θ21 = θ20 + Δθ2 = 32,520550; θ31 = θ30 + Δθ3 = - 4,708540; 0 30,0000 0,00000 0,13975 0,42855 2,52055 -4,70854 1 32,52055 -4,70854 -0,03198 -0,00223 -0,50003 0,33348 2 32,02025 -4,37506 -0,00033 -0,000115 - 0,00513 0,004073 3 32,01518 -4,370988 -0,405E-07 -0,112E-07 -0,000001 0,000000 4 32,01518 -4,370987 2. Phương pháp lặp. Hệ n phương trình phi tuyến với n ẩn số có dạng tổng quát: hay - Đưa về dạng: hay - Ví dụ: Hệ phương trình phi tuyến: - Chọn xấp xỉ ban đầu: X(0) = [x1(0), x2(0), . . ., xn(0)] - Tính xấp xỉ thứ nhất: thì α - nghiệm của hệ phương trình. - Quá trình tính dừng lại khi: ε – sai số cho phép; xi (i = 1, 2, . . ., n) - nghiệm gần đúng của hệ phương trình.