Οδήγηση

Υπάρχει ένα προφανές πρόβλημα με τη διαδικασία απαλοιφής 480#480 όπως την έχουμε περιγράψει, όπως επίσης και άλλο ένα, κατά κάποιο τρόπο πιο σύνθετο, πρόβλημα. Η προφανής πιθανή δυσκολία είναι ότι η διαδικασία καταρρέει άν το οδηγό διαγώνιο στοιχείο του εναπομένοντος μη απλοποιημένου τμήματος του πίνακα είναι μηδέν σε οποιοδήποτε στάδιο της απαλοιφής, αφού ο υπολογισμός τον πολλαπλασιαστών 481#481 για μία δεδομένη στήλη απαιτεί διαίρεση με το διαγώνο στοιχείο αυτής της στήλης. Η λύση στο πρόβλημα αυτό είναι σχεδόν εξίσου προφανής: εάν το στοιχείο της διαγωνίου είναι μηδέν στο στάδιο 482#482 τότε εναλλάσσουμε τη γραμμή 432#432 του συστήματος με μία επόμενη γραμμή της οποίας το στοιχείο που έχει στην 432#432 στήλη είναι μη μηδενικό. Οπως γνωρίζουμε από το Παράδειγμα 2.2, μία τέτοια εναλλαγή δε μεταβάλλει τη λύση του συστήματος. Με ένα μη μηδενικό στοιχείο της διαγωνίου ως οδηγό, η διαδικασία μπορεί να συνεχιστεί ως συνήθως.

Αλλά τι συμβαίνει αν δεν υπάρχει κανένα μη μηδενικό στοιχείο στη διαγώνιο ή κάτω από αυτή στη στήλη 483#483 Τότε δεν υπάρχει κάτι που θα μπορούσαμε να κάνουμε στο στάδιο αυτό αφού όλα τα στοιχεία που θα έπρεπε να μηδενιστούν είναι ήδη μηδέν, επομένως μπορούμε απλά να προχωρήσουμε στην επόμενη στήλη (δηλαδή, 484#484). Σημειώστε ότι αυτό το βήμα αφήνει ένα μηδενικό στη διαγώνιο και για το λόγο αυτό ο άνω τριγωνικός πίνακας 108#108 που θα προκύψει θα είναι ιδιάζων, αλλά η 2#2 παραγοντοποίηση μπορεί ακόμη να ολοκληρωθεί. Σημαίνει, όμως, ότι η προς τα πίσω αντικατάσταση που θα επακολουθήσει θα αποτύχει, αφού απαιτεί διαίρεση με κάθε ένα στοιχείο της διαγωνίου του 485#485 Αυτό όμως δε μας εκπλήσσει, αφού ο αρχικός πίνακας θα πρέπει να ήταν έτσι κι αλλιώς ιδιάζων. Ενα ακόμη λιγότερο εμφανές πρόβλημα είναι ότι στην αριθμητική κινητής υποδιαστολής είναι πιθανόν να μην πάρουμε μηδέν ακριβώς, αλλά μόνον ένα πολύ μικρό διαγώνιο στοιχείο, κάτι το οποίο μας φέρνει σε ένα πιο λεπτό σημείο.

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

Οι απαιτούμενες εναλλαγές των γραμμών της μερικής οδήγησης περιπλέκουν λίγο την τυπική περιγραφή της 2#2 παραγοντοποίησης που δόθηκε προηγουμένως. Πιο αναλυτικά, κάθε στοιχειώδης πίνακας απαλοιφής 486#486 ακολουθεί ένα μεταθετικό πίνακα 487#487 ο οποίος εναλλάσσει τις γραμμές για να φέρει το μεγαλύτερου μεγέθους στοιχείο στη διαγώνια θέση οδηγού. Ακόμη έχουμε ότι 488#488, όπου ο 108#108 είναι άνω τριγωνικός, αλλά τώρα

Σημειώστε ότι ο μεταθετικός πίνακας

Η ονομασία "μερική" οδήγηση προέρχεται από το γεγονός ότι στην τρέχουσα στήλη αναζητείται ένα κατάλληλο οδηγό στοιχείο. Μία περισσότερο εξαντλητική τακτική οδήγησης είναι η "πλήρης (ολική)" οδήγηση, κατά την οποία σε ολόκληρο τον εναπομένοντα μη ελαττωμένο υποπίνακα αναζητείται το απόλυτα μεγαλύτερο στοιχείο, το οποίο εν συνεχεία μετατίθεται στην οδηγό διαγώνια θέση. Σημειώστε ότι αυτό απαιτεί εναλλαγή στηλών καθώς επίσης και γραμμών και, επομένως, οδηγεί σε μια παραγοντοποίηση της μορφής

Αφού η επιλογή των οδηγών στοιχείων εξαρτάται από τα μεγέθη των στοιχείων του πίνακα, η συγκεκριμένη επιλογή εξαρτάταται προφανώς και από τη στάθμιση του πίνακα. Μά διαγώνια στάθμιση του πίνακα (θυμηθείτε το Παράδειγμα 2.3) μπορεί να δίνει διαφορετική ακολουθία οδηγών στοιχείων. Για παράδειγμα, ένα οποιοδήποτε μη μηδενικό στοιχείο σε μια δεδομένη στήλη μπορεί να καταστεί το μέγιστο σε μέγεθος απλά δίνοντας στη συγκεκριμένη γραμμή ένα ακούντως μεγάλο συντελεστή βάρους. Αυτό δε σημαίνει ότι μια οποιαδήποτε αυθαίρετη ακολουθία οδηγών στοιχείων είναι αποδεκτή, όμως μία κακώς επιλεγμένη στάθμιση μπορεί να έχει ως αποτέλεσμα ένα ασταθές σύστημα και αντίστοιχα μια μη ακριβή λύση. Ενα καλώς διατυπωμένο πρόβλημα θα πρέπει να έχει σύμμετρες μονάδες μέτρησης των αγνώστων μεταβλητών (στάθμιση στηλών) και μία βαρύτητα των επί μέρους εξισώσεων η οποία θα αντανακλά κατάλληλα τη σχετική σπουδαιότητά τους (στάθμιση γραμμών). Θα πρέπει επίσης να λαμβάνει υπόψη τη σχετική ακρίβεια των δεδομένων εισόδου. Κάτω απ' αυτές τις συνθήκες, η διαδιακασία της οδήγησης θα δίνει συνήθως μια λύση που θα είναι όσο το δυνατόν πιο ακριβής εγγυάται το πρόβλημα (δείτε Κεφάλαιο 2.4).

Οπως μόλις είδαμε, η οδήγηση απαιτείται γενικά για να είναι η απαλοιφή 1#1 ευσταθής. Ομως, υπάρχουν κάποιες κατηγορίες πινάκων για τους οποίους η απαλοιφή 1#1 είναι ευσταθής και χωρίς οδήγηση. Για παράδειγμα, αν ο πίνακας 363#363 είναι αυστηρά διαγώνια υπέρτερος κατά στήλες, που σημαίνει ότι κάθε στοιχείο της διαγωνίου είναι μεγαλύτερο σε μέτρο από το άθροισμα των μέτρων των υπόλοιπων στοιχείων της ίδιας στήλης,