Come utilizzare il metodo di bisezione per il calcolo numerico

Utilizzare il metodo di bisezione nel calcolo numerico

Comprensione del metodo di bisezione per la trovatura delle radici e il suo funzionamento

Foto di Andrew su Unsplash

POSSIAMO COLLEGARCI SU:| LINKEDIN | TWITTER | VoAGI | SUBSTACK |

Un sotto-campo dell’informatica e della matematica noto come calcolo numerico si concentra sull’utilizzo di metodi e algoritmi numerici implementati su computer per risolvere problemi matematici. Implica l’esecuzione di simulazioni e calcoli per ottenere approssimazioni di risposte a enigmi matematici che potrebbero essere difficili o impossibili da risolvere analiticamente.

In matematica abbiamo molte equazioni. Per usare queste equazioni nella vita reale, dobbiamo risolverle. Diciamo “l’equazione è risolta” quando troviamo le sue radici, ovvero f(x) = 0, dove f(x) è una funzione continua e vogliamo trovare il valore (o i valori) di ‘x‘ che rende la funzione uguale a zero. Quando inseriamo le radici nell’equazione, l’equazione diventa zero. Vediamo un semplice esempio:

f(x) = x * x — 1

x * x — 1 = 0

f(1) = (1) * (1) –1 = 0

f(-1) = (-1) * (-1) –1=0

Quindi le radici delle equazioni sopra sono 1 e –1.

Come abbiamo capito ciò?

Abbiamo inserito 1 al posto di x nell’equazione. È così che possiamo risolvere queste equazioni. Ma purtroppo, nella vita reale, le equazioni non sono così semplici da risolvere.

Per risolvere le equazioni della vita reale, abbiamo molti metodi noti come “metodi di ricerca delle radici”. Questi metodi sono molto utili per il calcolo numerico, l’ottimizzazione, l’interpolazione, il fitting di curve, l’analisi numerica e in molti altri campi.

Se iniziassimo a parlare di evoluzione, ci vorrebbe un intero blog, ma iniziamo direttamente con l’implementazione delle tecniche.

Metodo di bisezione

Il metodo di bisezione in matematica è un approccio semplice per individuare le radici numeriche di un’equazione con una sola incognita. Il metodo di bisezione è il metodo numerico più semplice per risolvere il problema trascendentale. Approfondiremo in dettaglio l’approccio di bisezione con problemi risolti in questo articolo.

Per determinare le radici di un problema polinomiale, utilizziamo il metodo di bisezione. Esso divide e separa l’intervallo in cui si trova la radice dell’equazione. Il teorema degli intervalli intermedi per funzioni continue serve come premessa guida del metodo. Esso opera riducendo la distanza tra gli intervalli positivi e negativi finché non si avvicina alla risposta corretta. Questa tecnica riduce la distanza tra le variabili facendo la media tra gli intervalli positivi e negativi.

Sebbene sia un processo semplice, si muove lentamente. Il metodo di bisezione è talvolta indicato come metodo della dichotomia, metodo di ricerca binaria, metodo di divisione degli intervalli e metodo di ricerca delle radici.

Fonte: Wikipedia

Algoritmo del metodo di bisezione

Per ogni funzione continua f(x), [Fonte]

Trovare due punti, diciamo a e b, tali che a < b e f(a)* f(b) < 0

Trovare il punto medio tra a e b, diciamo “c”

t è la radice della funzione data se f(c) = 0; altrimenti, seguire il passaggio successivo

Dividere l’intervallo [a, b] — Se f(c)*f(a) <0, esiste una radice tra c e a – altrimenti, se f(c) *f (b) < 0, esiste una radice tra c e b

Ripetere i tre passaggi sopra fino a quando f(c) = 0.

Il metodo della bisezione è un metodo di approssimazione per trovare le radici dell’equazione data dividendo ripetutamente l’intervallo. Questo metodo dividerà l’intervallo fino a quando non verrà trovato l’intervallo risultante, che è estremamente piccolo.

CODICE:

Avviso/Avvertenza: Questo codice serve solo a mostrare come creare un codice di bisezione di base in Python. Non rivendico alcuna ottimizzazione nel codice e ulteriori miglioramenti sono necessari in base al problema specifico.

Prendiamo una funzione semplice.

F(x) = x * x — 3

def fun(x):    return x * x - 3

Scriviamo un codice molto semplice per creare una semplice pipeline per il codice del metodo di bisezione.

a = 1    #Approssimazione prima radiceb = 2    #Approssimazione seconda radice #Dichiarazione della funzionedef fun(x):    return x*x - 3a_originale = fun(a)b_originale = fun(b)i = 0while i < 50 :        #Fai questo per 50 volte     c = (a + b)/2    c_originale = fun(c)    if c_originale < 0:        a = c    else:        b = c#     plt.plot(a)    print("Il valore di a è {}".format(a))    print("Il valore di b è {}".format(b))    i+=1

Quanto sopra è molto semplice ma un codice di base che rappresenta il metodo di bisezione a un livello di forza bruta.

Vediamo il suo output

Il valore di a è 1.5Il valore di b è 2Il valore di a è 1.5Il valore di b è 1.75Il valore di a è 1.625Il valore di b è 1.75Il valore di a è 1.6875Il valore di b è 1.75Il valore di a è 1.71875Il valore di b è 1.75Il valore di a è 1.71875Il valore di b è 1.734375Il valore di a è 1.7265625Il valore di b è 1.734375Il valore di a è 1.73046875Il valore di b è 1.734375Il valore di a è 1.73046875Il valore di b è 1.732421875Il valore di a è 1.7314453125Il valore di b è 1.732421875Il valore di a è 1.73193359375Il valore di b è 1.732421875Il valore di a è 1.73193359375Il valore di b è 1.732177734375Il valore di a è 1.73193359375Il valore di b è 1.7320556640625Il valore di a è 1.73199462890625Il valore di b è 1.7320556640625Il valore di a è 1.732025146484375Il valore di b è 1.7320556640625Il valore di a è 1.7320404052734375Il valore di b è 1.7320556640625Il valore di a è 1.7320480346679688Il valore di b è 1.7320556640625Il valore di a è 1.7320480346679688Il valore di b è 1.7320518493652344Il valore di a è 1.7320499420166016Il valore di b è 1.7320518493652344Il valore di a è 1.7320499420166016Il valore di b è 1.732050895690918Il valore di a è 1.7320504188537598Il valore di b è 1.732050895690918Il valore di a è 1.7320506572723389Il valore di b è 1.732050895690918Il valore di a è 1.7320507764816284Il valore di b è 1.732050895690918Il valore di a è 1.7320507764816284Il valore di b è 1.7320508360862732Il valore di a è 1.7320508062839508Il valore di b è 1.7320508360862732Il valore di a è 1.7320508062839508Il valore di b è 1.732050821185112Il valore di a è 1.7320508062839508Il valore di b è 1.7320508137345314Il valore di a è 1.7320508062839508Il valore di b è 1.732050810009241Il valore di a è 1.7320508062839508Il valore di b è 1.732050808146596Il valore di a è 1.7320508072152734Il valore di b è 1.732050808146596Il valore di a è 1.7320508072152734Il valore di b è 1.7320508076809347Il valore di a è 1.732050807448104Il valore di b è 1.7320508076809347Il valore di a è 1.7320508075645193Il valore di b è 1.7320508076809347Il valore di a è 1.7320508075645193Il valore di b è 1.732050807622727Il valore di a è 1.7320508075645193Il valore di b è 1.7320508075936232Il valore di a è 1.7320508075645193Il valore di b è 1.7320508075790713Il valore di a è 1.7320508075645193Il valore di b è 1.7320508075717953Il valore di a è 1.7320508075681573Il valore di b è 1.7320508075717953Il valore di a è 1.7320508075681573Il valore di b è 1.7320508075699763Il valore di a è 1.7320508075681573Il valore di b è 1.7320508075690668Il valore di a è 1.732050807568612Il valore di b è 1.7320508075690668Il valore di a è 1.7320508075688394Il valore di b è 1.7320508075690668Il valore di a è 1.7320508075688394Il valore di b è 1.7320508075689531Il valore di a è 1.7320508075688394Il valore di b è 1.7320508075688963Il valore di a è 1.7320508075688679Il valore di b è 1.7320508075688963Il valore di a è 1.7320508075688679Il valore di b è 1.732050807568882Il valore di a è 1.732050807568875Il valore di b è 1.732050807568882Il valore di a è 1.732050807568875Il valore di b è 1.7320508075688785Il valore di a è 1.7320508075688767Il valore di b è 1.7320508075688785Il valore di a è 1.7320508075688767Il valore di b è 1.7320508075688776

La produzione sopra riportata è il risultato di un esperimento con i valori di a e b per 50 iterazioni. Il sistema avrà difficoltà a elaborare numeri superiori a 16 cifre a causa di limitazioni. Ma possiamo vedere che i valori delle radici si avvicinano sempre di più.

Ultimo valore di a: 1.73205080

Ultimo valore di b: 1.73205080

Sostituendo questi ultimi valori nell’equazione otterremo:

F(a) = -0.000176000

F(b) = 0.000176000

Molto vicino a 0 !!!

Ora sappiamo che questa logica funziona. Ottimizziamo il codice e visualizziamo il risultato in modo da comprenderlo meglio.

import matplotlib.pyplot as pltdef Metodo_bisezione(a, b, iterazioni):    def fun(x):        return x * x - 3    # Crea un grafico e un asse per il plot    plt.figure()    plt.xlabel('x')    plt.ylabel('y')    plt.title('Visualizzazione dell\'equazione y = x^2 - 3')    # Traccia l'equazione y = x^2 - 3 nell'intervallo [a, b]    x_values = [x / 100.0 for x in range(int(a * 100), int(b * 100) + 1)]    y_values = [fun(x) for x in x_values]    plt.plot(x_values, y_values, color='orange', label='y = x^2 - 3')    # Traccia i punti iniziali a e b sul grafico    plt.plot(a, fun(a), 'ro', label='f(a)')    plt.plot(b, fun(b), 'go', label='f(b)')    # Traccia la linea dell'asse x    plt.axhline(linewidth=2, y=0, color='brown', linestyle='dashdot')    plt.axhline(y=fun(a), color='blue', linestyle='dashdot')    plt.axhline(y=fun(b), color='blue', linestyle='dashdot')    plt.legend()    plt.grid()    # Aggiorna il grafico e mostralo    plt.pause(1)    a_vals = [a]    b_vals = [b]    i = 0    while i < iterazioni:        c = (a + b) / 2        c_originale = fun(c)        if c_originale < 0:            a = c        else:            b = c        i += 1        a_vals.append(a)        b_vals.append(b)    # Traccia tutti i valori di a e b in colori diversi    plt.plot([fun(a_val) for a_val in a_vals], 'mo', label='f(a)',color='orange')    plt.axhline(y=0, color='brown', linestyle='dashdot')    plt.plot([fun(b_val) for b_val in b_vals], 'co', label='f(b)')    plt.axhline(y=0, color='brown', linestyle='dashdot')    plt.legend()    plt.grid()    # Aggiorna il grafico e mostralo#     plt.pause(1)    plt.show()

#Chiama la funzione con i valori iniziali di a, b e il numero di iterazionia_iniziale = 1b_iniziale = 2iterazioni = 50Metodo_bisezione(a_iniziale, b_iniziale, iterazioni)

Ho modificato questo codice in modo che accetti input e mostri il grafico delle radici.

Output del codice

Nella figura sopra, possiamo vedere i nostri punti di partenza e i loro valori di F(x). La linea rossa evidenziata è ciò che vogliamo ottenere con queste radici iniziali.

Nella figura sopra, ho tracciato gli output degli ultimi 10 punti su 50. Puoi vedere che i valori convergono verso 0 e gli ultimi punti sono quasi 0. È un segno che abbiamo trovato le radici. Le iterazioni sono il limite che puoi impostare per controllare l’intera esecuzione. Il parametro potrebbe essere il valore soglia per la funzione. Quindi devi fermarti dopo un certo numero di iterazioni o se hai raggiunto un certo valore soglia.

Puoi cambiare la funzione e utilizzare questo codice per trovare le radici della tua equazione, o puoi utilizzare direttamente il link sottostante, che ti porterà al calcolatore online del metodo della bisezione.

Calcolatrice online del metodo della bisezione

Il calcolatore online del metodo della bisezione è un semplice e affidabile strumento per trovare la radice reale di equazioni non lineari usando…

www.codesansar.com

Vantaggi del metodo della bisezione:

Convergenza: la garanzia di affidabilità assicura che l’approccio troverà una soluzione fintanto che viene fornito un intervallo che contiene la radice.

Semplicità: il metodo è semplice teoricamente e facile da usare.

Robustezza: rispetto ad altre tecniche di ricerca delle radici, il metodo della bisezione è meno sensibile all’ipotesi iniziale.

Raffinamento dell’intervallo: ogni miglioramento garantisce che con ogni iterazione la soluzione sia più precisa.

Nessuna necessità di derivate: ciò lo rende adatto a funzioni per le quali le derivate sono indisponibili o difficili da calcolare.

Convergenza globale: questo approccio troverà infine una radice se è presente all’interno dell’intervallo.

Limitazioni del metodo della bisezione:

Convergenza lenta: il metodo può essere lento rispetto ad altri algoritmi di ricerca delle radici con tassi di convergenza più rapidi, specialmente per funzioni con pendenze ripide, anche se garantisce la convergenza.

Richiesta di un intervallo: la procedura potrebbe non essere appropriata se tale intervallo è sconosciuto o difficile da determinare.

Può essere trovata solo una radice: il metodo della bisezione è progettato per scoprire una sola radice nell’intervallo fornito [a, b]. La procedura raggiungerà una delle radici di una funzione se ne ha più di una all’interno di quell’intervallo.

Applicabilità limitata a equazioni complesse: il metodo della bisezione è più adatto per equazioni con una singola radice reale all’interno dell’intervallo specificato.

Per superare queste limitazioni, abbiamo molti altri metodi che sono a livello avanzato per la ricerca delle radici con diversi meccanismi. Li copriremo nella prossima serie di blog.

Se hai trovato utile questo articolo

È un fatto provato che “la generosità ti rende una persona più felice”; quindi, applaude all’articolo se ti è piaciuto. Se hai trovato utile questo articolo, seguimi su Linkedin e VoAGI. Puoi anche iscriverti per essere avvisato quando pubblico articoli. Creiamo una comunità! Grazie per il tuo supporto!

Puoi fare clic qui per offrirmi un caffè.

Comprensione di LangChain 🦜️🔗: PARTE 1

Comprensione teorica di catene, promemoria e altri moduli importanti in Langchain

pub.towardsai.net

Guida pratica alla selezione delle architetture CNN per applicazioni di visione artificiale

Da LeNet a EfficientNet: Scegliendo la migliore architettura CNN per il tuo progetto

levelup.gitconnected.com

Guida completa: Risorse principali per la visione artificiale in un unico blog

Salva questo blog per risorse complete per la visione artificiale

VoAGI.com

Potenzia i tuoi progetti di Data Science, ML e CV: Strumenti essenziali per la gestione efficace dei progetti

Rendi più veloci le tue compilazioni e i tuoi progetti con questi strumenti

pub.towardsai.net

Saluti,

Chinmay