Kysymyksen kirjaimeen vastaamiseksi "tavalliset pienimmät neliöt" ei ole algoritmi; pikemminkin se on tietyntyyppinen ongelma laskennallisessa lineaarisessa algebrassa, josta yksi esimerkki on lineaarinen regressio. Tavallisesti yhdellä on tiedot $ \ ((x_1, y_1), \ pisteet, (x_m, y_m) \} $ ja alustava funktio ("malli"), johon tiedot sovitetaan, muodossa $ f (x) = c_1 f_1 (x) + \ pistettä + c_n f_n (x) $. $ F_j (x) $ kutsutaan "perustoiminnoiksi", ja ne voivat olla mitä tahansa monomaaaleista $ x ^ j $ trigonometrisiin funktioihin (esim. $ \ Sin (jx) $, $ \ cos (jx) $) ja eksponentiaalisiin funktioihin ($ \ exp (-jx) $). Termi "lineaarinen" "lineaarisessa regressiossa" tässä ei viittaa perustoimintoihin, vaan kertoimiin $ c_j $ siinä, että mallin osittaisen johdannaisen ottaminen mihin tahansa $ c_j $: sta antaa sinulle kertoimen $ c_j $; eli $ f_j (x) $.
Yhdellä on nyt $ m \ kertaa n $ suorakulmainen matriisi $ \ mathbf A $ ("suunnittelumatriisi"), jolla (yleensä) on enemmän rivejä kuin sarakkeita, ja jokainen merkintä on muodoltaan $ f_j (x_i) $, $ i $ on riviindeksi ja $ j $ on sarakeindeksi. OLS: n tehtävänä on nyt löytää vektori $ \ mathbf c = (c_1 \, \ dots \, c_n) ^ \ top $, joka minimoi määrän $ \ sqrt {\ sum \ limits_ {j = 1} ^ {m} \ vasen (y_j-f (x_j) \ oikea) ^ 2} $ (matriisimerkinnässä $ \ | \ mathbf {A} \ mathbf {c} - \ mathbf {y} \ | _2 $; tässä, $ \ mathbf { y} = (y_1 \, \ pisteet \, y_m) ^ \ top $ kutsutaan yleensä "vastevektoriksi").
Käytännössä käytetään ainakin kolmea menetelmää pienimmän neliösumman ratkaisujen laskemiseksi: normaaliyhtälöt, QR-hajoaminen ja yksikköarvon hajoaminen. Lyhyesti sanottuna ne ovat tapoja muuttaa matriisi $ \ mathbf {A} $ matriisien tuloksi, joita on helppo käsitellä vektorin $ \ mathbf {c} $ ratkaisemiseksi.
George osoitti jo normaalien yhtälöiden menetelmä vastauksessaan; ratkaistaan vain lineaaristen yhtälöiden $ n \ kertaa n $ joukko
$ \ mathbf {A} ^ \ top \ mathbf {A} \ mathbf {c} = \ mathbf {A} ^ \ top \ mathbf {y} $
kohteelle $ \ mathbf {c} $. Johtuen siitä, että matriisi $ \ mathbf {A} ^ \ top \ mathbf {A} $ on symmetrinen positiivinen (puoli) selvä, tavallinen tähän käytetty menetelmä on Cholesky-hajoaminen, joka kertoo $ \ mathbf {A} ^ \ top \ mathbf {A} $ muotoon $ \ mathbf {G} \ mathbf {G} ^ \ top $ ja $ \ mathbf {G} $ alemman kolmion matriisin. Tämän lähestymistavan ongelmana on se etu, että $ m \ times n $ -matriisista voidaan pakata (yleensä) paljon pienempi $ n \ kertaa n $ -matriisi, että tämä operaatio on taipuvainen merkittävien lukujen menetykseen ( tällä on jotain tekemistä suunnittelumatriisin "ehtonumeron" kanssa.
Hieman parempi tapa on QR-hajoaminen, joka toimii suoraan suunnittelumatriisin kanssa. Se kertoo $ \ mathbf {A} $ as $ \ mathbf {A} = \ mathbf {Q} \ mathbf {R} $, missä $ \ mathbf {Q} $ on ortogonaalinen matriisi (kertomalla tällainen matriisi sen transponoidulla saadaan identiteettimatriisi) ja $ \ mathbf {R} $ on ylempi kolmiomainen. $ \ mathbf {c} $ lasketaan myöhemmin nimellä $ \ mathbf {R} ^ {- 1} \ mathbf {Q} ^ \ top \ mathbf {y} $. Syistä, joihin en pääse (katso vain kunnollinen numeerinen lineaarinen algebrateksti, kuten tämä), tällä on paremmat numeeriset ominaisuudet kuin normaalien yhtälöiden menetelmällä.
Yksi vaihtelu QR-hajotuksen käytössä on seminaalinormaalien yhtälöiden menetelmä. Lyhyesti sanottuna, jos jollakin on hajotus $ \ mathbf {A} = \ mathbf {Q} \ mathbf {R} $, ratkaistava lineaarinen järjestelmä on muoto
$$ \ mathbf {R} ^ \ top \ mathbf {R} \ mathbf {c} = \ mathbf {A} ^ \ top \ mathbf {y} $$
Käytetään käytännössä QR-hajotusta muodostaen koleskyinen kolmio $ \ mathbf {A} ^ \ top \ mathbf {A} $ tässä lähestymistavassa. Tämä on hyödyllinen tilanteessa, jossa $ \ mathbf {A} $ on harva ja $ \ mathbf {Q} $ (tai sen eräs versio) nimenomainen tallennus ja / tai muodostus on ei-toivottua tai epäkäytännöllistä.
Lopuksi, kallein, mutta turvallisin tapa ratkaista OLS on singular value decomposition (SVD). Tällä kertaa $ \ mathbf {A} $ lasketaan muodossa $ \ mathbf {A} = \ mathbf {U} \ mathbf \ Sigma \ mathbf {V} ^ \ top $, missä $ \ mathbf {U} $ ja $ \ mathbf {V} $ ovat molemmat kohtisuoria, ja $ \ mathbf {\ Sigma} $ on lävistäjämatriisi, jonka lävistäjämerkintöjä kutsutaan "yksikköarvoiksi". Tämän hajoamisen voima on diagnoosikyvyssä, jonka yksittäiset arvot antavat sinulle siinä, että jos joku näkee yhden tai useamman pienen yksikön arvon, on todennäköistä, että olet valinnut ei täysin itsenäisen perustan, mikä edellyttää mallisi. (Aikaisemmin mainittu "ehtoluku" liittyy itse asiassa suurimman yksikköarvon ja pienimmän väliseen suhteeseen; suhde tietysti kasvaa valtavaksi (ja matriisi on siten huonosti ehdollistettu), jos pienin yksikköarvo on "pieni" .)
Tämä on vain luonnos näistä kolmesta algoritmista; minkä tahansa hyvän kirjan laskennallisista tilastoista ja numeerisesta lineaarisesta algebrasta pitäisi pystyä antamaan sinulle olennaisempia yksityiskohtia