Cramerovo pravidlo nebo metoda determinantů je matematický vzorec pro popis řešení soustavy lineárních rovnic s regulární maticí soustavy pomocí determinantů matice soustavy a matic z ní získaných nahrazením jednoho sloupce vektorem pravých stran. Je pojmenována po Gabrielu Cramerovi (1704–1752), který v roce 1750 publikoval pravidlo pro libovolný počet neznámých.[1]

Cramerovo pravidlo má především teoretický význam, protože výpočet mnoha determinantů obvyklým způsobem je výpočetně náročný. V praxi se proto pro řešení soustav používají jiné metody numerické matematiky.

Znění

editovat

Nechť čtvercová matice   řádu   je matici soustavy   lineárních rovnic o   neznámých (čili počet neznámých i rovnic je shodný). Nechť   je matice, získaná z matice   nahrazením  -tého sloupce sloupcem pravých stran.

Konkrétně, pro matici soustavy  a vektor pravých stran  

  tvar:

 

Pokud je matice soustavy   regulární, pak má soustava právě jedno řešení. Jednotlivé složky řešení   jsou určeny podíly [2]

 .

Konkrétně, pro soustavu o dvou neznámých

 

s rozšířenou matici soustavy

 

je řešení dáno vzorci:

  a
 

Pravidlo platí nejen v oboru reálných či komplexních čísel, ale i pro soustavy lineárních rovnic s koeficienty a neznámými v libovolném tělese.

Ukázky

editovat

Soustava o dvou neznámých

editovat

Reálná soustava lineárních rovnic:

 

dává rozšířenou matici soustavy:

 

Podle Cramerova pravidla je řešení soustavy určeno podíly:

 
 

Soustava o třech neznámých

editovat

Pro soustavu lineárních rovnic:

 

s rozšířenou maticí

 

jsou složky řešení podle Cramerova pravidla dána podíly:

 
 
 

Řešení soustavy splňuje vztah

 ,

neboli  , kde   značí  -tý sloupec matice  .

Pro matici  , sloupcový index   a libovolný vektor   značí symbol   matici, která vznikne z   nahrazením jejího  -tého sloupce vektorem  . Mimo jiné platí již dříve zavedená notace  .

Cramerovo pravidlo vyplývá ze dvou vlastností determinantu:

  • Determinant je multilineární vzhledem ke sloupcům (i řádkům) matice, tj. lineární vůči každému jednotlivému sloupci (řádku) a
  • je alternující vzhledem k pořadí sloupů (řádků), což má mimo jiné za následek, že determinant matice se dvěma shodnými sloupci (řádky) je nulový.

Z linearity determinantu vyplývá:

 

V rozvinutém tvaru lze tento krok zapsat:

 
 
 
 

Matice   je totožná s  , protože fakticky nedošlo k žádnému nahrazení. Pro každé   má matice   svůj  -tý sloupec shodný s  -tým (zvýrazněny zeleně) a její determinant je roven nule.

Po vyloučení nulových členů   pro   se výraz redukuje na:

 

Odtud Cramerovo pravidlo vyplývá vydělením obou stran nenulovým výrazem  .

Krátký důkaz

editovat

Krátký důkaz Cramerova pravidla začíná pozorováním, že   je determinant matice  , která vznikne z jednotkové matice   nahrazením  -tého sloupce   vektorem řešení  . V notaci předchozího důkazu jde o matici:

 

Za předpokladu, že původní matice   je regulární, lze sloupce matice   vyjádřit výrazy  , kde   je  -tý sloupec matice  . Připomeňme, že sloupce matice   jsou  , a proto  .

Zbývá využít fakt, že determinant součinu dvou matic je součinem determinantů, z čehož vyplývá:

 

Další verze důkazu

editovat

 

Jestliže matici získanou vynecháním j-tého řádku a i-tého sloupce matice   označíme  , pak rozvinutím determinantu v čitateli podle i-tého sloupce získáme

 

Zlomek ve výrazu je prvkem   inverzní matice  .

 

Protože   a  , je   a tedy

 

Výpočetní složitost

editovat

Cramerovo pravidlo implementované naivním způsobem je výpočetně neefektivní již pro soustavy s více než třemi rovnicemi.[3] V případě   rovnic o   neznámých vyžaduje výpočet   determinantů, zatímco Gaussova eliminace dává výsledek se stejnou výpočetní složitostí jako výpočet jediného determinantu.[4][5]  Cramerovo pravidlo může být také numericky nestabilní i pro soustavy o dvou rovnicích.[6] Nedávno se však ukázalo, že Cramerovo pravidlo lze implementovat se stejnou složitostí jako Gaussova eliminace [7][8] (vyžaduje dvakrát tolik aritmetických operací a má stejnou numerickou stabilitu, pokud jsou použity stejné permutační matice).

Aplikace

editovat

Celočíselné programování

editovat

Cramerovo pravidlo lze použít k důkazu, že problém celočíselného programování, jehož matice omezení je totálně unimodulární a jehož pravá strana je celočíselná, má celočíselná bázická řešení, což výrazně usnadňuje řešení úlohy.

Obyčejné diferenciální rovnice

editovat

Cramerovo pravidlo se používá k odvození obecného řešení nehomogenní lineární diferenciální rovnice metodou variace konstant.

Ricciho kalkul

editovat

Cramerovo pravidlo se používá v Ricciho kalkulu v různých výpočtech zahrnujících Christoffelovy symboly prvního a druhého druhu.[9]

Cramerovo pravidlo lze zejména využít v důkazu, že operátor divergence na Riemannově varietě je invariantní vzhledem ke změně souřadnic.

Historie

editovat

Cramerovo pravidlo publikoval v roce 1750 Gabriel Cramer ve své knize Introduction à l'analyse des lignes courbes algébriques.[1] V něm explicitně uvedl vzorce pro lineární soustavy rovnic až se třemi rovnicemi a popsal, jak lze vytvořit vzorce řešení pro soustavy rovnic s více rovnicemi. Protože determinant ještě nebyl zaveden, použil zlomky s polynomem v čitateli a jmenovateli. Jak ukazuje následující úryvek z původní práce, jsou totožné s polynomy Leibnizova vzorce .

 

Tento úryvek ukazuje, že Cramer ještě nepoužíval dnešní zápis soustav lineárních rovnic, protože v něm by vzorec zněl:

 

Sám Cramer si byl vědom, že soustavy lineárních rovnic nemají vždy jednoznačné řešení.[10] Étienne Bézout pak v roce 1764 ukázal, pokud soustavu rovnic nelze jednoznačně vyřešit, je determinant matice soustavy (jmenovatel ve výše uvedeném výrazu) nulový.[10] Cramer svůj vzorec nijak nedokázal, to provedl až Augustin Louis Cauchy v roce 1815. Cauchy též zavedl dodnes používanou notaci pro zápis Cramerova pravidla.

Již v roce 1678 si Cramerovo pravidlo zapsal Gottfried Wilhelm Leibniz ve svém rukopise. Ten však byl objeven až později a neměl tak žádný vliv na vývoj metod řešení soustav lineárních rovnic.[10] Speciální případy Cramerova pravidla pro soustavy dvou nebo tří rovnic popsal Colin Maclaurin ve svém Pojednání o algebře, publikovaném v roce 1748. Přestože měl nápad rozšířit tyto vzorce i na soustavy rovnic s více rovnicemi, nenašel na rozdíl od Cramera žádné pravidlo, jak správně nastavit znaménka v použitých polynomech.[11] Carl Benjamin Boyer vyvolal ve 20. století spor mezi matematickými historiky, zda byl objevitelem vzorce Maclaurin nebo Cramer. Doporučil, aby pravidlo bylo přejmenováno na Maclaurinovo-Cramerovo.[12]

Reference

editovat

V tomto článku byly použity překlady textů z článků Cramersche Regel na německé Wikipedii a Cramer's rule na anglické Wikipedii.

  1. a b Gabriel Cramer: Introduction à l’analyse des lignes courbes algébriques. Genf 1750, S. 657–659.
  2. Cramerovo pravidlo — Matematika polopatě. www.matweb.cz [online]. [cit. 2021-08-16]. Dostupné online. 
  3. David Poole. Linear Algebra: A Modern Introduction. [s.l.]: Cengage Learning, 2014. ISBN 978-1-285-98283-0. S. 276. 
  4. Joe D. Hoffman; STEVEN FRANKEL. Numerical Methods for Engineers and Scientists, Second Edition. [s.l.]: CRC Press, 2001. ISBN 978-0-8247-0443-8. S. 30. 
  5. Thomas S. Shores. Applied Linear Algebra and Matrix Analysis. [s.l.]: Springer Science & Business Media, 2007. ISBN 978-0-387-48947-6. S. 132. 
  6. Nicholas J. Higham. Accuracy and Stability of Numerical Algorithms: Second Edition. [s.l.]: SIAM, 2002. ISBN 978-0-89871-521-7. S. 13. 
  7. Ken Habgood; ITAMAR AREL. A condensation-based application of Cramerʼs rule for solving large-scale linear systems. Journal of Discrete Algorithms. 2012, s. 98–109. Dostupné online. DOI 10.1016/j.jda.2011.06.007. 
  8. G.I.Malaschonok. Solution of a System of Linear Equations in an Integral Ring. USSR J. Of Comput. Math. And Math. Phys.. 1983, s. 1497–1500. arXiv 1711.09452. 
  9. LEVI-CIVITA, Tullio. The Absolute Differential Calculus (Calculus of Tensors). [s.l.]: Dover, 1926. ISBN 9780486634012. S. 111–112. 
  10. a b c Jean-Luc Chabert et al.: A History of Algorithms. From the Pebble to the Microchip. Springer-Verlag, 1999, ISBN 3-540-63369-3, S. 284–287 (Tato kniha obsahuje anglický překlad Cramerovy původní publikace.).
  11. Antoni A. Kosinski: Cramer's Rule Is Due to cramer. In: Mathematics Magazine. Bd. 74, Nr. 4, Oktober 2001, S. 310–312.
  12. Bruce A. Hedman: An Earlier Date for „Cramer’s Rule“ In: Historica Mathematica. Bd. 24, 1999, S. 365–368.

Literatura

editovat
  • BÄRTSCH, Hans-Jochen. Matematické vzorce. Praha: Academia, 2006. 832 s. ISBN 80-200-1448-9. Kapitola Matice, s. 180–198. 
  • BEČVÁŘ, Jindřich. Lineární algebra. 1.. vyd. Praha: Matfyzpress, 2019. 436 s. ISBN 978-80-7378-392-1. 
  • HLADÍK, Milan. Lineární algebra (nejen) pro informatiky. 1.. vyd. Praha: Matfyzpress, 2019. 328 s. ISBN 978-80-7378-378-5. 
  • OLŠÁK, Petr. Lineární algebra [online]. Praha: 2007 [cit. 2023-02-20]. Dostupné online. 
  • MOTL, Luboš; ZAHRADNÍK, Miloš. Pěstujeme lineární algebru [online]. [cit. 2023-02-20]. Dostupné online. 

Související články

editovat

Externí odkazy

editovat