Minimalizace součtu čtverců
- úvod
Optimalizuje teoretický model tak, aby co nejvíce
odpovídal naměřeným datům.
=> Minimalizuje odchylku modelu od naměřených
hodnot.
Využití:
Všude, kde máme co do činění s analýzou nějakého
přírodního nebo technického systému.
Minimalizace součtu čtverců
- úvod II
Naměřená data si můžeme představit jako dvojice:
(ti, yi), i = 1, ..., m
kde:
ti  Rk bod měření (například čas nebo místo měření
nebo obojí)
yi hodnota, naměřená v ti
Minimalizace součtu čtverců
- úvod III
Dále pak máme nějaký matematický model M:
Rk+n -> R, který je závislý na n volných parametrech
x1, x2, ..., xn a pro který požadujeme, aby:
M(ti, x)  yi
kde:
x = (x1, ..., xn)
i = 1, ..., m
(m je tedy počet naměřených bodů, se kterými
budeme pracovat)
Minimalizace součtu čtverců
- úvod IV
V úlohách tohoto typu tedy pro mprvkovou
množinu naměřených bodů
(ti, yi) hledáme parametry x1,..., xn
modelu M tak, aby daný model co
možná nejlépe popisoval tuto
množinu.
=> Minimalizujeme odchylku modelu
od naměřených dat.
Minimalizace součtu čtverců
- příklad
Ohmův zákon
Data: ((Ui), Ii) kde Ui je napětí na svorkách
rezistoru a Ii je proud, který prochází
rezistorem
Model: Obecně: M(ti, x) pro data (ti, yi)
Konkrétně: ( )
R
U
)R(),U(M i
i =
Parametry modelu: x = (R), kde R je odpor
rezistoru.
Minimalizace součtu čtverců
- příklad II
Radioaktivní rozpad
Data: ((ti), Ni) kde ti je čas od počátku
měření a Ni je počet atomů v čase ti
Model: Obecně: M(ti, x) pro data (ti, yi)
Konkrétně:
Parametry modelu: x = (N0, T), kde N0 je počet
atomů v čase 0 a T je poločas rozpadu.
( ) 2ln.T
t
00i
i
e.N)T,N(),t(M
−
=
Minimalizace součtu čtverců
- příklad III
Potenciální energie molekuly
Data: ((s1,..., sn), Epot) kde s1, ..., sn jsou souřadnice
jednotlivých atomů molekuly a Epot je potenciální
energie molekuly
Model: Obecně: M(ti, x) pro data (ti, yi)
Konkrétně:
Parametry modelu: je jich velmi mnoho – ideální
vazebné vzdálenosti, vazebné úhly a torzní úhly,
konstanty úměrnosti, atd ...
( ) elvdwtoranbnn1 EEEEE(...)),s,...,s(M ++++=
Minimalizace součtu čtverců
- obecně
Chceme minimalizovat odchylku modelu od
naměřených dat =>
Chceme tedy, aby hodnoty rozdílů
ri(x) = M(ti, x) - yi
byly v absolutní hodnotě co nejmenší.
To se dá interpretovat jako minimalizace
normy vektoru:
r(x) = (r1(x), ..., rm(x))T
Minimalizace součtu čtverců
- obecně II
Nejčastěji se používá euklidovská (L2) norma, pro
kterou dostáváme minimalizovanou funkci ve
tvaru:
Namísto L2 normy je také možno použít normu L1 (součet
absolutních hodnot ri) nebo L (maximum z absolutních
hodnot ri). Tyto normy mají svoje opodstatnění: například
L1 norma lépe eliminuje body měření, které „uletěly“, tj.
jsou výraznì mimo průběh zadaný ostatními body, často v
dùsledku chyby při měření. V přednáškách budeme dále
pracovat pouze s Euklidovskou normou.
=
==
m
1i
2
i
T
)(r)()()(f xxrxrx
Minimalizace součtu čtverců
- obecně III
Na funkce typu:
je možno přímo aplikovat minimalizační metody,
probrané v předchozích kapitolách. Při výpočtech
ale můžeme ušetřit mnoho času i paměti tím, že
využijeme speciální vlastnosti tohoto problému :-).
=
==
m
1i
2
i
T
)(r)()()(f xxrxrx
Minimalizace součtu čtverců
- obecně IV
Gradient funkce f se dá vyjádřit jako:
kde J(x)  Rnm je Jakobiho matice funkce f(x)
(i-tý řádek matice J(x) je gradient ri v bodě x).
Hessián funkce f se pak dá zapsat jako:
)(.)(2)(r).(r2)( T
m
1i
ii xrxJxxxg == =
G x x x x x( ) ( ). ( ) ( ). ( )=   + 
= =
 2 2
1
2
1
r r r ri i
T
i
m
i i
i
m
Minimalizace součtu čtverců
- obecně V
Pokud je model M v dobré shodě s daty, pak v
minimu x* má funkce f velmi malou (kladnou)
hodnotu. Pak tedy ri(x) jsou malá čísla a v okolí
x* se proto dá zanedbat druhá suma ve vztahu:
Hessián funkce f pak může být aproximován jako:
G x x x x x( ) ( ). ( ) ( ). ( )=   + 
= =
 2 2
1
2
1
r r r ri i
T
i
m
i i
i
m
)()(2)(r).(r2)( T
m
1i
T
ii xJxJxxxG = =
Minimalizace součtu čtverců
- Gauss-Newtonovy metody
Metody, které kombinují tuto aproximaci s
Newtonovskými metodami se nazývají GaussNewtonovy
metody.
Klasický Newtonovský vztah pro výpočet směru
přesunu (sk) z bodu xk do bodu xk+1:
je tedy přeformulován na vztah:
)k()k()k(
. gsG −=
J J s J r( ) ( ) ( ) ( ) ( )
. . .k T k k k T k
= −
Minimalizace součtu čtverců
- Levenberg-Marquardtovy metody
Použití dané aproximace v metodě s omezeným
krokem dává Levenberg-Marquardtovu metodu
pro součet čtverců. Původně byla LevenbergMarquardtova
metoda vyvinuta právě pro tuto
aplikaci. Rovnice:
kterou využívá Levenberg-Marquardtova metoda se
v tomto speciálním případě přepisuje do tvaru:
( )G I g( ) ( ) ( )k k k
+ = − 
( )J J I J r( ) ( ) ( ) ( ) ( )
. .k T k k k T k
+ = − 
Lineární úloha nejmenších čtverců
- úvod
V tomto případě je model lineární vzhledem k aproximovaným
parametrům:
M(ti, x) = f1(ti).x1 + ... + fn(ti).xn
Pro odchylku modelu od reálného výsledku měření platí:
=> ri(x) = M(ti, x) - yi = f1(ti).x1 + ... + fn(ti).xn - yi
Funkce, kterou budeme v rámci metody minimalizovat, má tedy
tvar:
 f r t x t x yi
i
m
i n i n i
i
m
( ) ( ) ( ). ... ( ).x x= = + + −
= =
 2
1
1 1
2
1
f f
Lineární úloha nejmenších čtverců
- úvod II
Budeme tedy minimalizovat funkci:
V minimu musí pro všechny parametry x1, ..., xn modelu platit:
Po odderivování tedy platí:


f
xj
= 0
 =
−f++f=
m
1i
2
inin1i1 yx).t(...x).t()(f x
 


f f f
f
x
t t x t x y
j
j i i n i n i
i
m
= + + − =
=
2 01 1
1
. ( ). ( ). ... ( ).
Lineární úloha nejmenších čtverců
- úvod III
Rovnici:
budeme dále upravovat:
Soustavu rovnice v tomto tvaru můžeme zapsat pomocí matice:
A.x = b
 =
=−f++ff
m
1i
inin1i1ij 0yx).t(...x).t().t(.2
  =ff++f=f = =
)t(.x).t(...x).t()t(.y ij
m
1i
m
1i
nin1i1iji
 ==
ff++ff=
m
1i
ijinn
m
1i
iji11 )t().t(.x...)t().t(.x
Lineární úloha nejmenších čtverců
- úvod IV
Soustavu rovnic:
lze zapsat ve tvaru A.x = b následovně:
kde k, j {1, …, n}
Můžeme tedy obejít náročný proces minimalizace a získat
minimum přímo řešením této soustavy.
 ===
ff++ff=f
m
1i
ijinn
m
1i
iji11
m
1i
iji )t().t(.x...)t().t(.x)t(.y
=
ff=
m
1i
ijikkj )t().t(a =
f=
m
1i
ijik )t(.yb
Lineární úloha nejmenších čtverců
- příklad
Chceme řešit tento problém:
Mějme objekt, pohybující se v čase t rychlostí v.
Naměřili jsme, že objekt se v čase
t1 = 1s pohyboval rychlostí v1 = 1 m/s
t2 = 2s pohyboval rychlostí v2 = 6 m/s
t3 = 3s pohyboval rychlostí v3 = 2 m/s
Pohyb tohoto objektu považujeme za rovnoměrně zrychlený a
můžeme ho tedy modelovat pomocí vztahu:
v = a.t + v0, kde:
a zrychlení objektu
v0 počáteční rychlost objektu
Úkolem je určit parametry a a v0.
Lineární úloha nejmenších čtverců
- příklad II
Obecný vztah pro model:
M(ti, x) = f1(ti).x1 + ... + fn(ti).xn
můžeme tedy v našem případě přepsat do tvaru:
M(ti, (a, v0)) = f1(ti).a + f2(ti).v0 = a.t + v0
=> n = 2
Pro f1 a f2 tedy platí:
f1(ti) = ti
f2(ti) = 1
Lineární úloha nejmenších čtverců
- příklad III
Měřením jsme získali 3 body: (1, 1); (2, 6) a (3, 2) (=> m = 3)
Problém lze obecně zapsat pomocí soustavy n rovnic A.x = b
kde k, j {1, …, n}=
ff=
m
1i
ijikkj )t().t(a =
f=
m
1i
ijik )t(.yb
V našem případě tedy bude platit:
a11 = t1. t1 + t2. t2 + t3. t3 = 14
a12 = t1 + t2 + t3 = 6
a21 = t1 + t2 + t3 = 6
a22 = 1 + 1 + 1 = 3
b1 = y1. t1 + y2. t2 + y3. t3 = 19
b2 = y1 + y2 + y3 = 9
x1 = a
x2 = v0
Lineární úloha nejmenších čtverců
- příklad IV
Budeme tedy řešit soustavu rovnic:
Řešení: a = 0.5 m/s2
v0 = 2 m/s
Součet čtverců odchylek:








9
19
36
614
( ) ( )( ) =−+=−=  ==
3
1i
2
i0i
m
1i
2
ii yvt.ay),t(MS x
5,135,1)3(5,1
)223.5,0()622.5,0()121.5,0(
222
222
=+−+=
=−++−++−+=
Lineární úloha nejmenších čtverců
- příklad V
Grafické znázornění výsledku:
y = 0,5x + 2
0
1
2
3
4
5
6
7
0 0,5 1 1,5 2 2,5 3 3,5
t [s]
v[m/s]
Lineární úloha nejmenších čtverců
- úlohy se dvěma parametry
S tímto typem úloh se setkáváme v praxi velmi často, jedná se o
úlohy typu:
Máte zadáno m bodů (ti, yi), proložte těmito body přímku.
= nalezněte koeficienty k a q v rovnici y = k.t + q.
V tomto případě lze obecnou soustavu rovnic A.x = b
kde k, j {1, …, n}
Přepsat do tvaru:
=
ff=
m
1i
ijikkj )t().t(a =
f=
m
1i
ijik )t(.yb












=





















=
=
=
==
m
1i
i
m
1i
ii
m
1i
i
m
1i
i
m
1i
2
i
y
t.y
q
k
.
mt
tt
Lineární úloha nejmenších čtverců
- úlohy se dvěma parametry II
Řešením této soustavy:
Pak získáme pro k a q vztahy:












=





















=
=
=
==
m
1i
i
m
1i
ii
m
1i
i
m
1i
i
m
1i
2
i
y
t.y
q
k
.
mt
tt
m
t.t
t
m
y.t
t.y
k m
1i
i
m
1i
im
1i
2
i
m
1i
i
m
1i
im
1i
ii




==
=
==
=
−
−
=
m
t.ky
q
m
1i
i
m
1i
i  ==
−
=
Lineární úloha nejmenších čtverců
- úlohy se dvěma parametry III
Příklad:
Zadání stejné jako u předchozího příkladu o „objektu, pohybujícím
se v čase t rychlostí v“.
Máme tedy body: (1, 1); (2, 6) a (3, 2) a chceme jimi proložit
přímku: v = a.t + v0
Konkrétní výpočet:
19t.v i
3
1i
i ==
6t
3
1i
i ==
9v
3
1i
i ==
14t
3
1i
2
i ==
5,0
3
6.6
14
3
9.6
19
k =
−
−
=
3
6.5,09
q
−
=
Kvadratická úloha nejmenších čtverců
- úloha se třemi parametry
Naměřenými body tedy chceme proložit rovnici:
y = a.t2 + b.t + c
Analogicky jako v lineárním případě lze i v kvadratickém
případě tuto speciální úlohu zapsat pomocí soustavy
rovnic A.x = b, a to následovně:
t t t
t t t
t t cm
a
b
c
t y
t y
y
i i i
i i i
i i
i
i
i
m
i
m
i
m
i
m
i
m
i
m
i
m
i
m
i
i
m
i
i
m
i
i
m
4
1
3
1
2
1
3
1
2
1 1
2
1 1
2
1
1
1
= = =
= = =
= =
=
=
=
  
  
 





























=
















.
Kvadratická úloha nejmenších čtverců
- úloha se třemi parametry II
Metodou nejmenších čtverců najděte polynom
2.stupně, který je nejblíže bodům:
[1,1], [2,3], [4,6].
Řešíme tedy soustavu rovnic:
t t t
t t t
t t m
a
b
c
t y
t y
y
i i i
i i i
i i
i
i
i
m
i
m
i
m
i
m
i
m
i
m
i
m
i
m
i
i
m
i
i
m
i
i
m
4
1
3
1
2
1
3
1
2
1 1
2
1 1
2
1
1
1
= = =
= = =
= =
=
=
=
  
  
 





























=
















.
Kvadratická úloha nejmenších čtverců
- úloha se třemi parametry III
=> soustava: 273a + 73b + 21c = 109
73a + 21b + 7c = 31
21a + 7b + 3c = 10
Výsledek je:
a = -1/6,
b = 5/2,
c = -4/3.
y t t=
−
+ −
1
6
5
2
4
3
2
Cvičení
- příklad 1
Metodou nejmenších čtverců najděte přímku, která je
nejblíže bodům: (1,1); (2,6) a (3,2)
Použijte „přímý přístup“ - vytvořit funkci, odderivovat,
derivaci položit rovnu nule, dořešit :-).
Řešení: Hledáme přímku ve tvaru y = kx + q
Minimalizovaná funkce:
f k q t k q yi i
i
n
( , ) ( . )= + −
=
1
2
f k q k q k q k q( , ) ( ) ( ) ( )= + − + + − + + −1 2 6 3 22 2 2
f k q k kq k q q( , ) = + − + − +14 12 38 3 18 412 2
Cvičení
- příklad 1 II
Derivace:
Řešíme tedy a
Minimum je v bodě k = 0.5 a q = 2


f
k
k q= + −28 12 38


f
q
k q= + −12 6 18
0 28 12 38= + −k q 0 12 6 18= + −k q
Cvičení
- příklad 2
Metodou nejmenších čtverců najděte přímku, která je
nejblíže bodům: (1, 2); (2, 2.3) a (3, 3)
Vytvořte soustavu rovnic A.x = b a vyřešte ji, obecně:
kde k, j {1, …, n}=
ff=
m
1i
ijikkj )t().t(a =
f=
m
1i
ijik )t(.yb
Cvičení
- příklad 2
Metodou nejmenších čtverců najděte přímku, která je
nejblíže bodům: (1, 2); (2, 2.3) a (3, 3)
Vytvořte soustavu rovnic A.x = b a vyřešte ji, obecně:
kde k, j {1, …, n}=
ff=
m
1i
ijikkj )t().t(a =
f=
m
1i
ijik )t(.yb
Soustava:
a11 = 14 a12 = 6 a21 = 6 a22 = 3
b1 = 15,6 b2 = 7,3
Řešení: k = 0,5 q = 1,43
Cvičení
- příklad 3
Metodou nejmenších čtverců najděte přímku, která je nejblíže
bodům: (-2,0); (0,1) a (2,3)
Využijte vztahy:
m
t.t
t
m
y.t
t.y
k m
1i
i
m
1i
im
1i
2
i
m
1i
i
m
1i
im
1i
ii




==
=
==
=
−
−
=
m
t.ky
q
m
1i
i
m
1i
i  ==
−
=
y ti i
i=
 =
1
3
6 ti
i=
 =
1
3
0 yi
i=
 =
1
3
4 ti
i
2
1
3
8
=
 =
k =
−
−
=
6
0 4
3
8
0 0
3
0 75
.
.
, q =
−
=
4 0
3
1 33
3
4 .
,
Cvičení
- příklad 4
Metodou nejmenších čtverců najděte polynom
2.stupně, který je nejblíže bodům:
[1,2], [2,0], [3,3], [4,4].
Opět hledáme polynom ve tvaru y ax bx c= + +2