Στην Εργασία 1 δοκιμάσαμε να γράψουμε ένα πρόγραμμα που έβρισκε αυτόματα ρίζες σε πολυώνυμα, αλλά δυστυχώς δεν είχαν όλα τα πολυώνυμα ρίζες. Για παράδειγμα, το πολυώνυμο \(x^2 + 1\) δεν είχε ρίζες καθώς η διακρίνουσα είναι αρνητική. Με τους φανταστικούς αριθμούς όμως, όπου η φανταστική μονάδα \(i\) όταν υψωθεί στο τετράγωνο μας κάνει −1 (\(i^2 = -1\)), μπορούμε να πούμε ότι το \(x = i\) είναι μια ρίζα του παραπάνω πολυωνύμου. Αντίστοιχα, μπορεί η ρίζα ενός πολυωνύμου να είναι ένας συνδυασμός πραγματικών και φανταστικών, δηλαδή κάτι που ονομάζεται μιγαδικός αριθμός (complex number).
Θα δοκιμάσουμε να βρούμε λύσεις σε πολυώνυμα στο μιγαδικό επίπεδο. Η μέθοδος Newton παραμένει η ίδια, απλά αλλάζουμε τον ορισμό του τύπου που παίρνει η f: Δεδομένης μιας μιγαδικής συνάρτησης \(f(z)\) και της παραγώγου της \(f'(z)\), ξεκινώντας με ένα τυχαίο \(z_0\) μία καλύτερη προσέγγιση μιας ρίζας του πολυωνύμου \(z_1\) δίνεται από την σχέση:
\[z_1 = z_0 - \frac{f(z_0)}{f'(z_0)}\]Αντίστοιχα, η γενική αναδρομική σχέση της μεθόδου του Νεύτωνα είναι:
\[z_{n+1} = z_n - \frac{f(z_n)}{f'(z_n)}\]όπου \(z_{n+1}\) είναι η προσεγγιστική τιμή μιας ρίζας της συνάρτησης \(f(z)\) μετά από \(n + 1\) επαναλήψεις. Σε αντίθεση με την προηγούμενη άσκηση, όλες οι πράξεις που κάναμε με αριθμούς κινητής υποδιαστολής και μας δίνονταν ως βασικοί τελεστές (built in primitives/operators), τώρα θα πρέπει να οριστούν και να υλοποιηθούν για complex αριθμούς. Κάποιες από τις βασικές πράξεις για μιγαδικούς που μπορεί να χρειαστείτε περιλαμβάνουν (ελέγξτε την ορθότητά τους για την αποφυγή ορθογραφικών με άλλες πηγές):
\[(a + bi) + (c + di) = (a + c) + (b + d)i\] \[(a + bi) \cdot (c + di) = (ac - bd) + (ad + bc)i\] \[\frac{a + bi}{c + di} = \frac{ac + bd}{c^2 + d^2} + \frac{bc - ad}{c^2 + d^2}i\] \[|a + bi| = \sqrt{a^2 + b^2}\]Για κάθε αρχικό \(z_0\), η μέθοδος Newton μπορεί να βρει μια ρίζα του πολυωνύμου - χωρίς να μπορούμε να προβλέψουμε ποια - και οι υπόλοιπες ρίζες μας διαφεύγουν. Μια συχνή λύση για να βρούμε περισσότερες ρίζες είναι να δοκιμάσουμε πολλά και διαφορετικά \(z_0\) και να τρέξουμε πολλές φορές την μέθοδο Newton.
Για το ζητούμενο αυτής της άσκησης, καλείστε να γράψετε ένα πρόγραμμα που υπολογίζει αυτόματα τις ρίζες (τα z για τα οποία μηδενίζεται) οποιουδήποτε πολυωνύμου για ένα σύνολο από μιγαδικούς προκειμένου να μπορούμε να εντοπίσουμε περισσότερες από μία ρίζες.
Τεχνικές Προδιαγραφές
progintro/hw3-<YourTeamName>fractal/src/complexlib.c - το αρχείο στο οποίο θα βρίσκεται η
υλοποίηση για όλες τις βασικές πράξεις με μιγαδικούς: πρόσθεση, αφαίρεση, διαίρεση
κτλ.fractal/src/complexlib.h - το αρχείο κεφαλίδων στο οποίο θα
βρίσκονται οι δηλώσεις όλων των βασικών συναρτήσεων μιγαδικών που υλοποιήσατε.fractal/src/fractal.c - το αρχείο στο οποίο θα βρίσκεται η main
σας και θα κάνει include το "complexlib.h" προκειμένου να χρησιμοποιήσει όλες τις
συναρτήσεις μιγαδικών που θα χρειαστείτε../fractal filename. Για το περιεχόμενο του αρχείου δείτε παρακάτω. Αν το αρχείο δεν
μπορεί να ανοιχτεί το πρόγραμμα πρέπει να επιστρέφει με κωδικό εξόδου (exit code) 1.Η βασική είσοδος για το πρόγραμμα θα είναι μέσω των περιεχομένων του αρχείου (το όνομα του αρχείου θα δίνεται ως πρώτο όρισμα όπως αναφέρθηκε παραπάνω). Το αρχείο θα έχει την ακόλουθη μορφή:
POLYNOMIAL_DEGREE_N
A0 A1 A2 ... AN
MIN_REAL MIN_IMAG MAX_REAL MAX_IMAG STEP
Η πρώτη γραμμή περιέχει τον βαθμό του πολυωνύμου. Η δεύτερη περιέχει τους πραγματικούς όρους του πολυωνύμου γραμμένους ως double. Η τρίτη και τελευταία γραμμή περιέχει δύο double όρους που καθορίζουν το παράθυρο μέσα στο οποίο θα αναζητήσουμε λύσεις με την μέθοδο Newton (δες παρακάτω στην ενδεικτική λύση). Για παράδειγμα, για ένα πολυώνυμο 5ου βαθμού \(0.0 + 1.0x + 2.0x^2 + 3.0x^3 + 4.0x^4 + 5.0x^5\) και μέγεθος παραθύρου το \([-1.0 - i, 1.01 + 1.01i]\) με βήμα 0.1 η είσοδος θα είναι:
5
0.0 1.0 2.0 3.0 4.0 5.0
-1.0 -1.0 1.01 1.01 0.1
double και επαρκούς ακρίβειας
ώστε να χωράνε σε μεταβλητές double. Συνιστούμε να χρησιμοποιήσετε την συνάρτηση
βιβλιοθήκης fscanf για να διαβάσετε τους αριθμούς από το αρχείο με τους κατάλληλους
μετατροπείς.Η λύση σας πρέπει να κάνει χρήση ενός τύπου complex προκειμένου να μοντελοποιήσει
τους μιγαδικούς αριθμούς. Περιμένουμε ότι ο ορισμός του τύπου θα έχει αυτήν την μορφή:
typedef struct {
double real;
double imag;
} complex;
Το αρχείο C που θα υποβληθεί πρέπει να μεταγλωττίζεται χωρίς ειδοποιήσεις για λάθη και με κωδικό επιστροφής (exit code) που να είναι 0. Συγκεκριμένα, το αρχείο σας πρέπει να μπορεί να μεταγλωττιστεί επιτυχώς με τις ακόλουθες εντολές σε ένα από τα μηχανήματα του εργαστηρίου (linuxXY.di.uoa.gr):
gcc -Ofast -Wall -Wextra -Werror -pedantic -c -o complexlib.o complexlib.c
gcc -Ofast -Wall -Wextra -Werror -pedantic -c -o fractal.o fractal.c
gcc -o fractal complexlib.o fractal.o -lm
fractal/README.mdfractal/test/inputfractal/test/outputnan.incomplete.complex.h, η χρήση του τύπου _Complex κτλ. Θέλουμε όλες οι πράξεις να οριστούν από
εσάς και να βασίζονται στον τύπο complex που ορίσαμε παραπάνω.Έστω ότι θέλουμε να βρούμε τις λύσεις της Newton-Raphson για το πολυώνυμο \(1 + z - z^3 + z^4\) για τα ακόλουθα \(z_0\): \(\{-1 - i, -1 + 0i, -1 + i, 0 - i, 0, 0 + i, 1 - i, 1, 1 + i\}\), δηλαδή θέλουμε να σαρώσουμε όλους τους μιγαδικούς από το \(-1 - i\) μέχρι το \(1 + i\) με βήμα 1. Παρακάτω παραθέτουμε την αλληλεπίδραση με μια ενδεικτική λύση:
$ cat input
4
1.0 1.0 0.0 -1.0 1.0
-1.0 -1.0 1.01 1.01 1.0
$ ./fractal input
-0.57-0.46i incomplete -0.57+0.46i
+1.07-0.86i incomplete +1.07+0.86i
+1.07-0.86i incomplete +1.07+0.86i
όπου βλέπουμε ότι για \(z_0 = -1 - i\) (το πρώτο στοιχείο της πρώτης σειράς) η Newton συγκλίνει στην ρίζα \(-0.57 - 0.46i\), ενώ για \(z_0 = 0\) το αποτέλεσμα είναι incomplete (το 2ο στοιχείο της 2ης σειράς). Επομένως το αποτέλεσμα είναι ένας δισδιάστατος πίνακας με τις ρίζες στις οποίες αποτιμάται το πολυώνυμο για τα διάφορα \(z_0\):
| real/imag | -i | 0i | 1i |
|---|---|---|---|
| -1 | -0.57-0.46i | incomplete | -0.57+0.46i |
| +0 | +1.07-0.86i | incomplete | +1.07+0.86i |
| +1 | +1.07-0.86i | incomplete | +1.07+0.86i |
Το Σχήμα 3 της εκφώνησης δείχνει τα Newton fractals για το πολυώνυμο \(1 + z - z^3 + z^4\) από το \(-2 - 2i\) μέχρι το \(+2 + 2i\), και το ίδιο fractal με βήμα 5× μικρότερο: κάθε ρίζα έχει δικό της χρώμα.
Αντίστοιχα μπορούμε να αυξήσουμε την πυκνότητα των αποτελεσμάτων που ελέγχουμε σε ένα παράθυρο, μειώνοντας το βήμα (τους μιγαδικούς στο \([-0.2 + 0.2i, 0.21 + 0.51i]\) με βήμα 0.05). Για παράδειγμα:
$ cat input
4
1.0 1.0 0.0 -1.0 1.0
-0.2 0.2 0.21 0.51 0.05
$ ./fractal input
-0.57+0.46i -0.57+0.46i -0.57+0.46i -0.57+0.46i -0.57+0.46i -0.57+0.46i -0.57+0.46i
-0.57+0.46i -0.57+0.46i -0.57+0.46i -0.57+0.46i -0.57+0.46i -0.57+0.46i -0.57+0.46i
-0.57+0.46i -0.57+0.46i -0.57+0.46i -0.57+0.46i -0.57+0.46i -0.57+0.46i -0.57+0.46i
+1.07-0.86i -0.57+0.46i -0.57+0.46i -0.57+0.46i +1.07+0.86i -0.57-0.46i -0.57-0.46i
-0.57-0.46i +1.07-0.86i -0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i +1.07+0.86i
-0.57+0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i
-0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i
-0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i
-0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i -0.57-0.46i
Αν κοιτάξουμε προσεκτικά το παραπάνω βλέπουμε 4 διαφορετικές λύσεις, τις: \(-0.57 - 0.46i\), \(-0.57 + 0.46i\), \(+1.07 + 0.86i\) και \(+1.07 - 0.86i\) (πράγματι παρατηρούμε ότι \(f(-0.57 - 0.46i) = -0.00 - 0.00i\)) και επομένως καταφέραμε να βρούμε και τις τέσσερις ρίζες αυτού του πολυωνύμου! Η μόνη δυσκολία ίσως βρίσκεται στο να βρούμε τις περιοχές των μιγαδικών που πρέπει να σκανάρουμε.
Στο αρχείο README.md πρέπει να προσθέσετε οποιεσδήποτε παρατηρήσεις σας κατά την
διεκπεραίωση της άσκησης. Ο κώδικας απαιτείται να είναι καλά τεκμηριωμένος με σχόλια
καθώς αυτό θα είναι μέρος της βαθμολόγησης.
Αν συνεχίσουμε να μειώνουμε το βήμα από την είσοδο του fractal παραπάνω οι πίνακες γίνονται μεγάλοι γρήγορα και αυξάνοντας την ανάλυση (resolution) των αποτελεσμάτων βλέπουμε πως μια μικρή αλλαγή της τάξης του 0.01 σε μια διάσταση μπορεί να κάνει την μέθοδο Newton να συγκλίνει σε διαφορετική ρίζα. Αν πειραματιστούμε αρκετά και έχουμε υπομονή μπορεί να παρατηρήσουμε ότι οι ρίζες προκύπτουν επαναλαμβανόμενα με μια κανονικότητα που θυμίζει fractal. Ένας τρόπος να οπτικοποιήσουμε αυτήν την κανονικότητα είναι να δώσουμε ένα χρώμα στην κάθε διαφορετική λύση στην οποία συγκλίνει η Newton-Raphson και να βάλουμε όλα αυτά τα χρώματα σε ένα δισδιάστατο επίπεδο που αναπαριστά τις αρχικές τιμές του \(z_0\) στο πεδίο των μιγαδικών. Τα fractal που δημιουργούνται με αυτήν την μέθοδο λέγονται Newton Fractals. (Το Σχήμα 4 της εκφώνησης δείχνει ένα Newton fractal για το \(z^4 - 1\), όπου το βάθος των χρωμάτων υποδεικνύει πόσο γρήγορα συγκλίνει, σε αριθμό επαναλήψεων, το κάθε σημείο σε μια ρίζα.)
Σε αυτήν την επέκταση της προηγούμενης άσκησης, ο στόχος είναι να προσθέσετε την δυνατότητα στο πρόγραμμά σας να δημιουργεί fractal visualizations.
Τεχνικές Προδιαγραφές (Επέκταση της λύσης fractal)
"-g output.bmp", δηλαδή το όρισμα "-g" που ορίζει ότι θέλουμε graphical output και
το όρισμα που το ακολουθεί - π.χ., "output.bmp" - το οποίο είναι το αρχείο στο οποίο
θέλουμε να σώσουμε την οπτικοποίηση του fractal μας.fractal/data/input. Ένα αρχείο με πολυώνυμο που δοκιμάσατε να
οπτικοποιήσετε.fractal/data/output.bmp. Το αρχείο από Newton Fractal που οπτικοποίησε το
πρόγραμμά σας για το παραπάνω input.Ξεκινήστε από τη βιβλιοθήκη: ορίστε τον complex στο complexlib.h (με include guard)
μαζί με τα πρωτότυπα, υλοποιήστε και ελέγξτε κάθε πράξη χωριστά, και μόνο μετά γράψτε
τη Newton στο fractal.c. Υπολογίστε το πολυώνυμο και την παράγωγό του με τον κανόνα του
Horner πάνω σε μιγαδικούς, και προσέξτε τη σειρά σάρωσης: κάθε γραμμή της εξόδου
αντιστοιχεί σε ένα πραγματικό μέρος και κάθε στήλη σε ένα φανταστικό. Προσέξτε επίσης το
«μείον μηδέν» στην εκτύπωση και τη συσσώρευση σφάλματος όταν προσθέτετε το βήμα
επανειλημμένα· για το bonus, ξαναχρησιμοποιήστε ό,τι μάθατε για τη μορφή BMP στο
fauxtoshop.
Αριθμός στον οδηγό: Α23.6
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: hw-2023-hw3-fractal ·
Σύνδεσμος: https://progintro.github.io/study/questions/homework/hw-2023-hw3-fractal.html ·
Markdown (GitHub)