Algoritmi e dintorni: La radice quadrataettorelimoli.altervista.org/wp-content/lezioni/lezioni...1...

6
1 Algoritmi e dintorni: La radice quadrata Prof. Ettore Limoli Formule iterative L’algoritmo che, comunemente, viene presentato a scuola per l’estrazione della radice quadrata è alquanto laborioso e di scarsa utilità didattica. Chiunque si rende conto che basta pigiare un tasto per ottenere quel risultato in modo pressoché istantaneo. Questo, a mio modesto avviso, può creare disaffezione verso lo studio della matematica. Si chiede allo studente di trasformarsi in una macchina capace di eseguire un’operazione insegnando il come e non il perché. Qual è l’utilità didattica? Creare un fenomeno da baraccone? Udite… udite…! Un uomo, col solo ausilio di carta e penna, riesce ad eseguire le quattro operazioni fondamentali e INCREDIBILE pure l’estrazione di una radice quadrata. Si, lo so, la cosa fa sorridere ma, se ci pensate bene, è proprio così: esercitare le abilità manuali di calcolo è un esercizio inutile e dannoso! Si potrebbe presentare una formula iterativa che, assegnato un qualsiasi valore di , ci conduca rapidamente a una stima della . Diventerebbe un pretesto per spiegare come funziona un formula iterativa. La formula che vi propongo è quella iterativa di Newton. Ci proponiamo di determinare = √ attraverso un processo iterativo che ci consente di determinare i membri di una successione { } convergente a , ossia, tale che lim →∞ =. { 0 =1 1 = ( 0 + 0 )2 +1 = ( + )2 Per renderci conto di come funziona la cosa, seguiamo il processo iterativo servendoci del foglio elettronico di calcolo.

Transcript of Algoritmi e dintorni: La radice quadrataettorelimoli.altervista.org/wp-content/lezioni/lezioni...1...

Page 1: Algoritmi e dintorni: La radice quadrataettorelimoli.altervista.org/wp-content/lezioni/lezioni...1 Algoritmi e dintorni: La radice quadrata Prof. Ettore Limoli Formule iterative L’algoritmo

1

Algoritmi e dintorni:

La radice quadrata Prof. Ettore Limoli

Formule iterative L’algoritmo che, comunemente, viene presentato a scuola per l’estrazione della radice quadrata è alquanto

laborioso e di scarsa utilità didattica. Chiunque si rende conto che basta pigiare un tasto per ottenere quel

risultato in modo pressoché istantaneo. Questo, a mio modesto avviso, può creare disaffezione verso lo

studio della matematica. Si chiede allo studente di trasformarsi in una macchina capace di eseguire

un’operazione insegnando il come e non il perché. Qual è l’utilità didattica? Creare un fenomeno da

baraccone?

Udite… udite…! Un uomo, col solo ausilio di carta e penna, riesce ad eseguire le quattro operazioni fondamentali e

INCREDIBILE pure l’estrazione di una radice quadrata.

Si, lo so, la cosa fa sorridere ma, se ci pensate bene, è proprio così: esercitare le abilità manuali di calcolo è

un esercizio inutile e dannoso!

Si potrebbe presentare una formula iterativa che, assegnato un qualsiasi valore di 𝑎, ci conduca

rapidamente a una stima della √𝑎. Diventerebbe un pretesto per spiegare come funziona un formula

iterativa. La formula che vi propongo è quella iterativa di Newton.

Ci proponiamo di determinare 𝑥 = √𝑎 attraverso un processo iterativo che ci consente di determinare i

membri di una successione {𝑥𝑛} convergente a 𝑥, ossia, tale che lim𝑛→∞ 𝑥𝑛 = 𝑥.

{

𝑥0 = 1

𝑥1 = (𝑥0 + 𝑎 𝑥0⁄ ) 2⁄ ⋯

𝑥𝑛+1 = (𝑥𝑛 + 𝑎 𝑥𝑛⁄ ) 2⁄

Per renderci conto di come funziona la cosa, seguiamo il processo iterativo servendoci del foglio elettronico

di calcolo.

Page 2: Algoritmi e dintorni: La radice quadrataettorelimoli.altervista.org/wp-content/lezioni/lezioni...1 Algoritmi e dintorni: La radice quadrata Prof. Ettore Limoli Formule iterative L’algoritmo

2

Le formule inserite sono:

Alla cella [B4] è stato assegnato il nome: a.

Come si può osservare, già al 7° passo (step) iterativo abbiamo la soluzione esatta.

Il processo può essere seguito con facilità anche da una semplice calcolatrice scientifica. Consideriamo una

calcolatrice con il display a due righe. Nella prima riga si vede la formula inserita (riga di input). Premendo il

tasto [ = ] il risultato è visualizzato nella seconda riga (riga di output). Il tasto [ Ans ] restituisce il risultato

della precedente operazione.

Seguiamo il processo passo passo con una calcolatrice di questo tipo.

Input line 1 [=]

Output line 1

Input line (Ans + 100Ans) 2 [=]

Output line 50,5

Ad ogni successiva pressione del tasto [=] la formula viene ricalcolata col valore aggiornato di Ans. Si

ottiene così la sequenza di output: 26,24009901; 15,02553012 …

Dal 7° passo l’output si stabilizzerà sul valore 10.

Controllo della convergenza Per controllare quando il processo iterativo ha termine abbiamo adottato sostanzialmente due metodi:

1. Procedendo nell’iterazione il risultato si è stabilizzato su un determinato risultato (nel nostro

esempio 10);

2. Procedendo nell’iterazione abbiamo verificato il valore del quadrato di x.

Page 3: Algoritmi e dintorni: La radice quadrataettorelimoli.altervista.org/wp-content/lezioni/lezioni...1 Algoritmi e dintorni: La radice quadrata Prof. Ettore Limoli Formule iterative L’algoritmo

3

Il primo metodo ha un valore più generale e può essere adottato su diversi tipi di formule iterative. Il

secondo metodo è specifico dell’algoritmo in studio (calcolo della radice quadrata).

Esiste un metodo più generale che può essere applicato ad ogni processo iterativo convergente.

Si prefissa un errore Er per predeterminare il numero di cifre decimali esatte che si vogliono ottenere. Ad

esempio: Er = 10-5 per ottenere 4 cifre decimali esatte. Si arresta l’iterazione quando |𝑥𝑛 − 𝑥𝑛−1| < 𝐸𝑟.

Si voglia calcolare, ad esempio, √245,89 con almeno 2 cifre decimali esatte.

Le formule introdotte sono:

I nomi dati alle celle sono:

Page 4: Algoritmi e dintorni: La radice quadrataettorelimoli.altervista.org/wp-content/lezioni/lezioni...1 Algoritmi e dintorni: La radice quadrata Prof. Ettore Limoli Formule iterative L’algoritmo

4

Nell’ultima colonna è riportato un test di verifica. Se |𝑥𝑛 − 𝑥𝑛−1| < 𝐸𝑟 allora si scrive il valore della radice

quadrata altrimenti si prosegue visualizzando due asterischi(“**”). Col foglio elettronico di calcolo si usa la

funzione SE avente la seguente sintassi: SE(test; azione se vero; azione se falso).

Il calcolo può essere automatizzato servendosi di un qualsiasi linguaggio di programmazione. Ad esempio,

in VBA all’interno di Excel, si può scrivere una function del tipo:

Option Explicit ‘obbliga ad usare le Dim Public Function RadiceQuadrata(a As Double) As Double Dim x As Double ‘dichiarazione della variabile Dim x0 As Double ‘dichiarazione della variabile Const Er As Double = 0.000000001 ‘dichiarazione della costante If a = 0 then RadiceQuadrata = 0 ‘la radice di 0 vale 0 ElseIf a > 0 then ‘calcola la radice di a se a > 0

x = 1 ‘inizializza la variabile Do ‘inizio ciclo iterativo

x0 = x ‘memorizza l’attuale valore di x x = (x + a / x) / 2 ‘ricalcola x Loop Until Abs(x - x0) < Er ‘fine ciclo iterativo

RadiceQuadrata = x ‘assegna il valore x alla funzione Else ‘ossia se a < 0 e non esiste la radice RadiceQuadrata = 1/0 ‘forza una condizione di errore End if End Function

L’iterazione è realizzata dall’istruzione Do… Loop Until… che ha la seguente sintassi:

Do azione

Loop Until condizione

L’azione viene svolta sin quando la condizione si mantiene falsa. Se condizione risulta vera si esce dal ciclo.

Corrisponde al ciclo REPEAT… UNTIL… del Pascal.

L’errore è stato fissato al valore: Er = 10-9.

La function dichiarata Public può essere usata all’interno del foglio di calcolo come una qualsiasi funzione

predefinita. Ad esempio, calcoliamo le radici quadrate degli interi da 1 a 30.

Page 5: Algoritmi e dintorni: La radice quadrataettorelimoli.altervista.org/wp-content/lezioni/lezioni...1 Algoritmi e dintorni: La radice quadrata Prof. Ettore Limoli Formule iterative L’algoritmo

5

Le formule sono:

Come si può osservare, la funzione definita dall’utente, all’interno di Excel, è usata come una qualsiasi

funzione predefinita.

Ovviamente questa funzione esiste già in Excel e non occorre definirla. Il nostro è solo un esempio che ci

consente di capire meglio come funziona l’algoritmo.

Un po’ di teoria Vediamo ora come nasce la formula iterativa di Newton, ossia qual è il fondamento teorico che ci ha

consentito di determinarla.

Si vogliono ricercare gli zeri di una funzione y = f(x), ossia le soluzioni dell’equazione f(x) = 0.

Nel nostro caso cerchiamo la radice positiva dell’equazione x 2 – a = 0, ossia lo zero positivo della funzione

f(x) = x 2 – a. Partiamo dal punto iniziale x0 = 1 e determiniamo sulla parabola il punto A di ascissa x0.

Calcoliamo quindi la tangente alla parabola in A. Detta tangente intercetterà sull’asse X il punto di ascissa

x1. Sia B il punto della parabola di ascissa x1. La tangente in B intercetterà sull’asse X un punto di ascissa x2.

Si genera in questo modo una successione {𝑥𝑛} rapidamente convergente a 𝑥 (intersezione positiva della

parabola con l’asse X).

Poiché la tangente ad una funzione f(x) in un suo punto di ascissa xn è data da:

Page 6: Algoritmi e dintorni: La radice quadrataettorelimoli.altervista.org/wp-content/lezioni/lezioni...1 Algoritmi e dintorni: La radice quadrata Prof. Ettore Limoli Formule iterative L’algoritmo

6

𝑦 − 𝑓(𝑥𝑛) = 𝑓′(𝑥𝑛) ∙ (𝑥 − 𝑥𝑛)

Ponendo y = 0 otteniamo l’intersezione con l’asse X. L’ascissa x dell’intersezione è:

𝑥 = 𝑥𝑛 −𝑓(𝑥𝑛)

𝑓′(𝑥𝑛) .

Nel nostro caso, essendo:

𝑓(𝑥) = 𝑥2 − 𝑎 ; 𝑓′(𝑥) = 2 𝑥 ;

Si ha:

𝑥 = 𝑥𝑛 −𝑥𝑛

2 − 𝑎

2 𝑥𝑛=

𝑥𝑛2 + 𝑎

2 𝑥𝑛= (𝑥𝑛 +

𝑎

𝑥𝑛) ∶ 2 .

L’ultima espressione è quella della formula iterativa che abbiamo adottato.

Questo metodo può, con una qualsiasi funzione, avere problemi di convergenza per cui è opportuna una

scelta oculata del valore d’innesco x0. Nel nostro caso non ci sono problemi e può essere usato il valore

x0 = 1 per qualsiasi valore di a.

Conclusione Abbiamo presentato un metodo di estrazione della radice quadrata che può essere usato, pure con carta e

penna, servendosi soltanto delle operazioni aritmetiche di addizione e divisione. Questo metodo è molto

più veloce ed efficiente del procedimento classico ed è ricco di spunti didattici.

Prof. Ettore Limoli