Appunti Calcolo Numerico Completi

CALCOLO NUMERICO

Corso di Alfio Maria Quarteroni

Gabriele Santicchi

Ingegneria Biomedica 2019-2020

Sommario

RICERCA DI RADICI DI FUNZIONI NON LINEARI ........................................................................................................ 3

Metodo Di Newton .................................................................................................................................................... 3

Metodo delle secanti ................................................................................................................................................. 3

Metodo Delle Corde .................................................................................................................................................. 3

CAPITOLO 1: ITERAZIONI DI PUNTO FISSO ............................................................................................................. 4

1) TEOREMA ESISTENZA/UNICITA’ PUNTO FISSO ......................................................................................................... 4

2) TEOREMA DI CONVERGENZA LOCALE ....................................................................................................................... 4

APPLICAZIONE DEL TEO 2: METODO DELLE CORDE .................................................................................................. 5

APPLICAZIONE DEL TEO 2: METODO DI NETWON ..................................................................................................... 5

CRITERI D’ARRESTO ....................................................................................................................................................... 5

METODI DIRETTI PER SISTEMI LINEARI .................................................................................................................. 6

=

METODO DI SOSTITUZIONE IN AVANTI (METODO ESATTO) ............................................................................. 6

=

METODO DI SOSTITUZIONE ALL’INDIETRO (METODO ESATTO) ....................................................................... 6

FATTORIZZAZIONE CON MEG ........................................................................................................................................ 6

TEOREMI SU APPLICABILITA’ MEG ............................................................................................................................. 7

FATTORIZZAZIONE DI CHOLESKI ................................................................................................................................ 7

PIVOTING (PARZIALE) ................................................................................................................................................ 7

ERRORI DI ARROTONDAMENTO .................................................................................................................................... 7

STABILITA’ DELLA SOLUZIONE DI UN SISTEMA LINEARE ............................................................................................... 8

PIVOTING TOTALE ...................................................................................................................................................... 8

FILL-IN (RIEMPIMENTO) ............................................................................................................................................. 9

METODI ITERATIVI PER SISTEMI LINEARI ............................................................................................................... 9

METODO JACOBI ......................................................................................................................................................... 10

METODO GAUSS - SEIDEL ............................................................................................................................................ 10

METODI (in forma generale) ITERATIVI LINEARI ......................................................................................................... 10

METODO DI RICHARSDON STAZIONARIO .................................................................................................................... 11

Metodo di Richardson Precondizionato .................................................................................................................. 12

METODO DI RICHARDSON NON STAZIONARIO (M. DEL GRADIENTE) ..................................................................... 13

METODO DEL GRADIENTE CONIUGATO (GC) .............................................................................................................. 14

GC Precondizionato ................................................................................................................................................. 14

CRITERI DI ARRESTO .................................................................................................................................................... 15

Criterio sul residuo ................................................................................................................................................... 15

Criterio dell’incremento .......................................................................................................................................... 15

METODI NUMERICI PER SISTEMI NON LINEARI .................................................................................................... 16

METODO DI NEWTON ................................................................................................................................................. 16

CRITERI D’ARRESTO.................................................................................................................................................. 16

COSTO COMPUTAZIONALE ...................................................................................................................................... 16

APPROSSIMAZIONE DI DATI E FUNZIONI ............................................................................................................. 17

APPROSSIMANTE DI TIPO INTERPOLATORIO .............................................................................................................. 17

INTERPOLATORE LAGRANGIANO ............................................................................................................................... 17

1 – Calcolo Numerico Gabriele Santicchi 2019/2020

APPROSSIMAZIONI ALTERNATIVE A LAGRANGE ......................................................................................................... 19

Interpolazione Lagrangiana Composita ................................................................................................................... 19

Interpolazione di Chebyshev ................................................................................................................................... 20

Interpolatore Trigonometrico .................................................................................................................................. 21

Interpolazione ai minimi quadrati ........................................................................................................................... 22

INTEGRAZIONE NUMERICA ................................................................................................................................. 23

Formula Del Punto Medio Composita ..................................................................................................................... 24

Formula dei Trapezi Composita ............................................................................................................................... 25

Formula di Simpson Composita ............................................................................................................................... 25

APPROSSIMAZIONE NUMERICA DI EQUAZIONI DIFFERENZIALI ORDINARIE .......................................................... 26

APPROSSIMAZIONE DI DERIVATE ................................................................................................................................ 26

Metodo Di Eulero In Avanti (O Esplicito) EA ............................................................................................................ 27

Metodo Di Eulero All’Indietro (O Implicito) EI ......................................................................................................... 27

Aspetti computazionali dei metodi di Eulero .......................................................................................................... 27

Metodo Di Crank - Nicolson ..................................................................................................................................... 28

Metodo Di Heun ...................................................................................................................................................... 29

ASSOLUTA STABILITA’ .................................................................................................................................................. 29

Analisi Assoluta stabilità per EA ............................................................................................................................... 30

Analisi Assoluta stabilità per EI ................................................................................................................................ 30

Stabilità per problemi di Cauchy Generici ............................................................................................................... 30

CONVERGENZA ............................................................................................................................................................ 31

CONSISTENZA .............................................................................................................................................................. 32

LIBRI: Primo è Teoria, Secondo è per esercizi

DA PROBLEMA MATEMATICO A NUMERICO

PORTARE PROBLEMA AL FINITO (=num finito di incognite e equazioni): Necessario per trasformare PM in PN. La soluzione del

problema numerico ricavata con il software deve essere

1. STABILE (cambiando leggermente dati anche la soluzione cambia leggermente) e

( − = )

2. CONVERGENTE: per essere considerata buona e affidabile.

PROBLEMA AL FINITO

h = Passo di discretizzazione; distanza tra un punto e il successivo

2 – Calcolo Numerico Gabriele Santicchi 2019/2020

RICERCA DI RADICI DI FUNZIONI NON LINEARI

() = 0

Trovare valori tali che in un problema numerico. Utilizzo METODO ITERATIVO Con struttura generica:

1) Parto da punto (generico)

0 (1) (2) ()

, , …

2) Genero SUCCESSIONE (Insieme infinito di valori)

(→ ∞)

lim =

3) Voglio che limite di questa successione sia <-> VERIFICARE CONVERGENZA

Esistono diversi metodi in grado di generare ciò; sono tutti metodi iterativi perché essendo problemi non lineari, per essi non

esistono metodi per trovare una soluzione esplicita:

Metodo Di Newton

Secondo Newton quando non so risolvere un problema complesso, è utile cercare di semplificare il problema in un problema che

lo approssima, ma che sono in grado di risolvere. In altre parole, Newton dice che se devo risolvere un problema non lineare per

una funzione complessa che non so risolvere potrei approssimarla ad una funzione più semplice e che di cui sono in grado di

calcolare lo zero. Quali sono le funzioni semplici di cui sappiamo calcolare a mano gli zeri? Le rette, ovvero le equazioni lineari in

( )

una variabile. Quello che piacerebbe fare a Newton è quindi partire da un punto x0, conoscere e poi approssimare la

0

funzione f con una funzione lineare. Nello specifico una retta che approssima f nel punto x0. Quindi…

Sostituisco alla curva la tangente nel punto e trovo intersezione tra asse e

tangente (della quale è necessario ricavare equazione)

+

( ) = ,

E’ un metodo iterativo, procedo fino a quando generando

una successione di valori che posso calcolare.

Efficace… MA Devo conoscere valore derivata prima (non sempre

disponibile... si può evitare utilizzando RETTA SECANTE O CORDA!

Metodo delle secanti

Sostituisco derivata prima con rapporto incrementale

E’ sempre metodo iterativo, troppo altro tipo di successione

La prima volta traccio la retta passante tra f(a) e f(b). Trovo il punto

che interseca l’asse x e lo chiamo x1. Trovo f(x1), traccio la retta

passante per f(a) e f(x1), il punto in cui che questa retta interseca l’asse

x lo chiamo x2, trovo poi f(x2). A questo punto ho due punti f(x2) e

f(x1). Per trovare il terzo prendo la secante tra x2 e x1. Il punto in cui la

secante interseca l’asse x lo chiamo x3. Andando avanti traccio tante

secanti e avvicino il punto intersezione asse x con il vero α. Questo

metodo è molto efficace perché assomiglia molto a Newton, ma non

calcolo nessuna derivata.

Metodo Delle Corde

Utilizza una retta (=corda) fissa (q = rapporto incrementale = costante) per tutte le iterazioni

Disegno la corda che collega f(a) e f(b). Il punto di intersezione

tra la corda e l’asse x lo chiamo x0. Calcolo f(x0). Traccio una

nuova retta, parallela alla precedente, passante per f(x0); ricavo

x1, da qui ricavo f(x1), traccio la nuova retta e così via... Il

coefficiente angolare è facile da calcolare. Questo metodo si usa

poco, a meno che siamo disperati.

Per vedere se sono efficaci, bisogna analizzare CONVERGENZA alla soluzione (=radice) del PM

3 – Calcolo Numerico Gabriele Santicchi 2019/2020

CAPITOLO 1: ITERAZIONI DI PUNTO FISSO (Slide 1.24)

;

Ho intervallo [a;b] su cui ho funzione considero bisettrice y = x e osservo se ci sono punti di

)); = ().

intersezione. (es. A (, hanno proprietà particolare: Essi sono i PUNTI FISSI DELLA

→

. () − = 0 () = () −

FUNZIONE Perciò Definisco

().

PROPRIETA’: PUNTO FISSO DI se e solo se è ZERO di Quindi

Come cerco i punti fissi? Introduco algoritmo: METODO DELLE ITERAZIONI DI PUNTO FISSO

() () () ()

, , . . , ( );

Genero successione di numeri reali ( e per ciascuno di essi calcolo osservo

!

che mano a mano mi avvicino ad ()!

Metodi di NEWTON e CORDE possono essere visti come iteraz di P.FISSO introducendo variabile (Sl 1.27; Audio 2.12:00)

SECANTE NON LO E’

(+1) () (−1)

( ℎ )

Quindi per analisi convergenza METODO

CORDE/NEWTON basta studiare convergenza delle

iterazioni di punto fisso relative!

In generale NON è vero che IT.P. FISSO è sempre

convergente! →

() =

Ad es. se cerco punti fissi della , NON ci sono punti fissi (=NO intersezioni con y=x) le iterazioni di punto fisso

(+1) ()

= ( ) NON convergono. Necessari teoremi (2) per affermare l’esistenza/unicità

di punti fissi..

1) TEOREMA ESISTENZA/UNICITA’ PUNTO FISSO

NB continua →

1. Se ogni immagine di x [a,b] è ancora all’interno di [a,b] Ne esiste almeno uno →

, < 1

2. Comunque scelga in [a,b], differenza tra le immagini (L) converge <->

1 2 ()

Unicità punto fisso + Iterazione di punto fisso converge ad

NB convergenza dipende da [a,b]; come trovo l’intervallo [a;b] t.c valga la proprietà 2.

Richiesta dal TEO? →

Inoltre proprietà richiesta 1. E’ molto restrittiva! Necessario

2) TEOREMA DI CONVERGENZA LOCALE

= funz di iterazione con punto fisso. E’ continua, e continua anche la sua derivata prima. Allora:

1. Se scelgo vicino ad tale che valga la relazione riportata

0 ()

→

Successione converge ad + vale la relazione

′′() ′() = 0

2. Se è continua anche ed è nulla (NON semplicemente <1 come in 1.)

()

→

Successione converge ad + vale la relazione 2

è (= )

Dice che

Il punto precedente convergeva a passo 1, questo a passi successivi! CONVERGO

CON RAPIDITA’ MAGGIORE

Si chiama CONV.LOCALE perché deve essere abbastanza vicino ad (NON come nel TEO precedente)

0

METODO DI NEWTON (M di punto fisso) sarà di ordine 2, METODO DELLE CORDE di ordine 1

4 – Calcolo Numerico Gabriele Santicchi 2019/2020

APPLICAZIONE DEL TEO 2: METODO DELLE CORDE

′ ′

() ()

= 0, = 1 − 0 = 1!

NON posso dire niente su convergenza..

′ ()

≠ 0,

Se allora può essere convergente

, !)

Metodo ci dice come devo scegliere (↔ affinchè abbia la convergenza lineare

APPLICAZIONE DEL TEO 2: METODO DI NETWON ′ ′

()

() = 0 ′() ≠ 0, = 0, ′() ≠ 0!

Se è radice semplice si ha sostituendo ottengo

applicando il TEO CONV LOCALE.. Osservo che ho CONVERGENZA DI ORDINE 2

CRITICITA’

• deve essere scelto molto vicino

• →

Se è radice doppia/multipla convergenza NON più 2° ma LINEARE, come nel M. Delle Corde!)

Es. di radice semplice ed esempio di radice doppia (esistono anche radici multiple)

Necessario modificarlo affinchè converga sempre a ordine 2..

à !

NETWON MODIFICATO: Se non

ne sono a conoscenza, utilizzo algoritmi in grado di stimarne valori

Esiste altro metodo (METODO DELLE SECANTI), che è intermedio tra i due

appena analizzati (e molti altri...)

CRITERI D’ARRESTO

?

Quando fermo il processo iterativo? Quando è abbastanza vicino ad Due criteri, basati su controllo:

); |( )|

(