Άρθρα

34: 17 Ανάθεση στην τάξη - Αποσυνθέσεις και εξόντωση Gauss


34: 17 Ανάθεση στην τάξη - Αποσυνθέσεις και εξάλειψη Gauss

Ο Schur συμπληρώνει τη γραμματική κατηγορίας Lambek & # x27s: Μια άλλη άποψη για την αποβολή Gauss και την αποσύνθεση LU

Για τρεις δεκαετίες, τα συμπληρώματα Schur έχουν παρατηρήσει αυξανόμενες εφαρμογές στη γραμμική άλγεβρα, συχνά ως αφαιρέσεις της εξάλειψης του Gauss. Είναι γνωστό ότι υπακούουν σε ορισμένες ασυνήθιστες ταυτότητες, όπως οι Crabtree και Haynsworth & # x27s πηλίκα ιδιοκτησία. Ξεκινήσαμε αυτό το έργο ρωτώντας αν υπήρχε μια θεωρία για τον καθορισμό των ιδιοτήτων τους γενικά.

Lambek & # x27s Η κατηγορική γραμματική είναι ένα αφαιρετικό σύστημα που επισημοποιήθηκε το 1958 από τον Lambek ως μαθηματικό ίδρυμα για ένα συντακτικό λογισμό της γλώσσας. Δείχνουμε ότι η Κατηγοριακή Γραμματική δίνει ένα αφαιρετικό σύστημα για την εξαγωγή ταυτοτήτων που ακολουθούνται από τις συνθέσεις LU-και UL, την εξάλειψη Gauss και τα συμπληρώματα Schur.

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


Κανόνας του αντίχειρα / TLDR: Όταν πραγματοποιείτε υπολογισμούς χρησιμοποιώντας αριθμούς κυμαινόμενου σημείου (όπως τύπους διπλών, μονών και πλωτών δεδομένων σε πολλές κοινές γλώσσες προγραμματισμού), χρησιμοποιήστε μερική περιστροφή εκτός εάν γνωρίζετε ότι είστε ασφαλείς χωρίς αυτό και ολοκληρώστε τη περιστροφή μόνο όταν γνωρίζετε ότι το χρειάζεστε.

Μεγαλύτερη εξήγηση: Ένας τετραγωνικός πίνακας $ A $ έχει παραγοντοποίηση $ LU $ (χωρίς περιστροφή) εάν, και μόνο εάν, δεν υπάρχει μηδέν στη συγκεντρωτική θέση κατά τον υπολογισμό παραγοντοποίησης $ LU $ $ A $. Ωστόσο, πότε οι υπολογισμοί που χρησιμοποιούν αριθμούς κινητής υποδιαστολής είναι ένας άξονας που είναι σχεδόν Το μηδέν μπορεί να οδηγήσει σε δραματικά σφάλματα στρογγυλοποίησης. Ο απλός τρόπος αντιμετώπισης είναι να διαπερνούν πάντα τις σειρές της μήτρας έτσι ώστε η μεγαλύτερη μη μηδενική καταχώριση σε μια στήλη να επιλέγεται ως κεντρική καταχώρηση. Αυτό διασφαλίζει ότι ποτέ δεν επιλέγεται σχεδόν μηδέν. Η πλήρης περιστροφή προχωρά ακόμη περισσότερο χρησιμοποιώντας τις παραλλαγές γραμμής και στήλης για να επιλέξετε τη μεγαλύτερη καταχώριση σε ολόκληρο τον πίνακα ως την καταχώρηση περιστροφής.

Η παραπάνω παράγραφος είναι μια χαμένη, διαισθητική εικόνα για το γιατί είναι απαραίτητη η περιστροφή. Κάποιος μπορεί επίσης να αποδείξει έντονα όρια σφάλματος παρακολουθώντας προσεκτικά τη διάδοση σφαλμάτων σε ολόκληρο τον υπολογισμό παραγοντοποίησης $ LU $. Ένας τρόπος δομής αυτού του δεσμευμένου σφάλματος είναι ο λεγόμενος εκτίμηση σφάλματος προς τα πίσω. Σε μια εκτίμηση σφάλματος προς τα πίσω για την επίλυση ενός γραμμικού συστήματος εξισώσεων $ Ax = b $, οριοθετείται η διαταραχή $ E $ που απαιτείται για να γίνει η υπολογισμένη λύση $ hat$ που παράγεται κάνοντας Gaussian αποκλεισμό ακολουθούμενο από πίσω υποκατάσταση και ακριβής λύση σε ένα κοντινό σύστημα γραμμικών εξισώσεων $ (A + E) hat = β $. Μια εκτίμηση σφάλματος προς τα πίσω μπορεί να είναι πολύ αποκαλυπτική εάν, για παράδειγμα, ο πίνακας $ A $ καθορίζεται από μετρήσεις ενός μηχανικού συστήματος με κάποια ανοχή σφαλμάτων. Εάν οι καταχωρίσεις $ A $ είναι γνωστές μόνο $ pm 1 \% $ και το σφάλμα προς τα πίσω είναι μικρότερο από .1 \% $, τότε τα αριθμητικά σφάλματα που έγιναν κατά τη διάρκεια των υπολογισμών μας είναι μικρότερα από τα σφάλματα μέτρησης και έχουμε κάνει καλή δουλειά. TLDR η ποσότητα $ E $ είναι μια λογική ποσότητα για τη μέτρηση του σφάλματος σε παραγοντοποίηση $ LU $ και την προκύπτουσα γραμμική επίλυση.

Για την εξουδετέρωση Gauss χωρίς περιστροφή, το σφάλμα προς τα πίσω μπορεί να είναι αυθαίρετα κακό. Ευτυχώς, για μερική περιστροφή, το σφάλμα προς τα πίσω $ E $ μπορεί να οριοθετηθεί ως $ | E | _ infty le 6n ^ 3 rho | A | _ infty u + mbox$ $ <> ^ στιλέτο $. Εδώ, το $ | cdot | _ infty $ είναι ο πίνακας χειριστή $ infty $ -norm και το $ u $ είναι η μονάδα roundoff που ποσοτικοποιεί την ακρίβεια των υπολογισμών κινητής υποδιαστολής ($ u περίπου 10 ^ <-16> $ για την αριθμητική διπλής ακρίβειας IEE). Η ποσότητα $ rho $ είναι γνωστή ως ο παράγοντας ανάπτυξης για μερική περιστροφή. Ενώ είναι πιθανό το $ rho $ να είναι τόσο μεγάλο όσο $ 2 ^$, στην πράξη το $ rho $ συνήθως αυξάνεται πολύ μετρίως με $ n $. $ <> ^ dagger $ Όσον αφορά το γεγονός ότι το $ rho $ αυξάνεται πολύ μετριοπαθώς στις περισσότερες εφαρμογές, ο θρυλικός αριθμητικός αναλυτής Kahan έγραψε: "Αφόρητη περιστροφική ανάπτυξη [με μερική περιστροφή] είναι ένα φαινόμενο που συμβαίνει μόνο σε αριθμητικούς αναλυτές που αναζητούν. αυτό το φαινόμενο. " $ <> ^ $

Παρ 'όλα αυτά, μπορεί κανείς να γράψει πίνακες για τους οποίους η μερική περιστροφή θα αποτύχει να δώσει μια ακριβή απάντηση λόγω ενός εκθετικού παράγοντα ανάπτυξης $ rho = 2 ^$. Ο Wilkinson έδειξε ότι ο αυξητικός παράγοντας για πλήρης περιστροφή είναι πολύ μικρότερο στη χειρότερη περίπτωση $ rho le n ^ <1/2> (2 cdot 3 ^ <1/2> cdots n ^ <1 / n-1>) ^ <1/2> $. Στην πράξη, το $ rho $ για πλήρη περιστροφή είναι σχεδόν πάντα λιγότερο από $ 100 $. $ <> ^ στιλέτο $

Αφού μελετήσετε τις λεπτομέρειες, μπορείτε να δείτε ότι πρόκειται για μια λεπτή επιχείρηση, και ακόμη και στον κλασικό τομέα της αριθμητικής γραμμικής άλγεβρας υπάρχει κάπως ένα κενό μεταξύ θεωρίας και πειράματος. Σε γενικές γραμμές, η εξάλειψη του Gauss με μερική περιστροφή είναι πολύ αξιόπιστη. Εκτός αν γνωρίζετε ότι μπορείτε να ξεφύγετε χωρίς περιστροφή (τα συμμετρικά θετικά καθορισμένα και διαγώνια κυρίαρχοι πίνακες είναι αξιοσημείωτα παραδείγματα), θα πρέπει να χρησιμοποιήσετε μερική περιστροφή για να έχετε ένα ακριβές αποτέλεσμα. (Ή αντισταθμίστε με κάτι έξυπνο. Για παράδειγμα, το SuperLU χρησιμοποιεί το "static pivoting" όπου κάποιος κάνει την "καλύτερη εικασία" περιστροφή πριν ξεκινήσει το $ LU $ factorization και στη συνέχεια δεν περιστρέφεται κατά την παραγοντοποίηση. Η απώλεια ακρίβειας αυτής της προσέγγισης αντισταθμίζεται από χρησιμοποιώντας μερικά βήματα επαναληπτικής βελτίωσης.)

Εάν η μερική περιστροφή δεν είναι αρκετά ακριβής, μπορεί κανείς να χρησιμοποιήσει την πλήρη περιστροφή αντί για τον χαμηλότερο παράγοντα ανάπτυξης. Όπως επισημαίνει ο χρήστης3417, υπάρχουν άλλοι τρόποι επίλυσης $ Ax = b $ διαφορετικοί από τη χρήση προσεγγίσεων βάσει παραγοντοποίησης $ LU $ και αυτές μπορεί να είναι πιο γρήγορες και πιο ακριβείς από την εξάλειψη Gauss με πλήρη περιστροφή. Για παράδειγμα, η παραγοντοποίηση $ QR $ εκτελείται στις λειτουργίες $ O (n ^ 3) $ και δεν έχει αυξητικό παράγοντα. Μπορεί να υπάρχουν ειδικές περιπτώσεις όταν κάποιος πραγματικά θέλει να χρησιμοποιήσει παραγοντοποίηση $ LU $: για παράδειγμα, μια προσέγγιση που βασίζεται στην αποβολή Gauss μπορεί να χρησιμοποιηθεί για την κατασκευή παραγοντοποιήσεων διατήρησης δομής ενός πίνακα Cauchy. Σε αυτήν την περίπτωση, η πλήρης περιστροφή (ή ο γείτονάς της ξαδέλφου περιστροφής) μπορεί να είναι η καλύτερη προσέγγιση.

$ <> ^ dagger $ Reference Golub και Van Loan's Υπολογισμοί Matrix Τέταρτη έκδοση Κεφάλαιο 3.4

$ <> ^ $ Αναφέρεται στο Higham's Ακρίβεια και σταθερότητα των αριθμητικών αλγορίθμων Δεύτερη Έκδοση Κεφάλαιο 9


Το LU σημαίνει & # 8216Lower Upper & # 8217, και έτσι μια αποσύνθεση LU ενός πίνακα (A ) είναι μια αποσύνθεση έτσι ώστε

όπου (L ) είναι κατώτερο τριγωνικό και (U ) είναι ανώτερο τριγωνικό.

Τώρα, η αποσύνθεση LU είναι ουσιαστικά η γκάουσα εξάλειψη, αλλά δουλεύουμε μόνο με το πλέγμα (A ) (σε αντίθεση με τον αυξημένο πίνακα).

Ας δούμε πώς λειτουργεί η εξάλειψη της γκάους (ge). Θα αντιμετωπίσουμε ένα σύστημα εξισώσεων (3 φορές 3 ) για συνοπτικότητα, αλλά όλα εδώ γενικεύονται στην περίπτωση (n φορές n ). Εξετάστε την ακόλουθη εξίσωση:

Για απλότητα, ας υποθέσουμε ότι ο αριστερός πίνακας (A ) δεν είναι μοναδικός. Για να επιλύσουμε το σύστημα χρησιμοποιώντας το ge, ξεκινάμε με το & # 8216augmented matrix & # 8217:

Ξεκινάμε από την πρώτη καταχώριση, (a_ <11> ). Εάν (a_ <11> neq 0 ), τότε διαιρούμε την πρώτη σειρά με (a_ <11> ) και στη συνέχεια αφαιρούμε το κατάλληλο πολλαπλάσιο της πρώτης σειράς από καθεμία από τις άλλες σειρές, μηδενίζοντας την πρώτη καταχώριση όλων των σειρών. (Εάν (a_ <11> ) είναι μηδέν, πρέπει να αλλάξουμε σειρές. Δεν θα το αναλύσουμε εδώ εδώ.) Το αποτέλεσμα έχει ως εξής:

Επαναλαμβάνουμε τη διαδικασία για τη δεύτερη σειρά, διαιρώντας πρώτα με την αρχική καταχώρηση και μετά αφαιρώντας το κατάλληλο πολλαπλάσιο της γραμμής που προκύπτει από καθεμία από τις τρίτες και πρώτες σειρές, έτσι ώστε η δεύτερη καταχώρηση στη σειρά 1 και στη σειρά 3 να είναι μηδέν. Εμείς θα μπορούσε συνεχίστε έως ότου η μήτρα στα αριστερά είναι η ταυτότητα. Σε αυτήν την περίπτωση, μπορούμε απλώς να & # 8216 διαγράψουμε & # 8217 τη λύση: δηλαδή, το διάνυσμα (x ) είναι το προκύπτον διάνυσμα στήλης στα δεξιά. Συνήθως, είναι πιο αποτελεσματικό να σταματήσετε μειωμένο eschelon σειράς μορφή (άνω τριγωνικό, με αυτά στη διαγώνια) και στη συνέχεια χρησιμοποιήστε υποκατάσταση πίσω για να λάβετε την τελική απάντηση.

Σημειώστε ότι σε ορισμένες περιπτώσεις, είναι απαραίτητο να μετατρέψετε σειρές για να αποκτήσετε μειωμένη φόρμα eschelon. Αυτό ονομάζεται μερική περιστροφή. Εάν χειριστούμε επίσης στήλες, αυτό ονομάζεται πλήρης περιστροφή.

Θα πρέπει να αναφερθεί ότι μπορούμε να αποκτήσουμε το αντίστροφο μιας μήτρας χρησιμοποιώντας ge, μειώνοντας τον πίνακα (A ) στην ταυτότητα, με τον πίνακα ταυτότητας ως το αυξημένο τμήμα.

Τώρα, αυτό είναι εντάξει όταν επιλύουμε ένα σύστημα μία φορά, για ένα αποτέλεσμα (b ). Πολλές εφαρμογές περιλαμβάνουν λύσεις σε πολλαπλά προβλήματα, όπου η αριστερή πλευρά της εξίσωσης του πίνακα δεν αλλάζει, αλλά υπάρχουν πολλοί διανύσματα αποτελεσμάτων (b ). Σε αυτήν την περίπτωση, είναι πιο αποτελεσματικό αναλύω (ΕΝΑ) .

Αρχικά, ξεκινάμε ακριβώς όπως στο ge, αλλά παρακολουθούμε & # 8217 από τα διάφορα πολλαπλάσια που απαιτούνται για την εξάλειψη των καταχωρήσεων. Για παράδειγμα, σκεφτείτε τη μήτρα

Πρέπει να πολλαπλασιάσουμε τη σειρά (1 ) επί (2 ) και να αφαιρέσουμε από τη σειρά (2 ) για να εξαλείψουμε την πρώτη καταχώρηση στη σειρά (2 ) και, στη συνέχεια, να πολλαπλασιάσουμε τη σειρά (1 ) με ( 4 ) και αφαιρέστε από τη σειρά (3 ). Αντί να εισάγουμε μηδενικά στις πρώτες καταχωρίσεις των σειρών (2 ) και (3 ), καταγράφουμε τα πολλαπλάσια που απαιτούνται για την εξάλειψή τους, ως εξής:

Και μετά καταργούμε τη δεύτερη καταχώρηση στην τρίτη σειρά:

Και τώρα έχουμε την αποσύνθεση:

Μπορούμε να λύσουμε το σύστημα επιλύοντας δύο προβλήματα υποκατάστασης:

Αυτά είναι και τα δύο (O (n ^ 2) ), οπότε είναι πιο αποτελεσματικό να αποσυντίθεται όταν υπάρχουν πολλά αποτελέσματα για επίλυση.

Σημειώστε ότι χρησιμοποιείται η αποσύνθεση μερική περιστροφή (οι σειρές μήτρας είναι διαμορφωμένες ώστε να χρησιμοποιούν τον μεγαλύτερο άξονα). Αυτό συμβαίνει επειδή οι μικρές περιστροφές μπορούν να οδηγήσουν σε αριθμητική αστάθεια. Ένας άλλος λόγος για τον οποίο κάποιος πρέπει να χρησιμοποιεί λειτουργίες βιβλιοθήκης όποτε είναι δυνατόν!


Πρόγραμμα αριθμητικών αλγορίθμων

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

Prolegomena, ζητήματα μηχανών και αριθμητική αναπαράσταση, εισαγωγή

Επισκόπηση της άλγεβρας μήτρας, αποβολή Gauss

Πρόσθετα εργαλεία για το κιτ εργαλείων (Αυτά δεν απαιτείται να υποβληθούν ξεχωριστά για έναν βαθμό αλλά θα χρησιμοποιηθούν για την επαλήθευση άλλων αναθέσεων προγραμματισμού.)

  • Πολλαπλασιασμός μήτρας για αυθαίρετους πίνακες κατάλληλου μεγέθους
  • Προσθήκη μήτρας για αυθαίρετους πίνακες κατάλληλου μεγέθους
  • Πολλαπλασιασμός μήτρας / διανύσματος με κλίμακα
  • Dot προϊόν διανυσμάτων (n x 1 πίνακες)

Βρείτε μηχανή epsilon για πλωτήρες και δίκλινα (Προθεσμία 15 Ιανουαρίου). Δείτε και χρησιμοποιήστε τον Αλγόριθμο 1.3.1 στη σελίδα 9 του κειμένου.

Δημιουργήστε και εκτυπώστε ένα ιστόγραμμα, με τουλάχιστον 50 κάδους, για μια τυχαία κατανομή Gauss χρησιμοποιώντας μια ομοιόμορφη γεννήτρια τυχαίας διανομής (Προθεσμία 20 Ιανουαρίου). Δείτε και χρησιμοποιήστε (όπως απαιτείται) τις εξισώσεις με αριθμό 1.6.10a και 1.6.10b στη σελίδα 20 του κειμένου. Βεβαιωθείτε ότι ο μέσος όρος = 0 και η τυπική απόκλιση = 1 για τη διανομή που δημιουργείτε. Τέλος, δημιουργήστε μια διανομή της οποίας ο μέσος όρος = 73 και η τυπική απόκλιση = 16 και επαληθεύστε τα αποτελέσματά σας.

Εφαρμογή των μεθόδων εξάλειψης Gauss-Jordan και Gauss (Αλγόριθμοι 2.2.1 και 2.3.1)

Αντιστροφή Matrix, καθοριστικοί παράγοντες, αποσύνθεση LU, αριθμός συνθηκών, συστήματα που δεν είναι κλιματιζόμενα.

Επεκτείνετε τη μέθοδο εξάλειψης Gauss-Jordan και Gauss για να βρείτε αντίστροφα μήτρα (Αλγόριθμος 2.2.2) και προσαρμόστε τον Αλγόριθμο 2.3.1 για να βρείτε καθοριστικούς παράγοντες (Αλγόριθμος 2.3.2). Σημείωση: Ετοιμάζουμε να εφαρμόσουμε μεθόδους μήτρας σε ένα πρόβλημα παραμόρφωσης εικόνας.


Σημειώσεις τάξης

Εβδομάδες 9-10 (29 Φεβρουαρίου - 11 Μαρτίου)

  • Γεωμετρία LP
  • Ανάλυση ευαισθησίας
  • Η Γεωμετρία του Γραμμικού Προγραμματισμού
  • Ανάλυση ευαισθησίας
  • Ανάλυση ευαισθησίας: Παράδειγμα συγκεκριμένων προϊόντων
  • Προϊόντα σκυροδέματος 2 (Λύσεις)
  • Παράδειγμα οικογενειακής φάρμας
  • Συζητήστε τα μοντέλα 11-20
  • Γεωμετρική δυαδικότητα
  • Προβλήματα ευαισθησίας

Εβδομάδα 8 (22-26 Φεβ)

  • Θεωρία δυαδικότητας
  • Γεωμετρία LP
  • Ο αλγόριθμος Dual Simplex
  • Η Γεωμετρία του Γραμμικού Προγραμματισμού
  • Ο αλγόριθμος Dual Simplex
  • Κάνετε τα μοντέλα 16-20
  • Σχόλια από το γκρέιντερ στο Κουίζ 4: Ο μέσος όρος ήταν 60/80 βαθμοί. Στην ερώτηση 1, πολλοί άνθρωποι μπερδεύτηκαν τη διαφορά μεταξύ ενός μη περιορισμένου επιτραπέζιου και ενός εκφυλισμένου επιτραπέζιου. Υπήρχαν πολλά λάθη στην ερώτηση 2 (ο αλγόριθμος διφασικών απλών). Θα συνιστούσα τον διπλό έλεγχο των υπολογισμών σας καθώς εργάζεστε. Επίσης, πιθανότατα απαιτεί λιγότερες λειτουργίες εάν δεν έχετε τη σειρά "z" στη φάση Ι.

Εβδομάδα 7 (16-19 Φεβ)

  • 11/9: Θεωρία δυαδικότητας
  • 11/17: Το θεμελιώδες θεώρημα του γραμμικού προγραμματισμού, της ισχυρής δυαδικότητας και της συμπληρωματικής χαλαρότητας
  • Συμπληρωματική χαλαρότητα
  • Πρόσθετη πρακτική στη μέθοδο simplex: προβλήματα 3.1.3.2.3.9.3.10 από αυτό το φυλλάδιο.

Εβδομάδα 6 (8-12 Φεβρουαρίου)

  • Ενότητα 3: Λειτουργεί ο αλγόριθμος Simplex;
  • Ενότητα 4: Θεωρία δυαδικότητας
  • 2/8: Λειτουργεί ο απλός αλγόριθμος;
  • 2/10: Ο διφασικός απλός αλγόριθμος
  • 2/12: Το θεμελιώδες θεώρημα των LPs, η ισχυρή δυαδικότητα, η συμπληρωματική χαλαρότητα
  • Κάνετε τα μοντέλα 11-15. Λήξη στην τάξη την Τετάρτη 2/17
  • Δίχρωμος απλός αλγόριθμος

Εβδομάδα 5 (1-5 Φεβρουαρίου)

  • Ενότητα 3: Λειτουργεί ο αλγόριθμος Simplex;
  • Σχόλια από το γκρέιντερ στο Κουίζ 3:
  • 2 / 1,3: Λειτουργεί ο απλός αλγόριθμος;
  • Επαναλάβετε τα προβλήματα από το "Simplex Algorithm for LPs with Feasible Origin" χρησιμοποιώντας αριστερή πολλαπλή αναπαραγωγή με πίνακες εξάλειψης Gaussian. Μάθετε να διαβάζετε τη βέλτιστη λύση στο διπλό από το βέλτιστο πίνακα του πρωτογενούς. Σε κάθε βήμα της μεθόδου, μάθετε να διαβάζετε την τρέχουσα βασική εφικτή λύση και την τιμή αντικειμενικής λειτουργίας.

Εβδομάδα 4 (25-29 Ιανουαρίου)

  • Ενότητα 2: Ο αλγόριθμος Simplex
  • Πίνακες, δομές μπλοκ και εξάλειψη Gauss
  • 1/25: Ο αλγόριθμος Simplex, I: The Basics (φινίρισμα)
  • 1/27: Ο αλγόριθμος Simplex II: Γλώσσα, Σημειογραφία και Γραμμική Άλγεβρα
  • 1/29: Μοντέλα
  • Κάνετε τα μοντέλα 6-10 από τον παραπάνω σύνδεσμο "Μοντέλα".
  • Επαναλάβετε τα προβλήματα από το "Simplex Algorithm for LPs with Feasible Origin" χρησιμοποιώντας τη μέθοδο του πίνακα.

Εβδομάδα 3 (19 Ιανουαρίου-22 Ιανουαρίου)

  • Διαβάστε από σημειώσεις τάξης
    • Ενότητα 2: Ο αλγόριθμος Simplex (ενότητες 1.1-1.2)
    • LP σε τυπική μορφή
    • Ο αλγόριθμος Simplex I: Τα βασικά
    • Μετασχηματισμός των LP σε τυπική μορφή
    • Simplex Algorithm for LPs με εφικτή προέλευση (μέθοδος λεξικού) (θα συνεχιστεί την επόμενη εβδομάδα)

    Εβδομάδα 2 (11-15 Ιανουαρίου)

    • Διαβάστε από σημειώσεις τάξης
      • Τμήμα 1: Εισαγωγή
      • 1/11: Εισαγωγή στον γραμμικό προγραμματισμό
      • 1 / 13,15: Μοντελοποίηση LP
      • Κάνετε τα μοντέλα 1-5 από τον παραπάνω σύνδεσμο "Μοντέλα".

      Εβδομάδα 1 (4-8 Ιανουαρίου)

      • Σχόλια από το γκρέιντερ στο Κουίζ 1: Συνολικά οι άνθρωποι τα πήγαν καλά, αλλά η ερώτηση 4 ήταν δύσκολη --- κανείς δεν το πήρε σωστά. Έβγαλα ένα σημείο για την ερώτηση 2β εάν μετέφεραν τη μήτρα και άρχισαν να μειώσουν τις σειρές, αντί να χρησιμοποιήσω τη φόρμα Echelon που έχουν ήδη υπολογίσει. Έβγαλα επίσης ένα σημείο για την ερώτηση 3β αν έλεγαν κάτι σαν "το πλέγμα δεν έχει αντίστροφο γιατί είναι μοναδικό" γιατί αυτό επαναδιατύπωσε αυτό που υποτίθεται ότι δικαιολογούν. Η μέση βαθμολογία ήταν 7,9 / 13 πόντοι.
      • Διαβάστε από σημειώσεις τάξης
        • Linear Algebra Review (περιλαμβάνει δείγματα κουίζ στο τέλος)
        • Πίνακες, δομές μπλοκ και εξάλειψη Gauss
        • Τμήμα 1: Εισαγωγή (ενότητες 1.1,1.2)
        • 1/4: Διάλεξη 1: Ανασκόπηση γραμμικής άλγεβρας
        • 1 / 6,8: Διάλεξη 2: Εισαγωγή στον γραμμικό προγραμματισμό
        • Γραφικές λύσεις σε δισδιάστατα LP
        • Πρόβλημα 1.1 (α), (β)
        • Πρόβλημα 1.4
        • Πρόβλημα 1.6
        • Πρόβλημα 1.8
        • Πρόβλημα 2.4.1
        • Πρόβλημα 2.4.4
        • Πρόβλημα 2.4.6
        • Μοντελοποίηση: Ανάμειξη δημητριακών, προγραμματισμός διόδων διοδίων, πρόβλημα ταχυδρομείου
        • Μετατροπή LP σε τυπική μορφή: Προβλήματα 2 & 3 σε αυτό το φυλλάδιο (αρχείο pdf)
        • Επίλυση γραφικών LP: Και τα δύο προβλήματα σε αυτό το φυλλάδιο (αρχείο pdf)
        • Μπορείτε να δοκιμάσετε τα προβλήματα στις σημειώσεις του P. Tseng (διανέμονται στην τάξη).
        • Θα μπορούσατε επίσης να δοκιμάσετε τα υπόλοιπα προβλήματα από το Κεφάλαιο 1 στο Chvatal

        Επισκόπηση: Εβδομάδα 2 (12-16 Ιανουαρίου)

        Ανάγνωση εργασιών: Κεφάλαιο 2 του Chvatal

        • simplex method Οι δέκα κορυφαίοι αλγόριθμοι του 20ού αιώνα, Δείτε επίσης αυτήν την ιστοσελίδα
        • μεταβλητές slack και αποφάσεων, λεξικό, βασική εφικτή λύση
        • βασικές μεταβλητές, μη βασικές μεταβλητές, εισαγωγή μεταβλητής, έξοδος μεταβλητής
        • δοκιμή ελάχιστης αναλογίας, γραμμή περιστροφής, περιστροφή
        • πολλαπλά βέλτιστα
        • Ο απλός αλγόριθμος
        • Πώς να αναγνωρίσετε εάν ένα LP έχει πολλαπλά βέλτιστα ή ένα μοναδικό βέλτιστο.
        • Πώς να γράψετε όλες τις βέλτιστες λύσεις σε ένα LP όταν υπάρχουν πολλά βέλτιστα.
        • Πρόβλημα 2.1 (α)
        • Πρόβλημα 2.1 (γ) - επιλύστε επίσης αυτό το πρόβλημα γραφικά και βεβαιωθείτε ότι έχετε την ίδια βέλτιστη λύση.
        • Πρόβλημα 2.2
        • Πρόβλημα 2.3.6
        • Λύστε χρησιμοποιώντας το αρχείο pdf της μεθόδου simplex (από τον J. Burke)
        • Μπορείτε να δοκιμάσετε τα προβλήματα στις σημειώσεις του P. Tseng (διανέμονται στην τάξη) - συγκεκριμένα δοκιμάστε όλα τα προβλήματα στις Ενότητες 2.3, 2.4 και 2.5.
        • Δείτε όλα τα παραδείγματα στο Κεφάλαιο 2 του Chvatal και στο 2.1 (β).

        Επισκόπηση: Εβδομάδα 3 (19-23 Ιανουαρίου)

        Εργασίες ανάγνωσης: Κεφάλαιο 3 του Chvatal (αρχικοποίηση) και Γεωμετρία της απλής μεθόδου

        • υπερπλάνο, ακμές
        • βοηθητικό πρόβλημα, εφικτό / ανέφικτο λεξικό, Φάση Ι και Φάση II
        • εκφυλισμένη κορυφή, κανόνας με τον μεγαλύτερο συντελεστή, διακοπή, χωρίς περιορισμούς LP
        • Η γεωμετρία του απλού αλγορίθμου.
        • Δεδομένης της εφικτής περιοχής, πώς να ανακατασκευάσει το λεξικό σε μια δεδομένη κορυφή της εφικτής περιοχής.
        • Φάση Ι της απλής μεθόδου για να αποφασίσει εάν ένα LP είναι ανέφικτο ή όχι. Εάν το LP είναι εφικτό, πώς να αποκτήσετε ένα πρώτο εφικτό λεξικό.
        • Πώς να διαπιστώσετε εάν η τρέχουσα κορυφή είναι εκφυλισμένη.
        • Πώς να διαπιστώσετε εάν η μέθοδος simplex καθυστερεί.
        • Πώς να διαπιστώσετε εάν το LP δεν είναι περιορισμένο.

        (Προβλήματα γεωμετρίας) Όλα τα προβλήματα από αυτό το φύλλο: αρχείο pdf

        • Πρόβλημα 3.9 (α)
        • Διπλή απλή μέθοδος (από τον J. Burke) αρχείο pdf
        • Πρόβλημα 2 από το φύλλο προβλημάτων γεωμετρίας στην εργασία.
        • Πρόβλημα Chvatal 3.9 (γ)

        Επισκόπηση: Εβδομάδα 4 (26-30 Ιανουαρίου)

        Ανάγνωση εργασιών: Κεφάλαιο 3 του βιβλίου του Chvatal

        • ποδηλασία, εκφυλισμένος άξονας, εκφυλισμένη κορυφή, μέθοδος διαταραχής
        • συγκεντρωτικοί κανόνες, κανόνας μικρότερου συνδρομητή, κανόνας μεγαλύτερης αύξησης
        • εκφυλισμένη κορυφή, κανόνας με τον μεγαλύτερο συντελεστή, διακοπή, χωρίς περιορισμούς LP
        • Πώς να διαπιστώσετε εάν η τρέχουσα κορυφή είναι εκφυλισμένη.
        • Πώς να διαπιστώσετε εάν η μέθοδος simplex καθυστερεί.
        • Πώς να διαπιστώσετε εάν το LP δεν είναι περιορισμένο.
        • Πώς να ανιχνεύσετε την ποδηλασία και τη γεωμετρία πίσω από την ποδηλασία.
        • Απόδειξη ότι μια σταθερή βάση έχει ένα μοναδικό λεξικό που σχετίζεται με αυτό.
        • Πώς να αποτρέψετε την ποδηλασία - κανόνας του Bland και μέθοδος διαταραχής.
        • Το θεμελιώδες θεώρημα του γραμμικού προγραμματισμού (δήλωση και απόδειξη).
        • Η πολυπλοκότητα του απλού αλγορίθμου και τα παραδείγματα Klee-Minty.
        • Πρόβλημα 3.1
        • Πρόβλημα 3.2
        • Πρόβλημα 3.9 (β)
        • Πρόβλημα 3.10
        • Πρόβλημα 4.1 (b), (c) - θα μπορούσατε να τα κάνετε γραφικά

        Επισκόπηση: Εβδομάδα 5 (2-6 Φεβρουαρίου)

        Ανάγνωση εργασιών: Κεφάλαιο 4 του βιβλίου του Chvatal

        • συγκεντρωτικοί κανόνες, κανόνας μικρότερου συνδρομητή, κανόνας μεγαλύτερης αύξησης
        • Η πολυπλοκότητα του απλού αλγορίθμου και τα παραδείγματα Klee-Minty.

        34: 17 Ανάθεση στην τάξη - Αποσυνθέσεις και εξόντωση Gauss

        Προθεσμία Τετάρτης 3 Φεβρουαρίου

        Διαβάστε τις Ενότητες 1.1 και 1.2

        Εργαστείτε μέσω Περιήγησης του Maple στο Μενού Βοήθειας του Maple
        Εργαστείτε μέσω του Dr. Becker Εισαγωγή στο Maple: mw pdf Solutions

        Εργαστείτε τουλάχιστον με τον Οδηγό γρήγορης εκκίνησης του Maple στην ενότητα Υλικό εκπαίδευσης Maple.

        Λήξη Δευτέρας, 8 Φεβρουαρίου

        Διαβάστε τις Ενότητες 1.1 και 1.2
        σελ. 14-15 # 1b (χρησιμοποιήστε θεώρημα ενδιάμεσης τιμής), 3β (χρησιμοποιήστε θεώρημα ενδιάμεσης τιμής), 8, 10, (λύσεις για 8 και 10 mw pdf), βαθμολογία 7abc (ενδέχεται να χρησιμοποιήσετε το Maple) (Λύση mw pdf)

        Προθεσμία Τετάρτης 10 Φεβρουαρίου

        Διαβάστε την Ενότητα 1.3
        σελ. 20-22 # 1bd, 3d, 4g (απάντηση = .284), 7a, 11, βαθμολογία 2d (Λύση)

        Προθεσμία Παρασκευής, 12 Φεβρουαρίου

        Διαβάστε την Ενότητα 1.2
        Έργο 1: σελ. 14 # 12ab (εκτός από το Maple) (Λύση mw pdf)

        Για την επανάληψη για άτομα με λιγότερο από 20/20 ως βαθμό, κάντε το ίδιο πρόβλημα με τη συνάρτηση f (x) = ln (x 4 +3) (Λύση mw pdf)

        Λήξη Δευτέρας, 15 Φεβρουαρίου

        Διαβάστε την Ενότητα 1.4
        σελ. 28-29 # 1d, 3, 7, 10ac (Λύσεις - οι λύσεις αριθμούνται διαφορετικά από τα προβλήματα, αλλά είναι εδώ), 11abd (Λύσεις - οι λύσεις αριθμούνται διαφορετικά από τα προβλήματα, αλλά είναι εδώ), βαθμολογείται:

        X1: Βρείτε το ποσοστό σύγκλισης του limn - & gt & # x221E n / (n 3 +2) = 0. (Λύση)
        X2: Βρείτε το ποσοστό σύγκλισης του limh - & gt0 e h = 1. (Λύση)

        Για την επανάληψη:

        XX1: Βρείτε το ποσοστό σύγκλισης του limn - & gt & # x221E 6n 2 / (3n 5 +5) = 0. (Λύση)
        XX2: Βρείτε το ποσοστό σύγκλισης του limh - & gt0 (1 + e h) = 2. (Λύση)

        Προθεσμία Τετάρτης 17 Φεβρουαρίου

        Έργο 2:

        Στους παλιούς πίνακες trig που χρησιμοποιήθηκαν πριν από την ευρεία χρήση των υπολογιστών, οι πίνακες πήγαν μόνο από 0 μοίρες σε 45 μοίρες και όλες οι τιμές trig από sin έως csc μπορούσαν να ληφθούν από αυτούς. Χρησιμοποιήστε ένα πολυώνυμο Taylor για να κάνετε έναν πίνακα αμαρτίας από 0 έως 45 μοίρες ακριβείς έως τέσσερα ψηφία και να εκτυπώσετε τα αποτελέσματα για κάθε 5 μοίρες. Θυμηθείτε να αλλάξετε βαθμούς σε ακτίνια για την εργασία σας. Ξεκινήστε βρίσκοντας τον βαθμό ενός πολυωνύμου Taylor που προσεγγίζει την αμαρτία από 0 έως Pi / 4 με σφάλμα μικρότερο από 0,00005. Μπορείτε να χρησιμοποιήσετε την αριθμομηχανή για να ελέγξετε την ακρίβεια των αποτελεσμάτων σας, αλλά φροντίστε να δείξετε τα απαραίτητα βήματα της διαδικασίας.

        Λύσεις: mw pdf

        Επανάληψη του έργου 2:

        Δημιουργήστε έναν πίνακα εκθετικής συνάρτησης ανεβαίνοντας κατά δέκατα από το 0 έως το 1. Θέλουμε αυτές τις τιμές να είναι ακριβείς με 4 δεκαδικά ψηφία μετά από στρογγυλοποίηση, δηλαδή εντός 0,00005 από τις ακριβείς τιμές. Το κάνουμε αυτό χρησιμοποιώντας ένα πολυώνυμο Taylor για το x0= 0 για προσέγγιση της εκθετικής συνάρτησης. Ωστόσο, πρέπει πρώτα να βρούμε τον βαθμό του πολυωνύμου Taylor που θα μας δώσει την επιθυμητή ακρίβεια. Το κάνουμε αυτό βρίσκοντας πρώτα ένα ανώτατο όριο για το σφάλμα για ένα πολυωνύμιο Taylor βαθμού. Λάβετε υπόψη ότι το exp (x) είναι το δικό του παράγωγο, ότι το exp (x) αυξάνεται και ότι το exp (1) & lt3.

        Λύσεις: mw pdf

        Προθεσμία Δευτέρας 22 Φεβρουαρίου

        Διαβάστε τις Ενότητες 2.1 και 2.2
        σελ. 38 # 3c (με το χέρι) (Λύση), 5b (Λύση: mw pdf), 7 (Λύση: mw pdf), 11 (Λύση), βαθμολογία 9 (Λύση: mw pdf), 12 (με το χέρι) (Λύση )

        Αναμένεται Τετάρτη, 24 Φεβρουαρίου

        Διαβάστε την Ενότητα 2.3
        σελ. 43-44 # 1α (με το χέρι), 3d (με το χέρι), 13b (Λύση: mw pdf), 15 (16 στο 3ο), βαθμολογία 2α (με το χέρι) (Λύση), 4b (μόλις στο [1, 2]) (Λύση: mw pdf)

        Προθεσμία Παρασκευής, 26 Φεβρουαρίου

        Διαβάστε τις Ενότητες 2.3 και 2.4
        σελ. 43-44 # 1b (με το χέρι), 5α (με το χέρι), 13α, βαθμολογημένο 2b (με το χέρι) (Λύση)
        σελ. 49-50 # 3α (με το χέρι), 7b, 17, βαθμολογία 16α (Λύσεις: mw pdf)

        Προθεσμία Τετάρτης 3 Μαρτίου

        Διαβάστε την Ενότητα 2.5
        Π. 54 # 1d (με το χέρι), 5a (i-ii) (με το χέρι) (Λύση), 7α (σημειώστε ότι ο εκθέτης είναι -2 n, όχι -2n) (Λύση), βαθμολογήθηκε 6α (με το χέρι) (Λύση) , X (Χρησιμοποιήστε τη μέθοδο του Stephensen για να προσεγγίσετε τη ρίζα στο [2,3] για 2 + sin xx = 0 έως εντός 10 -5 - σε βήματα εκτός του Stephensen, χρησιμοποιήστε σταθερό σημείο με x = 2 + sin x) (Λύση: mw pdf),

        Διαβάστε την Ενότητα 2.6
        σελ. 58-59 # 2α (χρήση νεύτο και κέρατος αλγόριθμοι ανάλογα με τις ανάγκες, μπορούν να ελέγξουν την εργασία σας χρησιμοποιώντας το POLY σε μια αριθμομηχανή), 4b, 12 (Set Digits: = 20, με την έκφραση στο σελ.59 και, στη συνέχεια, χρησιμοποιήστε νεύτο για να δείτε πόσο καλή ήταν η Fibinacci), βαθμολογήθηκε 2d (Λύση: mw pdf), 4c (Λύση: mw pdf)

        Προθεσμία Τετάρτης 10 Μαρτίου

        Διαβάστε την Ενότητα 3.2
        σελ. 73-75 # 1α (ii) (με το χέρι βεβαιωθείτε ότι βρίσκεστε σε λειτουργία ακτίνας-cos τιμές στρογγυλοποιημένες σε 6 δεκαδικά ψηφία) (Λύση), 2α (ii) (Λύση), 3α (Σφένδαμος) (Λύση mw pdf ), 7a (Maple) (Λύση mw pdf), βαθμολογία 10 (Maple - μην χρησιμοποιείτε ψηφία: = 4) (Λύση: mw pdf)
        Σημείωση: Για να χρησιμοποιήσετε τον κοινό λογάριθμο βάσης 10 στο Maple, ας πούμε για να βρείτε το αρχείο καταγραφής στη βάση 10 του 85, κάντε τα εξής:
        & gtevalf (log10 (85))

        Διαβάστε την Ενότητα 3.3
        σελ. 81-82 # 1α (κάντε βαθμό 2 μόνο με τα πρώτα τρία σημεία με το χέρι), βαθμολογία 6 [Δείτε την ακόλουθη έξοδο Maple: mw pdf. Τι πρέπει να προσθέσετε ή να αλλάξετε για να λάβετε split_diff σε καρφί για να λειτουργήσει σωστά.] (Λύση: mw pdf), 12

        Διαβάστε την Ενότητα 3.4
        σελ. 86-87 # 1γ (με το χέρι - συγκρίνετε την απάντηση με τη συνάρτηση του # 2c), βαθμολογία 4α (προτείνουμε το Maple) (Λύση: mw pdf)

        Προθεσμία Τετάρτης 17 Μαρτίου

        Διαβάστε τις Ενότητες 3.5
        σελ. 97-99 (ΕΡΓΟ) # 5c, 11 (εκτός από το a = 2) (Λύση), βαθμολογία 12 (Λύση), & "Βρείτε μια ελεύθερη κυβική σφήνα με το χέρι για τα σημεία [0,1], [1,2] , και [2, -1] & quot (Λύση)

        Διαβάστε την Ενότητα 4.2
        σελ. 114-15 # 1g, 3c, 5a, 11, 13a, graded 4c, 6a (Λύση: mw pdf)

        Αναμένεται Τετάρτη, 24 Μαρτίου

        Διαβάστε την Ενότητα 4.3
        σελ. 122-24 # 1g, 2g, 3g, 5, βαθμολογία 4, 8 (Λύσεις: mw pdf)

        Διαβάστε την Ενότητα 4.4
        σελ. 130-32 # 1a, 3b, βαθμολογία 2f, 4a (Λύσεις: mw pdf)

        Διαβάστε την Ενότητα 4.5
        σελ. 137-38 # 1a, 3c, βαθμολογία 2b (Λύση: mw pdf)

        Προθεσμία Τετάρτης 31 Μαρτίου

        Διαβάστε την Ενότητα 4.6
        σελ. 143-45 # 1b, 3c, βαθμολογία 3b (Λύση: mw pdf)

        Προθεσμία Τετάρτης 7 Απριλίου

        Διαβάστε την Ενότητα 5.2
        σελ. 182-83 # 1δ (απλώς δείξτε ότι η IVP έχει μια μοναδική λύση και βρείτε τη λύση), 8 (απλώς δείξτε ότι η IVP έχει μια μοναδική λύση και βρείτε τη λύση), βαθμολογήθηκε 1c (απλώς δείξτε ότι η IVP έχει μια μοναδική λύση και βρείτε τη λύση) (Λύση: mw pdf)

        (Προαιρετικό έργο - 10 πόντοι επιπλέον πίστωση σε βαθμό έργου) Γράψτε μια διαδικασία gaussian που εφαρμόζει gaussian quadrature. Για παραμέτρους θα χρειαστείτε τη συνάρτηση f (τύπος αλγεβρικού), το κατώτατο όριο ολοκλήρωσης a (τύπος αριθμητικός), το ανώτερο όριο ολοκλήρωσης b (τύπος αριθμητικός), τον βαθμό του πολυωνύμου n Legendre που θα χρησιμοποιήσετε (τύπος posint) η μεταβλητή επιστροφής S (όνομα τύπου). Η δήλωση with (orthopoly) μπορεί να βρίσκεται μέσα στο σώμα της διαδικασίας. Όλες οι δηλώσεις που χρειάζεστε βρίσκονται στα φύλλα εργασίας gaussian.mw και gaussian.pdf. Η μόνη έξοδος πρέπει να είναι η τιμή του ακέραιου. Ελέγξτε τη διαδικασία σας για το πρόβλημα 3α στη σελίδα 138. (Λύσεις: mw pdf)

        Διαβάστε την Ενότητα 5.2
        σελ. 182-83 # 1γ (με το χέρι), 3b, 9a (bi) (Λύσεις: mw pdf), βαθμολογία 8a (bi) (Λύσεις: mw pdf)

        Προθεσμία Τετάρτης 14 Απριλίου

        Διαβάστε την Ενότητα 5.2
        σελ. 182-83 # 5γ (Λύσεις: mw pdf), 9e (Λύσεις: mw pdf), βαθμολογία 8e (Λύσεις: mw pdf)

        Προθεσμία Δευτέρας, Απρ19

        Διαβάστε την Ενότητα 5.4
        Π. 198 # 3b (απλώς χρησιμοποιήστε τη μέθοδο τεσσάρων βημάτων Adams-Bashforth) (Λύσεις: mw pdf), 4b (Λύσεις: mw pdf), βαθμολογία 3c (απλώς χρησιμοποιήστε τη μέθοδο τεσσάρων βημάτων Adams-Bashforth - Χρησιμοποιήστε τη λύση για το DE δίνεται στο κείμενο) (Λύσεις: mw pdf), 4c (Λύσεις: mw pdf)

        Προθεσμία Τετάρτης 21 Απριλίου

        Διαβάστε τις ενότητες 5.5 και 5.6
        σελ. 203 # 3β (Λύση: mw pdf), βαθμολογία 4d (Λύση: mw pdf)
        σελ. 213-14 # 3c (εάν δεν χρησιμοποιείτε NA, χρησιμοποιήστε abserr = Float (1, -4) - αγνοήστε hmax και hmin) (Λύσεις: mw pdf), βαθμολογία 4b ((αν δεν χρησιμοποιείτε NA, χρησιμοποιήστε abserr = Float) (1, -6) - αγνοήστε hmax και hmin) (Λύσεις: mw pdf)

        Διαβάστε την Ενότητα 5.7
        σελ. 221-22 # 1b (Λύση: mw pdf), 2c (Λύση: mw pdf), βαθμολογία 6 (Λύσεις: mw pdf) (χρησιμοποιήστε rk4 για όλα τα προβλήματα με h = 0.1 για # 6)

        Διαβάστε την Ενότητα 5.8
        Π. 227 # 1a (με τη μέθοδο rk4) (Λύση: mw pdf), 1b (μέθοδος rosenbrock) (Λύση: mw pdf), βαθμολογία 1d (με τη μέθοδο lsode [backfull]) (Λύση: mw pdf)

        Προθεσμία Τετάρτης 28 Απριλίου

        Διαβάστε την Ενότητα 6.2
        σελ. 238-240 # 1acg (απλώς γράφημα με το χέρι - όπως στην τάξη άλγεβρας), 3f (αποβολή Gaussiam με το χέρι), βαθμολογία 4d (Εξαγωγή Gauss με Maple, σετ ψηφίων: = 7) (Λύση: mw pdf)

        Διαβάστε την Ενότητα 6.3
        Π. 246-47 # 7d (σύνολο ψηφίων: = 3, στρογγυλοποίηση 3 ψηφίων), 8δ (σύνολο ψηφίων: = 3, στρογγυλοποίηση 3 ψηφίων), βαθμολογία 5d (χρήση πλήρους περιστροφής με ψηφία: = 10) (Λύση: mw pdf)

        Διαβάστε την Ενότητα 6.4
        σελ. 256-60 # 2de (συν προσδιοριστές εύρεσης καθενός με το χέρι), βαθμολογία 4b (Λύση: mw pdf)

        Διαβάστε την Ενότητα 6.5
        σελ. 265-66 # 1a, 3bc, βαθμολογία 5α (αγνοήστε τις οδηγίες στο 2α ότι μεγάλοii = 1 για όλα τα i.) (Λύση: mw pdf)

        Διαβάστε την Ενότητα 7.2
        σελ. 284-85 # 1ac, 3bc, 5a, βαθμολογία 2b (Λύση: mw pdf)

        Διαβάστε την Ενότητα 7.3
        σελ. 291-92 # 1ag, 5ag, βαθμολογία 2h (Λύση: mw pdf)


        34: 17 Εργασία στην τάξη - Αποσυνθέσεις και εξάλειψη Gauss

        Ώρες γραφείου: MW: 3: 30-4: 30 και κατόπιν ραντεβού (απλώς μιλήστε με μετά το μάθημα ή στείλτε μου email)

        Γραφείο: APM 5256, τηλ. (858) 534-2734

        Βοηθοί διδασκαλίας: Jeremy Greene (email: [email protected]) ώρες γραφείου: MW10-11: 30 APM 6434 και Michael Kelly (email: [email protected]) ώρες γραφείου: F10-12 APM 6333

        Υπολογισμός βαθμού: Ο βαθμός υπολογίζεται από τις βαθμολογίες σας στον τελικό (50%), 2 μεσάνυχτα 2 (20% το καθένα) και την εργασία στο σπίτι (10%). Ο βαθμός επιτυχίας για τον τελικό απαιτείται για την επιτυχία του μαθήματος Θα κάνω ένα τελικό προπόνησης διαθέσιμο πριν από τον πραγματικό τελικό.

        Ενδιάμεσα: 10/20 και 11/17 στην τάξη

        Κείμενα

        Syllabus: Πρόκειται για ένα δεύτερο μάθημα γραμμικής άλγεβρας που εστιάζει σε υπολογιστικές πτυχές και εφαρμογές, παρουσιάζοντας παράλληλα τις γεωμετρικές έννοιες. Ξεκινάμε με μια γρήγορη ανασκόπηση των βασικών μεθόδων για την επίλυση συστημάτων γραμμικών εξισώσεων και των σχετικών γεωμετρικών υποπεριοχών και εννοιών. Οι εφαρμογές θα καλύπτουν γραφήματα και δίκτυα, λιγότερα τετραγωνικά προβλήματα, γρήγορο μετασχηματισμό Fourier, διαφορές και διαφορικές εξισώσεις και αριθμητικές λύσεις αυτών. Το μάθημα θα προχωρήσει περισσότερο από ένα πρώτο μάθημα στην παραγοντοποίηση των πινάκων. Η διαγώνιοτητα παράγει παραγοντοποιήσεις των περισσότερων τετραγωνικών πινάκων, αλλά γενικά έχουμε τριγωνοποίηση και φυσιολογική μορφή της Ιορδανίας. Η εξάλειψη Gauss και η ορθογωνικοποίηση Gram-Schmidt παράγουν παραγοντοποιήσεις, αλλά μια πιο χρήσιμη είναι η Αποσύνθεση Μοναδικής Αξίας, η οποία μπορεί συγκεκριμένα να χρησιμοποιηθεί για την κατασκευή μιας Ψευδοαποδόμησης όταν δεν υπάρχει αντίστροφη λύση για τα λιγότερα τετραγωνικά προβλήματα.

        Προβλεπόμενο αναλυτικό πρόγραμμα σπουδών (μπορεί να αλλάξει, δηλαδή να πάμε λίγο πιο γρήγορα ή πιο αργά από ό, τι υποδεικνύεται):

        Εβδομάδα 1 (έως 10/1): 1,1-7, 2,1 Matrices και συναρτήσεις γκάους, διανύσματα και υποδιαστήματα
        Εβδομάδα 2: 2.2-5 επίλυση Ax = b, γραμμική ανεξαρτησία, βάση και διάσταση
        Εβδομάδα 3: 2.4-6 Τα τέσσερα βασικά υποδιαστήματα, γραφήματα και δίκτυα, γραμμικοί μετασχηματισμοί
        Εβδομάδα 4: 3.1-3.4 Ορθογώνια διανύσματα και υποδιαστήματα, προβολές, ελάχιστα τετράγωνα, ορθογώνιες μήτρες, Gram-Schmidt,
        Εβδομάδα 5: 3.5: Fast Fourier Transform, 4.1-4 καθοριστικοί παράγοντες
        Εβδομάδα 6:
        Εβδομάδα 7:
        Εβδομάδα 8:
        Εβδομάδα 9:
        Εβδομάδα 10:

        Οι οικιακές εργασίες πρέπει να είναι ενεργοποιημένες ή πριν από την καθορισμένη ημερομηνία, συνήθως την Τετάρτη στις ή πριν από τις 17:00. Θα πρέπει να είναι διαθέσιμο ένα γραμματοκιβώτιο στον 6ο όροφο της APM, αλλά επικοινωνήστε πρώτα με τους TA στην πρώτη εβδομάδα. Καμία εργασία στο σπίτι δεν πρέπει να παραδοθεί κάθε Τετάρτη όταν έχει προγραμματιστεί ένα μεσοδιάστημα. Ωστόσο, ορισμένες από τις εργασίες στο σπίτι μπορεί επίσης να είναι μέρος του υλικού που ζητείται για τα μεσοπρόθεσμα. Είναι πολύ σημαντικό να κάνετε τα προβλήματα στην εργασία, καθώς τα περισσότερα από τα προβλήματα των εξετάσεων θα είναι παραλλαγές των προβλημάτων στην εργασία.

        Αποποίηση ευθυνών: Θα προσπαθήσω να κάνω έγκαιρη την ανάθεση της εργασίας στο Διαδίκτυο. Λόγω του χρόνου και άλλων περιορισμών, αυτό μπορεί να μην είναι πάντα δυνατό. Το γεγονός ότι δεν έχει αναρτηθεί κάποια εργασία για μια συγκεκριμένη ημερομηνία ΔΕΝ σημαίνει απαραίτητα ότι δεν απαιτείται εργασία στο σπίτι.

        για 9/29: Sec. 1.2: 3, 10, Δευ. 1.3: 3 (εσφαλμένη εκτύπωση: εξίσωση 2 -> εξίσωση 1, εξίσωση 3 -> εξίσωση 2), 18, 31, Δευ. 1.4: 6, 10, 30. 32

        για 10/6: Sec. 1.5: 1, 4, 15, Δευ. 1.6: 4,6,22,35,50, Δευτ. 1.7: 3,6, Δευτ. 2.1: 3, 7abcf, 8, 25, 26,

        για 10/13: Sec. 2.2: 5, 8, 10, 24, 25, Sec: 2.3: 2,10, 12,13,20,26,30, Sec. 2.4: 2,5,8,27,28,

        για 10/27: Sec 2.5: 6, 8, Sec. 2.6: 6, 7, 8, 9, 16, 18, 22, 33, Δευ. 3.1: 2, 7, 11, 14, 16, 19, 22, 32, 37, 44, 51, Δευ. 3.2: 14, 17, 19, 21,

        για 11/3: Sec. 3.3: 4,6,12, 17, 22, 27, Δευ. 3.4: 13, 15, 16, 21, 23, (30 καταργημένα), Εν. 3.5: 11,14,

        για 11/10: Sec. 4.2: 2,7,10,12,14,18,28, Sec. 4.3: 3,5,28,43, Δευτ. 4.4: 5, 10, 14, 18,

        για 11/17: δεν χρειάζεται να παραδοθείτε, αλλά σχετικό για τα μεσοπρόθεσμα. Οι λύσεις θα αναρτηθούν παρακάτω: Κεφ. 5.1: 5, 7, 14, 25, 27, Δευ. 5.2: 4, 5, 7, 8, 15, 21, 29, 30, 34, 40,

        για 11/24: Sec. 5.3: 2, 8, 10, 12, 15, 25, 28, Δευ. 5.4: 1, 2, 3, 5, 8, 9,

        για 12/1: Sec. 5.5: 16,17,18,36,38, 41,44,46, Sec. 5.6: 3, 8, 11, 13, 17 (χρήση 5R στη σελίδα 296), 25, 31, 41, 44,

        για τον τελικό (δεν χρειάζεται να παραδοθείτε, αλλά οι σχετικές για τις τελικές λύσεις θα αναρτηθούν αργότερα): Sec 6.2: 2,4,8,23,27,29,30, Sec 6.3: 2,3,5,10,15, 19,

        Λύσεις για τα μεσοπρόθεσμα: Οι ΤΑ πέρασαν από τον ενδιάμεσο σε ενότητες. Επομένως, δεν θα δημοσιεύσουμε λύσεις για τα μεσοπρόθεσμα. Ωστόσο, θα δείξω παρακάτω πώς τα προβλήματα του δεύτερου μεσοπρόθεσμου είναι παρόμοια με τα προβλήματα στην εργασία, για τα οποία μπορείτε να αναζητήσετε τις λύσεις ή να δώσω κάποιες άλλες ενδείξεις πώς να τα κάνετε.

        Το Πρόβλημα 1 (α) ήταν σαν το Πρόβλημα 7 της Ενότητας 2.6, αλλά πιο εύκολο, και για (β) έπρεπε μόνο να τετραγωνίσετε τη μήτρα.

        Το πρόβλημα 2 (α) ήταν το Gram-Schmidt (λύση: (1,2,2,0) και (0,2, -2,1)), το Πρόβλημα 2 (β) ήταν σαν το Πρόβλημα 16 στην Ενότητα 3.1, για παράδειγμα, εσείς can solve it by calculating the null space of the 2 by 4 matrix with rows (1,2,2,0) and (1,4,0,1). Problem 2(c) is just the projection u of x onto S, which is u = (1,10/3, 2/3, 2/3)^T, and for 2(d) we have u as in 2(c) and v = x - u .

        In Problem 3 you calculate the determinant by putting it into echelon form (solution: 1), and for (b) det(2C)=8 det(C).

        Problem 4(a),(b) was like Problem 14 of Section 5.1. To review: B has rank 1, and hence the null space has dimension 3, and we have had several problems where one calculates a basis for a nullspace. For a rank 1 matrix, any column vector is an eigenvector. In our case, B can be written as B=vv^T, where v^T=(1,-1,1,-1). Then you see that Bv=vv^Tv=4v. For 4(c) you just have to know that the columns of S consist of a basis of eigenvectors of B, which have been calculated in parts (a) and (b), and that the diagonal entries of Lambda are the eigenvalues of B, i.e. 4,0,0,0 to solve part (d) (here we assume that the first column of S is the eigenvector for 4, and the following three column vectors are a basis for the null space of B).

        Final: We will have the same rules for the final as for the midterm. One cheat sheet, no calculators, books or other tools. Please bring bluebook/paper. I will post solutions for homework problems below. The new problems start with posting 8, part of which was already made available for the second midterm. Here is also a practice final given by another professor, with solutions. Please read below how my final may differ from that practice final, and for further tips.

        Office hours for exam week: Jeremy: TW 9-12 (APM 6434), Hans Wenzl: MT 3-4+ (i.e. I'll stay beyond 4 if there are students around) (APM 5256)

        More remarks: The practice final has two problems concerning calculating determinants, and two problems concerning solving linear equations and fundamental subspaces. Probably, our final will contain somewhat fewer problems of that type. Also, we have not covered material for question 8(c). Instead, some of the following problems may be on the exam:

        - Calculate SVD for a given matrix

        - Matrix of a linear transformation

        - Exponential or large power of a matrix solution of system of differential equation

        - Properties of positive definite matrices, of symmetric matrices, Hermitian matrices

        Midterm: The second midterm takes place in class on Wednesday, 11/17. The material goes primarily over the assignments for 10/27 until 11/17. Previous material will only be relevant if it is needed in connection with problems of these later sections. You are allowed to use one hand-written cheat sheet, but no books or calculators. Below is a practice midterm with solutions (but only look at the solutions after you have tried the problems in serious. You can also find solutions for homework problems below that.


        Columbia University UN2010 Section 003 Linear algebra, Spring 2017

        Our teaching assistants hold their office hours in the Help Room in Math 406. The Help Room is open Monday-Thursday 9am-6pm and Friday 9am-4pm. You can go there any time during open hours to get help with the material (not just from our TAs).

        Textbook Otto Bretscher Linear algebra with applications, Fifth edition. Cheaper 4th edition is fine too, except for the homework problems, which come from the 5th edition. If you buy the fourth edition, you'll need to get the correct problems from a friend who has the 5th edition

        Syllabus: Our goal is to cover chapters 1 through 8 of the textbook, with few omissions. The topics are: systems of linear equations and Gaussian elimination, matrices, linear transformations, subspaces, linear spaces, orthogonality and the Gram-Schmidt, determinants, eigenvalues, eigenvectors, symmetric matrices.

        Homework: Homework consists in reading the textbook sections before class according to the schedule of lectures and writing down (and turning in) the solutions of problems. The homework problems will be assigned on Tuesdays in Class, due Tuesday the next week before class. Drop the homework off to the hw box with my name on it on the 4th floor of the Math building Two lowest homework scores will be dropped. Graded homework can be picked up from a tray on the 6th floor (up the stairs, turn left and through the door, the table with hw trays is to your left half the hall way). LATE HOMEWORK WON'T BE ACCEPTED. The numerical grade for the course will be the following linear combination:
        15% homework, 25% each midterm, 35% final.

        Homework Assignment

        Homework 1, due Tuesday January 24th. Solve in Section 1.1: # 6, 18, 24, 37, 44 and in Section 1.2: # 2, 4, 9, 11, 18.


        Homework 2, due Tuesday January 31st. Solve in Section 1.2: # 29, 37, 67, in Section 1.3: # 2. 8, 9, 24, 50 and in Section 2.1: # 6, 8.


        Homework 3, due Tuesday February 7th. Solve in Section 2.2: # 14, 32, 39, in Section 2.3: # 7, 20, 47, 60 and in Section 2.4: # 4, 30, 84.


        Homework 4, due Tuesday February 28th. Solve in Section 3.1: # 7, 20, 34, 46, 50 in Section 3.2: # 3, 14, 15, 37, 41.


        Homework 5, due March 7th. Solve in Section 3.2: # 46, 52, 57 in Section 3.3: # 16, 27, 33, 36, 39, 62, 69.


        Homework 6, due March 21st. Solve in Section 3.4: # 45, 60, 82, in Section 4.1: # 29, 49, 59, in Section 4.2: # 7, 53, 65, 70, in Section 4.3: # 38, 62.


        Homework 7, due April 4th. Solve in Section 5.1: # 12, 14, 16, 23, 31 and in Section 5.2: # 29, 35, 38, 44.


        Homework 8, due April 11th. Solve in Section 5.3: # 30, 38, 42, 67 and in Section 5.5: # 5, 10, 16, 20.


        Homework 9, due April 18th. Solve in Section 6.1: # 10, 15, 28, 50 and in Section 6.2: # 5, 23, 31, 43, 45, 54.


        Homework 10, due April 25th. Solve in Section 6.3: # 10, 11, 38, 39, in Section 7.1 : # 13, 44, 53, 64 and in section 7.2 # 2, 22, 33, 45.


        34: 17 In-Class Assignment - Decompositions and Gaussian Elimination

        The Final Course Average will come from 3 sources: Graded Quizzes, Midterm Exams, and the Comprehensive Final Exam. All individual scores on graded work will be converted to percentage scores. Then these percentage scores will be used to calculate your Final Course Average using the following criteria:

        • Graded Quiz Average contributes 15%.
        • Midterm Exam Average contributes 65%.
        • Comprehensive Final Exam contributes 20%.

        You may take each of the Graded Quizzes one time before the deadline date and time that appear to the right of the quiz link in the Quiz and Test System for that quiz.

          • Graded Quizzes in Math 1114 are accessible from any location.
          • You will have scores for 17 Graded Quizzes this semester.
          • Your scores on Graded Quizzes will count in your final course average. See the Deadlines section below for details Only the highest 12 Graded Quiz scores will be used to calculate your ending Quiz % Average at the end of the semester. Δείτε το Deadlines section below for details.

          For more details about Graded Quizzes and how to study for your quizzes, go to the Quizzes page.

          Proctored Exams:

          • Midterm Exams:
            • Each Midterm Exam consists of 18 problems in multiple-choice format covering the same material as the corresponding Practice Problems.
            • You may take each midterm exam one time before the deadline date and time that appear to the right of the exam link in the Quiz and Test System for that exam.
            • Midterm Exams are only accessible from the computers in the Testing Area of the Math Emporium.
            • All 4 of your Midterm Exams will count in your Midterm Exam Average. To allow for unforeseen situations (e.g., short-term illness, transportation problem, human error, etc.), when calculating your ending Midterm Exam Average at the end of the semester, the percentage score on your Final Exam will replace your one lowest Midterm Exam percentage score, if the Final Exam percentage score is higher. Δείτε το Deadlines section below for details.

            • The Final Exam consists of 25 problems in multiple-choice format covering all the course content.
            • You may take the Final Exam one time before the deadline.
            • The Final Exam is only accessible from the computers in the Testing Area of the Math Emporium.

            For more details about Proctored Exams, including Honor System and calculator policies, go to the Proctored Exams page.

            Deadlines for Proctored Exams and Graded Quizzes will be strictly enforced. You can find your deadline for graded work by logging into the Quiz and Test System and viewing the "Must Be Started By" date and time that appear to the right of the link for each graded quiz or exam. As implied by the "Must Be Started By" statement, the deadline is the latest day and time that you can begin your graded work. Unless there are documented extenuating circumstances (see *NOTE* below), deadlines for Proctored Exams and Graded Quizzes will not be extended.

              Midterm Exams:

            A missed exam will receive a 0 score. To allow for unforeseen situations (e.g., short-term illness, transportation problem, human error, etc.), the percentage score on your Final Exam will replace your one lowest Midterm Exam percentage score, if the Final Exam is higher.

            A missed quiz will receive a 0 score. To allow for unforeseen situations (e.g., short-term illness, transportation problem, human error, etc.), your Graded Quiz Average will be calculated using the percentage scores from your highest 12 Graded Quiz scores.

            *NOTE* For extenuating circumstances, you must contact Schiffert Health Center or Student Advocacy in 109 Eggleston Hall to provide documentation to your college. You are expected to work ahead so that you do not miss a deadline due to a one or two day illness or other unforeseen circumstance that fails to satisfy Schiffert or Student Advocacy requirements for documentation. Failure to meet this expectation is not a valid reason for a deadline extension.

            The Undergraduate Honor Code pledge that each member of the university community agrees to abide by states:

            "As a Hokie, I will conduct myself with honor and integrity at all times. I will not lie, cheat, or steal, nor will I accept the actions of those who do."

            Students enrolled in this course are responsible for abiding by the Honor Code. A student who has doubts about how the Honor Code applies to any assignment is responsible for obtaining specific guidance from the course instructor before submitting the assignment for evaluation. Ignorance of the rules does not exclude any member of the University community from the requirements and expectations of the Honor Code.


            Δες το βίντεο: Το τρελοβαπορο - Δημητρης Λαγιος (Δεκέμβριος 2021).