phuong phap binh phuong cuc tieu

By Admin 08/11/2023 0

  • 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 Sài Gòn - 2017 . 1 / 24

    • Bạn đang xem: phuong phap binh phuong cuc tieu

  • 2. Tổng quan lại đề tài Khái niệm bình phương rất rất tè bắt mối cung cấp kể từ dự án công trình tiên phong của Gauss và Legendre trong tầm thời điểm đầu thế kỷ 19. Bình phương cực tiểu được dùng nhiều nhập đo đếm tiến bộ và quy mô toán học. Các việc mong muốn dùng cách thức bình phương rất rất tiểu: giải hệ phương trình, lần đàng cong tương thích nhất ứng với dải dữ liệu cho trước (curve fitting), lần phương trình hồi quy nhập đo đếm ... 2 / 24

  • 3. Tổng quan lại đề 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 phù hợp Ax = b vô nghiệm + Phương pháp khử Gauss ko thể hiện nghiệm đúng chuẩn. + Phương pháp thay cho thế: lần ¯x ∈ Rn sao cho tới ¯x là sớm nhất nhằm trở thành nghiệm theo đòi nghĩa khoảng cách Euclide, tức là A¯x − b 2 nhỏ nhất. Nghiệm ¯x nhập tình huống này được gọi là nghiệm bình phương rất rất tè (least squares solution), coi [3]. 3 / 24

  • 4. Tổng quan lại đề 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 phù hợp Ax = b vô nghiệm + Phương pháp khử Gauss ko thể hiện nghiệm đúng chuẩn. + Phương pháp thay cho thế: lần ¯x ∈ Rn sao cho tới ¯x là sớm nhất nhằm trở thành nghiệm theo đòi nghĩa khoảng cách Euclide, tức là A¯x − b 2 nhỏ nhất. Nghiệm ¯x nhập tình huống này được gọi là nghiệm bình phương rất rất tè (least squares solution), coi [3]. 3 / 24

  • 5. Tổng quan lại đề tài Bài toán lần đàng cong khớp nhất với tài liệu cho tới trước. Giả sử với tài liệu (ti , yi )i=1..m, tao cần thiết lần đàng cong g(xj , t)j=1..n sao cho tới g(ti ) ≈ yi . Đặt χ2 = m i=1 [yi − g(xj , ti )]2 , cách thức bình phương rất rất tè là lần những thông số xj sao χ2 là nhỏ bé nhất. Bài toán lần phương trình hồi quy nhập thống kê 4 / 24

  • 6. Tổng quan lại đề tài Bài toán lần đàng cong khớp nhất với tài liệu cho tới trước. Giả sử với tài liệu (ti , yi )i=1..m, tao cần thiết lần đàng cong g(xj , t)j=1..n sao cho tới g(ti ) ≈ yi . Đặt χ2 = m i=1 [yi − g(xj , ti )]2 , cách thức bình phương rất rất tè là lần những thông số xj sao χ2 là nhỏ bé nhất. Bài toán lần phương trình hồi quy nhập thống kê 4 / 24

  • 7. Các khái niệm và tấp tểnh lý Giả sử A ∈ Rm×n, b ∈ Rm, x ∈ Rn Định nghĩa 1. (Hệ ko nhất quán (inconsistent)) Hệ Ax = b không tồn tại nghiệm gọi là hệ ko nhất quán. Định nghĩa 2. (Nghiệm bình phương rất rất tè (least squares solution)) Nghiệm ¯x của hệ ko nhất quán Ax = b thỏa A¯x − b 2 nhỏ nhất gọi là nghiệm bình phương rất rất tè. 5 / 24

  • 8. Các khái niệm và tấp tể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 rất rất tè (least squares problem)) Bài toán bình phương rất rất tè là sự lần điểm rất rất tè địa phương x∗ của F(x) = 1 2 m i=1 [fi (x)]2 , nhập bại fi : Rn → R là hàm cho trước và m > n. Định nghĩa 4. (Điểm rất rất tè địa hạt (local minimizer)) Cho số dương nhỏ δ và hàm số F(x). Điểm x∗ gọi là vấn đề rất rất tiểu địa phương của F(x) nếu như F(x∗) F(x), ∀x thỏa x − x∗ < δ. 6 / 24

  • 9. Các khái niệm và tấp tểnh lý Định nghĩa 5. (Điểm giới hạn (stationary point)) Điểm xs gọi là vấn đề giới hạn của F(x) nếu như F (xs) = 0. Định nghĩa 6. (Ma trận xác lập dương (positive definite matrix)) Ma trận đối xứng M ∈ Rn×n gọi là + Xác tấp tểnh dương nếu như xT Mx > 0, ∀x ∈ Rn, x = 0. + Nửa xác lập dương (positive semidefinite) nếu như xT Mx 0, ∀x ∈ Rn, x = 0. 7 / 24

  • 10. Các khái niệm và tấp tể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 trong những điểm rất rất tè địa hạt của F(x) thì F (x∗) = 0. Định lý 2. Nếu x là vấn đề giới hạn của F(x) và F (x) xác lập dương thì x là một trong những rất rất tè địa hạt của F(x) . 8 / 24

  • 11. Nghiệm bình phương rất rất tè của hệ ko nhất quán Xét hệ phương trình ko nhất quán Ax = b Định lý 3. (Nghiệm bình phương rất rất 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 ngược kể từ tấp tểnh lý 3: nghiệm bình phương rất rất tè 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. Phương pháp đạo hàm cho tới việc bình phương rất rất tiểu 1. Xấp xỉ vì chưng hàm tuyến tính Giả sử g(xj , t) = α + βt là hàm cần thiết lần, nhập bại (x1, x2) = (α, β). Đặt G(x) = m i=1 [α + βti − yi ]2 . Khi bại (α, β) được lần kể 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

    • Xem thêm: tang qua sinh nhat cho nguoi yeu

  • 13. Phương pháp đạo hàm cho tới việc bình phương rất rất tiểu 2. Xấp xỉ vì chưng hàm bậc 2 Giả sử g(xj , t) = α + βt + γt2 là hàm cần thiết lần, nhập đó (x1, x2, x3) = (α, β, γ). Đặt G(x) = m i=1 α + βti + γt2 i − yi 2 . Khi bại (α, β, γ) được lần 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. Phương pháp đạo hàm cho tới việc bình phương rất rất tiểu 3. Xấp xỉ vì chưng hàm mũ Giả sử g(xj , t) = CeAt là hàm cần thiết lần, nhập bại (x1, x2) = (C, A). Khi bại ln g(xj , t) = ln C + At Đưa về sự lần hàm xấp xỉ tuyến tính ˜g(˜xj , t) = α + βt, trong đó ˜x = (α, β) = (ln C , A) 12 / 24

  • 15. Phương pháp Gauss-Newton cho tới việc bình phương cực tiểu Giả sử f : Rn → Rm, (m > n) là hàm liên tiếp, khả vi cung 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 lần nghiệm bình phương rất rất tiểu (i) Tính ma mãnh trận Jacobian J(x) của f và lần hgn kể từ hệ phương trình tuyến tính JT Jhgn = −JT f (ii) Cách lặp x = x + hgn . 13 / 24

  • 16. Các việc áp dụng Bài toán 1. Tìm hàm tuyến tính và hàm bậc nhì khớp nhất với những dữ liệu về chừng chếch nhiệt độ chừng tầm toàn thị trường quốc tế từ thời điểm năm 1991-2000 được cho như bảng sau (xem [4]) 14 / 24

  • 17. Các việc áp dụng Dùng cách thức đạo hàm. (ti , yi ) là tài liệu cho tới trước. g1(t) = 0.123 + 0.034t. g2(t) = −0.4078 + 0.2997t − 0.0241t2. 15 / 24

  • 18. Các việc áp dụng Bài toán 2. Tìm đàng cong khớp nhất với dải tài liệu đem chu kỳ luân hồi về nhiệt độ ghi cảm nhận được ở Washington ngày 1/1/2001 được cho tới như bảng sau (xem [3]) 16 / 24

  • 19. Các việc áp dụng Dùng cách thức giải hệ Ax = b với tế bào hình g(xj , t) = x1 + x2 cos 2πt + x3 sin 2πt. Kết ngược thu được g(t) = −1.95 − 0.7445 cos 2πt − 2.5594 sin 2πt 17 / 24

  • 20. Các việc áp dụng Bài toán 3. Tìm đàng cong khớp nhất với dải tài liệu về độ cao và trọng lượng tầm của nhỏ bé trai kể từ 2-11 tuổi tác được ghi nhận vì chưng trung tâm trấn áp dịch bệnh dịch (Centers for Disease Control, CDC) năm 2002 như sau (U.S. National Health and Nutrition Examination Survey) (xem [3]) 18 / 24

  • 21. Các việc áp dụng Dùng cách thức giải hệ Ax = b với tế bào hình + Mô hình 1: g1(xj , t) = αeβt. Kết ngược nhận được g1(t) = 2.0907e2.0553t + Mô hình 2: g2(xj , t) = αtβ. Kết ngược nhận được g2(t) = 16.3044t2.4199 19 / 24

  • 22. Các việc áp dụng Bài toán 4. Tìm đàng cong khớp nhất với dải tài liệu tế bào mô tả con số ô tô sinh hoạt bên trên trái đất từ thời điểm năm 1950 cho tới 1980 (xem [3]) 20 / 24

    • Xem thêm: cong ty co phan vien thong cmc

  • 23. Các việc áp dụng Dùng cách thức Gauss-Newton sau 5 bước lặp với ĐK ban đầu (x1, x2) = (50, 0.1) và quy mô g(xj , t) = x1ex2t 21 / 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. Phụ lục về cách thức Gauss-Newton Giả sử f : Rn → Rm, (m > n) là hàm liên tiếp, khả vi cung 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. Phụ lục về cách thức Gauss-Newton Từ (1) và (2) tao 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à vấn đề giới hạn của L, tao đem L (hgn) = 0. Khi đó JT Jhgn = −JT f (5) L (h) = JT J là ma mãnh trận đối xứng, xác lập dương nên hgn là rất rất trị địa phương. Từ (5) tao có hT gnJT f = −hT gnJT Jhgn < 0 (6) Thay (6) nhập (4) tao được F(x + hgn) ≈ F(x) − 1 2 hT gnJT Jhgn 24 / 24