Trình bày về phương pháp tiếp tuyến GIẢI gần đúng phương trình

Khoa Xây Dựng Thủy Lợi Thủy Điện Bộ môn Cơ Sở Kỹ Thuật Bài Giảng Chuyên Đề Phương Pháp Tính Trang: 37 Chương 4 GIẢI GẦN ĐÚNG PHƯƠNG TRÌNH VÀ HỆ PHƯƠNG TRÌNH PHI TUYẾN ROOTS OF NONLINEAR EQUATIONS 4.1 Giải gần đúng phương trình Để tìm nghiệm gần đúng của phương trình f(x) = 0, ta phải tách nghiệm. Giả sử trong khoảng [a,b] hàm f(x) liên tục cùng với các đạo hàm f’(x), f”(x), của nó. Các giá trị f(a), f(b) là giá trị của hàm tại các điểm mút của đoạn này f(a).f(b) < 0 và f’(x) giữ nguyên dấu trên đoạn [a , b]. Đôi khi để cho thuận lợi, viết lại: f(x) = 0  (x) = (x). Nghiệm thực của phương trình f(x) = 0 là giao điểm của đồ thị các hàm y = (x) và y = (x). 4.1.1 Phương pháp dây cung Thay cung AB của y = f(x) bởi dây cung AB, lấy x1 tại giao điểm P của dây cung với trục hoành làm giá trị gần đúng của nghiệm chính xác . Phương trình dây cung AB: abaX)a(f)b(f)a(fY Tại P ta có: Y = 0, X = x1, nên: abax)a(f)b(f)a(f1 Suy ra: x1 = a - )a(f)b(f)a(bf)b(af)a(f)b(f)a(f)ab( Sau khi tính được x1 ta xét được khoảng phân li nghiệm mới là [a,x1] hay [x1,b] rồi tiếp tục áp dụng phương pháp dây cung vào khoảng phân li mới, tiếp tục ta được x2, x3, x4  ngày càng gần đến nghiệm chính xác . Sai số ước lượng: 31)]x('f[)x("fmax2)b(f).a(fx  x yO A B a b P X1  Khoa Xây Dựng Thủy Lợi Thủy Điện Bộ môn Cơ Sở Kỹ Thuật Bài Giảng Chuyên Đề Phương Pháp Tính Trang: 38 Ví dụ: Tìm nghiệm trong khoảng (1,1;1,4) của phương trình: f(x)= x3-0,2x2-0,2x-1,2 =0 Bằng phương pháp lặp dây cung(Với 2 lần lặp) Giải: x1 = x0-)4,1()()4,1)((0fxfxxfoo=1,1-)4,1()1,1()4,11,1)(1,1(fff=1,1-18254,1872,0331,0)3,0)(331,0( f(x1)=f(1,18254)=-0,06252 x2 = x1-)4,1()()4,1)((111fxfxxf=1,18254-19709,1872,006252,0)4,118254,1)(06252,0( 4.1.2 Phương pháp Newton-Raphson Còn gọi là phương pháp Newton hay phương pháp tiếp tuyến. Xét phương trình f(x) = 0 Khai triển Taylor hàm f(x) tại lân cận x0: f(x) = f(x0) + (x - x0) f’(x0) + )()!1()()(!)( )("!2)(11000020Cfnxxxfnxxxfxxnnnn Với: C = x0 + (x - x0), với: 0 <  < 1, có nghĩa: x0 < C < x Bây giờ ta chỉ lấy số hạng bậc 1 của chuỗi Taylor: f(x0) + ( x - x0).f’(x0) = 0 (4.1) Gọi x1 là nghiệm của (4.1), ta có: x1 = x0 - )x('f)x(f00 Tương tự: x2 = x1 - )x('f)x(f11 ,…, xn + 1 = xn - )x('f)x(fnn , với x0  [a,b] Vì (4.1) dùng thay cho phương trình f(x) = 0, nó tuyến tính đối với x nên phương pháp Newton cũng gọi là phương pháp tuyến tính hóa, f’(x0) chính là hệ số góc của y = f(x) tại x0 . Tại B(x0, f(x0)). Y - f(x0) = f’(x0).(X - x0) , tại P : x = x1 ; Y = 0 đó chính là phương trình (4.1) Khoa Xây Dựng Thủy Lợi Thủy Điện Bộ môn Cơ Sở Kỹ Thuật Bài Giảng Chuyên Đề Phương Pháp Tính Trang: 39 Hội tụ và sai số Người ta sẽ áp dụng phương pháp lặp Newton nếu nghiệm xn   khi n   Định lý: Giả sử [a,b] là khoảng phân ly nghiệm  của phương trình:f(x) = 0, f có đạo hàm f’,  f” với f’ liên tục trên [a,b], f’ và f” không đổi dấu trên (a, b). Xấp xỉ đầu x0 chọn là a hay b sao cho f(x0) cùng dấu với f”. Khi đó xn   khi n  . Cụ thể hơn xn đơn điệu tăng tới  nếu f’.f” < 0, và xn đơn điệu giảm tới  nếu f’.f” > 0 . Sai số: nx < m)x(fn , với: 0 < m < )(,nxf và   x  b Trường Hợp Lặp Newton - Raphson Không Có Hiệu Quả (hàm 1 biến) Ví dụ: Tìm nghiệm dương nhỏ nhất của phương trình f(x)= 2x -4x Bằng phương pháp Newton – Raphson với 3 lần lặp (cho x0 = 0,3) xo x1 f(x)f(x)x2x0x1x2x xf(x) X0 X1 X x f(x) O x0 x3 x1 x4 x2 xya bp OMABKhoa Xây Dựng Thủy Lợi Thủy Điện Bộ môn Cơ Sở Kỹ Thuật Bài Giảng Chuyên Đề Phương Pháp Tính Trang: 40 4.2 Giải hệ phương trình phi tuyến Ở đây ta đi giải hệ phương trình phi tuyến theo phương pháp lặp Newton-Raphson Từ khai triển Taylor cho bài toán một biến: f(xi + 1) = f(xi) + f’(xi)(xi + 1- xi) + 2i1i)xx(!2)("f vì f(xi + 1) = 0 Tổng quát hoá cho bài toán 2 biến (hàm 2 biến): iii1iiii1ii1iiii1iiii1ii1iyv).yy(xv).xx(vvyu).yy(xu).xx(uu )2.4()2.4(ba Từ (4.2a) và (4.2b) ta có: xv.yuyv.xuxvuxuvyyxv.yuyv.xuyuvyvuxxiiiiiiiii1iiiiiiiiii1i )3.4()3.4(ba Mẫu số của (4.3a) và (4.3b) gọi là định thức Jacobien (detJ), của hệ thống: yvxvyuxudetJdetiiii Một cách tổng quát cho phương trình: f(x)=0 Với x = [x1,x2, ,xn]T và f = [f1,f2, ,f n]T Phương pháp lặp Newton-Raphson cho hệ phương trình n ẩn này là: x(k+1) = x(k) -Fx-1(x(k)).f(x(k)) Với ma trận Jacobi Fx như sau: Fx=nn2n1nn22212n12111xf xfxfxf xfxfxf xfxf )x('f)x(fxxiii1iKhoa Xây Dựng Thủy Lợi Thủy Điện Bộ môn Cơ Sở Kỹ Thuật Bài Giảng Chuyên Đề Phương Pháp Tính Trang: 41 Ví dụ: Hãy tính lặp theo phương pháp Newton- Raphson 1. Cho f(x) = e-x - x , với x0 = 0 (điểm ban đầu) Giải : Ta có f’(x) = - e-X - 1 , xi + 1 = xi - 1exeiixix Ta lập được bảng tính: i xi (%) 0 0 100 1 0, 5 0 0 0 0 0 0 0 0 11,8 2 0, 5 6 6 3 1 1 0 0 3 0,147 3 0, 5 6 7 1 4 2 1 6 3 0,0000220 4 0, 5 6 7 1 4 3 2 7 0 < 10-8 2. Cho 057xy3y)y,x(v010xyx)y,x(u22 cho biết nghiệm (x = 2, y = 3) Nghiệm ban đầu cho ( x = 1,5 , y = 3,5 ) Giải: 5,1xyu25,3)5,3)(5,1(61xy61yv0000 Vậy định thức Jacobien: det J = 6,5(32,5) - 1,5(36,75) = 156,125 và u0 = (1,5)2 + 1,5(3,5) - 10 = - 2,5 v0 = 3,5 + 3(1,5)(3,5)2 - 57 = 1,625 Từ đó có: 84387,2125,156)75,36)(5,3()5,6(625,15,3y03603,2125,156)5,3(625,1)5,32(5,25,1x Tiếp tục các phần xấp xỉ bị dư  (x = 2 , y = 3) 3. Cho hàm: f(x) = - 0,9x2 + 1,7x + 2,5, điểm ban đầu x0 = 5, chọn 0 = 0,01%. 5,65,3)5,1(2yx2xu75,36)5,3(3y2 xv002200Khoa Xây Dựng Thủy Lợi Thủy Điện Bộ môn Cơ Sở Kỹ Thuật Bài Giảng Chuyên Đề Phương Pháp Tính Trang: 42 Câu hỏi: 1. Phương trình (hoặc hệ phương trình) phi tuyến thông thường có nhiều nghiệm; để giải nó (hoặc chúng nó), bước đầu tiên ta phải làm gì ? 2. Trình bày cách giải hệ phương trình phi tuyến theo công thức lặp Newton-Raphson? 3. Tại sao phương pháp lặp Newton – Raphson còn được gọi là phương pháp tiếp tuyến ? 4. Ưu nhược điểm của các phương pháp lặp để giải phương trình phi tuyến ? Bài tập: 1) Dùng phương pháp dây cung, tìm nghiệm gần đúng với độ chính xác 10-2 của: a) x3 + 3x + 5=0 b) x4-3x +1=0 2) Áp dụng hai lần phương pháp đây cung, tìm nghiệm thực gần đúng của phương trình x3-10x+5 trong khoảng phân ly(0;0,6). Đánh giá sai số của nghệm gần đúng x2. 3) Cho phương trình x=sin3x, có khoảng phân ly nghiệm là(3,6). Tìm nghiệm gần đúng trong khoảng đã cho bằng phương pháp dây cung, tính đến phép lặp thứ 3 là x3. 4) Tìm nghiệm gần đúng của hệ 02202223yxxyxyx Bằng phương pháp Newton, cho x0=0,7; y0=1,0. 5) Tìm nghiệm gần đúng của hệ bằng phương pháp lặp Newton. 85,0cos32,1yxySinx Với xấp xỉ đầu(x0, y0)=(1,80; -0,33). Đáp số: 2) 51,0 3) x3 75649,0 4) )087387,1;704402,0(,  5) )34,0;79,1(,  Khoa Xây Dựng Thủy Lợi Thủy Điện Bộ môn Cơ Sở Kỹ Thuật Bài Giảng Chuyên Đề Phương Pháp Tính Trang: 43 TÀI LIỆU THAM KHẢO 1. Phạm Kỳ Anh, Giải tích số, NXB ĐHQG, Hà Nội 1996 2. Phan Văn Hạp và các tác giả khác, Cơ sở phương pháp tính, NXB ĐH-THCN, Hà Nội 1970. 3. Nguyễn Thế Hùng, Giáo trình Phương pháp số, Đại học Đà Nẵng 1996. 4. Đinh Văn Phong, Phương pháp số trong cơ học, NXB KHKT, Hà Nội 1999. 5. Lê Đình Thịnh, Phương pháp tính, NXB KHKT, Hà Nội 1995. 6. Lê Trọng Vinh, Giải tích số, NXB KHKT, Hà Nội 2000. 7. BURDEN, RL, & FAIRES, JD, Numerical Analysis, 5th ed., PWS Publishing, Boston 1993. 8. CHAPRA S.C, Numerical Methods for Engineers, McGraw Hill, 1998. 9. GURMUND & all, Numerical Methods, Dover Publications, 2003. 10. JAAN KIUSAALAS, Numerical Methods in Engineering with Matlab, Cambridge University Press, 2005. 11. STEVEN T. KARRIS, Numerical Analysis, Using Matlab and Excel, Orchard Publications, 2007. Website tham khảo: http://ocw.mit.edu/index.html http://gigapedia.org http://ebookee.com.cn http://www.info.sciencedirect.com/books http://db.vista.gov.vn http://dspace.mit.edu http://ecourses.ou.edu http://www.dbebooks.com The end

Ý tưởng của thuật toán như sau: Ở bước lặp thứ k ta thay hàm f(x) bởi tiếp tuyến với đồ thị tại điểm xk. Nghiệm xấp xỉ tiếp theo là giao điểm của tiếp tuyến với trục hoành.

f là hàm khả vi và dễ tính giá trị đạo hàm thì phương pháp tiếp tuyến có tốc độ hội tụ nhanh.

Giả sử f(x) là hàm khả vi liên tục 2 lần trên đoạn [a,b] và thoả mãn: f(a).f(b)<0 và f’, f’’ không đổi dấu trên đoạn [a,b].

Định nghĩa: Điểm x0 gọi là điểm Fourier của f nếu:

f(x0) f’’(x0) >0

Dễ thấy với các điều kiện trên nếu một trong hai điểm a, b là điểm Fourier, thì điểm kia không là Fourier. (Vì f(a) và f(b) trái dấu, còn f’’(x) không đổi dấu)

Định lý (điều kiện hội tụ theo Furiê_điều kiện đủ)

Giả sử [a,b] là khoảng nghiệm của phương trình f(x)=0. Đạo hàm f’(x), f’’(x) liên tục, không đổi dấu, không tiêu diệt trên [a,b]. Khi đó ta chọn xấp xỉ nghiệm ban đầu x0 thuộc[a,b] sao cho f(x0)*f’’(x0) > 0 thì quá trình lặp sẽ hội tụ đến nghiệm.

Phương pháp tiếp tuyến hay còn gọi là phương pháp Fourier có tốc độ hội tụ cao.

Xấp xỉ ban đầu x0 được chọn là một điểm Fourier thuộc [a,b] kể cả a và b.

Phương trình tiếp tuyến với đồ thị y=f(x) tại xk là:

y = f’(xk) (x-xk) +f(xk);

Nghiệm xấp xỉ ở bước k+1 sẽ là nghiệm của phương trình:

f’(xk) (x-xk) +f(xk) =0

hay ta có công thức lặp:

Ta có thể chứng minh dãy trên đơn điệu và hội tụ đến nghiệm phương trình

Ước lượng sai số:

Giả sử x* là nghiệm của (4.1), đặt m = min{|f’(x)| | x∈[a,b]}. Ta có ước lượng sau:

Thật vậy, ta có

f(xn) = f(xn) – f(x*) = f’(c) (xn – x*)

nên

Vì các đạo hàm f’(x) và f’’(x) không đổi dấu trên [a,b] nên

m = min { |f’(a)|, |f’(b)| } >0

Dạng giả mã của thuật toán:

Procedure Newton

{

m= min (|f’(a)|, |f’(b)| );

x=x 0 =điểm Fourier

while (|f(x)/m|>ε) x = x – f(x) / f’(x);

// x là nghiệm gần đúng

}

Sai số ở bước n được tính theo công thức là:

Ví dụ 1: Để tính gần đúng 153 size 12{ nroot { size 8{3} } {"15"} } {} ta giải phương trình x3 -15 =0 trên đoạn [2,3]. Dễ kiểm tra thấy f(2).f(3) <0; f’(x) =3x2 >0; f’’(x) =6x>0 trên đoạn [2,3] và x0=3 là điểm Fourier và m = min{12, 27} = 12

Công thức có dạng:

Ta có x1 = 2,5556; x2 = 2,4693

Sai số |x2- x*| < |f(x2)|/m = 0,005

Vídụ2: Giải phương trình: x3 + x - 5 = 0 bằng phương pháp tiếp tuyến

Giải: - Tách nghiệm:

f(x) = x3 + x - 5

f’(x) = 3x2 + 1 > 0 mọi x

Phương trình trên có 1 nghiệm duy nhất f(1)* f(2) = (-3)*5 < 0

Vậy phương trình có 1 nghiệm duy nhất x thuộc (1, 2)

- Chính xác hoá nghiệm: f’’(x) = 6x > 0 mọi x thuộc (1, 2) f’(x) > 0 mọi x

Thoả mãn điều kiện hội tụ Furiê, áp dụng phương pháp tiếp tuyến

Chọn với x0 = 2 ( vì f(2). f’’(2) > 0)

Ví dụ 3: Xét phương trình f(x) = x3 - 3x + 1 = 0 trong khoảng cách ly nghiệm [0,1/2]. Ta có

Chọn x0 = 0 thỏa điều kiện Fourier.

Kết quả tính toán theo công thức lặp Newton cho ta bảng sau: