Cramerin sääntö

Wikipedia
Loikkaa: valikkoon, hakuun

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[1], joskin Colin Maclaurin julkaisi säännön erikoistapauksen 1748[2] ja mahdollisesti tunsi säännön jo 1729.[3][4][5]


Yleinen tapaus[muokkaa | muokkaa wikitekstiä]

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

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

 A\bold{x} = \bold{b},

missä n \times n matriisilla  A on nollasta poikkeava determinantti, ja vektori  \bold{x} = (x_1, \ldots, x_n)^\mathrm{T} 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:

 x_i = \frac{\det(A_i)}{\det(A)} \qquad i = 1, \ldots, n \,

missä  A_i on matriisi joka muodstetaan korvaamalla matriisin  A i:s sarake sarakevektorilla  \bold{b} .

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)[6]. 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 n \times n 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) [7].


Todistus[muokkaa | muokkaa wikitekstiä]

Olkoon A kertoimien matriisi ja alimatriisi M_{ij} matriisi, joka on saatu poistamalla matriisista A i:s rivi ja j:s sarake.

Määritellään alkion a_{ij} kofaktori

(-1)^{i+j} det(M_{ij}) = A_{ij}.

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

\operatorname{adj} A = \begin{bmatrix}A_{11} & \cdots & A_{1n} \\ \vdots & \ddots & \vdots \\ A_{n1} & \cdots & A_{nn} \end{bmatrix}^\operatorname{T}.


Olkoon edelleen det (A) \neq 0, jolloin sillä on käänteismatriisi. Kääntyvälle matriisille pätee:

A \left( \frac{1}{\det A}\operatorname{adj} A \right) = I ja \left( \frac{1}{\det A}\operatorname{adj} A \right) A = I.

Nyt käänteismatriisi A^{-1} voidaan esittää A:n determinantin käänteisluvun ja A:n adjungoidun matriisin tulona.

\bold{x}=\begin{bmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n 
\end{bmatrix}= A^{-1}\bold{b}=
\begin{bmatrix}
\frac{A_{11}}{{det(A)}} & \frac{A_{21}}{{det(A)}} & \dots & \frac{A_{n1}}{{det(A)}}\\ 
\frac{A_{12}}{{det(A)}} & \frac{A_{22}}{{det(A)}} & \dots & \frac{A_{n2}}{{det(A)}}\\ 
\vdots & \vdots & & \vdots \\
\frac{A_{1i}}{{det(A)}} & \frac{A_{2i}}{{det(A)}} & \dots & \frac{A_{ni}}{{det(A)}}\\ 
\vdots & \vdots & & \vdots \\
\frac{A_{1n}}{{det(A)}} & \frac{A_{2n}}{{det(A)}} & \dots & \frac{A_{nn}}{{det(A)}}
\end{bmatrix} 
\begin{bmatrix}
b_1 \\
b_2 \\
\vdots \\
b_n 
\end{bmatrix}.

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


x_i = \frac{A_{1i}}{{det(A)}}b_1 + \frac{A_{2i}}{{det(A)}}b_2 + \dots + \frac{A_{ni}}{{det(A)}}b_n, \text{ kun } i = 1,2,3,\dots,n.

Olkoon nyt

A_i=
\begin{bmatrix}
a_{11} & a_{12} & \dots & a_{1i-1} & b_1 & a_{1i+1} & \dots & a_{1n} \\
a_{21} & a_{22} & \dots & a_{2i-1} & b_1 & a_{2i+1} & \dots & a_{2n} \\
\vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots\\
a_{n1} & a_{n2} & \dots & a_{ni-1} & b_1 & a_{ni+1} & \dots & a_{nn} \\
\end{bmatrix} 
.

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

det(A_i) = A_{1i}b_1 + A_{2i}b_2 + \dots + A_{ni}b_n.

Tällöin

x_i = \frac{det(A_i)}{det(A)}\text{, kun } i = 1,2,\dots,n. [8]


Esimerkkejä pienillä yhtälöryhmillä[muokkaa | muokkaa wikitekstiä]

Tarkastellaan lineaarista yhtälöryhmää \left\{\begin{matrix}ax+by&={\color{red}e}\\ cx + dy&= {\color{red}f}\end{matrix}\right.\

Yhtälöryhmä voidaan esittää matriisimuodossa: \begin{bmatrix} a & b \\ c & d \end{bmatrix}\begin{bmatrix} x \\ y \end{bmatrix}=\begin{bmatrix} {\color{red}e} \\ {\color{red}f} \end{bmatrix}.

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

x = \begin{vmatrix} \color{red}{e} & b \\ \color{red}{f} & d \end{vmatrix}/\begin{vmatrix} a & b \\ c & d \end{vmatrix}  = { {\color{red}e}d - b{\color{red}f} \over ad - bc}

ja

y = \begin{vmatrix} a & \color{red}{e} \\ c & \color{red}{f} \end{vmatrix}/\begin{vmatrix} a & b \\ c & d \end{vmatrix}  = { a{\color{red}f} - {\color{red}e}c \over ad - bc}.

Säännöt 3×3-matriiseille ovat samankaltaiset. Olkoon \left\{\begin{matrix}ax + by + cz&= {\color{red}j}\\dx + ey + fz&= {\color{red}k}\\gx + hy + iz&= {\color{red}l}\end{matrix}\right..

Yhtälöryhmä voidaan esittää matriisimuodossa \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix}\begin{bmatrix} x \\ y \\ z \end{bmatrix}=\begin{bmatrix} {\color{red}j} \\ {\color{red}k} \\ {\color{red}l} \end{bmatrix}.

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

x = \frac { \begin{vmatrix} {\color{red}j} & b & c \\ {\color{red}k} & e & f \\ {\color{red}l} & h & i \end{vmatrix} } { \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} }, \quad y = \frac { \begin{vmatrix} a & {\color{red}j} & c \\ d & {\color{red}k} & f \\ g & {\color{red}l} & i \end{vmatrix} } { \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} },\text{ ja }z = \frac { \begin{vmatrix} a & b & {\color{red}j} \\ d & e & {\color{red}k} \\ g & h & {\color{red}l} \end{vmatrix} } { \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} }.


Katso myös[muokkaa | muokkaa wikitekstiä]

Viitteet[muokkaa | muokkaa wikitekstiä]

  1. Cramer, Gabriel: Introduction à l'Analyse des lignes Courbes algébriques Europeana. Viitattu 2012-05-18.
  2. MacLaurin, Colin (1748). A Treatise of Algebra, in Three Parts.. 
  3. Boyer, Carl B. (1968). A History of Mathematics, 2nd, Wiley, 431. 
  4. Katz, Victor (2004). A History of Mathematics, Brief, Pearson Education, 378–379. 
  5. Hedman, Bruce A. (1999). "An Earlier Date for Cramer's rule". Historia Mathematica 4(26): 365–368. doi:10.1006/hmat.1999.2247. 
  6. Ken Habgood, Itamar Arel (2012). "A condensation-based application of Cramerʼs rule for solving large-scale linear systems". Journal of Discrete Algorithms 10: 98–109. doi:10.1016/j.jda.2011.06.007. 
  7. Haataja, Juha: Numeeriset menetelmät käytännössä Viitattu 2013-09-15.
  8. Kolman, Bernard (2000). Elementary Linear Algebra, 7th, Prentice Hall.