Cramer metode

Cramers metode ( Cramers regel) er en metode til at løse systemer af lineære algebraiske ligninger med antallet af ligninger lig med antallet af ukendte med en hoveddeterminant ikke-nul for koefficientmatrixen for systemet (for sådanne ligninger er løsningen desuden eksisterer og er unik). [en]

Beskrivelse af metoden

For et system af lineære ligninger med ukendte (over et vilkårligt felt ) $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 af systemmatricen , som er forskellig fra nul, skrives løsningen på 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 kolonne i systemmatricen er erstattet af en kolonne af frie medlemmer).
I en anden form er Cramers regel formuleret som følger: for alle koefficienter c 1 , c 2 , ..., c n er ligheden sand:

(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 denne form er Cramers metode gyldig uden den antagelse, at den er forskellig fra nul, det er ikke engang nødvendigt, at systemets koefficienter er elementer i en integralring (systemets determinant kan endda være en nuldivisor i ringen af koefficienter). Vi kan også antage, at enten sættene og , eller sættet ikke består af elementer af systemets koefficientring, men af et eller andet modul over denne ring. I denne form bruges Cramers formel for eksempel til at bevise formlen for Grams determinant og Nakayamas Lemma . $\Delta$ $b_{1},b_{2},...,b_{n}$ $x_{1},x_{2},...,x_{n}$ $c_{1},c_{2},...,c_{n}$

Eksempel

System af lineære ligninger med reelle 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{cases}}

Kvalifikationer:

{\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 determinanterne er kolonnen med koefficienter for den tilsvarende ukendte erstattet af kolonnen med frie termer i systemet.

Løsning:

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

Eksempel:

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

Kvalifikationer:

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

Beregningsmæssig kompleksitet

Cramers metode kræver beregning af dimensionelle determinanter . Når man bruger Gauss-metoden til at beregne determinanterne, har metoden kompleksitet i elementære operationer med addition-multiplikation af ordenen , hvilket er vanskeligere end Gauss-metoden, når man løser systemet direkte. Derfor blev metoden, set ud fra et tidsforbrug på beregninger, anset for upraktisk. I 2010 blev det dog vist, at Cramers metode kan implementeres med en kompleksitet, der kan sammenlignes med Gauss-metodens [2] . $n+1$ $n\ gange n$ $O(n^{4})$ $O(n^{3})$

Litteratur

Maltsev I. A. Grundlæggende om lineær algebra. - Ed. 3., revideret, M .: "Nauka", 1970. - 400 s.

Noter

↑ Cramer, Gabriel. Introduktion à l'Analyse des lignes Courbes algébriques (fransk) 656–659. Genève: Europeana (1750). Hentet: 18. maj 2012.
↑ Ken Habgood og Itamar Arel. 2010. Gensyn med Cramers regel for løsning af tætte lineære systemer. I forbindelse med 2010 Spring Simulation Multiconference (SpringSim '10)

Se også

Gauss metode

Metoder til løsning af SLAE
Direkte metoder	Matrix metode Gauss metode Gauss-Jordan metode Cramer metode LU nedbrydning Kolesky nedbrydning Feje metode
Iterative metoder	Jacobi metode Gauss-Seidel metode Iterationsmetode Afslapningsmetode Konjugeret gradientmetode Bikonjugeret gradientmetode Stabiliseret bikonjugat gradientmetode
Generel	omvendt matrix Projektionsmetoder til løsning af SLAE Forkonditionering