Elementi di analisi numerica

Elementi di analisi numerica

Di:

Matteo Daddi

Liceo scientifico "Sacro Cuore", Livorno

Esame di maturità a.s. 2006-07

Introduzione

La mia tesina tratterà brevemente l'analisi numerica. In particolare si descriveranno alcuni metodi di determinazione delle radici di un'equazione e alcuni metodi per il calcolo numerico dell'integrale definito.

Le materie interessate sono: Matematica, Informatica, Fisica (accenni), Filosofia (accenni).

Il lavoro si compone di questo testo, una presentazione multimediale e tre software a scopo dimostrativo da me realizzati per integrare le argomentazioni.

Nota

I file contenenti il materiale della tesina sono: "testo_tesina.pdf" (questo documento), "presentazioneMultimediale.odp" (la presentazione completa e "ufficiale", per vederla è necessario avere OpenOffice.org), "presentazioneStatica.pdf" (versione senza animazioni del file precedente, non richiede OpenOffice.org), "(sconsigliato)_presentazioneALTERNATIVA.ppt" (una versione PowerPoint della presentazione, sconsigliata), "bin/Bisezione.jar", "bin/Secanti.jar", "bin/Integrale.jar" (i tre software da me sviluppati). Cos'è?

Definizione

L'Analisi numerica è la branca della matematica che si occupa di trovare gli algoritmi per risolvere numericamente problemi matematici dei quali generalmente, ma non necessariamente, non è possibile trovare la soluzione esatta.

La ricerca punta all'algoritmo che risolva il problema nel minor tempo e con la massima accuratezza possibile (oppure con un'accuratezza arbitraria).

Scopo (stabilità, accuratezza, efficienza)

"Lo scopo dell'analisi numerica è fornire metodi convenienti per ottenere soluzioni utili di problemi matematici e per estrarre informazioni utili dalle soluzioni disponibili che non sono espresse in forma utilizzabile".

Quando si usa

L'analisi numerica si usa, come abbiamo già detto, quando non possiamo trovare la soluzione esatta di un problema (per esempio, nella ricerca delle radici di molte equazioni oppure in alcuni casi in cui dobbiamo calcolare un integrale definito) ma si usa anche quando ci possiamo accontentare di una soluzione approssimata ad esempio quando i dati con cui lavoriamo sono valori trovati sperimentalmente e quindi già soggetti ad un certo errore oppure ancora quando per la soluzione di un problema ci affidiamo ad un calcolatore che, per quanto potente sia, lavora con una certa precisione dalla quale non può prescindere.

Questa presentazione può stupire chi si è fatto della matematica una rappresentazione stereotipata.

"Non ci sono errori nella matematica! Il fatto è che troppo spesso si confonde tra errore e approssimazione. Approssimato e approssimativo non sono sinonimi".

Chi la usa

Velocemente: Scienziati, Ingegneri, Fisici, Programmatori, Studenti, ecc...

L'analisi numerica è usata quotidianamente per risolvere molti problemi scientifici e tecnici (progettazione di strutture, di veicoli, ecc.), nello studio delle molecole e anche nelle previsioni meteorologiche. Insomma è una grande protagonista dell'epoca dei calcolatori, i suoi algoritmi fanno da base per i software di CAAD e CAE, quasi tutti i super-computer sono costantemente impegnati a eseguire operazioni di analisi numerica.

L'elaborazione al computer, con la necessità di dover risolvere in modo finito problemi di natura continua, ha creato nuovi terreni di gioco per questa branca della matematica.

Fra questi possiamo individuarne alcuni di particolare rilevanza:

• Studio del condizionamento numerico di un problema
• Studio della stabilità numerica di un algoritmo
• Studio della complessità computazionale di un problema
• Questioni legate alla discretizzazione di un problema continuo

Studio dell'errore

Lo studio degli errori costituisce una parte importante dell'analisi numerica. Ci sono più modi in cui si possono introdurre errori nella soluzione di un problema, per esempio:

• Errore di arrotondamento: errori dovuti alla necessità di lavorare con numeri macchina a virgola mobile (è impossibile rappresentare esattamente qualsiasi numero reale su un computer)
• Errore di troncamento: si ha quando si arresta un metodo iterativo prima che la soluzione approssimata abbia raggiunto la soluzione esatta
• Errore di discretizzazione: quando si approssima un problema continuo con un problema discreto

Un errore, una volta che è stato generato, generalmente si propagherà attraverso i calcoli successivi rendendo il risultato sempre meno vicino all'esatto. Questo conduce al concetto di stabilità numerica: un algoritmo si dice numericamente stabile se un errore, una volta che è stato generato, non cresce troppo durante il calcolo. Il compito dell'analisi numerica è dunque quello di creare algoritmi stabili.

Per alcuni problemi però, non esistono algoritmi stabili. Un altro compito dell'analisi numerica è quindi quello di trovare, in questi casi, problemi risolvibili con algoritmi stabili le cui soluzioni approssimino quelle dei problemi originali.

In generale chi usa l'analisi numerica non persegue l'esattezza ma cerca di trovare un metodo che gli fornisca un'approssimazione il cui errore sia minore di una fissata tolleranza.

La ricerca degli zeri

Teoria ed empirismo

L'analisi numerica è una scienza sia teorica che sperimentale, un metodo euristico ma efficiente può essere preferito a un metodo con una solida base teorica ma inefficiente. Gli assiomi e i teoremi restano comunque le solide fondamenta su cui costruire, del resto:

"Non c'è nulla di più pratico di una buona teoria".

In particolare i teoremi fondamentali per procedere alla ricerca degli zeri sono:

T. degli zeri

Ip:

f(x) continua in [a, b]

f(a) · f(b) < 0

Th:

⇒ esiste almeno un punto c ∈ [a, b] ∣ f(c) = 0

Questo teorema ci dice quando poter essere certi della presenza di almeno "uno zero" in un intervallo, la tesi non è invertibile (le ip. sono condizioni sufficienti non necessarie).

Sfruttando l'analisi numerica, possiamo però verificare l'esistenza di una soluzione anche nel caso in cui le ip. non siano soddisfatte, basterà infatti dimezzare di volta in volta l'intervallo e rivalutare il T. usando i vecchi estremi e il punto medio, si proseguirà così fino a trovare almeno un intervallo con (almeno) una soluzione o fino a che la distanza tra i due estremi di valutazione del T. sarà al più "ε" (la nostra approssimazione). In questo ultimo caso, se il T. non sarà verificato, considereremo che nell'intervallo non esiste una soluzione.

Ora che sappiamo se nell'intervallo c'è (o non c'è) una soluzione, ci torna utile sapere se questa è unica (nell'intervallo), così sarà più facile pensare un algoritmo per la risoluzione.

Primo T. di unicità delle radici

Ip:

Il T. degli Zeri è soddisfatto e verificato

f(x) è derivabile in (a, b) e f'(x) ≠ 0 ∀ x ∈ (a, b)

Th:

L'equazione f(x) = 0 ammette una sola soluzione in (a, b)

Secondo T. di unicità delle radici

Ip:

Il T. degli Zeri è soddisfatto e verificato

f(x) è derivabile 2 volte in (a, b) e f''(x) ≠ 0 ∀ x ∈ (a, b)

Th:

L'equazione f(x) = 0 ammette una sola soluzione in (a, b)

I due T. in sostanza ci dicono che se il T. Degli Zeri è verificato e f(x) è sempre strettamente crescente/decrescente, oppure è sempre concava/convessa in (a,b) allora la soluzione è unica.

I metodi per la determinazione delle radici

Dopo aver verificato l'esistenza di almeno uno "Zero" e aver eventualmente trovato un intervallo dove lo Zero è unico, possiamo avviarci a vedere alcuni metodi che ci consentono di calcolare la soluzione approssimata.

La bisezione

Dividere in 2

Il metodo della bisezione (detto anche algoritmo dicotomico) è il metodo numerico più semplice per trovare una soluzione approssimata di un'equazione.

L'efficienza del metodo di bisezione è però scarsa (la convergenza ha andamento lineare), per trovare una soluzione con una discreta approssimazione sono infatti necessari molti passaggi. Le sue migliori caratteristiche sono quella di essere stabile in ogni situazione (garantisce sempre la buona riuscita dell'operazione) e quella di consentire una semplice valutazione dell'errore di approssimazione.

In pratica

1) Si guarda se gli estremi possono già essere considerati una soluzione approssimata

|b − a| < ε

Se è così allora ci fermiamo, a e b sono due soluzioni valide per l'ε scelto

⇒ r = b oppure r = a

2) Se non è così ci calcoliamo il punto medio

m = (a + b) / 2

Se f(m) = 0 allora m è la soluzione ESATTA quindi ci fermiamo

f(m) = 0 ⇒ r = m

3) Se f(m) ≠ 0 valutiamo il T. degli Zeri tra [a,m] e [m,b], troveremo così il sotto-intervallo che contiene la soluzione. Da qui torniamo al punto 1 usando come nuovi estremi a, b gli estremi dell'ultimo intervallo trovato ([a,m] o [m,b])

f(m) ≠ 0

f(a) · f(m) < 0 ⇒ b = m

f(m) · f(b) < 0 ⇒ a = m

I valori delle "a successive" (a_i) sono valori approssimati per difetto della radice, i valori delle "b successive" (b_i) sono invece valori della radice approssimati per eccesso. Le "a" formano una successione non decrescente limitata e le "b" formano una successione non crescente limitata. Le due successioni ammettono lo stesso limite che è la radice dell'equazione esaminata. Fissata l'approssimazione "ε" richiesta, si può ricavare il numero "n" di iterazioni necessarie per ottenere la radice:

(b − a) / 2ⁿ < ε ⇒ n > log₂((b − a) / ε)

Programmi esemplificativi

Requisiti di sistema

I tre software facenti parte di questa tesina sono scritti in Java, perciò sono multipiattaforma e per poterli eseguire è necessario che sulla macchina sia installato il JRE.

I programmi sono contenuti nella cartella "tesina/bin", se lanciandone uno (basta un doppio-clic) questo si avvia allora il JRE è installato, se non fosse installato è possibile scaricarlo gratuitamente da: http://java.com/it/