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.Gabriel Cramer: Introduction à l’analyse des lignes courbes algébriques. Genf 1750, S. 657–659.
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
. 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. 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. Cramerovo pravidlo může být také numericky nestabilní i pro soustavy o dvou rovnicích. Nedávno se však ukázalo, že Cramerovo pravidlo lze implementovat se stejnou složitostí jako Gaussova eliminace (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.
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. 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 .
500x500pixelů
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í.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.). É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ý. 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. 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.Antoni A. Kosinski: Cramer's Rule Is Due to cramer. In: Mathematics Magazine. Bd. 74, Nr. 4, Oktober 2001, S. 310–312. 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.Bruce A. Hedman: An Earlier Date for „Cramer’s Rule“ In: Historica Mathematica. Bd. 24, 1999, S. 365–368.
Odkazy Reference
Literatura
Související články Adjungovaná matice Determinant Matice Regulární matice Soustava lineárních rovnic
Externí odkazy
Online výpočet soustav lineárních rovnic
Kategorie:Rovnice Kategorie:Teorie matic Kategorie:Matematické věty a důkazy