Scuola di Ingegneria dell'Informazione
Anno accademico 2011/12
REGISTRO DELLE LEZIONI
Docente: RESTELLI MARCO
089154 - CALCOLO SCIENTIFICO PER L'INFORMATICA (Monodisciplinare)
Codice incarico: 529350
Sede: MI
Periodo: 1° semestre
CFU: 5.0
Mix forme didattiche:
ore lezione:
ore esercitazione:
ore laboratorio:
ore progetto:
32
0
22
0
Totali delle ore svolte per ciascuna forma didattica:
lezione
esercitazione
laboratorio
progetto
seminario
altre attività
32
0
24
0
0
0
0
0
Numero delle squadre attivate per ciascuna forma didattica:
1
0
Stampato il 19/01/2012 17:18
1
0
Docente: RESTELLI MARCO
Insegnamento: CALCOLO SCIENTIFICO PER L'INFORMATICA
Codice incarico: 529350
Anno accademico: 2011/12
giovedì 06 ottobre 2011
aula: L.26.02
orario: 12:15 - 14:15
2:00 ore di lezione
Argomento
Note
Introduzione al corso. Nozioni sulla
rappresentazione in virgola mobile dei
numeri reali: intervallo rappresentabile,
spaziatura dei numeri in virgola mobile,
l'epsilon macchina. Errore di
arrotondamento: legame tra epsilon
macchina ed errore relativo, cifre
significative. Propagazione degli errori
nelle operazioni elementari: somma e
sottrazione, cancellazione delle cifre
significative.
lunedì 10 ottobre 2011
aula: S 1.7
orario: 12:15 - 13:15
1:00 ore di lezione
Argomento
Esempi di cancellazione di cifre
significative. Esistenza di formulazioni
matematicamente equivalenti ma
computazionalmente stabili/instabili.
Richiami sulla buona posizione dei
sistemi lineari quadrati. Sistemi
triangolari. Il metodo di eliminazione
Gaussiana senza pivotazione.
Note
lunedì 10 ottobre 2011
aula: S 1.7
orario: 13:15 - 15:15
2:00 ore di laboratorio
Argomento (Attività svolta da: Mattia
Penati)
Introduzione ad Octave/Matlab: numeri
floating point, cancellazione di cifre
significative, overflow. Definizione di
funzioni ed M-file. Gestione file e
cartelle: pwd, ls, cd. Definizione di
variabili: matrici e vettori. Operatori + * .* / ./ ^ .^ . Operatore di trasposizione
'. Comandi zeros, diag, eye. Cicli for e
while, costrutto if. I messaggi di errore.
Note
giovedì 13 ottobre 2011
aula: L.26.02
orario: 12:15 - 14:15
2:00 ore di lezione
Argomento
Note
La pivotazione nel metodo
dell'eliminazione gaussiana (GEM) in
presenza di elementi pivotali nulli o
"piccoli". Matrici che non necessitano la
pivotazione: s.d.p. e a dominanza
diagonale. Matrici di permutazione.
Prodotto, determinante e inversa di
matrici matrici triangolari inferiori
(unitarie). Prodotti di matrici: inversa,
trasposta e determinante del prodotto.
Il GEM come fattorizzazione LU con e
senza pivotazione. Risoluzione di
sistemi lineari tramite
fattorizzazione.
lunedì 17 ottobre 2011
aula: S 1.7
orario: 12:15 - 13:15
1:00 ore di lezione
Argomento
Varianti della fattorizzazione LU:
LDM^T, LDL^T (per matrici
simmetriche), H^TH (Cholesky per
matrici s.d.p.). Per la decomposizione
di Cholesky: dimostrazione del fatto
che D_{kk}>0 se la matrice di partenza
è s.d.p. e calcolo diretto dei coefficienti
h_{ij}. Calcolo dell'inversa di una
matrice.
giovedì 19 gennaio 2012 17:18
Note
Firma:______________________________________
pag. 2/8
Docente: RESTELLI MARCO
Insegnamento: CALCOLO SCIENTIFICO PER L'INFORMATICA
Codice incarico: 529350
Anno accademico: 2011/12
lunedì 17 ottobre 2011
aula: S 1.7
orario: 13:15 - 15:15
2:00 ore di laboratorio
Argomento (Attività svolta da: Mattia
Penati)
Implementazione del metodo di
eliminazione gaussiana e della
fattorizzazione LU senza pivotazione.
Applicazioni ed esempi. Confronto con
il comando lu di Octave/Matlab, uso
della forma [l,u,p]=lu(A). Importanza
del pivoting in presenza di elementi
pivotali "piccoli". Matrici sparse:
formato di memorizzazione compatta:
vantaggi e svantaggi; fenomeno del
"fill-in". Comando chol. Comando help.
giovedì 20 ottobre 2011
aula: L.26.02
orario: 12:15 - 14:15
2:00 ore di lezione
Argomento
Note
Norme di vettori e norme di matrici
indotte, i casi p=1,2,inf.
Condizionamento per problemi generici
e per sistemi lineari. Numero di
condizionamento per matrici quadrate:
accuratezza della soluzione; perdita di
cifre significative; l'effetto di
perturbazioni della matrice; matrici
"quasi" singolari: condizionamento, e
annullamento del determinante.
lunedì 24 ottobre 2011
aula: S 1.7
orario: 12:15 - 13:15
1:00 ore di lezione
Argomento
Condizionamento, errore e residuo:
stima dell'errore a partire dal residuo in
funzione del condizionamento di una
matrice. Miglioramento
dell'accuratezza dei metodi diretti:
riscalatura di righe e/o colonne,
raffinamento iterativo. Metodi iterativi
per sistemi lineari: metodi di Jacobi e
Gauss-Seidel, forma generale in
termini della matrice di iterazione,
proprietà di consistenza e
convergenza.
lunedì 24 ottobre 2011
aula: S 1.7
orario: 13:15 - 15:15
2:00 ore di laboratorio
Argomento (Attività svolta da: Mattia
Note
Penati)
Condizionamento di sistemi lineari e
matrici. La matrice di Hilbert. Relazione
tra residuo ed errore in funzione di
K(A). Condizionamento del problema,
K(A), det(A). Importanza dell'uso di
algoritmi numericamente stabili in
aggiunta al buon condizionamento del
problema di partenza.
Implementazione calcolo norma ||v||_p
di vettori (p generico) e ||A||_1 e
||A||_Inf di matrici. Matrici sparse:
calcolo della norma (comando norm),
comando condest per la stima del
condizionamento.
giovedì 19 gennaio 2012 17:18
Note
Note
Firma:______________________________________
pag. 3/8
Docente: RESTELLI MARCO
Insegnamento: CALCOLO SCIENTIFICO PER L'INFORMATICA
Codice incarico: 529350
Anno accademico: 2011/12
giovedì 27 ottobre 2011
aula: L.26.02
orario: 12:15 - 14:15
2:00 ore di lezione
Argomento
Criteri di arresto per i metodi iterativi:
basati sul residuo e sull'incremento.
Criteri di convergenza: ||B||<1
(sufficiente) e rho(B)<1 (necessario e
sufficiente). Andamento asintotico
dell'errore. Alcuni criteri di
convergenza: dominanza diagonale
stretta per righe (Jacobi e GaussSeidel) e s.d.p. (Gauss-Seidel). Il
metodo del gradiente per matrici s.d.p.
Cenni alla variante precondizionata del
metodo del gradiente.
Note
giovedì 03 novembre 2011
aula: L.26.02
orario: 12:15 - 14:15
2:00 ore di lezione
Argomento
Autovalori ed autovettori. Teoremi di
Gershgorin, Bauer-Fike e del
residuo (i primi due con
dimostrazione). Metodi locali: il metodo
delle potenze, e il metodo delle
potenze inverse con shift. Metodi
globali: il metodo LR (cenni) ed il
metodo QR nella sua forma base.
Per il metodo QR: convergenza nel
caso di autovalori di moduli
distinti, il caso delle matrici
simmetriche e il caso di coppie di
autovalori complessi coniugati.
Note
lunedì 07 novembre 2011
aula: S 1.7
orario: 12:15 - 13:15
1:00 ore di lezione
Argomento
Criteri di arresto per il metodo QR: i
casi A simmetrica (teorema di
Gershgorin) e A generica (cenni).
Miglioramenti del metodo QR (non
richiesti per l'esame): shift, riduzione in
forma di Hessenberg e deflazione. La
fattorizzazione QR: forme ridotta e
completa, legame con la
ortonormalizzazione di una base
arbitraria. Algoritmi: di Gram-Schmidt e
di Householder.
Note
lunedì 07 novembre 2011
aula: S 1.7
orario: 13:15 - 15:15
2:00 ore di laboratorio
Argomento (Attività svolta da: Mattia
Note
Penati)
Implementazione metodo GaussSeidel, problema del fill-in per la
matrice B, riformulazione in termini del
residuo precondizionato z = P^-1*r per
evitare di costruire B. Esempi: velocità
di convergenza, grafico del residuo,
effetto della scelta del dato iniziale. Il
comando PCG: sintassi ed esempi. Il
metodo del gradiente:
implementazione ed esempi. Scelta del
criterio di arresto: residuo/incremento.
Confronto tra i vari metodi (superiorità
di PCG rispetto al metodo del
gradiente).
giovedì 19 gennaio 2012 17:18
Firma:______________________________________
pag. 4/8
Docente: RESTELLI MARCO
Insegnamento: CALCOLO SCIENTIFICO PER L'INFORMATICA
Codice incarico: 529350
Anno accademico: 2011/12
giovedì 10 novembre 2011
aula: L.26.02
orario: 12:15 - 14:15
2:00 ore di lezione
Argomento
Note
Rango per colonne e fattorizzazione
QR. Riepilogo delle fattorizzazioni viste
nella prima parte del corso. La
decomposizione a valori singolari
(SVD): definizione e proprietà:
caratterizzazione di rango, immagine e
nucleo, relazioni con la norma 2 e con
il numero di condizionamento,
approssimazione di una matrice,
determinazione numerica del rango.
Sistemi sovradeterminati di rango
pieno: nozione di soluzione e
risoluzione numerica mediante la
fattorizzazione QR.
lunedì 14 novembre 2011
aula: S 1.7
orario: 12:15 - 14:15
2:00 ore di laboratorio
Argomento (Attività svolta da: Mattia
Note
Penati)
Metodo del gradiente, comportamento
nei due casi ben condizionato e mal
condizionato. Metodi per il calcolo degli
autovalori: il metodo delle potenze:
convergenza, assenza di convergenza
e dipendenza/indipendenza dal valore
iniziale; il comando eig.
giovedì 17 novembre 2011
aula: L.26.02
orario: 12:15 - 14:15
2:00 ore di lezione
Argomento
Note
Risoluzione nel senso dei minimi
quadrati di sistemi lineari
sovradeterminati a rango pieno:
ridefinizione del concetto di soluzione e
risoluzione mediante fattorizzazione
QR. Risoluzione di sistemi generici:
ridefinizione del concetto di soluzione e
risoluzione mediante SVD. Problemi
nonlineari: il caso scalare.
Condizionamento, residuo ed errore.
lunedì 21 novembre 2011
aula: S 1.7
orario: 13:15 - 15:15
2:00 ore di laboratorio
Argomento (Attività svolta da: Mattia
Note
Penati)
Implementazione metodo delle potenze
inverse (la matrice viene fattorizzata
una volta per tutte con LU); cerchi di
Gershgorin; decomposizione QR,
metodo di Gram-Schmidt (modificato);
metodo QR per autovalori: matrici
simmetriche, antisimmetriche e matrici
generiche, presenza di autovalori
complessi coniugati.
giovedì 24 novembre 2011
aula: L.26.02
orario: 12:15 - 14:15
2:00 ore di lezione
Argomento
Il metodo di bisezione per le equazioni
non lineari: algoritmo, convergenza e
maggiorazione dell'errore. I metodi di
punto fisso: condizione di convergenza
e stime per l'errore e l'incremento.
Importanza della scelta del punto di
partenza. La velocità asintotica di
convergenza e l'ordine del metodo.
Criteri di arresto: residuo e incremento,
rispettivi ambiti di validità. Il metodo di
Newton: definizione del metodo e
proprietà di convergenza; ordine nel
caso f' diversa da zero.
giovedì 19 gennaio 2012 17:18
Note
Firma:______________________________________
pag. 5/8
Docente: RESTELLI MARCO
Insegnamento: CALCOLO SCIENTIFICO PER L'INFORMATICA
Codice incarico: 529350
Anno accademico: 2011/12
lunedì 28 novembre 2011
aula: S 1.7
orario: 13:15 - 15:15
2:00 ore di laboratorio
Argomento (Attività svolta da: Mattia
Penati)
Riepilogo metodi Gram-Schmidt e
Gram-Schmidt modificato per la
fattorizzazione QR. Risolizione sistemi
sovra/sotto-determinati con la
fattorizzazione QR (rango n) e SVD
(caso generico). Calcolo del rango,
determinazione della base di nucleo e
immagine. Esempio di uso di SVD per
approssimazione di matrici (esempio
"compressione di immagini").
Note
giovedì 01 dicembre 2011
aula: L.26.02
orario: 12:15 - 14:15
2:00 ore di lezione
Argomento
Metodi per sistemi di equazioni non
lineari: metodi di punto fisso e metodi
di Newton e Newton modificati. Il
metodo della matrice di Frobenius (o
companion matrix) per il calcolo degli
zeri di un polinomio. Interpolazione
polinomiale semplice: definizione della
base di Lagrange, esistenza ed unicità
del polinomio interpolante. Costruzione
mediante matrice di Vandermonde.
Stima dell'errore e comportamento per
n crescente.
Note
lunedì 05 dicembre 2011
aula: S 1.7
orario: 12:15 - 14:15
2:00 ore di laboratorio
Argomento (Attività svolta da: Mattia
Note
Penati)
Metodo di bisezione, implementazione,
ordine ed errore. Iterazione di punto
fisso, implementazione (arresto basato
sul residuo), applicazione alla mappa
logistica, velocità di convergenza e
confronto con la teoria. Metodo di
Newton, implementazione (arresto
basato sull'incremento), i casi scalare e
vettoriale, velocità di convergenza
(radici semplici e multiple), effetto del
dato iniziale. Funzione fsolve di
MATLAB. Costruzione della matrice
compagna e calcolo delle radici di un
polinomio.
lunedì 12 dicembre 2011
aula: S 1.7
orario: 12:15 - 14:15
2:00 ore di laboratorio
Argomento (Attività svolta da: Mattia
Penati)
Interpolazione polinomiale: base di
Lagrange (formulazione per nodi
generici ed esempi con nodi
equispaziati), effetto della regolarità
della funzione interpolata. Fenomeno
di Runge (mancata convergenza al
crescere di n). Distribuzione dell'errore
e confronto con il polinomio nodale.
Costruzione della matrice di
Vandermonde e calcolo dei coefficienti
del polinomio. Confronto con le
funzioni polyfit e polyval di Matlab.
Estensione della matrice di
Vandermonde al caso di polinomi
trigonometrici.
giovedì 19 gennaio 2012 17:18
Note
Firma:______________________________________
pag. 6/8
Docente: RESTELLI MARCO
Insegnamento: CALCOLO SCIENTIFICO PER L'INFORMATICA
Codice incarico: 529350
Anno accademico: 2011/12
giovedì 15 dicembre 2011
aula: L.26.02
orario: 12:15 - 14:15
2:00 ore di lezione
Argomento
Interpolazione polinomiale:
condizionamento del problema e
definizione della costante di Lebesgue.
Interpolazione polinomiale a tratti:
definizione della base di Lagrange,
stima del'errore di interpolazione e
comportamento dell'errore nei due casi
di grado crescente e numero di
elementi crescente. Interpolazione
mediante funzioni spline: definizione
delle funzioni spline e costruzione
dell'interpolante (cenni).
lunedì 19 dicembre 2011
aula: S 1.7
orario: 12:15 - 14:15
2:00 ore di laboratorio
Argomento (Attività svolta da: Mattia
Note
Penati)
Interpolazione composita: interp1,
lineare a tratti e spline cubiche.
Valutazione dell'ordine di convergenza
con funzioni regolari e poco regolari
(esempio abs(x)). Valutazione
dell'ordine di convergenza come
rapporto incrementale in scala
bilogaritmica. Valutazione della
costante di Lebesgue, effetto di
perturbazioni sui valori nodali
(condizionamento del problema).
Regole di quadratura: formule dei
trapezi e di Simpson, implementazione.
giovedì 22 dicembre 2011
aula: L.26.02
orario: 12:15 - 14:15
2:00 ore di lezione
Argomento
Approssimazione polinomiale:
definizione del problema e costruzione
del polinomio approssimante nel senso
dei minimi quadrati. Regressione
lineare in presenza di dati con
componente deterministica e
stocastica (cenni, non richiesti per
l'esame). Quadratura numerica:
formule interpolatorie, calcolo dei pesi
di quadratura per un insieme di nodi
assegnati. Formule semplici e
composite. Grado di esattezza. Le
formule del punto medio, dei trapezi e
di Cavalieri-Simpson. Stime dell'errore.
lunedì 09 gennaio 2012
aula: S 1.7
orario: 12:15 - 13:15
1:00 ore di lezione
Argomento
Note
Introduzione ai metodi numerici per le
equazioni differenziali ordinarie (ODE).
Esistenza ed unicità della soluzione del
problema continuo (cenni). Sistemi
autonomi, riduzione al primo ordine.
Forma generale di un metodo
numerico, funzione di incremento. Il
metodo di Eulero esplicito: definizione
e motivazioni. I metodi di Eulero
implicito, Crank-Nicolson, Heun e theta
metodo. Metodi espliciti ed impliciti.
giovedì 19 gennaio 2012 17:18
Note
Note
Firma:______________________________________
pag. 7/8
Docente: RESTELLI MARCO
Insegnamento: CALCOLO SCIENTIFICO PER L'INFORMATICA
Codice incarico: 529350
Anno accademico: 2011/12
lunedì 09 gennaio 2012
aula: S 1.7
orario: 13:15 - 15:15
2:00 ore di laboratorio
Argomento (Attività svolta da: Mattia
Note
Penati)
Implementazione metodo Eulero
esplicito. Analisi qualitativa dell'errore e
dipendenza da h. Valutazione
qualitativa della stabilità. Calcolo
dell'ordine di convergenza per i metodi
di Eulero esplicito e Heun.
Implementazione del metodo di Eulero
implicito. Valutazione dell'ordine del
metodo. Confronto qualitativo della
stabilità delle due versioni
esplicita/implicita. Il programma ode45
di Matlab.
giovedì 12 gennaio 2012
aula: L.26.02
orario: 12:15 - 14:15
2:00 ore di lezione
Argomento
Note
Analisi dei metodi numerici per ODE.
Definizione di errore di troncamento
locale e globale, definizione di
consistenza e ordine del metodo.
Rapporto tra l'errore di troncamento e
l'errore. Calcolo dell'ordine di
infinitesimo dell'errore di troncamento
per i metodi di Eulero esplicito e il theta
metodo. Stabilità dei metodi numerici: il
problema modello nel caso di
decadimento/crescita esponenziale e
nel caso delle oscillazioni armoniche.
lunedì 16 gennaio 2012
aula: S 1.7
orario: 12:15 - 13:15
1:00 ore di lezione
Argomento
Applicazione dei metodi numerici al
problema modello y'=lambda*y con
lambda numero complesso: regione di
assoluta stabilità, errore di ampiezza
ed errore di fase. I casi particolari
lambda reale e immaginario.
lunedì 16 gennaio 2012
aula: S 1.7
orario: 13:15 - 15:15
2:00 ore di laboratorio
Argomento (Attività svolta da: Mattia
Note
Penati)
Regione di assoluta stabilità dei metodi
di Eulero: calcolo e visualizzazione.
Metodi di ordine >1 : Crank-Nicolson,
Heun, RK4. Studio del problema
modello dell'oscillatore armonico:
confronto qualitativo e quantitativo tra
le soluzioni esatta e numerica e
relazione con i grafici della funzione di
stabilità (modulo e fase).
giovedì 19 gennaio 2012
aula: L.26.02
orario: 12:15 - 14:15
2:00 ore di lezione
Argomento
Note
Definizione di zero stabilità per i metodi
numerici per la risoluzione delle
equazioni differenziali (per metodi
espliciti). Relazione tra errore di
troncamento ed errore: un metodo zero
stabile con errore di troncamento
infinitesimo di ordine p ha un errore di
ordine p. Lipschitzianità della funzione
di incremento e zero stabilità del
metodo. Esempi: i metodi di Eulero
esplicito e Heun.
giovedì 19 gennaio 2012 17:18
Note
Firma:______________________________________
pag. 8/8