Phương pháp tính với C++ - Chương 8

Tài liệu tham khảo giáo trình Phương pháp tính với C++ - Chương 8 Tối ưu hóa
Nội dung trích xuất từ tài liệu:
Phương pháp tính với C++ - Chương 8 CHƯƠNG8:TỐIƯUHOÁ §1.PHƯƠNGPHÁPTỈLỆVÀNG Trong chương 8 chúng tađã xét bài toán tìm nghiệm của phương trìnhphi tuyến tức là tìm giá trị của x mà tại đó hàm triệt tiêu. Trong phần nàychúng ta sẽ đặt vấnđề tìm giá trị của x mà tạiđó hàmđạt giá trị cực trị(cựcđại hay cực tiểu). Phương pháp tiết diện vàng là một phương phápđơn giảnvàhiệuquảđểtìmgiátrịcựctrịcủahàm. Giả sử ta có hàm y = f(x) và cần tìm giá trị cực trị trong khoảng [a, b].Khi tìm nghiệm chỉ cần biết 2 giá trị của hàm là ta khẳngđịnhđược nghiệmcó nằm trong khoảngđã cho hay không bằng cách xét dấu của hàm. Khi tìmgiátrịcựctrịtaphảibiếtthêmmộtgiátrịnữacủahàmtrongkhoảng[a,b]thìmới khẳngđịnhđược hàm cóđạt cực trị trongđoạnđã cho hay không. Sauđó ta chọn thêm mộtđiểm thứ tư và xácđịnh xem giá trị cực trị của hàm sẽnằmtrongđoạnnào.Theohìnhvẽ,khichọnđiểmtrunggianctacó: l1+l2=l0 (1)vàđểtiệntínhtoántachọn: l1 l 2 = (2) l 0 l1 c a bThaythế(1)vào(2)tacó: l 0 l1 l l 2 l 1 =2 (3) l1 + l 2 l1 lGọi r = 2 ,tanhậnđượcphươngtrình: l1 1 1+ r = (4) rhay: r2+r‐1=0 (5)Nghiệmcủaphươngtrình(5)là: − 1 + 1 − 4( −1) 5 −1 r= = = 0.61803... (6) 2 2Giá trị nàyđãđược biết từ thời cổ đại vàđược gọi là “tỉ lệ vàng”. Như trênđã nói, phương pháp tỉ lệ vàngđược bắtđầu bằng 2 giá trị đã cho của biến xlàavàb.Sauđótachọn2điểmx1vàxbêntrongkhoảng[a,b]theotỉlệ174 5 −1vàng: d = = 0.61803... 2 y y b x1 a x x x2 x12 a d b x2 d x1cũ x2 cũ a bTa tính giá trị của hàm tại cácđiểm bên trongđoạn [a, b]. Kết quả có thể làmộttrongcáckhảnăngsau: 1. Nếu,như trường hợp hình a, f(x1) > f(x2) thì giá trị cực trị của hàm nằmtrong[x2,b]vàx2trởthànhavàtatínhtiếp. 2. Nếu f(x1) return(a);};floatmax(floatxlow,floatxhigh){ floatxl,xu,r,d,x1,x2,f1,f2,xopt,s; intlap; xl=xlow; xu=xhigh; lap=1; r=(sqrt(5.0)‐1.0)/2.0; d=r*(xu‐xl); x1=xl+d; x2=xu‐d; f1=f(x1); f2=f(x2); if(f1>f2) xopt=x1; else xopt=x2; do { d=r*d; if(f1>f2) { xl=x2; x2=x1; x1=xl+d; f2=f1; f1=f(x1); } else { xu=x1; x1=x2; x2=xu‐d;176 f1=f2; f2=f(x2); } lap=lap+1; if(f1>f2) xopt=x1; else xopt=x2; if(xopt!=0) s=(1.0‐r)*fabs((xu‐xl)/xopt)*100; } while((s>eps)&&(lap if(f1 printf(ʺChokhoangcantimcuctri ʺ); printf(ʺChocanduoia=ʺ); scanf(ʺ%fʺ,&xlow); print ...