Appunti di Calcolo numerico

ANALISI E CALCOLO NUMERICO

PAOLO FARAGALLA

ANALISI E CALCOLO NUMERICO

FRANCESCA PITOLLAfrancesca.pitolli@[...].itwww[...].francesca.pitollie-learning […]

COORDINATORE MICHELA BRUNELLI […]

GIOVEDì POMERIGGIO 15:00 - 17:00 […]

LIBRI:1. [...] Calcolo Numerico, Ed. Kappa 20062. [...] Escolio di Calcolo Numerico Ed. Kappa 2007

LIBRI PER APPROFONDIMENTO- [...] Colli [...], Esercizio Calcolo Lettura Prezziari Kappa 2017- Conte - De Boor Elementare Calculoins 2018

[...] Vittorio Brusoni

CORSO PER MATLAB: [...] MATLAB ON RAMP

CONCETTI DA SAPERE:

• ANALISI 1
• ANALISI 2
• GEOMETRIA - [matrici, determinanti, autovalori, ecc.]
• SVILUPPO IN SERIE DI TAYLOR

ESAME [90 max 30L]

SCRITTO (orale facoltativo)

Non verbalizza la bocciatura

ESAME 6/06/2019 - 25 NUOVA proposimenscion [MP1] [...] 20/07/2018 - 25 SCRITTE calcolare - ridefinire tester [...].

esercitazione: […] dalle 14:00 [...]: […] portare il computer […].

CRITERIO DI ARRESTO

Le iterazioni facciamo finchè il risultato sarà accurato.

|e_k| = |x_k - x| ≤ ε

ε = 0.5 · 10^-6

Il numero delle iterazioni approssimative

Il errore è la differenza tra due iterazioni successive.

|b - a_xk| ≤ ε

k ≈ grande

|e_k| ≈ 1/2^k · |e₁|

Per ogni iterazione, l'errore si dimezza (circa)

Se k è grande, più diminuisce l'errore.

ORDINE DI CONVERGENZA: p ≥ 1

Serve per sapere quanto velocemente diminuisce l'errore.

lim _k→∞ |e_k+1| / |e_k|^p = C < ∞

|e_k+1| ≈ C |e_k|¹

Nel metodo di bisezione

L'ordine di convergenza è: 1

|e_k+1| ≈ 1/2 |e_k|

lim _k→∞ |e_k+1| / |e_k|¹ = 1/2

CRITERIO DI ARRESTO

|e_k| = 3^-k × |x_k - x_k-1| ≤ ε

ALGORITMO

a₀ = a

b₀ = b

for k = 0, 1, 2, ..., 10

X_n = (a_k, b_k) / 2

Se f(a_x) · f(X_n) < 0 → [a_x, X_n]

Se f(X_n) · f(b) < 0 → [X_n, b_x]

STOP se la radice è nel punto.

ISTRUZIONI PER GRAFICI SU MATLAB

plot (x,y)

x = linspace (0,10,4)

y = exp (x).²

z = cos (x)

z = exp (x).^-x

SISTEMI DI EQUAZIONI NON LINEARI

F(X) = 0 con le lettere maiuscole indico i vettori

F(X) = 0 ⇔ Fƒ(x₁, x₂, ⋯, x_n) = 0

X ∈ ℝⁿ

O E X = 0 sono vettori

⟹ X = (x₁, x₂, ⋯, x_n)

⟹ F(X) = (f₁(x), f₂(x), ⋯, f_n(x))

la soluzione è

L'uso generalizzato il metodo delle approssimazioni successive

F(X) = 0 ⟹ X = Φ(X)

Φ(X) : ℝⁿ → ℝⁿ

Φ(x) = {φ₁(x), φ₂(x), ⋯, φ_n(x)}

X₀ ∈ ℝⁿ

X_k+1 = Φ(X_k) k = 0,1

• x₁ = φ₁(x₁, x₂, x_n)
• x₂ = φ₂(x₁, x₂, x_n)
• x_n = φ_n(x₁, x₂, x_n)

METODO DI NEWTON-RAPHSON

1 dimensione ⇔ f(x) = f′(x)¹(x_k) (x − x_k) − 0

n dimensione ⇔ F(X) = F(X_k) + J(X) (X − X_k)

{

X_k ∈ ℝⁿ

{x₀, x_k, ⋯}

J(X)

MATICE JACOBIANA

CONVERGENZA

(procedimento iterativo)

• C.N. lim x^(k) = x̄ → CONDIZIONE NECESSARIA
• C.S. ||c|| < 1 → CONDIZIONE SUFFICIENTE
• C.N.S ρ(c) < 1 con ρ(c) = max |λ_i| → autovalori in modulo

CONDIZIONE NECESSARIA E SUFFICIENTE DELLA CONVERGENZA

CRITERIO DI ARRESTO

(procedimento iterativo)

• A posteriori: ||E^(k+1)|| = ||x^(k+1) - x^(k)(H)|| ≤ ε
• A priori: ||E^(k)|| ≤ ((x̄ - x⁽⁰⁾))
• ||E^(k)|| ≤ ||x^(k+1) - x^(k)(H)|| + ||x^(k)|| ^{DIAGONALIZZAZIONE TRIANGOLARE}

E^(k+1) ≤ ||c|| E^(k) ≤ ||c|| ||E⁽⁰⁾|| + (x^(H) - x⁽⁰⁾)

E^(k+1) ≤ ||c|| E⁽⁰⁾ ≤ (cont. del modulo)

termine residuo

K ≥ log_{( <1 )} ε → -1/||c|| < ||E.sup.(k)||

Esercizio

x_β = β

(procedimento iterativo) (ultima linea)

(x^(k+1)) = β(y^(k))^||c||

procedimento iterativo

iterazioni unite

(max > (f(x) <) = ())

2) ||x^(k+1) = f(x^(k))

= Cx^(k) + Q

PROCEDIMENTO ITERATIVO

MATRICE DI ITERAZIONE

le vediamo la convergenza relativa al valore della norma di derivazione

NORMA 1

||C₁|| = max

Esercizio (SISTEMA LINEARE)

{x + y - 2z = 1

2x - y + 2z = 0

2x + y + z = 0

Il sistema ammette soluzione se il det A ≠ 0

• A = [1 1 -2]
• [2 -1 2]
• [2 1 1]

⟹ det A = 1(-1⋅1 -1⋅2) - (-2⋅1 -2⋅2) ≠ 0

1 > λ 1 + |λ 2| no

1 > 2 + 2λ no

gli elementi sulla diagonale principale sono diversi da 0, quindi posso procedere con Jacobi

C_j = D^-1(L + U) = [0 1 -2]

[2 0 2]

[2 1 0]

⟹ [0 1 -2]

[1 0 1]

[2 2 0]

Dunque verifico che ρ(C_j) < 1:

det (C_j - λ I) = det [λ -1 2]

[-2 λ 1]

[ 1 λ -2]

⟹ [λ(λ(.)+1) (λ(.)+)]

⟹ -λ [(λ +(-) 0]}

⟹ -λ [(λ+λ)] [

p(C_j) = 0 ⟹ dunque il metodo converge

• CON GAUSS SEIDEL

C= -(D+L)^-1U = [1 0 0]

[2 4 0]

[2 1 4]

⟹ [0 -1 2]

[0 0 0]

[0 0 0]

⟹ [0 -1 -2]

[1 0 0]

[0 2 -2]

⟹ [2 0 0]

[0 3 4]

[0 1 0]

Dunque verifico che ρ(C_GS) < 1

det (C_GS - λ I) = 0 det [λ -1 2]

[-2 λ -6]

[0 0 -2λ]

⟹ [λ -1 2]

⟹ -2(2-λ)(2-λ) = 0 ⟹ λ_1,3=2

ρ(C_GS) = 2 > 1

DUNQUE IN QUESTO CASO IL METODO DI GAUSS-SEIDEL NON CONVERGE

TEORIA DELL'APPROSSIMAZIONE DI DATI

• PROBLEMA:

  Data una tabella di dati, {x_i, y_i}; i = 0 ..., n, si vuole trovare una funzione analitica φ_n di approssimazione ai dati.

  In quale classe di funzioni si vuole cercare (es. polinomi di 1°, 2° ... approssimazione)?

  Il metodo di approssimazione.

• FUNZIONI APPROSSIMANTI

  • Polinomi algebrici di grado M a coefficienti reali: M + 1 parametri
  • Polinomi trigonometrici di ordine M a coefficienti reali: 2M + 1 parametri
  • Funzioni razionali: M + N + 2 parametri
  • Funzioni esponenziali: 2M parametri
  • Funzioni splines: polinomi a tratti di grado M e regolarità C^h+2

• METODI DI APPROSSIMAZIONE

  • INTERPOLAZIONE:

    Si regola la funzione approssimante φ_n(x) in modo che soddisfi la condizione di interpolazione.

  • APPROSSIMAZIONE AI MINIMI QUADRATI:

    Si regola la funzione approssimante φ_n in modo da minimizzare la quantità:

    1. ∑ [φ_n(x_i, Γ) - y_i]² -> SCARTO QUADRATICO

    Giunta introducendo i pesi si elegge per:

    1. ∑ w_i [φ_n(x_i, Γ) - y_i]² -> SCARTO QUADRATICO PESATO

    Si usa lo scarto quadratico pesato quando i dati y_i sono poco accurati o in numero elevato.

    Adesso andremo dunque in modo più dettagliato al metodo di approssimazione ai minimi quadrati.