Calcolo Numerico

C C C C

particolare, − ≤ −

[ ] [ ] [ ] ( )

: , → , ∈ , : =

La condizione del teorema è difficilmente verificabile, perché dovrei conoscere , ma è importante

perché stabilisce che l'algoritmo può convergere.

(zš1) (z)

′ ′

( )C

C C C:

In particolare, − ≤ − il rapporto tra gli errori è minore o uguale a

Siamo quindi in una situazione di un metodo almeno di ordine 1! Ricordiamo infatti che un metodo

ž

(zš1) (z) ( )

C C C

numerico si dice di ordine p se ≤ C , ≤ 1, = 1 .

Può il metodo delle iterazioni di punto fisso essere di ordine superiore a 1? (0) ž

(ï)C

C/

(<) (ž) (zš1) (z)

( ) C C C C

Teo. se = 0, = 0,1, … , − 1 e ≠ 0, allora ≤ e quindi il

(žš1)!

metodo è precisamente di ordine p.

( )

Se, oltre a soddisfare = , soddisfa anche le derivate prima, seconda e terza nulle in , ma non la

derivata quarta, allora posso dire che il metodo è di ordine 4. più derivate si annullano nel punto fisso,

28

meglio è. Accettato che il metodo scali linearmente, più la costante C è minore di 1, migliore è il metodo.

′ ( )C

C

In particolare se = 0, il metodo è almeno di ordine 2. per avere migliore precisione si può

guardare la derivata seconda.

[ ] ( ) ( ) ( ) ( )

Data : , → ℝ, gli zeri di f sono punti fissi di = − . Infatti se = 0, allora =

( )

− = . [ ] ( ) ( ) ( )

Viceversa, data : , → [, ], I punti fissi di sono zeri di = − . Infatti se = ,

( ) ( )

allora = − = − = 0.

Questo risultato è molto interessante perché metodi come Newton possono essere utilizzati per trovare

I punti fissi. Non applicherò Newton a , ma a − . Viceversa, posso usare il metodo delle iterazioni

di punto fisso per trovare le radici, applicandolo a − .

Esempio 2 2

( ) ( )

Cerco punti fissi di = sin . pPerfare questo, cerco radici fi = − sin .

Newton: 2

(z) (z)

B D

− sin

(zš1) (z)

= − ( ) ( )

(z) (z)

1 − 2 sin cos

Esempio 3

( )

Cerco radici di = sin −

√ 3

( )

Allora cerco il punto fisso di = − sin +

√ 3 ê

(zš1) (z) (z) (z)

B D

= − sin +

( )

Cerco : = 0 (˜)

³B“ D

(zš1) (z)

Newton: = − (˜)

′

³ B“ D

³(“) ′

( ) ( )

Introduciamo = − , ≠ 0

′ (“)

³

³(µ)

( )

Allora = − = → è punto fisso di .

′ (µ)

³ ( ),

In generale, = − ≠ 0 allora le radici di f sono punti fissi di .

Quindi applicando il metodo delle interazioni di punto fisso a , trovo radici di f. Cerco quindi che

massimizza la velocità di convergenza.

′ ( )

In particolare impongo = 0, così il metodo è almeno di ordine 2.

1

′ ′

() ( )

= 1 − → = ( )

′

1 ′ ()

Noto anche che se = , ho che = 0.

′ (“)

³ ³(“)

( )

Allora la scelta ottimale è con = − .

′ (“)

³ (zš1)

Quindi se applico il metodo delle interazioni di punto fisso a ho (almeno) = 2 → =

(˜)

³B“ D

(z) (z)

B D

= − .

(˜)

′

³ B“ D

29 1

′

′ ( ) ( )

Se = 0, si pu`ò dimostrare che = 1 − , m molteplicità di . Ricordiamo che molteplicità di

À

(<) ( )

è m se = 0, = 1, … , .

Allora considero Newton modificato: (z) D

B

(zš1) (z) ′ ( )

= − → = 0 → = 2

%

( )

(z)

′

Non conosco m, ma tipicamente posso farne delle stime. Se non conosco proprio nulla riguardo a m, lo

pongo uguale a 1 e mi accontento di un ordine pari a 1.

CRITERI DI ARRESTO (z) ′ ( )C

CB DC C

< → ≫ 1

(zš1) (z)

C C

− <

(zš1) (z) (zš1) (z) (z) (z) (z) (z) (z)

′ ′

C C C C C B D C C1 B DC

− + − = − = − = −

(zš1) (z) (z) ′ ( )C

C C~ C

− ≪ 1

Quindi OK per Newton

SISTEMA DI EQUAZIONI NON LINEARI

3

Data : ℝ → ℝ , determinare ∈ ℝ : BD = 0

Esempio 12

3 − ln = 0

3

⎧ 2

⎪

⎪ “

− ê + = 0

3

2

2

cos 1

= ⎨ 2

− 1 1

3

⎪ 1 + 5 − tan = 0

⎪ 3

2

⎩ 2

1 1

q r

= 2

3

Non riesco a scrivere come matrice: il prodotto matrice vettore deve essere lineare.

Nella maggior parte dei casi, per risolvere questi sistemi si utilizza una versione del metodo di Newton

30

modificata per equazioni vettoriali.

Newton

L'algoritmo "classico" di Newton prevede di dividere per la derivata prima della funzione. Ma in questo

caso la funzione è un vettore, e non posso dividere per il vettore!

Devo introdurre un vettore incremento che sia variabile ausiliaria.

(0)

Dato (zš1) (z) (zš1)

= +

(z) (z) (z)

B D B D

= −

(z) (z)

B D

Con lo jacobiano di valutato in . BD

<

BD¨

§ = , , = 1, … ,

<= =

Esempio

1 1 1

1

⎛ ⎞

1 2 3 6 0 −

1

⎜ ⎟

2 2 2

BD

= = : ;

3

⎜ ⎟

? ? −

⎜ ⎟

1 2 3

− − −

3 3 3

⎝ ⎠

1 2 3

(z)

B D

Devo risolvere un sistema lineare con matrice ad ogni iterazione. Se la matrice non è sparsa,

potrebbe essere una buona idea usare la fattorizzazione LU? La matrice cambia ad ogni iterazione,

(z)

perchè va valutata in un che è noto, ma cambia ad ogni iterazione! Aggiornare ad ogni terazione

è la cosa giusta da fare, ma è molto costoso sia perché il suo aggiornamento è costoso, sia perchè non

posso utilizzare fattorizzazioni precedenti, dato che cambia ad ogni iterazione.

(z)

B D

Newton è di ordine 2, ma ad ogni iterazione cambia.

Ci sono fondamentalmente due idee:

(z)

B D

1. Congelo per s iterazioni, e lo aggiorno solo ogni s iterazioni. È come se stessi cambiando

"", prendendone uno diverso che non è molto lontano da quello ottimale. Non sto mettendo in

discussione la convergenza. Il metodo non sarà più di ordine 2, ma mi aspetto = 1. non sto

introducendo un errore, la soluzione a convergenza è la stessa identica che si ha con Newton.

Arrivo però molto più lentamente a questa soluzione! Sono disposto ad aumentare il numero di

iterazioni, ma sperando che ogni iterazione sia molto più economica, perchè non devo più

ricalcolare la J, e posso usare fattorizzazioni LU per s iterazioni.

(z)

B D,

2. Approssimo ad esempio in modo che sia triangolare. Come nel primo metodo, = 1.

anche qui non sto introducendo errore numerico: la soluzione a cui convergo è sempre la stessa

di Newton! Anche qui aumenta il numero di iterazioni, ma ogni iterazione è più economica,

quindi al netto risparmio tempo.

31

4 - Interpolazione/approssimazione di funzioni

Esempio

Applico delle forze ad un disco intervertebrale e valuto sforzi e deformazioni

<=

DEFORMAZIONE = Þ

#

SFORZO = —

0.00 0.00

0.06 0.08

0,14 0,14

0,25 0,20

0,31 0,23

0,47 0,25

0,60 0,28

0,70 0,29

Mi chiedo quanto vale per = 0.38. Posso rifare l'esperimento, ma non sempre questo è fattibile.

Posso approssimare corrispondente, facendo uso dei dati a disposizione? Il valore approssimato non

sarà mai quello esatto. Voglio introdurre uno strumento matematico che possa fornirmi un valore

sensato. ( ),

Ho + 1 dati (che solitamente provengono da misure) , = 0, … , . Come posso avere

< <

( ),

un'approssimazione della quantit`à per ∈ , ≠ , ∀ = 0, … , ?

A 3 <

APPROSSIMAZIONE DI FUNZIONI

( ), [ ] ( )

Data ∈ , , continua, supponiamo di conoscere solo nei punti , = 0, … , → =

< < <

I valori , potrebbero provenire da una simulazione numerica fatta a monte. Immaginiamo infatti di

< <

dover risolvere linearmente un problema che ha come soluzione un vettore, il cui significato è una certa

quantità approssimata risolvendo un sistema lineare. Voglio capire quanto valga questa quantità non in

prossimità dei valori del vettore, ma in mezzo ad essi.

Nel caso di approssimazione di funzioni so che esiste una funzione vera, anche se non la conosco. Nel

caso di approssimazione di valori, non esiste una funzione analitica. Non avrò quindi mai una risposta

in termini di errore.

All’approssimazione di funzione invece posso applicare un metodo del quale posso quantificare la

bontà. Questo metodo sarà poi applicato all’approssimazione di dati.

32 IN