\[
\def\_#1{\mathbf{#1}}
\def\x{\times}
\def\R{\mathbb{R}}
\def\mat#1{\begin{bmatrix}#1\end{bmatrix}}
\def\matr#1{\begin{bmatrix*}[r]#1\end{bmatrix*}}
\]


===== Minimaxní lineární regrese =====

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.

{{body2.svg?400}}

**Úkoly:**
  - Úlohu (pro obecná $m,n$) převeďte na lineární program.
  - 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. Poznámka: $\_y$ je i v pythonu dvojrozměrný numpy array.
  - 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''.
  - 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.)

=== Příklady I/O === 

Uvádíme příklady pro případ $n=3$, kde je složitější vizuálně ověřit správnost. Primárně ale úlohu testujte na případě $n=1$, kde vše vykreslíte funkcí ''plotline''.

Pro python:
<code python>
import numpy as np
    
x = np.array([[1, 2, 3, 3, 2], [4, 1, 2, 5, 6], [7,8,9, -5,7]])
y = np.array([[7,4,1,2,5]])
a, b, r = minimaxfit(x,y)

# a = [-2.776, 0.194, -0.030]
# b = 9.403
# r = 0.194
</code>

Pro matlab:
<code matlab>   
x = [1 2 3 3 2 ; 4 1 2 5 6; 7 8 9 -5 7]
y = [7 4 1 2 5]
[a b r] = minimaxfit(x,y)

% a = [-2.776 0.194 -0.030]
% b = 9.403
% r = 0.194
</code>