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. Poznámka: $\_y$ je i v pythonu dvojrozměrný numpy array.
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.)

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:

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

Pro 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