Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
CALCOLO NUMERICO
Soluzione di equazioni non lineari
voglio ξ t.c. f(ξ)=0
Se x=ξ f(x)=0
x∈[a,b]
x∈[a,b]
- y=f(x)
- y=0
L'esistenza e l'unicità della soluzione può dipendere dall'intervallo considerato
ESISTENZA => Se f(x) continua e f(a)⋅f(b) <0
UNICITÀ => Se f(x) monotona
Noi cerchiamo un'approssimazione di ξ. È bene dare una tolleranza
cerco x1 t.c. |ξ - x1| < toll
ε = |ξ - x1| = errore -> dà una valenza teorica
Noi useremo lo scarto tra due soluzioni successive
(xn+1 - xn)
cerco una successione lim xn = ξ0
METODI
- Bisezione
Troviamo x ∈ [a0, b0] t.c. f(x) = 0
- (f continua in [a0, b0]) → cond. sufficiente per x∗
- f(x0) . f(x1) < 0 ∀x ∈ [a0, b0] → cond. sufficiente per x∗
Dato [a0, b0]
Costruisco In = [an, bn] ∈ [a0, b0]
tale che ξ ∈ In
lim In = |bn - an| = 0
n→∞
Trovo il punto medio di [a0, b0] = x1 = (b - a) / 2
Se x1 > 0 → b1 = x1
Se x1 < 0 → a1 = x1
Algoritmo
Dato I0 = [a0, b0] con ξ ∈ [a0, b0]
Dato ϵ>0
iter=0
a= a
b= b
Scarto = 2 ϵ
WHILE (scarto > ϵ & iter ≤ Tmax)
- xn = (an + bn) / 2
- if f(an) . f(xn) > 0
- an = xn
- else
- bn = xn
end
Scarto = bn - an
end
2) Scelta
- Interpolazione: trovo Pm(x)
- Approssimazione
- Approssimazione ai minimi quadrati
cerco la funzione che minimizza la differenza
tra i dati osservati e i valori della funzione
passante per i punti osservati
xi | yi ------------ | ---------- x0 | y0 ... xm | gm = f(crm)m <= n
Pn(x)
f(c01)=y01 Σ ( f(xi) - g* (xi) )2 ω(xi) = min i = 0 i = 0g ∈ Pm(x)
- migliore approssimazione
max | f(xi) - g* (xi)| = min max |f(xi) -g(xi) | o <= i <= mquando xi in cui l'errore è massimo e tanto
g(xi) che lo minimizza
A =
( 1 x00 x01 x02 ... x03 )
( 1 x10 x11 x12 ... x13 )
( 1 xm0 xm1 xm2 ... xm3 )
{m+1 }
( x0 ; y0 )
b = ( y0 )
( ym )
{m+1 x m}
( y0 ; x0 )
a = ( a0 )
( am )
{m+1}
Ax = b
ATA a = ATb
Retta di regressione o ai minimi quadrati
pi(x) = a0 + a1x
( xi ; yi )
( x0 ; y0 )
( xm ; ym )
A = ( 1 x0 )
( 1 x1 )
( 1 xm )
ATA =
( 1 1 ... 1 ) ( 1 x0 ) =
( x0 x1 ... xm ) ( 1 x1 ) =
( 1 xm ) =
{(m+1) }
( m+1 [Σ i=0m xi] ) =
( Σ i=0m xi Σ i=0m (xi)2 )
ATb =
( 1 x 1 ( 1 ) ) =
( x0 x1 x2 ... xm ) ( y0 ) =
( ym )
{m+1 x 1}
( Σ i=0m yi =
( Σ i=0m xiyi )
Metodi iterativi per risolvere sistemi lineari
Metodi iterativi stazionari
(metodo Picard)
Problema: trovare \( x : F(x) = 0 \)
\(\Rightarrow\) trovare \( x_i : x = x + F(x) \)
\(g(x)\)
- \(x_{q+1} = g(x_q)\)
- errore \( E_q = x_q - x \)
- \(|E_q|_{q \rightarrow \infty} \rightarrow 0 \ \Leftrightarrow \ |g'(x)| < 1\)
- \(\lim_{q \to \infty} \frac{E_{q+1}}{E_q} = |g'(x)| < 1\) \(p=1\) convergenza lineare
Estensione ai sistemi lineari
definiamo \(F(x)\) vettoriale \(F : \mathbb{R}^m \rightarrow \mathbb{R}^m\)
\(F(x) = b - Ax = 0\) \(\Leftrightarrow\) \(Ax = b\)
cerco \( x \in \mathbb{R}^m \ t.c. \ F(x) = b - Ax = 0\)
uso l'idea del punto fisso
\(x = x + F(x) = g(x)\)
\(b-Ax\)
\(g(x)\)
Picard:
- \(x_{q+1} = x_q + F(x_q) = x_q+b-Ax_q\)
- \(=(I-A)x_q+b\)
ERRORI DI CONDIZIONAMENTO DI METODI ITERATIVI
Ea è ignoto
Ea = x - xa
x non lo conosco
r2 = b - Axa, meno calcolato
= A x - Axa
- A (x - xa)
= A Ea
|| r2 ||2 ?
|| Ea ||2
|| r0 ||2 < tole ⇒
|| E0 ||2 < tole
Se x0 = ɛ0 , r0 = b , ɛ0 = x
|| b - Axa ||2
|| b ||2 ?
|| x - xa ||2
|| x - ɛ ||2 < tole
Facciamo una minima delle norme
|| r0 ||2 = || A Eɛ ||2 < || A ||2 || Ea ||2
|| Eɛ ||2 = || A -1r2 || < || A -1 ||2 || r2 || 2
|| r2 || < || A || 2 || ɛ0 ||2 (⇔) ɛɛ ||2 > || r0 ||2 / || A || 2
Allora
|| Eɛ ||2 <
|| ɛɛ ||2-1 = || A || 2 || rɛ ||2
|| r0 ||2 / || A || 2
κ(A) = (|| A ||2 || A -1 ||2)
Se κ(A) ≈ 1 => non c'è tanto differenza tra || E ||2 e || b ||2
Bene Condizionato
Se κ(A) >>> 1 => La diff tra ||E ||ɛ e || r ||2 è grande
Mal Condizionato
κ(A) ≥ 1 matrice
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
