Relazione parte 1 Metodi Numerici

FORMULA RISULTATO

Formula dei Trapezi 132

Formula di Cavalieri-Simpson 1/3 68

Formula di Cavalieri Simpson 3/4 68

Formula di Boole 68

Formula di Newton-Cotes con 1 punto 36

Formula di Newton-Cotes con 2 punti 46.67

Formula di Newton-Cotes con 3 punti 68

Formula di Newton-Cotes con 4 punti 68

Studenti: Giovanni Donini 896077, Francesco Diana 952362, Mattia Ferrari 919506

Metodo di Newton per risolvere equazioni non

lineari

Problema:

−

= −

Per utilizzare il metodo di Newton è necessario che

la funzione sia continua e abbia derivata prima

continua all’interno dell’intervallo considerato.

Nel caso in esame la derivata prima è pari a:

−

′ = − −1

E’ poi necessario definire un criterio per verificare se

l'algoritmo ha raggiunto una precisione nella

soluzione adeguata alla richiesta. Si parla del

concetto di tolleranza, ovvero un valore da porre a

priori che differenzia una soluzione ben

approssimata da una affetta da un errore non

accettabile. E' anche possibile porre uno stop al

procedimento ricorsivo ponendo un numero

massimo di iterazioni che permette un primo

controllo sulla convergenza.

−8

10

E’ stata scelta una tolleranza pari a in quanto questo ordine di grandezza risulta sufficiente a ricavare il

−16

10

valore esatto di x (in caso avessimo usato , che corrisponde alla precisione di macchina, il valore di x

ricavato sarebbe stato lo stesso); inoltre è stato scelto un numero di iterazioni pari a 10 poiché risultano

essere sufficienti per arrivare a convergenza.

Infine è necessario scegliere un punto iniziale da dove l’algoritmo partirà con il calcolo della soluzione.

= 0.52

E’ stato scelto come punto iniziale perché dal grafico della funzione (stampato tramite MATLAB

0

con il comando ‘’plot’’) questo valore risulta essere molto vicino alla soluzione esatta e ciò garantisce la

convergenza del metodo.

I risultati sono i seguenti:

Il metodo di Newton è molto veloce nel ricavare la

soluzione in quanto l’ordine di convergenza (di tipo

locale) risulta quadratico se viene scelto bene il

punto iniziale. Il costo computazionale di tale

metodo è alto poiché bisogna calcolare la derivata e

valutare f(x) e f’(x) per ogni iterazione.

Il numero di iterazioni che esegue l’algoritmo

dipende dalla posizione del punto iniziale rispetto

allo zero cercato: più il punto iniziale è lontano e

maggiore sarà il numero di iterazioni. = 1

Ad esempio se si sceglie il numero di iterazioni sale a 4:

0

Il metodo di Newton ha una convergenza globale nel caso in cui la f(x) sia continua, avente derivata seconda

continua nell’intervallo considerato e siano soddisfatte le seguenti ipotesi:

[0.50 , 0.60] [0 , 2]

Intervallo Intervallo

IPOTESI = 0.52 = 1

Punto iniziale Punto iniziale

0 0

<0 VERIFICATA VERIFICATA

′

≠ 0 ∀ ∈ [, ] VERIFICATA VERIFICATA

′′ ′′

> 0 < 0 ∀ ∈ [, ] VERIFICATA VERIFICATA

()

= − <− = − <− VERIFICATA VERIFICATA

′

′()

La funzione soddisfa tutte le condizioni, quindi la convergenza è di tipo globale .

Conclusioni

Il metodo di Newton risulta uno strumento molto potente per risolvere le equazioni non lineari ma per

essere utilizzato ha bisogno di molti dati in fase di input e ha un costo computazione alto per ogni iterazione

effettuata.

In particolare, se non è possibile calcolare in maniera analitica la derivata prima della funzione, tale metodo

non può essere utilizzato.

Come grande altra limitazione possiamo affermare che il punto iniziale scelto arbitrariamente gioca un ruolo

fondamentale nella velocità di calcolo della soluzione: in caso di scelta di un valore ottimale la convergenza è

di ordine quadratico, mentre degrada in caso contrario.

Bisogna fare anche attenzione al numero di radici della funzione, poiché se la radice non è singola la

convergenza degrada.

Il metodo di Newton lavora con convergenza locale salvo poi espandere la convergenza a globale tramite la

verifica delle ipotesi esposte precedentemente.

Studenti: Giovanni Donini 896077, Francesco Diana 952362, Mattia Ferrari 919506

Quando scegliere metodi diretti o iterativi

Problema:

A x = b

La matrice A oggetto di studio è una matrice quadrata 50x50, tridiagonale con elementi tutti (5) sulla

diagonale principale ed elementi tutti (-2) sulla prima sottodiagonale e prima sovradiagonale.

La struttura della matrice è quella visibile nell’immagine a destra.

Si è imposta come soluzione esatta il vettore x composto da soli (1).

Attraverso il sistema A x = b si è determinato il vettore dei termini noti b.

La matrice A risulta avere le seguenti caratteristiche:

• Non singolare

• Simmetrica

• Definita positiva

• Predominanza diagonale (righe e colonne)