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í
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
má 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
Soustava o dvou neznámých
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
Pro soustavu lineárních rovnic:
s rozšířenou maticí
jsou složky řešení podle Cramerova pravidla dána podíly:
Důkaz
Ř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
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
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
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
Celočíselné programování
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
Cramerovo pravidlo se používá k odvození obecného řešení nehomogenní lineární diferenciální rovnice metodou variace konstant.
Ricciho kalkul
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
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]
Odkazy
Reference
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.
- ↑ a b Gabriel Cramer: Introduction à l’analyse des lignes courbes algébriques. Genf 1750, S. 657–659.
- ↑ Cramerovo pravidlo — Matematika polopatě. www.matweb.cz [online]. [cit. 2021-08-16]. Dostupné online.
- ↑ David Poole. Linear Algebra: A Modern Introduction. [s.l.]: Cengage Learning, 2014. ISBN 978-1-285-98283-0. S. 276. Je zde použita šablona
{{Cite book}}
označená jako k „pouze dočasnému použití“.
- ↑ 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. Je zde použita šablona
{{Cite book}}
označená jako k „pouze dočasnému použití“.
- ↑ Thomas S. Shores. Applied Linear Algebra and Matrix Analysis. [s.l.]: Springer Science & Business Media, 2007. ISBN 978-0-387-48947-6. S. 132. Je zde použita šablona
{{Cite book}}
označená jako k „pouze dočasnému použití“.
- ↑ Nicholas J. Higham. Accuracy and Stability of Numerical Algorithms: Second Edition. [s.l.]: SIAM, 2002. ISBN 978-0-89871-521-7. S. 13. Je zde použita šablona
{{Cite book}}
označená jako k „pouze dočasnému použití“.
- ↑ 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. Je zde použita šablona
{{Cite journal}}
označená jako k „pouze dočasnému použití“.
- ↑ 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. Je zde použita šablona
{{Cite journal}}
označená jako k „pouze dočasnému použití“.
- ↑ LEVI-CIVITA, Tullio. The Absolute Differential Calculus (Calculus of Tensors). [s.l.]: Dover, 1926. ISBN 9780486634012. S. 111–112. Je zde použita šablona
{{Cite book}}
označená jako k „pouze dočasnému použití“.
- ↑ 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.).
- ↑ Antoni A. Kosinski: Cramer's Rule Is Due to cramer. In: Mathematics Magazine. Bd. 74, Nr. 4, Oktober 2001, S. 310–312.
- ↑ Bruce A. Hedman: An Earlier Date for „Cramer’s Rule“ In: Historica Mathematica. Bd. 24, 1999, S. 365–368.
Literatura
- 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
Externí odkazy