Teoria calcolo

22/2/21

Partiamo sempre da un problema fisico. Attraverso la

modellistica matematica arrivo al problema matematico

(che sarebbe solo la traduzione del problema fisico tramite

equazioni) (d sono i dati).

Passo attraverso l’approssimazione numerica e arrivo al

problema numerico(che è un’approssimazione del

problema matematico). Poi all’algoritmo (che è una

sequenza finita di operazioni). Attraverso il linguaggio

matlab e octave ho una soluzione computazionale.

Il calcolatore lavora con un’aritmetica finita, che ha una memoria finita. Aritmetica floating point (per

certi numeri ci sarà un’approssimazione).

Devo verificare che la soluzione numerica Xn esiste ed è unica.

Verificare che sia stabile, cioè la soluzione numerica deve dipendere dai dati in una maniera limitata.

Verificare che sia convergente, ovvero che |Xn-Xm|, che sarebbe l’accuratezza, voglio la differenza

sia piccola

PROBLEMI MATEMATICI

1- radici di equazioni non lineari

2- sistemi lineari

3- interpolazione —> fornire una funzione che passa in più punti

4- integrazione

5- equazioni differenziali ordinarie (EDO) —> che sono i problemi di Cauchy

PROBLEMA Se la derivata è uguale a 0 , la variazione

nel tempo del numero di batteri è nulla.

Quindi io cresco ma arrivo a una certa

che non cresco più.

Questo era il problema matematico. Per

arrivare al problema numerico uso le

approssimazioni.

L’idea è di discretizzare l’intervallo di tempo T

in intervalli di ampiezza h. Tra un intervallo e

l’altro dico che c’è un tempo tk . Devo

soddisfare l’equazione iniziale per ogni tempo,

provo così a soddisfarla per i tempi discreti

che io ho generato.

1- RICERCA DI RADICI DI FUNZIONI NON LINEARI

Radici ed equazioni non lineari

1.1

Esempio: immagino di investire una quota v=quota annuale, per un numero di anni n.

R= tasso di rendimento

La quota che io ottengo dopo tot anni —>

Quanto deve valere r per accumulare M dopo n anni, dato l’investimento annuale v?

Obiettivo: data f(x) , f : I R

Voglio trovare numero reale α R tale che f(α)=0. α È la radice

Esempio

Ho una funzione f(x)

Voglio trovare α

Ma questa era un’equazione lineare

Spesso non è possibile determinare α in maniera analitica, quindi uso metodi numerici.

Metodi iterativi locali

1.2

L’idea è di costruire una successione di approssimazioni di α, nello specifico avrò:

Esempio Voglio costruire una successione di approssimazioni che tendono

ad andare verso la mia radice

Convergenza

Io vorrei che:

NB non posso fare infinite iterazioni

Metodo di Newton

• Suppongo di essere in un punto E di aver già

trovato un’approssimazione al passo k-esimo. Valuti

f al passo k-esimo e costruisci la retta tangente.

L’iterata di Newton è tale che: È l’intersezione tra Yk(x) con l’asse delle ascisse.

L’iterata di Newton è:

METODO DI NEWTON (ALGORITMO)

• Scelgo iterata iniziale

• Per k=0,1,2...

Osservazione: sulla carta il metodo converge in un infinito numero di iterazioni. L’algoritmo viene in

realtà arrestato quando un certo criterio di arresto è soddisfatto. Mi voglio fermare quando :

Esempio: I metodi iterativi locali (come Newton)

convergono se l’iterata iniziale

è su cientemente vicino ad alfa.

Su cientemente vicino vuol dire che :

Esempio: Mi sono allontanato dalla mia radice. Questa è

una divergenza. Questo succede perchè il mio

metodo genera una successione

che non converge, perchè l’iterata iniziale non era

su cientemente vicino ad alfa.

Oss: questo comportamento e la convergenza di

Newton si può spiegare interpretando il metodo

come metodo delle iterazioni di punto sso.

Osservazione: per usare Newton devo calcolare la derivata prima della funzione , questa può essere

difficoltosa. Si possono usare metodi alternativi a Newton

Metodo delle corde

•

q approssima la derivata prima Usare questo metodo vuol dire costruire

una pendenza che è sempre ssa per

ogni iterata, è data dalla retta passante

per il punto iniziale e nale dell’intervallo

Metodo delle secanti

•

Dice che : per k=1,2,... Osservazione: funzionano se la prima iterata è

su cientemente vicino a alfa 24/2/21

Iterazioni di punto fisso

1.3

Osservazione:

Definizione: detta phi(x) la funzione di iterazione , alfa è punto fisso se alfa=phi(alfa)

Osservazione: se phi(x)= f(x) + x allora alfa è radice di f <-> alfa è punto fisso di phi

Interpretazione grafica del punto fisso: traccio bisettrice I-III quadrante, e identifico l’intersezione

Osservazione: voglio approssimare il punto fisso alfa di

phi. C’è un algoritmo —> delle iterazioni di

algoritmo

punto fisso.

Osservazione:

Esempio:

La derivata prima è minore di 1 ma maggiore di -1, se è negativa converge a ragnatela, se no

convergo sempre dallo stesso lato.

Proposizione: convergenza globale in un intervallo

Data

1) se phi è continua in [a,b] e phi(x) appartiene ad [a,b] per ogni x appartenente ad [a,b], allora esiste

almeno un punto fisso di phi, alfa appartenente a [a,b]

2) se oltre all’ipotesi 1 , esiste una costante L tale che 0<=L<1, e per cui

per ogni x1,x2 appartenenti a [a,b] , allora il punto fisso è unico e l’algoritmo delle iterazioni di punto

fisso converge ad alfa per ogni scelta di

( posso partire da qualsiasi punto nell’intervallo per arrivare poi a convergere)

Per avere convergenza richiedo che tutti i rapporti incrementali in [a,b] siano minori di 1 in modulo.

Proposizione: convergenza globale in un intervallo

Se phi è

1) continua in [a,b] e phi(x) appartiene ad [a,b] per ogni x appartenente ad [a,b], allora esiste almeno

un punto fisso alfa in [a,b]

2) se phi è derivabile con continuità in [a,b] e se

allora il punto fisso è unico in [a,b] e le iterazioni di punto fisso convergono ad alfa , ovvero:

Osservazione:

Osservazione: L è il valore massimo che assume la derivata prima di phi in [a,b] , se phi è derivatile

con continuità nell’intervallo.

Osservazione: se L è vicino a 0 (cioè se la derivata prima di phi è circa zero), allora l’errore si abbatte

in poche iterazioni.

Se L è circa 1, ma minore di 1, servono più iterazioni per ridurre l’errore.

(Se ho funzione di iterazione più piatta possibile allora mi servono poche iterazioni)

La convergenza globale spiega come convergono le iterazioni di punto fisso per ogni scelta di

un’iterata iniziale in [a,b].

Teorema : convergenza locale/ di Ostrowski

• (ovvero in un intorno del punto fisso)

Ad ogni iterata l’errore si riduce.

Se phi’ è 0.99 l’errore si riduce di poco

Se

Osservazione:

Proposizione ( di convergenza locale):

Allora il metodo delle iterazioni di punto fisso converge per Sufficientemente vicino as alfa con

ordine p=2

(Meglio convergere con ordine 2 perchè l’errore sta scendendo in mod più rapido.)

Convergenza rapida per funzioni che tagliano la bisettrice in modo tipo piatto, cioè la derivata prima

è zero. E si dice convergere con ordine 2.

Osservazione : CRITERIO DI ARRESTO DEL METODO DI ITERAZIONI DI PUNTO FISSO

Non posso iterare fino ad infinito criterio differenza tra iterate successive

Introduco un indicatore dell’errore —> —> mi fermo a

k+1 tale che:

Il criterio è soddisfacente se

Il criterio non è soddisfacente se. Perchè l’errore è sottostimato dalla differenza di

iterate successive

• Se Errore sovrastimato dalla di erenza,

criterio è comunque soddisfacente

anche se faccio più del necessario.

• metodo di Newton come metodo di iterazioni di punto fisso

Se scelgo

Allora posso interpretare il metodo di newton come metodo di iterazioni di punto fisso

Definizione: la radice alfa di f è semplice se f(alfa)=0 ma f’(alfa) diverso da 0

Definizione: la radice di f ha molteplicità m se f(alfa)=0

Proposizione:

Proposizione: se alfa è radice semplice (quindi m =1) allora il metodo di Newton converge con

ordine p=2, infatti ho che:

Se alfa è radice multipla (m>1) allora il metodo di Newton converge con ordine p=1

Metodo di Newton modificato

•

L’iterata k-esima dipenda da m

Nota m posso ripristinare l’ordine di convergenza p=2 anche se m>1 3/3/21

Criteri di arresto per il metodo di Newton

•

1) differenza tra iterate successive: arresto le iterazioni quando la differenza tra due iterate

successive scende sotto una certa tolleranza (scelta a priori) Questo è un buon criterio

quando:

Siccome il metodo di Newton si può interpretare come metodo delle iterazioni di pnt fisso, è noto

che il criterio sia soddisfacente se

Se alfa è semplice allora

Se alfa è multiplo il criterio non è soddisfacente perchè l’errore è sottostimato dalla differenza tra

iterate successive

2) criterio del residuo: mi fermo quando il valore del residuo al passo k che è

Deve essere minore di una certa tolleranza.

Sappiamo che f(alfa)=0. Quando il criterio è soddisfacente? Cioè

Soddisfacente se f’(x)=1 per ogni x appartenente all’interno di

alfa.

Se invece la pendenza è maggiore di 45 —>. Il

criterio è inosddisfacente perchè l’errore vero è sovrastimato dal

residuo. Vuol dire che mi fermo quando residuo è sotto una

certa tolleranza ma il mio errore è molto più piccolo.

Se invece la pendenza è molto bassa l ‘errore è molto maggiore

del residuo. Il criterio è quindi insoddisfacente perchè l’errore è

sottostimato dal residuo.

metodo delle corde

•

Tale metodo può essere interpretato come metodo delle iterazioni di punto fisso con iterata:

Il metodo converge se :

Osservazione: il metodo delle secanti non è interpretabile come metodo delle iterazioni di punto

fisso. 2) SISTEMI LINEARI

Risolvere un sistema lineare Ax=b , dove

L’elemento della matrice A

Definizione: la matrice A è non singolare<-> det(A) diverso da 0

Proposizione: se A è non singolare, allora esiste un’unica soluzione x del sistema lineare

Osservazione: in generale , dobbiamo risolvere sistemi lineari di dimensione n grande. Devo usare

un calcolatore. Devo usare metodi per risolvere il sistema lineare che si traducano il algoritmi

computazionalmente efficenti.

Esempio

Emessi dei raggi x e una parte viene assorbita dal corpo in maniera diversificata a seconda delle

proprietà del materiale (la densità). L’idea è che il tubo che emette i raggi e il rilevatore devono

girare.

Il nostro corpo venga diviso il piccolo dimensioni, se la densità di queste porzioni è grande allora

riaveranno meno raggi x al rilevatore. In bidimensionale

bi= porzione di raggi x assorbita lungo la direzione i-esima

Questo può essere visto come un sistema Ax=b

(A)ij = 1 se il pixe j-esimo è attraversato dal raggio i-esimo

Osservazione: come risolvere sistema lineare?

Il numero di operazioni da effettuare con il metodo di Cramer è (3(n+1)!) , un calcolatore ha una CPU

che è in grado di effettuare 1 miliardo di operazioni al secondo (pari a 1GHz).

Tempo CPU= n operazioni che farei a meno/ potenza in GHz

Osservazione : se il determinante di A è diverso da 0 esiste

Con il calcolatore non lo faccio mai perchè costa molto di ppiù e richiede molta memoria al

computer per eseguire l’operazione. Gli errori computazionali in oltre si amplificano.

METODI DIRETTI

2.1

Sono metodi numerici per risolvere il sistema lineare in cui si effettuano un numero finito di passaggi

noto a priori.

Osservazione: i metodi diretti riconducono la soluzione di Ax=b a quella di sistemi lineare più

“semplici” da risolvere.

Vediamo i metodi semplice:

• matrice triangolare inferiore

Algoritmo delle sostituzioni in avanti: ovvero parto dalla prima riga trovando X1, lo metto nella

seconda riga e trovo X2 ecc. in particolare l’algoritmo è :

Quante operazioni: divisioni —>(una sulla prima riga e una sulle righe successive) n divisioni

Prodotti —>

Somme e sottrazioni —>

La somma di queste operazioni fa n^2

Osservazione: det(L) = prodotto degli elementi che stanno sulla diagonale principale

• matrice triangolare superiore

Algoritmo delle sostituzioni all’indietro

N^2 operazioni

Osservazione:

• metodo della fattorizzazione LU

Def: data una matrice. non singolare, la sua fattorizzazione LU consiste nel trovare una

matrice triangolare inferiore L e una matrice triangolare superiore U , tale che A=LU (se esistono).

Oss: voglio risolvere Ax=b. Se esistono L e U tale che A=LU allora LUx=b

Introduco vettore ausiliario y=Ux

Il primo sistema è triangolare inferiore, il secondo triangolare superiore.

Li risolvo con gli algoritmi trovati sopra

Def: il metodo della fattorizzazione LU per risolvere il sistema lineare Ax=b consiste in:

1) determinare se esiste la fattorizzazione LU di A

2) risolvere sistema triangolare inferiore ( Ly=b) con l’algoritmo delle sostituzioni in avanti

3) risolvere sistema triangolare superiore (Ux=y) con l’algoritmo delle sostituzioni all’indietro

Oss: n=2

Problema sottodeterminato perchè ho più coefficienti che equazioni. In generale ho n+n^2

coefficienti e solo n^2 equazioni (vincoli) —> per convenzione fisso n elementi di L pare ad 1 sulla

diagonale principale.

• metodo di eliminazione di Gauss (MEG)

è un metodo che fornisce i fattori L e U di una matrice A non singolare, ammesso che esistano.

—> algoritmo MEG

Esempio:

Come faccio a fare venire lo 0 li? Prendo la seconda riga di A la devo sottrarre a un coefficiente e

moltiplico con la prima 10/3/21

Oss stavamo vedendo le soluzioni del sistema lineare con metodi diretti, in particolare con il metodo

della fattorizzazione LU

1) determino L e U tale che A=LU tramite MEG

2) soluzione Ly=b con algoritmo sostituzioni in avanti

3)soluzione Ux=y con algoritmo sostituzione indietro

L’algoritmo trasforma A in U e cea la matrice L dei moltiplicatori, sfruttando gli elementi pivotali che

compaiono

Esempio

Oss il MEG comporta un costo computazionali di (2n^3/3) operazioni

1) MEG 2n^3/3

2) Ly=b n^2

3) Ux=y n^2

Per n grande prevale MEG che è comunque