Dáno je $m$ bodů $(x_1,y_1), \ldots,(x_m,y_m)$, kde $x_i,y_i\in\bb R$. Úkolem je nalézt takovou lineární funkci \[ f_{a,b}(x) = a x + b , \] parametrizovanou čísly $a,b\in\bb R$, která nejlépe aproximuje funkční závislost odpovídající daným bodům.

Je mnoho kritérií, kterými můžeme definovat dobrou aproximaci. Konkrétní volba kritéria závisí na aplikaci. My si jako kritérium dobré aproximace zvolíme maximální absolutní odchylku definovanou jako \[ \epsilon(a,b) = \max_{i=1,\ldots,m} |f_{a,b}(x_i)-y_i| . \] Naším cílem bude nalézt parametry $a,b$ lineární funkce, pro které je $\epsilon(a,b)$ nejmenší.

Úloha má názornou geometrickou interpretaci, znázorněnou na obrázku: hledáme pás s minimální šířkou (měřeno svisle), jenž obepíná všechny body. Střed pásu je přímka $ax + b = 0$ a jeho šířka je $2 \epsilon(a,b)$.

1. Úlohu převeďte na lineární program. Výstup: lineární program (matlabská notace není přípustná).
2. Stáhněte si soubor data1.mat. Soubor obsahuje vektor x [50 x 1] a vektor y [50 x 1] s body $x_i,y_i$. V našem případě tedy je $m=50$. Vykreslete si body do grafu. Výstup: nic.
3. Pro staženou množinu bodů vyřešte úlohu s použitím kódu na řešení LP. Nalezenou optimální přímku vykreslete do grafu s body. Jaká je maximální absolutní odchylka pro tuto přímku? Výstup: graf a číslo.
4. Přeformulujte úlohu pro případ, kdy $\_a,\_x_1,\ldots,\_x_m$ jsou vektory v $\bb R^n$. Vyjádřete tuto úlohu jako LP. Výstup: lineární program (matlabská notace není přípustná).