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

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

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

Περιγραφή

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

${\displaystyle \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.}$

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

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

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

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

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

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

${\displaystyle 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.}$

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

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

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

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

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

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

Ο κανόνας του Κράμερ χρειάζεται ${\displaystyle n+1}$ υπολογισμούς οριζουσών για ${\displaystyle n}$ εξισώσεις με ${\displaystyle n}$ αγνώστους. Δεν συμφέρει να χρησιμοποιήσουμε την απαλοιφή Γκάους για τον υπολογισμό της ορίζουσας, καθώς ένας υπολογισμός της απαλοιφής Γκάους είναι ήδη αρκετός για να λύσει το σύστημα.^[5][6] Ωστόσο, υπάρχουν πιο αποδοτικές υλοποιήσεις που κανόνα του Κράμερ που απαιτούν (ασυμπτωτικά) τον ίδιο αριθμό πράξεων με την απαλοιφή Γκάους.^[7][8]

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

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

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

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

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

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

${\displaystyle 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}.}$

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

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

${\displaystyle \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.}$

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

${\displaystyle 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}}.}$

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

${\displaystyle 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)}}}$

${\displaystyle 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)}}}$

${\displaystyle 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)}}}$

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

${\displaystyle 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}}.}$

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

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

${\displaystyle \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 γραμμές του συστήματος είναι γραμμικά εξαρτημένες όταν εξετάζεται μόνο το αριστερό μέλος, αλλά δεν είναι εξακολουθούν να είναι όταν συμπεριλαμβάνεται και το δεξί μέλος. Επομένως, δεν μπορεί να υπάρξει λύση.

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

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

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

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

Παραπομπές

1. Cramer, Gabriel (1750). Introduction à l'analyse des lignes courbes algébriques (στα Γαλλικά). Genève: Chez les Frères Cramer & Cl. Philibert. 
2. MacLaurin, Colin (1748). A Treatise of Algebra, in Three Parts: Containing I. The Fundamental Rules and Operations. II. The Composition and Resolution of Equations of All Degrees; and the Different Affections of Their Roots. III. The Application of Algebra and Geometry to Each Other : to which is Added, an Appendix, Concerning the General Properties of Geometrical Lines. A. Millar, and J. Nourse. 
3. Carl B. Boyer (1968). A History of Mathematics (2η έκδοση). Wiley. σελ. 431. 
4. «Fontene Georges». serge.mehl.free.fr. Ανακτήθηκε στις 22 Ιανουαρίου 2024. 
5. Joe D. Hoffman· Steven Frankel (2001). Numerical Methods for Engineers and Scientists, Second Edition. CRC Press. σελ. 30. ISBN 978-0-8247-0443-8. 
6. Thomas S. Shores (2007). Applied Linear Algebra and Matrix Analysis. Springer Science & Business Media. σελ. 132. ISBN 978-0-387-48947-6. 
7. Ken Habgood; Itamar Arel (2012). «A condensation-based application of Cramerʼs rule for solving large-scale linear systems». Journal of Discrete Algorithms 10: 98–109. doi:10.1016/j.jda.2011.06.007. https://hal.archives-ouvertes.fr/hal-01500199/document. 
8. G.I.Malaschonok (1983). «Solution of a System of Linear Equations in an Integral Ring». USSR J. Of Comput. Math. And Math. Phys. 23: 1497–1500. 

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

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