Phương pháp tính - Chương 1: Giải gần đúng phương trình phi tuyến f(x) = 0

Nội dung text: Phương pháp tính - Chương 1: Giải gần đúng phương trình phi tuyến f(x) = 0

1. BỘ MƠN TỐN ỨNG DỤNG - ĐHBK PHƯƠNG PHÁP TÍNH – HK2 0506 CHƯƠNG 1 GIẢI GẦN ĐÚNG PHƯƠNG TRÌNH PHI TUYẾN f(x) = 0 • TS. NGUYỄN QUỐC LÂN (02/2006)
2. NỘI DUNG 1– KHÁI NIỆM TỔNG QUÁT. CƠNG THỨC SAI SỐ 2– PHƯƠNG PHÁP CHIA ĐƠI 3– PHƯƠNG PHÁP LẶP ĐƠN 4– PHƯƠNG PHÁP NEWTON (TIẾP TUYẾN) 5– HỆ PHƯƠNG TRÌNH PHI TUYẾN. PHƯƠNG PHÁP NEWTON – RAPHSON.
3. 1. KHÁI NIỆM TỔNG QUÁT – CƠNG THỨC SAI SỐ Phương trình f(x) = 0 (1), f: hàm số liên tục, cĩ đạo hàm Khoảng cách ly nghiệm: Đoạn [a, b] (hoặc khoảng (a, b) ), trên đĩ phương trình (1) cĩ nghiệm duy nhất VD: Phương trình x – cosx = 0 cĩ khoảng cách ly nghiệm: ĐK đủ: [a, b] là KCLN của (1) khi ➢ Đạo hàm f’ khơng đổi dấu trên đoạn (hoặc khoảng) (a,b) ➢ f(a).f(b) < 0 (giá trị 2 đầu trái dấu) Tìm KCLN: Tính f’, lập bảng biến thiên; Cách 2: Đồ thị (máy!)
4. CƠNG THỨC SAI SỐ Cơng thức sai số tổng quát: Phương trình f(x) = 0 (1) với nghiệm chính xác trên khoảng cách ly nghiệm [a, b] f (x) x a,b: Nghiệm gần đúng đã biết x − m f '(x) m1 0  x a,b m1 = min f '(x) 1 a,b VD: P/trình f(x) = x – cosx = 0 cĩ khoảng cách ly nghiệm [0,1] a / 0.00014? Nếu chọn nghiệm gần đúng x = 0.739 x : b / 0.00015? Giải: Ghi nhớ: Sai số luơn làm trịn lên
5. PHƯƠNG PHÁP CHIA ĐƠI Ý tưởng: Liên tục chia đơi khoảng cách ly nghiệm f(x) = 0 trên KCL nghiệm [a, b]. Ký hiệu: a0 = a, b0 = b f(a0).f(b0) < 0. Chia đơi: c0 = (a0 + b0)/2 KCL nghiệm mới? a0 c0 b0 f(a0).f(c0) < 0: KCL mới [a0, c0] f(c0).f(b0) < 0 → [c0, b0] Dừng với nghiệm xấp xỉ (trung điểm ở hàng thứ n) x = cn (b − a) log b − a  Cơng thức sai số: x −  n −1 2n+1 log 2
6. VÍ DỤ PHƯƠNG PHÁP CHIA ĐƠI Xấp xỉ nghiệm của phương trình f(x) = x – cosx = 0 trên khoảng cách ly nghiệm [0, 1] với sai số 0.2 Giải: Lập bảng chứa mọi kết quả trung gian cần thiết n an bn cn n Tìm n để cĩ thể xấp xỉ nghiệm f(x) = x – cosx = 0 trên khoảng cách ly nghiệm [0, 1] bằng phương pháp chia đơi, sai số 10-8
7. DÃY LẶP ĐƠN Dãy lặp đơn: Dãy xn  xác định xn+1 = (xn), (x): hàm lặp VD: Kiểm tra những dãy sau cĩ là lặp đơn? Nếu cĩ, viết ra hàm lặp . Tính 5 số hạng đầu của dãy (x0 bất kỳ). Từ đĩ, đốn tính hội tụ? Tìm liên hệ giữa giới hạn dãy và hàm lặp x a / x = cos n n x n z n+1 10 n n 0 0 3 b / yn+1 = nyn 1 1 zn c / zn+1 = +1 2 2 15 Dãy lặp đơn xn = (xn-1) hội tụ về là nghiệm p/t x = (x)
8. DÃY LẶP ĐƠN HỘI TỤ Minh hoạ sự hội tụ của dãy lặp đơn: xn+1 = (xn) = axn + b Dãy lặp hội tụ về nghiệm p/trình: x = (x) = b/(1 – a)
9. DÃY LẶP ĐƠN PHÂN KỲ Phân kỳ Hội tụ khi dãy {xn} “co” lại x2 − x1 = (x1 )− (x0 ) q x1 − x0
10. HÀM CO Hàm y = (x) co trên [a, b] với hệ số co q  q, 0 < q < 1:  x, y a,b : (x)− (y) q x − y | ’(x)| q < 1  x [a, b] (x) co trên [a, b] với hệ số co q VD: Hàm y = x2 co trên [-1/4, 1/4]??? VD: Trong những hàm sau đây, hàm nào thoả điều kiện co? Xác định hằng số q với các hàm co đĩ a / (x) = cos x , x 0,1 b / (x) = arcsin x , x R 1 c / (x) = +1, x a,b, 0 a b x2
11. PHƯƠNG PHÁP LẶP ĐƠN ➢ Ph. trình f(x) = 0. Xác định khoảng cách ly nghiệm [a, b] ➢ Đưa pt f(x) = 0 về dạng lặp đơn x = (x), co trên [a, b] Lấy x0 bất kỳ [a,b] Dãy lặp xn+1 = (xn) → Chú ý: Nhiều cách chọn hàm càng đơn giản càng tốt Ước lượng sai số (q: hệ số co của hàm lặp đơn (x) ) qn Tiên nghiệm: x − x − x Số lần lặp tối thiểu: n 1− q 1 0 x −  q n Hậu nghiệm: x − x − x n 1− q n n−1 log (1− q) x − x  n 1 0 log q
12. VÍ DỤ PHƯƠNG PHÁP LẶP ĐƠN Xấp xỉ nghiệm ptrình f(x) = x3 + x – 1000 = 0 với sai số 10-8 Giải: Khoảng cách ly nghiệm Lặp đơn: x = 1000 – x3 = (x): Kiểm tra điều kiện co? Xây dựng hàm lặp mới: x = 3 1000 − x = (x) Hàm co? x0 9,10 Dãy lặp: 3 xn+1 = (xn ) = 1000 − xn Sai số: n xn n q x − x − x 0 n 1− q n n−1
13. CẢI TIẾN PHƯƠNG PHÁP LẶP ĐƠN Nhận xét: q = 0.0034 << 1 Hội tụ rất nhanh Vấn đề: Xây dựng hàm với q << 1? Tìm số lần lặp để xấp xỉ nghiệm x – cosx = 0 trên [0,1] với -8 phương pháp lặp đơn, x0 = 0 với sai số 10 Giải: Dạng lặp x = cosx = (x) q = x0 = 0 x1 = (x0) = 1 Ước lượng sai số tiên nghiệm: f (x) Cải tiến tốc độ: Lặp Newton f (x) = 0 x = x − = (x) f '(x)
14. PHƯƠNG PHÁP LẶP NEWTON (TIẾP TUYẾN) f (x) f(x) = 0 Dạng lặp đơn x = g(x) = x − : hội tụ nhanh f '(x) f (xn ) •Cơng thức lặp Newton: xn+1 = g(xn ) = xn − f '(xn ) •Minh hoạ hình học:
15. ĐIỀU KIỆN LẶP NEWTON – SAI SỐ • • • • Lặp Newton thất bại: • • • Điều kiện hội tụ: 1/ Đhàm f’, f” khơng đổi dấu trên [a, b] 2/ Giá trị lặp ban đầu thoả: f(x0) . f’’(x0) > 0 (ĐK Fourier) •Ước lượng sai số : Cơng thức tổng quát (chủ yếu) hoặc M 2 2 •(Phức tạp hơn) xn − (xn − xn−1) , M 2 = max f " a,b 2m1  
16. VÍ DỤ LẶP NEWTON – TIẾP TUYẾN Giải xấp xỉ f(x) = x – cosx = 0 trên [0, 1], sai số 10–8 1/ Kiểm tra điều kiện hội tụ 2/ Xây dựng dãy lặp: Sai số : n xn n 0 1
17. HỆ PHI TUYẾN – PP NEWTON – RAPHSON Minh hoạ : Hệ 2 phương trình, 2 ẩn f1(x1, x2 ) = 0 f1 2 2 x1 f (x) = 0 , f = : R → R , x = f2 (x1, x2 ) = 0 f2 x2 Ký hiệu ma trận f’(x) f1 f1 Cĩ thể tính “giá x x (ma trận Jacobi): f '(x) = 1 2 trị” f’(x(0)) tại “điểm” f f 2 2 (0) x cho trước x1 x2 Ký hiệu: (k ) k k Bộ nghiệm gần đúng ở bước thứ k x = x1 , x2 : Xem x(k) đã biết. Tính x(k+1): giải thuật Newton - Raphson 1/ Tính ma trận A = f’(x(k)) (thay x(k) vào) & vectơ b = –f(x(k)) 2/ Giải hệ p/tr (bằng máy bỏ túi) Ah = b. Tính x(k+1) = x(k) + h
18. VÍ DỤ LẶP NEWTON – RAPHSON VỚI HỆ PHI TUYẾN Tìm nghiệm gần đúng x(1) của hệ phi tuyến sau với 3 chữ số lẻ: 2 f (x , x )  x + 3ln x − x = 0 T 1 1 2 1 1 2 , x(0) = 1.5,−1.5 2 f2 (x1, x2 )  2x1 − x1x2 − 5x1 +1 = 0 Giải: Ma trận A = f’(x) b “nhỏ”: x(k) gần nghiệm n x(n) Ma trận Jacobian A Vectơ –f(x(n) ) Vectơ h 1.5 0 −1.5
19. ỨNG DỤNG THỰC TẾ: LÝ THUYẾT MẠCH Mạch điện: Nguồn (pin) V0, Điện trở R, Tụ C, Cảm ứng L di q C R U = iR,U = L ,U = R L dt C C i di q Kirchhoff: L + Ri + = 0 V0 L dt C dq d 2q dq q i = L + R + = 0 dt dt 2 dt C Rt 2 − 1 R Nghiệm: q(t) = q e 2L cos − t , q = V C 0 0 0 LC 2L Tìm R (L, C đã biết) để năng lượng tiêu hao của mạch cĩ vận –4 tốc cho trước: q/q0 = 0.01 với t = 0.05s, L = 5H, C = 10 F
20. LỜI GIẢI VÍ DỤ THỰC TẾ Biến đổi phương trình thu được (ẩn R) Rt 2 − 1 R q f (R) = e 2L cos − t − = 0 LC 2L q 0 f (R) = e−0.005 R cos 2000 − 0.01R2 (0.05)− 0.01 = 0 Khoảng cách ly nghiệm: R [0, 400 ] (2000 – 0.01R2 0) Giải thực tế: Đồ thị ❖P/p chia đơi (n = 21) ❖P/p Newton R = 328.1515 