Riassunto "Calcolo numerico e programmazione"

Modello numerico

Si utilizza quando un problema non può essere risolto (o è difficile da risolvere) tramite metodi analitici.Il modello numerico consiste nel discretizzare il modello matematico (continuo).Discretizzazione: consiste nel generare un numero finito di numeri. Ciò comporta che la soluzione non sarà esatta ma approssimata e si può stimare l'errore.

Algoritmo

È un numero finito di operazioni logiche che consentono di ottenere da un numero iniziale di dati un numero finito di risultati.Serve a cercare le soluzioni approssimate partendo dal modello numerico.

Metodo numerico

Un modello numerico è l'algoritmo per la sua risoluzione. Deve avere:1) Accuratezza: precisione del risultato ed errore limitato;2) Efficienza: velocità di calcolo;3) Stabilità: risultati simili in corrispondenza a dati iniziali simili.

Analisi degli errori

Nel calcolo numerico si commettono sempre due tipi di errori:1) Errori di arrotondamento dovuti all'utilizzo del calcolatore (essendo una macchina finita non può fare operazioni all'infinito ma solo discrete);2) Errori di troncamento: le approssimazioni che ci afflitta sempre un'approssimazione rispetto al metodo analitico.

• Errore computazionale = arrotondamento + troncamenti
• Errore computazionale assoluto: ε_a = x - x̃ (x = soluzione esatta, x̃ = sol. approssimata)
• Errore computazionale relativo: ε_rel = ε_a / x (rapporto alla grandezza della soluzione esatta)

Sistema Floating-point

Sistema col quale il calcolatore rappresenta i numeri reali:x = (-1)^S (0, a₁, a₂ ... a_s) ⋅ B^F

• S:
  • da segno
• 0 positivo
• 1 negativo
• a_n: cifre presenti nel numero
• B: base (d; norma B = 10)
• F: esponente, numero di cifre prima della virgola
• α₁B^ϒ + α₂B^ϒ-1 + α₃B^ϒ-2 = mantissa

Epsilon di macchina

ε_m = Β^1-t (t: numero di cifre della mantissa)Rappresenta la distanza tra 1 e il numero maggiore di 1 più vicino ad esso rappresentabile col sistema floating-point: ε_m ≈ 2 ⋅ 10^-16 circa

Precisione di macchina

u = Σz_iB^i-t massimo errore che la macchina commette quando rappresenta un numero col sistema floating-point. Quindi l'errore di arrotondamento è sempre di u: |x - R(x)| ≤ u

Condizionamento

Un problema è ben condizionato quando la soluzione non diffresce molto dalla soluzione esatta per piccole variazioni in ingresso ed è mal condizionato quando e non sensibile alle soluzioni simili in ingresso. Se R(x _rosso) < ε_relEs: errore nel metodo numerico si propaga. Nel calcolo numerico si risolve: E₁, E_t → E_fStima errore di troncamento: ε_t ≈ c ⋅ h^ϒ

Algebra matriciale

Particolari matrici:

• simmmetrica: \(A^T = A\)
• ortogonale: \(A^T A = AA^T = I\)
• hermitiana: \(A^N = A\) \( (A^* =\) trasposta coniugata di \(A) \)
• diagonale se \(a_{ij} = 0\) per \(i \neq j\)
• triangolare superiore se \(a_{ij} = 0\) per \(i > j\)
• triangolare inferiore se \(a_{ij} = 0\) per \(i < j\)
• invertibile se \(\det A \neq 0 \Rightarrow A^{-1} A = AA^{-1} = I\)
• definita positiva: \( x^* Ax > 0\)
  • \(x\) vettore orizzontale
  • \(\bar{x}\) vettore verticale

Criterio di Sylvester: una matrice Hermitiana è definita positiva se e solo se tutti i suoi minori principali di testa (determinator della sottomatrice formata con i primi k elementi di A) sono positivi.

• convergente: \(\lim_{k \to \infty} A^k = 0\), matrice nulla

Autovalori: \(\lambda\) è autovalore della matrice \(A\) se il sistema \(Ax = \lambda x\) ammette soluzioni \(\neq 0\).

In questo caso x è autovettore associato a \(\lambda\). \(\lambda\) è autovalore di \(A\) se e solo se il polinomio caratteristico è zero: \(\det(A - \lambda I) = 0\). Spettro: insieme di tutti gli autovalori di A.

Raggio spettrale: è il maggiore autovalore in modulo: \(\rho(A) = \max |\lambda|\).

\(A^k\) è convergente se e solo se \(\rho(A) < 1\).

Gli autovalori di una matrice hermitiana sono tutti reali.

DIM. Da \(Ax = \lambda x\) si moltiplica per \(x^*\), \(x^* Ax = \lambda x^* x \Rightarrow x^* Ax = \lambda x^* x\). Dove \(x^* x\) = reale positivo in quanto prodotto di un vettore per il suo trasposto

\(x^* Ax\) = reale positivo poiché \((x^*) x)\) \(x^* Ax = x^* Ax\)

\(\Rightarrow \lambda \in \mathbb{R}\).

Se \(A\) è definita positiva i suoi autovalori sono positivi (e viceversa).

Norma: è una funzione \(\|.\| : \mathbb{C}^m \to \mathbb{R}\) tale che:

1. \(\|x\| \geq 0\), \(\|x\| = 0\) solo per \(x = 0\)
2. \(\|c x\| = |c| \cdot \|x\|\)
3. \(\|x + y\| \leq \|x\| + \|y\|\)

La norma di una matrice è \(\|.\| : \mathbb{C}^{m \times n} \to \mathbb{R}\) e richiede due ulteriori condizioni:

4. \(\|AB\| \leq \|A\| \cdot \|B\|\) _{submoltiplacità}
5. \(\|A I\| = \|A\| \cdot \|I\|\) _{compatibilità}

Norma indotta o norma matriciale ricavata da una norma vettoriale.

TR. Per ogni norma matriciale indotta vale la relazione \(\rho(A) \leq \|A\|\).

DIM. Sia \(\lambda\) un generico autovalore. Si ha da \(A x = \lambda x => |\lambda| = \|Ax\|/\|x\| \leq \|A\| \cdot \|x\|/\|x\|\leq \|A\|\) quindi \(|\lambda| \leq \|A\|\), il che vale anche per l’autovalore di modulo massimo \(\rho(A)\leq \|A\|\).

Dato ciò se \(\|A\| \leq r < 1 => \rho(A) < 1 \Rightarrow\)se \(\|A\| < 1\) allora \(A\) è convergente.

TR. Se \(A\) è hermitiana il raggio spettarale corrisponde con la norma 2 di \(A\).

DIM. \(\|A\|_2 = \rho(A^*A) = \rho(A^*) \cdot \rho(A) = \rho(A)\)

Metodo di Richardson

Generalizzazione dei metodi iterativi, serve a far convergere più velocemente il metodo introducendo ad ogni iterazione il parametro α_k. quindi le iterate successive si calcolano come: x^(k+1) = x^(k) + α_k r^(k)

Stazionario: fai il parametro α_k costante.

Il metodo di Richardson stazionario converge se ∃ β 0<α>β<2λ_max (2: autovalori di P^-1A)La velocità di convergenza è massima nel valore ottimale: α_opt = λ_min+λ_max

Dinamico: hai il parametro α_k variabile ad ogni iterazione. Il metodo converge se A, P sono simmetriche definite positive e r^(k) r^(k)>z^(k) Az^(k) In questo caso il metodo è detto del gradiente precondizionato; se P=I è detto metodo del gradiente.

Metodi di rilassamento

Servono ad avere tecniche di risoluzione più rapide.Si ha: P = 1ωD - E con {ω<2α_k = 1

Equazioni non lineari

Determinare le radici di un’equazione equivale a trovare gli zeri di una funzione.Tutti i metodi numerici per la ricerca degli zeri sono iterativi.Un metodo iterativo è convergente se la successione da esso generata converge alla soluzione esatta: lim _k→∞ x^(k) = x* dove x*: &betta;(x*) = 0.

Ordine di convergenza: determina la velocità di convergenza del metodo. Un metodo ha ordine di convergenza p se esiste una costante c: lim _k→∞ |x^(k+1) - x*||x^(k) - x*|^p= c

All’aumentare di p l’errore diminuisce più velocemente e quindiil metodo converge più velocemente.

Metodo di bisezione

Consiste nel dimezzare sempre l’intervallo all’interno del quale si annulla la funzione in modo da arrivare iterativamente nel punto in cui f(x)=0. Per applicare il metodo bisogna:1) Scomporre l’intervallo iniziale in due sottointervalli;2) Si sceglie l’intervallo in cui la funzione ammette almeno uno zero;3) In tale intervallo si approssima la soluzione col punto medio f;4) Si ripete da punto 2).In questo modo l’errore è sempre massimo la metà dell’iterazione precedente quindi il metodo è convergente. La velocità di convergenza è lenta (p=1; c= ¹/₂).

Metodo di Newton-Raphson

Si sceglie un punto a caso x⁽⁰⁾ e si traccia la tangente alla funzionecorrispondente al punto x⁽⁰⁾. All’intersezione tra la tangente e l’assedelle x si ha il punto x⁽¹⁾. Si traccia la tangente alla funzione in corrispondenza di x⁽¹⁾ ecc. Si ottiene il metodo iterativo: x_n+1 = x_n -f(x_n)f’(x_n)

Questo metodo è sempre convergente e converge velocemente. Il metodo di Newton-Raphson non garantiscela soluzione di due estremi medi; se la pendenza è prossima a zero converge in modo non incrementale.