next up previous contents
Next: Ακρίβεια Λύσεων Up: Νόρμες και Αριθμοί Κατάστασης Previous: Νόρμες Πινάκων   Contents

Δείκτης (Αριθμός) Κατάστασης ενός Πίνακα

Ο δείκτης κατάστασης ενός τετραγωνικού μη ιδιάζοντα πίνακα 369#369, με βάση δοσμένη νόρμα, ορίζεται ως:

635#635

Συμβατικά, ορίζεται 636#636 αν ο 369#369 είναι ιδιάζων. Επειδή

637#637

ο δείκτης κατάστασης ενός πίνακα μετράει το λόγο της μέγιστης μεγέθυνσης που μπορεί να επιφέρει ο πίνακας σε ένα μη μηδενικό διάνυσμα προς την αντίστοιχη μέγιστη συρρίκνωση. Θα δούμε στο Κεφάλαιο 2.4.2 ότι αυτή η έννοια είναι συνεπής με τη γενική ιδέα του δείκτη κατάστασης όπως αυτή ορίστηκε στο Κεφάλαιο 1.2.5: ο δείκτης κατάστασης του πίνακα φράσσει τον αντίστροφο της σχετικής μεταβολής στη λύση ενός γραμμικού συστήματος σε μία δοσμένη σχετική μεταβολή των δεδομένων.

Ο δείκτης κατάστασης αποτελεί ένα μέτρο του πόσο κοντά βρίσκεται του πίνακα από το να είναι ιδιάζων: ένας πίνακας με μεγάλο αριθμό κατάστασης (τον οποίο θα υπολογίσουμε στο Κεφάλαιο 2.4.2) είναι σχεδόν ιδιάζων, ενώ ένας πίνακας με δείκτη κατάστασης κοντά στη μονάδα βρίσκεται μακριά από το να είναι ιδιάζων. Σημειώστε ότι η ορίζουσα ενός πίνακα δεν είναι μία καλή ένδειξη για να αποφανθούμε πόσο κοντά βρίσκεται ο πίνακας στο να είναι ιδιάζων: αν και, ο πίνακας 369#369 είναι ιδιάζων αν 638#638, το μέγεθος μιας μη μηδενικής ορίζουσας, μεγάλο ή μικρό, δε δίνει πληροφορία σχετικά με το πόσο κοντά σε κάποια ιδιάζουσα κατάσταση βρίσκεται ο πίνακας. Για παράδειγμα, η ορίζουσα 639#639 , η οποία μπορεί να γίνει οσονδήποτε μικρή για 640#640, παρ' όλα αυτά, ο πίνακας είναι τελείως πολύ καλής κατάστασης για οποιοδήποτε μη μηδενικό 641#641, με δείκτη κατάστασης 39#39.

Κάποιες σημαντικές ιδιότητες του δείκτη κατάστασης (ενός αντιστρέψιμου πίνακα) είναι

  1. Για κάθε πίνακα 369#369, 642#642.
  2. Για τον ταυτοτικό πίνακα, 643#643.
  3. Για κάθε μεταθετικό πίνακα 398#398, 644#644.
  4. Για κάθε πίνακα 369#369 και πραγματικό μη μηδενικό 385#385, 645#645.
  5. Για κάθε διαγώνιο πίνακα 646#646, 647#647.

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

Η νόρμα πίνακα 648#648 υπολογίζεται εύκολα ως το μέγιστο άθροισμα των απόλυτων τιμών των στοιχείων της κάθε στήλης του πίνακα (ή το αντίστοιχο άθροισμα των στοιχείων των γραμμών, ανάλογα με τη νόρμα που χρησιμοποιείται). Υπολογίζει τη 649#649 με χαμηλό κόστος που αποτελεί πρόκληση. Από τις ιδιότητες των νορμών, γνωρίζουμε ότι αν 386#386 είναι η λύση του 650#650 τότε:

651#651

και η ισότητα επιτυγχάνεται για κάποιο βέλτιστα επιλεγμένου 170#170. Ετσι επιθυμούμε να επιλέξουμε ένα διάνυσμα 170#170 τέτοιο ώστε ο λόγος 652#652 να είναι όσο το δυνατόν μεγαλύτερος και άρα να έχουμε μία λογική εκτίμηση της 653#653. Ο υπολογισμός του βέλτιστου 170#170 θα ήταν απαγορευτικά αντιοικονομικός από άποψη πράξεων, αλλά μια χρήσιμη προσέγγιση μπορεί να βρεθεί πολύ πιο οικονομικά. Μία ευρετική μέθοδος είναι να επιλέξουμε το 170#170 ως τη λύση του συστήματος 654#654, όπου 655#655 είναι ένα διάνυσμα του οποίου τα στοιχεία είναι 656#656, με τα πρόσημα διαδοχικά επιλεγμένα ώστε να κάνουν το 170#170 όσο μεγαλύτερο γίνεται.

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



Manolis Vavalis 2000-03-24