Appunti del corso Calcolo numerico e programmazione

SCELTA DEL PUNTO DI INNESCO

L’approssimazione iniziale considerata può influire o meno sulla convergenza del metodo. Un metodo

iterativo converge:



localmente se la convergenza della successione dipende in modo critico da ;

→



globalmente se la convergenza della successione non dipende da .

→

SCELTA DELLA FUNZIONE DI ITERAZIONE ∗

La scelta del metodo iterativo influisce sulla velocità di convergenza ad una soluzione , ovvero sul numero

di iterazioni necessarie per avvicinarsi alla radice dell’equazione. Un metodo iterativo è convergente di

| | ∗

+1

lim = < ∞ = −

ordine se , dove è il fattore di convergenza.

| |

→∞

è il più grande valore che soddisfa il limite, mentre è la costante (reale) asintotica dell’errore diversa da

= 1 = 2

zero. Se si parla di convergenza lineare, mentre se la convergenza è quadratica. In generale

Università degli studi di Firenze 7

C. Bracco – Scienze chimiche I anno II semestre – A.A. 2021-22 Calcolo numerico e programmazione

≥ 1

l’ordine di convergenza può assumere anche valori non interi, ma deve comunque essere affinché il

metodo sia convergente.

SCELTA DEL CRITERIO DI ARRESTO ∗ ∗

Si vuole determinare un’approssimazione della soluzione che disti da al più una tolleranza fissata. Ci

sono due condizioni: ∗ ∗

| | | |

= − ≤ .

1. si deve arrestare il metodo quando (ma non è nota) )

() = 0 ( = 0

2. un criterio di arresto per il problema deve tener conto che la condizione potrebbe

non verificarsi mai: ∗ ∗

)

( = , ()

se è continua e in aritmetica esatta, in un punto sufficientemente vicino a ,

dovrà essere sufficientemente vicino a 0;

) |( )|

( = <

il controllo può essere sostituito con uno del tipo , dove è una

tolleranza tale che la prima condizione sia verificata.

, ( )

Per trovare assumendo sufficientemente regolare, si considera lo sviluppo di Taylor di nel

)|

|(

∗ ∗ ∗ ∗ ∗ ∗

) ) )( ) )( ) | |

( ≈ ( + ′( − = ′( − ≈ <

punto al primo ordine: quindi

′ ∗

| ( )|

′ ∗ ′ ∗

|( )| |

⇔ < ≈ ( )| ( )

con anche se in generale non è noto e se ne considera

un’approssimazione: ′ ∗

|

≪ ( )| ≈

se (funzione molto piatta);

′ ∗

|

≫ ( )| ≫

se (la tangente a ha un grosso coefficiente angolare).

CRITERI DI SALVAGUARDIA

È buona norma usare sempre un criterio di salvaguardia: si fissano a priori un numero massimo di

iterazioni da eseguire indipendentemente dall’aver raggiunto l’accuratezza desiderata (per evitare loop

infiniti). Questo è importante per i metodi:

globalmente convergenti nel caso in cui il programmatore abbia impostato una tolleranza non

→

considerando la precisione di macchina;

localmente convergenti per i quali la successione di approssimazioni può divergere se il punto di

→ ∗

innesco non è sufficientemente vicino a , non soddisfando mai alcun criterio di arresto possibile.

0

Università degli studi di Firenze 8

C. Bracco – Scienze chimiche I anno II semestre – A.A. 2021-22 Calcolo numerico e programmazione

CONDIZIONAMENTO DEL PROBLEMA ′ ∗ ∗

| ( )|. | |, | |

≈ ≈ − ≈

Riprendiamo in considerazione la relazione Essendo si ha che

1 1

∗ ∗ ∗ ∗

|( ) )|, | | |( ) )| ) )|

≈ − ( − ≈ − ( = |( − (

e, dato che

′ ∗ ′ ∗

( )| ( )|

| |

1

=

dove è il numero di condizionamento del problema.

′ ∗

( )|

|

METODO DI BISEZIONE

[, ], ∈ ([, ]), < , () ∙ () < ⇒

Se è una funzione continua in con e per il teorema degli

∗ ∗

[, [,

∃ ∈ ] . . ( ) ≠ . ] ≡ [ , ]

zeri L’intervallo si dice anche che è un intervallo di confidenza

1 1

per la radice dell’equazione. +

∗ 1 1

[ , ] ⇒ =

Dim: Si considera come approssimazione iniziale di il punto medio di e, dopo

1 1 1 1 2

( )

aver calcolato il valore che la funzione assume in tale punto:

1

❖ )

( = 0 ;

se allora è radice di

1 1

❖ )( )

( < 0 [ , )

se allora lo zero cade in e

1 1 1 1

[ , ];

quindi si ripete il procedimento nell’intervallo 1 1

❖ )( )

( < 0 ( , ]

se allora lo zero cade in e

1 1 1 1

[ , ].

quindi si ripete il procedimento nell’intervallo 1 1

∗

Si considera poi come approssimazione di il punto

+

[ , ] ⇒ =

medio di e, dopo aver calcolato il

2

( )

valore che la funzione assume in tale punto:

❖ )

( = 0 ;

se allora è radice di

❖ )( )

( < 0 [ , )

se allora lo zero cade in e

[ , ];

quindi si ripete il procedimento nell’intervallo

❖ )( )

( < 0 ( , ]

se allora lo zero cade in e

[ , ].

quindi si ripete il procedimento nell’intervallo

[, ) )

] = [ , ] ( ∙ ( < 0

TEOREMA: Se è continua nell’intervallo e , allora la successione

1 1 1 1 ∗

{ } ∈ [ , ]

generata dal metodo di bisezione converge ad un punto tale che

=1,2,… 1 1

−

∗ ∗

) | | | | | |

( = 0. 0 ≤ = − ≤ ⇒ lim = 0.

2 ⟶∞

| | 1 1

+1

 lim = ⇒ = 1 > 1 =

Ordine di convergenza del metodo: (poiché non verifica il limite); .

| | 2 2

⟶∞ −

 ⌈ (

: ≤ ⇒ ≥ − ) −

Limite massimo al # di iterazioni per convergere al limite di 2

2

()⌉.

2

METODO DI NEWTON

Dato il punto di innesco , l’approssimazione alla prima iterazione si calcola come

0 (

= , ( ))

l’ascissa dell’intersezione tra una retta passante per e l’asse delle

0 0 0

ascisse. ( )

)

= ( + ( − ) 0

0 0

{ ⇒ = −

0

=0

Università degli studi di Firenze 9

C. Bracco – Scienze chimiche I anno II semestre – A.A. 2021-22 Calcolo numerico e programmazione

′ ∗

( ),

=

Posto si considera come approssimazione di l’ascissa dell’intersezione fra la retta e l’asse

1

( )

0

= −

delle ascisse, ovvero: . Analogamente, all’iterazione , l’approssimazione si

( + 1) −

1 0 ′( )

0

( )

= −

ottiene come: .

+1 ′( )

Dobbiamo studiare la convergenza del metodo, che è locale.

() =

TEOREMA DEL PUNTO FISSO: Sia una funzione di iterazione che definisce il metodo numerico +1

|()

( ). > 0 0 ≤ < 1 − ()| ≤ | − |

Se esistono e tali che ,

∗ ∗

∀, ∈ ≔ ( − , + ) , allora:

∗ ∗ ∗ ∗

)

() ∈ . . ( =

(i) è l’unico punto fisso di in (cioè l’unico ;

∈ ⇒ ∈ , = 1, 2, …;

(ii) Se per

0

∗

lim =

(iii) .

→∞ ()

() = −

È sufficiente applicare questo teorema con .

′()

∗ ∗ ∗ ∗

| | |( )| |

, ̅ ∈ , − ̅ = ) − (̅ ≤ | − ̅ <

Dim (i): Per assurdo, se esistessero due punti fissi allora

∗

| |

− ̅ , che è assurdo. ∈ , = 0, 1, 2, … = 0 ( ∈ ). ∈

Dim (ii): Dimostriamo per induzione che . È vero per Notiamo che

0

∗ ∗ ∗ ∗

| | |

⇔ | − | < . ∈ , − = |( ) − ( )| ≤ | − <

Supponendo si ha

+1

< ⇒ ∈ .

+1

∗ ∗ ∗ ∗ 2 ∗

| | |( ) | ) )| | |

− = − ( )| ≤ | − = |( − ( ≤ − = ⋯ ≤

Dim (iii): −1 −1 −2 −2

∗ ∗ ∗

| | | | | | | |

− → → ∞ 0 ≤ lim = lim − ≤ lim − =

per e dunque

0 0

→∞ →∞ →∞<