Metoda Cramer

Metoda lui Cramer ( regula lui Cramer ) este o metodă de rezolvare a sistemelor de ecuații algebrice liniare cu numărul de ecuații egal cu numărul de necunoscute cu un determinant principal diferit de zero al matricei de coeficienți a sistemului (mai mult, pentru astfel de ecuații, soluția există și este unic). [unu]

Descrierea metodei

Pentru un sistem de ecuații liniare cu necunoscute (pe un câmp arbitrar ) $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}}

cu determinantul matricei sistemului , care este diferit de zero, soluția se scrie sub forma $\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}}

(coloana i-a a matricei sistemului este înlocuită cu o coloană de membri liberi).
Într-o altă formă, regula lui Cramer este formulată după cum urmează: pentru orice coeficienți c 1 , c 2 , ..., c n egalitatea este adevărată:

(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}}

În această formă, metoda lui Cramer este valabilă fără a presupune că este diferită de zero, nici măcar nu este necesar ca coeficienții sistemului să fie elemente ale unui inel integral (determinantul sistemului poate fi chiar un divizor de zero în inel). de coeficienţi). De asemenea, putem presupune că fie mulțimile și , fie mulțimea nu constă din elemente ale inelului de coeficienți al sistemului, ci dintr-un modul peste acest inel. În această formă, formula lui Cramer este utilizată, de exemplu, pentru a demonstra formula pentru determinantul lui Gram și Lema lui Nakayama . $\Delta$ $b_{1},b_{2},...,b_{n}$ $x_{1},x_{2},...,x_{n}$ $c_{1},c_{2},...,c_{n}$

Exemplu

Sistem de ecuații liniare cu coeficienți reali:

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

Calificări:

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

În determinanți, coloana de coeficienți pentru necunoscuta corespunzătoare este înlocuită cu coloana de termeni liberi ai sistemului.

Soluţie:

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

Exemplu:

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

Calificări:

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

Complexitate computațională

Metoda lui Cramer necesită calculul determinanților dimensionali . Atunci când se folosește metoda Gauss pentru calcularea determinanților, metoda are complexitate în operațiile elementare de adunare-înmulțire a ordinului , ceea ce este mai dificil decât metoda Gauss când se rezolvă sistemul direct. Prin urmare, metoda, din punct de vedere al timpului alocat calculelor, a fost considerată nepractică. Totuși, în 2010 s- a demonstrat că metoda lui Cramer poate fi implementată cu o complexitate comparabilă cu cea a metodei Gauss [2] . $n+1$ $n\ ori n$ $O(n^{4})$ $O(n^{3})$

Literatură

Maltsev I. A. Fundamentele algebrei liniare. - Ed. a 3-a, revăzută, M .: „Nauka”, 1970. - 400 p.

Note

↑ Cramer, Gabriel. Introduction à l'Analyse des lignes Courbes algébriques (franceză) 656–659. Geneva: Europeana (1750). Preluat: 18 mai 2012.
↑ Ken Habgood și Itamar Arel. 2010. Revizuirea regulii lui Cramer pentru rezolvarea sistemelor liniare dense. În Proceedings of the Spring Simulation Multiconference 2010 (SpringSim '10)

Vezi și

metoda Gauss

Metode de rezolvare a SLAE
Metode directe	Metoda matricei metoda Gauss Metoda Gauss-Iordan Metoda Cramer descompunerea LU Descompunerea Cholesky Metoda de măturare
Metode iterative	metoda Jacobi Metoda Gauss-Seidel Metoda de iterație Metoda de relaxare Metoda gradientului conjugat Metoda gradientului biconjugat Metoda gradientului biconjugat stabilizat
General	matrice inversă Metode de proiecție pentru rezolvarea SLAE Precondiționare