\[
\def\_#1{\mathbf{#1}}
\def\bb#1{\mathbb{#1}}
\]

===== (DÚ4) Optimální proložení bodů kružnicí =====

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
\]


==== Implementační úkoly ====

  - Implementujte funkci ''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$.
  - Implementujte funkci ''[x_new] = make_GN_iter(x, A)'', která provede jednu iteraci čisté (tedy s jednotkovou délkou kroku) Gauss-Newtonovy metody. 
  - Implementujte funkci ''[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:
  * Pro práci na úloze máte k dispozici skript ''main.m'' a funkci ''fit_circle.m''.
  * Udělejte si v matlabu jednoduchý skript, který vám dovolí naklikat body $\_a_i$ a uložit si je do MAT souboru (pro naklikání se bude hodit funkce ''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ů.     
==== Teoretické úkoly (do zprávy) ====

  - Mějme několik bodů $\_a_1, ..., \_a_m$ v obecné konfiguraci. Je funkce $f$ všude diferencovatelná? Má jedno nebo více lokálních minim? Odpovědi zdůvodněte. Navrhujeme (ale nemusíte to dělat), abyste při vyšetřování funkce $f(\_x) = f(\_c, r)$ uvažovali funkci $h(\mathbf{c}) = f(\mathbf{c}, r)$ pro nějaká konstantní $r$, tedy řez funkce $f$ podle $r$. Grafy takových řezů lze snadno vizualizovat.
  - Diskutujte, jaký algoritmus je vhodný na minimalizaci funkce $f(\_x)$ a proč. Čím více myšlenek a argumentů uvedete, tím lépe. Je možné, aby Gaussův-Newtonův algoritmus na naší úloze divergoval?
  - Může se zdát, že algoritmy na nelineární nejmenší čtverce bez omezení nejde použít, protože máme omezení $r\ge0$. Vadí to? Co se stane, budeme-li toto omezení ignorovat? Můžou algoritmy konvergovat k řešení se záporným $r$? Své odpovědi odůvodněte.
  - Najděte nějakou množinu $m\ge 3$ bodů $\{\_a_1, \_a_2, ..., \_a_m\}$ a takovou dvojici počátečních parametrů kružnice $\_x^{(1)}_0$ a $\_x^{(2)}_0$, aby algoritmus inicializovaný těmito parametry skončil v různých lokálních minimech. Do zprávy udělejte následující tabulku s obrázky (všechny elementy tabulky jsou obrázky exportované z matlabu, např. pomocí funkce ''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$| 


==== Co potřebujete udělat: ====
  * Z {{ https://gitlab.fel.cvut.cz/B0B33OPT/public/tree/master/cviceni/04_circle | gitlabu}}  si stáhněte šablony pro funkce k implementaci a pomocné funkce a skripty. 
  * Implementujte funkce popsané výše. 
  * Napište PDF zprávu a pojmenujte ji ''report.pdf'' 
  * Zabalte všechny implementované funkce (plus jakékoli vaše pomocné funkce, které výše čtyři zmíněné používají) a PDF zprávu do ZIP souboru a nahrajte je do [[https://cw.felk.cvut.cz/brute/ | upload systému]]. Udělejte ZIP soubor tak, aby se vaše soubory rozbalily rovnou do aktuálního adresáře, ne do nějakého podadresáře (jinak to nebude fungovat.)