ĐẠ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(cid:246)c l(cid:246)c
Trang
L(cid:237)i c£m (cid:236)n 2
L(cid:237)i n(cid:226)i (cid:31)ƒu 3
Ch(cid:247)(cid:236)ng 1 Gi(cid:238)i thi»u v• ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi
thi”u to(cid:160)n phƒn 6
1.1. Mºt sŁ k(cid:254) hi»u v(cid:160) ki‚n thøc c(cid:236) b£n . . . . . . . . . . . . . 6
1.2. Ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u . . . . . . . . . . . . . 8
1.2.1. Ph¥n t‰ch gi¡ tr(cid:224) k… d(cid:224) . . . . . . . . . . . . . . . . 11
1.2.2. Nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u v(cid:160) SVD . . . . . . . 14
1.3. Ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn . . . . . . . 14
1.3.1. Thi‚t l“p b(cid:160)i to¡n . . . . . . . . . . . . . . . . . . 14
1.3.2. Nghi»m c(cid:236) b£n . . . . . . . . . . . . . . . . . . . . 16
1.4. Thu“t to¡n b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn . . . . . . . . 20
Ch(cid:247)(cid:236)ng 2 Mºt sŁ øng d(cid:246)ng cıa ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng
tŁi thi”u to(cid:160)n phƒn 22
2.1. H(cid:231)i quy (cid:31)(cid:236)n tuy‚n t‰nh . . . . . . . . . . . . . . . . . . . . 22
2.2. H(cid:231)i quy phi tuy‚n . . . . . . . . . . . . . . . . . . . . . . . 26
2
L(cid:237)i c£m (cid:236)n
Lu“n v«n (cid:31)(cid:247)æc ho(cid:160)n th(cid:160)nh d(cid:247)(cid:238)i s(cid:252) ch¿ b£o v(cid:160) h(cid:247)(cid:238)ng d¤n t“n t…nh cıa
TS. Nguy„n Th(cid:224) Ng(cid:229)c Oanh. C(cid:230) (cid:31)¢ d(cid:160)nh nhi•u th(cid:237)i gian h(cid:247)(cid:238)ng d¤n v(cid:160)
gi£i (cid:31)¡p th›c m›c cıa t(cid:230)i trong suŁt qu¡ tr…nh l(cid:160)m lu“n v«n. T(cid:230)i xin
b(cid:160)y t(cid:228) lÆng bi‚t (cid:236)n s¥u s›c (cid:31)‚n c(cid:230).
T(cid:230)i xin gßi t(cid:238)i c¡c thƒy, c(cid:230) trong khoa To¡n - Tin cıa Tr(cid:247)(cid:237)ng (cid:30)⁄i
h(cid:229)c Khoa h(cid:229)c - (cid:30)⁄i h(cid:229)c Th¡i Nguy¶n l(cid:237)i c£m (cid:236)n s¥u s›c nh§t v• c(cid:230)ng
lao d⁄y dØ trong suŁt qu¡ tr…nh h(cid:229)c t“p t⁄i tr(cid:247)(cid:237)ng.
CuŁi c(cid:242)ng t(cid:230)i xin c£m (cid:236)n Ban gi¡m hi»u tr(cid:247)(cid:237)ng THPT Qu‚ Vª sŁ 1,
t“p th” c¡c thƒy c(cid:230) gi¡o trong tŒ To¡n-Tin cıa Tr(cid:247)(cid:237)ng, gia (cid:31)…nh, b⁄n
b– v(cid:160) ng(cid:247)(cid:237)i th¥n (cid:31)¢ quan t¥m, t⁄o (cid:31)i•u ki»n, (cid:31)ºng vi¶n, cŒ v(cid:244) (cid:31)” t(cid:230)i c(cid:226)
th” ho(cid:160)n th(cid:160)nh nhi»m v(cid:246) cıa m…nh.
Th¡i Nguy¶n, ng(cid:160)y...th¡ng 4 n«m 2019
H(cid:229)c vi¶n
Trƒn Th(cid:224) Thu H(cid:247)(cid:237)ng
3
L(cid:237)i n(cid:226)i (cid:31)ƒu
Ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn (Total least square
-TLS) (cid:31)(cid:247)æc gi(cid:238)i thi»u b(cid:240)i Golub v(cid:160) Van Loan ....nh(cid:247) mºt k(cid:255) thu“t gi£i
c¡c h» "qu¡ x¡c (cid:31)(cid:224)nh" (overdetermined system), tøc l(cid:160) nhœng h» c(cid:226)
sŁ ph(cid:247)(cid:236)ng tr…nh nhi•u h(cid:236)n sŁ 'n c(cid:226) d⁄ng AX ≈ B, v(cid:238)i c¡c ma tr“n A ∈ Rm×n v(cid:160) B ∈ Rm×d cho tr(cid:247)(cid:238)c v(cid:160) X ∈ Rn×d ch(cid:247)a bi‚t, (cid:31)ang cƒn t…m. V(cid:238)i m > n, n(cid:226)i chung kh(cid:230)ng c(cid:226) nghi»m ch‰nh x¡c X cho x§p x¿
(cid:31)ang t…m. Ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn l(cid:160) s(cid:252) tŒng qu¡t
qu¡ cıa ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u (Least square -LS) khi c£
ma tr“n A v(cid:160) B (cid:31)•u b(cid:224) nhi„u.
Ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn l(cid:160) mºt k(cid:255) thu“t hi»u
qu£ (cid:31)” (cid:247)(cid:238)c l(cid:247)æng tham sŁ tuy‚n t‰nh. B(cid:160)i to¡n (cid:247)(cid:238)c l(cid:247)æng tham sŁ tuy‚n
tinh (cid:31)¢ d¤n t(cid:238)i mºt l(cid:238)p rºng r¢i c¡c l(cid:190)nh v(cid:252)c khoa h(cid:229)c nh(cid:247) xß l(cid:254) t‰n hi»u,
(cid:31)i•u khi”n t(cid:252) (cid:31)ºng,. . . , v(cid:160) nhi•u øng d(cid:246)ng kh¡c trong k(cid:255) thu“t, thŁng
k¶, v“t l(cid:254), kinh t‚, sinh h(cid:229)c,. . . . N(cid:226) (cid:31)(cid:247)æc b›t (cid:31)ƒu b‹ng mºt ph(cid:247)(cid:236)ng tr…nh
tuy‚n t‰nh sau
(0.1) α1x1 + · · · + αnxn = β
trong (cid:31)(cid:226) α1, . . . , αn v(cid:160) β l(cid:160) c¡c bi‚n v(cid:160) x = [x1, . . . , xn]T ∈ Rn l(cid:160) v†c t(cid:236) tham sŁ (cid:31)(cid:176)c tr(cid:247)ng cho h» (0.1). B(cid:160)i to¡n (cid:31)(cid:176)t ra l(cid:160) tł dœ ki»n (cid:31)o (cid:31)(cid:247)æc
n(cid:160)o (cid:31)(cid:226) cıa c¡c bi‚n, ta x¡c (cid:31)(cid:224)nh mºt (cid:247)(cid:238)c l(cid:247)æng cıa tham sŁ ch(cid:247)a bi‚t
theo mºt c¡ch (cid:31)(cid:243)ng nh§t.
G(cid:229)i A ∈ Rm×n l(cid:160) ma tr“n c(cid:226) h(cid:160)ng thø i t(cid:247)(cid:236)ng øng chøa c¡c dœ ki»n
αi, i = 1, . . . , n v(cid:160) v†c t(cid:236) b ∈ Rm chøa β. Khi (cid:31)(cid:226) ta c(cid:226) h»
Ax = b (0.2)
4
l(cid:160) h» g(cid:231)m m ph(cid:247)(cid:236)ng tr…nh v(cid:160) n 'n.
V(cid:238)i c¡ch ti‚p c“n b(cid:160)i to¡n b‹ng ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u
th… ma tr“n A cıa c¡c dœ ki»n (cid:31)o αi (v‚ tr¡i cıa (0.2)) (cid:31)(cid:247)æc gi£ sß l(cid:160)
ch‰nh x¡c, kh(cid:230)ng c(cid:226) sai sŁ. Do (cid:31)(cid:226), c¡c sai sŁ (cid:31)•u (cid:31)(cid:247)æc t⁄o ra b(cid:240)i v†c t(cid:236)
quan s¡t b (tøc l(cid:160) v‚ ph£i cıa (0.2)). Tuy nhi¶n (cid:31)i•u gi£ sß n(cid:160)y kh(cid:230)ng
mang t‰nh th(cid:252)c t‚ b(cid:240)i t§t c¡c c¡c sai sŁ cıa m(cid:230) h…nh, sai sŁ (cid:31)o (cid:31)⁄c c(cid:244)ng
(cid:31)(cid:247)æc t⁄o ra b(cid:240)i c¡c dœ ki»n cıa ma tr“n A. Ti‚p c“n b…nh ph(cid:247)(cid:236)ng tŁi
thi”u to(cid:160)n phƒn mang (cid:254) ngh(cid:190)a th(cid:252)c t‚ h(cid:236)n khi x†t sai sŁ (cid:31)(cid:247)æc t⁄o ra c£
(cid:240) v†c t(cid:236) quan s¡t b v(cid:160) ma tr“n dœ li»u A.
(cid:30)” minh h(cid:229)a t‰nh hœu hi»u cıa ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u
to(cid:160)n phƒn so v(cid:238)i ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u, ta c(cid:226) th” x†t mºt
v‰ d(cid:246) trong tr(cid:247)(cid:237)ng hæp ta c(cid:226) mºt tham sŁ, tøc l(cid:160) v(cid:238)i n = 1. Ph(cid:247)(cid:236)ng
tr…nh (0.1) tr(cid:240) th(cid:160)nh
αx = β. (0.3)
B(cid:160)i to¡n (cid:31)(cid:176)t ra l(cid:160) tł m (cid:31)o (cid:31)⁄c cıa c¡c bi‚n α v(cid:160) β, ta (cid:31)i (cid:247)(cid:238)c l(cid:247)æng tham sŁ x. Ta s‡ (cid:31)i gi£i h» (0.2) v(cid:238)i A = [a1, . . . , am]T v(cid:160) b = [b1, . . . , bm]T trong (cid:31)(cid:226)
i + ∆ai,
(0.4)
i + ∆bi, i = 1, . . . , m,
i cıa c¡c
i , b0
(0.5) ai = a0 bi = b0
v(cid:238)i ∆ai, ∆bi l(cid:160) c¡c sai sŁ cºng v(cid:160)o c¡c dœ ki»n ch‰nh x¡c a0 bi‚n α, β.
N‚u α l(cid:160) (cid:31)o (cid:31)(cid:247)æc ch‰nh x¡c, tøc l(cid:160) ∆ai = 0, khi (cid:31)(cid:226) sai sŁ ch¿ x£y ra khi (cid:31)o β chøa trong v‚ ph£i b. Trong tr(cid:247)(cid:237)ng hæp n(cid:160)y ta c(cid:226) th” sß d(cid:246)ng
ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u (cid:31)” gi£i ph(cid:247)(cid:236)ng tr…nh (0.2), tøc l(cid:160) ta
m (cid:88)
c(cid:252)c ti”u h(cid:226)a tŒng c¡c b…nh ph(cid:247)(cid:236)ng c(cid:226) d⁄ng
i=1
(bi − aix)2.
Trong tr(cid:247)(cid:237)ng hæp n(cid:160)y, b‹ng c¡ch khai tri”n tŒng tr¶n th… c(cid:252)c ti”u hay
5
(cid:247)(cid:238)c l(cid:247)æng x(cid:48) cıa x (cid:31)(cid:247)æc cho b(cid:240)i c(cid:230)ng thøc
i=1 aibi i=1 a2 i
x(cid:48) = (cid:80)n (cid:80)n
N‚u β kh(cid:230)ng c(cid:226) sai sŁ, tøc l(cid:160) ∆bi = 0, ta vi‚t l⁄i ph(cid:247)(cid:236)ng tr…nh (0.1)
d(cid:247)(cid:238)i d⁄ng
= α. β x
i=1 b2 i i=1 aibi
. x(cid:48) = Sß d(cid:246)ng ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u, b‹ng c¡ch c(cid:252)c ti”u h(cid:226)a tŒng b…nh ph(cid:247)(cid:236)ng sai ph¥n ta thu (cid:31)(cid:247)æc (cid:247)(cid:238)c l(cid:247)æng tŁt nh§t x(cid:48)(cid:48) nh(cid:247) sau (cid:80)n (cid:80)n
Tuy nhi¶n trong th(cid:252)c t‚, c¡c bi‚n (cid:31)(cid:247)æc (cid:31)o lu(cid:230)n c(cid:226) sai sŁ, ngh(cid:190)a l(cid:160) ∆ai (cid:54)= 0 v(cid:160) ∆bi (cid:54)= 0. Trong tr(cid:247)(cid:237)ng hæp n(cid:160)y, ta cƒn sß d(cid:246)ng ph(cid:247)(cid:236)ng ph¡p b…nh
ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn (cid:31)” nghi¶n cøu b(cid:160)i to¡n, c¡ch ti‚p c“n b(cid:160)i
to¡n b‹ng ph(cid:247)(cid:236)ng ph¡p n(cid:160)y mang nhi•u (cid:254) ngh(cid:190)a th(cid:252)c t‚ h(cid:236)n.
Lu“n v«n (cid:31)(cid:247)æc chia l(cid:160)m hai ch(cid:247)(cid:236)ng. Ch(cid:247)(cid:236)ng 1 gi(cid:238)i thi»u v• ph(cid:247)(cid:236)ng
ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn c(cid:242)ng mºt sŁ ki‚n thøc li¶n quan
nh(cid:247): Ph¥n t‰ch gi¡ tr(cid:224) k… d(cid:224), nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u, nghi»m b…nh
ph(cid:247)(cid:236)ng tŁi thi”u c(cid:226) chu'n nh(cid:228) nh§t, nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n
phƒn, (cid:30)(cid:224)nh l(cid:254) v• nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn,. . . . Ch(cid:247)(cid:236)ng 2
cıa lu“n v«n tr…nh b(cid:160)y mºt sŁ øng d(cid:246)ng cıa ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng
tŁi thi”u to(cid:160)n phƒn trong nghi¶n cøu h(cid:231)i quy (cid:31)(cid:236)n tuy‚n t‰nh v(cid:160) h(cid:231)i quy
phi tuy‚n. Mºt sŁ v‰ d(cid:246) sŁ (cid:31)(cid:247)æc tr…nh b(cid:160)y (cid:31)” minh h(cid:229)a cho t‰nh hi»u
qu£ cıa ph(cid:247)(cid:236)ng ph¡p.
6
Ch(cid:247)(cid:236)ng 1
Gi(cid:238)i thi»u v• ph(cid:247)(cid:236)ng ph¡p b…nh
ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn
Trong ch(cid:247)(cid:236)ng n(cid:160)y, ch(cid:243)ng t(cid:230)i tr…nh b(cid:160)y mºt sŁ ki‚n thøc li¶n quan
t(cid:238)i ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u, ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi
thi”u to(cid:160)n phƒn v(cid:160) c(cid:226) minh h(cid:229)a mºt v(cid:160)i v‰ d(cid:246) khi sß d(cid:246)ng hai ph(cid:247)(cid:236)ng
1.1. Mºt sŁ k(cid:254) hi»u v(cid:160) ki‚n thøc c(cid:236) b£n
ph¡p n(cid:226)i tr¶n.
• Ma tr“n chuy”n v(cid:224) cıa ma tr“n A (cid:31)(cid:247)(cid:236)c k(cid:254) hi»u l(cid:160) AT . • R(S) (t(cid:247)(cid:236)ng øng Rr(S)) l(cid:160) kh(cid:230)ng gian sinh b(cid:240)i c¡c cºt (t(cid:247)(cid:236)ng øng c¡c h(cid:160)ng) cıa ma tr“n S, N (S) k(cid:254) hi»u l(cid:160) kh(cid:230)ng gian v†c t(cid:236) kh(cid:230)ng ho(cid:176)c
l(cid:160) nh¥n cıa S.
• Ma tr“n (cid:31)(cid:247)(cid:237)ng ch†o A c(cid:239) m × n k‰ hi»u l(cid:160)
A = diag(α1, · · · , αp), v(cid:238)i p = min {m, n}
v(cid:238)i aij = 0 v(cid:238)i i (cid:54)= j v(cid:160) aii = αi v(cid:238)i i = 1, . . . , p.
• Ma tr“n (cid:31)(cid:236)n v(cid:224) c(cid:239) m × m (cid:31)(cid:247)æc k‰ hi»u l(cid:160) Im hay (cid:31)(cid:236)n gi£n l(cid:160) I. • Cho ph(cid:247)(cid:236)ng tr…nh
AX = B (1.1)
trong (cid:31)(cid:226) A l(cid:160) ma tr“n c(cid:239) m × n, X l(cid:160) ma tr“n c(cid:239) n × d, v(cid:160) B l(cid:160) ma
7
tr“n c(cid:239) m × d.
Nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u c(cid:226) chu'n nh(cid:228) nh§t cıa ph(cid:247)(cid:236)ng tr…nh (1.1) (cid:31)(cid:247)æc k(cid:254) hi»u l(cid:160) X (cid:48), nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn c(cid:226) chu'n nh(cid:228) nh§t (cid:31)(cid:247)æc k(cid:254) hi»u l(cid:160) ˆX.
Trong tr(cid:247)(cid:237)ng hæp d = 1, ta c(cid:226) th” k‰ hi»u c¡c ma tr“n X, B b(cid:240)i c¡c
v†c t(cid:236) x, b t(cid:247)(cid:236)ng øng.
• Chu'n Frobenius cıa ma tr“n M c(cid:239) m × n (cid:31)(cid:247)æc (cid:31)(cid:224)nh ngh(cid:190)a b(cid:240)i
n (cid:88)
m (cid:88)
ij =
i=1
i=1
(cid:113) m2 tr(M T M ), (1.2) (cid:107)M (cid:107)F = (cid:118) (cid:117) (cid:117) (cid:116)
trong (cid:31)(cid:226) tr(M T M ) l(cid:160) v‚t cıa ma tr“n M T M.
• Chu'n 2 hay chu'n Euclide cıa v†c t(cid:236) y trong kh(cid:230)ng gian n chi•u
n (cid:88)
(cid:31)(cid:247)æc (cid:31)(cid:224)nh ngh(cid:190)a b(cid:240)i
i=1
(1.3) (cid:107)y(cid:107)2 = (cid:118) (cid:117) (cid:117) (cid:116) y2 i .
• Ph¥n t‰ch gi¡ tr(cid:224) k… d(cid:224) - SVD.
K(cid:254) hi»u SVD cıa ma tr“n A c(cid:239) m × n, m > n c(cid:226) d⁄ng
A = U (cid:48)Σ(cid:48)V (cid:48)T , (1.4)
trong (cid:31)(cid:226)
1, · · · , u(cid:48)
n], U (cid:48)
2 = [u(cid:48)
n+1, · · · , u(cid:48)
m], u(cid:48)
i ∈ Rm, U (cid:48)T U (cid:48) = Im,
U (cid:48) = [U (cid:48)
2], U (cid:48) 1; U (cid:48) 1, · · · , v(cid:48)
V (cid:48) = [v(cid:48)
1 = [u(cid:48) n], v(cid:48) 1, · · · , σ(cid:48)
i ∈ Rn, V (cid:48)T V (cid:48) = In, n) ∈ Rm×n, σ(cid:48)
1 ≥ · · · ≥ σ(cid:48)
n ≥ 0.
Σ(cid:48) = diag(σ(cid:48)
Ta c(cid:244)ng k‰ hi»u SVD cıa ma tr“n [A; B] c(cid:239) m × (n + d), m > n c(cid:226) d⁄ng
[A; B] = U ΣV T , (1.5)
8
trong (cid:31)(cid:226)
U = [U1; U2], U1 = [u1, · · · , un], U2 = [un+1, · · · , um], ui ∈ Rm, U T U = Im,
(cid:33) (cid:32)
V = = [v1, · · · , vn+d], vi ∈ Rn+d, V T V = In+d,
(cid:32) V11 V12 V21 V22 (cid:33) 0 Σ = = diag(σ1, · · · , σn+t) ∈ Rm×(n+d), t = min{m − n, d}, Σ1 0 Σ2
Σ1 = diag(σ1, · · · , σn) ∈ Rn×n, Σ1 = diag(σn+1, · · · , σn+t) ∈ R(m−n)×d,
1.2. Ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u
v(cid:160) σ1 ≥ · · · ≥ σn+t ≥ 0.
Ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u (LS) l(cid:160) mºt c¡ch ti‚p c“n phŒ
bi‚n khi gi£i h» tuy‚n t‰nh qu¡ x¡c (cid:31)(cid:224)nh, tøc l(cid:160) sŁ ph(cid:247)(cid:236)ng tr…nh nhi•u
h(cid:236)n sŁ 'n. N(cid:226)i chung c¡c h» nh(cid:247) v“y kh(cid:230)ng c(cid:226) nghi»m nh(cid:247)ng ta t…m
nghi»m x§p x¿ cıa h» b‹ng c¡ch c(cid:252)c ti”u h(cid:226)a tŒng b…nh ph(cid:247)(cid:236)ng cıa sai
sŁ (cid:31)(cid:247)æc t⁄o th(cid:160)nh khi gi£i mØi ph(cid:247)(cid:236)ng tr…nh (cid:31)(cid:236)n l·. X†t b(cid:160)i to¡n t…m x ∈ Rn th(cid:228)a m¢n ph(cid:247)(cid:236)ng tr…nh
Ax = b,
trong (cid:31)(cid:226) b ∈ Rm (cid:31)¢ bi‚t v(cid:160) dœ li»u A ∈ Rm×n. Khi sŁ ph(cid:247)(cid:236)ng tr…nh nhi•u h(cid:236)n sŁ 'n, tøc l(cid:160) m > n th… h» (cid:31)(cid:247)æc g(cid:229)i l(cid:160) h» qu¡ x¡c (cid:31)(cid:224)nh. Trong
tr(cid:247)(cid:237)ng hæp b /∈ R(A) th… h» qu¡ x¡c (cid:31)(cid:224)nh kh(cid:230)ng c(cid:226) nghi»m ch‰nh x¡c,
do v“y ta sß d(cid:246)ng k‰ hi»u Ax ≈ b.
Nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u (cid:31)(cid:247)æc tr…nh b(cid:160)y trong (cid:31)(cid:224)nh ngh(cid:190)a d(cid:247)(cid:238)i
(cid:31)¥y.
(cid:30)(cid:224)nh ngh(cid:190)a 1.1 X†t b(cid:160)i to¡n t…m c(cid:252)c ti”u
(1.6) (cid:107)Ax − b(cid:107)2, A ∈ Rm×n, b ∈ Rm. min x∈Rn
C(cid:252)c ti”u x(cid:48) b§t k(cid:253) (cid:31)(cid:247)æc g(cid:229)i l(cid:160) nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u cıa h» Ax ≈ b.
9
Mºt trong nhœng øng d(cid:246)ng quan tr(cid:229)ng cıa b(cid:160)i to¡n LS l(cid:160) (cid:247)(cid:238)c l(cid:247)æng
tham sŁ trong m(cid:230) h…nh thŁng k¶ tuy‚n t‰nh. Gi£ sß r‹ng ta c(cid:226) m quan s¡t b = [b1, . . . , bm]T li¶n h» v(cid:238)i n tham sŁ ch(cid:247)a bi‚t x = [x1, . . . , xn]T b(cid:240)i ph(cid:247)(cid:236)ng tr…nh
Ax = b0, b = b0 + ∆b,
v(cid:238)i ∆b [∆b1, . . . , ∆bm]T v(cid:160) ∆bi, i = 1, 2, . . . , m l(cid:160) c¡c sai sŁ ng¤u nhi¶n. Ta s‡ gi£ sß r‹ng A c(cid:226) h⁄ng l(cid:160) n v(cid:160) ∆b c(cid:226) gi¡ tr(cid:224) trung b…nh b‹ng 0. Khi (cid:31)(cid:226) (cid:247)(cid:238)c l(cid:247)æng LS x(cid:48) th(cid:228)a m¢n hai (cid:31)i•u ki»n d(cid:247)(cid:238)i (cid:31)¥y
i) Kh(cid:230)ng c(cid:226) sai sŁ h» thŁng trong (cid:247)(cid:238)c l(cid:247)æng.
ii) C¡c (cid:247)(cid:238)c l(cid:247)æng l(cid:160) h(cid:160)m tuy‚n t‰nh cıa b.
T‰nh ch§t nghi»m cıa ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u (cid:31)(cid:247)æc tr…nh
b(cid:160)y trong (cid:31)(cid:224)nh l(cid:254) sau (cid:31)¥y.
(cid:30)(cid:224)nh l(cid:254) 1.1 (T‰nh ch§t nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u) (cid:30)(cid:176)t
S = {x ∈ Rn v(cid:238)i (cid:107)Ax − b(cid:107)2 −→ min}
l(cid:160) t“p c¡c nghi»m cıa b(cid:160)i to¡n (1.6). Khi (cid:31)(cid:226) ta c(cid:226)
x(cid:48) ∈ S ⇐⇒ AT (b − Ax(cid:48)) = 0. (1.7)
Chøng minh.
"⇐": Cho AT (b − Ax(cid:48)) = 0 v(cid:160) z ∈ Rn l(cid:160) mºt v†c t(cid:236) b§t k…. Khi (cid:31)(cid:226) ta
c(cid:226)
b − Az = b − Ax(cid:48) + A(x(cid:48) − z),
do (cid:31)(cid:226)
2 = (cid:107)b − Ax(cid:48)(cid:107)2 = (cid:107)b − Ax(cid:48)(cid:107)2
2 + 2 (cid:104)b − Ax(cid:48), A(x(cid:48) − z)(cid:105) + (cid:107)A(x(cid:48) − z)(cid:107)2 2 2 + 2 (cid:10)AT (b − Ax(cid:48)), x(cid:48) − z(cid:11) + (cid:107)A(x(cid:48) − z)(cid:107)2 2.
(cid:107)b − Az(cid:107)2
V… AT (b − Ax(cid:48)) = 0 n¶n
2 = (cid:107)b − Ax(cid:48)(cid:107)2
2 + (cid:107)A(x(cid:48) − z)(cid:107)2 2.
(cid:107)b − Az(cid:107)2
2 ≥ (cid:107)b − Ax(cid:48)(cid:107)2
2, ∀z ∈ Rn, tøc l(cid:160) x(cid:48) ∈ S.
Do (cid:31)(cid:226) (cid:107)b − Az(cid:107)2
10
"⇒": Ta chøng minh b‹ng ph£n chøng. Gi£ sß x(cid:48) ∈ S v(cid:160) AT (b − Ax(cid:48)) = z (cid:54)= 0, (cid:31)(cid:176)t u = x(cid:48) + (cid:15)z, (cid:15) > 0, ta c(cid:226)
b − Au = b − Ax(cid:48) − (cid:15)Az.
Khi (cid:31)(cid:226)
2 = (cid:107)b − Ax(cid:48)(cid:107)2 = (cid:107)b − Ax(cid:48)(cid:107)2
2
(cid:107)b − Au(cid:107)2
2 − 2(cid:15) (cid:104)b − Ax(cid:48), Az(cid:105) + (cid:15)2(cid:107) 2 − 2(cid:15) (cid:10)AT (b − Ax(cid:48)), z(cid:11) + (cid:15)2(cid:107)Az(cid:107)2 2 + (cid:15)2(cid:107)Az(cid:107)2 2 − 2(cid:15)(cid:107)z(cid:107)2 2.
2 ≥ (cid:107)b−Au(cid:107)2 Nh(cid:247) v“y khi (cid:15) (cid:31)ı nh(cid:228), ta c(cid:226) th” (cid:31)⁄t (cid:31)(cid:247)æc (cid:31)¡nh gi¡ (cid:107)b−Ax(cid:48)(cid:107)2 2, (cid:31)i•u n(cid:160)y m¥u thu¤n v(cid:238)i gi£ thi‚t x(cid:48) ∈ S. Ta nh“n (cid:31)(cid:247)æc (cid:31)i•u ph£i chøng
= (cid:107)b − Ax(cid:48)(cid:107)2
minh.
(cid:30)(cid:224)nh l(cid:254) 1.1 (cid:31)¢ ch¿ ra r‹ng phƒn d(cid:247) r(cid:48) = b − Ax(cid:48) cıa nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u x(cid:48) l(cid:160) tr(cid:252)c giao v(cid:238)i mi•n gi¡ tr(cid:224) R(A) cıa A. Do (cid:31)(cid:226) v‚ ph£i b (cid:31)(cid:247)æc ph¥n t‰ch th(cid:160)nh hai phƒn tr(cid:252)c giao
b = Ax(cid:48) + r(cid:48) = b(cid:48) + r(cid:48), r(cid:48) ⊥ Ax(cid:48) = b(cid:48),
trong (cid:31)(cid:226) b(cid:48) l(cid:160) ph†p chi‚u tr(cid:252)c giao cıa b l¶n R(A).
C(cid:244)ng tł (cid:30)(cid:224)nh l(cid:254) 1.1, ta suy ra r‹ng nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u s‡
th(cid:228)a m¢n ph(cid:247)(cid:236)ng tr…nh
AT Ax = AT b. (1.8)
Ta c(cid:226) h» qu£ sau
H» qu£ 1.1 (Nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u v(cid:160) phƒn d(cid:247)) N‚u
rank(A) = n th… B(cid:160)i to¡n (1.6) c(cid:226) duy nh§t mºt nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u x(cid:48) v(cid:160) (cid:31)(cid:247)æc cho b(cid:240)i c(cid:230)ng thøc
x(cid:48) = (AT A)−1AT b. (1.9)
V(cid:160) phƒn d(cid:247) t(cid:247)(cid:236)ng øng
r(cid:48) = b − Ax(cid:48) = b − b(cid:48), (1.10) b(cid:48) = PAb,
trong (cid:31)(cid:226) PA = A(AT A)−1AT l(cid:160) ph†p chi‚u tr(cid:252)c giao l¶n R(A).
11
N‚u rank(A) = r < n, B(cid:160)i to¡n (1.6) l(cid:160) h⁄ng thi‚u v(cid:160) c(cid:226) v(cid:230) sŁ nghi»m.
N‚u x l(cid:160) mºt c(cid:252)c ti”u v(cid:160) z ∈ N (A) th… x + z c(cid:244)ng l(cid:160) c(cid:252)c ti”u. Nghi»m
duy nh§t l(cid:160) nghi»m c(cid:226) chu'n 2 nh(cid:228) nh§t ch(cid:229)n ra tł t“p t§t c£ c¡c c(cid:252)c
ti”u
X = {x ∈ Rn : (cid:107)Ax − b(cid:107)2 min}.
Ta k‰ hi»u nghi»m n(cid:160)y l(cid:160) x(cid:48) (ch(cid:243) (cid:254) r‹ng trong tr(cid:247)(cid:237)ng hæp h⁄ng (cid:31)ƒy (cid:31)ı
th… ch¿ c(cid:226) duy nh§t mºt nghi»m LS v(cid:160) do (cid:31)(cid:226) n(cid:226) ph£i c(cid:226) chu'n 2 nh(cid:228)
nh§t).
Trong phƒn ti‚p theo ta s‡ tr…nh b(cid:160)y bi”u di„n nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u x(cid:48) v(cid:160) phƒn d(cid:247) r(cid:48) = b − Ax(cid:48) th(cid:230)ng qua Ph¥n t‰ch gi¡ tr(cid:224) k… d(cid:224)
(Singular Value Decomposition - SVD).
1.2.1. Ph¥n t‰ch gi¡ tr(cid:224) k… d(cid:224)
(cid:30)(cid:224)nh l(cid:254) 1.2 (Ph¥n t‰ch gi¡ tr(cid:224) k… d(cid:224) - SVD) N‚u C ∈ Rm×n, th… t(cid:231)n t⁄i ma tr“n tr(cid:252)c giao U = [u1, . . . , cm] ∈ Rm×m v(cid:160) V = [u1, . . . , cn] ∈ Rn×n sao cho
U T CV = Σ = diag(σ1, . . . , σp), σ1 ≥ · · · ≥ σp, p = min{m, n}.
(1.11)
Trong t(cid:160)i li»u tham kh£o [3] (cid:31)¢ c(cid:226) chøng minh chi ti‚t cho (cid:31)(cid:224)nh l(cid:254) n(cid:160)y.
C¡c gi¡ tr(cid:224) σi (cid:31)(cid:247)æc g(cid:229)i l(cid:160) gi¡ tr(cid:224) k(cid:253) d(cid:224) cıa C v(cid:160) t“p c¡c gi¡ tr(cid:224) k… d(cid:224) (cid:31)(cid:247)æc g(cid:229)i l(cid:160) phŒ k(cid:253) d(cid:224). C¡c v†c t(cid:236) ui v(cid:160) vi t(cid:247)(cid:236)ng øng l(cid:160) c¡c v†c t(cid:236) k… d(cid:224) tr¡i thø i v(cid:160) v†c t(cid:236) k… d(cid:224) ph£i thø i. Bº (ui, σi, vi) (cid:31)(cid:247)æc g(cid:229)i l(cid:160) gi£i k(cid:253) d(cid:224).
Tł (cid:31)(cid:226) ta c(cid:226)
i = 1, . . . , p. (1.12) Cvi = σiui v(cid:160) C T ui = σivi,
Ph¥n t‰ch gi¡ tr(cid:224) k… d(cid:224) c(cid:226) li¶n quan l(cid:238)n t(cid:238)i c§u tr(cid:243)c cıa ma tr“n. N‚u
ph¥n t‰ch gi¡ tr(cid:224) k… d(cid:224) cıa C (cid:31)(cid:247)æc cho b(cid:240)i (cid:30)(cid:224)nh l(cid:254) 1.2 r (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh
nh(cid:247) 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(cid:236)n nœa, n‚u (cid:31)(cid:176)t Ur = [u1, . . . , ur], diag(σ1, . . . , σr) v(cid:160) Vr = [v1, . . . , vr]
r (cid:88)
ta c(cid:226) khai tri”n SVD
r =
i=1
(1.13) C = UrΣrV T σiuivT i .
Ph(cid:247)(cid:236)ng tr…nh (1.13) (cid:31)(cid:247)æc g(cid:229)i l(cid:160) ph¥n t‰ch hai ng(cid:230)i, tøc l(cid:160) ph¥n t‰ch ma
tr“n C h⁄ng r th(cid:160)nh tŒng cıa r ma tr“n h⁄ng 1. Chu'n 2 v(cid:160) chu'n
m (cid:88)
n (cid:88)
Frobenius (cid:31)(cid:247)æc t‰nh th(cid:230)ng qua c¡c phƒn tß cıa SVD nh(cid:247) sau
ij = σ2 c2
1 + · · · + σ2 p,
i=1
p = min{m, n}, (cid:107)C(cid:107)F =
j=1 (cid:107)Cy(cid:107)2 (cid:107)y(cid:107)2
= σ1. (cid:107)C(cid:107)F = sup y(cid:54)=1
Tł ph(cid:247)(cid:236)ng tr…nh (1.11) ta suy ra r‹ng
i , i = 1, . . . , p l(cid:160) gi¡ tr(cid:224) ri¶ng cıa ma tr“n (cid:31)Łi xøng, x¡c (cid:31)(cid:224)nh
C T C = V ΣT ΣV T v(cid:160) CC T = U ΣΣT U T .
Do (cid:31)(cid:226) σ2 kh(cid:230)ng ¥m C T C v(cid:160) CC T v(cid:238)i c¡c v†c t(cid:236) ri¶ng t(cid:247)(cid:236)ng øng l(cid:160) vi v(cid:160) ui.
V‰ d(cid:246) 1.1 X†t tr(cid:247)(cid:237)ng hæp n = 2, cho
1 c2 = cos γ v(cid:160) (cid:107)c1(cid:107)2 = (cid:107)c2(cid:107)2 = 1,
C = [c1, c2], v(cid:238)i cT
trong (cid:31)(cid:226) γ l(cid:160) g(cid:226)c giœa hai v†c t(cid:236) c1 v(cid:160) c2. Ma tr“n
(cid:34) (cid:35) 1 cos γ C T C = cos γ 1
13
c(cid:226) c¡c gi¡ tr(cid:224) ri¶ng
λ1 = 2 cos2 γ 2 , λ2 = 2 sin2 γ 2
do (cid:31)(cid:226) √ √ 2 cos 2 sin . σ1 = , σ2 = γ 2 γ 2
C¡c v†c t(cid:236) k… d(cid:224) ph£i cıa C l(cid:160) (cid:34) (cid:35) (cid:34) (cid:35) 1 1 . v1 = ; v2 = 1 √ 2 1 √ 2 1 −1
C¡c v†c t(cid:236) k… d(cid:224) tr¡i cıa C l(cid:160)
i v(cid:238)i r = rankC.
i=1 σiuivT
u1 = (c1 + c2); u2 = (c1 − c2). 1 2 cos γ 2 1 2 sin γ 2
i=1 σiuivT i
th… (cid:30)(cid:224)nh l(cid:254) 1.3 ((cid:30)(cid:224)nh l(cid:254) x§p x¿ ma tr“n Eckart-Young-Mirsky) Cho ph¥n t‰ch SVD cıa C ∈ Rm×n c(cid:226) d⁄ng C = (cid:80)r N‚u k < r v(cid:160) Ck = (cid:80)k
(1.14) (cid:107)C − D(cid:107)2 = (cid:107)C − Ck(cid:107)2 = σk+1 min rank(D)=k
p (cid:88)
v(cid:160)
i=k+1
(cid:107)C − D(cid:107)F = (cid:107)C − Ck(cid:107)F = (cid:118) (cid:117) (cid:117) (cid:116) σ2 i , p = min{m, n}. (1.15) min rank(D)=k
(cid:30)(cid:224)nh l(cid:254) 1.3 ban (cid:31)ƒu (cid:31)(cid:247)æc chøng minh cho chu'n Frobenius v(cid:160)o n«m 1936
b(cid:240)i Eckart v(cid:160) Young [3]. V(cid:160)o n«m 1960 Minsky (cid:31)¢ chøng minh (cid:31)(cid:224)nh l(cid:254)
cho chu'n 2, tł (cid:31)(cid:226) (cid:30)(cid:224)nh l(cid:254) 1.3 (cid:31)(cid:247)æc g(cid:229)i l(cid:160) (cid:30)(cid:224)nh l(cid:254) Eckart-Young-Mirsky.
(cid:30)(cid:224)nh l(cid:254) 1.4 ((cid:30)(cid:224)nh l(cid:254) xen k‡ c¡c gi¡ tr(cid:224) k… d(cid:224)) Cho C l(cid:160) ma tr“n c(cid:239) m × n v(cid:238)i gi¡ tr(cid:224) k… d(cid:224) γ1 ≥ · · · ≥ γminmin{m,n}. Cho D l(cid:160) ma tr“n con c(cid:239) p × q cıa C v(cid:238)i gi¡ tr(cid:224) k… d(cid:224) δ1 ≥ · · · ≥ δmin{p,q}. (cid:30)” thu“n ti»n, ta (cid:31)(cid:224)nh ngh(cid:190)a γt = 0 v(cid:238)i min{m, n} < t ≤ max{m, n} v(cid:160) δt = 0 v(cid:238)i min{p, q} < t ≤ max{p, q}. Khi (cid:31)(cid:226)
i = 1, . . . , min{p, q}, (1.16) γi ≥ δi,
i ≤ min{p + q − m, p + q − n}. (1.17) δi ≥ γi+(m−p)+(n−q),
14
Ch(cid:243) (cid:254) 1.1 N‚u ma tr“n D c(cid:226) (cid:31)(cid:247)æc b‹ng c¡ch x(cid:226)a mºt cºt cıa C th…
ta c(cid:226)
(1.18) N‚u m ≥ n : γ1 ≥ δ1 ≥ γ2 ≥ δ2 ≥ · · · ≥ δn−1 ≥ γn ≥ 0;
(1.19) N‚u m < n : γ1 ≥ δ1 ≥ γ2 ≥ δ2 ≥ · · · ≥ γm ≥ δm ≥ 0.
1.2.2. Nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u v(cid:160) SVD
SVD l(cid:160) mºt c(cid:230)ng c(cid:246) m⁄nh (cid:31)” gi£i b(cid:160)i to¡n b…nh ph(cid:247)(cid:236)ng tŁi thi”u b(cid:240)i
v… ta (cid:31)(cid:247)a ma tr“n tr(cid:252)c giao C v• ma tr“n (cid:31)(cid:247)(cid:237)ng ch†o theo c(cid:230)ng thøc
(1.11). Ta c(cid:226) k‚t qu£ c(cid:236) b£n sau (cid:31)¥y
iv(cid:48)T
iu(cid:48)
i=1 σ(cid:48)
r (cid:88)
(cid:30)(cid:224)nh l(cid:254) 1.5 (Nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u c(cid:226) chu'n nh(cid:228) nh§t) Gi£ sß SVD cıa ma tr“n A ∈ Rm×n (cid:31)(cid:247)æc b(cid:240)i c(cid:230)ng thøc (1.4), tøc l(cid:160) A = (cid:80)n i v(cid:160) gi£ sß rank(A) = r. N‚u b ∈ Rm th…
i v(cid:48)
iu(cid:48)T i b
i=1
x(cid:48) = σ(cid:48)−1 (1.20)
c(cid:252)c ti”u h(cid:226)a (cid:107)Ax − b(cid:107)2 v(cid:160) c(cid:226) chu'n nh(cid:228) nh§t trong t§t c£ c¡c c(cid:252)c ti”u.
m (cid:88)
H(cid:236)n nœa,
2 =
i b)2.
i=r+1
r(cid:48)2 = (cid:107)Ax(cid:48) − b(cid:107)2 (u(cid:48)T (1.21)
Ta c(cid:226) th” vi‚t (1.20) v(cid:160) (1.21) d(cid:247)(cid:238)i d⁄ng sau
r , 0, · · · , 0) ∈ Rn×m
1 , · · · , σ(cid:48)−1
x(cid:48) = A†b v(cid:160) r(cid:48)2 = (cid:107)(I − AA†)b(cid:107)2 2,
1.3. Ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn
trong (cid:31)(cid:226) A† = V (cid:48)Σ(cid:48)†U (cid:48)T , Σ(cid:48)† = diag(σ(cid:48)−1 (cid:31)(cid:247)æc g(cid:229)i l(cid:160) gi£ ngh(cid:224)ch (cid:31)£o cıa A.
1.3.1. Thi‚t l“p b(cid:160)i to¡n
(cid:30)” thi‚t l“p ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn (TLS),
tr(cid:247)(cid:238)c ti¶n ta ph¡t bi”u l⁄i ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u theo mºt
c¡ch kh¡c
15
(cid:30)(cid:224)nh ngh(cid:190)a 1.2 Cho mºt h» qu¡ x¡c (cid:31)(cid:224)nh g(cid:231)m m ph(cid:247)(cid:236)ng tr…nh Ax ≈ b
v(cid:238)i n 'n, ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u l(cid:160) (cid:31)i t…m c(cid:252)c ti”u
(1.22) (cid:107)b − b(cid:48)(cid:107)2, min b(cid:48)∈Rm
v(cid:238)i
b(cid:48) ∈ R(A). (1.23)
Khi t…m (cid:31)(cid:247)æc c(cid:252)c ti”u b(cid:48) th… n‚u x th(cid:228)a m¢n
Ax = b(cid:48)
th… x (cid:31)(cid:247)æc g(cid:229)i l(cid:160) nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u v(cid:160) ∆b(cid:48) = b − b(cid:48) l(cid:160) hi»u
ch¿nh b…nh ph(cid:247)(cid:236)ng tŁi thi”u (Least square correction).
Ph(cid:247)(cid:236)ng tr…nh (1.24) v(cid:160) (1.25) th(cid:228)a m¢n n‚u b(cid:48) l(cid:160) ph†p chi‚u tr(cid:252)c giao cıa b l¶n R(A). Nh(cid:247) v“y, ta th§y r‹ng (cid:31)Łi v(cid:238)i ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng
tŁi thi”u th… ch¿ c(cid:226) v‚ ph£i b c(cid:226) sai sŁ (c(cid:226) nhi„u) cÆn ma tr“n A (cid:31)(cid:247)æc cho
ch‰nh x¡c. Tuy nhi¶n (cid:31)i•u ki»n n(cid:160)y kh(cid:230)ng th(cid:252)c t‚ v… c¡c m(cid:230) h…nh ho(cid:176)c
c¡c sai sŁ (cid:31)o (cid:31)⁄c lu(cid:230)n £nh h(cid:247)(cid:240)ng t(cid:238)i ma tr“n A. B‹ng c¡ch x†t tr(cid:247)(cid:237)ng
hæp ma tr“n A c(cid:226) nhi„u, ta d¤n t(cid:238)i b(cid:160)i to¡n b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n
phƒn nh(cid:247) sau
(cid:30)(cid:224)nh ngh(cid:190)a 1.3 Cho mºt h» qu¡ x¡c (cid:31)(cid:224)nh c(cid:226) m ph(cid:247)(cid:236)ng tr…nh tuy‚n
t‰nh Ax ≈ b v(cid:238)i n 'n, ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn l(cid:160)
(cid:31)i t…m
(1.24) (cid:107)[A; b] − [ ˆA; ˆb](cid:107)F , minimize [ ˆA;ˆb]∈Rm×(n+1)
v(cid:238)i
ˆb ∈ R( ˆA). (1.25)
Khi t…m (cid:31)(cid:247)æc c(cid:252)c ti”u [ ˆA, ˆb] th… n‚u x th(cid:228)a m¢n
ˆAx = ˆb
th… x (cid:31)(cid:247)æc g(cid:229)i l(cid:160) nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn v(cid:160) [∆ ˆA; ∆ˆb] = [A; b] − [ ˆA; ˆb] l(cid:160) hi»u ch¿nh b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn (Total least
16
square correction). Ta k‰ hi»u nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn
l(cid:160) ˆx.
Mºt trong nhœng øng d(cid:246)ng quan tr(cid:229)ng cıa b(cid:160)i to¡n TLS l(cid:160) (cid:247)(cid:238)c l(cid:247)æng
tham sŁ trong m(cid:230) h…nh bi‚n c(cid:226) sai sŁ. Gi£ sß r‹ng ta c(cid:226) m gi¡ tr(cid:224) (cid:31)o
cıa A, b li¶n h» v(cid:238)i n tham sŁ ch(cid:247)a bi‚t x b(cid:240)i ph(cid:247)(cid:236)ng tr…nh
A0x = b0, A = A0 + ∆A, b = b0 + ∆b,
v(cid:238)i ∆A, ∆b l(cid:160) c¡c sai sŁ (cid:31)o (cid:31)⁄c. Gi£ sß r‹ng A0 c(cid:226) h⁄ng (cid:31)ƒy (cid:31)ı v(cid:160) c¡c h(cid:160)ng cıa [∆A; ∆b] l(cid:160) (cid:31)ºc l“p tuy‚n t‰nh v(cid:160) c(cid:226) c(cid:242)ng ph¥n bŁ v(cid:238)i gi¡ tr(cid:224)
trung b…nh b‹ng 0. Khi (cid:31)(cid:226) nghi»m TLS ˆx cıa ph(cid:247)(cid:236)ng tr…nh Ax = b (cid:247)(cid:238)c
l(cid:247)æng gi¡ tr(cid:224) tham sŁ ch‰nh x¡c x0 (cid:31)(cid:247)æc cho b(cid:240)i A†b0, tøc l(cid:160) ˆx hºi t(cid:246) t(cid:238)i x0 khi m ti‚n ra v(cid:230) c(cid:242)ng.
1.3.2. Nghi»m c(cid:236) b£n
Sau (cid:31)¥y ta s‡ sß d(cid:246)ng k(cid:255) thu¥t ph¥n t‰ch gi¡ tr(cid:224) k… d(cid:224) (SVD) (cid:31)” gi£i
b(cid:160)i to¡n b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)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(cid:160) ph¥n t‰ch gi¡ tr(cid:224) k… d(cid:224) cıa [A; b]. N‚u σn+1 (cid:54)= 0 th… ma tr¥n [A; b] h⁄ng n + 1 v(cid:160) S l(cid:160) kh(cid:230)ng gian sinh b(cid:240)i c¡c dÆng cıa [A; b] tr(cid:242)ng v(cid:238)i Rn+1. Sß d(cid:246)ng (cid:30)(cid:224)nh l(cid:254) 1.3, x§p x¿ b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn [ ˆA; ˆb] tŁt nh§t h⁄ng n cıa [A; b] (cid:31)(cid:247)æc cho b(cid:240)i
(1.27) [ ˆA; ˆb] = U ˆΣV T , v(cid:238)i ˆΣ = diag(σ1, · · · , σn, 0).
Hi»u ch¿nh b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn nh(cid:228) nh§t (cid:31)(cid:247)æc cho b(cid:240)i
rank([ ˆA;ˆb])=n
σn+1 = min (cid:107)[A; b] − [ ˆA; ˆb](cid:107)F
v(cid:160)
n+1.
(1.28) [A; b] − [ ˆA; ˆb] = [∆ ˆA; ∆ˆb] = σn+1un+1vT
Ch(cid:243) (cid:254) r‹ng ma tr“n hi»u ch¿nh TLS c(cid:226) h⁄ng b‹ng 1 v(cid:160) t“p c¡c gi¡ tr(cid:224)
x§p x¿
[ ˆA; ˆb][xT ; −1]T = 0 (1.29)
17
l(cid:160) t(cid:247)(cid:236)ng th‰ch v(cid:160) nghi»m cıa ch(cid:243)ng (cid:31)(cid:247)æc cho b(cid:240)i duy nh§t v†c t(cid:236) vn+1 (tøc l(cid:160) cºt cuŁi c(cid:242)ng cıa V ) thuºc N [ ˆA; ˆb]. Nghi»m TLS (cid:31)(cid:247)æc cho b(cid:240)i v†c t(cid:236) vn+1 sau khi t(cid:27) l» h(cid:226)a l⁄i cho th(cid:160)nh phƒn cuŁi c(cid:242)ng l(cid:160) −1 ho(cid:176)c
[xT ; −1]T = (1.30) vn+1. −1 vn+1,n+1
N‚u vn+1,n+1 (cid:54)= 0 th…
ˆb = ˆAˆx = ˆA[v1,n+1, . . . , vn,n+1]T ∈ R( ˆA) −1 vn+1,n+1
Nh(cid:247) v“y (1.25) (cid:31)(cid:247)æc th(cid:228)a m¢n, do (cid:31)(cid:226) ˆx l(cid:160) nghi»m TLS.
n > σn+1 th…
(cid:30)(cid:224)nh l(cid:254) 1.6 (Nghi»m cıa b(cid:160)i to¡n TLS Ax ≈ b) Gi£ sß (1.4) v(cid:160) (1.5) t(cid:247)(cid:236)ng øng l(cid:160) SVD cıa ma tr“n A v(cid:160) [A; b]. N‚u σ(cid:48)
(1.31) [ ˆA; ˆb] = U ˆΣV T v(cid:160) ˆΣ = diag(σ1, . . . , σn, 0),
v(cid:238)i ma tr“n hi»u ch¿nh TSL t(cid:247)(cid:236)ng øng
n+1,
(1.32) [∆ ˆA; ∆ˆb] = [A; b] − [ ˆA; ˆb] = σn+1un+1vT
gi£i b(cid:160)i to¡n (1.24) v(cid:160) (1.25) v(cid:160) t(cid:231)n t⁄i duy nh§t nghi»m
ˆx = (1.33) [v1,n+1, · · · , vn,n+1]T −1 vn+1,n+1
cıa b(cid:160)i to¡n ˆAx = ˆb.
Chøng minh. Theo (cid:31)(cid:224)nh l(cid:254) 1.4 cho c¡c gi¡ tr(cid:224) k… d(cid:224), ta c(cid:226)
1 ≥ · · · ≥ σn ≥ σ(cid:48)
n ≥ σn+1.
σ1 ≥ σ(cid:48)
n > σn+1 n¶n σn+1 kh(cid:230)ng tr(cid:242)ng v(cid:238)i b§t k… gi¡ tr(cid:224) k… d(cid:224) n(cid:160)o cıa [A; b].
Do σ(cid:48)
N‚u
n+1
n+1y.
(cid:34) (cid:35) (cid:34) (cid:35) y y [A; b]T [A; b] = σ2 v(cid:160) y (cid:54)= 0 ⇒ AT Ay = σ2 0 0
Do (cid:31)(cid:226) m¤u thu¤n v(cid:238)i (cid:31)i•u ki»n σ(cid:48)2 n l(cid:160) gi¡ tr(cid:224) ri¶ng nh(cid:228) nh§t cıa AT A. Nh(cid:247) v“y, N ([ ˆA; ˆb]) ph£i chøa v†c t(cid:236) c(cid:226) th(cid:160)nh phƒn thø n + 1 kh¡c 0. Do
18
v“y, b(cid:160)i to¡n TLS c(cid:226) nghi»m. V… dim N ([ ˆA; ˆb]) = 1 n¶n nghi»m n(cid:160)y l(cid:160) duy nh§t.
H(cid:236)n nœa, sß d(cid:246)ng (cid:30)(cid:224)nh l(cid:254) 1.3, x§p x¿ TLS [ ˆA; ˆb] h⁄ng n cıa [A; b]
(cid:31)(cid:247)æc cho b(cid:240)i
[ ˆA; ˆb] = U ˆΣV T v(cid:160) ˆΣ = diag(σ1, . . . , σn, 0).
Hi»u ch¿nh TLS nh(cid:228) nh§t l(cid:160)
rank([ ˆA;ˆb])=n
(cid:107)[A; b] − [ ˆA; ˆb](cid:107) σn+1 = min
v(cid:160)
n+1.
[A; b] − [ ˆA; ˆb] = [∆ ˆA; ∆ˆb] = σn+1un+1vT
K‚t hæp v(cid:238)i dim N ([ ˆA; ˆb]) = 1, ta c(cid:226)
[ ˆA; ˆb][x(cid:48)T ; −1]T = 0.
Tł (cid:31)(cid:226) ta c(cid:226) th” k‚t lu“n
ˆb = ˆAˆx = ˆA[v1,n+1, · · · , vn,n+1]T ∈ R( ˆA). −1 vn+1,n+1
Nh(cid:247) v“y
ˆx = [v1,n+1, · · · , vn,n+1]T . −1 vn+1,n+1
Ta c(cid:226) (cid:31)i•u ph£i chøng minh.
T‰nh ch§t cıa nghi»m TLS ˆx v(cid:160) hi»u ch¿nh TLS nh(cid:228) nh§t σn+1 (cid:31)(cid:247)æc
tr…nh b(cid:160)y trong (cid:31)(cid:224)nh l(cid:254) sau (cid:31)¥y
(cid:30)(cid:224)nh l(cid:254) 1.7 (Bi”u di„n d⁄ng (cid:31)(cid:226)ng cıa nghi»m TLS) Gi£ sß (1.4) v(cid:160) (1.5) t(cid:247)(cid:236)ng øng l(cid:160) SVD cıa ma tr“n A v(cid:160) [A; b]. N‚u σ(cid:48) n > σn+1 th…
n+1I)−1AT b
ˆx = (AT A − σ2 (1.34)
n (cid:88)
n+1
i=1
v(cid:160) (cid:104) (cid:105) 1 + (1.35) σ2 n+1 (cid:107)Ax − b(cid:107)2 2. = min x∈Rn σ(cid:48)2 (u(cid:48)T i b)2 i − σ2
19
Chøng minh.
n > σn+1 n¶n ˆx l(cid:160) t(cid:231)n t⁄i v(cid:160) duy nh§t. V… c¡c v†c t(cid:236) k… d(cid:224) l(cid:160) c¡c v†c t(cid:236) ri¶ng cıa [A; b]T [A; b] n¶n ˆx th(cid:228)a m¢n ph(cid:247)(cid:236)ng tr…nh d(cid:160)nh cho v†c
Do σ(cid:48)
t(cid:236) ri¶ng sau
n+1
(cid:34) (cid:35) (cid:34) (cid:35) (cid:34) (cid:35) (cid:34) (cid:35) ˆx ˆx ˆx [A; b]T [A; b] = = σ2 . (1.36) −1 −1 AT A AT b bT A bT b −1
Do (cid:31)(cid:226) ta c(cid:226)
n+1ˆx
AT Aˆx − AT b = σ2
hay
n+1I)−1AT b.
ˆx = (AT A − σ2
M(cid:176)t kh¡c, tł c(cid:230)ng thøc (1.37) ta nh“n (cid:31)(cid:247)æc
n+1
(cid:35) (cid:35) (cid:34) (cid:34) (cid:35) (cid:34) z z = σ2 , v(cid:238)i g = Σ(cid:48)T U (cid:48)T b, z = V (cid:48)T ˆx. (1.37) −1 Σ(cid:48)T Σ(cid:48) gT −1 g (cid:107)b(cid:107)2 2
Tł ph(cid:247)(cid:236)ng tr…nh n(cid:160)y, ta c(cid:226)
n+1I)z = g v(cid:160) σ2
n+1 + gT z = (cid:107)b(cid:107)2 2.
(Σ(cid:48)T Σ(cid:48) − σ2 (1.38)
Th‚ z tł ph(cid:247)(cid:236)ng tr…nh tr(cid:247)(cid:238)c trong (1.38) v(cid:160)o ph(cid:247)(cid:236)ng tr…nh sau trong
(1.38) ta c(cid:226)
n+1 + gT (Σ(cid:48)T Σ(cid:48) − σ2 σ2
n+1I)−1g = (cid:107)b(cid:107)2 2.
(1.39)
m (cid:88)
n (cid:88)
Do (cid:31)(cid:226) ta c(cid:226) th” vi‚t l⁄i ph(cid:247)(cid:236)ng tr…nh (1.39) d(cid:247)(cid:238)i d⁄ng
i b)2
n+1
i=1
i=1
= (u(cid:48)T (1.40) σ2 n+1 + σ(cid:48)2 (u(cid:48)T i b)2 i − σ2
hay
m (cid:88)
n (cid:88)
i b)2.
n+1
i=n+1
i=1
(cid:105) = (u(cid:48)T (cid:104) 1 + (1.41) σ2 n+1 σ(cid:48)2 (u(cid:48)T i b)2 i − σ2
m (cid:88)
M(cid:176)t kh¡c, v…
2 = min
2 =
i b)2
ω
i=n+1
(cid:107)b − Ax(cid:107)2 (cid:107)u(cid:48)T b − Σω(cid:107)2 (u(cid:48)T (1.42) min x
20
n (cid:88)
n+1
i=1
1.4. Thu“t to¡n b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn
n¶n (cid:105) (cid:104) 1 + (1.43) (cid:107)Ax − b(cid:107)2 2. σ2 n+1 = min x∈Rn σ(cid:48)2 (u(cid:48)T i b)2 i − σ2
Thu“t to¡n t…m nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn (cid:31)(cid:247)æc m(cid:230) t£
nh(cid:247) sau:
(cid:30)ƒu v(cid:160)o: Cho ma tr“n A ∈ Rm×n v(cid:160) B ∈ Rm×d.
1. T‰nh SVD
[A; B] = U ΣV T
trong (cid:31)(cid:226) (cid:33) (cid:32)
. V :=
V11 V12 V21 V22 2. N‚u V22 kh(cid:230)ng k… d(cid:224) th… nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u ˆx = −V12V −1 22 . Ng(cid:247)æc l⁄i b(cid:160)i to¡n kh(cid:230)ng c(cid:226) nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn
v(cid:160) dłng thu“t to¡n.
(cid:30)ƒu ra: Nghi»m b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn ˆx cıa ph(cid:247)(cid:236)ng tr…nh
Ax = b.
V‰ d(cid:246) 1.2 V(cid:238)i n = 1 v(cid:160)
(cid:32) (cid:33) 1 0 . [A; b] = 0 2
Trong tr(cid:247)(cid:237)ng hæp n(cid:160)y A; b] (cid:31)¢ (cid:240) d⁄ng ch†o v(cid:160) c(cid:226) duy nh§t mºt gi¡ tr(cid:224) k… d(cid:224) nh(cid:228) nh§t σ2 = 1, v2 = [10]T v(cid:160) v2,2 = 0. C(cid:252)c ti”u duy nh§t [∆ ˆA; ∆ˆb] (cid:31)(cid:247)a t(cid:238)i (cid:32) (cid:33) 0 0 [ ˆA; ˆb] = [A − ∆ ˆA; b − ∆ˆb] = . 0 2
Do (cid:31)(cid:226) t“p x§p x¿ Ax ≈ b l(cid:160) kh(cid:230)ng t(cid:247)(cid:236)ng th‰ch n¶n kh(cid:230)ng t(cid:231)n t⁄i nghi»m
TLS cıa (1.24) v(cid:160) (1.25).
21
(cid:30)(cid:224)nh l(cid:254) d(cid:247)(cid:238)i (cid:31)¥y s‡ ch¿ ra r‹ng hi»u ch¿nh TLS (1.24) lu(cid:230)n nh(cid:228) h(cid:236)n hi»u
ch¿nh LS (1.22).
(cid:30)(cid:224)nh l(cid:254) 1.8 Cho Ax = b(cid:48) v(cid:160) ˆAx = ˆb t(cid:247)(cid:236)ng øng l(cid:160) x§p x¿ LS v(cid:160) TLS cıa t“p Ax ≈ b th… khi (cid:31)(cid:226)
(cid:107)b − b(cid:48)(cid:107)2 ≥ (cid:107)[A; b] − [ ˆA; ˆb](cid:107)F .
V‰ d(cid:246) 1.3 X†t ph(cid:247)(cid:236)ng tr…nh Ax = b c(cid:226) d⁄ng
N − 1 −1 · · · −1 1
−1 −1 N − 1 · · · −1
. . . . . . ≈ = , (1.44) x1 x2 . . . −1 −1 −1 · · · N − 1
N,N −2
N − 1 −1 −1 · · · −1 xN −3 xN −2 −1 −1 −1 · · · −1
nghi»m LS x(cid:48) v(cid:160) nghi»m TLS ˆx (cid:31)(cid:247)æc t‰nh mºt c¡ch gi£i t‰ch v(cid:160) cho b(cid:240)i
x(cid:48) = −0.5[1, 1, . . . , 1]T , ˆx = −[1, 1, . . . , 1]T .
C¡c hi»u ch¿nh t(cid:247)(cid:236)ng øng
∆b(cid:48) = b − b(cid:48) = 0.5[0, 0, . . . , 0, N, −N ]T
[∆ ˆA; ∆ˆb] = [A; b] − [ ˆA; ˆb] = [−1, . . . , −1, N − 1]T [1, . . . , 1]. 1 N − 1
Tł (cid:31)(cid:226) ta c(cid:226)
= N 2 (cid:107)∆b(cid:48)(cid:107)2 2 (cid:107)[∆ ˆA; ∆ˆb](cid:107)2 F
s‡ l(cid:238)n khi N l(cid:238)n.
22
Ch(cid:247)(cid:236)ng 2
Mºt sŁ øng d(cid:246)ng cıa ph(cid:247)(cid:236)ng ph¡p
b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn
2.1. H(cid:231)i quy (cid:31)(cid:236)n tuy‚n t‰nh
Trong kh(cid:230)ng gian R2 cho m (cid:31)i”m sŁ li»u
(2.1) {(xi, yi) ∈ R2 | i = 1, · · · , m}
th(cid:228)a m¢n mŁi quan h» tuy‚n t‰nh y(x) = a + bx. T…m tham sŁ a, b (cid:31)”
m (cid:88)
cho ta c(cid:252)c ti”u "tŁt nh§t" cıa tŒng b…nh ph(cid:247)(cid:236)ng c¡c phƒn d(cid:247)
i=1
f (a, b) := (2.2) (yi − a − bxi)2.
Ta c(cid:226) th” hi”u (cid:31)i•u n(cid:160)y theo ngh(cid:190)a t…m (cid:31)(cid:247)(cid:237)ng thflng l := {(x, y) ∈ R2|y = a + bx} "gƒn" c¡c (cid:31)i”mm dœ li»u nh§t. Ta c(cid:226) th” minh h(cid:229)a kho£ng c¡ch giœa c¡c (cid:31)i”m dœ li»u v(cid:160) (cid:31)(cid:247)(cid:237)ng thflng l nh(cid:247) trong H…nh v‡
2.1 d(cid:247)(cid:238)i (cid:31)¥y.
i=1 myi)T , ta vi‚t
i=1 mxi, 1 m
(cid:80) (cid:80) Sß d(cid:246)ng tr(cid:229)ng t¥m ¯z = (¯x, ¯y)T = ( 1 m
m (cid:88)
m (cid:88)
f (a, b) d(cid:247)(cid:238)i d⁄ng
i=1
i=1 m (cid:88)
f (a, b) := (yi − a − bxi)2 = (yi − ¯y + b(xi − ¯x))2 + m(¯y − a − b¯x)2
i=1
≥ (yi − ¯y + b(xi − ¯x))2, ∀a, b.
23
H…nh 2.1: (cid:30)(cid:247)(cid:237)ng LS: Kho£ng c¡ch theo tr(cid:246)c y.
(cid:30)flng thøc x£y ra khi ¯y = a + b¯x, khi (cid:31)(cid:226) tr(cid:229)ng t¥m n‹m tr¶n (cid:31)(cid:247)(cid:237)ng
thflng, tøc l(cid:160) ¯z ∈ l. Khi (cid:31)(cid:226) c(cid:252)c ti”u cıa (2.2) l(cid:160)
i=1(¯x − xi)(¯y − yi) (cid:80)m i=1(¯x − xi)2
(cid:80)m b = v(cid:160) a = ¯y − b¯x.
Nh(cid:247) trong c(cid:230)ng thøc (2.2) v(cid:160) H…nh 2.1, ta x†t b(cid:160)i to¡n t…m v(cid:224) tr‰ cıa
(cid:31)(cid:247)(cid:237)ng thflng gƒn nh§t cho t“p c¡c (cid:31)i”m. Ta s‡ sß d(cid:246)ng kho£ng c¡ch
Euclide, (cid:31)(cid:247)(cid:237)ng thflng sß d(cid:246)ng ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u c(cid:226)
th” (cid:31)(cid:247)æc minh h(cid:229)a nh(cid:247) H…nh 2.2
Ta x†t b(cid:160)i to¡n b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn t…m (cid:31)(cid:247)(cid:237)ng thflng l
m (cid:88)
c(cid:252)c ti”u h(cid:226)a tŒng b…nh ph(cid:247)(cid:236)ng cıa kho£ng c¡ch th“t
i=1
f (l) = dist((xi, yi), l)2.
Thay v… t…m (cid:31)(cid:247)(cid:237)ng thflng y = ax + b, ta sß d(cid:246)ng d⁄ng (cid:31)Łi xøng sau
1 + r2
2 = 1,
l = {(x, y) ∈ R2|a + r1x + r2y = 0} = w + r⊥ v(cid:238)i (cid:107)r(cid:107)2 = r2
24
H…nh 2.2: (cid:30)(cid:247)(cid:237)ng TLS: Kho£ng c¡ch theo c£ tr(cid:246)c x v(cid:160) tr(cid:246)c y.
trong (cid:31)(cid:226) w l(cid:160) mºt (cid:31)i”m b§t k(cid:253) tr¶n (cid:31)(cid:247)(cid:237)ng thflng l, tøc l(cid:160) a + r1w1 + r2w2 = 0. B‹ng c¡ch tham sŁ ho¡ n(cid:160)y cıa l, c(cid:226) th” x£y ra tr(cid:247)(cid:237)ng hæp r2 = 0, khi (cid:31)(cid:226) (cid:31)(cid:247)(cid:237)ng thflng kh(cid:230)ng th” c(cid:226) d⁄ng y = αx + β. Trong bi”u di„n l = w + r⊥ v(cid:238)i r l(cid:160) v†c t(cid:236) (cid:31)(cid:236)n v(cid:224), kho£ng c¡ch tł (cid:31)i”m z t(cid:238)i (cid:31)(cid:247)(cid:237)ng thflng l (cid:31)(cid:247)æc cho b(cid:240)i dist(z, l) = |rT (z − w)|, trong (cid:31)(cid:226) l = w + r⊥ = {z ∈ R2|rT (z − w) = 0} v(cid:160) (cid:107)r(cid:107) = 1. Khi (cid:31)(cid:226), b(cid:160)i to¡n b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn l(cid:160) t…m r v(cid:160) w c(cid:252)c ti”u h(cid:226)a h(cid:160)m
m (cid:88)
2 = rT BT Br,
i=1 trong (cid:31)(cid:226) B ∈ Rm×2 l(cid:160) ma tr“n
(cid:16) (cid:17) I(r, w) = = (cid:107)Br(cid:107)2 (2.3) r1(xi − ¯x) + r2(yi − ¯y)
x1 − ¯x y1 − ¯y x2 − ¯x y2 − ¯y B = (x − ¯xe|y − ¯ye) = . . . . . . xm − ¯x ym − ¯y
2 v(cid:238)i (cid:107)r(cid:107) = 1 ch‰nh l(cid:160) b(cid:160)i to¡n ph¥n t‰ch gi¡
B(cid:160)i to¡n t…m c(cid:252)c ti”u (cid:107)Br(cid:107)2
25
tr(cid:224) k… d(cid:224) cıa B
(cid:32) (cid:33)
B = U ΣV T , v(cid:238)i Σ = v(cid:160) σ1 ≥ σ2. σ1 0 0 σ2
V†c t(cid:236) nghi»m r cıa (2.3) l(cid:160) v†c t(cid:236) k… d(cid:224) ph£i cıa B t(cid:247)(cid:236)ng øng v(cid:238)i gi¡
tr(cid:224) k… d(cid:224) nh(cid:228) h(cid:236)n cıa B.
V‰ d(cid:246) 2.1 SŁ li»u v• khŁi l(cid:247)æng v(cid:160) chi•u cao cıa ph(cid:246) nœ trong (cid:31)º tuŒi
tł 30-39, (cid:31)(cid:247)æc cho trong b£ng sau
1.52 1.51 1.50 1.61 1.60 1.57 1.60 1.55
1.63 1.68 1.83 1.60 1.62 1.60 1.80
Chi•u cao, xi KhŁi l(cid:247)æng, yi 52.21 53.12 54.48 55.84 57.20 58.57 59.93 61.29 Chi•u cao, xi KhŁi l(cid:247)æng, yi 63.11 64.47 66.28 68.10 69.92 72.19 74.46
H…nh 2.3: K‚t qu£ h(cid:231)i quy tuy‚n t‰nh khi sß d(cid:246)ng TLS v(cid:160) LS
Ch(cid:247)(cid:236)ng tr…nh MATLAB s‡ (cid:31)(cid:247)æc n¶u trong phƒn Ph(cid:246) l(cid:246)c.
H…nh 2.3 m(cid:230) t£ (cid:31)(cid:247)(cid:237)ng h(cid:231)i quy (cid:31)(cid:236)n khi sß d(cid:246)ng ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng
tŁi thi”u v(cid:160) b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn. Sai sŁ khi sß d(cid:246)ng ph(cid:247)(cid:236)ng
ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u to(cid:160)n phƒn l(cid:160) ErrTLS = 0.0226 v(cid:160) sai sŁ
khi sß d(cid:246)ng ph(cid:247)(cid:236)ng ph¡p b…nh ph(cid:247)(cid:236)ng tŁi thi”u l(cid:160) ErrLS = 133.1582
26
2.2. H(cid:231)i quy phi tuy‚n
Trong tr(cid:247)(cid:237)ng hæp m(cid:230) h…nh phi tuy‚n, kh(cid:226) (cid:31)” (cid:31)(cid:247)a ra mŁi quan h» to¡n
h(cid:229)c ch‰nh x¡c cho vi»c t‰nh to¡n c¡c tham sŁ cıa m(cid:230) h…nh. Trong v‰ d(cid:246) d(cid:247)(cid:238)i (cid:31)¥y ta s‡ minh h(cid:229)a h(cid:231)i quy phi tuy‚n d⁄ng y = ax2 + bx + c.
V‰ d(cid:246) 2.2 Cho c¡c (cid:31)i”m dœ li»u (1.2855, 11.4827); (1.7693, 10.1865);
(1.8751, 11.6311); (2.7917, 12.0355); (3.8174, 10.3946); (5.9197, 12.1562);
(7.3133, 12.6762); (8.2018, 10.2297); (9.5408, 11.5356); (10.3918, 10.8350);
(11.8336, 8.9380); (12.9259, 9.4711); (13.2589, 9.4175); (14.7536, 7.4543);
(15.4299, 5.9990); (16.9608, 5.9532); (17.3013, 6.6710); (18.7012, 3.4274);
(19.8249, 5.6086); (20.7231, 2.5100);
T…m m(cid:230) h…nh phi tuy‚n d⁄ng y = ax2 + bx + c cho dœ li»u tr¶n.
Ch(cid:247)(cid:236)ng tr…nh m(cid:230) ph(cid:228)ng (cid:31)ƒy (cid:31)ı (cid:31)(cid:247)æc n¶u (cid:240) Ph(cid:246) l(cid:246)c cuŁi lu“n v«n. K‚t
H…nh 2.4: K‚t qu£ h(cid:231)i quy phi tuy‚n khi sß d(cid:246)ng TLS v(cid:160) LS
qu£ (cid:31)(cid:247)æc m(cid:230) t£ trong H…nh 2.4 sau
27
M(cid:230) h…nh sß d(cid:246)ng ph(cid:247)(cid:236)ng ph¡p LS c(cid:226) sai sŁ l(cid:160) 16.90 v(cid:160) (cid:31)(cid:247)(cid:237)ng parabol
(cid:31)(cid:247)æc cho b(cid:240)i
y = −0.0335x2 + 0.2998y + 10.8836.
M(cid:230) h…nh sß d(cid:246)ng ph(cid:247)(cid:236)ng ph¡p TLS c(cid:226) sai sŁ l(cid:160) 15.01 v(cid:160) (cid:31)(cid:247)(cid:237)ng parabol
(cid:31)(cid:247)æc cho b(cid:240)i
y = −0.0422x2 + 0.5092y + 10.0000.
28
T(cid:160)i li»u tham kh£o
[1] de Groen, Pieter (1996), "An introduction to Total Least Squares,"
Nieuw Arch. Wisk., 14(2), pp. 237(cid:21)253.
[2] Markovsky, Ivan and Van Huffel, Sabine (2007), (cid:16)Overview of total
least-squares methods,(cid:17) Signal processing, 87(10), pp. 2283(cid:21)2302.
[3] Van Huffel, Sabine & Vanderwalle, Joos (1991), The Total Least
Squares Problem: Computational Aspects and Analysis, SIAM,
Philadelphia, PA.
29
Ph(cid:246) l(cid:246)c
V‰ d(cid:246) 2.1. SŁ li»u v• khŁi l(cid:247)æng v(cid:160) chi•u cao cıa ph(cid:246) nœ trong (cid:31)º
tuŒi tł 30-39, (cid:31)(cid:247)æc cho trong b£ng sau 1.52 1.51 1.50 1.55 1.61 1.60 1.60 1.57
1.68 1.83 1.63 1.80 1.60 1.60 1.62
Chi•u cao, xi KhŁi l(cid:247)æng, yi 52.21 53.12 54.48 55.84 57.20 58.57 59.93 61.29 Chi•u cao, xi KhŁi l(cid:247)æng, yi 63.11 64.47 66.28 68.10 69.92 72.19 74.46 Ch(cid:247)(cid:236)ng tr…nh MATLAB (cid:31)(cid:247)æc sß d(cid:246)ng nh(cid:247) sau
Ph(cid:247)(cid:236)ng ph¡p h(cid:231)i quy tuy‚n t‰nh trong kh(cid:230)ng gian 2 chi•u
function [Err, P] = fit_2D_data(XData, YData, vizualization)
% Orthogonal linear regression method in 2D for model: y = a + bx
% Input parameters:
% - XData: input data block (cid:21) x: axis
% - YData: input data block (cid:21) y: axis
% - vizualization: figure (’yes’,’no’)
% Return parameters:
% - Err: error - sum of orthogonal distances
% - P: vector of model parameters [b-slope, a-offset]
kx=length(XData);
ky=length(YData);
if kx = ky
disp(’Incompatible X and Y data.’);
close all;
end
30
n=size(YData,2);
sy=sum(YData)./ky;
sx=sum(XData)./kx;
sxy=sum(XData.*YData);
sy2=sum(YData.ˆ2);
sx2=sum(XData.ˆ2);
B=0.5.*(((sy2-ky.*sy.ˆ2)-(sx2-kx.*sx.ˆ2))./(ky.*sx.*sy-sxy));
b1=-B+(B.ˆ2+1).ˆ0.5;
b2=-B-(B.ˆ2+1).ˆ0.5;
a1=sy-b1.*sx;
a2=sy-b2.*sx;
R=corrcoef(XData,YData);
if R(1,2) > 0
P=[b1 a1];
Yhat = XData.*b1 + a1;
Xhat = ((YData-a1)./b1);
end
if R(1,2) < 0
P=[b2 a2];
Yhat = XData.*b2 + a2;
Xhat = ((YData-a2)./b2);
end
alpha = atan(abs((Yhat-YData)./(Xhat-XData)));
d=abs(Xhat-XData).*sin(alpha);
Err=sum(d.ˆ2);
switch lower(vizualization)
case ’yes’
plot(XData,YData,’blue*’);
plot(XData,Yhat,’black’); hold off hold on;
case ’no’
31
disp(’No vizualization.’)
end
% ==========================================
function [F, Srez, Scel]=statindexes(XData, YData, a, b)
% [F, Srez, Scel]=statindexes(xdata, ydata, a, b)
% Computation of statistical indicators for linear model
% Input parameters:
% - xdata: input data block (cid:21) x: axis
% - ydata: input data block (cid:21) y: axis
% - a: parameter of linear model y = bx + a
% - b: parameter of linear model /
% Return parameters:
% - F: value for F-test
% - Srez: residual dispersion
% - Scel: total dispersion
kx=length(XData);
ky=length(YData);
if kx = ky
disp(’Incompatible X and Y data.’);
close all;
end
n=size(YData,2);
Srez = sum((YData-(a+b*XData)/(sqrt(1+bˆ2))).ˆ2)/(n-2);
Scel=sum((YData-mean(YData)).ˆ2+(XData-mean(XData)).ˆ2)/(n-
1);
F=Scel/Srez;
% ==========================================
clear all; close all;
xdata=[1.50 1.51 1.52 1.55 1.57 1.60 1.60 1.61 1.6 1.62 1.63 1.60 1.68
32
1.80 1.83];
ydata=[52.21 53.12 54.48 52.84 57.20 58.57 59.93 61.29 63.11 64.47
66.28 68.10 69.92 72.19 74.46];
[ErrTLS, P1] = fit_2D_data(xdata, ydata, ’no’)
YhatTLS=polyval(P1,xdata);
[F_TLS, Srez_TLS, Scel_TLS] = statindexes(xdata, ydata, P1(2),
P1(1))
P2=polyfit(xdata, ydata, 1)
YhatLS=polyval(P2,xdata);
ErrLS=sum((YhatLS-ydata).ˆ2)
[F_LS, Srez_LS, Scel_LS] = statindexes(xdata, ydata, P2(2), P2(1))
plot(xdata, ydata, ’*’);
hold on
plot(xdata,YhatTLS,’k’);
hold on
plot(xdata,YhatLS,’b(cid:21)’,’linewidth’,1.5,’markersize’,2);
xlabel(’x’);
ylabel(’y’);
legend(’Data’,’Model (TLS)’, ’Model (LS)’).
33
V‰ d(cid:246) 2.2. Cho c¡c (cid:31)i”m dœ li»u
(1.2855, 11.4827); (1.7693, 10.1865); (1.8751, 11.6311); (2.7917, 12.0355);
(3.8174, 10.3946); (5.9197, 12.1562); (7.3133, 12.6762); (8.2018, 10.2297);
(9.5408, 11.5356); (10.3918, 10.8350); (11.8336, 8.9380); (12.9259, 9.4711);
(13.2589, 9.4175); (14.7536, 7.4543); (15.4299, 5.9990); (16.9608, 5.9532);
(17.3013, 6.6710); (18.7012, 3.4274); (19.8249, 5.6086); (20.7231, 2.5100); T…m m(cid:230) h…nh phi tuy‚n d⁄ng y = ax2 + bx + c cho dœ li»u tr¶n.
(cid:30)” minh h(cid:229)a t‰nh hi»u qu£ cıa ph(cid:247)(cid:236)ng ph¡p TLS v(cid:160) LS, ta sß d(cid:246)ng
c¡c h(cid:160)m MATLAB nh(cid:247) sau
%==================================
% Demo on Nonlinear regression models via TLS and classical LS method
function [Err, min_param]=numerFminS(fun, p, LBa, UBa, xdata, ydata)
if (exist(’fminsearchbnd’, ’file’) == 2)
P = requireFEXpackage(8277);
% fminsearchbnd is part of 8277 at MathWorks.com end
warning off all
options1 = odeset(’RelTol’,1e-6,’AbsTol’,1e-6);
options = optimset(’MaxIter’,1e+4,’MaxFunEvals’,1e+4,’TolX’,1e-6,’TolFun’,1e-
6);
Mpoints(:,1)=xdata;
Mpoints(:,2)=ydata;
sum=0;
a0=zeros(1,p);
[a,fval,exitflag,output] = fminsearchbnd(@calculation,a0,LBa,UBa,options);
% calculating with optimized parameters: [yy]=fun(xdata, a);
x=xdata; y=yy;
%some output information about the minimization:
algoritm=output.algorithm;
funcCount=output.funcCount;
iter=output.iterations;
34
output.message;
min_param=a;
%================================
%function for evaluating the model with optimized parameters function
[sum] = calculation (a)
sum=0;
[yy]=fun(xdata, a);
x=xdata; y=yy;
points(:,1)=x;
points(:,2)=y;
for m=1:size(Mpoints,1)
[min_dist, IP]=dist_dsearch(points,Mpoints(m,:),’off’);
sum=sum+(min_dist).ˆ2;
end
Err=sum;
end
end
%=============================
function [I] = corrindex(XData, YData, YDataM, par_number)
% Function for calculation of the correlation index % Inputs: XData: x
data % YData: y data % YDataM: model data % par_number: number
of model parameters % Output: I: correlation index
kx=length(XData);
ky=length(YData);
kym=length(YDataM);
if kx = ky
disp(’Incompatible X and Y data.’);
close all;
end
35
n=kym;
sey=(sum((YData-YDataM).ˆ2))/(n-par_number);
sy=var(YData);
I=(1-(sey./sy))ˆ0.5;
%==============================
clear all; close all;
xdata=[1.2855 1.7693 1.8751 2.7917 3.8174 5.9197 7.3133 8.2018 9.5408
10.3918 11.8336 12.9259 13.2589 14.7536 15.4299 16.9608 17.3013 18.7012
19.8249 20.7231];
ydata=[11.4827 10.1865 11.6311 12.0355 10.3946 12.1562 12.6762 10.2297
11.5356 10.8350 8.9380 9.4711 9.4175 7.4543 5.9990 5.9532 6.6710 3.4274
5.6086 2.5100];
par_number = 3;
[ErrTLS,P1]=numerFminS(@model,par_number,[-0.05 0.5 9.5], [-0.04
0.7 10.0], xdata, ydata)
YhatTLS=polyval(P1(1:par_number),xdata);
Index_TLS = corrindex(xdata, ydata, YhatTLS, par_number)
P2=polyfit(xdata,ydata,2)
YhatLS=polyval(P2,xdata);
Index_LS = corrindex(xdata, ydata, YhatLS, par_number)
plot(xdata, ydata, ’*’);
hold on
plot(xdata,YhatTLS,’k’);
hold on
plot(xdata,YhatLS,’r’);
xlabel(’x’);
ylabel(’y’);
legend(’Data’,’Model (TLS)’, ’Model (LS)’);
