\[ \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*}} \]
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:
[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.
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
.
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