Metóda najmenších štvorcov
Jakub Záthurecký
zathurecky@math.muni.cz
Dept. of Mathematics and Statistics, Faculty of Science, Masaryk University
December 3, 2024
Motivácia
Riešme systém lineárnych rovníc Ax = b.
Ak h(A) = h(A|b), potom má systém práve jedno riešenie
(Frobeniova veta).
V praktických situáciách je táto podmienka často porušená.
Typický príklad: systém je preurčený (overdetermined) - má
omnoho viac rovníc ako neznámych.
Ak riešenie neexistuje, hľadáme nejaký jeho „najlepší“
ekvivalent.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 2 / 26
Príklad
Nech je medzi veličinami y a x lineárny vzťah: y = ax + b, pre
nejaké (neznáme) a, b ∈ R.
Pre n hodnôt xi veličiny x máme nameraných n hodnôt yi veličiny
y, i = 1, . . . , n.
V ideálnom prípade by body (xi, yi) ležali na priamke y = ax + b.
Vzhľadom k tomu, že merania sú zaťažené (náhodnou) chybou,
body neležia na žiadnej priamke.
Snažíme sa nájsť priamku y = ax + b (koeficienty a, b) tak, aby
danými bodmi „prechádzala“ čo najlepšie.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 3 / 26
Príklad
i xi yi
1 0 5
2 1 3
3 3 3
4 5 2
5 6 1
y = ax + b
0a + b = 5,
1a + b = 3,
3a + b = 3,
5a + b = 2,
6a + b = 1.
Systém nemá riešenie (z prvej rovnice dostávame b = 5 a po
dosadení do ostatných rovníc dostávame rôzne hodnoty pre a).
Obrázok.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 4 / 26
Maticový zápis
0a + b = 5,
1a + b = 3,
3a + b = 3,
5a + b = 2,
6a + b = 1.
Ac = f ,
A =






0 1
1 1
3 1
5 1
6 1






, c =
a
b
, f =






5
3
3
2
1






c - vektor neznámych koeficientov a, b
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 5 / 26
Geometrická interpretácia systému lineárnych rovníc






0 1
1 1
3 1
5 1
6 1






·
a
b
=






5
3
3
2
1






⇔ a ·






0
1
3
5
6






+ b ·






1
1
1
1
1






=






5
3
3
2
1






systém Ac = f má riešenie práve vtedy, keď sa dá vektor f
napísať ako lineárna kombinácia stĺpcov s1(A) a s2(A) matice A.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 6 / 26
Geometrická interpretácia systému lineárnych rovníc
Definujeme priestor Im(A) generovaný stĺpcami matice A:
Im(A) = {Ac | c ∈ R2
}
= {a · s1(A) + b · s2(A) | a, b ∈ R}
Tento zápis je v skutočnosti parametrické vyjadrenie roviny (v
5-rozmernom priestore R5), ktorej smerové vektory sú stĺpce
matice A, teda s1(A) a s2(A), a v ktorej leží bod 0 = [0, 0, 0, 0, 0]
(ten dostaneme voľbou a = b = 0).
Systém Ac = f má riešenie práve vtedy, keď bod f leží v rovine
Im(A). Ak f /∈ Im(A), potom tento systém nemá riešenie.
Obrázok.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 7 / 26
Skalárny súčin
Pre vektory u = (u1, . . . , uk)T , v = (v1, . . . , vk)T ∈ Rk (vektory
chápeme ako stĺpcové vektory, teda ako matice, ktoré majú k
riadkov a 1 stĺpec, takže ak ich chceme napísať do riadku,
musíme použiť transponovanie) sme definovali skalárny súčin
u, v = u · v = u1v1 + · · · + ukvk =
k
i=1
uivi.
To sa dá vyjadriť tiež pomocou maticového násobenia:
uT
· v = (u1, . . . , uk) ·



v1
...
vk


 = u1v1 + · · · + ukvk =
k
i=1
uivi.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 8 / 26
Najlepšie (ne)riešenie
Pokúsime sa nájsť bod f ∗ v rovine Im(A), ktorý je nabližšie k
bodu f spomedzi všetkých bodov roviny Im(A). Inými slovami, je
to bod, v ktorom sa realizuje vzdialenosť bodu f od roviny Im(A).
Tento bod má tú vlastnosť, že vektor f − f ∗ je kolmý na rovinu
Im(A).
Zároveň, vzhľadom k tomu, že f ∗ ∈ Im(A), existuje vektor
koeficentov c∗ taký, že Ac∗ = f ∗. Inými slovami, systém Ac = f ∗
má riešenie a tým je vektor c∗.
Obrázok.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 9 / 26
Výpočet
Vektor f − f ∗ je kolmý na rovinu Im(A) práve vtedy, keď je kolmý
na jej obidva smerové vektory:
s1(A)T
· (f − f ∗
) = s1(A)T
· (f − Ac∗
) = 0,
s2(A)T
· (f − f ∗
) = s2(A)T
· (f − Ac∗
) = 0.
To môžeme v maticovom tvare vyjadriť nasledujúcim spôsobom:
AT
· (f − Ac∗
) = 0,
pričom nula na pravej strane označuje nulový vektor (0, 0)T .
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 10 / 26
Výpočet
(0, 1, 3, 5, 6) ·












5
3
3
2
1






−






0 1
1 1
3 1
5 1
6 1






·
a
b






= 0,
(1, 1, 1, 1, 1) ·












5
3
3
2
1






−






0 1
1 1
3 1
5 1
6 1






·
a
b






= 0.
0 1 3 5 6
1 1 1 1 1
·












5
3
3
2
1






−






0 1
1 1
3 1
5 1
6 1






·
a
b






=
0
0
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 11 / 26
Výpočet
Rovnicu AT · (f − Ac∗) = 0 upravíme:
AT
· (f − Ac∗
) = 0,
AT
f − AT
Ac∗
= 0,
AT
Ac∗
= AT
f .
AT
A =
0 1 3 5 6
1 1 1 1 1
·






0 1
1 1
3 1
5 1
6 1






=
71 15
15 5
.
Matica AT A je evidentne invertibilná, takže môžeme dopočítať c∗:
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 12 / 26
Výpočet
AT
Ac∗
= AT
f ,
c∗
= (AT
A)−1
AT
f .
c∗
=
71 15
15 5
−1
0 1 3 5 6
1 1 1 1 1






5
3
3
2
1






=




−
7
13
287
65




Hľadaná priamka má tvar y = −
7
13
x +
287
65
.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 13 / 26
Názov metódy (Interpretácia výsledku)
c∗ sme hľadali tak, že sme minimalizovali vzdialenosť f od
f ∗ = Ac∗. Inak povedané, hľadali sme c∗ tak, aby vektor f − Ac∗
mal minimálnu veľkosť.
f − Ac∗
=



y1 − ax1 − b
...
y5 − ax5 − b


 =






5 − 0a − b
3 − 1a − b
3 − 3a − b
2 − 5a − b
1 − 6a − b






|f − Ac∗
| =
5
i=1
(yi − axi − b)2
=
(5 − 0a − b)2
+ (3 − 1a − b)2
+ (3 − 3a − b)2
+ (2 − 5a − b)2
+ (1 − 6a − b)2
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 14 / 26
Názov metódy (Interpretácia výsledku)
Vzhľadom k tomu, že
√
• je rastúca funkcia, minimalizácia
|f − Ac∗| je ekvivalentá (dostaneme ten istý výsledok)
minimalizácii výrazu
5
i=1
(yi − axi − b)2
Obrázok.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 15 / 26
Všeobecná MNŠ
Nech je medzi veličinami y a x vzťah
y = ϕ(x) = c1ϕ1(x) + · · · + ckϕk(x) =
k
i=1
ciϕi(x),
kde c1, . . . , ck ∈ R a ϕ1, . . . , ϕk sú tzv. bázové funkcie, teda
funkčný vzťah y = ϕ(x) sa dá vyjadriť ako lineárna kombinácia
bázových funkcií.
V predošlom príklade bolo k = 2, c1 = a, c2 = b, ϕ1(x) = x a
ϕ2(x) ≡ 1.
Pre n rôznych hodnôt xi veličiny x máme predpísaných n hodnôt
yi veličiny y, i = 1, . . . , n.
Typicky je n omnoho väčšie ako k, teda daných bodov (xi, yi) je
omnoho viac ako parametrov ci.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 16 / 26
Všeobecná MNŠ
V ideálnom prípade by existovali koeficienty c1, . . . , ck tak, že pre
každé i ∈ {1, . . . , n} by platilo yi = ϕ(xi), teda každý bod (xi, yi)
by ležal na grafe funkcie y = ϕ(x).
Systém rovníc yi = ϕ(xi), i ∈ {1, . . . , n} má tvar
c1ϕ1(x1) + · · · + ckϕk(x1) = y1,
...
c1ϕ1(xn) + · · · + ckϕk(xn) = yn.
Je to systém n lineárnych rovníc pre k neznámych koeficientov
c1, . . . , ck. V praxi je beznádejné, aby mal riešenie. Preto hľadáme
tie „najlepšie“ koeficienty c1, . . . , ck v zmysle metódy najmenších
štvorcov.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 17 / 26
Všeobecná MNŠ
Maticový zápis systému:
Ac = f ,
A =



ϕ1(x1) · · · ϕk(x1)
...
...
...
ϕ1(xn) · · · ϕk(xn)


 c =



c1
...
ck


 f =



y1
...
yn



Ac = f ⇔ c1



ϕ1(x1)
...
ϕ1(xn)


 + · · · + ck



ϕk(x1)
...
ϕk(xn)


 =



y1
...
yn



J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 18 / 26
Geometrická interpretácia
Definujeme priestor Im(A) generovaný stĺpcami matice A:
Im(A) = {Ac | c ∈ Rk
}
= {c1 · s1(A) + · · · + ck · sk(A) | c1, . . . , ck ∈ R}
Im(A) je k-rozmerná nadrovina v n-rozmernom priestore Rn,
ktorej smerové vektory sú stĺpce matice A, teda s1(A), . . . , sk(A).
Hľadáme bod f ∗ v nadrovine Im(A), ktorý je nabližšie k bodu f
spomedzi všetkých bodov nadroviny Im(A). Inými slovami,
minimalizujeme veľkosť |f − f ∗| vektora f − f ∗.
Tento bod má tú vlastnosť, že vektor f − f ∗ je kolmý na
nadrovinu Im(A).
Zároveň, vzhľadom k tomu, že f ∗ ∈ Im(A), existuje vektor
koeficentov c∗, taký, že Ac∗ = f ∗.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 19 / 26
Výpočet
Vektor f − f ∗ je kolmý na nadrovinu Im(A) práve vtedy, keď je
kolmý na všetky jej smerové vektory:
s1(A)T
· (f − f ∗
) = s1(A)T
· (f − Ac∗
) = 0,
...
sk(A)T
· (f − f ∗
) = sk(A)T
· (f − Ac∗
) = 0.
To môžeme v maticovom tvare vyjadriť nasledujúcim spôsobom:
AT
· (f − Ac∗
) = 0,
pričom nula na pravej strane označuje nulový vektor (0, . . . , 0)T .
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 20 / 26
Výpočet
Rovnicu AT · (f − Ac∗) = 0 upravíme:
AT
· (f − Ac∗
) = 0,
AT
f − AT
Ac∗
= 0,
AT
Ac∗
= AT
f .
Matica AT A je invertibilná práve vtedy, keď má A plnú hodnosť.
To sa dá zabezpečiť rozumnou voľbou bázových funkcií. Stačí aby
boli tzv. lineárne nezávislé na uzloch xi. Takže hodnosť matice A
a tým pádom aj invertibilita matice AT A závisí len od vlastností
bázových funkcií, nie od dát (xi, fi).
c∗
= (AT
A)−1
AT
f
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 21 / 26
Riešenie
Koeficienty c∗ podľa ich konštrukcie minimalizujú hodnotu
|f − Ac| =
n
i=1

yi −
k
j=1
cjϕj(xi)


2
=
n
i=1
(yi − ϕ(xi))2.
Podľa vlastností funkcie
√
• je tento problém ekivalentý
minimalizácii výrazu
|f − Ac|2
=
n
i=1

yi −
k
j=1
cjϕj(xi)


2
=
n
i=1
(yi − ϕ(xi))2
.
Odtiaľ pochádza názov metódy - hľadáme koeficienty c tak, aby
sme minimalizovali súčet druhých mocnín (štvorcov) odchýliek
aproximovaných hodnôt od skutočných/predpísaných hodnôt.
Matica (AT A)−1AT sa nazýva Mooreova-Penroseova
pseudoinverzia matice A.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 22 / 26
Dôkaz
Ukážeme, že c∗ naozaj minimalizuje výraz |f − Ac|2
.
Nech c ∈ Rk je ľubovoľné. Označme rozdiel c − c∗ symbolom ∆c,
takže c = c∗ + ∆c. Ukážeme, že |f − Ac|
2
≥ |f − Ac∗|2
:
|f − Ac|
2
= (f − Ac)T
· (f − Ac)
= (f − A(c∗
+ ∆c))T
· (f − A(c∗
+ ∆c))
= (f − Ac∗
− A∆c)T
· (f − Ac∗
− A∆c))
= ((f − Ac∗
) − A∆c)T
· ((f − Ac∗
) − A∆c))
= ((f − Ac∗
)T
− (A∆c)T
) · ((f − Ac∗
) − A∆c))
= (f − Ac∗
)T
· (f − Ac∗
) − (f − Ac∗
)T
· A∆c
− (A∆c)T
· (f − Ac∗
) + (A∆c)T
· A∆c
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 23 / 26
Dôkaz
Pripomeňme, že c∗ má tú vlastnosť, že vektor f − Ac∗ je kolmý na
nadrovinu Im(A). Vzhľadom k tomu, že A∆c leží v nadrovine
Im(A) a výrazy (f − Ac∗)T · A∆c a (A∆c)T · (f − Ac∗) sú skalárne
súčiny vektora f − Ac∗ s vektorom A∆c (skalárny súčin je
symetrický), sú obidva rovné nule.
|f − Ac|
2
= (f − Ac∗
)T
· (f − Ac∗
) + (A∆c)T
· A∆c
= |f − Ac∗
|2
+ |A∆c|2
Opäť sme využili vzťah medzi veľkosťou vektora a skalárnym
súčinom: |u|2
= uT · u. Keďže |A∆c|2
≥ 0, môžeme z predošlej
nerovnosti usúdiť
|f − Ac|
2
≥ |f − Ac∗
|2
.
Dôkaz je tým hotový.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 24 / 26
Štatistika
Zo štatistického hľadiska sa snažíme minimalizovať odhad
rozptylu náhodnej veličiny Y − ϕ(X).
Rozptyl je číselná charakterisitka vyjadrujúca mieru variability
náhodnej veličiny - mieru s akou sa odkláňa od svojej strednej
hodnoty.
V našom prípade očakávame, že Y − ϕ(X) ≈ 0, teda že náhodná
veličina Y − ϕ(X) je blízka konštantnej náhodnej veličine 0,
ktorej rozptyl je prirodzene 0.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 25 / 26
Príklady
Príklady na kalibračnú krivku spektrometra a na materiálové
konštanty skla v študijných materiáloch.
J. Záthurecký ·Metóda najmenších štvorcov ·December 3, 2024 26 / 26