Giáo trình Tính toán khoa học: Phần 2

Chia sẻ: Nguyệt Thượng Vô Phong | Ngày: | Loại File: PDF | Số trang:205

Thêm vào BST

Báo xấu

11
lượt xem 3
download

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

Phần 2 của cuốn giáo trình "Tính toán khoa học" tiếp tục cung cấp cho bạn đọc những nội dung chính gồm: Chương 4 - Giải phương trình phi tuyến; Chương 5 - Tính gần đúng đạo hàm và phân tích; Chương 6 - Bài toán giá trị ban đầu đối với phương trình vi phân thường; Chương 7 - Các phương pháp cực tiểu hóa không ràng buộc; Chương 8 - Quy hoạch tuyến tính;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Tính toán khoa học: Phần 2

Chương 4 GIẢI PHƯ Ơ NG TRÌNH PHI TUYẾN 4.1. ĐẬT VÁN ĐÈ Cho hàm / , ta cần tìm X thỏa mãn: m = 0. Lời giải X được gọi là nghiệm của phương trình và cũng gọi là nghiệm (không điểm ) cúa hàm f. Bài toán đặt ra được gọi là giải phtnmg trình/tìm nghiệm (root finding). Ví dụ: X* = 0 là không điểm của hàm fị x ) = X, J[x) = X2, j(x) = ln(x+l). X ét một số ví dụ khác về các phương trinh phi tuyến: 1. 1 + 4 * -1 6 jt2 + 3x 3 -3jc4 = 0. 2. j{x) - a = 0 . , x(2.1 - 0 .5 x ) ,/2 - 3 6 9 = 0 ( ữ < x < 1). (1 -JC)(1.1 -0 .5 jc >i/2 4. tg(jf) = tanh(2jr). Phương trinh đầu tiên là một phương trinh đa thức, phương trình như vậy có thể coi là phương trình đặc trưng của công thức đệ quy tuyến tính. Việc giải phương trình trong ví dụ 2 tương đương với việc tín h / “'(a ) với f[x) là m ột hàm nào đó v à / 1 là hàm ngược của nó. Ví dụ 3 là trường hợp đặc biệt của 2. Ví dụ 4 là một phương trình siêu việt. M ột trong những lý do đầu tiên giải thích tại sao chúng ta phải giải các phương trinh phi tuyến bằng các phương pháp số là các phương trình phi tuyến thưcmg không có lời giải dưới dạng công thức hiện, ngoại trừ một số rất ít các phương trình đặc biệt. Ví dụ, công thức nghiệm cho các phương trình đa thức với bậc không quá 4 tồn tại, nhưng không có công thức nghiệm cho các đa thức bậc lớn hơn 4. Chính vì vậy, đề tim nghiệm của các phương trinh phi tuyến chúng ta cần sù dụng các phưorig pháp số dựa trên các thủ tục lặp. 199
Sự tồn tại và duy nhất nghiệm Vấn đề tồn tại và duy nhất nghiệm đối với phương trình phi tuyến phức tạp hơn rất nhiều SO với trường hợp tuyến tính. Đối với hàm '/: /?— R, đoạn [a, 0] được gọi là đoạn phân ly nghiệm nếu hàm / có > dấu trái ngược tại hai đầu mút. N ếu / l à hàm liên tục và sign(/(a)) * signựịb)) thì định lý về giá trị tning bình . * * khăng định sự tôn tại của X e [a, b] sao daoJ[x ) = 0. Phương trình phi tuyến có thể có một số lượng tùy ý nghiệm , chẳng hạn: 1. ex + 1 = 0 không có nghiệm. 2. e_x - X = 0 có m ột nghiệm. 3. X2 - 4 sin(jr) = 0 có hai nghiệm. 4. X3 + 6x2 + 1 ìx - 6 = 0 có ba nghiệm. 5. cos(x) = 0 cỏ vô số nghiệm. Phương trình phi tuyến có thể có nghiệm bội, tại đó cà hàm đã cho và đạo hàm của nó đều bằng 0 . V í dụ: Phuơng trình X - 2x + 1 = 0 có X = 1 là nghiệm bội 2. Còn phương trình X3 - 3X2 + 3x - 1 = 0 có X = 1 là nghiệm bội 3. Độ nhạy và điều kiện cùa bài toáti giải phinm g trình Điều kiện của bài toán giải phương trình đối nghịch với điều kiện của bài toán tính giá trị hàm. G iá trị tuyệt đối của số điều kiện của bài toán tìm nghiệm x ’ của hàm t h ự c / R -» R là l / | / ’(*‘) |. N ghiệm X* được gọi là điều kiện tồi nếu đường tiếp tuyến với đồ thị tại điểm cỏ hoành độ X* gần như nằm ngang (xem hình minh họa bên dưới). T rong trường hợp riêng, nghiệm bội có điều kiện tồi. Đ iều kiện tốt Điều kiện tồi Hình 1. Vồ đlèu kiện của bài toán 200
Thủ tục lặp Các phương trinh phi tuyến thường không có lời giải dưới dạng công thức hiện, ngoại trừ một số rất ít các phương trình đặc biệt. Chính vì vậy, để tìm nghiệm của các phương trinh phi tuyến chúng ta cần sử dụng các phương pháp sổ dựa trên các thủ tục lặp. Điều kiện dừng trong các thủ tục lặp Thông thường tiêu chuấn kết thúc cùa các thủ tục lặp giải phương trình phi tuyến là: I.Ẩ Ĩ)I 1 - tốc độ hội tụ trên tuyến tính; - r = 2 - tốc độ hội tụ bình phương. Hiện nay có rất nhiều phương pháp số để tìm nghiệm của phương trình phi tuyến. Tuy nhiên mỗi phương pháp đều có những ưu điểm và khuyết điểm riêng. Vì vậy, chúng ta cần biết được những đặc trưng cơ bản của mỗi phương pháp để vận dụng chúng vào việc giải các phương trình phi tuyến xuất hiện trong thực tế ứng dụng. Các tính năng cơ bản và các điều kiện áp dụng của m ột số phương pháp thường dùng để giải các phương trình phi tuyến được tóm tắt trong bảng sau: 201
Cần biết Đỏi hỏi tính Kiếu Phương pháp khoảng liên tục củaphươ ng Tinh năng đặc biệt khác phân ly đạo hàm bậc 1 trình nghiệm Chia đôi Có Không Bất kỳ Có thể áp dụng với hàm không (Bisection) cho dưới dạng giải tích. Dây cung Có Có Bất kỳ Hội tụ chậm khi khoảng lớn. (False position) Newton K.hông Có Bất kỳ Hội tụ nhanh, c ầ n tín h / . Cát tuyến Không Có Bất kỳ H ội tụ nhanh. (Secant K hông cần t í n h / . Method) Lặp Không Có Bất kỳ Có th ể không hội tụ. Bairstow Không Có Đa thức N hân tử b ậc 2. Có thể tìm nghiệm phức. Hai phương pháp đầu đều có đặc điểm chung là đòi hỏi phải biết khoảng phân ly nghiệm. Vì vậy, để sứ dụng các phương pháp này, chúng ta phải tìm cách xác định trước khoảng chứa nghiệm cần tìm. Phương pháp Newton và phương pháp cát tuyến cần có giá trị phỏng đoán ban đầu để tìm nghiệm và không đòi hỏi đánh giá khoảng chứa nghiệm . Phương pháp lặp (thay thế liên tục) là thuật toán lặp đơn giàn nhưng trờ ngại của nó là phép lặp không phái lúc nào cũng hội tụ. Phương pháp Bairstow chi hạn chế sử dụng đối với các đa thức. Phương pháp này có thể tìm được tất cả các nghiệm kể cả nghiệm phức m à không đòi hôi bất cứ thông tin gì, tuy nhiên phương pháp có thề không hội tụ. 4.2. PHƯƠNG PHÁP CHIA ĐỒI Phương pháp chia đôi là một phương pháp đơn giản và an toàn để tìm nghiệm trong khoảng xác định chi chứa một nghiệm đã biết (khoảng phân ly nghiệm ). Đ iểm mạnh của phư ơng pháp là nó làm việc ngay cả với các hàm không cho dưới dạng giải tích. Giả sử giữa khoảng [a, c] chì có m ột nghiệm . Phương pháp chia đôi dựa vào tính chất sau: nếu khoảng [a, c] chi có một nghiệm thì giá trị f[ x ) tại hai đầu múttrái dấu nhau hoặc một trong hai giá trịX
M ô tả phirơng p h á p Phương pháp thực hiện tìm nghiệm của phương trinh bằng cách thu nhò dần khoảng phân ly nghiệm . C húng ta sẽ chia đôi liên tục các khoảng phân ly nghiệm tim được trong quá trinh tính toán. Trước hết chia đôi khoảng [a, c] với điềm chia b = (a + c)/2. N ếu J[b) = 0 thì b là nghiệm đúng cần tìm. Thông thường J[b) * 0. Khi đó khoảng phân ly nghiệm m ới đư ợc tìm ra nhờ kiềm tra dấu /[a)f[b) và J[b) Jịc). Nếu J{a)/[b) < 0 thì khoảng phân ly nghiệm mới là [a, b]. Ngược lại j[b) cùng dấu với f[a), tức là trái dấu với J[c) thì khoảng phân ly nghiệm mới là [b, c]. Quá trình trên được lặp lại Hên tục cho đến khi khoảng phân ly nghiệm có độ dài nhò hơn giá trị e cho trước. Sau bước lặp thứ nhất, độ dài khoảng phân ly nghiệm là: (c - a)/2l. Sau bước lặp thứ hai, độ dài khoảng phân ly nghiệm là: (c - ứ)/22. Sau bước lặp thứ n, độ dài khoảng phân ly nghiệm là: (c - a)/2". N hư vậy nếu như cho trước độ chính xác £ thì số bước lặp cần thiết sẽ là số nguyên n nhò nhất thỏa mãn: c-a 2 --------< £ , n hay tương đương: Vi vậy n = *og2 — £ Chẳng hạn, nếu c - a = 1 và e = 0.0001 thỉ cần lấy n = 14. Ví dụ: Biết phương trình ex - 2 = 0 có nghiệm nằm trong khoảng [0, 2]. Hãy tìm nghiệm với sai số cho phép 0 .0 1 bằng phưcmg pháp chia đôi. Khoáng phân ly nghiệm [0, 2] có nghĩa là a = 0; c = 2,J[a) = = 5.3890. Chia đôi khoảng phân ly bởi điềm b = (2 - 0)/2 = 1;J(b) = 0.7182. Vậy khoảng phân ly nghiệm cho lần 2 là [0, 1], Chia đôi khoảng phân ly nghiệm [0, 1] bời điểm b = (1 + 0)/2 = 0.5, Jịb) = -0.3512. Vậy khoảng phân ly nghiệm mới là [0.5,1], Các bước lặp tiếp theo được tiến hành tương tự cho đến khi đáp ứ ng độ chính xác đòi hỏi. Giá trị cuối cùng của b được coi là lời giải. 203
Lần lặp a b c m f(b) f(c) Sai so 1 0 1 2 -I 0.7182 503890 1 2 0 0.5 1 -1 -0.3512 0.7182 0.5 3 0.5 0.75 1 -0.3512 0.1170 0.7182 0.25 4 0.5 0.625 0.75 -0.3512 -0.1317 0.1170 0.125 5 0.625 0.6875 0.75 -0.1317 - 0 .0 1 1 2 0.1170 0.0625 6 0.6875 0.7187 0.75 - 0 .0 1 1 2 0.058 0.1170 0.03125 7 0.6875 0.7031 0.7187 - 0 .0 111 0 .0 2 0 0 0.0518 0.015625 8 0.6875 0.6953 0.7031 - 0 .0 1 1 2 0.0043 0 .0 2 0 0 0.0078125 G iá trị gần đ ú n g th ứ 8 với n g h iệm b = 0.6953. G iá trị sai số lớn n h ất là 0.0078 < 0.01 th ỏ a m ãn y êu cầu đ ặt ra. Gợi X * là nghiệm chính xác c ú a j ị x ) trên đoạn [0, 1], Ký hiệu e„ = max{x* - a„, bn- x * } chênh lệch lớn nh ất SO v ớ i hai đầu mút c ũ a [ a n, b n] là đoạn phân l y thứ 71. Đoạn chương trình M A TLA B dưới đây sẽ thực hiện phương pháp chia đôi và vẽ đồ thị của hàm: y (n ) = - \ o g 2(e„) , n = 1 ,2 ,... % Giải phuong trình phi tuyến bằng phuong pháp chia đôi eps=lnput('Cho do chinh xac = ') ; a=0; b = l ; n=round (abs(log((b-a)/eps) )) ; en=zero5(n,l); x s = 0 .56714329030365; f=inline('1/(x-exp(-x))'); f«=f(a); fb=f(b); k=l; en(l)= b-a; done = 0; while abs(a-b) > eps & ~done c = (a+b)/2; fc = f(c); if fa*fc < 0 % Left half b = c; fb = fc; elseif fc*fb < 0 % Right half a = c;fa = fc; else % Exact solution done = 1 ; 204
end k=k+l; en(k)= max(b-xs, xs-a); end p l o t (1:k ,-log2(en),'r o '); title('-log_2(e_n) verus n 1); Đồ thị cùa -lo g 2(e„) phụ thuộc vào n (xem hình vẽ bên dư ới) cho thấy e„ = c.2~". M e>Wrsn r 0u ) 15 10 5 0_ 0 6 10 16 20 26 Nhận xét - Để sử dụng phương pháp chia đôi cần xác định đư ợc khoảng ban đầu có đúng m ột nghiệm vàjịa)f{c) < 0. Tuy nhiên điều kiện j[ấ)J[c) < 0 có thể được thỏa mãn khi khoáng đã cho chứa một số lẻ nghiệm (hình ba). Trong trư ờ n g hợp này phương pháp chia đôi chỉ tìm ra được một trong các nghiệm phân biệt trong khoảng đã cho. - Phương pháp chia đôi không tim ra được nghiệm kép, tức là khi đồ thị hàm f[x) tiếp xúc với trục hoành (xem hình 3). - Trong trường hợp hàm J{x) có những điểm không xác định (điểm kỳ dị), phương pháp chia đôi có thể coi những điểm này là nghiệm bời vì nó không phân biệt được sự khác biệt giữa nghiệm và điểm kỳ dị (xem hình 4). Đ ể loại bỏ khó khăn này, chương trình phải kiểm tra xem ựịc) - J \ a )\ có hội tụ tới 0 hay không. N ếu đại lượng này không hội tụ, thì phương pháp có xu hướng tìm ra đ iểm kỳ dị hom là tìm ra nghiệm. - Để tìm ra khoảng chứa nghiệm có thể vẽ đồ thị hàm sổ. 205
Hình 2. Nhiểu nghiệm Hình 4. Điềm k ỳ dị
4.3. PHƯƠNG PHÁP DÂY CUNG M ô tà p h ư ơ n g p háp Phương pháp dây cung được xây dựng dựa trên phép nội suy tuyến tính. Tương tự như phương pháp chia đôi, phương pháp dây cung cũng tiến hành việc thu nhó dần khoảng phân ly nghiệm sau mỗi bước lặp. Tuy nhiên, thay vì chia đôi khoảng phân ly nghiệm một cách đơn điệu, nó sử dụng một đường thẳng đi qua hai đầu mút cúa khoảng phân ly - dây cung để tìm nghiệm. Vì vậy, nếu hàm có dạng phép nội suy tuyến tính thì nghiệm tìm được có độ chính xác cao và dãy các phép lặp sẽ hội tụ nhanh tới đích hơn phương pháp chia đôi. Già sử [a, c] là khoảng phân ly nghiệm. Phương trình đưcmg thẳng đi qua hai điểm A(ừ,y(a)) và B(c,y(í:)) (dãy cung AB) là: y = f(a ) + f ( c ) ~ f ( a ) ( x - a ) c-a hay giải theo X ta thu được: x = a + ------ ^ ------------ { y - f ( c) ~ / ( a) Từ đó suy ra hoành độ giao điểm của dây cung với trục hoành là (đ ặ t^ = 0 trong phương trình cuối): b - a -------- 1 . Sau khi tìm được b, đoạn [a, c] được chia làm hai khoảng [a, è] và [b, c]. N ếu J(a)J{b) < 0 thi nghiệm nằm trong khoảng [a, b]\ nếu ngược lại nghiệm sẽ nằm trong khoảng [b, c]. C ác đầu m út của đoạn chứa nghiệm lại được đặt tên lại là a và c, quá trinh được lặp lại với đoạn thu được cho đén khi đạt được độ chính xác đòi hỏi với nghiệm . N hược điểm lớn nhất của phương pháp là sự hội tụ chi được thực hiện từ một phía (hình vẽ 5) nên chậm, nhất là trong trường hợp đoạn chứa nghiệm rất lớn hoặc hàm có dáng điệu khác hẳn đường thẳng trong đoạn phân ly. Với những trường hợp như vậy có thê sứ dụng phương pháp dây cung cải tiến. Trong phương pháp này, nếu giá tr ị/ c ủ a đầu mút không thay đổi trong hai lần lặp liên tiếp thì bước tiếp theo sẽ tiến hành chia đôi đoạn phân ly. Ket auả, giá trị cùa phép nội suy tuyến tính sẽ gần với nghiệm hơn. 207
A(a,y(a)) Hình 5. Minh họa cho p h ư ơ n g pháp dây c un g 4.4. PHƯƠNG PHÁP NEWTON M ô tả p h ư ơ n g p h áp Phương pháp Newton được sừ dụng để tìm nghiệm của phương trình nếu như cho biết m ột xấp xi đầu của nghiệm. Ý tưởng cơ bản của phương pháp là thay phương trinh/fx) = 0 phi tuyến đối với X bằng m ột phương trinh gần đúng, tuyến tính đổi với X . Phương pháp được xây dựng trên nền tảng của khai triền Taylor. Đ ịn h lý (Khai triển T ay lo r với phần dư): Già sù f , f (n) liê n tục trên [a,b] và / (n+1)(x) tồn tại với mọi X e (a,b). Khi đó tìm được số ị e (a,b) sao cho: m = / ( « ) + ( b - ò ) f Xa ) + f "(ứ) + ... + /(*) 2 ! n\ Ạ b -a Ỵ ' („ + u (n + 1)! Xét phưomg trình J[x) = 0. Khai triển Taylor cùa j{x) tại lân cận nghiệm xấp xi ban đầu Xo là: 0 =J[x) =fixo) + f ' ( x 0)(x - Xo) + 0 ( h 2) trong đó: h - X - Xo- 208
Giải phương trình xấp xi: + f ' ( x 0) ( x - x o) = 0 theo X sẽ không thu được nghiệm chính xác, do sai số xấp xi hàm, nhưng lời giải thu được X\ sẽ gần với nghiệm đúng hơn giá trị khởi tạo x 0. Do đó, bằng cách lặp lại phương pháp với nghiệm xấp xi mới thu được, việc đánh giá độ chính xác cùa lời giải sẽ được cải thiện liên tục. Thuật toán có thể được mô tả qua hình vẽ: Hình 6. Minh họa cho p h ư ơ n g pháp Newton G iả sử Xo là giá trị xấp xì khởi tạo tùy ý của nghiệm. Vẽ tiếp tuyến với ß x ) tại điềm (at0, Vo)- T iếp tuyến này cắt trục hoành tại * 1 và X\ được nhận là một xấp xi mới cho nghiệm. Lập lại thủ tục trong đó xấp xi nghiệm mới thu được ( X | ) được sừ dụng thay cho xấp xi khởi tạo ( * o ) cho chu kỳ lặp tiếp theo. P h ư ơ n g trìn h tiếp tuyổn v ái J ịx ) đi qua (.Vu^'d) là: g(x) = f ( x 0) ( x - x 0) +f[x0). Do g(x) triệt tiêu tại XỊ nên suy ra: /(* o ) f ' ( x 0y Tóm lại, thủ tục lặp Newton để giải phương trìn h /fx ) = 0 được mô tả như sau: - Chọn lời giải xấp xỉ xuất phát Xo- - X ây dựng dãy xấp xi theo công thức sau: 209
Khi tính toán, có thể dừng thủ tục lặp tại bước lặp k nếu !_/(**) Ị < £, trong đó £ là độ chính xác cho trước. Nhận xét: Phương pháp Newton đòi hỏi tính đạo hàm bậc nhất. Đ iều đó có thể là trở ngại lớn. Trong những trường hợp như vậy, đạo hàm bậc nhất có thể được tính bởi giá trị gần đúng. Ví dụ f'(x ¡- 1) có thể được tính: / l^í-l >- h với h là giá trị rất nhỏ (chẳng hạn, 0 .0 0 1 ). Sai số nhỏ gây ra trong phép tính sai phân không ảnh hường lớn đến độ chính xác của kết quả cuối cùng. N ếu hàm không có những điểm kỳ dị ở lân cận nghiệm , cả hai phương pháp tín h /'(•*) ở trên đều làm việc tốt. Còn nếu tồn tại, cần phải lựa chọn hoặc phương pháp này, hoặc phương pháp kia tùy theo vị trí điểm kỳ dị. Tính hội tụ địa phương của phương pháp Newton là rất hấp dẫn. Giả sử X là không điểm cùa Tí*) và đặt e„ = x „ - X là sai số trong lần lặp thứ n. G iả thiết rằng: - f { x ) và f ' { x ) tồn tại và liên tục; - Xo đủ gần X . Khi đó có thể chứng minh được rằng: trong đó: ệ là điểm giữa x„ và x ' . Nói cách khác: Ta gọi sự hội tụ này là' hội tụ bình phương. Như vậy, đối với hàm đủ trơn và ta bắt đầu từ điểm gần nghiệm thì sai số được gần như là bình phương sau mỗi bước lặp. Có rất nhiều định lý về điều kiện đủ đối với lời giải xuất phát đảm bảo sự hội tụ của phương pháp Newton. Các định lý này đều đòi hỏi những kiểm tra rất phức tạp và như ví dụ m inh họa, dưới đây ta trinh bày một định lý như vậy. Đ ịnh lý: G iả s ử / l à khả vi liên tục tới đạo hàm cấp hai, Xo là đủ gần nghiệm X* c ủ a / v à / ’(**) * 0. Khi đó phương pháp Newton hội tụ đến X* và cuối cùng tổc độ hội tụ là bình phương; nghĩa là tồn tại hằng số c* = \f " (x * ) !{ 2 f\ x * ))\ sao cho: lim 1 r' *-**■ I —JC I2 I 210
Trước khi nêu chứng minh định lý ta đưa một vài nhận xét về nội dung định lý. Tốc độ hội tụ bình phương mô tả trong định lý cỏ nghĩa là với k đủ lớn, sự hội tụ sỗ rất nhanh. N ếu c là hằng số lớn hơn c * , thì từ khẳng định của định lý suy ra có thể tìm được K sao cho với mọi k > K: í C \ x k - x * \ 2. C hẳng hạn, nếu c = 1 và - x * | = 0.1 thì ta có [x*+i - x*\ < 10 2, ịx/c+2 - -**1 á 10 A ... Đ iều kiện nêu trong định lý vẫn còn mập mờ: ta đòi hỏi X o là đủ gần X*, vậy chính xác thế nào là đủ gần và có thề kiểm tra điều kiện này như thế nào? M ặc dù có thể chi ra cuối cùng tốc độ hội tụ là bình phương nhưng không chi ra được sau bao nhiêu bước lặp thì đạt được tốc độ này. Điều này lại cũng phụ thuộc vào việc lời giải xuất phát gần nghiệm đến mức độ nào. Hai vấn đề trên được nêu cụ thể trong chứng minh định lý. C hứng minh định lý hội tụ Xét phân tích T aylor tại xk là điểm trong lân cận của X*: 0 = /(*„) + (X - x ữ) f ’( x ũ) + ( x ' ~ * o)ĩ f ' \ Ẹ ) trong đó: Ç là điểm nằm ừong khoảng giữa Xo và X*. T rong công thức trên thay Xo bói Xk ta suy ra: /(**> ư - x kf f \ ậ k) * f\x t) 2 f \ x k) trong đó: là điểm nằm trong khoảng giữa Xk và X*. T rừ vể với vế công thức này với công thức lặp: **+1 = xk ~ A xk)ỉf(x k\ ta suy ra: , . x >= £ M ã . ự - Xh) \ n 2 f \ x k) Bây giờ d o / ’ là liên tục vàf { x * ) * 0, nếu C*=\f"(x*)IỌf{x*))\ thì với mọi c> c* luôn tỉm được một khoảng chứa X* trong đó < c. Nếu với một K nào đó, X* n ằm trong khoảng này và nếu |jc* - **1 < l/c (điều này là chắc chắn có, ngay cả đối với K = 0, nếu đòi hỏi Xo đủ gần X*), thì từ công thức (*) suy ra: |x*+ i - j c * | £ C | x * - x * | 2 < | x * - . x * | , vì thế Xk* 1 cũng nằm ừ ong khoảng này và thỏa mãn 1**+! - x * | < 1 1C. 211
Bằng quy nạp ta có thể chi ra rằng Xfr thuộc khoảng này với mọi k > K và vì vậy, theo (*), sẽ thóa mãp' \xk„ - x * \ < c \ x k - x * \ \ * i X i Từ đó suy ra Xk -> X , khi /r — 00. Cuôi cùng, do > xk và cả £,* đêu hội tụ đen X* nên từ (*) suy ra: if ü iZ £ Ü = /" (Ă ) I* * -* I2 2 f \ x k) Định lý được chứng minh. Nếu như các giả thiết đối với sự hội tụ không được thỏa mãn, phương pháp Newton có thể không tin cậy được nữa. Neuyfx) không có đạo hàm cấp m ột và cấp hai giới nội và liên tục hoặc điểm xuất phát không ờ gần nghiệm, thỉ sự hội tụ địa phương nói trên không được đảm bảo nữa và hơn nữa chúng ta có thể gặp tình huống hội tụ rất chậm, thậm chí không hội tụ. V í dụ: 1) Sử dụng phương pháp Newton để tìm nghiệm của phương trình: J [ x ) = x 2 - 4 sin(jc) = 0 . Ta có: f ( x ) = 2x - 4 cos(x), do đó công thức lặp của thuật toán Newton đối với phương trình đang xét là: x ... xl - 4 s i n ( . r J 2 * ,- 4 co sto )’ Lấy nghiệm xấp xỉ xuất phát X o = 3. Đoạn chương trinh trên M A TLA B dưới đây sẽ thực hiện hai bước lặp của thuật toán Newton, hiển thị vị trí nghiệm xấp xi bời ngôi sao đỏ, điểm trên đồ thị cùa hàm bởi nốt tròn xanh. clear hold off f=inline('x.A2 - 4*sin(x)'); fd=inline('2.*x - 4*cos(x)'); x = 0 .5:0.01:3.5; y=f(x) ; plot(x,y); hold on plot([0.5 3.5],[0 0],'r') % vẻ trục hoánh x=n ; 212
y=[] ; x=[x 3]; y=[y f(x(l))]; for i= 2:3 x=[x x(i-l)-f(x(i-l))/fd(x(i-l))]; y=[y f (x (i) ) ] ; end plot(x,y,'o '); % hiển thị điểm trên dồ thị plot(x,[0 0 0],'rp'); % hiển thị nghiệm xấp xi fprintf('\n X f(x) ’) fprintf ('\n ====== = = = = = = = = = = = 1) for i=l:3 fprintf('\n %f %f ',x(i), y(i)) end X f (X ) 3.000000 8.435520 2.153058 1.294773 1.954039 0.108439 Hình 7 Tim nghiệm theo p h ư ơ n g pháp Newton . 2) Tính căn bậc hai cùa 2. Ta áp dụng phương pháp N ew ton tìm nghiệm cùa phương trinh X 2 - 2 = 0. Do j { x ) = X - 2, f ’(x) = 2x, nên công thức lặp của phương pháp Newton sẽ là: X2 - 2 -t t+l — Ak - í X r - ~ --- > ¿ = 0 1*1 J ■ •• 2 ^* 213
Ký hiệu e* = Xk - \ Ị Ĩ . Đoạn chương trình sau đây nhập vào số bước lặp n, nghiệm xuất phát x 0 \ tính và đưa ra X i,, e* với k = 0 , 1 , n. n=input('Nhap vao SO buoc lap n = '); x(l)=input('Nhap vao nghiem xap xi xuat phat xO = '); can2=sqrt(2); fprintf('\n k X e(x) ') fprintf (' \ n ----------- ===== --- =======\ n ') fprintf(' %f%f\n',x(l), x(l)-can2) for k=l:n x(k+l)= X (k) - (x (k) A2-2) / (2*x ( c ) ; l) fprintf('% 4 .0f %12.9f %12.10f \n',k, x(k+l), X(k+1)-can2) end X e(x) 2.000000 0.585786 1.500000 0.085786 1.416667 0.002453 1.414216 0.000002 Nhận xét: Phương pháp Nevvton hội tụ tới 7 2 với mọi nghiệm xấp xi xuất phát x 0 > 0, hội tụ tới - \ [ ĩ vói Xữ < 0, không làm việc nếu Xo = 0. 3) Trong ví dụ này chúng ta sẽ thấy phương pháp Newton sẽ lặp vô hạn. Bước lặp: /( * .) ’■ / '( * „ ) sẽ vòng lại và quẩn tại điểm a nếu: *»+1 - a = - ( x n - a ) Điều đó xảy ra k h i/ĩ* ) thỏa mãn: x. a. m H x . aị f\x ) 214
hay là: / '( * ) 1 f(x ) 2( x - a ) ' Giải phương trinh vi phân này, ta tlm được: f ( x ) = s ig n (;t - a ) y j \ x - a \ . Rõ ràng không điềm của hàm này là x ’= a. Để trực quan, ta sẽ vẽ đồ thị của hàm/(;c) với a = 2, nhờ sử dụng lệnh M ATLAB: ezplot('sign(x-2)*sqrt(abs(x-2))',0,4) Hình 8. P hương pháp Newton k hô ng hội tụ D ễ thấy, nếu ta vẽ tiếp tuyến đối với đồ thị tại điểm bất kỳ, thì nó luôn cắt trục X tại phía đối diện với đường thẳng x = a. Phương pháp N ew ton lặp vô hạn, không hội tụ m à cũng không phân kỳ. T rong trường hợp này sự hội tụ của phương pháp không được đảm bảo v ì f ( x ) không bi chăn khi X —> (7. 4.5. PHƯƠNG PHÁP CÁT TUYẾN M ô tả phutm g pháp Phương pháp cát tuyến thay việc tính đạo hàm trong phương pháp N ew ton bởi việc tính sai phân xấp xi dựa trên hai bước lặp liên tiếp. Thay vì vẽ tiếp tuyến đối với đồ thị c ù a fịx ) tại m ột điểm , chúng ta sẽ vẽ cát tuyến đi qua hai điểm. Thao tác tiếp theo là tìm giao điểm của cát tuyến với trục X . T hủ tục lặp đòi hỏi phải có hai điềm xuất phát Xo, X{. Các bước lặp tiếp theo được thực hiện theo công thức: 215
«- Công thức này cho thấy, để thu được phương pháp cát tuyến, ta đã thay fị x „ ) trong phương pháp N ew ton bằng s„ là hệ số góc của cát tuyến. Hình 9. Minh họa p h ư ơ n g pháp cát tuyén Phương pháp cát tuyến có ưu điểm hơn phương pháp N ew ton ờ chỗ nó không đòi hỏi tính đạo h à m /( x ) . Đặc tính hội tụ cùa nó cũng gần tương tự. Giả s ừ / ( x ) và f ' ( x ) là liên tục, khi đó có thể chứng minh: 2 f(ặ ) trong đó: ệ là điểm giữa x „ và X . Đây là sự hội tụ trên tuyến tính. Có thể chi ra là: e.«+I trong đó: (Ị) là tỷ lệ vàng ( ộ = (1 + - J Ĩ ) / 2 ) . Trên thực tế tốc độ hội tụ này nhanh gần như phương pháp Newton. N hư là bài tập, hãy tính toán theo phương pháp cát tuyến để giải phương trinh fị x ) = 0 với: f ( x ) = sig n (x - a ) y j \ x - a \ . Ví d ụ : Đoạn chương trình trên M ATLAB sau đây minh họa cho phưcmg pháp cát tuyến giải phương trình: -x/2 f[ x) = e sin(3x) = 0. 216
G iá trị của nghiệm xấp xi xuất phát X o nhập bằng cách kích chuột vào điểm trên đồ thị cùa hàm J(x). x ấ p xì thứ hai được đặt là *1 = Xo + 0 .1. Tại mỗi bước lặp ta vẽ cát tuyến và hiển thịvị trí của hai điểm xấp xi liên tiếp và (x„, f„) tương ứng bằng hình ông sao đỏ và nốt tròn xanh. % close all; clc; clear; f = inline('e x p (-x/2).*sin(3*x)’); display(' PHUONG PHAP CAT T U YEN'); display (1= = = = = = = = = = = = = ------') ; display('Nhap vao doan khao sat [a, b ] '); a=input('Cho mut trai a = '); b=input('Cho mut phai b = '); eps=input('Cho do chinh xác eps = '); xvals = linspace(a,b,100); fvals = f(xvals); p l o t (xvals,fvals,xvals,0*xvals) set(gcf,'Position', [53 81 856 585]) axis ([0 10 -1 1]) title('Click in starting V a l u e F o n t s i z e 1,14) [x0,y] = ginput(1); fO = f(xO); xc = x 0 + 0 .1; k=l ; while abs(xc-x0)> eps % Tinh gia tri ham va xap xi cua dao ham £a “ £ (k c) / fpc = (fc-fO) / (xc-xO) ; % Hien thi ham va duong cat tuyen... Lvals = fc + fpc*(xvals-xc); plot(xvals,fvals,xvals,0*xvals) hold on; plot(xvals,Lvals,'r',xc,fc,'*r',x0,f0,'ob') xlabel(sprintf(1Iteration = %ld xc = %10.6f fc = %10.3e’,k,xc,£c),'Fontsize',14) a x i s ([0 10 -1 1J) 217
hold off; pause % Chuan bi cho buoc lap tiep theo... xO = xc; fO = fc; xc = xc - fc/fpc; k = k + l; end fprintf(1 Nghiêm xap xi X = %10.6f Gia tri do lech = %10.7f \ n 1,xc,f(xc)); fprintf('So buoc lap : %d \ n ', k ) ; 4.6. PHƯƠNG PHÁP LẠP T rong nhiều trường hợp, thay vì viết phương tì n h dưới d ạn g /[x ) = 0, người ta viết lại dưới dạng bài toán: (P) Tìm X thỏa mẫn X = g ( x ) . Đ ịnh n ghĩa: Điểm X * được gọi là điểm bất động của hàm g nếu X* = gộc*), nghĩa là điểm X * không bị biến đổi bời ánh xạ g . Bài toán (P) được gọi là bài toán điểm bất động. Ý nghĩa hình học: Điểm bất động X* là giao điểm của đường cong y = g(x) với đường thẳng y = X (xem hình 10). Hình 10. Điểm bắt động 218