Eliminace, LU a QR — jak se to počítá doopravdy
Předchozí kapitoly říkaly, co se počítá. Tahle říká jak — a hlavně proč zrovna tak, protože rozdíl mezi „matematicky správně“ a „použitelné“ je tady největší z celé labky.
Gaussova eliminace, krok za krokem
- A·x = b — rozšířená matice [A | b]
Soustava se zapíše jako rozšířená matice: koeficienty vlevo, pravá strana za čarou. Řádkové úpravy pak dělají s rovnicemi přesně to, co by člověk dělal ručně — jen se nemusí pořád opisovat x, y, z.
- R1 ↔ R2
Prohodí se řádky 1 a 2. Pivotuje se vždycky na největším dostupném prvku — ne proto, že by to bylo hezčí, ale protože se pivotem dělí a malý dělitel zvětší chybu.
- R1 ÷ −3,00
Řádek 1 se vydělí pivotem, aby na něm vznikla jednička.
- R2 + −2,00·R1
Od řádku 2 se odečte 2,00× řádek 1 — tím ve sloupci zůstane nula.
- R3 + 2,00·R1
Od řádku 3 se odečte -2,00× řádek 1 — tím ve sloupci zůstane nula.
- R2 ↔ R3
Prohodí se řádky 2 a 3. Pivotuje se vždycky na největším dostupném prvku — ne proto, že by to bylo hezčí, ale protože se pivotem dělí a malý dělitel zvětší chybu.
- R2 ÷ 1,67
Řádek 2 se vydělí pivotem, aby na něm vznikla jednička.
- R1 + −0,33·R2
Od řádku 1 se odečte 0,33× řádek 2 — tím ve sloupci zůstane nula.
- R3 + −0,33·R2
Od řádku 3 se odečte 0,33× řádek 2 — tím ve sloupci zůstane nula.
- R3 ÷ 0,20
Řádek 3 se vydělí pivotem, aby na něm vznikla jednička.
- R1 + 0,80·R3
Od řádku 1 se odečte -0,80× řádek 3 — tím ve sloupci zůstane nula.
- R2 + −0,40·R3
Od řádku 2 se odečte 0,40× řádek 3 — tím ve sloupci zůstane nula.
- x = (2, 3, −1)
Vlevo zůstala jednotková matice, takže vpravo stojí rovnou řešení. Tomuhle tvaru se říká redukovaný stupňovitý tvar a je jediný — ať se k němu jde jakoukoli cestou, vyjde týž.
Tři povolené úpravy, a všechny tři jsou vratné, což je přesně důvod, proč nemění množinu řešení: prohodit dva řádky, vynásobit řádek nenulovým číslem, přičíst k řádku násobek jiného.
LU: rozklad, který se vyplatí schovat
Eliminace se dá zapsat: U je to, co zbylo, L jsou násobky, kterými se odečítalo, a P říká, které řádky se prohodily. K čemu to je: když se má tatáž soustava řešit pro víc pravých stran, eliminace se udělá jednou (cena ~n³/3) a každá další pravá strana stojí jen dosazení (cena ~n²). U ramene, které řeší tutéž soustavu tisíckrát za sekundu s jinými čísly, je to rozdíl mezi „jde to“ a „nejde to“.
QR: když se rovnic sejde víc než neznámých
Q vzniká Gram-Schmidtovou ortogonalizací sloupců — je to kapitola 9 VectorLabu, zapsaná do matic. R jsou průměty, které se přitom odečetly.
QR je základ řešení přeurčených soustav (víc rovnic než neznámých, tedy každé proložení dat) a je numericky výrazně lepší než normální rovnice AᵀA x = Aᵀb: součin AᵀA totiž umocní číslo podmíněnosti na druhou. Matice s κ = 10⁴, se kterou se dá pracovat, dá po vynásobení sama sebou κ = 10⁸ a polovina platných číslic je pryč. Viz OptiLab.
Táž past je v této labce. SVD se tu počítá přes AᵀA — je to krátké a pro učební matice úplně stačí, ale platí se za to přesně tou polovinou číslic. Solver to má napsané v komentáři a jeho tolerance na hodnost je proto 10⁻⁷, ne 10⁻¹². Chytily to testy: matice hodnosti 2 hlásila hodnost 3, protože její nejmenší singulární hodnota vyšla 7,7·10⁻⁹ místo nuly.
Kolik to stojí
| operace | cena | poznámka |
|---|---|---|
| násobení A·B | ~n³ | |
| LU rozklad | ~n³/3 | a pak každá pravá strana jen n² |
| inverze | ~n³ | 3× dražší než LU a méně přesná |
| QR | ~2n³/3 | stabilnější, pro přeurčené soustavy |
| determinant z definice | n! | u 20×20 déle než stáří vesmíru |