Επιστημονικός Υπολογισμός — Ιανουάριος 2025 — Θεωρία¶
Μεταγραφή από τα αρχεία: IMG_20250129_151007.jpg, IMG_20250129_161934.jpg, IMG_20250129_162003.jpg, IMG_20250129_203151.jpg, IMG_20250129_203233.jpg, IMG_20250129_203304.jpg, IMG_20250129_203338.jpg, IMG_20250129_203403.jpg, IMG_20250129_203428.jpg, 20250129_151814.jpg, IMG_4163.jpg, file-4BuMfRHjFTdpKdUWHa3Rq3.png, Screenshot_20250129_182237_Discord.jpg.
IMG_20250129_151007.jpg¶
+11/2/939+
Ερώτηση 1 ♣ (20β), Χ.Ε.
Μαυρίστε ή σημειώστε X στο κουτάκι όσα από τα παρακάτω υποερωτήματα ισχύουν στη γενική περίπτωση (εκτός αν δηλώνεται κάτι διαφορετικό). Δεν υπάρχει αρνητική βαθμολογία. Προσοχή: Για να βαθμολογηθούν, 3 από τα υποερωτήματα που θα επιλέξετε εσείς, θα χρειαστούν και ΕΠΑΡΚΗ αιτιολόγηση (δείτε το επόμενο ερώτημα).
- [ ] Ένα μειονέκτημα της αναπαράστασης Kruskal ενός τανυστή είναι ότι η αναπαράσταση δεν είναι ακριβής.
- [ ] Αν στο κλασικό συνοριακό πρόβλημα 2 σημείων για μία άγνωστη συνάρτηση \(u(x)\) ο συντελεστής του όρου \(u\) δεν είναι μηδενικός, τότε το μητρώο που προκύπτει από την κλασική διακριτοποίηση με κεντρισμένες πεπερασμένες διαφορές αποκλείεται να είναι συμμετρικό.
- [ ] Αν \(n=2000+\mathrm{randi}(1000,1)\); \(D=\mathrm{rand}(n)\); \(u=\mathrm{randn}(n,1)\); \(v=\mathrm{ones}(n,1);\), τότε το \(u'*((D+u*v')u)\) μπορεί να υπολογιστεί σε \(O(n)\) πράξεις.
- [ ] Κανένα από τα 5 (μη τετριμμένα) προτεινόμενα δεν είναι σωστά.
- [ ] Ένα βασικό πλεονέκτημα της BiCG έναντι της CGS (CG squared) είναι ότι η πρώτη σε αντίθεση με τη δεύτερη μπορεί να χρησιμοποιηθεί για την επίλυση μη συμμετρικών συστημάτων.
- [ ] Αν τα \(B, C\) είναι μητρώα μετάθεσης, τότε και το γινόμενο Kronecker \(B \otimes C\) είναι και αυτό μητρώο μετάθεσης.
- [ ] Όλα τα 5 (μη τετριμμένα) προτεινόμενα είναι σωστά.
Ερώτηση 2 (15β)
Στο προηγούμενο ερώτημα, επιλέξτε ακριβώς 3 υποερωτήματα που απαντήσατε καλύτερα και σημειώστε τους λατ. αριθμούς I, II, III αριστερά από το αντίστοιχο κουτάκι, και αιτιολογήστε τα συνοπτικά παρακάτω. Προσοχή: Μην επιχειρήσετε να αιτιολογήσετε περισσότερες ερωτήσεις γιατί δεν θα θα ληφθούν υπόψη. Οι απαντήσεις πρέπει να είναι επαρκείς και όχι απλά αναδιατύπωση της εκφώνησης. Αν έχετε επιλέξει ότι είναι όλα σωστά ή όλα λάθος, τότε πρέπει να επιλέξετε 3 από τις ερωτήσεις που δεν είναι του τύπου όλα σωστά ή όλα λάθος και να τις απαντήσετε.
ΑΠΑΝΤΗΣΗ ΥΠΟΕΡ. I (σημειώστε ποιο είναι στην προηγούμενη ερώτηση):
[κομμένο]ΑΠΑΝΤΗΣΗ ΥΠΟΕΡ. II (σημειώστε ποιο είναι στην προηγούμενη ερώτηση):
[κομμένο]ΑΝΤΗΣΗ ΥΠΟΕΡ. III (σημειώστε ποιο είναι στην προηγούμενη ερώτηση):
(10β)
ΚΙΝΗΤΑ ΚΛΕΙΣΤΑ. ΑΝΤΙΓΡΑΦΗ, ΔΙΑΚΙΝΗΣΗ, ΣΥ[κομμένο] ΣΙΑ ΕΠΙΦΕΡΟΥΝ ΜΗΔΕΝΙΣΜΟ/ΑΝΑΦΟΡΑ.
IMG_20250129_161934.jpg¶
[Σημείωση: το επάνω τμήμα της σελίδας είναι εκτός φωτογραφίας (επικεφαλίδα και αρχή της ερώτησης)· το σχήμα φαίνεται μερικώς.]
[Σχήμα: τμήμα ορθογωνίου πλαισίου με σημεία αριθμημένα 1, 4, 5, 6 και ένα ακόμα σημείο με δυσανάγνωστη ετικέτα]
Κάτω από την επικεφαλίδα, οι 3 γραμμές του πίνακα παρακάτω περιέχουν τις τιμές, τον αριθμό γραμμής και τον δείκτη στήλης της αναπαράστασης CSC ενός \(A \in \mathbb{R}^{7\times 7}\). Όπου βλέπετε Inf στη γραμμή των δεικτών αγνοήστε το (θεωρήστε ότι η θέση είναι κενή.
VAL, ROW_IDX, COL_PTR
| VAL | 1 | 38 | 37 | 37 | 81 | 6 | 37 | 6 | 29 | 21 | 1 | 21 | 22 | 1 | 2 | 37 | 38 |
| ROW_IDX | 1 | 2 | 3 | 2 | 3 | 4 | 7 | 3 | 4 | 5 | 6 | 4 | 5 | 4 | 6 | 3 | 7 |
| COL_PTR | 1 | 2 | 4 | 8 | 12 | 14 | 16 | 18 | Inf | Inf | Inf | Inf | Inf | Inf | Inf | Inf | Inf |
Το μητρώο είναι συμμετρικό θετικά ορισμένο και έχει επίσης αποθηκευθεί σε μορφή sparse στη MATLAB με όνομα μεταβλητής A.
ΚΙΝΗΤΑ ΚΛΕΙΣΤΑ. ΑΝΤΙΓΡΑΦΗ, ΔΙΑΚΙΝΗΣΗ, ΣΥΝΕΡΓΑΣΙΑ ΕΠΙΦΕΡΟΥΝ ΜΗΔΕΝΙΣΜΟ/ΑΝΑΦΟΡΑ.
IMG_20250129_162003.jpg¶
- Έστω ότι καλούμε A = chol(A). Να συμπληρώσετε τον πίνακα παρακάτω με τις θέσεις γραμμών i και στηλών j στις οποίες προβλέπεται ότι θα υπάρξει fill-in (γέμισμα) λόγω της παραπάνω κλήσης. Προσοχή: στον πίνακα να γράψετε μόνον τα ΝΕΑ μη μηδενικά στοιχεία στο (άνω τριγωνικό) R και όχι όσα προϋπάρχουν στο A. Η σειρά απαρίθμησης πρέπει να είναι row major, από τα αριστερά προς τα δεξιά, π.χ. αν στο R εμφανιστούν τα νέα στοιχεία (2,4), ..., (1,2), (3,7), (2,6) εσείς θα συμπληρώσετε τον πίνακα με τις ακόλουθες τιμές i : 1, 2, 2, 3 και j : 2, 4, 6, 7. Υπόδειξη: Μην κάνετε την αριθμητική παραγοντοποίηση Cholesky! Τροποποιήστε το γράφημα με την προσθήκη των νέων ακμών (με διαφορετική διαγράμμιση) που δείχνουν το fill-in της παραγοντοποίησης Cholesky
Απάντηση υποερωτήματος 2: Οι νέες θέσεις που πρέπει να δημιουργηθούν λόγω fill-in στο άνω τριγωνικό τμήμα του A είναι (αφήστε κενά όσα κελιά δεξιά δεν χρειάζονται):
| i | ||||||||||||||
| j |
- Αν στη συνέχεια δοθεί η εντολή p = symamd(A), επιστρέφεται το διάνυσμα:
Να συμπληρώσετε τις τιμές του μητρώου A(p,p):
[Σχήμα: κενό μητρώο με αγκύλες (παρένθεση μεγάλου μεγέθους), προς συμπλήρωση των τιμών του A(p,p)]
Για τα συγκεκριμένα A, p, να υπολογίσετε την τιμή της κατατομής (profile) του [κομμένο]
ΚΙΝΗΤΑ ΚΛΕΙΣΤΑ. ΑΝΤΙΓΡΑΦΗ, ΔΙΑΚΙΝΗΣΗ, ΣΥΝ[κομμένο] ΣΙΑ ΕΠΙΦΕΡΟΥΝ ΜΗΔΕΝΙΣΜΟ/ΑΝΑΦΟΡΑ.
IMG_20250129_203151.jpg¶
[Σχήμα: γράφημα της ερώτησης 1, καλυμμένο από κόκκινη επικάλυψη στη φωτογραφία]
-
Συμπληρώστε το παραπάνω γράφημα με (μη κατευθυνόμενες) ακμές, παραλείποντας τους αυτοβρόχους, ώστε να είναι το γράφημα του μητρώου.
-
Έστω ότι καλούμε \(A = \mathrm{chol}(A)\). Να συμπληρώσετε τον πίνακα παρακάτω με τις θέσεις γραμμών \(i\) και στηλών \(j\) στις οποίες προβλέπεται ότι θα υπάρξει fill-in (γέμισμα) λόγω της παραπάνω κλήσης. Προσοχή: στον πίνακα να γράψετε μόνον τα ΝΕΑ μη μηδενικά στοιχεία στο (άνω τριγωνικό) \(R\) και όχι όσα προϋπάρχουν στο \(A\). Η σειρά απαριθμησης πρέπει να είναι row major, από τα αριστερά προς τα δεξιά, π.χ. αν στο \(R\) εμφανιστούν τα νέα στοιχεία \((2,4),\dots,(1,2),(3,7),(2,6)\) εσεις θα συμπληρώσετε τον πίνακα με τις ακολουθες τιμές \(i\): \(1,2,2,3\) και \(j\): \(2,4,6,7\). Υπόδειξη: Μην κάνετε την αριθμητική παραγοντοποίηση Cholesky! Τροποποιήστε το γράφημα με την προσθήκη των νέων ακμών (με διαφορετική διαγράμμιση) που δείχνουν το fill-in της παραγοντοποίησης Cholesky.
Απάντηση υποερωτήματος 2:
Οι νέες θέσεις που πρέπει να δημιουργηθούν λόγω fill-in στο άνω τριγωνικό τμήμα του \(A\) είναι (αφήστε κενά όσα κελιά δεξιά δεν χρειαστούν) :
| i | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| j |
- Αν στη συνέχεια δοθεί η εντολή \(p = \mathrm{symrem}(A)\), επιστρέφεται το διάνυσμα: \(p = (5\ 4\ 2\ 6\ 1\ 3\ 7)\). Να συμπληρώσετε τις τιμές του μητρώου \(A(p,p)\):
[Σχήμα: \(A(p,p) =\) κενό μητρώο με παρενθέσεις, προς συμπλήρωση]
- Για τα συγκεκριμένα \(A\), \(p\), να υπολογίσετε την τιμή της κατατομής (profile) του \(A(p,p)\).
ΚΙΝΗΤΑ ΚΛΕΙΣΤΑ. ΑΝΤΙΓΡΑΦΗ, ΔΙΑΚΙΝΗΣΗ, ΣΥΝΕΡΓΑΣΙΑ ΕΠΙΦΕΡΟΥΝ ΜΗΔΕΝΙΣΜΟ[δυσανάγνωστο]ΦΟΡΑ.
IMG_20250129_203233.jpg¶
[Λείπει από τη φωτογραφία: επικεφαλίδα της ερώτησης· το πάνω μέρος της σελίδας είναι καλυμμένο.]
Δίνονται το διάνυσμα και τα μητρώα: \(\ell = \begin{pmatrix} 1 \\ 2 \end{pmatrix}\), \(U = \begin{pmatrix} 0 & 1 \\ -1 & 0 \\ 2 & 3 \end{pmatrix}\), \(V = \begin{pmatrix} 1 & 0 \\ -3 & -4 \end{pmatrix}\), \(W = \begin{pmatrix} 2 & 4 \\ 3 & 5 \\ 1 & 3 \end{pmatrix}\).
Αυτά τα χρησιμοποιούμε για να ορίσουμε την αναπαράσταση Kruskal
όπου ως συνήθως, \(\lambda_i, u_i, v_i, w_i\), είναι στοιχεία και στήλες των \(\ell, U, V, W\). Να υπολογίσετε το \(T_{\cdot,2,\cdot}\) και να γράψετε το αποτέλεσμα.
[Σχήμα: κενό πεδίο απάντησης]
Ερώτηση 6 (20β)
[Σχήμα: διάγραμμα με 7 σημεία στο επίπεδο, αριθμημένα 1 έως 7, χωρίς ακμές· μερικές ετικέτες (ιδίως του πάνω σημείου) δυσανάγνωστες]
Κάτω από την επικεφαλίδα, οι 3 γραμμές του πίνακα παρακάτω περιέχουν τις τιμές, τον αριθμό στήλης και τον δείκτη γραμμής της αναπαράστασης CSR ενός \(A \in \mathbb{R}^{7 \times 7}\). Όπου βλέπετε Inf στη γραμμή των δεικτών αγνοήστε το (θεωρήστε ότι η θέση είναι κενή.)
VAL, COL, IDX, ROW_PTR
| 58 | 7 | 49 | 1 | 7 | 56 | 29 | 19 | 49 | 50 | 29 | 53 | 23 | 23 | 24 | 1 | 19 | 21 | 1 |
| 1 | 2 | 3 | 6 | 1 | 2 | 4 | 6 | 1 | 3 | 2 | 4 | 5 | 4 | 5 | 1 | 2 | 6 | 7 |
| 1 | 5 | 9 | 11 | 14 | 16 | 19 | 20 | Inf | Inf | Inf | Inf | Inf | Inf | Inf | Inf | Inf | Inf | Inf |
Το μητρώο είναι συμμετρικό θετικά ορισμένο και έχει επίσης αποθηκευθεί σε μορφή sparse στη MATLAB με όνομα μεταβλητής A.
IMG_20250129_203304.jpg¶
[κόκκινη σήμανση στο πάνω μέρος της σελίδας: καλύπτει την επικεφαλίδα της ερώτησης· δεν μεταγράφεται]
Δίνονται το διάνυσμα και τα μητρώα: \(\ell = \begin{pmatrix} 1 \\ -1 \end{pmatrix}\), \(U = \begin{pmatrix} 2 & 3 \\ 3 & 4 \\ -3 & -2 \end{pmatrix}\), \(V = \begin{pmatrix} -5 & -6 \\ 2 & 1 \end{pmatrix}\), \(W = \begin{pmatrix} 0 & 2 \\ 0 & 2 \\ 3 & 5 \end{pmatrix}\). Αυτά τα χρησιμοποιούμε για να ορίσουμε την αναπαράσταση Kruskal
όπου ως συνήθως, \(\lambda_i, u_i, v_i, w_i\) είναι στοιχεία και στήλες των \(\ell, U, V, W\). Δίνεται το διάνυσμα \(B = \begin{pmatrix} 0 \\ -2 \\ -1 \end{pmatrix}\). Από τα δοθέντα δεδομένα, υπολογίστε το τροπικό γινόμενο \(P = T \bar{\times}_3 B\).
Υπόδειξη: Πρόκειται για γινόμενο τανυστή με διάνυσμα (όπως π.χ. στο ttv). Το αποτέλεσμα είναι τανυστής βαθμού 2.
[κενό: πεδίο για την απάντηση]
Ερώτηση 4 (15β) Δίνονται
n=30; U = rand(n,4); V= rand(n,4); A=eye(n) + U*V'; y = rand(n,1); b = A*ones(n,1);.
Παρατηρούμε ότι κάθε φορά που καλείται gmres(A,b), η MATLAB επιστρέφει gmres converged at iteration 5 to a solution with relative residual XXXX. όπου XXXX είναι ένας αριθμός της τάξης του έψιλον της μηχανής. Να αποδείξετε γιατί ο αριθμός επαναλήψεων θα είναι πάντα (το πολύ) 5. ΑΠΑΝΤΗΣΗ:
Ερώτηση 5 (20β)
Δίνονται οι παρακάτω εντολές αρχικοποίησης τιμών και μητρώων B καθώς και ένας τρόπος υπολογισμού δύναμης του μητρώου που βασίζεται αποκλειστικά στη συνάρτηση mtimes (δηλ. στον τελεστή "*") και όχι στην mpower (δηλ. στον τελεστή ^.)
- Συμπληρώστε το πλαίσιο με κώδικες MATLAB για εναλλακτικό υπολογισμό του \(B^p\) που χρησιμοποιεί mtimes αλλά είναι πολύ αποδοτικότερος σε πράξεις και μνήμη από τον παραπάνω υπολογισμό. Προσοχή: Δεν επιτρέπεται η χρήση του τελεστή "^", ούτε υπερταχέων μεθόδων ούτε ζητάμε να γράψετε υλοποίηση του πολλαπλασιασμού μητρώων με εμφωλευμένους βρόχους τύπου \(ijk\).
A = rand(1500); B = kron(eye(2),A); p = 25;
B_rec = B; for j=1:p-1, B_rec=mtimes(B,B_rec); end; % προφανής υπολογισμός.
ΚΙΝΗΤΑ ΚΛΕΙΣΤΑ. ΑΝΤΙΓΡΑΦΗ, ΔΙΑΚΙΝΗΣΗ, ΣΥΝΕΡΓΑΣΙΑ ΕΠΙΦΕΡΟΥΝ ΜΗΔΕΝΙΣΜΟ/ΑΝΑΦΟΡΑ.
[στο κάτω μέρος της φωτογραφίας φαίνεται θολό τμήμα άλλης σελίδας με τίτλους ενοτήτων· δεν μεταγράφεται]
IMG_20250129_203338.jpg¶
[πάνω μέρος σελίδας καλυμμένο με κόκκινο σχέδιο]
- Συμπληρώστε το παραπάνω γράφημα με (μη κατευθυνόμενες) ακμές, παραλείποντας τους αυτοβρόχους, ώστε να είναι το γράφημα του μητρώου .
[Σχήμα: γράφημα του πρώτου ερωτήματος στο πάνω μέρος της σελίδας, καλυμμένο — δεν είναι ορατό]
- Έστω ότι καλούμε \(A = \mathrm{chol}(A)\). Να συμπληρώσετε τον πίνακα παρακάτω με τις θέσεις γραμμών \(i\) και στηλών \(j\) στις οποίες προβλέπεται ότι θα υπάρξει fill-in (γέμισμα) λόγω της παραπάνω κλήσης. Προσοχή: στον πίνακα να γράψετε μόνον τα ΝΕΑ μη μηδενικά στοιχεία στο (άνω τριγωνικό) \(R\) και όχι όσα προϋπάρχουν στο \(A\). Η σειρά απαρίθμησης πρέπει να είναι row major, από τα αριστερά προς τα δεξιά, π.χ. αν στο \(R\) εμφανιστούν τα νέα στοιχεία \((2,4), \dots, (1,2), (3,7), (2,6)\) εσείς θα συμπληρώσετε τον πίνακα με τις ακόλουθες τιμές \(i : 1, 2, 2, 3\) και \(j : 2, 4, 6, 7\). Υπόδειξη: Μην κάνετε την αριθμητική παραγοντοποίηση Cholesky! Τροποποιήστε το γράφημα με την προσθήκη των νέων ακμών (με διαφορετική διαγράμμιση) που δείχνουν το fill-in της παραγοντοποίησης Cholesky.
Απάντηση υποερωτήματος 2:
Οι νέες θέσεις που πρέπει να δημιουργηθούν λόγω fill-in στο άνω τριγωνικό τμήμα του \(A\) είναι (αφήστε κενά όσα κελιά δεξιά δεν χρειαστούν) :
| i | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| j |
Αν στη συνέχεια δοθεί η εντολή \(p = \mathrm{symamd}(A)\), επιστρέφεται το διάνυσμα:
Να συμπληρώσετε τις τιμές του μητρώου \(A(p,p)\):
[Σχήμα: κενή μήτρα \(A(p,p)\) για συμπλήρωση]
τα συγκεκριμένα \(A\), \(p\), να υπολογίσετε την τιμή της κατατομής (profile) του \(A(p,p)\):
[υποσέλιδο, εν μέρει καλυμμένο: ΚΙΝΗΤΑ ΚΛΕΙΣΤΑ. ΑΝΤΙΓΡΑΦΗ, ΔΙΑΚΙΝΗΣΗ, [δυσανάγνωστο] ΣΙΑ ΕΠΙΦΕΡΟΥΝ ΜΗΔΕΝΙΣΜΟ/ΑΝΑΦΟΡΑ.]
IMG_20250129_203403.jpg¶
[Σημείωση: η φωτογραφία είναι τραβηγμένη πλάγια· η μεταγραφή αφορά τη σωστά προσανατολισμένη εικόνα. Κόκκινη σήμανση καλύπτει μέρος της επάνω επικεφαλίδας και του αριστερού περιθωρίου.]
ΑΠΑΝΤΗΣΗ ΥΠΟΕΡ. III (σημειώστε ποιο είναι στην προηγούμενη ερώτηση):
Ερώτηση 3 (10β)
Δίνονται το διάνυσμα και τα μητρώα: \(\ell = \begin{pmatrix} -2 \\ 2 \end{pmatrix}\), \(U = \begin{pmatrix} -3 & -2 \\ 3 & 4 \end{pmatrix}\), \(V = \begin{pmatrix} 5 & 4 \\ 0 & -1 \\ -2 & -3 \end{pmatrix}\), \(W = \begin{pmatrix} 1 & 3 \\ 0 & 2 \end{pmatrix}\). Αυτά τα χρησιμοποιούμε για να ορίσουμε την αναπαράσταση Kruskal
όπου ως συνήθως, \(\lambda_i, u_i, v_i, w_i\) είναι στοιχεία και στήλες των \(\ell, U, V, W\). Δίνεται το διάνυσμα \(B = \begin{pmatrix} -1 \\ 2 \end{pmatrix}\). Από τα δοθέντα δεδομένα, υπολογίστε το τροπικό γινόμενο \(P = T \times_1 B\).
Υπόδειξη: Πρόκειται για γινόμενο τανυστή με διάνυσμα (όπως π.χ. στο ttv). Το αποτέλεσμα είναι τανυστής βαθμού 2.
[Σχήμα: κενό πλαίσιο απάντησης «P = ( )», μητρώο χωρίς εγγραφές]
[κομμένο]η 4 (20β)
IMG_20250129_203428.jpg¶
[Επικεφαλίδα φοιτητή: καλυμμένη με κόκκινο σημάδι· δεν μεταγράφεται]
Ερώτηση 1 ♣ (20β), Χ.Ε.
Μαυρίστε ή σημειώστε Χ στο κουτάκι όσα από τα παρακάτω υποερωτήματα ισχύουν στη γενική περίπτωση (εκτός αν δηλώνεται κάτι διαφορετικό). Δεν υπάρχει αρνητική βαθμολογία. Προσοχή: Για να βαθμολογηθούν, 3 από τα υποερωτήματα που θα επιλέξετε εσείς, θα χρειαστούν και ΕΠΑΡΚΗ αιτιολόγηση (δείτε το επόμενο ερώτημα).
- [ ] Αν \(A = \text{rand}(100)\) και \(x = \text{rand}(100,1)\), τότε το μητρώο \(K = [x, Ax, A^2x, \ldots, A^{n-1}x]\) αναμένεται να έχει καλό δείκτη κατάστασης.
- [ ] Δεδομένων όσων γνωρίζουμε για τα BLAS, είναι προτιμότερο να υλοποιούμε τον πολλαπλασιασμό μητρώο με διάνυσμα και την ανανέωση πρώτης τάξης με εντολές BLAS3.
- [ ] Αν στην απλή εξίσωση Poisson \(-u_{xx} = f(x,y)\) ορισμένη στο διάστημα \([0,1]\) με συνθήκες Dirichlet στο σύνορο χρησιμοποιήσουμε την κλασική διακριτοποίηση (κεντρισμένες πεπερασμένες διαφορές 2ης τάξης) και οι κόμβοι του πλέγματος ισαπέχουν, τότε αν διατάξουμε τους αγνώστους του διανύσματος των αγνώστων \(U_i\) έτσι ώστε να αριθμούνται πρώτα οι άγνωστοι για τους οποίους η τιμή \(i\) είναι περιττή, και μετά αυτοί για τους οποίους η τιμή \(i\) είναι άρτια, τότε το μητρώο των συντελεστών θα έχει τη δομή \(\begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix}\) τα \(A_{11}, A_{22}\) θα είναι διαγώνια μητρώα.
- [ ] Κανένα από τα 5 (μη τετριμμένα) προτεινόμενα δεν είναι σωστά.
- [ ] Όλα τα 5 (μη τετριμμένα) προτεινόμενα είναι σωστά.
- [ ] Το γινόμενο δύο τετραγωνικών μητρώων Toeplitz μεγέθους \(n \times n\) υπολογίζεται με \(\mathcal{O}(n^2 \log_2 n)\) πράξεις.
- [ ] Αν \(n=300+\text{randi}(1000,1)\); \(D=\text{toeplitz}([4,-1,\text{zeros}(1,n-2)])\); \(u= \text{randn}(n,1)\); \(v=\text{ones}(n,1)\); και το \(A = [D,u;v',1]\); παραγοντοποιηθεί ως \(LU\) με το \(L\) κάτω τριγωνικό με 1 στη διαγώνιο και το \(U\) άνω τριγωνικό, τότε όλα τα στοιχεία των \(L,U\) υπολογίζονται σε \(\Omega = \mathcal{O}(n)\) πράξεις.
Ερώτηση 2 (15β)
Στο προηγούμενο ερώτημα, επιλέξτε ακριβώς 3 υποερωτήματα που απαντήσατε καλύτερα και σημειώστε τους λατ. αριθμούς Ι, ΙΙ, ΙΙΙ αριστερά από το αντίστοιχο κουτάκι. και αιτιολογήστε τα συνοπτικά παρακάτω. Προσοχή: Μην επιχειρήσετε να αιτιολογήσετε περισσότερες ερωτήσεις γιατί δεν θα θα ληφθούν υπόψη. Οι απαντήσεις πρέπει να είναι επαρκείς και όχι απλά αναδιατύπωση της εκφώνησης. Αν έχετε επιλέξει ότι είναι όλα σωστά ή όλα λάθος, τότε πρέπει να επιλέξετε 3 από τις ερωτήσεις που δεν είναι του τύπου όλα σωστά ή όλα λάθος και να τις απαντήσετε.
ΑΠΑΝΤΗΣΗ ΥΠΟΕΡ. I (σημειώστε ποιο είναι στην προηγούμενη ερώτηση):
ΑΠΑΝΤΗΣΗ ΥΠΟΕΡ. II (σημειώστε ποιο είναι στην προηγούμενη ερώτηση):
20250129_151814.jpg¶
[Η φωτογραφία είναι στραμμένη και θολή στις πρώτες γραμμές· το δεξί άκρο είναι κομμένο. Τα σημεία που δεν διαβάζονται σημειώνονται με [δυσανάγνωστο] ή [κομμένο].]
Ερώτηση 4 ♣ (20β), Χ.Ε.
Μαυρίστε ή σημειώστε Χ στο κουτάκι όσα από τα παρακάτω υποερωτήματα ισχύουν στη γενική περίπτωση (εκτός αν δηλώνεται κάτι διαφορετικό). Δεν υπάρχει αρνητική βαθμολογία. Προσοχή: Για να βαθμολογηθούν, 3 από τα υποερωτήματα που θα επιλέξετε εσείς, θα χρειαστούν και ΕΠΑΡΚΗ αιτιολόγηση (δείτε το επόμενο ερώτημα).
- [ ] Έστω ότι \(n = 1000\) και ένα διαγώνιο μητρώο \(A \in \mathbb{R}^{n \times n}\) με όλα τα διαγώνια στοιχεία θετικά, χρησιμοποιούμε GMRES για την επίλυση του \(Ax = b\) (π.χ. καλώντας gmres(A,b)) τότε υπάρχει σύγκλιση σε λιγότερες από 10 επαναλήψεις.
- [ ] Αν \(n > 1\), \(I\) το ταυτοτικό μητρώο και \(u, v \in \mathbb{R}^n\) (στήλες), τότε \(u^T(I + uv^T)^p v\) μπορεί να υπολογιστεί σε \(O(n)\) πράξεις.
- [ ] Όταν χρησιμοποιούμε τις εντολές tic-toc για την εκτίμηση επίδοσης μιας συνάρτησης π.χ. myfun, για μεγαλύτερη αξιοπιστία συνιστάται να υπολογίσουμε το χρόνο πολλών κλήσεων με τις εντολές:
t=0; tic; for j=1:N, myfun; end; t=toc; T=t/N;για κάποιο κατάλληλα επιλεγμένο N. - [ ] Όλα τα 5 (μη τετριμμένα) προτεινόμενα είναι σωστά.
- [ ] Η τάξη της προς τα εμπρός Euler για την επίλυση του \(\frac{dy}{dt} = f(t,u), y(0) = c\) είναι κατά 1 λιγότερο της τάξης του τοπικού σφάλματος διακριτοποίησης.
- [ ] Το γινόμενο κάτω τριγωνικών μητρώων Toeplitz είναι πάντα μητρώο Toeplitz.
- [ ] Κανένα από τα 5 (μη τετριμμένα) προτεινόμενα δεν είναι σωστά.
Ερώτηση 5 (15β)
Στο προηγούμενο ερώτημα, επιλέξτε ακριβώς 3 υποερωτήματα που απαντήσατε καλύτερα και σημειώστε τους λατ. αριθμούς I, II, III αριστερά από το αντίστοιχο κουτάκι, και αιτιολογήστε τα συνοπτικά παρακάτω. Προσοχή: Μην επιχειρήσετε να αιτιολογήσετε περισσότερες ερωτήσεις γιατί δεν θα θα ληφθούν υπόψη. Οι απαντήσεις πρέπει να είναι επαρκείς και [κομμένο]
Αν έχετε επιλέξει ότι είναι όλα σωστά ή όλα λάθος, τότε πρέπει να επιλέξετε 3 από τις ερωτήσεις που δεν είναι του τύπου όλα σωστά ή όλα λάθος και να τις απαντήσετε.
ΑΠΑΝΤΗΣΗ ΥΠΟΕΡ. I (σημειώστε ποιο είναι στην προηγούμενη ερώτηση):
ΑΠΑΝΤΗΣΗ ΥΠΟΕΡ. II (σημειώστε ποιο είναι στην προηγούμενη ερώτηση):
IMG_4163.jpg¶
[δυσανάγνωστο: το πάνω μέρος της σελίδας είναι κομμένο]
...προηγούμενο ερώτημα, επιλέξτε ακριβώς 3 υποερωτήματα που απαντήσατε καλύτερα και σημειώστε τους λατ. αριθμούς I, II, III αριστερά από το αντίστοιχο κουτάκι. Προσοχή: Μην επιχειρήσετε να αιτιολογήσετε περισσότερες ερωτήσεις γιατί δεν θα θα ληφθούν υπόψη. Οι απαντήσεις πρέπει να είναι επαρκείς και όχι απλά αναδιατύπωση της εκφώνησης. Αν έχετε επιλέξει ότι είναι όλα σωστά ή όλα λάθος, τότε πρέπει να επιλέξετε 3 από τις ερωτήσεις που δεν είναι του τύπου όλα σωστά ή όλα λάθος και να τις απαντήσετε.
ΑΠΑΝΤΗΣΗ ΥΠΟΕΡ. I (σημειώστε ποιο είναι στην προηγούμενη ερώτηση):
[δυσανάγνωστο: το τμήμα της απάντησης είναι καλυμμένο]
ΑΠΑΝΤΗΣΗ ΥΠΟΕΡ. II (σημειώστε ποιο είναι στην προηγούμενη ερώτηση):
[δυσανάγνωστο: το τμήμα της απάντησης είναι καλυμμένο]
ΑΠΑΝΤΗΣΗ ΥΠΟΕΡ. III (σημειώστε ποιο είναι στην προηγούμενη ερώτηση):
[δυσανάγνωστο: το τμήμα της απάντησης είναι καλυμμένο]
Ερώτηση 6 (15β) Δίνονται
Να αποδείξετε ποιός είναι ο μέγιστος αριθμός επαναλήψεων που θα απαιτήσει η (πλήρης) GMRES για την επίλυση του \(Tx = y\) με τα δεδομένα που αναφέρθηκαν; (Υπόδ. θα είναι πολύ μικρότερος του 2n).
ΑΠΑΝΤΗΣΗ:
file-4BuMfRHjFTdpKdUWHa3Rq3.png¶
Ερώτηση 4 (20β)
Δίνονται το διάνυσμα και τα μητρώα: \(\ell = \begin{pmatrix} -2 \\ 2 \end{pmatrix}\), \(U = \begin{pmatrix} -2 & -\frac{1}{2} \\ 1 & 2 \end{pmatrix}\), \(V = \begin{pmatrix} 4 & 3 \\ 2 & 1 \\ -5 & -6 \end{pmatrix}\), \(W = \begin{pmatrix} 0 & 2 \\ 0 & 2 \end{pmatrix}\). Αυτά χρησιμοποιούμε για να ορίσουμε την αναπαράσταση Kruskal
όπου ως συνήθως, \(\lambda_i, u_i, v_i, w_i\) είναι στοιχεία και στήλες των \(\ell, U, V, W\).
- Να υπολογίσετε το \(T_{2,:,:}\) και να γράψετε το αποτέλεσμα.
Screenshot_20250129_182237_Discord.jpg¶
[Κείμενο κομμένο στα άκρα της φωτογραφίας· το παρακάτω είναι μόνο τα ορατά τμήματα.]
Κάτω αριστερά στο σχήμα δίνεται το [κομμένο]πο σχήμα, δίνονται οι αριθμημένες κορυφές του γραφή[κομμένο]
[κομμένο]το παραπάνω γράφημα με (μη κατευθυνόμενες) ακμές, [κομμένο] [κομμένο]ώστε το σχήμα να περιέχει το γράφημα του μητρώου (πλην [κομμένο]
[κομμένο]παραπάνω γράφημα με (μη κατευθυνόμενες) ακμές, παρα[κομμένο] [κομμένο]τε το σχήμα να περιέχει το γράφημα του μητρώου (πλην [κομμένο]
[Σχήμα: γράφημα με αριθμημένες κορυφές 1–6· ορισμένες ακμές είναι χρωματισμένες με πράσινο και κόκκινο, με σημάδια ίσης (πιθανώς χειρόγραφες σημειώσεις πάνω στο σχήμα). Το κάτω τμήμα του σχήματος καλύπτεται από γραμμή εργαλείων τηλεφώνου.]
[κομμένο]ον πίνακα με τα στοιχεία της αναπαράστασης CSC του [κομμένο]nters της αραιής αναπαράστασης). Προσοχή: Κάθε υποπίν[κομμένο]ις (στήλες). Εσείς ξεκινάτε από την πρώτη στήλη, και αφ[κομμένο]ες θέσεις δεν χρειάζονται.
[Πίνακας: μόνο τμήμα, η αριστερή στήλη είναι κομμένη. Ορατές γραμμές:]
[κομμένο] 5 5 0 3 0
[κομμένο] 26 0 0 0 0
[κομμένο] 0 26 0 0 0
[κομμένο] 0 0 21 0 0
[κομμένο] 0 0 0 24 0
[κομμένο] 0 0 0 0 21
Χωρίς να υπολογίσετε το \(R\), βρείτε σε ποιες θέσεις αυτό[κομμένο] αποκλειστικά με πράξεις επί του γραφήματος (π.χ. προσ[κομμένο] γράμμιση). Με βάση αυτό, ξαναγράψτε και συμπληρώστε [κομμένο]αραιή αναπαράσταση του \(A\) συμπεριλαμβάνοντας στο VAL[κομμένο]
[Πίνακας δυσανάγνωστος: ορατοί αριθμοί 34, 5, 5, 3, 5, 26, 5, 26, 21, 3, 24 (πρώτη γραμμή), 1, 2, 3, 4, 5, 6 (δεύτερη γραμμή), 7, 9, 10, 12, 13 (τρίτη γραμμή)· επικαλυμμένος από γραμμή εργαλείων τηλεφώνου.]
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.