Επιστημονικός Υπολογισμός — Ιούνιος 2022¶

Μεταγραφή από τα αρχεία: 1.jpg, 2.jpg, 5.jpg, 3.jpg, 7.jpg. Τα 4.jpg και 6.jpg είναι αντίγραφα και χρησιμοποιήθηκαν μόνο για επιβεβαίωση.

1.jpg¶

Ερώτηση 1 (20β) Τα επόμενα διανύσματα περιγράφουν ένα 4x4 μητρώο Α σε μορφή csc: val = (6 3 5 8 4 9) row_idx = (1 4 2 3 1 4), col_ptr = (1 3 4 5 7) Συμπληρώστε τις σωστές τιμές παρακάτω:

[ ] $A(1,2) =$
[ ] $A(2,3) =$
[ ] $A(4,4) =$
[ ] $A(3,1) =$

Ερώτηση 2 (6β) Αν το nxn μητρώο Α είναι άνω Hessenberg, το n μεγάλο και τα n διάστατα διανύσματα (στήλες) x, y τέτοια ώστε το $A+xy^T$ είναι αντιστρέψιμο, ο υπολογισμός του $(A+xy^T)^{-1} \cdot y$:

[ ] χρειάζεται $O(n^2)$ πράξεις α.κ.υ.
[ ] χρειάζεται $O(n^3)$ πράξεις α.κ.υ.
[ ] χρειάζεται $O(n)$ πράξεις α.κ.υ.

Ερώτηση 3 (20β) Αν το παρακάτω γράφημα γειτνίασης αντιστοιχεί σε ΣΘΟ μητρώο (έχουν εξαιρεθεί οι αυτοβρόχοι που αντιστοιχούν στα διαγώνια στοιχεία) να γράψετε στον παρακάτω πίνακα, 1 σε όλες τις θέσεις στις οποίες ο κάτω τριγωνικός παράγοντας Cholesky L του A αναμένεται να μην περιέχει 0. Στον πίνακα έχει γίνει ήδη αρχικοποίηση με 1 στις θέσεις της διαγωνίου που γνωρίζουμε ότι θα είναι μη μηδενικές.

[Σχήμα: Μη κατευθυνόμενο γράφημα γειτνίασης με 6 κορυφές αριθμημένες 1 έως 6 και ακμές μεταξύ τους]

2.jpg¶

Πίνακας για την Ερώτηση 3 (τα κενά κουτιά είναι κενά· οι 1 της διαγωνίου είναι ήδη συμπληρωμένα):

0	0	0	0	0
1	0	0	0	0
	1	0	0	0
		1	0	0
			1	0
				1

Ερώτηση 4 (8β) Διακριτοποιούμε τη Δ.Ε. $-u_{xx} + a \cdot u_x = 0$ με κεντρισμένες πεπερασμένες διαφορές στο διάστημα $(1, 2)$ με συνοριακές συνθήκες $u(1)=1, u(2)=-1$ και πλέγμα με $n=19$ εσωτερικούς ισαπέχοντες κόμβους όπου $a=100$. Να γράψετε Χ στα κουτάκια για όποιες επιλογές από τα παρακάτω ισχύουν για το μητρώο $A$ που θα προκύψει από τη διακριτοποίηση και για την επίλυση συστήματος $AU=f$ για δοθέν $f$:

[ ] διαγώνια κυρίαρχο
[ ] συμμετρικό
[ ] Toeplitz
[ ] επιλύσιμο με $O(n)$ πράξεις

Ερώτηση 5 (20β) $$T(:,:,1) = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}, T(:,:,2) = \begin{pmatrix} -1 & -1 \\ -1 & -1 \end{pmatrix}, T(:,:,3) = \begin{pmatrix} 3 & 4 \\ 0 & 4 \end{pmatrix}$$

Έστω επίσης ότι $A$ είναι το μητρώο που προέρχεται από το ξεδίπλωμα (μητρωοποίηση) του $T$ ως προς το 3-mode. Να απαντήσετε στα εξής:

Πόσες ίνες συνολικά έχει ο $T$;
Να υπολογίσετε το γινόμενο του $A$ με το διάνυσμα $e$ κατάλληλου μεγέθους με όλα τα στοιχεία μονάδες

\[Ae = \begin{pmatrix} \end{pmatrix}\]

5.jpg¶

Σημείωση: η φωτογραφία είναι χειρόγραφη και κομμένη στο αριστερό άκρο. Τα ονόματα μεταβλητών που λείπουν (στην αρχή των γραμμών) συμπληρώθηκαν από το 6.jpg, όπου η ίδια σελίδα φαίνεται ολόκληρη [συμπληρώθηκε από 6.jpg].

Ερώτηση 6 (20β)

Έστω μητρώο $A \in \mathbb{R}^{n \times n}$, με $n \geq 10$, του οποίου οι τιμές προκύπτουν ως:

A(i,j) = randi(n), αν j ≥ i

A(i,j) = 0, αλλιώς

Έστω επίσης ότι εκτελούνται οι ακόλουθες εντολές Matlab:

u = A(:,4); T = A + u*u;
f = nnz(T); b = sum(T,2);
k1 = A\b; k2 = A\u;
x1 = k1 - (k2 * (u' * k1)) / (1 + u' * k2);
r = norm(x1 - eye(n,1), inf);

Σημείωση: στο περιθώριο υπάρχει χειρόγραφη σημείωση «backslash» με βέλος προς τις εντολές k1 και k2· η αριστερή διαίρεση δεν είναι καθαρά ορατή στο πρωτότυπο και γράφεται εδώ ως A\b και A\u [δυσανάγνωστο: το σύμβολο «\» στις εντολές k1 και k2]. Οι εντολές k1 και k2 και τα ονόματα x1, r συμπληρώθηκαν από το 6.jpg [συμπληρώθηκε από 6.jpg].

Να συμπληρώσετε τις σωστές απαντήσεις σχετικά με τις αναμενόμενες τιμές των παρακάτω μεταβλητών:

□ r =

□ f =

Ερώτηση 7 (6β)

Δίνεται η διαφορική εξίσωση $\frac{du}{dt} = Au(t)$, $u(0) = g$, για γνωστό πυκνό μητρώο $A \in \mathbb{R}^{n \times n}$, $u, g \in \mathbb{R}^n$. Αν το μητρώο $A$ είναι αρκετά μεγάλο και εφαρμόζεται έμπρος Euler για την αριθμητική επίλυση της διαφορικής με σταθερό βήμα $h$ από το $0$ έως το $T$, ποιά από τις παρακάτω εκφράσεις εκπροσωπεί καλύτερα το κόστος του αριθμητικού υπολογισμού του $u(T)$;

[ ] $O\left(\left(\frac{T}{h}\,n\right)^2\right)$
[ ] $O\left(\frac{T}{h}\, n^{2}\right)$
[ ] $O\left(\frac{T}{h}\, n^{3}\right)$

3.jpg¶

[Λείπει από τη φωτογραφία: επάνω άκρο με την αρχή της Ερώτησης 6]

Η φωτογραφία είναι αντίγραφο της σελίδας 3 με κομμένο επάνω άκρο. Το πλήρες κείμενο των Ερωτήσεων 6 και 7 μεταγράφεται στο τμήμα «5.jpg» παραπάνω· ο ορισμός του A (randi(n) για j ≥ i, 0 αλλιώς) και οι εντολές Matlab συμφωνούν με αυτό.

7.jpg¶

[Λείπει από τη φωτογραφία: αρχή της γραμμής «Έστω μητρώο A ∈ R^{n×n}» (επάνω άκρο κομμένο) και αριστερή στήλη των μεταβλητών]

Αντίγραφο της σελίδας 3 (Ερώτηση 6 και Ερώτηση 7). Το πλήρες κείμενο μεταγράφεται στο τμήμα «5.jpg» παραπάνω. Τα πλαίσια απαντήσεων (r =, f =) είναι κενά.

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2022-06¶

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

Θέμα 1¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Από τον CSC πίνακα (1-based): - στήλη 1: $A(1,1)=6,\ A(4,1)=3$ - στήλη 2: $A(2,2)=5$ - στήλη 3: $A(3,3)=8$ - στήλη 4: $A(1,4)=4,\ A(4,4)=9$

Άρα: - $A(1,2)=0$ - $A(2,3)=0$ - $A(4,4)=9$ - $A(3,1)=0$

Θέμα 2¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Σωστή επιλογή: χρειάζεται $O(n^2)$ πράξεις α.κ.υ.

Με Sherman–Morrison για $B=A+xy^T$: [ B^{-1}y=A^{-1}y-A^{-1}x\,\frac{y^TA^{-1}y}{1+y^TA^{-1}x}. ] Το $A$ είναι άνω Hessenberg, άρα επίλυση γραμμικών συστημάτων με αυτό γίνεται σε $O(n^2)$. Τα υπόλοιπα γινόμενα είναι $O(n)$, οπότε συνολικά $O(n^2)$.

Θέμα 3¶

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Στην εικόνα 1.jpg (κάτω μέρος, Ερώτηση 3) φαίνεται ευκρινώς το μη κατευθυνόμενο γράφημα γειτνίασης του συμμετρικού θετικά ορισμένου (ΣΘΟ) μητρώου $A \in \mathbb{R}^{6 \times 6}$. Οι ακμές του γραφήματος (μηδενικά στοιχεία εκτός διαγωνίου στο $A$) είναι: - $(1, 2), (1, 3), (1, 4), (1, 6)$ - $(2, 5), (2, 6)$ - $(4, 5), (4, 6)$

Κατά την παραγοντοποίηση Cholesky $A = L L^T$ (με σειρά απαλοιφής $1, 2, 3, 4, 5, 6$), ένα στοιχείο $L_{ij} \neq 0$ ($i > j$) αν και μόνο αν υπάρχει μονοπάτι στο γράφημα μεταξύ $i$ και $j$ του οποίου όλοι οι ενδιάμεσοι κόμβοι έχουν δείκτη μικρότερο του $j$ (θεώρημα προσβασιμότητας / elimination game):

Στήλη 1 ($j=1$): Δεν υπάρχουν κόμβοι με δείκτη $<1$. Επομένως, $L_{i1} \neq 0$ μόνο αν υπάρχει άμεση ακμή $(i, 1)$ στο αρχικό γράφημα.
Ακμές με τον κόμβο 1 έχουν οι: 2, 3, 4, 6 $\implies L_{21}=1, L_{31}=1, L_{41}=1, L_{61}=1$.
Ο κόμβος 5 δεν συνδέεται με τον 1 $\implies L_{51}=0$.
Απαλοιφή κόμβου 1: Οι γείτονες του 1 με μεγαλύτερο δείκτη $\{2, 3, 4, 6\}$ συνδέονται μεταξύ τους (δημιουργία κλίκας / πλήρωση - fill-in). Εισάγονται ακμές πλήρωσης: $(2, 3), (2, 4), (3, 4), (3, 6)$. Τώρα για τη στήλη 2 ($j=2$): Όλοι οι κόμβοι $i \in \{3, 4, 5, 6\}$ συνδέονται με τον 2 είτε άμεσα (οι 6 και 5), είτε μέσω του κόμβου $1 < 2$ (οι 3 και 4). Άρα $L_{32}=1, L_{42}=1, L_{52}=1, L_{62}=1$.
Απαλοιφή κόμβου 2: Οι γείτονες του 2 με μεγαλύτερο δείκτη $\{3, 4, 5, 6\}$ συνδέονται μεταξύ τους, εισάγοντας ακμές πλήρωσης $(3, 5)$ και $(5, 6)$. Για τη στήλη 3 ($j=3$): Όλοι οι κόμβοι $i \in \{4, 5, 6\}$ έχουν μονοπάτι προς τον 3 μέσω των $\{1, 2\} < 3$. Άρα $L_{43}=1, L_{53}=1, L_{63}=1$.
Στήλες 4 και 5 ($j=4, 5$): Όλοι οι εναπομείναντες κόμβοι είναι πλήρως συνδεδεμένοι. Άρα $L_{54}=1, L_{64}=1$ και $L_{65}=1$.

Συνεπώς, όλες οι θέσεις του κάτω τριγωνικού μέρους του $L$ γεμίζουν με μονάδες εκτός από τη θέση $(5, 1)$ που παραμένει $0$.

Ο συμπληρωμένος πίνακας είναι:

1	0	0	0	0	0
1	1	0	0	0	0
1	1	1	0	0	0
1	1	1	1	0	0
0	1	1	1	1	0
1	1	1	1	1	1

Θέμα 4¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Είναι $h=\frac{1}{20}=0.05$ και $\frac{ah}{2}=\frac{100}{40}=2.5$. Με κεντρισμένες διαφορές προκύπτει τριδιαγώνιο μητρώο με σταθερές διαγωνίους (μετά από κλιμάκωση): [ A=\operatorname{tridiag}(-3.5,\ 2,\ 1.5). ] Άρα: - [ ] διαγώνια κυρίαρχο: όχι, αφού $3.5+1.5>2$. - [ ] συμμετρικό: όχι, αφού οι υποδιαγώνιος και υπερδιαγώνιος διαφέρουν. - [x] Toeplitz: ναι, οι διαγώνιοι είναι σταθερές. - [x] επιλύσιμο με $O(n)$ πράξεις: ναι, είναι τριδιαγώνιο.

Σωστά: Toeplitz και επιλύσιμο με $O(n)$ πράξεις.

Θέμα 5¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Το $T$ έχει διαστάσεις $2\times2\times3$. Συνολικά: [ 2\cdot3+2\cdot3+2\cdot2=6+6+4=16 ] ίνες. (Οι ίνες 3ης τάξης είναι $2\cdot2=4$.)
Με τη συνήθη σύμβαση $A=T_{(3)}\in\mathbb R^{3\times4}$, όπου οι mode-3 ίνες γίνονται στήλες: [ A= \begin{pmatrix} 1&1&1&1\ -1&-1&-1&-1\ 3&0&4&4 \end{pmatrix}, ] και για $e=(1,1,1,1)^T$: [ Ae= \begin{pmatrix} 4\ -4\ 11 \end{pmatrix}. ]

Θέμα 6¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Θεωρώ $T=A+uu^T$, όπως επιβάλλει ο τύπος Sherman–Morrison (το γραμμένο u*u δεν ορίζεται στο MATLAB για στήλη $u$).

Το $u=A(:,4)$ έχει μη μηδενικά μόνο στις θέσεις $1,\dots,4$. Το $uu^T$ προσθέτει μη μηδενικά στις 6 κάτω-τριγωνικές θέσεις του $4\times4$ άνω αριστερά μπλοκ. Άρα: [ f=\operatorname{nnz}(T)=\frac{n(n+1)}{2}+6. ]
Επειδή $b=\sum(T,2)=T\mathbf 1$, η λύση είναι $x=\mathbf 1$. Το eye(n,1) είναι το $e_1=(1,0,\dots,0)^T$, άρα [ r=|x_1-e_1|_\infty=1. ]

Απαντήσεις: - $r=1$ - $f=\dfrac{n(n+1)}{2}+6$

Θέμα 7¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Σωστή επιλογή: $O\!\left(\frac{T}{h}\,n^2\right)$.

Ο έμπρος Euler κάνει $N=\frac{T}{h}$ βήματα. Κάθε βήμα απαιτεί ένα γινόμενο πυκνού $n\times n$ μητρώου με διάνυσμα, δηλαδή $O(n^2)$ πράξεις. Συνολικό κόστος: [ O!\left(\frac{T}{h}n^2\right). ]

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή