Bài giảng Tính toán khoa học: Chương 4 - TS. Vũ Văn Thiệu

Chương 4 trong bộ bài giảng tính toán khoa học thuộc môn khoa học máy tính do tiến sĩ Vũ Văn Thiệu biên soạn trình bày về vấn đề giải phương trình phi tuyến. Nội dung cơ bản của chương 4 ngoài đề cập đến phương pháp chia dôi, phương pháp dây cung, phương pháp Newton còn hướng dẫn các kiến thức liên quan đến phương pháp cát tuyến, phương pháp lặp lại và phương pháp Bairstow. Với cách trình bày khoa học, ví dụ rõ ràng, cụ thể sẽ giúp ích cho các bạn muốn tìm hiểu, củng cố kiến thức trong vấn đề giải phương trình phi tuyến.
Nội dung trích xuất từ tài liệu:
Bài giảng Tính toán khoa học: Chương 4 - TS. Vũ Văn Thiệu CHƯƠNG 4 GiẢI PHƯƠNG TRÌNH PHI TUYẾN Nội dung Đặt vấn đề 1. Phương pháp chia đôi 2. Phương pháp dây cung 3. Phương pháp Newton 4. Phương pháp cát tuyến 5. Phương pháp lặp 6. Phương pháp Bairstow Đặt vấn đề • Phương trình phi tuyến (PTPT) – VD1: x2 = 0 – VD2: 1 + 2x + x2 - 3x3 + 7x4 = 0 – VD3: ln(x+1) = 0 – VD4: tg(x) – artg(2x) = 0 – Tổng quát: f(x) = 0 • Giải phương trình phi tuyến (root finding) – Tìm x để f(x) = 0 – X được gọi là nghiệm của PT, cũng được gọi là không điểm của hàm f • Tìm nghiệm dưới dạng công thức hiện: Khó, một số không tồn tại ( VD PT đa thức bậc lớn hơn 4) => sử dụng PP số dựa trên thủ tục lặp Giải PTPT: Một số khái niệm (1) • Sự tồn tại nghiệm – Định lý: Cho hàm f:R->R; [a,b] là đoạn phân ly nghiệm nếu f(a) và f(b) trái dấu. Nếu thêm điều kiện f liên tục trên [a,b] thì tồn tại nghiệm x* ϵ [a,b] sao cho f(x*)=0. – VD: ex + 1 = 0 vô nghiệm 2x + 3 = 0 có một nghiệm x2 + 3x + 1 = 0 có hai nghiệm sin(x) = 0 có vô số nghiệm • Độ nhạy và điều kiện của bài toán giải PTPT – Số điều kiện của bài toán tìm nghiệm x* : 1 f ( x* ) Giải PTPT: Một số khái niệm (2) • Giải PTPT bằng phương pháp lặp – Điều kiện dừng • f (x )   x*  x   • ɛ là độ chính xác cho trước – Tốc độ hội tụ: • Gọi sai số ở bước lặp k là ek = xk - x* ; xk là lời giải xấp xỉ tại bước k, x* là nghiệm chính xác. e • Dãy {ek} hội tụ với tốc độ r nếu: lim k 1  C; C ≠ 0 r k  ek – r = 1: hội tụ tuyến tính – r > 1: hội tụ trên tuyến tính – r = 2: hội tụ bình phương Giải PTPT: Phương pháp chia đôi (1) • Ý tưởng: nếu [a,c] chỉ chứa một nghiệm của PT f(x)=0 thì f(a)*f(c)≤0; [a,c]-khoảng phân ly nghiệm • Phương pháp chia đôi: Chia đôi khoảng phân ly nghiệm liên tục cho đến khi đủ nhỏ, như sau: – Chia đôi: b = (a+c)/2 – Kiểm tra: • Nếu f(b) = 0, => b là nghiệm • Nếu f(a)*f(b)≤0 thì đặt [a,b] là khoảng phân ly nghiệm mới • Nếu f(c)*f(b)≤0 thì đặt [b,c] là khoảng phân ly nghiệm mới – Lặp cho đến khi khoảng phân ly nghiệm nhỏ hơn độ chính xác ɛ cho trước Giải PTPT: Phương pháp chia đôi (2) • Độ dài khoảng phân ly nghiệm sau mỗi bước lặp: – Bước 1: (c-a)/21 – Bước 2: (c-a)/22 – Bước n: (c-a)/2n • Cho trước độ chính xác ɛ, thì số bước lặp cần thiết là số nguyên n thỏa mãn: ca ca   n  log 2 2 n   c  a • Vậy số bước lặp cần thiết là:  n  log 2    7 Giải PTPT: Phương pháp chia đôi (3) • VD: PT ex – 2 = 0 có nghiệm nằm trong khoảng [0,2]. Tìm nghiệm với sai số cho phép 0.01 – Đặt a = 0, c = 2, => f(a)*f(c) = -1*5.389 < 0 – Bước lặp 1: • Đặt b = (2+0)/2 = 1; f(b) = 0.718 • Kiểm tra: f(a)*f(b) < 0, => [0,1] là khoảng phân ly nghiệm mới – Bước lặp 2: • Đặt b = (1+0)/2 = 0.5; f(b) = - 0.351 • Kiểm tra: f(b)*f(c) < 0, => [0.5,1] là khoảng phân ly nghiệm mới – ………. Giải PTPT: Phương pháp chia đôi (4) Lần a b c f(a) f(b) f(c) Sai số lặp (độ dài khoảng PLN) 1 0 1 2 -1 0.718 5.3890 1 2 0 0.5 1 -1 -0.351 0.718 0.5 3 0.5 0.75 1 -0.351 0.117 0.718 0.25 4 0.5 0.625 0.75 -0.351 -0.132 0.117 0.125 5 0.625 0.688 0.75 -0.132 -0.011 0.117 0.0625 6 0.688 0.719 0.75 -0.011 0.058 0.117 0.03125 7 0.688 0.703 0.719 -0.011 0.020 0.052 0.015625 8 0.688 0.695 0.703 -0.011 0.004 0.020 0.0078125  2  0 • Ghi chú: số bước lặp:  n  log 2   log 2 200  8  0.01  24-Nov-13 9 Giải PTPT: Phương pháp chia đôi (5) • Yêu cầu và tính năng: – Yêu cầu phải biết trước khoảng phân ly nghiệm – Không đòi hỏi tính liên tục của đạo hàm bậc nhất – Có thể giải kiểu PTPT bất kỳ – Có thể áp dụng cho hàm không biểu diễn dưới dạng giải tích 24-Nov-13 10 Giải PTPT: Phương pháp chia đôi (6) • Bài tập: Viết chương trình Matlab giải phương trình ...