Principali informazioni sull’insegnamento Denominazione
dell’insegnamento
Calcolo Numerico
Corso di studio Informatica e Tecnologie per la produzione del Software
Anno di corso II
Crediti formativi universitari (CFU) / European Credit Transfer and Accumulation System (ECTS): :
SSD MAT 09
Lingua di erogazione Italiano
Periodo di erogazione 27 settembre 2021—14 gennaio 2022 Obbligo di frequenza NO
Docente
Nome e cognome Francesca Mazzia; Antonella Falini
Indirizzo mail francesca.mazzia@uniba.it antonella.falini@uniba.it
Telefono
0805442283 int. 2283 ; 0805443284 interno 3284Sede Dipartimento di informatica, Via Edoardo Orabona 4, Bari
Sede virtuale MS Teams, classe “Ricevimento”, codice h0hat71
Ricevimento (giorni, orari e modalità)
Su appuntamento, via MS Teams.
Syllabus
Obiettivi formativi
Il corso si propone come raccordo costruttivo fra la matematica e l'informatica, fornendo allo studente gli strumenti specifici di base per risolvere i problemi matematici usando il calcolatore mettendo in evidenza i rischi che si corrono con un uso ingenuo delle risorse di calcolo.Prerequisiti Elementi di base di algebra lineare; tutti gli argomenti trattati nei corsi di analisi matematica; elementi di programmazione.
Contenuti di insegnamento (Programma)
Il corso presenta i metodi fondamentali per risolvere numericamente problemi matematici, mettendo in evidenza gli aspetti computazionali. Il programma comprende i metodi iterativi per equazioni non lineari, i metodi diretti per sistemi lineari, interpolazione, approssimazione, integrazione e calcolo di autovalori.
1. Introduzione al Calcolo Scientifico
Modelli matematici e metodi numerici, sorgenti di errori, il processo di risoluzione numerica, efficienza, testing, errori computazionali, ambienti computazionali, linguaggi per il calcolo scientifico, problem solving enviroments: MATLAB, PYTHON.
2. Analisi dell'errore.
Rappresentazione dei numeri. IEEE singola e doppia precisione. Troncamento e Arrotondamento.
Precisione di macchina. Errore assoluto e relativo. Operazioni con i numeri di macchina. Cancellazione di cifre significative. Condizionamento di un problema. Stabilita' degli algoritmi. Propagazione degli errori. Introduzione a Python, il linguaggio, file di tipo script e function. Funzioni predefinite in NumPy.
Introduzione alla grafica. Esempi Python sugli errori di arrotondamento.
3. Elementi di algebra lineare
Matrici e vettori. Operazioni con matrici. Inversa di una matrice. Sistemi lineari. Prodotto esterno fra vettori. Dipendenza lineare di vettori. Autovalori ed autovettori. Norme di vettori e matrici. Spazi vettoriali lineari
Base di uno spazio vettoriale. Trasformazioni lineari e matrici. Sottospazi vettoriali. Spazio vettoriale generato da un insieme di vettori. Nucleo e immagine di una trasformazione lineare. Sottospazio ortogonale.
4. Algoritmi per la soluzione di sistemi lineari
Il Python per l'algebra lineare, Memorizzazioni di vettori e matrici, operazioni sulle matrici. Sistemi triangolari inferiori e superiori. Matrici di permutazione e proprietà. Algoritmo di eliminazione di Gauss. Problematiche di stabilità. Teorema di esistenza della fattorizzazione LU con pivot. Studio del condizionamento di un sistema lineare. Studio del residuo. Metodo dei minimi quadrati. Pseudoinversa.
Esempi di codici Python, documentazione e testing, confronti con il software esistente.
5. Interpolazione e approssimazione
Base delle potenze. Interpolazione di Lagrange. Interpolazione di Newton. Differenze divise.
Interpolazione con nodi coincidenti. Interpolazione di Hermite. Errore nell'interpolazione polinomiale.
Scelta dei nodi per l'interpolazione. Studio del condizionamento. Interpolazione lineare a tratti. Spline lineare. Approssimazione ai minimi quadrati nel discreto. Fitting di dati: polinomio di migliore approssimazione nel senso dei minimi quadrati. Retta di regressione lineare. Esempi di codici Python, documentazione e testing, confronti con il software esistente.
6. Calcolo degli zeri di funzione
Metodo delle bisezioni. Convergenza. Criteri di arresto e stime dell'errore. Ordine di convergenza.
Iterazione funzionale. Teorema di contrazione. Ordine di convergenza. Il metodo di Newton. Criteri di stop. Metodi quasi newtoniani. Metodo della direzione costante. Metodo della falsa posizione. Il metodo delle secanti. Metodo di Brent. Errore accuratezza e numero di condizione. Esempi di codici Python, documentazione e testing, confronti con il software esistente.
7. Calcolo degli autovalori.
Metodo delle potenze. Applicazione: google page rank. Esempi di codici Python.
8. Calcolo degli integrali.
Metodo dei trapezi, di Simpson, dei trapezi composto, di Simpson composto per il calcolo di integrali definiti. Stime dell'errore e metodo dei trapezi adattativo. Esempi di codici Python.
Testi di riferimento
Uri M. Ascher, Chen Greif, A First Course in Numerical Methods, SIAM, 2011 L. Brugnano, C. Magherini, A. Sestini, Calcolo numerico, seconda edizione, Master, Università & Professioni, Firenze 2010.James F. Epperson, Introduzione all'analisi numerica, teoria, metodi, algoritmi. McGraw-Hill, Milano, 2003
Note ai testi di riferimento I libri di testo sono integrati con le slide, le dispense e gli appunti (elettronici) del docente distribuiti sulla piattaforma ADA e sul canale Teams della classe.
Organizzazione della didattica Ore
Totali Didattica frontale Pratica (laboratorio, campo, esercitazione, altro) Studio individuale
150 32 30 88
CFU/ETCS 6
Metodi didattici
Lezioni frontali ed esercitazioni/laboratorio in aula
Risultati di apprendimento previsti
Conoscenza e capacità di comprensione
o Conoscere le tecniche e i metodi per la programmazione numerica finalizzati alla risoluzione di problemi nell'ambito delle discipline matematiche ed affini, con particolare enfasi ai problemi fondamentali nell'ambito dell'algebra lineare.
o
Comprendere e saper illustrare le problematiche relative dell’uso del calcolatore per la risoluzione di problemi matematiciConoscenza e capacità di comprensione applicate
o
Capacità di risolvere problemi matematici mediante algoritmi ottimizzati dal punto di vista del costo computazionale e della stabilitào
Sviluppo delle capacità di programmare, documentare e testare algoritmi numerici, interpretandone correttamente i risultati.o
Sviluppo delle capacità di risolvere problemi matematici usando problem solving enviroments.Competenze trasversali • Autonomia di giudizio
o
Saper individuare il metodo numerico più idoneo per risolvere numericamente un problema matematico tra quelli trattati nel corso.• Abilità comunicative
o
Saper definire in modo rigoroso i problemi matematici trattati nel corso e saper esporre i relativi metodi numerici, delineandone le proprietà fondamentali.• Capacità di apprendere in modo autonomo
o
Capacità di studiare e risolvere problemi numerici simili ma non necessariamente uguali a quelli affrontati durante le lezioni.Valutazione Modalità di verifica dell’apprendimento
Durante le lezioni verranno discussi, in modo partecipato, diversi quesiti ed esercizi simili per tipologia a quelli comunemente somministrati durante gli esami e gli esoneri. La finalità è duplice: monitorare in tempo reale lo stato di preparazione degli studenti frequentanti, perfezionandone la preparazione in vista dell'esame o degli esoneri; agevolare lo studio in itinere degli aspetti pratici della disciplina, motivando concretamente i corsisti a sostenere l'esame in tempi brevi, sfruttando possibilmente la modalità degli esoneri. Sono previsti due esoneri: il primo durante l'interruzione delle lezioni a metà corso, il secondo a fine corso.
Entrambe le date sono concordate, nei limiti consentiti, con gli studenti frequentanti. Di seguito sono elencati ulteriori vantaggi riservati ai frequentanti.
- Il superamento di un solo esonero consentirà allo studente di recuperare in sede di esame unicamente la parte mancante, la cui valutazione verrà poi mediata con il voto conseguito nella prova di esonero superata.
- Lo studente che superi entrambi gli esoneri, può decidere comunque di rinunciare al voto conseguito in una delle due prove, recuperando in sede di esame la relativa parte (utile se c'è molta discrepanza nei voti conseguiti nelle due prove).
- Lo studente che superi entrambi gli esoneri, presenterà e discuterà in sede di esame un lavoro applicativo sul calcolatore con l’obiettivo di migliorare la sua valutazione finale (la valutazione verrà mediata con il voto conseguito).
Criteri di valutazione • Conoscenza e capacità di comprensione:
o Conoscere le tecniche e i metodi per la programmazione numerica finalizzati alla risoluzione di problemi nell'ambito delle discipline matematiche ed affini, con particolare enfasi ai problemi fondamentali nell'ambito dell'algebra lineare.
o
Comprendere e saper illustrare le problematiche relative dell’uso del calcolatore per la risoluzione di problemi matematici• Conoscenza e capacità di comprensione applicate:
o
Capacità di risolvere problemi matematici mediante algoritmi ottimizzati dal punto di vista del costo computazionale e della stabilitào
Sviluppo delle capacità di programmare, documentare e testare algoritmi numerici, interpretandone correttamente i risultati.• Autonomia di giudizio:
o
Saper individuare il metodo numerico più idoneo per risolvere numericamente un problema matematico tra quelli trattati nel corso• Abilità comunicative:
o
Saper definire in modo rigoroso i problemi matematici trattati nel corso e saper esporre i relativi metodi numerici, delineandone le proprietà fondamentali.• Capacità di apprendere:
o
Capacità di studiare e risolvere problemi numerici simili ma non necessariamente uguali a quelli affrontati durante le lezioni.Criteri di misurazione dell'apprendimento e di
L’apprendimento è valutato in base alla capacità di risoluzione di problemi
matematici utilizzando problem solving enviroments tramite lo svolgimento di
attribuzione del voto finale esercizi assegnati la settimana prima della data dell’esame. La valutazione orale è basata sul raggiungimento degli obiettivi di apprendimento previsti.
Altro
General information
Academic subject Numerical Calculus
Degree course Computer Science and Technologies for Software production Se
Academic Year Second
European Credit Transfer and Accumulation System (ECTS) 6
Language Italian
Academic calendar (starting and ending date) September 27, 2021—January 14, 2022
Attendance Not mandatory
Professor/ Lecturer
Name and Surname Francesca Mazzia; Antonella Falini
E-mail francesca.mazzia@uniba.it antonella.falini@uniba.it
Telephone
0805442283 int. 2283 ; 0805443284 interno 3284Department and address Computer Science department, Street Edoardo Orabona 4, Bari Virtual headquarters MS Teams, class name: “Ricevimento”. Access code: h0hat71
Tutoring (time and day) B y email appointment, online
Syllabus
Learning Objectives This course bridges the gap between theoretical mathematics and computer science by giving the fundamentals to model and solve mathematical problems by using practical coding.
Course prerequisites Basic of linear algebra and programming skills. Mathematical Analysis.
Contents
Il corso presenta i metodi fondamentali per risolvere numericamente problemi matematici, mettendo in evidenza gli aspetti computazionali. Il programma comprende i metodi iterativi per equazioni non lineari, i metodi diretti per sistemi lineari, interpolazione, approssimazione, integrazione e calcolo di autovalori.1. Introduction to Scientific Calculus
Mathematical models and numerical methods, error sources, numerical process to construct a solution efficiency, testing, computational errors, computational environments, programming languages for the scientific calculus, problem solving environments: MATLAB, PYTHON.
2. Error Analysis
Number representation. IEEE single and double precision. Cutting and Rounding techniques. Machine precision. Absolute and relative error. Algebraic operations with floating point numbers. Cancellation phenomenon. Conditioning of a given problem. Algorithms’ stability. Errors propagation. Introduction to Python regarding the language, scripts and functions. Predefined routines of NumPy. Introduction to graphics. Python examples for rounding errors.
3. Basics of linear algebra
Matrices and vectors. Algebraic operations with matrices. Inverse matrix. Linear systems. Outer product. Linear dependence. Eigenvalues and Eigenvectors. Vector and Matrix – Norms. Linear vectorial spaces. Basis of a vector space. Linear transformation and matrices. Subspaces. Kernel and Range space for a linear transformation. Orthogonal subspaces.
4. Algorithms for solving linear systems
The use of Python for linear algebra. Storing matrices and vectors. Performing operations with matrices and vectors. Upper and lower triangular linear systems. Permutation matrices and their properties. Gauss elimination algorithm. Stability issues. Existence LU with pivot-decomposition theorem. Conditioning of a linear system. Residual study. Least squares method. Pseudoinverse matrix.
Python examples, documents and tests, comparisons with available software.
5. Interpolation and approximation
Power basis. Lagrange interpolation. Newton interpolation. Divided finite differences. Interpolation
with coincident nodes. Hermite interpolation. Polynomial interpolation error. Choice of interpolation sites. Conditioning study. Piecewise linear interpolation. Linear splines. Discrete least squares approximation. Polynomial fitting: best approximation in the least squares sense. Linear regression.
Python examples, documents, tests, comparisons with available software.
6. Roots computation by iterative methods
Bisection method. Convergence. Stopping criteria and error estimates. Convergence order. Functional iteration. Fixed point theorem. Newton method and stopping criteria. Qausi-Newton methods.
Constant direction method. False position method. Secant method. Brent method. Error, accuracy and condition number. Python examples, documents, tests, comparisons with available software.
7. Eigenvalues compuation.
The power method. Application: Google page-rank algorithm. Python examples.
8. Integrals computations.
Quadrature rules for definite integrals: the trapezoidal rule, the Simpson rule, the composite trapezoidal rule, the composite Simpson rule. Error estimates and adaptive trapezoidal method. Python examples.
Books and bibliography
Uri M. Ascher, Chen Greif, A First Course in Numerical Methods, SIAM, 2011 L. Brugnano, C. Magherini, A. Sestini, Calcolo numerico, seconda edizione, Master, Università & Professioni, Firenze 2010.James F. Epperson, Introduzione all'analisi numerica, teoria, metodi, algoritmi. McGraw-Hill, Milano, 2003
Additional materials The suggested books are integrated with slides and lecture notes provided by the teachers on the e-learning platform ADA and on the corresponding MS Team class.
Work schedule
Total Lectures Hands on (Laboratory, working groups, seminars, field trips)
Out-of-class study hours/ Self-study hours
Hours
150 32 30 88
ECTS
Teaching strategy
Traditional lectures and coding-exercises Expected learning outcomes
Knowledge and understanding on:
o Numerical programming skills to solve mathematical problems, especially related to linear algebra.
o Understanding and reporting the issues of using computer machines to perform calculations for mathematical problems.
Applying knowledge and understanding on:
o Optimized algorithms for numerical stability and computational cost.
o Developments of programming skills, including documenting, and testing numerical algorithms by giving a meaningful interpretation of the results.
Soft skills • Making informed judgments and choices
o Being able to identify the best numerical method to numerically solve any of the mathematical problem taught during the class.
• Communicating knowledge and understanding
o Expressing rigorously mathematical problems taught during the class and
being able to express the related numerical methods by showing their
fundamental properties.
• Capacities to continue learning
o
Skills of studying and solving numerical problems similar to the ones taught during the class but not necessarily exactly the same problems.Assessment and feedback
Methods of assessment
During the classes the teacher will invite to discuss about exercises and questions similar to the ones that will be given during the exams. The goals is twofold: real-time monitoring of the current level of preparation and knowledge of the students plus to make easy the study of the subject and to motivate the attendees to steadily study the subject in order to pass the scheduled mid-term tests. There will be two mod-term tests: the firs one will take place during the first lecture break at the middle of the course-time. The second one will take place at the end of the course time. Both dates will be scheduled in accordance with the attendee-students, whenever is possible. Following additional advantages for the attendee students:- If you pass only one mid-term test, during the official exam date you will be evaluated only on the second-course part. The final grade will be an average of the two performances.
- If you pass both the mid-terms tests, you can decide to “cancel” one of the two marks and hence, you will need to have an oral examination about the part that you decided to drop (this modality is useful in case there are two very different marks between the first and second mid-term tests).
- If you pass both the mid-term tests, you will need to pass the final oral exam where you will be discussing a practical programming exercise. The final mark will be computed as average of the marks of the passed tests.
Evaluation criteria • Knowledge and understanding
o Numerical programming skills to solve mathematical problems, especially related to linear algebra.
o
Understanding and reporting the issues of using computer machines to perform calculations for mathematical problems.
• Applying knowledge and understanding
o
Optimized algorithms for numerical stability and computational cost.
o
Developments of programming skills, including documenting, and testing numerical algorithms by giving a meaningful interpretation of the results
• Autonomy of judgment
•
