Teoria calcolo

CRITERI D'ARRESTO

• residuo

• Differenza iterate successive

Oss Newton è un metodo locale. Convergenza si ottiene per sufficientemente vicino alla radice x

Oss ordine convergenza di Newton. Se è sufficientemente vicino a x e allora il metodo di Newton converge con ordine 2

Esempio

Oss se il metodo di Newton converge con ordine 2 ho bisogno di poche iterazioni per ottenere un risultato accurato.

Se n>>1 potrei avere problemi con la memoria del PC se la Jacobiana è matrice piena

Oss una strategia consiste nel tenere fissa la matrice Jacobiana per m iterazioni

Posso combinarlo con metodo della fattorizzazione LU di Jf

Oss faccio più iterazioni che con il metodo di Newton

Oss uso il metodo di Newton inesatto in cui costruisco un'approssimazione di

Algoritmo metodo di Broyden 7/4/21

APPROSSIMAZIONE DI DATI E FUNZIONI

3. esempi e introduzione al problema

3.1 Esempio

Suppongo di dover svolgere prove di trazione. Voglio individuare una legge costitutiva

Il problema dell'approssimazione di dati (o di una funzione) consiste nel determinare una funzione che abbia buone proprietà di approssimazione di tali dati e che abbia carattere predittivo.

Esempio ambiente finanziario, ho evoluzione nel tempo di un bene interpolazione polinomiale di Lagrange.

Un'approssimante si dice interpolatoria (interpolante) se un interpolante polinomiale è tale che ha la struttura di un polinomio di grado n. Devo determinare i miei coefficienti.

Oss ho le coppie. Il det di B è diverso da 0 se e solo se i nodi sono distinti, quindi solo in questo caso esiste una soluzione unica. Questo approccio non si usa mai perché B è mal condizionata anche per n piccolo -> costruzione inaccuparata dell'interpolante.

Serve quindi una strada alternativa -> metodo dell'interpolazione polinomiale di Lagrange. Def dati n+1 nodi distinti xi con i=0,...,n, il polinomio caratteristico di Lagrange associato al nodo xk.

èOssÈ il prodotto di n polinomi di grado 1

OssEsempioOss dati n+1 nodi distinti XI, i=0,...,n, costruisco n+1 polinomi caratteristici di Lagrange

OssInfatti è la combinazione lineare di n+1 polinomi caratteristici di grado n

Oss Interpola le coppi di dati

È unico interpolante delle coppie di dati e di grado n

Suppongo che ne esista anche un altro che interpola gli stessi dati

EsempioAccuratezza interpolazione polinomiale

Devo conoscere la funzione f(x) che genera i dati.

Def la funzione errore è:—> sia I un intervallo delimitato dai nodi, I=(x0, xn) , e gli n+1 nodi XI sono distinti. Se

se i nodi sono equispaziati (cioè hanno la stessa distanza tra loro) si può dire che:

OssOss convergenza

Con n che tende ad in nito spero che interpolante migliori al crescere del grado n equindi dei nodi xi

Oss per molte f, l’interpolazione polinomiale converge con n—> + inf

Per altre f, l’errore cresce per n—> +inf se

i nodi sono equispaziati (fenomeno di Runge)

Oss funzione di RungeL'errore aumenta agli estremi dell'intervallo per n->+inf e sui nodi equispaziati

Si rimedia in due modi:

• o interpoli su nodi non equispaziati
• o cambi tipo di interpolazione

Oss per controllare il fenomeno di Runge, ovvero errore cresce al crescere di n, e altri problemi distabilità dell'interpolante, un'idea è di usare nodi NON equispaziati nell'intervallo I =[a,b]

Interpolazione polinomiale di Lagrange su nodi di Chebyshev

Suppongo di considerare intervallo I = [-1,1]

I nodi sono più densi agli estremi dell'intervallo

Oss in generale abbiamo i nodi di Chebyshev da riportare sull'intervallo generale [a,b]

Oss costruisco i polinomi caratteristici di Lagrange sui nodi di Chebyshev

Se f è nota avrò il polinomio interpolante della funzione ->TEOREMA se f

OssHo sempre convergenza per s>=1 e la convergenza è

dei sottointervalli tende a zero allora l'errore scende e tende a 0 tanto più rapidamente tanto più è grande k (k+1 si dice ordine di convergenza rispetto ad H)

Oss su ciascun sottointervallo Ij devo evitare il fenomeno di Runge, tipicamente k<3,4 (se f data)

Oss se invece i dati provengono da misure

Quindi devo operare delle scelte su k e su H per costruire interpolante composito di grado k ovvero

Interpolazione trigonometrica3.4

Consideriamo una funzione f periodica con periodo 2π

Introduco una partizione dell'intervallo [0,2pi) con n+1 nodi equispaziati xj

Voglio costruire un interpolante trigonometrico e periodico

Oss assumiamo che n sia pari e

OssEquivalente alla precedente per

OssHo n+1 equazioni per trovare n+1 coe cienti di f

Oss la matrice T trasforma informazioni della funzione f dallo spazio sico allo spazio dellefrequenze. Trasforma valori nodali a coe cienti associati alla frequenza k-esima

Oss det(T) è diverso da 0 —> posso

passare dallo spazio delle frequenze c a quello sico f conOssÈ stata progettata la fast fourier transform che consente l’operazione precedente inFFT sfrutta la struttura particolare della matrice T ( di Toeplitz)EsempioOss è possibile riscrivere l’interpolante trigonometrico come un interpolante Lagrangiano

TEOREMA —> se f è periodica e foss l’interpolazione trigonometrica può so rire del fenomeno dell’aliasing —> costruiscointerpolante trigonometrico f con frequenze caratteristiche non corrette se il numero di dati (n+1) ètroppo basso rispetto alla frequenza massima associata ad f

TEOREMA DI SHANNON devo prendere il numero di punti tale che n> 2Kmax(Devo prendere un numero di punti maggiore al valore massimo della frequenza moltiplicato per 2)Oss l’insieme dei coe cienti determina lo spettro del segnale f 5/5/21approssimazione nel senso dei minimi quadrati3.5Immaginiamo di conoscere le coppie di dati

Cosa succede fuori da a b?

Come rappresentare nel complesso questi dati senza necessariamente interpolarli se n è grande, emagari anche con rumore e incertezze?

Come usarli per fare predizioni? (Estrapolazione al di fuori dell'intervallo [a , b]) -> abbandono il vincolo di interpolazione: q(xi) diverso da yi per qualche i = 0 , ... , n

Oss l'approssimante q dei dati nel senso dei minimi quadrati è un polinomio globale.

Il problema consiste nel determinare i coe cienti del polinomio.

Def: il problema dei minimi quadrati consiste nel trovare il polinomio q tale che lo scartoquadratico medio rispetto ai dati è minimo, ovvero cerco il polinomio q tale che ->

Esempio

Esempio

Def la retta di regressione è un polinomio nel senso dei minimi quadrati di grado m=1

Oss solitamente m << n

Oss in generale , devo trovare m+1 coe cienti del polinomio

Come si trova retta di regressione ?

Introduco una funzione a due variabili

Devo trovare a0 e a1