Πληροφορική Ι — Εβδομάδα 10

Αριθμητικός Υπολογισμός, Γραφήματα και Προσομοιώσεις

Προσέγγιση του π: Monte Carlo

Τυχαία δειγματοληψία → αριθμητική εκτίμηση. Σύγκλιση \(\sim 1/\sqrt{n}\) (αργή).

matplotlib, βαθύτερα

Τα βασικά (plot/scatter/bar) από την Εβδομάδα 1. Εδώ: πολλαπλές σειρές, λογαριθμικές κλίμακες, imshow.

Monte Carlo, οπτικά

Η μέθοδος του Αρχιμήδη

Παγιδεύει το \(\pi\) ανάμεσα σε περίμετρο εγγεγραμμένου/περιγεγραμμένου πολυγώνου:

Ρυθμός σύγκλισης: Αρχιμήδης

Ευθεία γραμμή σε λογαριθμική κλίμακα = εκθετική σύγκλιση.

float32 έναντι float64

double: 53 bits significand ≈ 15-17 δεκαδικά ψηφία. single: 24 bits ≈ 7.

Σύγκριση σφαλμάτων

float32 “κολλάει” — απώλεια σημαντικών ψηφίων (catastrophic cancellation).

Newton-Raphson

Γενική μέθοδος: δουλεύει για οποιαδήποτε παραγωγίσιμη \(f\).

Διχοτόμηση (bisection)

Δεν χρειάζεται παράγωγο· εγγυημένη σύγκλιση, αλλά πιο αργή (γραμμική).

Σειρές Taylor

Προσέγγιση συνάρτησης με πεπερασμένο άθροισμα όρων.

Σύγκλιση Taylor, οπτικά

Monte Carlo: πρόβλημα γενεθλίων

Σύγκριση προσομοίωσης με ακριβή, κλειστό τύπο.

Monte Carlo: ολοκλήρωση

Γενικεύεται εύκολα σε πολλές διαστάσεις.

Monte Carlo: Monty Hall

Μιγαδικοί αριθμοί & Mandelbrot

\(z_0=0,\ z_{n+1}=z_n^2+c\) — φραγμένο ή όχι; βήμα-βήμα:

def mandelbrot_escape(c, max_iter):
    z = 0
    for n in range(max_iter):
        if abs(z) > 2:
            return n
        z = z * z + c
    return max_iter

Οπτικοποίηση Mandelbrot

Αλγόριθμος χρόνου διαφυγής (escape-time) πάνω σε πλέγμα σημείων.

Σύνοψη

• Προσομοίωση Monte Carlo · Γραφήματα με matplotlib
• Επαναληπτικές μέθοδοι σύγκλισης (Αρχιμήδης)
• float32 έναντι float64, σφάλματα στρογγύλευσης
• Newton-Raphson, διχοτόμηση — εύρεση ρίζας συνάρτησης
• Προσέγγιση με πεπερασμένο άθροισμα όρων (Taylor)
• Monte Carlo σε προβλήματα πιθανότητας
• Αλγόριθμος χρόνου διαφυγής (Mandelbrot)

⤺ Πλήρεις σημειώσεις  ·  Πρόγραμμα μαθήματος