Tài liệu 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.3. 1.4. 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 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 1.3.2. Nghi»m cì b£n . . . . . . . . . . . . . . . . . . 14 . . . . . . . . . . . . . . . . . . . . 16 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 th­c m­c 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 s­c ¸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 s­c 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 A ∈ Rm×n t¼m. Vîi B ∈ Rm×d v  m > n, cho tr÷îc v  AX ≈ B , X ∈ Rn×d vîi c¡c ma trªn ch÷a bi¸t, ang c¦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 b­t ¦u b¬ng mët ph÷ìng tr¼nh tuy¸n t½nh sau α1 x1 + · · · + αn xn = β trong â α1 , . . . , αn v  β l  c¡c bi¸n v  x = [x1 , . . . , xn ]T ∈ Rn (0.1) 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 αi , i = 1, . . . , n l  ma trªn câ h ng thù v  v²c tì b ∈ Rm chùa β. Ax = b i t÷ìng ùng chùa c¡c dú ki»n Khi â ta câ h» (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 = β. B i to¡n °t ra l  tø x. sè (0.3) m o ¤c cõa c¡c bi¸n α v  β , ta i ÷îc l÷ñng tham Ta s³ i gi£i h» (0.2) vîi A = [a1 , . . . , am ]T v  b = [b1 , . . . , bm ]T trong â vîi ∆ai , ∆bi bi¸n ai = a0i + ∆ai , (0.4) bi = b0i + ∆bi , i = 1, . . . , m, (0.5) l  c¡c sai sè cëng v o c¡c dú ki»n ch½nh x¡c a0i , b0i cõa c¡c α, β. N¸u α l  o ÷ñc ch½nh x¡c, tùc l  khi o β chùa trong v¸ ph£i b. ∆ai = 0, khi â sai sè ch¿ x£y ra 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 ai bi x = Pi=1 n 2 i=1 ai 0 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 b x = Pni=1 i . i=1 ai bi 0 Tuy nhi¶n trong thüc t¸, c¡c bi¸n ÷ñc o luæn câ sai sè, ngh¾a l  v  ∆bi 6= 0. ∆ai 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 • R(S) (t÷ìng ùng Rr (S)) c¡c h ng) cõa ma trªn l  nh¥n cõa • A S , N (S) kþ hi»u l  khæng gian v²c tì khæng ho°c S. Ma trªn ÷íng ch²o aij = 0 AT . l  khæng gian sinh bði c¡c cët (t÷ìng ùng A cï m×n A = diag(α1 , · · · , αp ), vîi ÷ìc kþ hi»u l  vîi i 6= j v  • Ma trªn ìn và cï • Cho ph÷ìng tr¼nh aii = αi m×m vîi k½ hi»u l  vîi p = min {m, n} i = 1, . . . , p. ÷ñc k½ hi»u l  Im hay ìn gi£n l  AX = B trong â A l  ma trªn cï m × n, X l  ma trªn cï I. (1.1) 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  Trong tr÷íng hñp v²c tì • x, b d = 1, X̂ . ta câ thº k½ hi»u c¡c ma trªn X, B bði c¡c 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 2 t kM kF = mij = tr(M T M ), (1.2) i=1 i=1 trong â tr(M • T 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 nhi·u hìn sè ©n, tùc l  tr÷íng hñp b∈ / R(A) A ∈ Rm×n . Khi sè ph÷ìng tr¼nh m > n th¼ h» ÷ñc gåi l  h» qu¡ x¡c ành. Trong 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 , x∈Rn Cüc tiºu Ax ≈ b. x0 A ∈ Rm×n , b ∈ Rm . (1.6) b§t ký ÷ñc gåi l  nghi»m b¼nh ph÷ìng tèi thiºu cõa h» 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â s¡t b = [b1 , . . . , bm ]T li¶n h» vîi n tham sè ch÷a bi¸t m quan x = [x1 , . . . , xn ]T bði ph÷ìng tr¼nh Ax = b0 , vîi ∆b [∆b1 , . . . , ∆bm ]T Ta s³ gi£ sû r¬ng A v  ∆bi , i = 1, 2, . . . , m câ h¤ng l  Khi â ÷îc l÷ñng LS x0 b = b0 + ∆b, n v  ∆b l  c¡c sai sè ng¨u nhi¶n. câ gi¡ trà trung b¼nh b¬ng 0. 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 AT (b − Ax0 ) = z 6= 0, v  °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÷ ph÷ìng tèi thiºu ph£i b x0 r0 = b − Ax0 l  trüc giao vîi mi·n gi¡ trà cõa nghi»m b¼nh R(A) cõa A. Do â v¸ ÷ñc ph¥n t½ch th nh hai ph¦n trüc giao b = Ax0 + r0 = b0 + r0 , trong â b0 l  ph²p chi¸u trüc giao cõa r0 ⊥ Ax0 = b0 , 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, trong â PA = A(AT A)−1AT l  ph²p chi¸u trüc giao l¶n R(A). (1.10) 11 N¸u rank(A) N¸u x = r < n, B i to¡n (1.6) l  h¤ng thi¸u v  câ væ sè nghi»m. 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 tçn t¤i ma trªn trüc giao U = [u1, . . . , cm] ∈ Rm×m v  V Rn×n sao cho U T CV = Σ = diag(σ1 , . . . , σp ), C ∈ Rm×n , th¼ = [u1 , . . . , cn ] ∈ σ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à 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à. ÷ñc gåi l  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 nh÷ sau σ1 ≥ · · · ≥ σr > σr+1 = · · · = σp = 0, r ÷ñc x¡c ành 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 Ur Σr VrT C= = r X σi ui viT . (1.13) i=1 Ph÷ìng tr¼nh (1.13) ÷ñc gåi l  trªn C h¤ng r th nh têng cõa ph¥n t½ch hai ngæi, tùc l  ph¥n t½ch ma 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 kCkF = m X n X c2ij = σ12 + · · · + σp2 , p = min{m, n}, i=1 j=1 kCkF = sup y6=1 kCyk2 = σ1 . kyk2 Tø ph÷ìng tr¼nh (1.11) ta suy ra r¬ng C T C = V ΣT ΣV T Do â σi2 , i = 1, . . . , p CT C khæng ¥m V½ dö 1.1 v  trong â γ CC T = U ΣΣT U T . l  gi¡ trà ri¶ng cõa ma trªn èi xùng, x¡c ành CC T vîi c¡c v²c tì ri¶ng t÷ìng ùng l  X²t tr÷íng hñp C = [c1 , c2 ], v  vîi n = 2, cho cT1 c2 = cos γ c1 " l  gâc giúa hai v²c tì CT C = vi v  v  kc1 k2 = kc2 k2 = 1, c2 . Ma trªn 1 cos γ cos γ 1 # v  ui . 13 câ c¡c gi¡ trà ri¶ng γ γ λ1 = 2 cos2 , λ2 = 2 sin2 2 2 do â σ1 = C¡c v²c tì k¼ dà ph£i cõa √ C √ γ γ 2 cos , σ2 = 2 sin . 2 2 l  " # " # 1 1 1 1 v1 = √ ; v2 = √ . 2 1 2 −1 C¡c v²c tì k¼ dà tr¡i cõa u1 = C l  1 1 (c + c ); u = (c1 − c2 ). 1 2 2 2 cos γ2 2 sin γ2 ành lþ 1.3 (ành lþ x§p x¿ ma trªn Eckart-Young-Mirsky) Cho T i=1 σi ui vi vîi r = rankC. kC − Dk2 = kC − Ck k2 = σk+1 (1.14) ph¥n t½ch SVD cõa C ∈ Rm×n câ d¤ng C = P N¸u k < r v  Ck = ki=1 σiuiviT th¼ min rank(D)=k Pr v  min rank(D)=k v u p uX kC − DkF = kC − Ck kF = t σi2 , p = min{m, n}. (1.15) 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 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 â min{m,n} γi ≥ δi , i = 1, . . . , min{p, q}, δi ≥ γi+(m−p)+(n−q) , i ≤ min{p + q − m, p + q − n}. (1.16) (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 P A = ni=1 σi0 u0i v 0 Ti v  gi£ sû rank(A) = r. N¸u b ∈ Rm th¼ 0 x = r X −1 T σ 0 i vi0 u0 i b (1.4) , tùc l  (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 02 0 r = kAx − bk22 = X T (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 trong â v  r02 = k(I − AA† )bk22 , A† = V 0 Σ0 † U 0 T , Σ0 † = ÷ñc gåi l  gi£ nghàch £o cõa A. 0 −1 diag(σ 1 n×m , · · · , σ 0 −1 r , 0, · · · , 0) ∈ R 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 n vîi Cho mët h» qu¡ x¡c ành gçm m ph÷ìng tr¼nh Ax ≈ b ©n, ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu l  i t¼m cüc tiºu min b0 ∈Rm kb − b0 k2 , (1.22) vîi b0 ∈ R(A). Khi t¼m ÷ñc cüc tiºu b0 th¼ n¸u x (1.23) thäa m¢n Ax = b0 x th¼ ÷ñ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 cõa b0 l  ph²p chi¸u trüc giao 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 hñp ma trªn A. B¬ng c¡ch x²t tr÷íng 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 t½nh Ax ≈ b vîi n Cho mët h» qu¡ x¡c ành câ m ph÷ìng tr¼nh tuy¸n ©n, ph÷ìng ph¡p b¼nh ph÷ìng tèi thiºu to n ph¦n l  i t¼m k[A; b] − [Â; b̂]kF , minimize (1.24) [Â;b̂]∈Rm×(n+1) vîi b̂ ∈ R(Â). Khi t¼m ÷ñc cüc tiºu [Â, b̂] th¼ n¸u x (1.25) thäa m¢n Âx = b̂ th¼ x ÷ñc gåi l  nghi»m b¼nh ph÷ìng tèi thiºu to n ph¦n v  [∆Â; ∆b̂] = [A; b] − [Â; b̂] l  hi»u ch¿nh b¼nh ph÷ìng tèi thiºu to n ph¦n (Total least 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â cõa A, b li¶n h» vîi n tham sè ch÷a bi¸t A0 x = b0 , vîi ∆A, ∆b h ng cõa m A0 câ h¤ng ¦y õ v  c¡c l  ëc lªp tuy¸n t½nh v  câ còng ph¥n bè vîi gi¡ trà l÷ñng gi¡ trà tham sè ch½nh x¡c khi bði ph÷ìng tr¼nh l  c¡c sai sè o ¤c. Gi£ sû r¬ng [∆A; ∆b] gi¡ trà o A = A0 + ∆A, b = b0 + ∆b, trung b¼nh b¬ng 0. Khi â nghi»m TLS x0 x m x0 x̂ cõa ph÷ìng tr¼nh ÷ñc cho bði Ax = b ÷îc A†b0 , tùc l  x̂ hëi tö tîi 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 Gi£ sû (1.5) l  ph¥n t½ch gi¡ trà k¼ dà cõa tr¥n [A; b] tròng vîi ph¦n h¤ng Rn+1 . [Â; b̂] n+1 v  S [A; b]. (1.26) N¸u σn+1 6= 0 th¼ ma l  khæng gian sinh bði c¡c dáng cõa [A; b] Sû döng ành lþ 1.3, x§p x¿ b¼nh ph÷ìng tèi thiºu to n tèt nh§t h¤ng n cõa [Â; b̂] = U Σ̂V T , [A; b] vîi ÷ñc cho bð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 rank([Â;b̂])=n k[A; b] − [Â; b̂]kF v  T [A; b] − [Â; b̂] = [∆Â; ∆b̂] = σn+1 un+1 vn+1 . (1.28) 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 (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ì (tùc l  cët cuèi còng cõa v²c tì vn+1 V) Nghi»m TLS ÷ñc cho bði sau khi t l» hâa l¤i cho th nh ph¦n cuèi còng l  [xT ; −1]T = N¸u N [Â; b̂]. thuëc vn+1,n+1 6= 0 −1 vn+1,n+1 −1 vn+1 . ho°c (1.30) th¼ b̂ = Âx̂ = −1 vn+1,n+1 Â[v1,n+1 , . . . , vn,n+1 ]T ∈ R(Â) 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.5) vn+1 (1.4) t÷ìng ùng l  SVD cõa ma trªn A v  [A; b]. N¸u σn0 > σn+1 th¼ [Â; b̂] = U Σ̂V T v  Σ̂ = diag(σ1, . . . , σn, 0), v  (1.31) vîi ma trªn hi»u ch¿nh TSL t÷ìng ùng T [∆Â; ∆b̂] = [A; b] − [Â; b̂] = σn+1 un+1 vn+1 , gi£i b i to¡n (1.24) v  (1.25) x̂ = (1.32) v  tçn t¤i duy nh§t nghi»m −1 vn+1,n+1 [v1,n+1 , · · · , vn,n+1 ]T (1.33) cõa b i to¡n Âx = 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 [A; b]T [A; b] " # y 0 2 = σn+1 " # y Do â m¨u thu¨n vîi i·u ki»n Nh÷ vªy, 0 σ 0 2n v  2 y 6= 0 ⇒ AT Ay = σn+1 y. l  gi¡ trà ri¶ng nhä nh§t cõa AT A. N ([Â; b̂]) ph£i chùa v²c tì câ th nh ph¦n thù n + 1 kh¡c 0. Do 18 vªy, b i to¡n TLS câ nghi»m. V¼ dim N ([Â; b̂]) = 1 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̂] h¤ng n cõa [A; b] σn+1 ÷ñc ÷ñc cho bði [Â; b̂] = U Σ̂V T v  Σ̂ = diag(σ1 , . . . , σn , 0). Hi»u ch¿nh TLS nhä nh§t l  σn+1 = min rank([Â;b̂])=n k[A; b] − [Â; b̂]k v  T [A; b] − [Â; b̂] = [∆Â; ∆b̂] = σn+1 un+1 vn+1 . K¸t hñp vîi dim N ([Â; b̂]) = 1, ta câ [Â; b̂][x0T ; −1]T = 0. Tø â ta câ thº k¸t luªn b̂ = Âx̂ = −1 vn+1,n+1 Nh÷ vªy x̂ = Â[v1,n+1 , · · · , vn,n+1 ]T ∈ R(Â). −1 vn+1,n+1 [v1,n+1 , · · · , vn,n+1 ]T . 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 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û v  (1.5) (1.4) t÷ìng ùng l  SVD cõa ma trªn A v  [A; b]. N¸u σn0 > σn+1 th¼ 2 x̂ = (AT A − σn+1 I)−1 AT b v  2 σn+1 h n X (u0 Ti b)2 i 1+ = minn kAx − bk22 . 2 2 0 x∈R σ i − σn+1 i=1 (1.34) (1.35)