\[ \def\_#1{\mathbf{#1}} \def\bb#1{\mathbb{#1}} \]
Mějme $m$ bodů v rovině, $\_a_1,\ldots,\_a_m\in\bb R^2$. Chceme najít kružnici se středem $\_c\in\bb R^2$ a poloměrem $r\ge 0$ takovou, že součet čtverců vzdáleností bodů od kružnice je nejmenší.
Označme jako $\_x=(\_c,r)\in\bb R^3$ vektor parametrů kružnice. Nechť ${\rm dist}(\_x, \_a)$ je orientovaná vzdálenost bodu $\_a$ od kružnice s parametry $\_x$. Tedy $\lvert{\rm dist}(\_x, \_a)\rvert$ je Eukleidovská vzdálenost bodu $\_a$ od kružnice, přičemž pro $\_a$ vně kružnice je ${\rm dist}(\_x, \_a)>0$ a pro $\_a$ uvnitř kružnice je ${\rm dist}(\_x, \_a)<0$. Chceme minimalizovat funkci \[ f(\_x) = \sum_{i=1}^m {\rm dist}(\_x, \_a_i)^2 \]
d = dist(x, A)
, kde x
je vektor $3\times 1$, A
je matice $2\times m$ obsahující body $\_a_1, \_a_2, ..., \_a_m$, d
je vektor $N\times 1$.
[x_new] = make_GN_iter(x, A)
, která provede jednu iteraci čisté (tedy s jednotkovou délkou kroku) Gauss-Newtonovy metody.
[x_new, success] = make_LM_iter(x, A, mu)
, která provede jednu iteraci Levenberg-Marquardtovy metody (bližší popis funkcí je v jejich šablonách.)
Poznámky:
main.m
a funkci fit_circle.m
.
ginput
.) Takto si připravte několik zajímavých konfigurací bodů, mezi kterými pak můžete snadno přepínat a zkoušet na nich svoje implementace algoritmů.
print
):
body a kružnice $\_x^{(1)}_0$ | body a stav dokonvergovaný z $\_x^{(1)}_0$ | graf f_history (kritérium v závislosti na indexu iterace) pro $\_x^{(1)}_0$ |
body a kružnice $\_x^{(2)}_0$ | body a stav dokonvergovaný z $\_x^{(2)}_0$ | graf f_history (kritérium v závislosti na indexu iterace) pro $\_x^{(2)}_0$ |
report.pdf