›
›

Bài giảng Phương pháp số - Bài 2: Nghiệm của các phương trình phi tuyến

Download
BÀI 2  
NGHIỆM CỦA CÁC  
PHƢƠNG TRÌNH PHI TUYẾN  
GIẢI PHƯƠNG TRÌNH f(x) = 0  
KHÁI NIỆM CHUNG  
Bài toán  
Cho hàm f(x) liên tục trên đoạn [a, b] hoặc trên khoảng vô  
hạn và đƣờng cong y = f(x) chỉ có các nghiệm cô lập, tức là  
tồn tại các khoảng rời nhau chứa các không điểm của f(x)  
Các bƣớc giải  
1- Tách nghiệm hay tìm khoảng cách li nghiệm (a, b) - chỉ  
chứa một nghiệm của phƣơng trình f(x) = 0  
2- Kiện toàn nghiệm: tính gần đúng nghiệm với độ chính  
xác cho trƣớc  
Cơ sở của phƣơng pháp tách nghiệm  
Nếu hàm f(x) xác định và liên tục trên [a, b], f(a)f(b) < 0  
và f’(x) giữ dấu trên (a, b) thì tồn tại duy nhất một  
nghiệm thực x* ∊ (a, b) của phƣơng trình f(x) = 0  
PHƢƠNG PHÁP SỐ-Bài 2  
2
GiẢI PHƯƠNG TRÌNH f(x) = 0  
PHƢƠNG PHÁP TÁCH NGHIỆM  
Lập bảng xét dấu của đạo hàm cấp một f‘(x) rồi tìm các  
khoảng (a, b) thỏa mãn các điều kiện trên  
Ví dụ: Tìm các khoảng chứa các nghiệm cô lập của  
phƣơng trình f(x) = x3 – x – 1= 0  
Giải: f‘ (x) = 3x2 – 1, lập bảng xét dấu sau  
x
y’  
y
-2  
-1  
0
1
1.5  
2
+
5
-∞  
∞
+
+
+
0
_
0
+
+
-7  
0.875  
-1  
Vậy phƣơng trình trên có một nghiệm cô lập x1∊(1 ; 1.5)  
PHƢƠNG PHÁP SỐ-Bài 2  
3
CÁC PHƢƠNG PHÁP LẶP (1)  
Bắt đầu  
1 PHƢƠNG PHÁP CHIA ĐÔI  
Nhập a, b, ε  
Giả thiết Cho f(x) liên tục trên (a, b)  
và f(a) f(b) < 0  
m=(a+b)/2  
y=f(x)  
đ
f(a)f(m)<0  
s
b=m  
a=m  
a
b
x* (a+b)/2  
s
b-a<ε  
đ
Kết thúc  
PHƢƠNG PHÁP SỐ-Bài 2  
4
CÁC PHƢƠNG PHÁP LẶP (2)  
1 PHƢƠNG PHÁP CHIA ĐÔI (tiếp)  
Thuật toán:  
Lặp với n = 0, 1, 2, ,.., cho đến khi tìm đƣợc nghiệm đúng x* hoặc  
nghiệm gần đúng xn đạt đƣợc độ chính xác mong muốn  
- Đặt m = (an + bn) / 2, nếu f(m) = 0 dừng (m là nghiệm đúng)  
- Nếu f(an) f(m) < 0, đặt an + 1 = an, bn + 1 = m  
- Trái lại, đặt an + 1 = m, bn + 1 = bn  
Vậy f(x) luôn luôn có không điểm trong khoảng [an + 1 ; bn + 1] .  
Sự hội tụ và sai số:  
Sử dụng phƣơng pháp chia đôi liên tiếp ta nhận đƣợc dãy khoảng  
lồng nhau {(an ; bn)} hữu hạn nếu x* là điểm giữa của khoảng thứ n,  
hay vô hạn co lại: an < x* < bn f(an).f(bn) < 0, bn – an = (b – a) / 2n  
Khi n→, do sự liên tục của f(x) nên lim bn= lim an = x* và  
an bn  
bn an  
b a  
2n1  
x * xn   
xn   
2
2
PHƢƠNG PHÁP SỐ-Bài 2  
5
CÁC PHƢƠNG PHÁP LẶP (3)  
1 PHƢƠNG PHÁP CHIA ĐÔI (tiếp)  
Giải PT x3-x-1=0 trên đoạn [1; 1.5] với độ chính xác ε = 0.0005  
n an  
bn  
c
f(an)  
f( c) f(an) f( c) Sai số  
0 1.0000 1.5000  
1 1.2500 1.5000  
2 1.2500 1.3750  
3 1.3125 1.3750  
4 1.3125 1.3438  
5 1.3125 1.3281  
1.2500 -1.0000 -0.2969 0.29688 0.2500  
1.3750 -0.2969 0.2246 -0.06668 0.0625  
1.3125 -0.2969 -0.0515 0.01529 0.0156  
1.3438 -0.0515 0.0826 -0.00426 0.0039  
1.3281 -0.0515 0.0146 -0.00075 0.0010  
1.3203 -0.0515 -0.0187 0.00096 0.0002  
9 1.3242 1.3252  
1.3247 -0.0021 0.0000 0.00000 0.000001  
6
PHƢƠNG PHÁP SỐ-Bài 2  
CÁC PHƢƠNG PHÁP LẶP (4)  
1. PHƢƠNG PHÁP CHIA ĐÔI (tiếp): CÀI ĐẶT  
double chiaDoi (double a, double b, double epsilon) {  
int lanlap = 0;  
double m ;  
do {  
// Khoi tao so lan lap  
lanlap++ ;  
m = (a + b) / 2.0 ;  
if (f(m) == 0)  
else if (f(a)*f(m) > 0) a = m;  
else b = m;  
break; // m la nghiem dung  
} while (! ( (b − a) / 2.0 <= epsilon || lanlap >1000) );  
cout <<“So lanlap = " << lanlap << endl;  
return m;  
}
PHƢƠNG PHÁP SỐ-Bài 2  
7
CÁC PHƢƠNG PHÁP LẶP (5)  
2 PHƢƠNG PHÁP THỬ SAI:  
Ý tưởng: Tăng tốc độ hội tụ của phƣơng pháp chia đôi bằng  
việc kiểm tra f(x) tại điểm trung bình có trọng số gần 0 hơn  
| f(b)|.a| f(a)|.b f(b).a f(a).b  
w   
| f(b)| | f(a)|  
f(b) f(a)  
Thuật toán:  
Lặp với n = 0, 1, 2, ,.., cho đến khi tìm đƣợc nghiệm đúng x*  
hoặc nghiệm gần đúng xn đạt đƣợc độ chính xác mong muốn  
Tính w = [f(bn)an – f(an)bn] / [f(bn) – f(an)], nếu f(w) = 0 dừng  
- Nếu f(an)f(w) < 0, đặt an + 1 = an, bn + 1 = w  
- Trái lại, đặt an + 1 = w, bn + 1 = bn  
8
PHƢƠNG PHÁP SỐ-Bài 2  
CÁC PHƢƠNG PHÁP LẶP (6)  
2 PHƢƠNG PHÁP THỬ SAI (tiếp)  
f(bn )an f(an )bn  
f(bn ) f(an )  
w   
w là điểm mà tại đó đƣờng thẳng cắt  
trục Ox và đi qua các điểm [an, f(an)]  
[bn, f(bn)] (một dây cung của f(x))  
NHẬN XÉT: Phƣơng  
pháp này không ƣớc  
lƣợng đƣợc khoảng  
chứa nghiệm  
PHƢƠNG PHÁP SỐ-Bài 2  
9
CÁC PHƢƠNG PHÁP LẶP (7)  
2 PHƢƠNG PHÁP THỬ SAI (tiếp):  
Giải PT x3-x-1=0 trên đoạn [1; 1.5]  
n
an  
bn  
f(an)  
f(bn)  
w
f(w)  
f(an) f(w)  
0.2344  
0.0087  
0.0002  
0 1.0000 1.5000 -1.0000 0.8750 1.2667 -0.2344  
1 1.2667 1.5000 -0.2344 0.8750 1.3160 -0.0370  
2 1.3160 1.5000 -0.0370 0.8750 1.3234 -0.0055  
3 1.3234 1.5000 -0.0055 0.8750 1.3245 -0.0008  
4 1.3245 1.5000 -0.0008 0.8750 1.3247 -0.0001  
0.0000  
0.0000  
PHƢƠNG PHÁP SỐ-Bài 2  
10  
CÁC PHƢƠNG PHÁP LẶP (8)  
3 PHƢƠNG PHÁP DÂY CUNG:  
Cho hàm f(x) liên tục và 2 điểm x−1, x0. Coi xi+1 là nghiệm  
xấp xỉ thứ i+1 trên đoạn [xi -1 ; xi] ta nhận đƣợc công thức  
f(xi)xi-1 f(xi-1)xi  
xi1   
f(xi) f(xi-1)  
xi xi1  
f(xi) f(xi1)  
xi1 xi f(xi)  
NHẬN XÉT: f(xi -1) và f(xi) không nhất thiết phải trái dấu,  
thậm chí nếu f(xi -1) = f(xi) thì không tính đƣợc xi+1  
PHƢƠNG PHÁP SỐ-Bài 2  
11  
CÁC PHƢƠNG PHÁP LẶP (9)  
VÍ DỤ:  
Giải PT x3-x-1=0 trên đoạn [1; 1.5] với độ chính xác ε = 0.0005  
bằng phƣơng pháp dây cung  
Điều  
n xn-1  
xn  
xn - xn-1 f(xn-1) f(xn) f(xn) - f(xn-1) chỉnh Sai số  
-1 1.0000 1.5000 0.5000 -1.0000 0.8750  
0 1.5000 1.2667 -0.2333 0.8750 -0.2344  
1 1.2667 1.3160 0.0493 -0.2344 -0.0370  
2 1.3160 1.3252 0.0093 -0.0370 0.0021  
3 1.3252 1.3247 -0.0005 0.0021 0.0000  
1.8750 0.2333 0.9375  
-1.1094 -0.0493 0.4375  
0.1973 -0.0093 0.0924  
0.0392 0.0005 0.0173  
-0.0021 0.0000 0.0009  
4 1.3247 1.3247  
0.0000  
PHƢƠNG PHÁP SỐ-Bài 2  
12  
CÁC PHƢƠNG PHÁP LẶP (10)  
SAI SỐ CỦA CỦA PHƢƠNG PHÁP DÂY CUNG  
Giả sử 0 < m ≤ |f′(x)| ≤ M với mọi x [a, b], từ công thức  
f(xn ) f(xn1)  
xn xn1  
f(xn )xn-1 f(xn-1)xn  
f(xn ) f(xn-1)  
 f(xn )   
(xn1 xn )  
xn1   
Theo công thức số gia hữu hạn, giả sử ξ là nghiệm đúng  
f(x ) f(x )  
n
n1  
(ξ x )f '(ξ ) f(ξ) f(x )   
(x x )  
n
n
n
n1 n  
x x  
n n1  
f '(η )(x x )  
n n1 n  
hay  
(ξ x x x )f '(ξ ) f '(η )(x x )  
n1 n1 n  
n
n n1 n  
| f '(η ) | | f '(ξ )|  
M m  
n
n
|ξ x |   
|x x |   
|x x |  
n1  
n1 n  
n1 n  
|f '(ξ )|  
m
n
PHƢƠNG PHÁP SỐ-Bài 2  
13  
CÁC PHƢƠNG PHÁP LẶP (11)  
4 PHƢƠNG PHÁP NEWTON  
Cho f(x) khả vi liên tục và một điểm x0, trong công thức dây  
cung thay độ nghiêng của dây cung bằng độ nghiêng của  
tiếp tuyến tại xn, ta nhận đƣợc công thức lặp  
f(xn )  
f ' (xn )  
xn1 xn   
Chọn điểm xuất phát x0?  
f(x0)f’’(x0) > 0  
khi f’’ giữ dấu  
trên [a, b]  
PHƢƠNG PHÁP SỐ-Bài 2  
14  
CÁC PHƢƠNG PHÁP LẶP (12)  
VÍ DỤ:  
Giải PT x3–x–1=0 trên đoạn [1; 1.5] với độ chính xác ε = 0.0005  
bằng phƣơng pháp Newton  
f(xn) /  
Phương pháp này  
n xn  
f(xn) f'(xn) f'(xn) Sai số  
thường có dãy  
nghiệm xấp xỉ nằm  
về một trong hai phía  
của nghiệm đúng, khi  
f’’ không đổi dấu  
0 1.0000 -1.0000 2.0000 -0.5000  
1 1.5000 0.8750 5.7500 0.1522 0.5625  
2 1.3478 0.1007 4.4499 0.0226 0.0521  
3 1.3252 0.0021 4.2685 0.0005 0.0012  
Thử lại với x0 = 1.5 ??  
4 1.3247  
0.00002  
PHƢƠNG PHÁP SỐ-Bài 2  
15  
CÁC PHƢƠNG PHÁP LẶP (13)  
SAI SỐ CỦA PHƢƠNG PHÁP NEWTON  
• Từ công thức lặp Newton và khai triển Taylor cấp 1 tại xn  
f ''(ξn )  
f(xn1)   
Mặt khác, giả sử 0 < m1 ≤ |f′(x)| và |f′′(x)| ≤ M2  
với mọi x є [a, b], ta có  
| xn1 xn |2 (*)  
2
f(xn1) f(xn1) f(ξ ) f ' (ςn1)(xn1 ξ)  
| f(xn1) |  
| xn1 - ξ |   
m1  
M2  
| xn1 - ξ | | xn1 xn |2  
Thay (*) vào ta đƣợc  
2m1  
16  
PHƢƠNG PHÁP SỐ-Bài 2  
PHÉP LẶP ĐIỂM CỐ ĐỊNH (1)  
Khái niệm:  
Nếu phương trình f(x) = 0 (*) ↔ x = g(x)  
(**)  
thì một nghiệm bất kì của (**), tức là, bất kì điểm cố định  
nào của g(x), cũng đều là nghiệm của (*), g(x) được gọi là  
một hàm lặp để giải phương trình (*)  
Thuật toán 3.6: Phép lặp điểm cố định.  
Cho hàm lặp g(x) và một điểm xuất phát x0  
Với n = 0, 1, 2, … , cho đến khi thỏa mãn độ chính xác  
cho trước, lặp lại việc tính  
xn+1 = g(xn)  
PHƢƠNG PHÁP SỐ-Bài 2  
17  
PHÉP LẶP ĐIỂM CỐ ĐỊNH (2)  
Định lý: Cho g(x) thỏa mãn  
Hệ quả: Nếu g(x) là  
khả vi liên tục trong  
khoảng mở chứa điểm  
cố định ξ và |g’(ξ)| < 1  
thì tồn tại hằng số ε > 0:  
phép lặp điểm cố định  
xn+1 = g(xn) hội tụ bất  
cứ khi nào |x0 – ξ| ≤ ε  
Điểm cố định ξ mà  
|g’(ξ)| < 1,  
1.Tồn tại khoảng [a, b] sao cho g(x)  
xác định trên [a, b] , g(x) є [a, b].  
2. g(x) khả vi trên [a, b], và tồn  
tại hằng số 0 < K < 1 sao cho:với  
mọi x є [a, b], , |g’(x)| ≤ K  
Khi đó:  
1. g(x) có đúng một điểm cố  
định ξ є [a, b],  
2. Với điểm x0 є [a, b] bất kì, dãy  
xn+1 = g(xn) luôn hội tụ về ξ.  
đƣợc gọi là điểm hút.  
Phƣơng pháp Newton là trƣờng hợp riêng của phép lặp điểm cố định  
PHƢƠNG PHÁP SỐ-Bài 2  
18  
PHÉP LẶP ĐIỂM CỐ ĐỊNH (3)  
Ví dụ: Tìm nghiệm dƣơng nhỏ  
nhất của phƣơng trình  
f(x) = x3 – x – 1  
n
xn  
g(xn)  
0 1.0000 1.2599  
1 1.2599 1.3123  
2 1.3123 1.3224  
3 1.3224 1.3243  
Giải  
Bƣớc 1: . Chọn g(x) = (x + 1)1/3,  
với x є [1 ; 1.5], g(x) є [1; 1.5],  
Bƣớc 2: g(x) khả vi và  
g’(x)| = 1/[3(x + 1)2/3] < 1 trên  
[1; 1.5],phép lặp xn+1 = g(xn) sẽ  
hội tụ nếu chọn điểm x0 є [1; 1.5],  
4 1.3243 1.3246  
xn+1 = (xn + 1)1/3  
5 1.3246 1.3247  
PHƢƠNG PHÁP SỐ-Bài 2  
19  
PHÉP LẶP ĐIỂM CỐ ĐỊNH (4)  
SỰ HỘI TỤ VÀ PHÂN KÌ CỦA PHÉP LẶP ĐiỂM CỐ ĐỊNH  
g’>1  
0<g’<1  
g’<-1  
-1<g’<0  
PHƢƠNG PHÁP SỐ-Bài 2  
20  
Tải về để xem bản đầy đủ
pdf 34 trang Mãnh Khiết 15/01/2024 12660 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Phương pháp số - Bài 2: Nghiệm của các phương trình phi tuyến", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_phuong_phap_so_bai_2_nghiem_cua_cac_phuong_trinh_p.pdf