Programma di "Calcolo numerico e programmazione"

Cos'è un algoritmo?
Cos'è un programma?
Diagramma di flusso
Quali sono i tipi di istruzione?
Nomi di variabili e parole chiave
Cosa vuol dire l'asterisco nelle istruzioni?
Operazioni per mezzo standard
Cicli e contatori

Case sensitive?
Una istruzione per riga
Gli spazi separano dove la punteggiatura non c'è
Com'è composta la riga?
Label, carattere di continuazione, istruzioni, note
Perché questa formattazione?
Forma do standard e forma do label
Equivalenza e assegnazione?
A che servono i punti agli estremi degli operatori logici?
Passo su do e passo default

Come funziona un calcolatore?
Input, CPU/Memory, Output
Cos'è una memoria?
Memoria interna e esterna, ROM e RAM
BIT e BYTE
Codifica byte
ASCII

Linguaggio macchina, programmazione, umano
Linguaggio sorgente e linguaggio oggetto
Come avviene la traduzione macchina?
Interpretazione e compilazione (FORTRAN?)
Cosa fa il compilatore?
Locazioni di memoria e indirizzi
Tavola dei simboli
Cosa fa il linker?
Software di gestione mezzi I/O

Numeri
Numeri naturali
Base di numerazione
A cosa serve il primo bit?
Limite massimo per i numeri naturali e overflow
Cosa succede se overflow alla NASA? In un PC?
Numeri interi negativi
Complemento a 2 e inversione logica
Limite "massimo" per i numeri interi negativi

Distinguere reali da naturali: le iniziali
Divisioni tra interi
Come segnalare contravvenzioni alla convenzione
Real, integer, implicit none

Numeri reali
Floating point normalizzata
Precisione semplice e doppia
Caratteristica
Overflow e underflow
Reazione all'underflow
Reazioni all'overflow
Mantissa
Bit nascosto
Potenze del 2 e potende del 10 in binario
Mantissa troppo lunga?
Locazioni di registro (lunghe il doppio)
Approssimazioni mantissa
Arrotonda o tronca?
Come evitare numeri preferenziali?
Numeri reali in macchina sottoinsieme di IR
Floating fl(x)
Taratura: distanza da 1 e successivo
Quante cifre di mantissa?
Precisione: errore assoluto e relativo del floating
Epsilon di macchina: quanto?
Teorema sull'errore relativo con floating
Epsilon di macchina = precisione di macchina: perché?
Definizione su taratura e definizione operativa
Errore di cancellazione ed esempi

Lettura di vettori: do esplicito e do implicito
A(I) che significa? Funzione di I o componente i-esima?
Dimension A(100)
Quante locazione di memoria riservare?
Locazioni consecutive
Cosa succede se supero il massimo delle locazioni?

Amplificazione della perturbazione e propagazione degli errori
Amplificazione in successioni anche costanti
Condizionamento di un problema
Stabilità di un algoritmo
Esempio: intersezione tra rette

f:IR->IR Determinare x* / f(x*)=0
Procedimenti iterativi con ipotesi opportune
Successioni iterative di x(k) che tendono a x*
Scelta del punto x(0) di partenza (o dei punti)
Criteri di arresto
Velocità di convergenza

Metodo di bisezione
Teorema degli zeri
Caso funzioni tangenti all'asse x a segno costante
Successione di intervalli e di punti
Dimostrazione di convergenza globale
Dimostrazione di convergenza lineare (lento)
Criteri di arresto: massime iterazioni, tolleranza su f(x) e su x
Come scegliere soglie di tolleranza?
Perché si usano entrambe?
Criterio assoluto, relativo e misto per intervallo con numeri grandi e numeri piccoli

Metodo di Newton
Da non lineare a lineare
Successione di rette (corde) che approssimano f(x)
Rette tangenti e derivate
Dimostrazione di convergenza locale
Dimostrazione di convergenza quadratica (veloce)
Criteri di arresto: massime iterazioni, tolleranza su f(x), su x e su f'(x)
Metodo di Newton generalizzato: sistema di equazioni non lineari
Convergenza per f'(x) e f''(x) a segno costante in intorno sx/dx di x*
Dimostrazione di teorema di convergenza locale (LaGrange)
Dimostrazione di velocità quadratica (sviluppo Taylor al II ordine)
Metodo misto di bisezione e di Newton: combo

Costi del metodo di Newton
Difficoltà concernenti f'(x): espressione complicata da calcolare a mano, e talvolta inesistente
Conosco esplicitamente derivata: metodo di Newton stazionario (metodo delle corde)
Non conosco esplicitamente derivata: approssimo il limite al rapporto incrementale
Metodo delle secanti
Convergenza locale superlineare (non dimostrata)
Metodo di Newton alle differenze
R(k) e f'(x)
Errori di approssimazione, errori di cancellazione
Scelta dell'incremento: sufficientemente piccolo che evita errori
Convergenza locale quadratica, salvo funzioni "carogne"

Sottoprogrammi
Linguaggio compilatore e librerie di sottoprogrammi precompilati
Function e subroutine
Un solo risultato scalare, più risultati anche vettoriali
Argomenti muti/formali e argomenti attuali/reali
Compilazione indipendente dal contesto del programma principale
Richiamo function
Richiamo subroutine
Corrispondenza 1 a 1
Tipo e natura uguali, nomi anche diversi
Muti e attuali: come vengono trattati?
Assegnazione memoria ad attuali
Funzione del linker
Cosa succede in esecuzione?
Chiamata e associazione per indirizzo
Dimensione formale nel sottoprogramma: dimensionamento variabile e indefinito
Errori di tipo: da intero a reale, da doppia a semplice e viceversa

Risoluzione sistemi lineari: Ax=b
Determinante diverso da 0
Metodi iterativi: sucessioni di vettori
Metodi diretti: sequenza di operazioni

Metodi diretti
Fase 1: trasformo sistema in sistema equivalente Rx=d (stesso determinante)
Fase 2: risolvo R triangolare superiore con algoritmo di sostituzione all'indietro

Metodo di Gauss o metodo QR?
Risoluzione con Cramer e suo costo computazionale
Calcolo matrice inversa (n sistemi lineari )
Metodo di eliminazione di Gauss: perché così?
I passi del metodo di gauss: quanti e come?
Moltiplicatori e pivots
Pivot=0?
Pivots=0?

Stabilità del metodo di Gauss
Norma di una matrice necessaria per quantificare errore
Definizione norma di una matrice
Norma non indotta: vettore n*n e suoi svantaggi
Norma di Frobenius: si addice a contesto?
Norma indotta: vettore operatore
Ax -> y
IIAII grande per IIyII/IIxII grande
max dei rapporti o min rapporti?
Proprietà della norma dei vettori
Proprietà della norma della matrice
Disuguaglianza di Cauchy
Definizione norma attraverso raggio spettrale A^t*A
Metodo calcolo di autovalori costosissimo
Norma euclidea (2) di un vettore
Norma 1 e norma inf
Norma 1 e norma inf matrice

Condizionamento dei sistemi lineari
Teorema del fattore di amplificazione
Perturbazione sul sistema
Numero di condizionamento
Numero di condizionamento con norme euclidee: lavlmax/lavlmin
Distanza di A dall'insieme delle matrici singolari
Esempi controintuitivi tra determinanti e numeri di condizionamento
Matrice di Vandermonde e di Hilbert

Programma principale e sottoprogramma: dimensionamento
Come il compilatore decide l'ordine di allocazione di una matrice
Come il programma principale alloca i dati
Come risolvere il problema: far "saltare" i dati e la dimensione massima nel principale
Perché segnalo solo il numero di righe / la larghezza delle colonne?
Parameter, istruzione dichiarativa: introduce una costante

Compiti del programma principale e compiti del sottoprogramma
Chi legge? Chi stampa? Chi fa calcoli impegnativi?
Chiamate a catena: call di call
Return: restituzione di controllo
Differenze tra return, stop, end

Sistemi lineari e numero di condizionamento
Stima di errore relativo in sistemi lineari
Vettore residuo e vettore errore
Analisi a posteriori del sistema condizionato (dimostrato)
Errori piccoli e grandi in differenti condizionamenti
Stabilità di Gauss
Come rendere Gauss stabile
Moltiplicatori piccoli e pivot grandi
Strategia del pivoting parziale
Strategia del pivoting totale
Studi di Wilkinson
Stabilità del pivoting parziale: controesempi e quotidianeità
Quando è instabile Gauss?
Teorema su G(n)
G(n) segnala errore amplificabile e incompatibile con la stabilità
Come va G(n) nella teoria e nella quotidianeità
Fattore di crescita: elementi proiettati in numeri molto grandi

Sistemi di dimensioni macroscopiche
Problemi con Gauss: memoria e costo computazionale
Sistemi sparsi e matrici sparse
Matrice grande è spesso sparsa
Vettore elementi, vettori posizione
Grandi dimensioni => non trasformo matrice
Metodi iterativi
In quanto tempo arrivare alla soluzione?

Metodi iterativi: Jacobi e Gauss-Seidel
x(k)=Mx(k-1)+c
Metodo di Jacobi: decomposizione DE
Diagonale, extradiagonale
Metodo di Gauss: componenti vecchie e componenti nuove
Decomposizione LU: Lower, upper
Convergenza dei metodi iterativi: llMll<1
Convergenza locale
Predominanza diagonale per colonne o per righe
Raggio spettrale < 1
Velocità di convergenza funzione del raggio spettrale

Criteri di arresto per metodi iterativi
Interazioni massime, residuo, errore
Dimostrazione del perché l'errore non è criterio
Gauss-Seidel più veloce di Jacobi?
Esempi e controesempi
Criterio sul residuo relativo e soglia

Approssimazione dati sperimentali
Modellizzazione di dati
Errori trascurabili, errori non trascurabili
Modello interpolante e modello approssimante
Polinomio interpolante: grado e condizioni
Esistenza e unicità interpolante
Matrice di Vandermonde: non applicata
Metodo di Lagrange e metodo di Newton
Punti fondamentali o nodi
Punti molto vicini => errore di cancellazione
Pro e contro di Lagrange

Condizionamento polinomio interpolante (dimostrazione)
Costante di Lebesgue
Molti dati: divido in parti il polinomio
Nodi di Chebyshev
Forma di Newton
Le A di Newton e la matrice triangolare inferiore
Differenze divise e tavola delle differenze

Approssimazione dati sperimentali
Retta ai minimi quadrati lineari
Non fitta bene se ci sono outlayer
Rette, parabole, polinomi, altre funzioni

Approssimazione di integrali definiti
Ipotesi: f(x) continua, non so calcolare primitiva o non è calcolabile
Formule di quadratura (come il cerchio)
Approssimare come sommatorie
Quanta approssimazione? quanti termini? scarto idea
Approssimare funzione con interpolanti
Errore di approssimazione (dimostrabile con Rolle)
Osservazioni sull'errore
Nodi equidistanti=>errore agli estremi
Nodi di Chebyshev=>oscillazioni contenute

Formule di quadratura interpolante
Pochi nodi=>nodi equidistanti=>Newton
Molti nodi=>nodi di Chebyshev=>Gauss (non vista)
Formula di quadratura di Newton (dei trapezi)
Errore nella formula dei trapezi (dimostrato)
Errore per retta interpolante (2 nodi)
Formula di Simpson (parabola interpolante: 3 nodi)
Errore in Simpson

Formule composite
Formula dei trapezi composita
Convergenza della formula dei trapezi
Velocità di convergenza quadratica
Velocità di convegenza della formula di Simpson: potenza di 4

Formula di Simpson composita
Errore in Simpson composita
La derivata IV cambia poco da punto a punto
Per h->0 posso usare trapezi invece che Simpson, anche se meno precisa

Stima dell'errore secondo Richardson
Come scegliere numero di nodi?
In base all'errore: f''(x) difficile da calcolare
Formule di Richardson per gli errori (a 5 cifre di mantissa uguali)
Richardson per trapezi (dimostrazione)
Richardson per Simpson (senza dimostrazione, 5 volte meno dei trapezi)