Κανόνας του Κράμερ: Διαφορά μεταξύ των αναθεωρήσεων
μ Προσδιοριστής -> ορίζουσα, Παράγραφος για την υπολογιστική πολυπλοκότητα της υλοποίησης του |
|||
Γραμμή 1: | Γραμμή 1: | ||
Στην [[γραμμική άλγεβρα]], ο '''κανόνας του Κράμερ''' είναι [[θεώρημα]] που δίνει τη λύση σε ένα [[σύστημα γραμμικών εξισώσεων]] με αριθμό αγνώστων ίσο με το πλήθος των εξισώσεων. Το σύστημα γράφεται με τη μορφή [[πίνακας (μαθηματικά)|πινάκων]] και λύνεται με τη βοήθεια [[ορίζουσα|ορίζουσων]]. |
|||
Ο κανόνας παίρνει το όνομα του από τον [[Ελβετία|Ελβετό]] μαθηματικό [[Γκαμπριέλ Κράμερ]] (1704-1752), ο οποίος διατύπωσε αυτόν τον κανόνα το [[1750]] στo βιβλίο του {{lang|fr|''Ιntroduction á l’analyse des lignes courbes algébriques''}}.<ref>{{cite book |url=https://archive.org/details/bub_gb_gtKvSzJPOOAC |title=Introduction à l'analyse des lignes courbes algébriques |author=Cramer, Gabriel |publisher=Chez les Frères Cramer & Cl. Philibert |location=Genève |year=1750 |language=fr}}</ref> Εντούτοις, ο κανόνας αυτός είχε εκδοθεί πρωτύτερα το [[1748]] από τον [[Κόλιν Μακλόριν]] στο βιβλίο του ''Treatise of Algebra''<ref>{{Cite book|title=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|first=Colin|last=MacLaurin|publisher=A. Millar, and J. Nourse|date=1748|url=https://books.google.gr/books?id=BIrWrEEin5YC&printsec=frontcover&dq=Treatise+of+Algebra&hl=el&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwjFv7yn8vGDAxW3PhAIHSwiDrAQ6AF6BAgIEAI#v=onepage&q=Treatise%20of%20Algebra&f=false}}</ref> και πιστεύεται ότι ο Μακλόριν γνώριζε για τη μέθοδο αυτή από το [[1729]].<ref>{{cite book |author=Carl B. Boyer |title=A History of Mathematics |edition=2η |publisher=Wiley |year=1968 |page=431 }}</ref> |
|||
==Περιγραφή== |
==Περιγραφή== |
||
Γραμμή 9: | Γραμμή 11: | ||
a_{n,1}x_{1}+a_{n,2}x_{2}+...+a_{n,n}x_n = \lambda_n |
a_{n,1}x_{1}+a_{n,2}x_{2}+...+a_{n,n}x_n = \lambda_n |
||
\end{matrix}\right.</math> |
\end{matrix}\right.</math> |
||
αναπαρίσταται |
αναπαρίσταται με τη βοήθεια του [[Πολλαπλασιασμός πινάκων|πολλαπλασιασμού πινάκων]] ως εξής: |
||
:<math>\begin{pmatrix} |
:<math>\begin{pmatrix} |
||
a_{1,1} & a_{1,2} & \cdots & a_{1,n}\\ |
a_{1,1} & a_{1,2} & \cdots & a_{1,n}\\ |
||
Γραμμή 28: | Γραμμή 30: | ||
\end{pmatrix} \Leftrightarrow A \cdot X=\Lambda</math> |
\end{pmatrix} \Leftrightarrow A \cdot X=\Lambda</math> |
||
όπου ο τετραγωνικός πίνακας <math>A</math> περιέχει τους συντελεστές των αγνώστων, το διάνυσμα στήλης <math>X</math> περιέχει αυτούς τους αγνώστους και το διάνυσμα στήλης <math>\Lambda</math> περιέχει τα δεξιά μέλη των εξισώσεων του συστήματος |
όπου ο [[τετραγωνικός πίνακας]] <math>A</math> περιέχει τους συντελεστές των αγνώστων, το διάνυσμα στήλης <math>X</math> περιέχει αυτούς τους αγνώστους και το διάνυσμα στήλης <math>\Lambda</math> περιέχει τα δεξιά μέλη των εξισώσεων του συστήματος. Oι συντελεστές και οι άγνωστοι είναι μέρος του ίδιου [[Αντιμεταθετική ιδιότητα|αντιμεταθετικού]] [[Σώμα (άλγεβρα)|πεδίου]]. |
||
Το θεώρημα δηλώνει τότε ότι το σύστημα έχει μοναδική λύση αν και μόνο αν ο πίνακας <math>A</math> είναι αντιστρέψιμος (μη |
Το θεώρημα δηλώνει τότε ότι το σύστημα έχει μοναδική λύση αν και μόνο αν ο πίνακας <math>A</math> είναι [[αντιστρέψιμος πίνακας|αντιστρέψιμος]] (δηλαδή, με μη μηδενική ορίζουσα), και αυτή η λύση δίνεται τότε από : |
||
:<math>x_k = { \det(A_k) \over \det(A) }</math> |
:<math>x_k = { \det(A_k) \over \det(A) }</math> |
||
Γραμμή 36: | Γραμμή 38: | ||
όπου <math>A_k</math> είναι ο τετραγωνικός πίνακας που σχηματίζεται με την αντικατάσταση της ''k''-οστής στήλης του <math>A</math> με το διάνυσμα στήλης |
όπου <math>A_k</math> είναι ο τετραγωνικός πίνακας που σχηματίζεται με την αντικατάσταση της ''k''-οστής στήλης του <math>A</math> με το διάνυσμα στήλης |
||
<math>\Lambda</math>. |
<math>\Lambda</math>. |
||
:<math>A_k = ( a_{k|i,j} ) \ |
:<math>A_k = ( a_{k|i,j} ) \text{ με } a_{k|i,j} = \left\{\begin{matrix} a_{i,j} & \text{αν } j \ne k \\ \lambda_{i} & \text{αν }j = k\end{matrix}\right.</math> |
||
Ένα τετραγωνικό σύστημα (δηλαδή με τόσες εξισώσεις όσοι και οι άγνωστοι) ονομάζεται Κράμερ αν |
Ένα τετραγωνικό σύστημα (δηλαδή με τόσες εξισώσεις όσοι και οι άγνωστοι) ονομάζεται Κράμερ αν η ορίζουσα του πίνακα του είναι διάφορη του μηδενός. |
||
Όταν το σύστημα (πάντα τετράγωνο) δεν είναι Κράμερ (δηλαδή όταν |
Όταν το σύστημα (πάντα τετράγωνο) δεν είναι Κράμερ (δηλαδή όταν η ορίζουσα του ''Α'' είναι μηδέν): |
||
* αν |
* αν η ορίζουσα κάποιου από τους πίνακες <math>A_k</math> είναι διάφορη του μηδενός, τότε το σύστημα δεν έχει λύση, |
||
* το αντίστροφο |
* το αντίστροφο δεν ισχύει: μπορεί να συμβεί το σύστημα να μην έχει λύση ακόμη και αν οι ορίζουσες <math>\det(A_k)</math> είναι όλοι μηδέν. Ένα τέτοιο παράδειγμα δίνεται στο εξής σύστημα: |
||
:<math>\left\{\begin{matrix}x+y+z=1\\ |
::<math>\left\{\begin{matrix}x+y+z=1\\ |
||
x+y+z=2\\ |
x+y+z=2\\ |
||
x+y+z=3\end{matrix}\right.</math> |
x+y+z=3\end{matrix}\right.</math> |
||
Για περισσότερες λεπτομέρειες, δες το |
Για περισσότερες λεπτομέρειες, δες το [[θεώρημα Rouché–Capelli]].<ref>{{Cite web|url=http://serge.mehl.free.fr/chrono/fontene.html|title=Fontene Georges|website=serge.mehl.free.fr|accessdate=2024-01-22}}</ref> |
||
== Υπολογιστική πολυπλοκότητα == |
|||
Ο αριθμός των πράξεων που απαιτούνται για την επίλυση ενός γραμμικού συστήματος με τον κανόνα του Κράμερ εξαρτάται από τη μέθοδο που χρησιμοποιείται για τον υπολογισμό του προσδιοριστή. |
|||
Ο κανόνας του Κράμερ χρειάζεται <math>n+1</math> υπολογισμούς οριζουσών για <math>n</math> εξισώσεις με <math>n</math> αγνώστους. Δεν συμφέρει να χρησιμοποιήσουμε την [[Γκαουσιανή απαλοιφή|απαλοιφή Γκάους]] για τον υπολογισμό της ορίζουσας, καθώς ένας υπολογισμός της απαλοιφής Γκάους είναι ήδη αρκετός για να λύσει το σύστημα.<ref name="HoffmanFrankel2001">{{cite book|author1=Joe D. Hoffman|author2=Steven Frankel|title=Numerical Methods for Engineers and Scientists, Second Edition|year=2001|publisher=CRC Press|isbn=978-0-8247-0443-8|page=30}}</ref><ref name="Shores2007">{{cite book|author=Thomas S. Shores|title=Applied Linear Algebra and Matrix Analysis|year=2007|publisher=Springer Science & Business Media|isbn=978-0-387-48947-6|page=132}}</ref> Ωστόσο, υπάρχουν πιο αποδοτικές υλοποιήσεις που κανόνα του Κράμερ που απαιτούν (ασυμπτωτικά) τον ίδιο αριθμό πράξεων με την απαλοιφή Γκάους.<ref>{{cite journal |author1=Ken Habgood |author2=Itamar Arel |title=A condensation-based application of Cramerʼs rule for solving large-scale linear systems |journal=Journal of Discrete Algorithms |volume=10 |year=2012 |pages=98–109 |doi=10.1016/j.jda.2011.06.007|url=https://hal.archives-ouvertes.fr/hal-01500199/document|doi-access=free }} </ref><ref>{{cite journal |author1=G.I.Malaschonok |title=Solution of a System of Linear Equations in an Integral Ring |journal=USSR J. Of Comput. Math. And Math. Phys. |volume=23 |year=1983 |pages=1497–1500|arxiv=1711.09452 }}</ref> |
|||
Μια αποτελεσματική μέθοδος για τον υπολογισμό του προσδιοριστή είναι η πολυωνυμικής πολυπλοκότητας απαλοιφή Γκάους-Ζορντάν. |
|||
Ωστόσο, ο κανόνας του Κράμερ θα απαιτήσει έναν αριθμό υπολογισμών του προσδιοριστικού παράγοντα ίσο με το μέγεθος του συστήματος, οπότε η απαλοιφή Γκάους-Ζόρνταν που εφαρμόζεται απευθείας στο σύστημα επιλύει το πρόβλημα πιο αποτελεσματικά. |
|||
== Παραδείγματα == |
== Παραδείγματα == |
||
Γραμμή 75: | Γραμμή 76: | ||
Ας υποθέσουμε ότι : |
Ας υποθέσουμε ότι : |
||
:<math>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{ |
:<math>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} |
\Lambda = \begin{pmatrix} |
||
d_1\\ |
d_1\\ |
||
Γραμμή 93: | Γραμμή 94: | ||
\det(A_3)\end{pmatrix}.</math> |
\det(A_3)\end{pmatrix}.</math> |
||
====Περίπτωση |
====Περίπτωση μηδενικής ορίζουσας==== |
||
Για να μην |
Για να μην έχει λύση το σύστημα, "αρκεί" |
||
:<math>\det(A) = 0\quad\text{ |
:<math>\det(A) = 0\quad\text{και}\quad\Big( \det(A_1) \ne 0\quad\text{ή}\quad\det(A_2) \ne 0\quad\text{ή}\quad\det(A_3) \ne 0 \Big)</math>. |
||
Αυτό σημαίνει ότι οι 3 γραμμές του συστήματος είναι γραμμικά εξαρτημένες όταν εξετάζεται μόνο το αριστερό μέλος, αλλά δεν είναι εξακολουθούν να είναι όταν συμπεριλαμβάνεται και το δεξί μέλος. Επομένως, δεν μπορεί να υπάρξει λύση. |
|||
Στην περίπτωση |
Στην περίπτωση |
||
:<math>\det(A) = \det(A_1) = \det(A_2) = \det(A_3) = 0\,</math> |
:<math>\det(A) = \det(A_1) = \det(A_2) = \det(A_3) = 0\,</math> |
||
μπορούμε να έχουμε είτε έναν άπειρο αριθμό λύσεων, είτε καμία απολύτως: |
μπορούμε να έχουμε είτε έναν άπειρο αριθμό λύσεων, είτε καμία απολύτως: |
||
Όπως σημειώθηκε παραπάνω, det( |
Όπως σημειώθηκε παραπάνω, <math>\det(A) = 0</math> σημαίνει ότι οι γραμμές των συντελεστών του συστήματος είναι γραμμικά εξαρτημένες, ενώ η μία είναι γραμμικός συνδυασμός των άλλων. Σε αυτή την περίπτωση, πρέπει να εξάγουμε ένα σύστημα Κράμερ, επιλέγοντας <math>r = \mathrm{rank}(A)</math> κύριους αγνώστους και <math>r</math> εξισώσεις που δίνουν ένα σύστημα Κράμερ όταν βάλουμε τους μη κύριους αγνώστους στο δεξιό μέλος, και επομένως μια "μοναδική" λύση που εκφράζει τους κύριους αγνώστους ως προς τους άλλους αγνώστους που παραμένουν ελεύθερες παράμετροι. (Αυτό αντιστοιχεί σε έναν [[αφινικός χώρος|αφινικό υποχώρο]] διάστασης <math>n - r</math>.) Τέλος, ελέγχουμε αν οι πρόσθετες εξισώσεις ικανοποιούνται για τη λύση που προκύπτει με αυτόν τον τρόπο. |
||
== Παραπομπές == |
== Παραπομπές == |
Έκδοση από την 12:11, 9 Φεβρουαρίου 2024
Στην γραμμική άλγεβρα, ο κανόνας του Κράμερ είναι θεώρημα που δίνει τη λύση σε ένα σύστημα γραμμικών εξισώσεων με αριθμό αγνώστων ίσο με το πλήθος των εξισώσεων. Το σύστημα γράφεται με τη μορφή πινάκων και λύνεται με τη βοήθεια ορίζουσων.
Ο κανόνας παίρνει το όνομα του από τον Ελβετό μαθηματικό Γκαμπριέλ Κράμερ (1704-1752), ο οποίος διατύπωσε αυτόν τον κανόνα το 1750 στo βιβλίο του Ιntroduction á l’analyse des lignes courbes algébriques.[1] Εντούτοις, ο κανόνας αυτός είχε εκδοθεί πρωτύτερα το 1748 από τον Κόλιν Μακλόριν στο βιβλίο του Treatise of Algebra[2] και πιστεύεται ότι ο Μακλόριν γνώριζε για τη μέθοδο αυτή από το 1729.[3]
Περιγραφή
Το σύστημα n εξισώσεων με n αγνώστους, γενικής μορφής :
αναπαρίσταται με τη βοήθεια του πολλαπλασιασμού πινάκων ως εξής:
όπου ο τετραγωνικός πίνακας περιέχει τους συντελεστές των αγνώστων, το διάνυσμα στήλης περιέχει αυτούς τους αγνώστους και το διάνυσμα στήλης περιέχει τα δεξιά μέλη των εξισώσεων του συστήματος. Oι συντελεστές και οι άγνωστοι είναι μέρος του ίδιου αντιμεταθετικού πεδίου.
Το θεώρημα δηλώνει τότε ότι το σύστημα έχει μοναδική λύση αν και μόνο αν ο πίνακας είναι αντιστρέψιμος (δηλαδή, με μη μηδενική ορίζουσα), και αυτή η λύση δίνεται τότε από :
όπου είναι ο τετραγωνικός πίνακας που σχηματίζεται με την αντικατάσταση της k-οστής στήλης του με το διάνυσμα στήλης .
Ένα τετραγωνικό σύστημα (δηλαδή με τόσες εξισώσεις όσοι και οι άγνωστοι) ονομάζεται Κράμερ αν η ορίζουσα του πίνακα του είναι διάφορη του μηδενός.
Όταν το σύστημα (πάντα τετράγωνο) δεν είναι Κράμερ (δηλαδή όταν η ορίζουσα του Α είναι μηδέν):
- αν η ορίζουσα κάποιου από τους πίνακες είναι διάφορη του μηδενός, τότε το σύστημα δεν έχει λύση,
- το αντίστροφο δεν ισχύει: μπορεί να συμβεί το σύστημα να μην έχει λύση ακόμη και αν οι ορίζουσες είναι όλοι μηδέν. Ένα τέτοιο παράδειγμα δίνεται στο εξής σύστημα:
Για περισσότερες λεπτομέρειες, δες το θεώρημα Rouché–Capelli.[4]
Υπολογιστική πολυπλοκότητα
Ο κανόνας του Κράμερ χρειάζεται υπολογισμούς οριζουσών για εξισώσεις με αγνώστους. Δεν συμφέρει να χρησιμοποιήσουμε την απαλοιφή Γκάους για τον υπολογισμό της ορίζουσας, καθώς ένας υπολογισμός της απαλοιφής Γκάους είναι ήδη αρκετός για να λύσει το σύστημα.[5][6] Ωστόσο, υπάρχουν πιο αποδοτικές υλοποιήσεις που κανόνα του Κράμερ που απαιτούν (ασυμπτωτικά) τον ίδιο αριθμό πράξεων με την απαλοιφή Γκάους.[7][8]
Παραδείγματα
Σύστημα τάξης 2
Αν , Το σύστημα
έχει μοναδική λύση :
Ενδεικτικό παράδειγμα:
Σύστημα τάξης 3
Ας υποθέσουμε ότι :
Το σύστημα έχει μοναδική λύση εάν και μόνο εάν :
Ή απλούστερα :
Περίπτωση μηδενικής ορίζουσας
Για να μην έχει λύση το σύστημα, "αρκεί"
- .
Αυτό σημαίνει ότι οι 3 γραμμές του συστήματος είναι γραμμικά εξαρτημένες όταν εξετάζεται μόνο το αριστερό μέλος, αλλά δεν είναι εξακολουθούν να είναι όταν συμπεριλαμβάνεται και το δεξί μέλος. Επομένως, δεν μπορεί να υπάρξει λύση.
Στην περίπτωση
μπορούμε να έχουμε είτε έναν άπειρο αριθμό λύσεων, είτε καμία απολύτως:
Όπως σημειώθηκε παραπάνω, σημαίνει ότι οι γραμμές των συντελεστών του συστήματος είναι γραμμικά εξαρτημένες, ενώ η μία είναι γραμμικός συνδυασμός των άλλων. Σε αυτή την περίπτωση, πρέπει να εξάγουμε ένα σύστημα Κράμερ, επιλέγοντας κύριους αγνώστους και εξισώσεις που δίνουν ένα σύστημα Κράμερ όταν βάλουμε τους μη κύριους αγνώστους στο δεξιό μέλος, και επομένως μια "μοναδική" λύση που εκφράζει τους κύριους αγνώστους ως προς τους άλλους αγνώστους που παραμένουν ελεύθερες παράμετροι. (Αυτό αντιστοιχεί σε έναν αφινικό υποχώρο διάστασης .) Τέλος, ελέγχουμε αν οι πρόσθετες εξισώσεις ικανοποιούνται για τη λύση που προκύπτει με αυτόν τον τρόπο.
Παραπομπές
- ↑ Cramer, Gabriel (1750). Introduction à l'analyse des lignes courbes algébriques (στα Γαλλικά). Genève: Chez les Frères Cramer & Cl. Philibert.
- ↑ 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.
- ↑ Carl B. Boyer (1968). A History of Mathematics (2η έκδοση). Wiley. σελ. 431.
- ↑ «Fontene Georges». serge.mehl.free.fr. Ανακτήθηκε στις 22 Ιανουαρίου 2024.
- ↑ Joe D. Hoffman· Steven Frankel (2001). Numerical Methods for Engineers and Scientists, Second Edition. CRC Press. σελ. 30. ISBN 978-0-8247-0443-8.
- ↑ Thomas S. Shores (2007). Applied Linear Algebra and Matrix Analysis. Springer Science & Business Media. σελ. 132. ISBN 978-0-387-48947-6.
- ↑ 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:. https://hal.archives-ouvertes.fr/hal-01500199/document.
- ↑ 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