Cramerova metoda

Cramerova metoda ( Cramerovo pravidlo ) je metoda pro řešení soustav lineárních algebraických rovnic s počtem rovnic rovným počtu neznámých s nenulovým hlavním determinantem matice koeficientů soustavy (navíc pro takové rovnice je řešení existuje a je jedinečný). [jeden]

Popis metody

Pro soustavu lineárních rovnic s neznámými (nad libovolným polem ) $n$ $n$

{\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\ldots +a_{1n}x_{n}=b_{1}\\a_{21}x_{1} +a_{22}x_{2}+\ldots +a_{2n}x_{n}=b_{2}\\\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ a_{n1}x_{1}+a_{n2}x_{2}+\ldots +a_{nn}x_{n}=b_{n}\\\end{cases}}

s determinantem systémové matice , který je odlišný od nuly, se řešení zapíše ve tvaru $\Delta$

x_{i}={\frac {1}{\Delta }}{\begin{vmatrix}a_{11}&\ldots &a_{1,i-1}&b_{1}&a_{1,i+1}& \ldots &a_{1n}\\a_{21}&\ldots &a_{2,i-1}&b_{2}&a_{2,i+1}&\ldots &a_{2n}\\\ldots &\ldots & \ldots &\ldots &\ldots &\ldots &\ldots \\a_{n-1,1}&\ldots &a_{n-1,i-1}&b_{n-1}&a_{n-1,i +1}&\ldots &a_{n-1,n}\\a_{n1}&\ldots &a_{n,i-1}&b_{n}&a_{n,i+1}&\ldots &a_{nn} \\\end{vmatrix}}

(i-tý sloupec systémové matice je nahrazen sloupcem volných členů).
V jiné podobě je Cramerovo pravidlo formulováno následovně: pro libovolné koeficienty c 1 , c 2 , ..., c n platí rovnost:

(c_{1}x_{1}+c_{2}x_{2}+\tečky +c_{n}x_{n})\cdot \Delta =-{\begin{vmatrix}a_{11}&a_{12 }&\ldots &a_{1n}&b_{1}\\a_{21}&a_{22}&\ldots &a_{2n}&b_{2}\\\ldots &\ldots &\ldots &\ldots &\ldots \ \a_{n1}&a_{n2}&\ldots &a_{nn}&b_{n}\\c_{1}&c_{2}&\ldots &c_{n}&0\\\end{vmatrix}}

V této podobě platí Cramerova metoda bez předpokladu, že se liší od nuly, dokonce není nutné, aby koeficienty systému byly prvky integrálního kruhu (determinantem systému může být i nulový dělitel v kruhu koeficientů). Můžeme také předpokládat, že buď množiny a , nebo množina se neskládá z prvků koeficientového prstence soustavy, ale z nějakého modulu nad tímto prstencem. V této podobě se Cramerův vzorec používá například při dokazování vzorce pro Gramův determinant a Nakayamovo lemma . $\Delta$ $b_{1},b_{2},...,b_{n}$ $x_{1},x_{2},...,x_{n}$ $c_{1},c_{2},...,c_{n}$

Příklad

Soustava lineárních rovnic s reálnými koeficienty:

{\begin{cases}a_{11}x_{1}+a_{12}x_{2}+a_{13}x_{3}=b_{1}\\a_{21}x_{1}+a_{ 22}x_{2}+a_{23}x_{3}=b_{2}\\a_{31}x_{1}+a_{32}x_{2}+a_{33}x_{3}=b_ {3}\\\end{cases}}

Kvalifikace:

{\textstyle \Delta ={\begin{vmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{ 33}\\\end{vmatrix}},\ \ \Delta _{1}={\begin{vmatrix}b_{1}&a_{12}&a_{13}\\b_{2}&a_{22}&a_{ 23}\\b_{3}&a_{32}&a_{33}\\\end{vmatrix}},\ \ }

\Delta _{2}={\begin{vmatrix}a_{11}&b_{1}&a_{13}\\a_{21}&b_{2}&a_{23}\\a_{31}&b_{3}&a_ {33}\\\end{vmatrix}},\ \ \Delta _{3}={\begin{vmatrix}a_{11}&a_{12}&b_{1}\\a_{21}&a_{22}&b_ {2}\\a_{31}&a_{32}&b_{3}\\\end{vmatrix}}

V determinantech je sloupec koeficientů pro odpovídající neznámou nahrazen sloupcem volných členů soustavy.

Řešení:

x_{1}={\frac {\Delta _{1)){\Delta )),\ \ x_{2}={\frac {\Delta _{2)){\Delta )),\ \ x_{ 3}={\frac {\Delta _{3)){\Delta }}

Příklad:

{\begin{cases}2x_{1}+5x_{2}+4x_{3}=30\\x_{1}+3x_{2}+2x_{3}=150\\2x_{1}+10x_{2 }+9x_{3}=110\\\end{cases}}

Kvalifikace:

\Delta ={\begin{vmatrix}2&5&4\\1&3&2\\2&10&9\\\end{vmatrix}}=5,\ \ \Delta _{1}={\begin{vmatrix}30&5&4\\150&3&2\\110&10&9\ \\end{vmatrix}}=-760,\ \

\Delta _{2}={\begin{vmatrix}2&30&4\\1&150&2\\2&110&9\\\end{vmatrix}}=1350,\ \ \Delta _{3}={\begin{vmatrix}2&5&30\\1&3&150 \\2&10&110\\\end{vmatrix}}=-1270.

$x_{1}=-{\frac {760}{5}}=-152,\ \ x_{2}={\frac {1350}{5}}=270,\ \ x_{3}=-{\ frac {1270}{5}}=-254$

Výpočetní složitost

Cramerova metoda vyžaduje výpočet rozměrových determinantů . Při použití Gaussovy metody pro výpočet determinantů má metoda složitost v elementárních operacích sčítání-násobení řádu , což je při přímém řešení soustavy obtížnější než Gaussova metoda . Proto byla metoda z hlediska času stráveného výpočty považována za nepraktickou. V roce 2010 se však ukázalo, že Cramerovu metodu lze implementovat se složitostí srovnatelnou s Gaussovou metodou [2] . $n+1$ $n\krát n$ $O(n^{4})$ $O(n^{3})$

Literatura

Maltsev I. A. Základy lineární algebry. - Ed. 3., přepracované, M.: "Nauka", 1970. - 400 s.

Poznámky

↑ Cramer, Gabriel. Úvod à l'Analyse des lignes Courbes algébriques (francouzsky) 656–659. Ženeva: Europeana (1750). Staženo: 18. května 2012.
↑ Ken Habgood a Itamar Arel. 2010. Přehodnocení Cramerova pravidla pro řešení hustých lineárních systémů. In Proceedings of the Spring Simulation Multiconference 2010 (SpringSim '10)

Viz také

Gaussova metoda

Metody řešení SLAE
Přímé metody	Maticová metoda Gaussova metoda Gauss-Jordanova metoda Cramerova metoda LU rozklad Choleský rozklad Metoda zametání
Iterační metody	Jacobiho metoda Gauss-Seidelova metoda Iterační metoda Relaxační metoda Metoda konjugovaného gradientu Metoda bikonjugovaného gradientu Metoda stabilizovaného bikonjugátového gradientu
Všeobecné	inverzní matice Projekční metody pro řešení SLAE Předběžná úprava