Κανόνας του Κράμερ

Στην γραμμική άλγεβρα, ο κανόνας του Κράμερ είναι θεώρημα που δίνει τη λύση σε ένα σύστημα γραμμικών εξισώσεων με αριθμό αγνώστων ίσο με το πλήθος των εξισώσεων. Το σύστημα γράφεται με τη μορφή πινάκων και λύνεται με τη βοήθεια ορίζουσων.

Ο κανόνας παίρνει το όνομα του από τον Ελβετό μαθηματικό Γκαμπριέλ Κράμερ (1704-1752), ο οποίος διατύπωσε αυτόν τον κανόνα το 1750 στo βιβλίο του Ιntroduction á l’analyse des lignes courbes algébriques. Εντούτοις, ο κανόνας αυτός είχε εκδοθεί πρωτύτερα το 1748 από τον Κόλιν Μακλόριν στο βιβλίο του Treatise of Algebra και πιστεύεται ότι ο Μακλόριν γνώριζε για τη μέθοδο αυτή από το 1729.

Περιγραφή

Το σύστημα n εξισώσεων με n αγνώστους, γενικής μορφής :

$\left\{{\begin{matrix}a_{1,1}x_{1}+a_{1,2}x_{2}+...+a_{1,n}x_{n}=\lambda _{1}\\a_{2,1}x_{1}+a_{2,2}x_{2}+...+a_{2,n}x_{n}=\lambda _{2}\\\vdots \\a_{n,1}x_{1}+a_{n,2}x_{2}+...+a_{n,n}x_{n}=\lambda _{n}\end{matrix}}\right.$

αναπαρίσταται με τη βοήθεια του πολλαπλασιασμού πινάκων ως εξής:

${\begin{pmatrix}a_{1,1}&a_{1,2}&\cdots &a_{1,n}\\a_{2,1}&a_{2,2}&\cdots &a_{2,n}\\\vdots &\vdots &\ddots &\vdots \\a_{n,1}&a_{n,2}&\cdots &a_{n,n}\\\end{pmatrix}}\times {\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\\\end{pmatrix}}={\begin{pmatrix}\lambda _{1}\\\lambda _{2}\\\vdots \\\lambda _{n}\\\end{pmatrix}}\Leftrightarrow A\cdot X=\Lambda$

όπου ο τετραγωνικός πίνακας $A$ περιέχει τους συντελεστές των αγνώστων, το διάνυσμα στήλης $X$ περιέχει αυτούς τους αγνώστους και το διάνυσμα στήλης $\Lambda$ περιέχει τα δεξιά μέλη των εξισώσεων του συστήματος. Oι συντελεστές και οι άγνωστοι είναι μέρος του ίδιου αντιμεταθετικού πεδίου.

Το θεώρημα δηλώνει τότε ότι το σύστημα έχει μοναδική λύση αν και μόνο αν ο πίνακας $A$ είναι αντιστρέψιμος (δηλαδή, με μη μηδενική ορίζουσα), και αυτή η λύση δίνεται τότε από :

$x_{k}={\det(A_{k}) \over \det(A)}$

όπου $A_{k}$ είναι ο τετραγωνικός πίνακας που σχηματίζεται με την αντικατάσταση της k-οστής στήλης του $A$ με το διάνυσμα στήλης $\Lambda$.

$A_{k}=(a_{k|i,j}){\text{ με }}a_{k|i,j}=\left\{{\begin{matrix}a_{i,j}&{\text{αν }}j\neq k\\\lambda _{i}&{\text{αν }}j=k\end{matrix}}\right.$

Ένα τετραγωνικό σύστημα (δηλαδή με τόσες εξισώσεις όσοι και οι άγνωστοι) ονομάζεται Κράμερ αν η ορίζουσα του πίνακα του είναι διάφορη του μηδενός.

Όταν το σύστημα (πάντα τετράγωνο) δεν είναι Κράμερ (δηλαδή όταν η ορίζουσα του Α είναι μηδέν):

• αν η ορίζουσα κάποιου από τους πίνακες $A_{k}$ είναι διάφορη του μηδενός, τότε το σύστημα δεν έχει λύση,
• το αντίστροφο δεν ισχύει: μπορεί να συμβεί το σύστημα να μην έχει λύση ακόμη και αν οι ορίζουσες $\det(A_{k})$ είναι όλοι μηδέν. Ένα τέτοιο παράδειγμα δίνεται στο εξής σύστημα:

$\left\{{\begin{matrix}x+y+z=1\\x+y+z=2\\x+y+z=3\end{matrix}}\right.$

Για περισσότερες λεπτομέρειες, δες το θεώρημα Rouché–Capelli.

Υπολογιστική πολυπλοκότητα

Ο κανόνας του Κράμερ χρειάζεται $n+1$ υπολογισμούς οριζουσών για $n$ εξισώσεις με $n$ αγνώστους. Δεν συμφέρει να χρησιμοποιήσουμε την απαλοιφή Γκάους για τον υπολογισμό της ορίζουσας, καθώς ένας υπολογισμός της απαλοιφής Γκάους είναι ήδη αρκετός για να λύσει το σύστημα. Ωστόσο, υπάρχουν πιο αποδοτικές υλοποιήσεις που κανόνα του Κράμερ που απαιτούν (ασυμπτωτικά) τον ίδιο αριθμό πράξεων με την απαλοιφή Γκάους.

Παραδείγματα

Γεωμετρική ερμηνεία του κανόνα του Κράμερ. Τα εμβαδά του δεύτερου και του τρίτου παραλληλογράμμου είναι ίσα, ενώ το εμβαδόν του δεύτερου είναι $x_{1}$ φορές το εμβαδόν του πρώτου. Ο κανόνας προκύπτει από αυτή την ισότητα.

Σύστημα τάξης 2

Αν $ad-bc\neq 0$, Το σύστημα

$\left\{{\begin{matrix}ax+by=e\\cx+dy=f\end{matrix}}\right.$

έχει μοναδική λύση :

$x={{\begin{vmatrix}e&b\\f&d\end{vmatrix}} \over {\begin{vmatrix}a&b\\c&d\end{vmatrix}}}={ed-bf \over ad-bc},\quad y={{\begin{vmatrix}a&e\\c&f\end{vmatrix}} \over {\begin{vmatrix}a&b\\c&d\end{vmatrix}}}={af-ec \over ad-bc}.$

Ενδεικτικό παράδειγμα:

$\left.{\begin{matrix}4x+2y=24\\2x+3y=16\end{matrix}}\right\}\Leftrightarrow \left\{{\begin{matrix}x={24\cdot 3-16\cdot 2 \over 8}={40 \over 8}=5\\y={4\cdot 16-2\cdot 24 \over 8}={16 \over 8}=2\end{matrix}}\right.$

Σύστημα τάξης 3

$\left\{{\begin{matrix}a_{1}x_{1}+b_{1}x_{2}+c_{1}x_{3}=d_{1}\\a_{2}x_{1}+b_{2}x_{2}+c_{2}x_{3}=d_{2}\\a_{3}x_{1}+b_{3}x_{2}+c_{3}x_{3}=d_{3}\end{matrix}}\right.$

Ας υποθέσουμε ότι :

$A={\begin{pmatrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{pmatrix}},\quad X={\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}\quad {\text{και}}\quad \Lambda ={\begin{pmatrix}d_{1}\\d_{2}\\d_{3}\end{pmatrix}}.$

Το σύστημα έχει μοναδική λύση εάν και μόνο εάν $\det(A)\neq 0$ :

$x_{1}={\frac {\det(A_{1})}{\det(A)}}={\frac {\begin{vmatrix}d_{1}&b_{1}&c_{1}\\d_{2}&b_{2}&c_{2}\\d_{3}&b_{3}&c_{3}\end{vmatrix}}{\det(A)}}$

$x_{2}={\frac {\det(A_{2})}{\det(A)}}={\frac {\begin{vmatrix}a_{1}&d_{1}&c_{1}\\a_{2}&d_{2}&c_{2}\\a_{3}&d_{3}&c_{3}\end{vmatrix}}{\det(A)}}$

$x_{3}={\frac {\det(A_{3})}{\det(A)}}={\frac {\begin{vmatrix}a_{1}&b_{1}&d_{1}\\a_{2}&b_{2}&d_{2}\\a_{3}&b_{3}&d_{3}\end{vmatrix}}{\det(A)}}$

Ή απλούστερα :

$X={\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}={\frac {1}{\det(A)}}\cdot {\begin{pmatrix}\det(A_{1})\\\det(A_{2})\\\det(A_{3})\end{pmatrix}}.$

Περίπτωση μηδενικής ορίζουσας

Για να μην έχει λύση το σύστημα, "αρκεί"

$\det(A)=0\quad {\text{και}}\quad {\Big (}\det(A_{1})\neq 0\quad {\text{ή}}\quad \det(A_{2})\neq 0\quad {\text{ή}}\quad \det(A_{3})\neq 0{\Big )}$.

Αυτό σημαίνει ότι οι 3 γραμμές του συστήματος είναι γραμμικά εξαρτημένες όταν εξετάζεται μόνο το αριστερό μέλος, αλλά δεν είναι εξακολουθούν να είναι όταν συμπεριλαμβάνεται και το δεξί μέλος. Επομένως, δεν μπορεί να υπάρξει λύση.

Στην περίπτωση

$\det(A)=\det(A_{1})=\det(A_{2})=\det(A_{3})=0\,$

μπορούμε να έχουμε είτε έναν άπειρο αριθμό λύσεων, είτε καμία απολύτως:

Όπως σημειώθηκε παραπάνω, $\det(A)=0$ σημαίνει ότι οι γραμμές των συντελεστών του συστήματος είναι γραμμικά εξαρτημένες, ενώ η μία είναι γραμμικός συνδυασμός των άλλων. Σε αυτή την περίπτωση, πρέπει να εξάγουμε ένα σύστημα Κράμερ, επιλέγοντας $r=\mathrm {rank} (A)$ κύριους αγνώστους και $r$ εξισώσεις που δίνουν ένα σύστημα Κράμερ όταν βάλουμε τους μη κύριους αγνώστους στο δεξιό μέλος, και επομένως μια "μοναδική" λύση που εκφράζει τους κύριους αγνώστους ως προς τους άλλους αγνώστους που παραμένουν ελεύθερες παράμετροι. (Αυτό αντιστοιχεί σε έναν αφινικό υποχώρο διάστασης $n-r$.) Τέλος, ελέγχουμε αν οι πρόσθετες εξισώσεις ικανοποιούνται για τη λύση που προκύπτει με αυτόν τον τρόπο.

Εξωτερικοί σύνδεσμοι

• MIT Linear Algebra Lecture on Cramer’s Rule at Google Video, from MIT OpenCourseWare