Επιστημονικός Υπολογισμός — Σεπτέμβριος 2025¶
Μεταγραφή από τα αρχεία: themata_Sep_2025.pdf.
themata_Sep_2025.pdf¶
Θέματα Σεπτεμβρίου 2025¶
Ερώτηση 1 – Διακριτοποίηση Διαφορικής Εξίσωσης¶
Ήταν μια άσκηση παρόμοια με την παρακάτω με την διαφορά ότι ζητούσε την υπ’ αριθμό 1η εξίσωση.
[Φωτογραφία παλαιότερου θέματος, Ερώτηση 3 (25β)]
Δίνεται η διαφορική εξίσωση \(-u_{xx}+3xu_x+(x+5)u=4x\) στο διάστημα \(D=[3,4]\) με συνοριακές συνθήκες \(u(3)=0.0000\), \(u(4)=1.0000\). Διακριτοποιούμε με κεντρισμένες πεπερασμένες διαφορές και πλέγμα 37 κόμβων στο \(D\), όπου \(x_0=3\), \(x_{36}=4\) και οι υπόλοιποι 35 κόμβοι είναι εσωτερικοί στο \(D\). Όλοι οι κόμβοι ισαπέχουν. Το διάνυσμα των αγνώστων συμβολίζουμε με \(U=[U_1,U_2,\dots,U_{35}]^T\). Να γράψετε την υπ' αριθμ. 35 εξίσωση του γραμμικού συστήματος που προκύπτει από τη διακριτοποίηση. Προσοχή: Για να είναι αποδεκτοί, οι συντελεστές πρέπει να γραφτούν σε δεκαδική μορφή, δηλ. πρόσημο, ακέραιο μέρος και 4 δεκαδικά ψηφία δεξιά της υποδιαστολής. Δεν πρέπει να χρειάζονται επιπλέον πράξεις για τον υπολογισμό τους.
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
Τα \(U_0\), \(h\), \(b(x_1)\), \(c(x_1)\), \(d(x_1)\) μπορούν να βρεθούν.
Η τελική εξίσωση θα είναι της μορφής: \(aU_1 + bU_2 = c\)
Ερώτηση 2 – Σ/Λ¶
-
Αν \(n=1000+\text{randi}(1000,1)\); \(D=\text{diag}(\text{rand}(n,1))\); \(u=\text{randn}(n,1)\); \(v=u.*u\);, τότε \(u^T(D+uv^T)^{-1}v\) μπορεί να υπολογιστεί σε \(O(n)\) πράξεις.
-
Αν μητρώα A και B είναι ορθογώνιο τότε το A∘B (γινόμενο Hadamard) είναι επίσης ορθογώνιο μητρώο.
-
Ένα βασικό πλεονέκτημα της BiCG έναντι της CGS (CG squared) είναι ότι η πρώτη σε αντίθεση με τη δεύτερη μπορεί να χρησιμοποιηθεί για την επίλυση μη συμμετρικών συστημάτων.
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
Ερώτηση 3 – Γράφος μητρώου, fill-in, profile¶
[Σχήμα: χειρόγραφο γράφημα με 7 κόμβους, αριθμημένους 1 έως 7, μέσα σε πλαίσιο· δεν σχεδιάζονται ακμές. Η φωτογραφία φέρει την ένδειξη «(20β)».]
Κάτω από την επικεφαλίδα, οι 3 γραμμές του πίνακα παρακάτω περιέχουν τις τιμές, τον αριθμό γραμμής και τον δείκτη στήλης της αναπαράστασης CSC ενός \(A \in \mathbb{R}^{7\times 7}\). Όπου βλέπετε Inf στη γραμμή των δεικτών αγνοήστε το (θεωρήστε ότι η θέση είναι κενή). Το μητρώο είναι συμμετρικό θετικά ορισμένο και έχει επίσης αποθηκευτεί σε μορφή sparse στη MATLAB με όνομα μεταβλητής A.
| VAL, ROW_IDX, COL_PTR | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 17 | 9 | 7 | 38 | 19 | 18 | 9 | 27 | 15 | 2 | 19 | 15 | 35 | 18 | 2 | 21 | 7 | 8 |
| 1 | 2 | 4 | 7 | 3 | 5 | 6 | 2 | 4 | 5 | 6 | 3 | 4 | 5 | 3 | 4 | 6 | 2 | 7 |
| 1 | 2 | 5 | 8 | 12 | 15 | 18 | 20 | Inf | Inf | Inf | Inf | Inf | Inf | Inf | Inf | Inf | Inf | Inf |
-
Συμπληρώστε το παραπάνω γράφημα με (μη κατευθυνόμενες) ακμές, παραλείποντας τους αυτοβρόχους, ώστε να είναι το γράφημα του μητρώου.
-
Έστω ότι καλούμε \(A = \text{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: γραμμή \(i\) και γραμμή \(j\), με κενά κελιά όσα χρειάζονται.]
- Αν στη συνέχεια δοθεί η εντολή \(p = \text{symamd}(A)\), επιστρέφεται το διάνυσμα: \(p = (7\ 2\ 4\ 6\ 3\ 5\ 1)\). Να συμπληρώσετε τις τιμές του μητρώου \(A(p,p)\):
[Κενό πλέγμα απάντησης: μήτρα \(A(p,p)\).]
- Για τα συγκεκριμένα \(A\), \(p\) να υπολογίσετε την τιμή της κατανομής (profile) του \(A(p,p)\).
Ερώτηση 4 – Τανυστής Kruskal¶
Έπεσε άσκηση ίδια με την παρακάτω, με την διαφορά ότι ζητούσε το \(T_{:,:,2}\).
[Φωτογραφία παλαιότερου θέματος, Ερώτηση 4 (20β)]
Δίνονται το διάνυσμα και τα μητρώα: \(\ell=\begin{pmatrix}-2\\2\end{pmatrix}\), \(U=\begin{pmatrix}-2 & -1\\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
\[T=[\![\ell;U,V,W]\!]=\sum_i \lambda_i u_i\circ v_i\circ w_i\]όπου ως συνήθως, \(\lambda_i, u_i, v_i, w_i\) είναι στοιχεία και στήλες των \(\ell, U, V, W\).
- Να υπολογίσετε το \(T_{2,:,:}\) και να γράψετε το αποτέλεσμα.
\(T_{2,:,:}=\left(\ \ \right)\)
Ερώτηση 5 – Matlab, Αριθμός Πράξεων¶
Έστω ένα κάτω Hessenberg μητρώο \(A\in R^{n\times n}\) και ένα τριδιαγώνιο μητρώο \(B\in R^{n\times n}\). Θεωρούμε το γινόμενο \(C= AB\).
α) Προσδιορίστε τη δομή του προκύπτοντος μητρώου \(C\).
β) Γράψτε ένα αποδοτικό script σε Matlab που υπολογίζει το γινόμενο \(C= AB\), λαμβάνοντας υπόψιν τις ειδικές δομές των \(A\) και \(B\) για την ελαχιστοποίηση των περιττών υπολογισμών.
γ) Υπολογίστε τον προσεγγιστικό αριθμό πράξεων (FLOPS), που συμβολίζεται με Ω, που απαιτεί ο αλγόριθμος σας από το ερώτημα β) για μεγάλο \(n\). Εκφράστε την απάντηση σας συναρτήσει του \(n\).