Cramer metod

Cramers metod ( Cramers regel) är en metod för att lösa system av linjära algebraiska ekvationer med antalet ekvationer lika med antalet okända med en huvuddeterminant som inte är noll för koefficientmatrisen för systemet (desutom, för sådana ekvationer, lösningen finns och är unik). [ett]

Beskrivning av metoden

För ett system av linjära ekvationer med okända (över ett godtyckligt fält ) $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}}

med determinanten för systemmatrisen , som skiljer sig från noll, skrivs lösningen i formen $\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}}

(den i:te kolumnen i systemmatrisen ersätts av en kolumn med fria termer).
I en annan form är Cramers regel formulerad enligt följande: för alla koefficienter c 1 , c 2 , ..., c n är likheten sann:

(c_{1}x_{1}+c_{2}x_{2}+\dots +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}}

I denna form är Cramers metod giltig utan antagandet att den skiljer sig från noll, det är inte ens nödvändigt att koefficienterna för systemet är element i en integralring (systemets determinant kan till och med vara en nolldelare i ringen av koefficienter). Vi kan också anta att antingen mängderna och , eller mängden inte består av element i systemets koefficientring, utan av någon modul över denna ring. I denna form används Cramers formel till exempel för att bevisa formeln för Grams determinant och Nakayamas Lemma . $\Delta$ $b_{1},b_{2},...,b_{n}$ $x_{1},x_{2},...,x_{n}$ $c_{1},c_{2},...,c_{n}$

Exempel

System av linjära ekvationer med reella koefficienter:

{\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{case}}

Kvalificerade:

{\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}}

I determinanterna ersätts kolumnen med koefficienter för motsvarande okända med kolumnen med fria termer i systemet.

Lösning:

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

Exempel:

{\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}}

Kvalificerade:

\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$

Beräkningskomplexitet

Cramers metod kräver beräkning av dimensionella bestämningsfaktorer . När man använder Gauss-metoden för att beräkna determinanterna, har metoden komplexitet i elementära operationer av addition-multiplikation av ordningen , vilket är svårare än Gauss-metoden när man löser systemet direkt. Därför ansågs metoden, ur tidssynpunkt för beräkningar, opraktisk. 2010 visades det dock att Cramers metod kan implementeras med en komplexitet som är jämförbar med den för Gaussmetoden [2] . $n+1$ $n\ gånger n$ $O(n^{4})$ $O(n^{3})$

Litteratur

Maltsev I. A. Grunderna i linjär algebra. - Ed. 3:e, reviderad, M .: "Nauka", 1970. - 400 sid.

Anteckningar

↑ Cramer, Gabriel. Introduktion à l'Analyse des lignes Courbes algébriques (franska) 656–659. Genève: Europeana (1750). Hämtad: 18 maj 2012.
↑ Ken Habgood och Itamar Arel. 2010. Återbesök Cramers regel för att lösa täta linjära system. I samband med vårsimuleringsmultikonferensen 2010 (SpringSim '10)

Se även

Gauss metod

Metoder för att lösa SLAE
Direkta metoder	Matrismetod Gauss metod Gauss-Jordan-metoden Cramer metod LU-nedbrytning Cholesky nedbrytning Sopa metod
Iterativa metoder	Jacobi metod Gauss-Seidel-metoden Iterationsmetod Avslappningsmetod Konjugerad gradientmetod Bikonjugerad gradientmetod Stabiliserad bikonjugatgradientmetod
Allmän	invers matris Projektionsmetoder för att lösa SLAE Förkonditionering