Calcolo numerico - teoria del corso

Calcolo Numerico

Algoritmi

Un algoritmo è una successione finita di istruzioni che ci permette di passare da una situazione iniziale (Dati) ad una situazione finale (Risultati).

Dati Algoritmo → Risultati

• Successione finita di istruzioni
• Modo non ambiguo (preciso e ordinato)
• Fa passare dai dati ai risultati
• Tempo finito

Un buon algoritmo deve avere 2 requisiti:

• Generalità → deve risolvere una classe di problemi
• Ottimalità → deve essere un algoritmo "ottimale", cioè il migliore rispetto al tempo, rispetto al numero di operazioni, ecc.

Es:

Somma di n numeri \(a_1, a_2, ..., a_n\)

1. Leggi: n, \(a_1, a_2, ..., a_n\)
2. Pon: S = 0
3. Per: i = 1, 2, ... , n
   1. Pon: S = S + ai
4. Scrivi: S
5. Stop

Prodotto di n numeri \(a_1, a_2, ..., a_n\)

1. Leggi: n, \(a_1, a_2, ..., a_n\)
2. Pon: P = 1
3. Per: i = 1, 2, ... , n
   1. Pon: P = P * ai
4. Scrivi: P
5. Stop

Adesso prendiamo come problema il seguente:

DETERMINARE √N, N>0 mediante un procedimento iterativo

Procedimento iterativo: Procedimento che si basa su una sequenza di istruzioni ripetute continuamente con lo scopo di trovare una soluzione... avvicinandosi il più possibile ad essa. Non è certo che sia un numero finito di istruzioni.

Procedimento iterativo → Non è un algoritmo (dato che può non finire)

Determinare √N, N>0

1. Individuare m, h >0, tale che:m² < N < h²
2. Calcolare c = (m + h) / 2
3. Se c² = N, c = √N → STOP
4. Se c² < N → sostituire c con m e tornare al punto 2.
5. Se c² > N → sostituire c con h e tornare al punto 2.

Dato che per molti numeri non esiste un valore preciso di radice quadrata, dobbiamo trovare un numero di iterazioni dopo le quali fermarci. Questo "numero finito" renderebbe il nostro procedimento iterativo un algoritmo a tutti gli effetti.

A differenza del procedimento iterativo, il controllo dell'uguaglianza viene sostituito da un controllo di approssimazione dopo aver superato il numero di iterazioni da eseguire.

In questo caso è evidente che per ogni "n" abbiamo da eseguire n² moltiplicazioni e n² somme.

Costo nell'algoritmo 2 minore rispetto a quello dell'algoritmo 1.

Errore nella rappresentazione:

Errore assoluto:

e_r = |x - fl(x)|

Errore relativo:

e_R = |x - fl(x)| / |x|

Precisioni di Macchina:

Se si opera per troncamento:

|x - fl(x)| / |x| ≤ β^1-m ∀ x ≠ 0

Se si opera per arrotondamento:

|x - fl(x)| / |x| ≤ 1/2 β^1-m ∀ x ≠ 0

LA RISOLUZIONE DEL SISTEMA PUÒ ESSERE FATTA CON IL PIVOTING PARZIALE O TOTALE.

LA FATTORIZZAZIONE NON PUÒ ESSERE FATTA NÉ CON IL PIVOTING PARZIALE NÉ CON IL PIVOTING TOTALE

Esempio Pivoting

1 4 3

2 3 6

5 8 7

Pivoting PARZIALE

5 8 7

2 3 6

1 4 3

Il pivoting parziale mi chiede di cercare il numero più grande nella stessa colonna e quindi di scambiare le righe (1 e 3) in questo caso.

Al passo k=1 e alla riga 1, colonna 1

l₂₁ = max |a₃₁/a_{i i}| = 5

Pivoting TOTALE

8 5 7

3 2 6

4 1 3

Il pivoting totale mi chiede di cercare il numero più grande in tutta la matrice e, quindi di scambiare prima righe e poi colonna per portarlo in cima.

Al passo 1, scambio riga 1 e riga 3

Al passo k, scambio colonne 1 e colonna 2

Ad ex

l₀(x) = (x-x₁)(x-x₂) / (x₀-x₁)(x₀-x₂) = 1/6 (x-1)(x-2)

l₁(x) = (x-x₀)(x-x₂) / (x₁-x₀)(x₁-x₂) = -1/2 (x+1)(x-2)

l₂(x) = (x-x₀)(x-x₁) / (x₂-x₀)(x₂-x₁) = 1/3 (x+1)(x-1)

Quindi

l(x) = l₀(x)f₀ + l₁(x)f₁ + l₂(x)f₂ = 1/6 (x-1)(x-2) - 1/2 (x+1)(x-2) + 1/3 (x+1)(x-1)

= 2x² / 6 + 2x / 3 + 2 / 2 + x² / 3 - 1/3 = 1/6 x² - 1/2 x + 4/3

Formulazione di Newton

Formulazione basata su una nuova base. Es. Assegnati (x₀, f₀); (x₁, f₁); (x₂, f₁)

Base_P (1, x, x²)

Base_L (l₀(x), l₁(x), l₂(x)) → Base Lagrange

Base_N (1, (x-x₀), (x-x₀)(x-x₂)) → Base Newton

P₂ = A₀ + A₁(x-x₀) + A₂(x-x₀)(x-x₄)

Devo calcolarmi X₀, A₁, A₂

EQUAZIONI NON LINEARI

Le equazioni non lineari sono equazioni per le quali non c'è una formula risolutiva. Ad esempio: 4xsin(x) + x² = 0, √x - log x = 0.

Dobbiamo determinare le soluzioni tali che f(x) = 0. Si usano tecniche che approssimano le soluzioni. Ad esempio, Metodo di Bisezione.

METODO DI BISEZIONE

Supponiamo f(x) continua in [a,b].

f(a) · f(b) < 0. Con queste 2 supposizioni esiste almeno 1 α, a < α < b, t.c. f(α) = 0.

Questo metodo consiste nel suddividere l'intervallo [a,b] a metà scegliendo come nuovo intervallo quello dove è presente α.

Poniamo α = d₁ e d₁ = c₁ dato che a₁ < α < c₁.

Dato che può procedere all'infinito, ci arrestiamo quando:

|f(c₁)| ≤ ε e/o |b₂ - d₂| ≤ ε

Per capire quante volte dobbiamo fare questo passaggio prima di fermarci, utilizziamo questa formula:

h ≥ log₂((b₀ - a₀)/ε) - 1

In poche parole con il metodo di bisezione calcoliamo ogni volta la radice che annulla il vertice:

A(b₁, sgn(f(b₁)))