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

1. Najděte a 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$.
2. Implementujte funkci [x_new] = make_GN_iter(x, A), která provede jednu iteraci čisté (tedy s jednotkovou délkou kroku) Gauss-Newtonovy metody.
3. 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.
• Doporučujeme si napsat jednoduchý skript, který vám dovolí naklikat body $\_a_i$ a uložit si je do *.mat souboru (bude se hodit funkce ginput). Takto si připravte několik vhodných množin bodů, na kterých můžete zkoušet svůj kód.

1. Pro $m\ge3$ a body $\_a_1, ..., \_a_m$ v obecné poloze, zkuste nalézt co nejobecnější podmínky na body $\_x$, ve kterých je funkce $f$ diferencovatelná. Odpověď důvodněte.
2. 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$? Odpovědi odůvodněte.
3. Může mít pro nějakou množinu $\_a_1,\ldots,\_a_m$ funkce $f$ více lokálních minim s různou funkční hodnotou? Pokud odpovíte záporně, odůvodněte. Pokud odpovíte kladně, najděte příklad (množinu bodů $\_a_1,\ldots,\_a_m$ a dvě lokální minima $\_x^1,\_x^2$ funkce $f$ s různou funkční hodnotou) a odůvodněte, proč $\_x^1,\_x^2$ jsou lokální minima (můžete použít argument, že když např. Gauss-Newtonova metoda zkonverguje do stacoinárního bodu, tak tento bod je téměř jistě lokální minimum a není tedy třeba ověřovat definitnost Hessiánu). Do zprávy pak
   • exportujte (pomocí matlabské funkce print) obrázek, ve kterém budou body $\_a_1,\ldots,\_a_m$ a dvě kružnice s parametry $\_x^1,\_x^2$,
   • napište funkční hodnoty obou kružnic $f(\_x^1),f(\_x^2)$,
   • napište gradienty $\nabla f(\_x^1), \nabla f(\_x^2)$ (pokud by funkce v bodech $\_x^1,\_x^2$ nebyla diferencovatelná, diskutujte a zkuste najít jiný argument, proč jsou body lokální minima)

• Z 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 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.)