Bài tập về bình phương cực tiểu

PHƯƠNG PHÁP BÌNH PHƯƠNG CỰC TIỂU      hội nghị khoa học kỹ thuật lần thứ 34đhyd

Hoàng Hường                                                                                                                                                                                    8 months ago

phamxuan15                                                                                                                                                                                    2 years ago

NguynHiu151                                                                                                                                                                                    2 years ago

Hoàng Hường 8 months ago Hoàng Hường

phamxuan15 2 years ago phamxuan15

NguynHiu151 2 years ago NguynHiu151

PHƯƠNG PHÁP BÌNH PHƯƠNG CỰC TIỂU

1. 1. PHƯƠNG PHÁP BÌNH PHƯƠNG CỰC TIỂU BÁO CÁO ĐỀ TÀI NGHIÊN CỨU KHOA HỌC CẤP TRƯỜNG Chủ nhiệm đề tài: Huỳnh Thanh Toàn TP Hồ Chí Minh - 2017 . 1 / 24
2. 2. Tổng quan đề tài Khái niệm bình phương cực tiểu bắt nguồn từ công trình tiên phong của Gauss và Legendre trong khoảng đầu thế kỷ 19. Bình phương cực tiểu được sử dụng nhiều trong thống kê hiện đại và mô hình toán học. Các bài toán có nhu cầu sử dụng phương pháp bình phương cực tiểu: giải hệ phương trình, tìm đường cong phù hợp nhất ứng với dải dữ liệu cho trước (curve fitting), tìm phương trình hồi quy trong thống kê ... 2 / 24
3. 3. Tổng quan đề tài Bài toán giải hệ phương trình tuyến tính Ax = b với A  Rm×n, b  Rm, x  Rn. Trường hợp Ax = b vô nghiệm + Phương pháp khử Gauss không đưa ra nghiệm chính xác. + Phương pháp thay thế: tìm ¯x  Rn sao cho ¯x là gần nhất để trở thành nghiệm theo nghĩa khoảng cách Euclide, tức là A¯x  b 2 nhỏ nhất. Nghiệm ¯x trong trường hợp này được gọi là nghiệm bình phương cực tiểu (least squares solution), xem [3]. 3 / 24
4. 4. Tổng quan đề tài Bài toán giải hệ phương trình tuyến tính Ax = b với A  Rm×n, b  Rm, x  Rn. Trường hợp Ax = b vô nghiệm + Phương pháp khử Gauss không đưa ra nghiệm chính xác. + Phương pháp thay thế: tìm ¯x  Rn sao cho ¯x là gần nhất để trở thành nghiệm theo nghĩa khoảng cách Euclide, tức là A¯x  b 2 nhỏ nhất. Nghiệm ¯x trong trường hợp này được gọi là nghiệm bình phương cực tiểu (least squares solution), xem [3]. 3 / 24
5. 5. Tổng quan đề tài Bài toán tìm đường cong khớp nhất với dữ liệu cho trước. Giả sử với dữ liệu (ti , yi )i=1..m, ta cần tìm đường cong g(xj , t)j=1..n sao cho g(ti )  yi . Đặt χ2 = m i=1 [yi  g(xj , ti )]2 , phương pháp bình phương cực tiểu là tìm các tham số xj sao χ2 là bé nhất. Bài toán tìm phương trình hồi quy trong thống kê 4 / 24
6. 6. Tổng quan đề tài Bài toán tìm đường cong khớp nhất với dữ liệu cho trước. Giả sử với dữ liệu (ti , yi )i=1..m, ta cần tìm đường cong g(xj , t)j=1..n sao cho g(ti )  yi . Đặt χ2 = m i=1 [yi  g(xj , ti )]2 , phương pháp bình phương cực tiểu là tìm các tham số xj sao χ2 là bé nhất. Bài toán tìm phương trình hồi quy trong thống kê 4 / 24
7. 7. Các định nghĩa và định lý Giả sử A  Rm×n, b  Rm, x  Rn Định nghĩa 1. (Hệ không nhất quán (inconsistent)) Hệ Ax = b không có nghiệm gọi là hệ không nhất quán. Định nghĩa 2. (Nghiệm bình phương cực tiểu (least squares solution)) Nghiệm ¯x của hệ không nhất quán Ax = b thỏa A¯x  b 2 nhỏ nhất gọi là nghiệm bình phương cực tiểu. 5 / 24
8. 8. Các định nghĩa và định lý Giả sử F : Rn  R, f : Rn  Rm và fi : Rn  R Định nghĩa 3. (Bài toán bình phương cực tiểu (least squares problem)) Bài toán bình phương cực tiểu là bài toán tìm điểm cực tiểu địa phương x của F(x) = 1 2 m i=1 [fi (x)]2 , trong đó fi : Rn  R là hàm cho trước và m > n. Định nghĩa 4. (Điểm cực tiểu địa phương (local minimizer)) Cho số dương nhỏ δ và hàm số F(x). Điểm x gọi là điểm cực tiểu địa phương của F(x) nếu F(x) F(x), x thỏa x  x < δ. 6 / 24
9. 9. Các định nghĩa và định lý Định nghĩa 5. (Điểm dừng (stationary point)) Điểm xs gọi là điểm dừng của F(x) nếu F (xs) = 0. Định nghĩa 6. (Ma trận xác định dương (positive definite matrix)) Ma trận đối xứng M  Rn×n gọi là + Xác định dương nếu xT Mx > 0, x  Rn, x = 0. + Nửa xác định dương (positive semidefinite) nếu xT Mx 0, x  Rn, x = 0. 7 / 24
10. 10. Các định nghĩa và định lý Định nghĩa 7. Gradient của F là F (x) = F xj (x) = F1 x1 (x) ... F xn (x) . Định nghĩa 8. Ma trận Hessian của F là F (x) = 2F xi xj (x) Định lý 1. Nếu x là một điểm cực tiểu địa phương của F(x) thì F (x) = 0. Định lý 2. Nếu x là điểm dừng của F(x) và F (x) xác định dương thì x là một cực tiểu địa phương của F(x) . 8 / 24
11. 11. Nghiệm bình phương cực tiểu của hệ không nhất quán Xét hệ phương trình không nhất quán Ax = b Định lý 3. (Nghiệm bình phương cực tiểu) Đặt S = {x  Rn, b  Ax 2  min} và rx = b  Ax. Khi đó x  S  AT rx = 0 Chứng minh (i) AT rx = 0  x  S (ii) x  S  AT rx = 0 Kết quả từ định lý 3: nghiệm bình phương cực tiểu của Ax = b là nghiệm ¯x thỏa AT r¯x = 0. Khi đó AT r¯x = 0  AT (A¯x  b) = 0  AT A¯x = AT b 9 / 24
12. 12. Phương pháp đạo hàm cho bài toán bình phương cực tiểu 1. Xấp xỉ bởi hàm tuyến tính Giả sử g(xj , t) = α + βt là hàm cần tìm, trong đó (x1, x2) = (α, β). Đặt G(x) = m i=1 [α + βti  yi ]2 . Khi đó (α, β) được tìm từ hệ G α = 0 G β = 0 mα + m i=1 ti β = m i=1 yi m i=1 ti α + m i=1 t2 i β = m i=1 yi ti 10 / 24
13. 13. Phương pháp đạo hàm cho bài toán bình phương cực tiểu 2. Xấp xỉ bởi hàm bậc 2 Giả sử g(xj , t) = α + βt + γt2 là hàm cần tìm, trong đó (x1, x2, x3) = (α, β, γ). Đặt G(x) = m i=1 α + βti + γt2 i  yi 2 . Khi đó (α, β, γ) được tìm từ hệ G α = 0 G β = 0 G γ = 0 mα + m i=1 ti β + m i=1 t2 i γ = m i=1 yi m i=1 ti α + m i=1 t2 i β + m i=1 t3 i γ = m i=1 yi ti m i=1 t2 i α + m i=1 t3 i β + m i=1 t4 i γ = m i=1 yi t2 i 11 / 24
14. 14. Phương pháp đạo hàm cho bài toán bình phương cực tiểu 3. Xấp xỉ bởi hàm mũ Giả sử g(xj , t) = CeAt là hàm cần tìm, trong đó (x1, x2) = (C, A). Khi đó ln g(xj , t) = ln C + At Đưa về bài toán tìm hàm xấp xỉ tuyến tính ˜g(˜xj , t) = α + βt, trong đó ˜x = (α, β) = (ln C , A) 12 / 24
15. 15. Phương pháp Gauss-Newton cho bài toán bình phương cực tiểu Giả sử f : Rn  Rm, (m > n) là hàm liên tục, khả vi cấp 2 và hàm F : Rn  R thỏa F(x) = 1 2 m i=1 [fi (x)]2 = 1 2 f (x) 2 = 1 2 f T (x)f (x) Thuật toán Gauss-Newton tìm nghiệm bình phương cực tiểu (i) Tính ma trận Jacobian J(x) của f và tìm hgn từ hệ phương trình tuyến tính JT Jhgn = JT f (ii) Bước lặp x = x + hgn . 13 / 24
16. 16. Các bài toán áp dụng Bài toán 1. Tìm hàm tuyến tính và hàm bậc hai khớp nhất với các dữ liệu về độ lệch nhiệt độ trung bình toàn cầu từ năm 1991-2000 được cho như bảng sau (xem [4]) 14 / 24
17. 17. Các bài toán áp dụng Dùng phương pháp đạo hàm. (ti , yi ) là dữ liệu cho trước. g1(t) = 0.123 + 0.034t. g2(t) = 0.4078 + 0.2997t  0.0241t2. 15 / 24
18. 18. Các bài toán áp dụng Bài toán 2. Tìm đường cong khớp nhất với dải dữ liệu có chu kỳ về nhiệt độ ghi nhận được ở Washington ngày 1/1/2001 được cho như bảng sau (xem [3]) 16 / 24
19. 19. Các bài toán áp dụng Dùng phương pháp giải hệ Ax = b với mô hình g(xj , t) = x1 + x2 cos 2πt + x3 sin 2πt. Kết quả thu được g(t) = 1.95  0.7445 cos 2πt  2.5594 sin 2πt 17 / 24
20. 20. Các bài toán áp dụng Bài toán 3. Tìm đường cong khớp nhất với dải dữ liệu về chiều cao và trọng lượng trung bình của bé trai từ 2-11 tuổi được ghi nhận bởi trung tâm kiểm soát dịch bệnh (Centers for Disease Control, CDC) năm 2002 như sau (U.S. National Health and Nutrition Examination Survey) (xem [3]) 18 / 24
21. 21. Các bài toán áp dụng Dùng phương pháp giải hệ Ax = b với mô hình + Mô hình 1: g1(xj , t) = αeβt. Kết quả thu được g1(t) = 2.0907e2.0553t + Mô hình 2: g2(xj , t) = αtβ. Kết quả thu được g2(t) = 16.3044t2.4199 19 / 24
22. 22. Các bài toán áp dụng Bài toán 4. Tìm đường cong khớp nhất với dải dữ liệu mô tả số lượng ô tô hoạt động trên thế giới từ năm 1950 đến 1980 (xem [3]) 20 / 24
23. 23. Các bài toán áp dụng Dùng phương pháp Gauss-Newton sau 5 bước lặp với điều kiện ban đầu (x1, x2) = (50, 0.1) và mô hình g(xj , t) = x1ex2t 21 / 24
24. 24. TÀI LIỆU THAM KHẢO [1] ˚Ake Bj¨orck, Numerical Methods for Least Squares Problems, SIAM, 1996. [2] K. Madsen, H.B. Nielsen, O. Tingleff, Methods for Non-linear Least Squares Problems, Informatics and Mathematical Modelling Technical University of Denmark. [3] Timothy Sauer, Numerical Analysis, George Mason University. [4] Kap, The Methods of Least Squares, lectures INF2320. [5] Stephen Boyd, Least Squares, EE103 Stanford University. XIN CÁM ƠN QUÝ THẦY CÔ 22 / 24
25. 25. Phụ lục về phương pháp Gauss-Newton Giả sử f : Rn  Rm, (m > n) là hàm liên tục, khả vi cấp 2 và hàm F : Rn  R thỏa F(x) = 1 2 m i=1 [fi (x)]2 = 1 2 f (x) 2 = 1 2 f T (x)f (x) (1) Ta có Ma trận Jacobian của f : J(x) = fi xj (x) ij Gradient của f : F (x) = JT (x)f (x) Khai triển Taylor của f : f (x + h) = f (x) + J(x)h + O( h 2 ) (2) 23 / 24
26. 26. Phụ lục về phương pháp Gauss-Newton Từ (1) và (2) ta có f (x + h)  l(h) = f (x) + J(x)h (3) F(x + h)  L(h) = F(x) + hT JT f + 1 2 hT JT Jh (4) Gradient và Hessian của L: L (h) = JT f + JT Jh, L (h) = JT J Gọi hgn là điểm dừng của L, ta có L (hgn) = 0. Khi đó JT Jhgn = JT f (5) L (h) = JT J là ma trận đối xứng, xác định dương nên hgn là cực trị địa phương. Từ (5) ta có hT gnJT f = hT gnJT Jhgn < 0 (6) Thay (6) vào (4) ta được F(x + hgn)  F(x)  1 2 hT gnJT Jhgn 24 / 24

Share Clipboard        Name*        Description          Others can see my Clipboard CancelSave