Soustavy rovnic bez řešení

Z lineární algebry víme (viz Frobeniova větu), že soustavu $m$ rovnic pro $n$ reálných neznámých můžeme chápat jako rovnici pro průnik $m$ nadrovin v $n$-dimenzionálním prostoru $\mathbb{R}^n$. Pokud je to na Vás moc divných slov a dimenzí, položte si $n = 3$ a místo nadrovin si představte rovinu: v takovém případě jedna rovnice ve tvaru $$ ax + by + cz = d $$ odpovídá (obecné) rovnici roviny (pokud tedy platí, že $a,b,c$ nejsou všechny nulové). Řešení soustavy $m$ rovnic pak odpovídá hledání průniku $m$ rovin. Je tedy jasné, že dává smysl tvrdit, že čím více máme (nejen lineárních) rovnic, tím spíše neexistuje řešení příslušné soustavy. Ukážeme si dva problémy z (jak se říká) reálného života, při jejichž řešení narazíme právě na takovou neřešitelnou soustavu rovnic.

Navigační systém GPS

Předpokládám, že každý čtenář zná alespoň uživatelsky navigační systém GPS. Pokud je navíc čtenář trochu šťoura, a ve svém telefonu se podívá podrobněji na informace o GPS, zjistí, že občas telefon "nevidí" dostatek družic, aby mohl určit polohu a že čím více družic vidí, tím přesněji je poloha určena. Jenomže, jak si níže naznačíme, určovat polohu na základě signálu z $m$ družic, znamená řešit soustavu $m$ rovnic. A jelikož je poloha určena jako bod v třídimenzionálním prostoru $\R^3$, máme pouhé tři neznámé (ve skutečnosti určujeme i čtvrtou proměnnou čas, neboť se nepředpokládá, že máte v mobilu s družicemi synchronizované atomové hodiny). V souladu s výše napsaným tedy máme dvě pozorování: čím více družic, tím přesnější určení polohy a zároveň čím více rovnic, tím menší šance na existenci řešení. Takže co s tím?

Trochu matematických detailů k GPS

Když věci trochu zjednodušíme, tak GPS navigace je schopna zjistit z dostupných satelitů, jak je od každého z nich daleko a kde přesně se dané satelity nacházejí. Řekněme, že první satelit se nachází v bodě se souřadnicemi $(x_1, y_1, z_1)$ a je od našeho GPS zařízení ve vzdálenosti, kterou označíme $d_1$. Z této informace si odneseme to, že se nacházíme někde na kouli se středem v bodě $(x_1, y_1, z_1)$ a poloměrem $d_1$. Označíme-li naši neznámou polohu jako bod $(x,y,z)$, víme, že tento bod splňuje následující rovnici (vzpomeňte na střední školu): $$ (x - x_1)^2 + (y - y_1)^2 + (z - z_1)^2 = d_1^2. $$ No, tak víme, že jsme na kouli, ale to nám zřejmě k lokalizaci nestačí, a proto si přihodíme další satelit a další rovnici $$ (x - x_2)^2 + (y - y_2)^2 + (z - z_2)^2 = d_2^2. $$ Řešením soustavy těchto dvou rovnic je průnik dvou koulí, což je zpravidla kružnice, která nám ale stále nestačí. Tak přidáme další satelit a pronikneme tuto kružnici s další koulí. Výsledkem jsou (zpravidla) dva body, kdy se jeden nachází někde ve vesmíru, a lokalizace tak je úspěšná.

Tyto rovnice samozřejmě nejsou lineární, ale lze je takovým jednoduchým trikem zlinearizovat. Předpokládejme, že máme rovnice čtyři. Pak můžeme udělat to, že od druhé, třetí a čtvrté rovnice odečteme tu první. Co se stane? Zkusme odečíst první rovnici od druhé, tj. odečíst pravé a levé strany rovnic od sebe: $$ (x - x_2)^2 + (y - y_2)^2 + (z - z_2)^2 - ((x - x_1)^2 + (y - y_1)^2 + (z - z_1)^2) = d_2^2 - d_1^2. $$ Nyní můžeme použít starý známý fakt, že $(a - b)^2 = a^2 - 2ab + b^2$, a postupně se zbavit kvadrátů závorek a poodečítat je, např. $$ (x - x_2)^2 - (x - x_1)^2 = x^2 -2xx_2 + x_2^2 - (x^2 -2xx_1 + x_1^2) = (2x_1 - 2x_2)x + x_2^2 - x_1^2, $$ když toto uděláme, ze druhé, třetí a čtvrté nelineární rovnice zmizí druhé mocniny neznámých, tedy členy $x^2, y^2$ a $z^2$ a stanou se z nich rovnice lineární (pamatujte, že $x_i, y_i, z_i, d_i$ jsou jen nějaká známá čísla, nikoli proměnné).

Celkově můžeme říci, že když máme $m$ družic, dostaneme se k $m-1$ lineárním rovnicím o třech neznámých. Je-li ale $m \geq 5$, může se nám snadno stát, že rovnice nemá řešení. My ji ale vyřešit potřebujeme, jinak nebudeme vědět, kde jsme!!?

Jakou mají cenu znalosti lineární algebry

Vedle GPS se s neřešitelnými soustavami můžeme setkat při práci s daty, konkrétně při řešení problému, kterému se říká lineární regrese. Představme si, že chceme zjistit, jaká je závislost výše mzdy absolventa FITu po pěti letech od promoce (označme si tuto hodnotu jako $y$) na tom, kolik získal bodů v předmětu Lineární algebra (označme si tuto hodnotu jako $x$, hodnoty jsou od 50 do 100, s body pod 50 nelze FIT absolvovat).

Řekněme, že si myslíme, že ta závislost je zhruba kvadratická, tedy že platí něco takového: $$ y = ax^2 + bx + c + \text{nějaká náhodná odchylka}. $$ Tomuto se říká lineární regresní model a je to opravdu velmi často používaná a populární metoda, jak vykoukat z dat nějakou předpokládanou závislost.

Tento model je sice hezký, ale pokud neznáme parametry $a,b,c$, tak je nám celkem na nic. Cílem je, abychom byli schopni předpovědět budoucí mzdu pouze na základě zisku bodů v předmětu Lineární algebra, což fakticky znamená, že chceme dosadit číslo za $x$, např. $x = 60$ a chceme získat konkrétní předpověď veličiny $y$. Proto potřebujeme mít místo $a,b,c$ konkrétní čísla.

Jak tato čísla nejlépe určit, aby náš model odpovídal co nejlépe realitě? Obvyklý způsob je ten, že si nasbíráme nějaká data a pokusíme se model tzv. "naučit" na těchto datech. Co to znamená? Představme si, že jsme si u 10 absolventů zjistili jejich mzdu po pěti letech od promoce, a také jejich body: pro $i$tého absolventa si tato dvě čísla označme $y_i$ a $x_i$. Kdyby náš model byl naprosto přesný, měly by platit všechny následující rovnice mít řešení: $$ y_1 = ax_1^2 + bx_1 + c \\ y_2 = ax_2^2 + bx_2 + c \\ \vdots \\ y_{10} = ax_{10}^2 + bx_{10} + c. $$ Když si opět uvědomíme, že $x_i$ a $y_i$ jsou konkrétní čísla, zjistíme, že to je stará známá soustava (deseti) lineárních rovnic, pro tři neznámé $a,b,c$. A jelikož nečekáme, že náš model je naprosto přesný (třeba má na mzdu vliv i analýza!!), nedá se ani moc čekat, že tato soustava bude mít řešení. Navíc intuice i praxe říká, že čím více dat (a tedy rovnic), tím lépe máme naučený model. Jenže více dat a rovnic znamená menší a menší šanci na to, že existuje řešení! Hrůza a panika!

Matematické uchopení problému lineární regrese

Zkusme si soustavu deseti rovnic uchopit trochu formálněji a "lineárně algebraičtěji". Vstupní data o studentech si můžeme napsat do vektoru $$ Y = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_{10} \end{pmatrix} \in \mathbb{R}^{10}. $$ a matice $$ X = \begin{pmatrix} x_1^2 & x_1 & 1\\ x_2^2 & x_2 & 1 \\ \vdots & \vdots & \vdots \\ x_{10}^2 & x_{10} & 1 \end{pmatrix} \in \mathbb{R}^{10,3}. $$ Označíme-li si vektor proměnných (z tradičních důvodů) jako $\beta^T = (a\ b\ c)$, můžeme pomocí maticového násobení přepsat soustavu výše jako $$ X\beta = Y. $$

Na tuto soustavu se můžeme koukat také jinak: hledáme reálná čísla $a,b,c$ tak, aby platilo $$ a \begin{pmatrix} x_1^2 \\ x_2^2 \\ \vdots \\ x_{10}^2 \end{pmatrix} + b \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_{10} \end{pmatrix} + c \begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix} = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_{10} \end{pmatrix}. $$ Tedy hledáme koeficienty lineární kombinace tří vektorů z $\mathbb{R}^{10}$ tak, aby výsledek byl zadaný vektor $Y$, který je také z $\mathbb{R}^{10}$. Takové koeficienty existují pouze za předpokladu, že $Y$ je v lineárním obalu těchto tří vektorů (tj. tří sloupců matice $X$). To by nutně znamenalo, že v desetidimenzionálním prostoru se $Y$ zrovna trefil do jednoho zadaného (nejvýše) třídimenzionálního podprostoru! To se nedá čekat, představte si jen, jaká je šance, že v prostoru $\R^3$ víceméně náhodně vybraný bod padne na nějakou zadanou dvoudimenzionální rovinu. V našem případě má bod $Y$ k dispozici dokonce $7$ dimenzí, které mu dovolují uhnout.

Co s tím? Myšlenka je takováto: když náš bod $Y$ neleží v našem podprostoru generovaném sloupci matice, zkusme v tomto podprostoru najít nejbližší bod od $Y$. Tj. místo přesného řešení hledejme koeficienty $\beta^T = (a\ b \ c)$ tak, aby vzdálenost vektorů $X\beta \in \mathbb{R}^{10}$ a $Y \in \mathbb{R}^{10}$ byla co nejmenší!

Metoda nejmenších čtverců

Jak se měří vzdálenost vektorů? Nejobvyklejší mírou je tzv. Euklidovská vzdálenost, která při troše přemýšlení vypadne z Pythagorovy věty. Pro dva vektory $U^T = (u_1\ u_2\ \ldots\ u_n)$ a $V^T = (v_1\ v_2\ \ldots\ v_n)$ je definována jako Euklidovská norma jejich rozdílu $$ ||U - V|| = \sqrt{(u_1 - v_1)^2 + (u_2 - v_2)^2 + \cdots + (u_{10} - v_{10})^2}. $$ Všimněte si, že výraz pod odmocninou lze s využitím maticového násobení zapsat jako $$ (U - V)^T(U - V) = (u_1 - v_1)^2 + (u_2 - v_2)^2 + \cdots + (u_{10} - v_{10})^2. $$ Kdyby $n = 3$ a vektory $U$ a $V$ byly body v třídimenzionálním prostoru, tak jejich Euklidovská vzdálenost $||U - V||$ bude odpovídat jejich fyzické vzdálenosti, kterou byste naměřili pravítkem či podobným zařízením.

Když se vrátíme k našemu problému: snažíme se najít parametry $\beta^T = (a\ b\ c)$ tak, abychom minimalizovali výraz $$ ||X\beta - Y|| = \sqrt{(ax_1^2 + bx_1 + c - y_1)^2 + \cdots + (ax_{10}^2 + bx_{10} + c - y_{10})^2}. $$ Jelikož je odmocnina $\sqrt{x}$ ostře rostoucí funkcí pro $x \geq 0$, stačí nám minimalizovat výraz pod odmocninou: skutečně, jelikož jde o ostře rostoucí funkci, platí, že čím mennší číslo dosadíme, tím menší bude mít jeho odmocnina hodnotu. Takže minimalizovat odmocninu nějakého výrazu je vlastně stejné, jako hledat nejmenší hodnotu, jakou daný výraz pod odmocninou může nabývat. Celkově tedy hledáme minimum výrazu $$ ||X\beta - Y||^2 = (X\beta - Y)^T(X\beta - Y) = (ax_1^2 + bx_1 + c - y_1)^2 + \cdots + (ax_{10}^2 + bx_{10} + c - y_{10})^2. $$ Mno, takže minimalizujeme součet druhých mocnit (a.k.a. čtverců*) výrazů tvaru $$ ax_i^2 + bx_i + c - y_i $$ což je vlastně odchylka předpovědi mzdy dané naším modelem (s parametry parametry $a,b,c$) pro $i$tého studenta, tj. číslo $ax_i^2 + bx_i + c$, a skutečné mzdy $y_i$. Této odchylce se říká $i$té *reziduum a náš problém je tedy minimalizace sumy čtverců reziduí. Odtud metoda nejmenších čtverců.

Řešení!

Jak ale takové minumum výrazu $(X\beta - Y)^T(X\beta - Y)$ najít? Jedná se o výraz, která obsahuje tři neznámé. Když za tyto neznámé dosadíme, dostaneme jedno konkrétní reálné číslo. Funguje to tedy stejně jako funkce, které jste studovali v předmětu Základy matematické analýzy. Ty ale obsahovaly proměnnou jedinou. Výraz $(X\beta - Y)^T(X\beta - Y)$ lze tedy považovat za funkci, ovšem funkci tří proměnných!

Jak se hledá minimum funkce, která má více proměnných? Z prvácké analýzy to umíte pro jednu proměnnou: funkci $f(x)$ zderivujeme, najdeme řešení rovnice $f'(x) = 0$, atd. Pro více proměnných to funguje podobně a naučíte se to v předmětech BI-VMM: Vybrané matematické metody resp. *MI-MPI: Matematika pro informatiku*. Zde si postup jenom tak trochu prvácky naznačíme.

Předpokládejme pro chvilku, že $X$ a $Y$ jsou reálná čísla a $\beta$ je jednorozměrná reálná proměnná. Potom bychom mohli výraz $(X\beta - Y)^T(X\beta - Y)$ prostě zderivovat jako součin dvou výrazů $(X\beta - Y)$, neb transpozice čísla nic neudělá. Výsledná derivace je $$ -2X(X\beta - Y). $$ Když tento výraz položíme rovný nule, dostaneme jediné řešení (je-li $X$ nenulové) $$ \beta = (XX)^{-1}XY. $$

No a ve více rozměrech to funguje překvapivě podobně, hledané řešení je vektor $$ \beta = (X^TX)^{-1}X^TY. $$ Může se stát, že matice $X^TX$ inverzi nemá, ale to už je detail, kterým se zde nebudeme zabývat. Muselo by se totiž stát, že by sloupce matice $X$ byly lineárně závislé, což není moc pravděpodobné, má-li matice o hodně více řádků než sloupců.

Shrnutí

Máme-li matici $X \in \mathbb{R}^{n,p}$ a vektor $Y \in \mathbb{R}^{n}$, kde $n$ je větší než $p$, je velmi malá šance, že by soustava $$ X\beta = Y $$ měla nějaké řešení $\beta \in \mathbb{R}^{p}$.

Jelikož ale takový problém často řešíme v praxi, hledáme alespoň nějaké co nejlepší "neřešení". Jednou z možností je najít $\beta$ tak, aby vzdálenost vektorů $X\beta$ a $Y$ byla co nejmenší. Použijeme-li jako míru vzdálenosti klasickou Euklidovskou normu, potřebujeme vlastně najít minimum následující funkce $p$ proměnných (složek vektoru $\beta$) $$ (X\beta - Y)^T(X\beta - Y). $$ Takové minimum najít umíme za pomoci metod analogických metodám pro hledání extrému funkce jedné proměnné známých z prvácké analýzy. Výsledkem je vektor $$ \beta = (X^TX)^{-1}X^TY, $$ kterému se říká odhad metodou nejmenší čtverců.

---

Tento článek vznikl v rámci řešení projektu Institucionální podpora Českého vysokého učení technického v Praze (CZ.02.2.69/0.0/0.0/16_015/0002382).

---