Τμήμα Μαθηματικών

Πληροφορική Ι

Εβδομάδα 8 · Πίνακες και Γραμμική Παλινδρόμηση

(Οδηγίες χρήσης του διαδραστικού κώδικα: δείτε την αρχική σελίδα.)

1 Πίνακες (Matrices)

1.1 Αναπαράσταση πινάκων ως λίστες λιστών

Θυμηθείτε τις δισδιάστατες λίστες (Εβδομάδα 4): μια λίστα με στοιχεία που είναι κι αυτά λίστες. Αυτή είναι η φυσική αναπαράσταση ενός πίνακα (matrix) στην Python — χωρίς κανένα εξωτερικό module.

Κάθε εσωτερική λίστα είναι μία γραμμή· η θέση της στην εξωτερική λίστα είναι ο αριθμός της γραμμής.

Συνηθισμένη παγίδα: [[0]*cols]*rows

Πολύ συχνά χρειαζόμαστε έναν “μηδενικό” πίνακα \(r \times c\) ως αφετηρία. Ο πιο φυσικός τρόπος να τον φτιάξουμε είναι μια λίστα με κατανόηση (list comprehension, Εβδομάδα 4), μία λίστα-γραμμή για κάθε γραμμή:

Υπάρχει και ένας δελεαστικά σύντομος αλλά λανθασμένος τρόπος: [[0]*cols]*rows, με τον τελεστή επανάληψης * (Εβδομάδα 4).

Το πρόβλημα: το *rows δεν αντιγράφει την εσωτερική λίστα — φτιάχνει rows αναφορές (Εβδομάδα 1) στην ίδια ακριβώς λίστα.

Η λίστα με κατανόηση ([[0]*cols for _ in range(rows)]) αποφεύγει την παγίδα ακριβώς επειδή η έκφραση [0]*cols επανεκτελείται σε κάθε επανάληψη, φτιάχνοντας κάθε φορά μια ολοκαίνουργια εσωτερική λίστα.

1.2 Πρόσθεση πινάκων

Δύο πίνακες ίδιων διαστάσεων προστίθενται στοιχείο προς στοιχείο:

1.3 Πολλαπλασιασμός πινάκων

Ο πολλαπλασιασμός ενός πίνακα με αριθμό (scalar) πολλαπλασιάζει κάθε στοιχείο ξεχωριστά:

Ο πολλαπλασιασμός δύο πινάκων \(A \cdot B\) είναι πιο περίπλοκος: απαιτεί το πλήθος στηλών του \(A\) να ισούται με το πλήθος γραμμών του \(B\), και κάθε στοιχείο \((i,j)\) του αποτελέσματος είναι το εσωτερικό γινόμενο της γραμμής \(i\) του \(A\) με τη στήλη \(j\) του \(B\):

\[ (A \cdot B)_{ij} = \sum_{k} A_{ik} \, B_{kj}. \]

Δηλαδή το στοιχείο \((i,j)\) του αποτελέσματος «συνδυάζει» τη γραμμή \(i\) του \(A\) με τη στήλη \(j\) του \(B\):

flowchart LR
    Ai["γραμμή i του A<br>[A_i0, A_i1, A_i2]"] --> P(("Σ A_ik · B_kj"))
    Bj["στήλη j του B<br>[B_0j, B_1j, B_2j]"] --> P
    P --> C["(A·B)_ij"]

Χρειαζόμαστε επομένως τρεις ένθετους βρόχους for: δύο για να διατρέξουμε κάθε θέση \((i,j)\) του αποτελέσματος, κι έναν τρίτο για το άθροισμα του εσωτερικού γινομένου:

Σημαντικό

Ο πολλαπλασιασμός πινάκων δεν είναι αντιμεταθετικός: γενικά \(A \cdot B \neq B \cdot A\) (δοκιμάστε mat_mul(B, A) παραπάνω και συγκρίνετε).

1.4 Ανάστροφος πίνακας (transpose)

Ο ανάστροφος \(A^T\) ενός πίνακα προκύπτει αντικαθιστώντας γραμμές με στήλες: η γραμμή \(i\) του \(A\) γίνεται η στήλη \(i\) του \(A^T\).

1.5 Ορίζουσα (determinant)

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

  • αν ο πίνακας είναι αντιστρέψιμος (ορίζουσα \(\neq 0\))·
  • πόσο «τεντώνει» ή «συρρικνώνει» τους όγκους ο αντίστοιχος γραμμικός μετασχηματισμός.

Για πίνακα \(2\times2\):

\[ \det\begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad - bc. \]

Για πίνακα \(3\times3\) υπάρχει ένας αντίστοιχος (πιο μακρύς) τύπος, ο κανόνας του Sarrus:

\[ \det\begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix} = a(ei - fh) - b(di - fg) + c(dh - eg). \]

Για μεγαλύτερους πίνακες (\(n \ge 4\)) ο τύπος της ορίζουσας γενικεύεται με αναδρομική ανάπτυξη κατά γραμμή/στήλη (cofactor expansion) — μια φυσική εφαρμογή της αναδρομής, που θα μελετήσουμε αναλυτικά την επόμενη εβδομάδα.

1.6 Γραμμικά Συστήματα και η Μέθοδος Απαλοιφής του Gauss

Ένα γραμμικό σύστημα \(n\) εξισώσεων με \(n\) αγνώστους γράφεται συνοπτικά ως \(A\vec{x} = \vec{b}\), όπου \(A\) είναι ο πίνακας των συντελεστών. Η μέθοδος απαλοιφής του Gauss το λύνει σε δύο φάσεις:

  1. Ευθεία απαλοιφή (forward elimination): με κάθε γραμμή (το οδηγό στοιχείο, pivot) μηδενίζουμε τα στοιχεία της ίδιας στήλης σε όλες τις γραμμές από κάτω, αφαιρώντας ένα κατάλληλο πολλαπλάσιό της. Ο πίνακας καταλήγει άνω τριγωνικός.
  2. Αντικατάσταση προς τα πίσω (back substitution): η τελευταία εξίσωση έχει πλέον έναν άγνωστο· τη λύνουμε και αντικαθιστούμε διαδοχικά προς τα πάνω.

Δουλεύουμε πάνω στον επαυξημένο πίνακα \([A \mid \vec{b}]\) (τον πίνακα \(A\) με μια επιπλέον στήλη, το \(\vec{b}\)), ώστε κάθε πράξη γραμμής να ενημερώνει ταυτόχρονα και τα δύο μέλη της εξίσωσης:

Επαληθεύστε ότι η λύση είναι \(x=2, y=3, z=-1\): αντικαταστήστε τις τιμές στις τρεις αρχικές εξισώσεις και ελέγξτε ότι ικανοποιούνται. Δοκιμάστε το δικό σας σύστημα, αλλάζοντας τους πίνακες A και b — αρκεί το σύστημα να έχει ακριβώς μία λύση (δηλαδή \(\det(A) \neq 0\)).

Ας δούμε τον επαυξημένο πίνακα να γίνεται άνω τριγωνικός, βήμα-βήμα:

Τώρα η τελευταία γραμμή δίνει κατευθείαν το z, η προτελευταία το y (με αντικατάσταση του z), κ.ο.κ. — αυτή είναι η αντικατάσταση προς τα πίσω.

2 Γραμμική Παλινδρόμηση (Linear Regression)

2.1 Από γραμμικά συστήματα σε “καλύτερο δυνατό” ταίριασμα

Το gauss_solve παραπάνω λύνει συστήματα με ακριβώς μία λύση. Στην πράξη όμως συχνά έχουμε περισσότερες εξισώσεις (σημεία δεδομένων) από αγνώστους — π.χ. \(100\) μετρήσεις \((x_i, y_i)\) που θέλουμε να προσεγγίσουμε με μία ευθεία \(y = mx + b\) (μόνο \(2\) άγνωστοι). Δεν υπάρχει, γενικά, ευθεία που να περνάει ακριβώς από όλα τα σημεία· αναζητούμε αντ’ αυτού την ευθεία που ελαχιστοποιεί το άθροισμα των τετραγώνων των κατακόρυφων αποστάσεων (μέθοδος ελαχίστων τετραγώνων, least squares):

\[ \min_{m,b} \sum_{i=1}^{n} \big(y_i - (mx_i + b)\big)^2. \]

Αν οργανώσουμε τα δεδομένα σε έναν πίνακα σχεδιασμού (design matrix) \(X\), όπου η γραμμή \(i\) είναι \([1, x_i]\) (ή \([1, x_i, x_i^2, \ldots]\) για πολυωνυμική προσαρμογή μεγαλύτερου βαθμού), οι βέλτιστοι συντελεστές \(\vec{\beta}\) ικανοποιούν τις κανονικές εξισώσεις (normal equations):

\[ (X^T X)\, \vec{\beta} = X^T \vec{y}. \]

Αυτό είναι, πάλι, ένα τετραγωνικό γραμμικό σύστημα — το ίδιο πρόβλημα που λύνει ήδη η gauss_solve! Ας προσαρμόσουμε μια παραβολή (\(y = a + bx + cx^2\)) σε θορυβώδη δεδομένα, χρησιμοποιώντας την ίδια συνάρτηση gauss_solve που ορίσαμε παραπάνω, χωρίς καμία αλλαγή:

Ένα γράφημα το κάνει προφανές — τα θορυβώδη σημεία, η προσαρμοσμένη καμπύλη, και η «πραγματική» καμπύλη από την οποία παρήχθησαν (γράφημα με το matplotlib):

Δεν χρειάστηκε να γράψουμε κανέναν καινούριο αλγόριθμο επίλυσης — μόνο να φτιάξουμε τον σωστό πίνακα \(X\). Το ίδιο ακριβώς πρόγραμμα προσαρμόζει ευθεία, παραβολή, ή πολυώνυμο οποιουδήποτε βαθμού, αρκεί να προσθέσουμε τις αντίστοιχες στήλες \(x^k\) στον πίνακα σχεδιασμού.

2.2 Ίδια στατιστικά, διαφορετικά δεδομένα: το κουαρτέτο του Anscombe

Μόλις προσαρμόσαμε μια καμπύλη και ελέγξαμε στο γράφημα αν ταιριάζει. Είναι δελεαστικό να παραλείψουμε αυτό το βήμα και να εμπιστευτούμε μόνο τους αριθμούς — τον συντελεστή συσχέτισης, την κλίση της ευθείας. Μη το κάνετε.

Το 1973, ο στατιστικός Frank Anscombe κατασκεύασε τέσσερα σύνολα σημείων \((x, y)\) που έχουν — μέχρι δύο δεκαδικά — τον ίδιο μέσο όρο, την ίδια διασπορά, την ίδια συσχέτιση, και την ίδια ευθεία ελαχίστων τετραγώνων:

Οι τέσσερις γραμμές είναι σχεδόν ταυτόσημες. Και όμως:

Τα ίδια νούμερα, τέσσερις εντελώς διαφορετικές ιστορίες:

  • I — μια πραγματική, θορυβώδης γραμμική σχέση· η ευθεία ταιριάζει.
  • II — τα σημεία σχηματίζουν καμπύλη (παραβολή). Η ευθεία είναι λάθος μοντέλο.
  • III — τέλεια ευθεία, εκτός από ένα ακραίο σημείο (outlier) που τραβάει την προσαρμογή.
  • IV — όλα τα \(x\) ίδια, εκτός από ένα· εκείνο το μοναδικό σημείο δημιουργεί μόνο του τη «συσχέτιση».

Κανένας συνοπτικός αριθμός δεν σας λέει σε ποια περίπτωση βρίσκεστε — μόνο το γράφημα. Μια σύγχρονη, ακόμα πιο εντυπωσιακή εκδοχή είναι το Datasaurus Dozen: δώδεκα σύνολα με πανομοιότυπα στατιστικά, το ένα από τα οποία, σχεδιασμένο, είναι κυριολεκτικά ένας δεινόσαυρος.

3 Σύνοψη

Σε αυτή την εβδομάδα είδαμε:

  • Πίνακες ως λίστες λιστών, και βασικές πράξεις πάνω τους: πρόσθεση, πολλαπλασιασμό (με αριθμό και μεταξύ πινάκων), ανάστροφο, ορίζουσα.
  • Τον αλγόριθμο απαλοιφής του Gauss: ευθεία απαλοιφή + αντικατάσταση προς τα πίσω, για την επίλυση γραμμικών συστημάτων.
  • Μια τεχνική αναγωγής ενός προβλήματος σε άλλο ήδη γνωστό: η προσαρμογή δεδομένων σε καμπύλη ανάγεται σε ένα ακόμα γραμμικό σύστημα, λυμένο με τον ίδιο, αναλλοίωτο κώδικα (gauss_solve) που ήδη είχαμε.
  • Το κουαρτέτο του Anscombe: τέσσερα σύνολα δεδομένων με ταυτόσημα στατιστικά αλλά εντελώς διαφορετική μορφή — γιατί πάντα σχεδιάζουμε τα δεδομένα πριν τα εμπιστευτούμε.

⤺ Πίσω στην αρχική σελίδα / πρόγραμμα μαθήματος  ·  Διαφάνειες αυτής της εβδομάδας