Luận văn Thạc sĩ Toán học: Phương pháp bình phương tối thiểu toàn phần

Chia sẻ: Tri Tâm | Ngày: | Loại File: PDF | Số trang:37

Thêm vào BST

Báo xấu

13
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn được chia làm hai chương: Giới thiệu về phương pháp bình phương tối thiểu toàn phần cùng một số kiến thức liên quan như: Phân tích giá trị kì đị, nghiệm bình phương tối thiểu. nghiệm bình phương tối thiểu có chuẩn nhỏ nhất, nghiệm bình phương tối thiểu toàn phần; một số ứng dụng của phương pháp bình phương tối thiểu toàn phần trong nghiên cứu hồi quy đơn tuyến tính và hồi quy phi tuyến.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Phương pháp bình phương tối thiểu toàn phần

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- TRẦN THỊ THU HƯỜNG PHƯƠNG PHÁP BÌNH PHƯƠNG TỐI THIỂU TOÀN PHẦN LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- TRẦN THỊ THU HƯỜNG PHƯƠNG PHÁP BÌNH PHƯƠNG TỐI THIỂU TOÀN PHẦN Chuyên ngành: Toán ứng dụng Mã số : 8 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Nguyễn Thị Ngọc Oanh THÁI NGUYÊN - 2019
1 Möc löc Trang Líi c£m ìn 2 Líi nâi ¦u 3 Ch÷ìng 1 Giîi thi»u v· ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n 6 1.1. Mët sè kþ hi»u v ki¸n thùc cì b£n . . . . . . . . . . . . . 6 1.2. Ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu . . . . . . . . . . . . . 8 1.2.1. Ph¥n t½ch gi¡ trà k¼ dà . . . . . . . . . . . . . . . . 11 1.2.2. Nghi»m b¼nh ph÷ìng tèi thiºu v SVD . . . . . . . 14 1.3. Ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n . . . . . . . 14 1.3.1. Thi¸t lªp b i to¡n . . . . . . . . . . . . . . . . . . 14 1.3.2. Nghi»m cì b£n . . . . . . . . . . . . . . . . . . . . 16 1.4. Thuªt to¡n b¼nh ph÷ìng tèi thiºu to n ph¦n . . . . . . . . 20 Ch÷ìng 2 Mët sè ùng döng cõa ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n 22 2.1. Hçi quy ìn tuy¸n t½nh . . . . . . . . . . . . . . . . . . . . 22 2.2. Hçi quy phi tuy¸n . . . . . . . . . . . . . . . . . . . . . . . 26
2 Líi c£m ìn Luªn v«n ÷ñc ho n th nh d÷îi sü ch¿ b£o v h÷îng d¨n tªn t¼nh cõa TS. Nguy¹n Thà Ngåc Oanh. Cæ ¢ d nh nhi·u thíi gian h÷îng d¨n v gi£i ¡p thc mc cõa tæi trong suèt qu¡ tr¼nh l m luªn v«n. Tæi xin b y tä láng bi¸t ìn s¥u sc ¸n cæ. Tæi xin gûi tîi c¡c th¦y, cæ trong khoa To¡n - Tin cõa Tr÷íng ¤i håc Khoa håc - ¤i håc Th¡i Nguy¶n líi c£m ìn s¥u sc nh§t v· cæng lao d¤y dé trong suèt qu¡ tr¼nh håc tªp t¤i tr÷íng. Cuèi còng tæi xin c£m ìn Ban gi¡m hi»u tr÷íng THPT Qu¸ Vã sè 1, tªp thº c¡c th¦y cæ gi¡o trong tê To¡n-Tin cõa Tr÷íng, gia ¼nh, b¤n b± v ng÷íi th¥n ¢ quan t¥m, t¤o i·u ki»n, ëng vi¶n, cê vô º tæi câ thº ho n th nh nhi»m vö cõa m¼nh. Th¡i Nguy¶n, ng y...th¡ng 4 n«m 2019 Håc vi¶n Tr¦n Thà Thu H÷íng
3 Líi nâi ¦u Ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n (Total least square -TLS) ÷ñc giîi thi»u bði Golub v Van Loan ....nh÷ mët kÿ thuªt gi£i c¡c h» "qu¡ x¡c ành" (overdetermined system), tùc l nhúng h» câ sè ph÷ìng tr¼nh nhi·u hìn sè ©n câ d¤ng AX ≈ B , vîi c¡c ma trªn A ∈ Rm×n v B ∈ Rm×d cho tr÷îc v X ∈ Rn×d ch÷a bi¸t, ang c¦n t¼m. Vîi m > n, nâi chung khæng câ nghi»m ch½nh x¡c X cho x§p x¿ ang t¼m. Ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n l sü têng qu¡t qu¡ cõa ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu (Least square -LS) khi c£ ma trªn A v B ·u bà nhi¹u. Ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n l mët kÿ thuªt hi»u qu£ º ÷îc l÷ñng tham sè tuy¸n t½nh. B i to¡n ÷îc l÷ñng tham sè tuy¸n tinh ¢ d¨n tîi mët lîp rëng r¢i c¡c l¾nh vüc khoa håc nh÷ xû lþ t½n hi»u, i·u khiºn tü ëng,. . . , v nhi·u ùng döng kh¡c trong kÿ thuªt, thèng k¶, vªt lþ, kinh t¸, sinh håc,. . . . Nâ ÷ñc bt ¦u b¬ng mët ph÷ìng tr¼nh tuy¸n t½nh sau α1 x1 + · · · + αn xn = β (0.1) trong â α1 , . . . , αn v β l c¡c bi¸n v x = [x1 , . . . , xn ]T ∈ Rn l v²c tì tham sè °c tr÷ng cho h» (0.1). B i to¡n °t ra l tø dú ki»n o ÷ñc n o â cõa c¡c bi¸n, ta x¡c ành mët ÷îc l÷ñng cõa tham sè ch÷a bi¸t theo mët c¡ch óng nh§t. Gåi A ∈ Rm×n l ma trªn câ h ng thù i t÷ìng ùng chùa c¡c dú ki»n αi , i = 1, . . . , n v v²c tì b ∈ Rm chùa β. Khi â ta câ h» Ax = b (0.2)
4 l h» gçm m ph÷ìng tr¼nh v n ©n. Vîi c¡ch ti¸p cªn b i to¡n b¬ng ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu th¼ ma trªn A cõa c¡c dú ki»n o αi (v¸ tr¡i cõa (0.2)) ÷ñc gi£ sû l ch½nh x¡c, khæng câ sai sè. Do â, c¡c sai sè ·u ÷ñc t¤o ra bði v²c tì quan s¡t b (tùc l v¸ ph£i cõa (0.2)). Tuy nhi¶n i·u gi£ sû n y khæng mang t½nh thüc t¸ bði t§t c¡c c¡c sai sè cõa mæ h¼nh, sai sè o ¤c công ÷ñc t¤o ra bði c¡c dú ki»n cõa ma trªn A. Ti¸p cªn b¼nh ph÷ìng tèi thiºu to n ph¦n mang þ ngh¾a thüc t¸ hìn khi x²t sai sè ÷ñc t¤o ra c£ ð v²c tì quan s¡t b v ma trªn dú li»u A. º minh håa t½nh húu hi»u cõa ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n so vîi ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu, ta câ thº x²t mët v½ dö trong tr÷íng hñp ta câ mët tham sè, tùc l vîi n = 1. Ph÷ìng tr¼nh (0.1) trð th nh αx = β. (0.3) B i to¡n °t ra l tø m o ¤c cõa c¡c bi¸n α v β , ta i ÷îc l÷ñng tham sè x. Ta s³ i gi£i h» (0.2) vîi A = [a1 , . . . , am ]T v b = [b1 , . . . , bm ]T trong â ai = a0i + ∆ai , (0.4) bi = b0i + ∆bi , i = 1, . . . , m, (0.5) vîi ∆ai , ∆bi l c¡c sai sè cëng v o c¡c dú ki»n ch½nh x¡c a0i , b0i cõa c¡c bi¸n α, β. N¸u α l o ÷ñc ch½nh x¡c, tùc l ∆ai = 0, khi â sai sè ch¿ x£y ra khi o β chùa trong v¸ ph£i b. Trong tr÷íng hñp n y ta câ thº sû döng ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu º gi£i ph÷ìng tr¼nh (0.2), tùc l ta cüc tiºu hâa têng c¡c b¼nh ph÷ìng câ d¤ng m X (bi − ai x)2 . i=1 Trong tr÷íng hñp n y, b¬ng c¡ch khai triºn têng tr¶n th¼ cüc tiºu hay
5 ÷îc l÷ñng x0 cõa x ÷ñc cho bði cæng thùc Pn 0 ai bi x = Pi=1 n 2 i=1 ai N¸u β khæng câ sai sè, tùc l ∆bi = 0, ta vi¸t l¤i ph÷ìng tr¼nh (0.1) d÷îi d¤ng β = α. x Sû döng ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu, b¬ng c¡ch cüc tiºu hâa têng b¼nh ph÷ìng sai ph¥n ta thu ÷ñc ÷îc l÷ñng tèt nh§t x00 nh÷ sau Pn 2 0 b x = Pni=1 i . i=1 ai bi Tuy nhi¶n trong thüc t¸, c¡c bi¸n ÷ñc o luæn câ sai sè, ngh¾a l ∆ai 6= 0 v ∆bi 6= 0. Trong tr÷íng hñp n y, ta c¦n sû döng ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n º nghi¶n cùu b i to¡n, c¡ch ti¸p cªn b i to¡n b¬ng ph÷ìng ph¡p n y mang nhi·u þ ngh¾a thüc t¸ hìn. Luªn v«n ÷ñc chia l m hai ch÷ìng. Ch÷ìng 1 giîi thi»u v· ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n còng mët sè ki¸n thùc li¶n quan nh÷: Ph¥n t½ch gi¡ trà k¼ dà, nghi»m b¼nh ph÷ìng tèi thiºu, nghi»m b¼nh ph÷ìng tèi thiºu câ chu©n nhä nh§t, nghi»m b¼nh ph÷ìng tèi thiºu to n ph¦n, ành lþ v· nghi»m b¼nh ph÷ìng tèi thiºu to n ph¦n,. . . . Ch÷ìng 2 cõa luªn v«n tr¼nh b y mët sè ùng döng cõa ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n trong nghi¶n cùu hçi quy ìn tuy¸n t½nh v hçi quy phi tuy¸n. Mët sè v½ dö sè ÷ñc tr¼nh b y º minh håa cho t½nh hi»u qu£ cõa ph÷ìng ph¡p.
6 Ch÷ìng 1 Giîi thi»u v· ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n Trong ch÷ìng n y, chóng tæi tr¼nh b y mët sè ki¸n thùc li¶n quan tîi ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu, ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n v câ minh håa mët v i v½ dö khi sû döng hai ph÷ìng ph¡p nâi tr¶n. 1.1. Mët sè kþ hi»u v ki¸n thùc cì b£n • Ma trªn chuyºn và cõa ma trªn A ÷ìc kþ hi»u l AT . • R(S) (t÷ìng ùng Rr (S)) l khæng gian sinh bði c¡c cët (t÷ìng ùng c¡c h ng) cõa ma trªn S , N (S) kþ hi»u l khæng gian v²c tì khæng ho°c l nh¥n cõa S. • Ma trªn ÷íng ch²o A cï m×n k½ hi»u l A = diag(α1 , · · · , αp ), vîi p = min {m, n} vîi aij = 0 vîi i 6= j v aii = αi vîi i = 1, . . . , p. • Ma trªn ìn và cï m×m ÷ñc k½ hi»u l Im hay ìn gi£n l I. • Cho ph÷ìng tr¼nh AX = B (1.1) trong â A l ma trªn cï m × n, X l ma trªn cï n × d, v B l ma
7 trªn cï m × d. Nghi»m b¼nh ph÷ìng tèi thiºu câ chu©n nhä nh§t cõa ph÷ìng tr¼nh (1.1) ÷ñc kþ hi»u l X 0, nghi»m b¼nh ph÷ìng tèi thiºu to n ph¦n câ chu©n nhä nh§t ÷ñc kþ hi»u l ˆ. X Trong tr÷íng hñp d = 1, ta câ thº k½ hi»u c¡c ma trªn X, B bði c¡c v²c tì x, b t÷ìng ùng. • Chu©n Frobenius cõa ma trªn M cï m×n ÷ñc ành ngh¾a bði v u n m q uX X kM kF = t 2 mij = tr(M T M ), (1.2) i=1 i=1 T trong â tr(M M) l v¸t cõa ma trªn M T M. • Chu©n 2 hay chu©n Euclide cõa v²c tì y trong khæng gian n chi·u ÷ñc ành ngh¾a bði v u n uX kyk2 = t yi2 . (1.3) i=1 • Ph¥n t½ch gi¡ trà k¼ dà - SVD. Kþ hi»u SVD cõa ma trªn A cï m × n, m > n câ d¤ng A = U 0 Σ0 V 0T , (1.4) trong â U 0 = [U10 ; U20 ], U10 = [u01 , · · · , u0n ], U20 = [u0n+1 , · · · , u0m ], u0i ∈ Rm , U 0T U 0 = Im , V 0 = [v10 , · · · , vn0 ], vi0 ∈ Rn , V 0T V 0 = In , Σ0 = diag(σ10 , · · · , σn0 ) ∈ Rm×n , σ10 ≥ · · · ≥ σn0 ≥ 0. Ta công k½ hi»u SVD cõa ma trªn [A; B] cï m × (n + d), m > n câ d¤ng [A; B] = U ΣV T , (1.5)
8 trong â U = [U1 ; U2 ], U1 = [u1 , · · · , un ], U2 = [un+1 , · · · , um ], ui ∈ Rm , U T U = Im , ! V11 V12 V = = [v1 , · · · , vn+d ], vi ∈ Rn+d , V T V = In+d , V21 V22 ! Σ1 0 Σ= = diag(σ1 , · · · , σn+t ) ∈ Rm×(n+d) , t = min{m − n, d}, 0 Σ2 Σ1 = diag(σ1 , · · · , σn ) ∈ Rn×n , Σ1 = diag(σn+1 , · · · , σn+t ) ∈ R(m−n)×d , v σ1 ≥ · · · ≥ σn+t ≥ 0. 1.2. Ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu Ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu (LS) l mët c¡ch ti¸p cªn phê bi¸n khi gi£i h» tuy¸n t½nh qu¡ x¡c ành, tùc l sè ph÷ìng tr¼nh nhi·u hìn sè ©n. Nâi chung c¡c h» nh÷ vªy khæng câ nghi»m nh÷ng ta t¼m nghi»m x§p x¿ cõa h» b¬ng c¡ch cüc tiºu hâa têng b¼nh ph÷ìng cõa sai sè ÷ñc t¤o th nh khi gi£i méi ph÷ìng tr¼nh ìn l´. X²t b i to¡n t¼m x ∈ Rn thäa m¢n ph÷ìng tr¼nh Ax = b, trong â b ∈ Rm ¢ bi¸t v dú li»u A ∈ Rm×n . Khi sè ph÷ìng tr¼nh nhi·u hìn sè ©n, tùc l m > n th¼ h» ÷ñc gåi l h» qu¡ x¡c ành. Trong tr÷íng hñp b∈ / R(A) th¼ h» qu¡ x¡c ành khæng câ nghi»m ch½nh x¡c, do vªy ta sû döng k½ hi»u Ax ≈ b. Nghi»m b¼nh ph÷ìng tèi thiºu ÷ñc tr¼nh b y trong ành ngh¾a d÷îi ¥y. ành ngh¾a 1.1 X²t b i to¡n t¼m cüc tiºu min kAx − bk2 , A ∈ Rm×n , b ∈ Rm . (1.6) x∈Rn Cüc tiºu x0 b§t ký ÷ñc gåi l nghi»m b¼nh ph÷ìng tèi thiºu cõa h» Ax ≈ b.
9 Mët trong nhúng ùng döng quan trång cõa b i to¡n LS l ÷îc l÷ñng tham sè trong mæ h¼nh thèng k¶ tuy¸n t½nh. Gi£ sû r¬ng ta câ m quan s¡t b = [b1 , . . . , bm ]T li¶n h» vîi n tham sè ch÷a bi¸t x = [x1 , . . . , xn ]T bði ph÷ìng tr¼nh Ax = b0 , b = b0 + ∆b, vîi ∆b [∆b1 , . . . , ∆bm ]T v ∆bi , i = 1, 2, . . . , m l c¡c sai sè ng¨u nhi¶n. Ta s³ gi£ sû r¬ng A câ h¤ng l n v ∆b câ gi¡ trà trung b¼nh b¬ng 0. Khi â ÷îc l÷ñng LS x0 thäa m¢n hai i·u ki»n d÷îi ¥y i) Khæng câ sai sè h» thèng trong ÷îc l÷ñng. ii) C¡c ÷îc l÷ñng l h m tuy¸n t½nh cõa b. T½nh ch§t nghi»m cõa ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu ÷ñc tr¼nh b y trong ành lþ sau ¥y. ành lþ 1.1 (T½nh ch§t nghi»m b¼nh ph÷ìng tèi thiºu) °t S = {x ∈ Rn vîi kAx − bk2 −→ min} l tªp c¡c nghi»m cõa b i to¡n (1.6). Khi â ta câ x0 ∈ S ⇐⇒ AT (b − Ax0 ) = 0. (1.7) Chùng minh. "⇐": Cho AT (b − Ax0 ) = 0 v z ∈ Rn l mët v²c tì b§t k¼. Khi â ta câ b − Az = b − Ax0 + A(x0 − z), do â kb − Azk22 = kb − Ax0 k22 + 2 hb − Ax0 , A(x0 − z)i + kA(x0 − z)k22 = kb − Ax0 k22 + 2 AT (b − Ax0 ), x0 − z + kA(x0 − z)k22 . V¼ AT (b − Ax0 ) = 0 n¶n kb − Azk22 = kb − Ax0 k22 + kA(x0 − z)k22 . Do â kb − Azk22 ≥ kb − Ax0 k22 , ∀z ∈ Rn , tùc l x0 ∈ S .
10 "⇒": Ta chùng minh b¬ng ph£n chùng. Gi£ sû x0 ∈ S v AT (b − Ax0 ) = z 6= 0, °t u = x0 + z, > 0, ta câ b − Au = b − Ax0 − Az. Khi â kb − Auk22 = kb − Ax0 k22 − 2 hb − Ax0 , Azi + 2 k = kb − Ax0 k22 − 2 AT (b − Ax0 ), z + 2 kAzk22 = kb − Ax0 k22 − 2kzk22 + 2 kAzk22 . Nh÷ vªy khi õ nhä, ta câ thº ¤t ÷ñc ¡nh gi¡ kb−Ax0 k22 ≥ kb−Auk22 , i·u n y m¥u thu¨n vîi gi£ thi¸t x0 ∈ S. Ta nhªn ÷ñc i·u ph£i chùng minh. ành lþ 1.1 ¢ ch¿ ra r¬ng ph¦n d÷ r0 = b − Ax0 cõa nghi»m b¼nh ph÷ìng tèi thiºu x0 l trüc giao vîi mi·n gi¡ trà R(A) cõa A. Do â v¸ ph£i b ÷ñc ph¥n t½ch th nh hai ph¦n trüc giao b = Ax0 + r0 = b0 + r0 , r0 ⊥ Ax0 = b0 , trong â b0 l ph²p chi¸u trüc giao cõa b l¶n R(A). Công tø ành lþ 1.1, ta suy ra r¬ng nghi»m b¼nh ph÷ìng tèi thiºu s³ thäa m¢n ph÷ìng tr¼nh AT Ax = AT b. (1.8) Ta câ h» qu£ sau H» qu£ 1.1 (Nghi»m b¼nh ph÷ìng tèi thiºu v ph¦n d÷) N¸u rank(A) = n th¼ B i to¡n (1.6) câ duy nh§t mët nghi»m b¼nh ph÷ìng tèi thiºu x0 v ÷ñc cho bði cæng thùc x0 = (AT A)−1 AT b. (1.9) V ph¦n d÷ t÷ìng ùng r0 = b − Ax0 = b − b0 , b0 = PA b, (1.10) trong â PA = A(AT A)−1AT l ph²p chi¸u trüc giao l¶n R(A).
11 N¸u rank(A) = r < n, B i to¡n (1.6) l h¤ng thi¸u v câ væ sè nghi»m. N¸u x l mët cüc tiºu v z ∈ N (A) th¼ x+z công l cüc tiºu. Nghi»m duy nh§t l nghi»m câ chu©n 2 nhä nh§t chån ra tø tªp t§t c£ c¡c cüc tiºu X = {x ∈ Rn : kAx − bk2 min}. Ta k½ hi»u nghi»m n y l x0 (chó þ r¬ng trong tr÷íng hñp h¤ng ¦y õ th¼ ch¿ câ duy nh§t mët nghi»m LS v do â nâ ph£i câ chu©n 2 nhä nh§t). Trong ph¦n ti¸p theo ta s³ tr¼nh b y biºu di¹n nghi»m b¼nh ph÷ìng tèi thiºu x0 v ph¦n d÷ r0 = b − Ax0 thæng qua Ph¥n t½ch gi¡ trà k¼ dà (Singular Value Decomposition - SVD). 1.2.1. Ph¥n t½ch gi¡ trà k¼ dà ành lþ 1.2 (Ph¥n t½ch gi¡ trà k¼ dà - SVD) N¸u C ∈ Rm×n , th¼ tçn t¤i ma trªn trüc giao U = [u1, . . . , cm] ∈ Rm×m v V = [u1 , . . . , cn ] ∈ Rn×n sao cho U T CV = Σ = diag(σ1 , . . . , σp ), σ1 ≥ · · · ≥ σp , p = min{m, n}. (1.11) Trong t i li»u tham kh£o [3] ¢ câ chùng minh chi ti¸t cho ành lþ n y. C¡c gi¡ trà σi ÷ñc gåi l gi¡ trà ký dà cõa C v tªp c¡c gi¡ trà k¼ dà ÷ñc gåi l phê ký dà. C¡c v²c tì ui v vi t÷ìng ùng l c¡c v²c tì k¼ dà tr¡i thù i v v²c tì k¼ dà ph£i thù i. Bë (ui , σi , vi ) ÷ñc gåi l gi£i ký dà. Tø â ta câ Cvi = σi ui v C T ui = σi vi , i = 1, . . . , p. (1.12) Ph¥n t½ch gi¡ trà k¼ dà câ li¶n quan lîn tîi c§u tróc cõa ma trªn. N¸u ph¥n t½ch gi¡ trà k¼ dà cõa C ÷ñc cho bði ành lþ 1.2 r ÷ñc x¡c ành nh÷ sau σ1 ≥ · · · ≥ σr > σr+1 = · · · = σp = 0,
12 th¼ rank(C) = r, R(C) = R([u1 , . . . , ur ]), N (C) = R([vr+1 , . . . , vn ]), R(C T ) = R([v1 , . . . , vr ]), N (C T ) = R([ur+1 , . . . , um ]). Hìn núa, n¸u °t Ur = [u1 , . . . , ur ], diag(σ1 , . . . , σr ) v Vr = [v1 , . . . , vr ] ta câ khai triºn SVD r X C= Ur Σr VrT = σi ui viT . (1.13) i=1 Ph÷ìng tr¼nh (1.13) ÷ñc gåi l ph¥n t½ch hai ngæi, tùc l ph¥n t½ch ma trªn C h¤ng r th nh têng cõa r ma trªn h¤ng 1. Chu©n 2 v chu©n Frobenius ÷ñc t½nh thæng qua c¡c ph¦n tû cõa SVD nh÷ sau m X X n kCkF = c2ij = σ12 + · · · + σp2 , p = min{m, n}, i=1 j=1 kCyk2 kCkF = sup = σ1 . y6=1 kyk2 Tø ph÷ìng tr¼nh (1.11) ta suy ra r¬ng C T C = V ΣT ΣV T v CC T = U ΣΣT U T . Do â σi2 , i = 1, . . . , p l gi¡ trà ri¶ng cõa ma trªn èi xùng, x¡c ành khæng ¥m CT C v CC T vîi c¡c v²c tì ri¶ng t÷ìng ùng l vi v ui . V½ dö 1.1 X²t tr÷íng hñp n = 2, cho C = [c1 , c2 ], vîi cT1 c2 = cos γ v kc1 k2 = kc2 k2 = 1, trong â γ l gâc giúa hai v²c tì c1 v c2 . Ma trªn " # 1 cos γ CT C = cos γ 1
13 câ c¡c gi¡ trà ri¶ng γ γ λ1 = 2 cos2 , λ2 = 2 sin2 2 2 do â √ γ √ γ σ1 = 2 cos , σ2 = 2 sin . 2 2 C¡c v²c tì k¼ dà ph£i cõa C l " # " # 1 1 1 1 v1 = √ ; v2 = √ . 2 1 2 −1 C¡c v²c tì k¼ dà tr¡i cõa C l 1 1 u1 = (c 1 + c2 ); u2 = (c1 − c2 ). 2 cos γ2 2 sin γ2 ành lþ 1.3 (ành lþ x§p x¿ ma trªn Eckart-Young-Mirsky) Cho ph¥n t½ch SVD cõa C ∈ Rm×n câ d¤ng C = vîi r = rankC. Pr T i=1 σi ui vi N¸u k < r v Ck = ki=1 σiuiviT th¼ P min kC − Dk2 = kC − Ck k2 = σk+1 (1.14) rank(D)=k v v u p uX min kC − DkF = kC − Ck kF = t σi2 , p = min{m, n}. (1.15) rank(D)=k i=k+1 ành lþ 1.3 ban ¦u ÷ñc chùng minh cho chu©n Frobenius v o n«m 1936 bði Eckart v Young [3]. V o n«m 1960 Minsky ¢ chùng minh ành lþ cho chu©n 2, tø â ành lþ 1.3 ÷ñc gåi l ành lþ Eckart-Young-Mirsky. ành lþ 1.4 (ành lþ xen k³ c¡c gi¡ trà k¼ dà) Cho C l ma trªn cï m × n vîi gi¡ trà k¼ dà γ1 ≥ · · · ≥ γmin . Cho D l ma trªn min{m,n} con cï p × q cõa C vîi gi¡ trà k¼ dà δ1 ≥ · · · ≥ δmin{p,q}. º thuªn ti»n, ta ành ngh¾a γt = 0 vîi min{m, n} < t ≤ max{m, n} v δt = 0 vîi min{p, q} < t ≤ max{p, q}. Khi â γi ≥ δi , i = 1, . . . , min{p, q}, (1.16) δi ≥ γi+(m−p)+(n−q) , i ≤ min{p + q − m, p + q − n}. (1.17)
14 Chó þ 1.1 N¸u ma trªn D câ ÷ñc b¬ng c¡ch xâa mët cët cõa C th¼ ta câ N¸u m ≥ n : γ1 ≥ δ1 ≥ γ2 ≥ δ2 ≥ · · · ≥ δn−1 ≥ γn ≥ 0; (1.18) N¸u m < n : γ1 ≥ δ1 ≥ γ2 ≥ δ2 ≥ · · · ≥ γm ≥ δm ≥ 0. (1.19) 1.2.2. Nghi»m b¼nh ph÷ìng tèi thiºu v SVD SVD l mët cæng cö m¤nh º gi£i b i to¡n b¼nh ph÷ìng tèi thiºu bði v¼ ta ÷a ma trªn trüc giao C v· ma trªn ÷íng ch²o theo cæng thùc (1.11). Ta câ k¸t qu£ cì b£n sau ¥y ành lþ 1.5 (Nghi»m b¼nh ph÷ìng tèi thiºu câ chu©n nhä nh§t) Gi£ sû SVD cõa ma trªn A ∈ Rm×n ÷ñc bði cæng thùc (1.4) , tùc l A = ni=1 σi0 u0i v 0 Ti v gi£ sû rank(A) = r. N¸u b ∈ Rm th¼ P r −1 T X 0 x = σ 0 i vi0 u0 i b (1.20) i=1 cüc tiºu hâa kAx − bk2 v câ chu©n nhä nh§t trong t§t c£ c¡c cüc tiºu. Hìn núa, m T X 02 0 r = kAx − bk22 = (u0 i b)2 . (1.21) i=r+1 Ta câ thº vi¸t (1.20) v (1.21) d÷îi d¤ng sau x0 = A† b v r02 = k(I − AA† )bk22 , trong â A† = V 0 Σ0 † U 0 T , Σ0 † = diag(σ 1 0 −1 , · · · , σ 0 −1 r , 0, · · · , 0) ∈ R n×m ÷ñc gåi l gi£ nghàch £o cõa A. 1.3. Ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n 1.3.1. Thi¸t lªp b i to¡n º thi¸t lªp ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n (TLS), tr÷îc ti¶n ta ph¡t biºu l¤i ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu theo mët c¡ch kh¡c
15 ành ngh¾a 1.2 Cho mët h» qu¡ x¡c ành gçm m ph÷ìng tr¼nh Ax ≈ b vîi n ©n, ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu l i t¼m cüc tiºu min kb − b0 k2 , (1.22) b0 ∈Rm vîi b0 ∈ R(A). (1.23) Khi t¼m ÷ñc cüc tiºu b0 th¼ n¸u x thäa m¢n Ax = b0 th¼ x ÷ñc gåi l nghi»m b¼nh ph÷ìng tèi thiºu v ∆b0 = b − b0 l hi»u ch¿nh b¼nh ph÷ìng tèi thiºu (Least square correction). Ph÷ìng tr¼nh (1.24) v (1.25) thäa m¢n n¸u b0 l ph²p chi¸u trüc giao cõa b l¶n R(A). Nh÷ vªy, ta th§y r¬ng èi vîi ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu th¼ ch¿ câ v¸ ph£i b câ sai sè (câ nhi¹u) cán ma trªn A ÷ñc cho ch½nh x¡c. Tuy nhi¶n i·u ki»n n y khæng thüc t¸ v¼ c¡c mæ h¼nh ho°c c¡c sai sè o ¤c luæn £nh h÷ðng tîi ma trªn A. B¬ng c¡ch x²t tr÷íng hñp ma trªn A câ nhi¹u, ta d¨n tîi b i to¡n b¼nh ph÷ìng tèi thiºu to n ph¦n nh÷ sau ành ngh¾a 1.3 Cho mët h» qu¡ x¡c ành câ m ph÷ìng tr¼nh tuy¸n t½nh Ax ≈ b vîi n ©n, ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n l i t¼m minimize ˆ ˆb]kF , k[A; b] − [A; (1.24) ˆ ˆb]∈Rm×(n+1) [A; vîi ˆb ∈ R(A). ˆ (1.25) Khi t¼m ÷ñc cüc tiºu ˆ ˆb] [A, th¼ n¸u x thäa m¢n ˆ = ˆb Ax th¼ x ÷ñc gåi l nghi»m b¼nh ph÷ìng tèi thiºu to n ph¦n v [∆A; ˆ ∆ˆb] = ˆ ˆb] l hi»u ch¿nh b¼nh ph÷ìng tèi thiºu to n ph¦n (Total least [A; b] − [A;
16 square correction). Ta k½ hi»u nghi»m b¼nh ph÷ìng tèi thiºu to n ph¦n l xˆ. Mët trong nhúng ùng döng quan trång cõa b i to¡n TLS l ÷îc l÷ñng tham sè trong mæ h¼nh bi¸n câ sai sè. Gi£ sû r¬ng ta câ m gi¡ trà o cõa A, b li¶n h» vîi n tham sè ch÷a bi¸t x bði ph÷ìng tr¼nh A0 x = b0 , A = A0 + ∆A, b = b0 + ∆b, vîi ∆A, ∆b l c¡c sai sè o ¤c. Gi£ sû r¬ng A0 câ h¤ng ¦y õ v c¡c h ng cõa [∆A; ∆b] l ëc lªp tuy¸n t½nh v câ còng ph¥n bè vîi gi¡ trà trung b¼nh b¬ng 0. Khi â nghi»m TLS xˆ cõa ph÷ìng tr¼nh Ax = b ÷îc l÷ñng gi¡ trà tham sè ch½nh x¡c x0 ÷ñc cho bði A†b0 , tùc l xˆ hëi tö tîi x0 khi m ti¸n ra væ còng. 1.3.2. Nghi»m cì b£n Sau ¥y ta s³ sû döng kÿ thu¥t ph¥n t½ch gi¡ trà k¼ dà (SVD) º gi£i b i to¡n b¼nh ph÷ìng tèi thiºu to n ph¦n. Ta chuyºn h» Ax = b v· d¤ng [A; b][x; −1]T = 0 (1.26) Gi£ sû (1.5) l ph¥n t½ch gi¡ trà k¼ dà cõa [A; b]. N¸u σn+1 6= 0 th¼ ma tr¥n [A; b] h¤ng n+1 v S l khæng gian sinh bði c¡c dáng cõa [A; b] tròng vîi Rn+1 . Sû döng ành lþ 1.3, x§p x¿ b¼nh ph÷ìng tèi thiºu to n ph¦n ˆ ˆb] tèt nh§t h¤ng n cõa [A; b] ÷ñc cho bði [A; ˆ ˆb] = U ΣV [A; ˆ T, vîi ˆ = diag(σ1 , · · · , σn , 0). Σ (1.27) Hi»u ch¿nh b¼nh ph÷ìng tèi thiºu to n ph¦n nhä nh§t ÷ñc cho bði σn+1 = min ˆ ˆb]kF k[A; b] − [A; ˆ ˆb])=n rank([A; v ˆ ˆb] = [∆A; [A; b] − [A; ˆ ∆ˆb] = σn+1 un+1 v T . (1.28) n+1 Chó þ r¬ng ma trªn hi»u ch¿nh TLS câ h¤ng b¬ng 1 v tªp c¡c gi¡ trà x§p x¿ ˆ ˆb][xT ; −1]T = 0 [A; (1.29)
17 l t÷ìng th½ch v nghi»m cõa chóng ÷ñc cho bði duy nh§t v²c tì vn+1 (tùc l cët cuèi còng cõa V) thuëc ˆ ˆb]. N [A; Nghi»m TLS ÷ñc cho bði v²c tì vn+1 sau khi t l» hâa l¤i cho th nh ph¦n cuèi còng l −1 ho°c −1 [xT ; −1]T = vn+1 . (1.30) vn+1,n+1 N¸u vn+1,n+1 6= 0 th¼ ˆb = Aˆ ˆx = −1 ˆ 1,n+1 , . . . , vn,n+1 ]T ∈ R(A) ˆ A[v vn+1,n+1 Nh÷ vªy (1.25) ÷ñc thäa m¢n, do â xˆ l nghi»m TLS. ành lþ 1.6 (Nghi»m cõa b i to¡n TLS Ax ≈ b) Gi£ sû (1.4) v (1.5) t÷ìng ùng l SVD cõa ma trªn A v [A; b]. N¸u σn0 > σn+1 th¼ ˆ ˆb] = U ΣV [A; ˆ T v Σˆ = diag(σ1, . . . , σn, 0), (1.31) vîi ma trªn hi»u ch¿nh TSL t÷ìng ùng ˆ ∆ˆb] = [A; b] − [A; [∆A; ˆ ˆb] = σn+1 un+1 v T , (1.32) n+1 gi£i b i to¡n (1.24) v (1.25) v tçn t¤i duy nh§t nghi»m −1 xˆ = [v1,n+1 , · · · , vn,n+1 ]T (1.33) vn+1,n+1 cõa b i to¡n Ax ˆ = ˆb. Chùng minh. Theo ành lþ 1.4 cho c¡c gi¡ trà k¼ dà, ta câ σ1 ≥ σ10 ≥ · · · ≥ σn ≥ σn0 ≥ σn+1 . Do σn0 > σn+1 n¶n σn+1 khæng tròng vîi b§t k¼ gi¡ trà k¼ dà n o cõa [A; b]. N¸u " # " # y y [A; b]T [A; b] 2 = σn+1 v y 6= 0 ⇒ AT Ay = σn+1 2 y. 0 0 Do â m¨u thu¨n vîi i·u ki»n σ 0 2n l gi¡ trà ri¶ng nhä nh§t cõa AT A. Nh÷ vªy, ˆ ˆb]) ph£i chùa v²c tì câ th nh ph¦n thù n + 1 kh¡c 0. Do N ([A;
18 vªy, b i to¡n TLS câ nghi»m. V¼ ˆ ˆb]) = 1 dim N ([A; n¶n nghi»m n y l duy nh§t. Hìn núa, sû döng ành lþ 1.3, x§p x¿ TLS ˆ ˆb] [A; h¤ng n cõa [A; b] ÷ñc cho bði ˆ ˆb] = U ΣV [A; ˆ T v ˆ = diag(σ1 , . . . , σn , 0). Σ Hi»u ch¿nh TLS nhä nh§t l σn+1 = min ˆ ˆb]k k[A; b] − [A; ˆ ˆb])=n rank([A; v ˆ ˆb] = [∆A; [A; b] − [A; ˆ ∆ˆb] = σn+1 un+1 v T . n+1 K¸t hñp vîi ˆ ˆb]) = 1, dim N ([A; ta câ ˆ ˆb][x0T ; −1]T = 0. [A; Tø â ta câ thº k¸t luªn ˆb = Aˆ ˆx = −1 ˆ 1,n+1 , · · · , vn,n+1 ]T ∈ R(A). ˆ A[v vn+1,n+1 Nh÷ vªy −1 xˆ = [v1,n+1 , · · · , vn,n+1 ]T . vn+1,n+1 Ta câ i·u ph£i chùng minh. T½nh ch§t cõa nghi»m TLS xˆ v hi»u ch¿nh TLS nhä nh§t σn+1 ÷ñc tr¼nh b y trong ành lþ sau ¥y ành lþ 1.7 (Biºu di¹n d¤ng âng cõa nghi»m TLS) Gi£ sû (1.4) v (1.5) t÷ìng ùng l SVD cõa ma trªn A v [A; b]. N¸u σn0 > σn+1 th¼ xˆ = (AT A − σn+1 2 I)−1 AT b (1.34) v n 2 h X (u0 Ti b)2 i σn+1 1+ 0 2 2 = minn kAx − bk22 . (1.35) i=1 σ i − σn+1 x∈R