Link tải luận văn miễn phí cho ae Kết Nối
Nhan đề : Phương pháp Gradient liên hợp và ứng dụng
Tác giả : Phạm Thị Minh Thuận
Năm xuất bản : 2010
Nhà Xuất bản : Đại học Khoa học
Từ khóa : Toán học,Toán ứng dụng,Thuật toán,Thuật toán Gradient
Số trang : 63 tr.
1 Cơ sở toán học của phương pháp và các khái niệm liên
quan
1.1 Một số khái niệm và kết quả cơ bản của giải tích lồi . . .
1.2 Phương pháp hướng giảm . . . . . . . . . . . . . . . . .
1.2.1 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . .
1.2.2 Hướng giảm . . . . . . . . . . . . . . . . . . . . .
1.2.3 Độ dài bước . . . . . . . . . . . . . . . . . . . . .
1.3 Phương pháp gradient . . . . . . . . . . . . . . . . . . .
1.3.1 Thuật toán gradient với thủ tục tìm chính xác theo
tia . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.2 Thuật toán gradient với thủ tục quay lui . . . . .
1.4 Phương pháp Newton . . . . . . . . . . . . . . . . . . . .
2 Phương pháp gradient liên hợp
2.1 Hướng liên hợp . . . . . . . . . . . . . . . . . . . . . . .
2.2 Phương pháp gradient liên hợp . . . . . . . . . . . . . .
2.2.1 Phương pháp Fletcher - Reeves tìm cực tiểu hàm
tồn phương (F-R) . . . . . . . . . . . . . . . . .
2.2.2 Phương pháp Fletcher - Reeves tìm cực tiểu hàm
khả vi liên tục bất kỳ . . . . . . . . . . . . . . . .
2.2.3 Một số ví dụ áp dụng . . . . . . . . . . . . . . . .
2.3 Tốc độ hội tụ của phương pháp gradient liên hợp . . . .
1
3
3
7
7
9
11
13
13
14
14
17
17
22
22
35
37
40
ii
3 Mở rộng phương pháp gradient liên hợp
3.1 Phương pháp gradient liên hợp 3-số hạng . . . . . . . . .
3.1.1 Thuật toán tái khởi Beale-Powell . . . . . . . . .
3.1.2 Tính hội tụ toàn cục của phương pháp gradient
liên hợp 3-số hạng với thủ tục tìm theo tia kiểu
Wolfe . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3 Phương pháp gradient liên hợp 3-số hạng Beale .
3.2 Phương pháp gradient liên hợp hiệu chỉnh trước chỉ số
điều kiện . . . . . . . . . . . . . . . . . . . . . . . . . . .
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . .
Phụ lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
42
42
43
49
51
55
56
63
1
Mở đầu
Trong thực tế rất nhiều hoạt động kinh tế, xã hội,... đòi hỏi con người
phải quan tâm tới việc tìm phương án tốt nhất để đạt được mục tiêu
mong muốn. Đó chính là các bài tốn tối ưu. Các bài toán tối ưu là một
chủ đề hấp dẫn với nhiều kết quả phong phú luôn thu hút sự quan tâm
của các nhà nghiên cứu.
Luận văn này đề cập tới phương pháp gradient liên hợp và ứng dụng
của nó. Phương pháp gradient liên hợp được Hestenes và Stiefel nêu ra
đầu tiên vào những năm 1950 để giải hệ tuyến tính. Vì việc giải một hệ
tuyến tính tương đương với tìm cực tiểu của một hàm toàn phương xác
định dương, nên vào năm 1960 Fletcher - Reeves đã cải biên và phát
triển nó thành phương pháp gradient liên hợp cho cực tiểu khơng ràng
buộc. Nhờ đó phương pháp này hồn thiện phương pháp giảm nhanh
nhất nhằm làm tăng hiệu quả và độ tin cậy của thuật toán. Phương pháp
gradient liên hợp là trung gian giữa phương pháp gradient và phương
pháp Newton, nó thay đổi hướng tìm trong phương pháp gradient bằng
cách thêm vào một tỷ lệ dương của hướng dùng ở bước ngay trước đó.
Phương pháp này chỉ cần tới đạo hàm riêng bậc nhất nhưng lại khắc
phục được tính hội tụ chậm của phương pháp gradient.
Mục tiêu của luận văn là tìm hiểu và trình bày những kết quả cơ bản
đã biết liên quan đến phương pháp gradient liên hợp, các tính chất như
tính liên hợp, tính trực giao, tính hội tụ và một số phương pháp mở rộng
của phương pháp này. Nội dung đề cập trong luận văn được trình bày
một cách chặt chẽ về mặt tốn học kèm theo một số ví dụ minh họa.
Luận văn được chia làm 3 chương:
2
Chương 1: nhắc lại một số khái niệm cơ bản của giải tích lồi, như tập
lồi, hàm lồi và hàm toàn phương, hướng giảm và phương pháp gradient,
phương pháp Newton... để phục vụ cho các chương tiếp theo.
Chương 2: trình bày các khái niệm, tính chất của hướng liên hợp,
phương pháp gradient liên hợp giải bài toán cực tiểu hàm tồn phương,
nêu các định lý về tính hội tụ của phương pháp gradient liên hợp và mở
rộng phương pháp này để tìm cực tiểu của một hàm khả vi liên tục bất
kỳ. Cuối chương tác giả nêu ra một số ví dụ áp dụng.
Chương 3: trình bày phương pháp gradient liên hợp 3-số hạng. Đó là
sự cải tiến phương pháp F-R tìm cực tiểu hàm khả vi liên tục bất kỳ bởi
vì nếu dùng hướng giảm nhanh nhất thì mức giảm hàm mục tiêu thường
kém so với mức giảm có thể thu được khi khơng dùng tái khởi; cịn nếu
dùng hướng tái khởi tùy ý thì quan hệ liên hợp địi hỏi có thể khơng
cịn đúng. Ngồi ra, trong chương này còn chỉ ra nguyên nhân làm cho
phương pháp gradient liên hợp kết thúc sau nhiều hơn n lần lặp là do
sai số trong q trình tính tốn và từ đó đưa ra biện pháp khắc phục
tình trạng này.
Các kết quả tính tốn thử nghiệm được thực hiện bằng các chương
trình lập trong mơi trường Matlap.
Mặc dù đã rất cố gắng, song bản luận văn không thể tránh khỏi những
sai sót. Tác giả rất mong nhận được sự chỉ bảo, đóng góp của các Thầy
Cơ và các bạn đồng nghiệp để luận văn thêm hoàn thiện.
Tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc đến Thầy hướng dẫn
GS.TS Trần Vũ Thiệu đã tận tình hướng dẫn trong suốt quá trình làm
luận văn. Tác giả cũng xin chân thành Thank các Thầy Cô, các bạn
bè, đồng nghiệp và gia đình ln giúp đỡ, động viên, khích lệ trong suốt
quá trình học tập và nghiên cứu.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Nhan đề : Phương pháp Gradient liên hợp và ứng dụng
Tác giả : Phạm Thị Minh Thuận
Năm xuất bản : 2010
Nhà Xuất bản : Đại học Khoa học
Từ khóa : Toán học,Toán ứng dụng,Thuật toán,Thuật toán Gradient
Số trang : 63 tr.
1 Cơ sở toán học của phương pháp và các khái niệm liên
quan
1.1 Một số khái niệm và kết quả cơ bản của giải tích lồi . . .
1.2 Phương pháp hướng giảm . . . . . . . . . . . . . . . . .
1.2.1 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . .
1.2.2 Hướng giảm . . . . . . . . . . . . . . . . . . . . .
1.2.3 Độ dài bước . . . . . . . . . . . . . . . . . . . . .
1.3 Phương pháp gradient . . . . . . . . . . . . . . . . . . .
1.3.1 Thuật toán gradient với thủ tục tìm chính xác theo
tia . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.2 Thuật toán gradient với thủ tục quay lui . . . . .
1.4 Phương pháp Newton . . . . . . . . . . . . . . . . . . . .
2 Phương pháp gradient liên hợp
2.1 Hướng liên hợp . . . . . . . . . . . . . . . . . . . . . . .
2.2 Phương pháp gradient liên hợp . . . . . . . . . . . . . .
2.2.1 Phương pháp Fletcher - Reeves tìm cực tiểu hàm
tồn phương (F-R) . . . . . . . . . . . . . . . . .
2.2.2 Phương pháp Fletcher - Reeves tìm cực tiểu hàm
khả vi liên tục bất kỳ . . . . . . . . . . . . . . . .
2.2.3 Một số ví dụ áp dụng . . . . . . . . . . . . . . . .
2.3 Tốc độ hội tụ của phương pháp gradient liên hợp . . . .
1
3
3
7
7
9
11
13
13
14
14
17
17
22
22
35
37
40
ii
3 Mở rộng phương pháp gradient liên hợp
3.1 Phương pháp gradient liên hợp 3-số hạng . . . . . . . . .
3.1.1 Thuật toán tái khởi Beale-Powell . . . . . . . . .
3.1.2 Tính hội tụ toàn cục của phương pháp gradient
liên hợp 3-số hạng với thủ tục tìm theo tia kiểu
Wolfe . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3 Phương pháp gradient liên hợp 3-số hạng Beale .
3.2 Phương pháp gradient liên hợp hiệu chỉnh trước chỉ số
điều kiện . . . . . . . . . . . . . . . . . . . . . . . . . . .
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . .
Phụ lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
42
42
43
49
51
55
56
63
1
Mở đầu
Trong thực tế rất nhiều hoạt động kinh tế, xã hội,... đòi hỏi con người
phải quan tâm tới việc tìm phương án tốt nhất để đạt được mục tiêu
mong muốn. Đó chính là các bài tốn tối ưu. Các bài toán tối ưu là một
chủ đề hấp dẫn với nhiều kết quả phong phú luôn thu hút sự quan tâm
của các nhà nghiên cứu.
Luận văn này đề cập tới phương pháp gradient liên hợp và ứng dụng
của nó. Phương pháp gradient liên hợp được Hestenes và Stiefel nêu ra
đầu tiên vào những năm 1950 để giải hệ tuyến tính. Vì việc giải một hệ
tuyến tính tương đương với tìm cực tiểu của một hàm toàn phương xác
định dương, nên vào năm 1960 Fletcher - Reeves đã cải biên và phát
triển nó thành phương pháp gradient liên hợp cho cực tiểu khơng ràng
buộc. Nhờ đó phương pháp này hồn thiện phương pháp giảm nhanh
nhất nhằm làm tăng hiệu quả và độ tin cậy của thuật toán. Phương pháp
gradient liên hợp là trung gian giữa phương pháp gradient và phương
pháp Newton, nó thay đổi hướng tìm trong phương pháp gradient bằng
cách thêm vào một tỷ lệ dương của hướng dùng ở bước ngay trước đó.
Phương pháp này chỉ cần tới đạo hàm riêng bậc nhất nhưng lại khắc
phục được tính hội tụ chậm của phương pháp gradient.
Mục tiêu của luận văn là tìm hiểu và trình bày những kết quả cơ bản
đã biết liên quan đến phương pháp gradient liên hợp, các tính chất như
tính liên hợp, tính trực giao, tính hội tụ và một số phương pháp mở rộng
của phương pháp này. Nội dung đề cập trong luận văn được trình bày
một cách chặt chẽ về mặt tốn học kèm theo một số ví dụ minh họa.
Luận văn được chia làm 3 chương:
2
Chương 1: nhắc lại một số khái niệm cơ bản của giải tích lồi, như tập
lồi, hàm lồi và hàm toàn phương, hướng giảm và phương pháp gradient,
phương pháp Newton... để phục vụ cho các chương tiếp theo.
Chương 2: trình bày các khái niệm, tính chất của hướng liên hợp,
phương pháp gradient liên hợp giải bài toán cực tiểu hàm tồn phương,
nêu các định lý về tính hội tụ của phương pháp gradient liên hợp và mở
rộng phương pháp này để tìm cực tiểu của một hàm khả vi liên tục bất
kỳ. Cuối chương tác giả nêu ra một số ví dụ áp dụng.
Chương 3: trình bày phương pháp gradient liên hợp 3-số hạng. Đó là
sự cải tiến phương pháp F-R tìm cực tiểu hàm khả vi liên tục bất kỳ bởi
vì nếu dùng hướng giảm nhanh nhất thì mức giảm hàm mục tiêu thường
kém so với mức giảm có thể thu được khi khơng dùng tái khởi; cịn nếu
dùng hướng tái khởi tùy ý thì quan hệ liên hợp địi hỏi có thể khơng
cịn đúng. Ngồi ra, trong chương này còn chỉ ra nguyên nhân làm cho
phương pháp gradient liên hợp kết thúc sau nhiều hơn n lần lặp là do
sai số trong q trình tính tốn và từ đó đưa ra biện pháp khắc phục
tình trạng này.
Các kết quả tính tốn thử nghiệm được thực hiện bằng các chương
trình lập trong mơi trường Matlap.
Mặc dù đã rất cố gắng, song bản luận văn không thể tránh khỏi những
sai sót. Tác giả rất mong nhận được sự chỉ bảo, đóng góp của các Thầy
Cơ và các bạn đồng nghiệp để luận văn thêm hoàn thiện.
Tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc đến Thầy hướng dẫn
GS.TS Trần Vũ Thiệu đã tận tình hướng dẫn trong suốt quá trình làm
luận văn. Tác giả cũng xin chân thành Thank các Thầy Cô, các bạn
bè, đồng nghiệp và gia đình ln giúp đỡ, động viên, khích lệ trong suốt
quá trình học tập và nghiên cứu.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links