Lineární nejmenší čtverce a past normálních rovnic

Tohle je statická kopie kapitoly pro vyhledávače. Interaktivní verze má animované obrázky, kontrolní otázky a tlačítka, která příklad načtou do kalkulačky.

Lineární nejmenší čtverce a past normálních rovnic

Zvláštní případ, který stojí za vlastní kapitolu, protože je všude: model je v parametrech lineární a měření je víc než neznámých.

min ‖A x − b‖²přeurčená soustava, m > n

Derivace podle x se položí nule a vyjdou normální rovnice:

AᵀA x = Aᵀbnormální rovnice — pohodlné a zrádné

Proč to nedělat

Sestavit AᵀA je lákavé: matice je malá, čtvercová a symetrická. Jenže umocní číslo podmíněnosti na druhou:

κ(AᵀA) = κ(A)²a to stojí polovinu platných číslic

Když má A podmíněnost 10⁸ — což u polynomiálního proložení není nic zvláštního — má AᵀA 10¹⁶ a v dvojité přesnosti nezbude nic. Řešení přes ortogonální rozklad (QR) tenhle krok přeskočí a pracuje s podmíněností původní matice.

κ(A) = 18288, κ(AᵀA) = κ(A)² = 3.3e+8
Chyba QR: 2.08e-13 · chyba normálních rovnic: 5.03e-9 — 24150× horší
Sestavit AᵀA je pohodlné a stojí to polovinu platných číslic. U dobře podmíněné úlohy si toho nikdo nevšimne; tady ano.

Zvyšuj stupeň polynomu. Dokud je úloha slušně podmíněná, obě cesty splývají. Pak se normální rovnice utrhnou.

Nejde o zaokrouhlovací pedanterii. Obě cesty počítají totéž a na dobře podmíněné úloze se shodnou na poslední číslici — takže se ten rozdíl nikdy neprojeví, dokud najednou neprojeví. Testy tady proto kontrolují obojí: že si na slušné úloze odpovídají do 10⁻¹⁰, a že na Vandermondově matici je QR prokazatelně blíž pravdě.

Kde se to potkává se zbytkem akademie

Proložit přímku, spočítat rovinu ze změřených bodů, určit kalibrační konstanty senzoru — to všechno jsou lineární nejmenší čtverce. A jakmile je model v parametrech nelineární, přejde se ke Gauss-Newtonovi, který tuhle úlohu řeší opakovaně na linearizaci. Proto tahle kapitola stojí před ním.