Programma del corso di:
Calcolo Numerico Corso di laurea in Matematica
a.a. 2004-05 Prof. B.Paternoster
Richiami di analisi degli errori. Rappresentazione dei numeri in un calcolatore. Operazioni di macchina.
Errori e loro propagazione. Procedimenti stabili e instabili. Condizionamento di problemi numerici.
Approssimazione. Richiami sull’interpolazione polinomiale.
Approssimazione nel senso dei minimi quadrati: caso discreto.
Risoluzione numerica di equazioni non lineari. Metodi iterativi: metodo di bisezioni, delle secanti, metodo di Newton o delle tangenti. Ordine di convergenza e teoremi di convergenza. Metodi ibridi.
Calcolo delle radici di polinomi algebrici: metodo di Newton-Horner.
Risoluzione numerica di sistemi di equazioni non lineari.
Integrazione numerica. Quadratura interpolatoria. Grado di precisione. Formule di Newton - Cotes. Espressione dell’ errore. Formule composite e loro errore.
Polinomi ortogonali. Formule di quadratura Gaussiane. Stima dell’errore. Integratori automatici basati su schemi fissi e schemi adattativi.
Autovalori di matrici. Localizzazione di autovalori: teorema di Gerschgorin.
Metodi iterativi: metodo delle potenze e delle potenze inverse.
Metodi basati su trasformazioni di similitudine. Fattorizzazione QR di matrice. Il metodo QR per il calcolo degli autovalori.
Sviluppo di codici Matlab relativi ai principali algoritmi trattati.
Elenco dei programmi da sviluppare in Matlab:
§ Calcolo delle soluzioni di equazioni non lineari con il metodo di Newton (con esempi test significativi in merito alla convergenza), delle secanti e con metodo ibrido.
§ Calcolo delle radici di polinomi algebrici col metodo di Newton-Horner.
§ Calcolo di un integrale con la formula composita di Simpson (con esempi test significativi): schema fisso e adattivo
Testi consigliati:
G.Monegato, Fondamenti di Calcolo Numerico, CLUT V. Comincioli - Analisi Numerica - Ed. Mc Graw Hill
Modalita’ d’esame
L’esame consiste in una prova orale, che comprenderà anche una discussione sul software matematico sviluppato in ambiente Matlab, secondo le specifiche di seguito riportate.
I Parte della Prova di Laboratorio
Sviluppo, test e valutazione dei codici Matlab per il calcolo numerico di:
− radici di equazioni non lineari mediante il metodo delle tangenti (obbligatorio), delle secanti oppure mediante un metodo ibrido.
− radici reali di polinomi algebrici mediante il metodo di Newton-Horner.
Codificare almeno due algoritmi. La correzione avverrà in Laboratorio.
Suggerimenti per il test e la valutazione del software:
Le radici vanno calcolate con differenti accuratezze (ad es. 10-6 e 10-12), ed anche con la massima accuratezza possibile, valutando l’efficienza dei metodi provati.
Calcolare tutte le radici. Se la funzione è periodica di periodo 2π, calcolare tutte le radici in [0, 2π].
Confrontare poi l'efficienza dei metodi usati (ad esempio considerando i risultati ottenuti ed il numero di iterazioni utilizzate ogni volta).
Calcolare sperimentalmente l'ordine di convergenza dei metodi.
Tracciare il grafico della funzione di cui stanno cercando gli zeri, e giustificare la scelta dell'approssimazione iniziale.
Qualora la convergenza del metodo di Newton non risulti quadratica, riapplicare opportunamente il metodo di Newton in modo tale che la convergenza torni ad essere quadratica. In tal caso trascrivere la funzione a cui è stato applicato il metodo di Newton, i risultati ottenuti ed il numero di iterazioni utilizzate ogni volta.
Nel caso dei polinomi algebrici, confrontare le prestazioni dei due codici. Considerare anche il caso delle radici doppie. Qualora la convergenza del metodo di Newton non risulti quadratica, riapplicare
opportunamente il metodo di Newton in modo tale che la convergenza torni ad essere quadratica.
Alcuni esempi di equazioni non lineari da risolvere:
cos x=log x exp (-2x-1)=1-x
5- 2 cos2 x- 4 sin x = 2 cos2 x x4 +30 x3 +263 x2 + 644 x - 490=0
Consegnare:
− un dischetto con i codici Matlab; può accadere che si proceda a verificarne il funzionamento il laboratorio, anche su funzioni differenti da quelle già utilizzate;
− la stampa su carta dei codici Matlab sviluppati;
− i risultati ottenuti sugli esempi utilizzati.
Algoritmo basato sul metodo delle tangenti Algoritmo ibrido
begin begin
% Inizializzazioni % Inizializzazioni
% Si assegnano x 0, toll, Nmax, f, f’, ……. % Si assegnano x 0=a, x 1=b, toll, Nmax, f, …
f0=f(x0); df0=f ‘(x0) k=1, stimaerrore=…..
Niter=0 while (k < Nmax) and (stimaerrore > toll) Stimaerrore= ……… c= x k-f(x k)( x k- x k-1)/(f(x k)-f(x k-1)) while (Niter < Nmax) and (stimaerrore > toll) If c < a k or c > b k then
x=x0-f(x0)/ f’(x0) % esegui bisezione
stimaerrore = …… c= a k + ½ (b k- a k) Niter = Niter + 1 If f(a k) f(c) < 0 then
x0=x; [a k+1, b k+1] = [a k, c]
end x k+1 = c, x k= a k
If Niter >= Nmax else
errore (‘Non è possibile ottenere l’accuratezza [a k+1, b k+1] = [c, b k] richiesta in Nmax iterazioni’) x k+1 = c, x k= b k
end endif
else
% aggiorna l’intervallo con le secanti if f(a k ) f(c) < 0 then
[a k+1, b k+1] = [a k, c]
else
[a k+1, b k+1] = [c, b k] endif
x k+1 = c endif
stimaerrore=……
k = k + 1
If k >= Nmax then
errore (‘Non è possibile ottenere l’accuratezza richiesta in Nmax
iterazioni’) endif
end
Specifiche d’uso
function [x, Niter, iflag,…] = tangenti(funz,derfunz,x0,toll,Nmax,…) Tra i parametri c’è anche la derivata della funzione
% funz e derfunz sono parametri formali.
% Per valutare la funzione in input e la sua derivata nel punto x all’interno della function di Matlab si usa il comando feval
…… feval(funz,x)
In ambiente comando Matlab
>> tangenti(‘funzionemia’,derfunzionemia, x0, toll, Nmax, …)
% funzionemia.m e derfunzionemia.m sono le functions scritte dall’utente che contengono gli algoritmi per il calcolo della funzione e della sua derivata prima
II Parte della Prova di Laboratorio
− Sviluppo, test e valutazione dei codici Matlab per il calcolo di un integrale definito mediante la formula di quadratura composta trapezoidale e/o di Cavalieri-Simpson, utilizzando per la scelta dei nodi sia uno schema fisso, che uno schema adattivo.
La correzione avverrà in Laboratorio.
Suggerimenti per il test e la valutazione del software:
I comandi Matlab per la quadratura sono quad e quad8.
Utilizzare differenti accuratezze (ed anche la massima accuratezza possibile), verificando che l’accuratezza richiesta sia stata realmente ottenuta, ovvero confrontare la stima dell’errore con l’errore vero . Se non è stata ottenuta l’accuratezza richiesta, provare a spiegarne il motivo, ed eventualmente modificare la strategia di stima dell’errore utilizzata nell’algoritmo.
Confrontare l’efficienza dei due schemi, ad es. confrontando il numero di valutazioni di funzione effettuate dai due schemi a parità di accuratezza. Potrebbe essere utile annotare anche, ad es., il numero di iterazioni utilizzate dall’algoritmo a schema fisso, ed il numero di livelli di suddivisione utilizzati dall’algoritmo adattivo.
Osservare e confrontare anche la scelta dei nodi effettuata dai due algoritmi.
Verificare che il grado di precisione della formula usata sia quello previsto dalla teoria (ovvero ………)
Alcuni esempi di integrali da calcolare (è possibile aggiungerne altri):
∫
∫
− = + − −3
1 2
4 3
10 100
) 9 / 16 log(
20 / 1 ) 30 ( tan 3 ) 40 tan(
4 ) 10 ( tan
x dx x sin
a a
dx x a
Consegnare:
− un dischetto con i codici Matlab; può accadere che si proceda a verificarne il funzionamento il laboratorio, anche su funzioni differenti da quelle già utilizzate;
− la stampa su carta dei codici Matlab sviluppati;
− i risultati ottenuti sugli esempi utilizzati;
− la documentazione esterna dei programmi sulla quadratura.
Documentazione esterna di una routine
o Scopo Descrizione sintetica dello scopo della routine o Specifiche d'uso Testata della routine
o Descrizione Descrizione sintetica della routine e del metodo utilizzato o Bibliografia Eventuali riferimenti bibliografici
o Parametri Descrizione dei parametri: nome variabile, tipo, funzione (in input e/o
o Routines ausiliarie Descrizione di eventuali routines ausiliarie o Indicatori di errori Eventuali segnalatori di errori o anomalie o Accuratezza Ordine di accuratezza assicurato all'utente o Complessità computazionale Ordine di complessità dell'algoritmo utilizzato o Esempio test Esempio test, con dati ed risultati
