Cramerin sääntö

Lineaarialgebrassa, Cramerin sääntö on kaava yhtä monta yhtälöä ja tuntematonta sisältävän lineaarisen yhtälöryhmän ratkaisemiseksi. Sääntö pätee aina, kun yhtälöryhmällä on tasan yksi ratkaisu.

Sääntö ilmaisee ratkaisun kullekin lineaarisen yhtälöryhmän tuntemattomalle kahden determinantin osamäärän avulla. Determinantit saadaan yhtälöryhmän kertoimien muodostamasta neliömatriisista ja erityisestä kerroinmatriisista muodostetusta matriisista, missä sopiva kertoimien sarake on korvattu yhtälöryhmän vakioilla.

Cramerin sääntö on nimetty Gabriel Cramerin (1704–1752) mukaan, joka julkaisi säännön mielivaltaiselle tuntemattomien muuttujien määrälle vuonna 1750, joskin Colin Maclaurin julkaisi säännön erikoistapauksen 1748 ja mahdollisesti tunsi säännön jo 1729.

Yleinen tapaus
Tarkastellaan lineaarista yhtälöryhmää, missä on n tuntematonta ja n riviä.

Yhtälöryhmä voidaan esittää matriisien tulona seuraavasti:
,

missä  matriisilla  on nollasta poikkeava determinantti, ja vektori  on muuttujien muodostama sarakevektori.

Cramerin säännön mukaan jos tällä lineaarisella yhtälöryhmällä on yksittäinen ratkaisu, niin tuntemattomien arvot saadaan kaavasta:

missä  on matriisi joka muodostetaan korvaamalla matriisin  i:s sarake sarakevektorilla .

Sääntö pätee lineaarisille yhtälöryhmille, jonka kertoimet ja vakiot kuuluvat mihin tahansa kuntaan, ei ainoastaan reaaliluvuille.

On näytetty, että Cramerin sääntö voidaan toteuttaa ajassa O(n3). Aikavaativuus on verrattavissa Gaussin-Jordanin eliminaatiomenetelmään. Luokkaan O(n3) pääsemiseksi tarvitaan Cramerin säännön osalta tehokasta determinantin laskemistapaa. Perinteisellä determinantin laskukaavalla lasketaan   matriisien determinantteja n+1 kertaa antaen työmääräksi (n+1)!(n-1) laskutoimusta. Näin ollen perinteisellä determinantin laskukaavalla Cramerin säännön aikavaatimus on luokkaa O(n!n) .

Todistus

Olkoon  kertoimien matriisi ja alimatriisi  matriisi, joka on saatu poistamalla matriisista  i:s rivi ja j:s sarake. 

Määritellään alkion  kofaktori 
. 

Esitellään vielä uusi matriisi korvaamalla matriisin A alkiot niiden kofaktoreilla ja transponoimalla saatu matriisi. Tätä matriisia kutsutaan adjungoiduksi matriisiksi  ja se merkitään

.

Olkoon edelleen , jolloin sillä on käänteismatriisi. Kääntyvälle matriisille pätee:
 ja .

Nyt käänteismatriisi  voidaan esittää A:n determinantin käänteisluvun ja :n adjungoidun matriisin tulona. 

.

Koska kyseessä on matriisitulo, niin tämä tarkoittaa sitä, että 

.

Olkoon nyt

.

Jos selvitämme determinantin  kehittämällä i:nnen sarakkeen suhteen, niin huomaamme, että

. 

Tällöin 

.

Esimerkkejä pienillä yhtälöryhmillä

Tarkastellaan lineaarista yhtälöryhmää  

Yhtälöryhmä voidaan esittää matriisimuodossa:  

Oletetaan, että ad − bc ei ole 0. Nyt x ja y voidaan löytää Cramerin säännöllä:
 
ja

Säännöt 3×3-matriiseille ovat samankaltaiset. Olkoon .

Yhtälöryhmä voidaan esittää matriisimuodossa 

Arvot muuttujille x, y ja z voidaan löytää seuraavasti:

Katso myös
 Matriisi
 Lineaarinen yhtälöryhmä

Lähteet

Kirjallisuutta
 
 

Lineaarialgebra