A·x = b: tři možné odpovědi a žádná čtvrtá
Soustava lineárních rovnic je nejčastější důvod, proč vůbec někdo sáhne po maticích. Zapsat se dá dvěma způsoby a oba jsou na něco jiného.
Řádkový pohled: průsečík
Každá rovnice je jedna přímka (v prostoru rovina) a řešení je bod, kde se protnou. Kreslí se to snadno a odpovídá to na otázku kde. Má to ale dvě vady: nad tři neznámé se to nakreslit nedá, a neřekne to, proč řešení někdy neexistuje.
Sloupcový pohled: jde ten cíl poskládat?
Z kapitoly 1: násobení maticí je vážený součet sloupců. Takže se soustava ptá:
- A·x = b — najdi x
Soustava rovnic, zapsaná maticově. Skoro každý kurz ji kreslí jako průsečík přímek. Tenhle obrázek ukazuje druhý pohled, který se kreslí míň a řekne mnohem víc.
- x₁·c₁ + x₂·c₂ = b
Z kapitoly 1: násobení maticí je vážený součet sloupců. Takže se neptáme „kde se protnou přímky“, ale: jde b poskládat ze sloupců A? A pokud ano, s jakými váhami.
- b = 1,10·c₁ + 0,46·c₂
Když sloupce míří různými směry, dosáhnou na celou rovinu a každý cíl se z nich dá poskládat — a právě jedním způsobem. Táhni jezdci a sleduj, jak se váhy mění, ale cesta vždycky dorazí přesně na hrot b.
- c₂ = k · c₁ → obal je jen přímka
Když si sloupce lehnou na jednu přímku, všechny jejich kombinace leží na té přímce. Determinant je nula (kapitola 3), hodnost klesla na jedna — a to je pořád tentýž jeden fakt.
- b mimo přímku → žádné řešení
Když cíl na té přímce neleží, žádná kombinace se k němu nedostane. Soustava je neřešitelná — a není to vada výpočtu, je to poctivá odpověď. (Nejbližší dosažitelný bod ale existuje, a to je kapitola 12.)
- b na přímce → nekonečně mnoho řešení
A když na ní leží, jde poskládat nekonečně mnoha způsoby — přidat víc jednoho sloupce a méně druhého vyjde nastejno. Tři možnosti a žádná čtvrtá: právě jedno, žádné, nebo nekonečně mnoho. Přesně dvě řešení mít soustava lineárních rovnic nemůže.
Tenhle pohled dá klasifikaci zadarmo:
| situace | počet řešení | maticově |
|---|---|---|
| sloupce dosáhnou všude, cíl je dosažitelný | právě jedno | det ≠ 0, plná hodnost |
| sloupce dosáhnou jen na podprostor, cíl leží mimo | žádné | hodnost(A) < hodnost([A|b]) |
| sloupce dosáhnou jen na podprostor, cíl v něm leží | nekonečně mnoho | hodnosti si rovné, jádro netriviální |
A vypadne z toho i fakt, který zaskočí: soustava lineárních rovnic nemůže mít přesně dvě řešení. Kdyby existovala dvě, jejich rozdíl je nenulový vektor, který se zobrazí na nulu — a pak se dá přičíst kolikrát chce, takže řešení je hned nekonečně mnoho.
Jak se to řeší
Gaussovou eliminací: rovnice se přičítají a odečítají tak dlouho, až zůstane trojúhelníkový tvar, a ten se dopočítá zpětným chodem. Kalkulačka v téhle labce ukazuje každý krok, protože jinak je to nekontrolovatelná černá skříňka.
Pivotace není kosmetika. Když je vedoucí prvek nula, eliminace prostě nejde provést a musí se prohodit řádky. Horší je případ, kdy je vedoucí prvek jen malý: dělí se jím a chyba se zvětší v poměru, o jaký byl menší než ostatní. Proto se řádky prohazují vždycky tak, aby se pivotoval největší dostupný prvek — tomu se říká částečná pivotace a solver v téhle labce ji dělá. Testy na to mají případ s nulou v prvním pivotu, kde by to bez pivotace selhalo úplně.
Nikdy neřešte soustavu inverzí. x = A⁻¹b
je matematicky správně a numericky hloupé: spočítat celou inverzi je ~3× dražší než rozklad,
a výsledek je méně přesný, protože se počítá n soustav místo jedné. Správně je LU rozklad
a dosazení — kapitola 7. Inverze se počítá jen tehdy, když je opravdu potřeba ona sama,
což je vzácné.