Dáno je $m$ bodů $(\_x_1,y_1),\ldots,(\_x_m,y_m)$, kde $\_x_i\in\R^n$ a $y_i\in\R$. Úkolem je nalézt takovou afinní funkci \begin{equation} f(\_x) = \_a^T\_x + b , \label{eq:f} \end{equation} parametrizovanou vektorem $\_a\in\R^n$ a skalárem $b\in\R$, která `nejlépe' aproximuje funkční závislost odpovídající daným bodům.

Je mnoho způsobů, jak formalizovat kvalitu aproximace. Určitě znáte formulaci ve smyslu nejmenších čtverců. V této úloze si jako míru kvality aproximace zvolíme maximální absolutní odchylku \begin{equation} r = \max_{i=1}^m |f(\_x_i)-y_i| . \label{eq:r} \end{equation} Cílem je nalézt parametry $\_a,b$ afinní funkce, pro které je číslo $r$ nejmenší.

Pro $n=1$ má úloha názorný geometrický význam (viz obrázek): hledáme pás s minimální šířkou (měřeno svisle), do něhož se vejdou všechny body.

Úkoly:

1. Úlohu (pro obecná $m,n$) převeďte na lineární program.
2. Implementujte funkci [a,b,r]=minimaxfit(x,y), kde $\_x\in\R^{n\x m}$ a $\_y\in\R^{1\x m}$ obsahují zadané dvojice $(\_x_1,y_1),\dots,(\_x_m,y_m)$, $\_a\in\R^{n\x1}$ a $b\in\R$ jsou hledané parametry funkce \eqref{eq:f}, a $r\in\R$ je minimální hodnota kritéria \eqref{eq:r}. Funkce nemá nic vypisovat ani vykreslovat.
3. Implementujte funkci plotline(x,y,a,b,r), která pro případ $n=1$ vykreslí obrázek s body a nalezeným pásem, podle vzorového obrázku výše. Tedy $\_x,\_y\in\R^{1\x m}$. Při implementaci použijte funkce plot a hold on/off, na konci zavolejte příkaz axis tight equal. Pro účely ladění si můžete sami vytvářet množiny bodů příkazem ginput.
4. Pro případ $n=1$ vidíme v obrázku výše, že horní modrá přímka (horní okraj pásu) prochází jedním bodem a dolní modrá přímka (dolní okraj pásu) prochází dvěma body. Zamyslete se nad tímto jevem a co nejlépe ho vysvětlete. Proč tomu tak je? Musí tomu pro $n=1$ tak být vždy? Za jakých podmínek tomu může být jinak? Jak je to pro obecné $n$? (Výstup tohoto úkolu se nijak neodevzdává, ale přesto ho splňte.)