Riassunto Analisi numerica

Localizzazione dello zero di una funzione - Metodo di bisezione

Procedimento

Data una funzione:

• Trovare un intervallo di localizzazione con le seguenti caratteristiche:
  • f(a)xf(b)<0
  • f(x) continua e definita in [a,b]
  • f(x) monotona in [a,b]
• Trovare il punto c medio in [a,b]
• Verificare che una delle affermazioni sia vera:
  • f(c)f(a)<0
  • f(c)f(b)<0
• Scegliere come nuovo intervallo di localizzazione l'intervallo che verifica una delle equazioni sopra e reiterare fino a e <= TOL

Calcolo dell'errore

Sappiamo che la serie di c che andremo a scegliere porterà il punto c ad avvicinarsi sempre di più al risultato reale, quindi sappiamo sicuramente che:

− | − * | < 1/2( − ) = = +1 2 -t

Quindi elaborando la formula sappiamo che data una TOL espressa in 10 dove t è il numero di cifre decimali esatte dopo la virgola compresa l'unità. Vediamo che è possibile calcolare a priori il numero di iterazioni da svolgere come − ≥ −12

È possibile capire anche la velocità del metodo di bisezione che è data dalla funzione relativa alla decrescita dell'errore. Ovvero partendo da −− estrapolo , ovvero ogni 4 iterazioni ottengo un numero = = 10 = + 2+1 +1 102 esatto dopo la virgola.

Metodo di Newton

Procedimento

Per questo metodo è importante prendere un intervallo di localizzazione con le seguenti caratteristiche:

• f(a)xf(b)<0
• f(x) continua e definita in [a,b]
• f(x) monotona in [a,b]
• f’ è definita e continua in [a,b] e f’(x) ≠ 0 x∈[a,b] ∀

Vediamo quindi che data una prima approssimazione x di x l’approssimazione successiva sarà data dal punto di intersezione della tangente con l’asse x. Quindi vediamo che è la soluzione dell’approssimante lineare di forma

1( ) si ottiene così che 0() = ( ) + '( )( − ) = 0 = − '( )0 0 0 1 0 0

Generalizzando ( ) motivo per cui f’(x) ≠ 0 = − '( )+1

Notiamo però che questo metodo non è sempre valido; infatti le iterazioni potrebbero portare al di fuori dell’intervallo di localizzazione oppure portare a una interazione circolare nel caso di funzioni simmetriche in [a,b].

Teorema di convergenza generale

Teorema 6 (Maset)

Se x ∈ [a,b] per ogni n e la successione {x_n} converge, allora converge allo zero x*, ∈n_n

Quindi vediamo che l’iterazione iniziale è fondamentale per utilizzare il metodo di Newton. Si introduce quindi una funzione di iterazione φ: [a,b] →R data da 2() 1 ''(ξ)2 e se f∈C [a,b] allora dove ξ è un punto φ() = − φ() − *= ( − * )'() 2 '() tra x e x*

Teorema di convergenza locale

Teorema 8 (Maset)

2Sia f∈ C e sia definito un intervallo I :=[x*-ε;x*+ε] con ε>0 intorno circolare di x tale che ξI [a,b] e d - ε<1 e dove ⊆ξ ε1 |''()| : = ·2 |'()|ε

Se x appartiene a questo intervallo allora avremo le seguenti caratteristiche:

• x I per ogni n⊆n ε
• Il limite della successione tende a x*
• La differenza tra x e x* è minore del raggio dell’intorno d_n+1 e

Questo porta a dire che il metodo di Newton è localmente convergente, ovvero che funziona bene se e solo se all’interno dell’intervallo di localizzazione, ogni successione di x costruita con il metodo di Newton converge su x*

Si intuisce quindi che la velocità del metodo di Newton è dettata dalla velocità della convergenza della serie x a x_n

Partendo quindi da un intorno che rispetta le caratteristiche del Teorema di convergenza locale, possiamo calcolare la velocità del metodo infatti abbiamo che 2-t_n 2|x -x*|= 10, di conseguenza dato che |x -x*|≤d |x -x*| allora possiamo sostituire con n n ε n-t_n -t_n10 ≤ d 10ɛ

Quindi la velocità è dettata da = 2 + ɛ+1 10

Quindi ad ogni iterazione il metodo di Newton fornisce almeno il doppio delle cifre decimali esatte dell’iterazione precedente.

Convergenza generale

Esistono casi in cui la funzione permette di applicare la convergenza anche in generale, ovvero non in locale. Questo risulta molto comodo per velocizzare il processo andando a evitare la convergenza locale. Infatti basterà in questo caso la sola conoscenza dell’intervallo di localizzazione e del verso della convergenza.

Andiamo quindi a introdurre una nuova caratteristica dell'intervallo di localizzazione, ovvero:

• f(a)xf(b)<0
• f(x) continua e definita in [a,b]
• f(x) monotona in [a,b]
• f’ è definita e continua in [a,b] e f’(x) ≠ 0 x∈[a,b]∀
• f’’ è definita e continua in [a,b] e f’’≠ 0 x∈(a,b)∀

Questo implica che le funzioni strettamente convesse o strettamente concave possono venir risolte senza tirare in ballo il teorema di convergenza locale.

Teorema di convergenza non locale

Teorema 9 (Maset)

2Sia f C ([a,b]) tale che le disposizioni da 1 a 5 sussistano, Se x ∈ [a,b] è tale che sign(x -x*)=sign(f’f’’) allora la successione {x_n} del metodo di Newton si ha che:

• La successione è strettamente monotona e si sposta verso a x* rimanendo sempre dallo “stesso lato”
• lim = 0

Vediamo subito che la conseguenza 1 implica che la successione è sempre all’interno dell’intervallo di localizzazione [a,b]

Importante osservazione è che la condizione sign(x -x*)=sign(f’f’’) può essere girata per indicare il lato (destra o sinistra) in cui prendere la prima approssimazione.

Ovvero se sign(f’f’’) = 1 → prendo x a destra di x* ovvero b0, sign(f’f’’) = -1 → prendo x a sinistra di x* ovvero a0

Andando quindi a riassumere in una tabellina:

La velocità anche in questo caso come per l’intervallo locale si definisce come = 2 + ɛ+1 10

Notiamo molto importante che se esiste un punto di flesso all’interno dell’intervallo di localizzazione il criterio appena studiato non servirà a nulla, ma sarà necessario applicare Newton ad un intervallo di localizzazione locale.

Il criterio di arresto del metodo di Newton si basa anche questa volta sull’analisi della velocità del metodo, ovvero vogliamo fermare l’approssimazione nel momento in cui |x -x*| ≤ TOL_n

Teorema 11 (Maset)

|( )||x -x*| ≤ dove ' = |'()|n '

Interpolazione ed estrapolazione

Per interpolazione si intende la possibilità di ricostruire una funzione all’interno di un intervallo data una serie di punti all’interno dell’intervallo. Ovvero nel nostro caso ci permetterà di approssimare una funzione complessa in un intervallo come un polinomio.

Per estrapolazione si intende ricostruire la funzione all’esterno di un intervallo conoscendo dei punti all’interno dell'intervallo.

Problema di interpolazione di Lagrange

Dato n+1 punti (x_i,y_i) nel piano R tali che x_i ≠ x_j con i≠j, ovvero non allineati verticalmente, trovare un polinomio di grado ≤n passante per ogni punto.

La condizione di interpolazione di Lagrange e la possibilità di scrivere come un sistema lineare di n+1 equazioni

4ovvero una matrice di incognite moltiplicata per una matrice colonna di n+1 coefficienti incogniti

Il sistema così generato è detto sistema di Vandermonde e conoscendo tutti i valori di x e y dettati dai punti è possibile andare a ricostruire i coefficienti. La matrice di Vandermonde però non è singolare, ovvero ha idealmente infinite soluzioni.

Forma di Lagrange

Il polinomio di Lagrange si può esprimere in forma normale come dove x_i x_j sono due numeri noti dati dai punti presi in considerazione.

Base dei coefficienti di Lagrange

Vediamo che ogni L_i(x) è un coefficiente di Lagrange, ovvero un modo per calcolare i coefficienti del polinomio

Vediamo quindi come utilizzare i coefficienti di Lagrange per ricostruire il polinomio

Esempio

Retta passante per 2 punti (-1,3) (2,-5)

1 2 − −2 1

l₀(x)= 1 = − ( − 2) 0 − −1−2 30

1 − −(−1) 1

l₀(x)= 0 = ( + 1)0 − 2−(−1) 31

0

Quindi il polinomio è dato da () = ( ()) + ( ())0 0 1 0

Vediamo quindi che l’insieme dei polinomi di grado ≤ n è una matrice di dimensione n+1 (☐)