50% di sconto su tutto fino al 31/12/2024

Il mio account
Accedi ai contenuti scaricabili
a

Menu

M

Chiudi

Il metodo di bisezione

Metodo di bisezione

Home » Il metodo di bisezione

Il metodo di bisezione

Data un’equazione nella forma f(x)=0 in cui f è una funzione continua, il Il teorema di esistenza degli zeri permette di dimostrare l’esistenza di soluzioni in un intervallo [a,b], se f(a) e f(b) hanno segno diverso. Ricavare tali soluzioni in forma esplicita può essere difficile o anche impossibile. In tali casi, è utile determinare un’approssimazione delle soluzioni cercate e una stima dell’errore commesso.

Il metodo di bisezione è uno strumento in tale direzione, permettendo di ottenere tali approssimazioni con una precisione arbitraria, dipendente dal numero di passi che si intende compiere: partendo dall’intervallo iniziale, a ogni passo viene individuata la metà dell’intervallo contenente la soluzione, raddoppiando cioè la precisione sulla sua approssimazione.

Questo articolo espone il metodo in maniera chiara e precisa, mostrando esempi pratici e applicazioni al calcolo numerico. Esso risulta dunque una risorsa preziosa per studenti, appassionati e professionisti del settore. Se desideri intraprendere un intrigante viaggio nel mondo al confine tra la Matematica pura e l’analisi numerica, questo articolo è quello che cercavi!

Consigliamo le seguenti risorse di teoria collegata:

Di seguito le raccolte di esercizi su argomenti correlati:

 

Autori e revisori

Leggi...

Autore: Martina Moro  

Revisore: Valerio Brunetti.  

 

Introduzione

Leggi...

Consideriamo un’equazione della forma

(1)   \begin{equation*} f(x) = 0, \end{equation*}

dove f:[a,b] \rightarrow \mathbb{R} è una funzione continua sull’intervallo [a,b], per a,b \in \mathbb{R} con a<b. Quando la funzione f ha una forma elementare cioè è un polinomio di “grado basso”, una qualsiasi funzione elementare (come f(x) = e^x, f(x)=\cos(x), etc.), o una combinazione delle precedenti, l’equazione (1) può essere trattata con i metodi insegnati alle scuole superiori. Generalmente, per funzioni più complesse (e.g. f(x) = e^x+x), non è possibile calcolare analiticamente la soluzione dell’equazione (1) e bisogna ricorrere all’aiuto di un programma di calcolo per determinare se tale equazione ha una o più soluzioni nel campo dei numeri reali. In questi casi, se una soluzione esiste, ci si accontenta di una sua buona approssimazione. Esistono vari metodi di approssimazione ed il più elementare di questi è senza dubbio il metodo di bisezione che sfrutta il teorema degli zeri.

 

Metodo di bisezione

Leggi...

Un’idea intuitiva di cosa sia il metodo di bisezione è la seguente: è un metodo iterativo che prevede la costruzione di una successione di intervalli incapsulati che si stringono verso la soluzione. In poche parole, si costruisce una successione di intervalli via via più piccoli ognuno lungo la metà del precedente, tutti contenenti la soluzione; stringendo sempre di più l’intervallo ci si avvicina alla radice dell’equazione e si termina quando la lunghezza dell’n-esimo intervallo è sufficientemente piccola.

L’algoritmo generale del metodo di bisezione è descritto di seguito.

Consideriamo una funzione f: [a,b] \to \mathbb{R} continua nel proprio dominio e valutiamola agli estremi dell’intervallo.

Se la funzione valutata agli estremi ha segno opposto, cioè è tale che f(a)\cdot f(b)<0, per il teorema degli zeri la funzione f ammette almeno una radice reale in quell’intervallo [a,b]. Supponiamo che l’equazione f(x)=0 abbia una sola radice reale nell’intervallo [a,b].

Una volta individuato l’intervallo che contiene la soluzione, dobbiamo trovare il punto medio di tale intervallo e considerare quindi gli intervalli

    \[\bigg[a,\dfrac{a+b}{2}\bigg] \qquad \mbox{e} \qquad \bigg[\dfrac{a+b}{2},b\bigg].\]

Analogamente a quanto fatto con l’intervallo [a,b] dobbiamo valutare la funzione agli estremi di entrambi gli intervalli, scegliendo l’intervallo dove la funzione valutata agli estremi abbia segno opposto, quindi se

    \[f(a)\cdot f\left(\dfrac{a+b}{2}\right)<0\]

allora l’intervallo da considerare per il prossimo passo è

    \[\bigg[a,\dfrac{a+b}{2}\bigg]\]

altrimenti si considera l’intervallo

    \[\bigg[\dfrac{a+b}{2},b\bigg].\]

Essendo ancora una volta verificato il teorema degli zeri possiamo ripetere il procedimento iterando le operazioni: dimezzare l’intervallo e valutare la funzione agli estremi, scegliendo l’intervallo dove la funzione verifica la condizione di segno opposto agli estremi avvicinandoci sempre più alla soluzione dell’equazione.

Il processo appena descritto, nel caso in cui la soluzione non cada in uno dei punti medi degli intervalli trovati, deve essere arrestato secondo qualche criterio. Andiamo dunque ad esporre i vari criteri possibili. Una prima alternativa, per quanto semplice, consiste nel fissare a priori il numero massimo di iterazioni N_{\rm max}. Una volta arrestato il metodo, sempre nel caso non si sia già trovata la soluzione esatta durante qualche passo, la soluzione teorica è approssimata dal punto medio dell’ultimo intervallo trovato [a_{N_{\rm max}},b_{N_{\rm max}}], ossia

(2)   \begin{equation*} x^* \approx x_{N_{\rm max}} = \frac{a_{N_{\rm max}} + b_{N_{\rm max}}}{2}. \end{equation*}

Per questo primo criterio riportiamo un diagramma di flusso

    metodo di bisezione

   

Un secondo criterio consiste nell’arrestare il procedimento quando f(x_N) è abbastanza vicino a zero. Per questo fine, bisogna determinare l’errore assoluto commesso dall’approssimazione (2) procedendo come segue:

(3)   \begin{equation*} e_n := |x^* - x_n| \leq \frac{1}{2} |b_n - a_n| = \frac{b-a}{2^{n+1}}. \end{equation*}

La relazione (3) ci permette di trarre due importanti conclusioni. In primo luogo ci garantisce che il metodo, sotto le ipotesi sopracitate, converge effettivamente alla soluzione:

 

Corollario 1. \displaystyle \lim_{n\rightarrow +\infty} e_n = 0.

 

Dall’altro lato, otteniamo il secondo criterio di arresto per il metodo, che prevede di fissare una tolleranza sull’errore che siamo disposti ad accettare, denotata con \tau>0. Invertendo la disuguaglianza (3) scopriamo che per rispettare la tolleranza imposta, sono necessari almeno \lfloor \log_2\frac{b-a}{\tau} \rfloor passi, infatti

    \[\frac{b-a}{2^{n+1}}\leq \tau \quad\Longleftrightarrow\quad 2^{n+1} \geq \frac{b-a}{\tau} \quad\Longleftrightarrow\quad n \geq \log_2\left(\frac{b-a}{\tau}\right) -1.\]

 

Esempio 1.

Leggi...

Il seguente esempio ha il solo scopo di illustrare i passaggi del metodo, essendo la soluzione nota.

Consideriamo la funzione

    \[f(x) = \ln(x), \qquad \forall x \in \left[\dfrac{1}{2}\,, 2\right].\]

Si vuole trovare una soluzione nell’intervallo fissando la tolleranza \tau = 0,01.

Si vede facilmente che f(1/2)\cdot f(2) < 0 per cui deve esistere x_0 \in (1/2 \, , \, 2) tale che f(x_0) = 0. Nella seguente tabella sono riportate le iterazioni dell’algoritmo precedentemente discusso creando per ogni passo un nuovo intervallo più piccolo [a_n, b_n] contenente il punto x_0.

     

Tabella 1: applicazione dell’algoritmo di bisezione con \tau = 0,01, m_n punto medio dell’intervallo [a_n,b_n]

   

La tolleranza \tau=0.01 > \tau_4 quindi possiamo prendere m_{4} = 1.01 come zero di f. Osserviamo che f(m_{4}) = 0.0155 che è molto vicino allo zero. Questo non ci sorprende in quanto è noto che lo zero di f è x_0 = 1.

 

Codice MATLAB

Leggi...

Un esempio di codice MATLAB che implementa il metodo di bisezione Imponendo come condizione di arresto che l’errore (err) sia inferiore ad un certa tolleranza (toll). Il codice risulta diviso in tre parti:

 

  1. Dati di input: vengono inizializzati tutti gli elemnti necessari (e.g. a, b, toll);
  2. Algoritmo di bisezione: implementa il codice di bisezione tenendo conto della condizione di arresto err
  3. Post-processing: vengono graficati alcuni andamenti necessari ad una valutazione della correttezza del codice. In particolare, sono stati considerati gli andamenti di a_N e b_N e l’andamento dell’errore.

   

   

da cui

   

   

 
 

Tutta la teoria di analisi matematica

Leggi...

  1. Teoria Insiemi
  2. Il metodo della diagonale di Cantor
  3. Logica elementare
  4. Densità dei numeri razionali nei numeri reali
  5. Insiemi Numerici \left(\mathbb{N},\, \mathbb{Z},\, \mathbb{Q}\right)
  6. Il principio di induzione
  7. Gli assiomi di Peano
  8. L’insieme dei numeri reali: costruzione e applicazioni
  9. Concetti Fondamentali della Retta Reale: Sintesi Teorica
  10. Costruzioni alternative di \mathbb{R}
  11. Binomio di Newton
  12. Spazi metrici, un’introduzione
  13. Disuguaglianza di Bernoulli
  14. Disuguaglianza triangolare
  15. Teoria sulle funzioni
  16. Funzioni elementari: algebriche, esponenziali e logaritmiche
  17. Funzioni elementari: trigonometriche e iperboliche
  18. Funzioni goniometriche: la guida essenziale
  19. Teorema di Bolzano-Weierstrass per le successioni
  20. Criterio del rapporto per le successioni
  21. Definizione e proprietà del numero di Nepero
  22. Limite di una successione monotona
  23. Successioni di Cauchy
  24. Il teorema ponte
  25. Teoria sui limiti
  26. Simboli di Landau
  27. Funzioni continue – Teoria
  28. Il teorema di Weierstrass
  29. Il teorema dei valori intermedi
  30. Il teorema della permanenza del segno
  31. Il teorema di Heine-Cantor
  32. Il teorema di esistenza degli zeri
  33. Il metodo di bisezione
  34. Teorema ponte versione per le funzioni continue
  35. Discontinuità di funzioni monotone
  36. Continuità della funzione inversa
  37. Teorema delle contrazioni o Teorema di punto fisso di Banach-Caccioppoli
  38. Teoria sulle derivate
  39. Calcolo delle derivate: la guida pratica
  40. Teoria sulle funzioni convesse
  41. Il teorema di Darboux
  42. I teoremi di de l’Hôpital
  43. Teorema di Fermat
  44. Teoremi di Rolle e Lagrange
  45. Il teorema di Cauchy
  46. Espansione di Taylor: teoria, esempi e applicazioni pratiche
  47. Polinomi di Taylor nei limiti: istruzioni per l’uso
  48. Integrali definiti e indefiniti
  49. Teorema fondamentale del calcolo integrale (approfondimento)
  50. Integrali ricorsivi
  51. Formule del trapezio, rettangolo e Cavalieri-Simpson
  52. Teoria sugli integrali impropri
  53. Funzioni integrali – Teoria
  54. Introduzione ai numeri complessi – Volume 1 (per un corso di ingegneria — versione semplificata)
  55. Introduzione ai numeri complessi – Volume 1 (per un corso di matematica o fisica)
  56. Serie numeriche: la guida completa
  57. Successioni di funzioni – Teoria
  58. Teoremi sulle successioni di funzioni
    1. 58a. Criterio di Cauchy per la convergenza uniforme
    2. 58b. Limite uniforme di funzioni continue
    3. 58c. Passaggio al limite sotto il segno di integrale
    4. 58d. Limite uniforme di funzioni derivabili
    5. 58e. Piccolo teorema del Dini
    6. 58f. Procedura diagonale e teorema di Ascoli-Arzela
  59. Serie di funzioni – Teoria
  60. Serie di potenze – Teoria
  61. Serie di Fourier – Teoria e applicazioni
  62. Integrali multipli — Parte 1 (teoria)
  63. Integrali multipli — Parte 2 (teoria e esercizi misti)
  64. Regola della Catena — Teoria ed esempi.
  65. Jacobiano associato al cambiamento di coordinate sferiche
  66. Guida ai Massimi e Minimi: Tecniche e Teoria nelle Funzioni Multivariabili
  67. Operatore di Laplace o Laplaciano
  68. Teoria equazioni differenziali
  69. Equazione di Eulero
  70. Teoria ed esercizi sulla funzione Gamma di Eulero
  71. Teoria ed esercizi sulla funzione Beta
  72. Approfondimento numeri complessi
  73. Diverse formulazioni dell’assioma di completezza
  74. Numeri di Delannoy centrali
  75. Esercizi avanzati analisi

 
 

Tutte le cartelle di Analisi Matematica

Leggi...

  1. Prerequisiti di Analisi
    1. Ripasso algebra biennio liceo
    2. Ripasso geometria analitica
    3. Ripasso goniometria e trigonometria
    4. Errori tipici da evitare
    5. Insiemi numerici N,Z,Q,R
    6. Funzioni elementari
    7. Logica elementare
    8. Insiemi
  2. Successioni
    1. Teoria sulle Successioni
    2. Estremo superiore e inferiore
    3. Limiti base
    4. Forme indeterminate
    5. Limiti notevoli
    6. Esercizi misti Successioni
    7. Successioni per ricorrenza
  3. Funzioni
    1. Teoria sulle funzioni
    2. Verifica del limite in funzioni
    3. Limite base in funzioni
    4. Forme indeterminate in funzioni
    5. Limiti notevoli in funzioni
    6. Calcolo asintoti
    7. Studio di funzione senza derivate
    8. Dominio di una funzione
    9. Esercizi misti Funzioni
    10. Esercizi misti sui Limiti
  4. Funzioni continue-lipschitziane-holderiane
    1. Teoria sulle Funzioni continue-lipschitziane-holderiane
    2. Continuità delle funzioni
    3. Continuità uniforme
    4. Teorema degli zeri
    5. Esercizi sul teorema di Weierstrass senza l’uso delle derivate
  5. Calcolo differenziale
    1. Derivate
    2. Calcolo delle derivate
    3. Retta tangente nel calcolo differenziale
    4. Punti di non derivabilità nel calcolo differenziale
    5. Esercizi sul teorema di Weierstrass con l’uso delle derivate
    6. Studio di funzione completo nel calcolo differenziale
    7. Esercizi teorici nel calcolo differenziale
    8. Metodo di bisezione
    9. Metodo di Newton
  6. Teoremi del calcolo differenziale
    1. Teoria sui Teoremi del calcolo differenziale
    2. Teorema di Rolle
    3. Teorema di Lagrange
    4. Teorema di Cauchy
    5. Teorema di De L’Hôpital
  7. Calcolo integrale
    1. Integrale di Riemann
    2. Integrali immediati
    3. Integrale di funzione composta
    4. Integrali per sostituzione
    5. Integrali per parti
    6. Integrali di funzione razionale
    7. Calcolo delle aree
    8. Metodo dei rettangoli e dei trapezi
    9. Esercizi Misti Integrali Indefiniti
    10. Esercizi Misti Integrali Definiti
  8. Integrali impropri
    1. Teoria Integrali impropri
    2. Carattere di un integrale improprio
    3. Calcolo di un integrale improprio
  9. Espansione di Taylor
    1. Teoria Espansione di Taylor
    2. Limiti di funzione con Taylor
    3. Limiti di successione con Taylor
    4. Stime del resto
  10. Funzioni integrali (Approfondimento)
    1. Teoria Funzioni integrali (Approfondimento)
    2. Studio di funzione integrale
    3. Limiti con Taylor e De L’Hôpital
    4. Derivazione di integrali parametrici (Tecnica di Feynmann)
  11. Numeri Complessi
    1. Teoria Numeri complessi
    2. Espressioni con i numeri complessi
    3. Radice di un numero complesso
    4. Equazioni con i numeri complessi
    5. Disequazioni con i numeri complessi
    6. Esercizi misti Numeri complessi
  12. Serie numeriche
    1. Teoria Serie numeriche
    2. Esercizi Serie a termini positivi
    3. Esercizi Serie a termini di segno variabile
    4. Esercizi Serie geometriche e telescopiche
  13. Successioni di funzioni
    1. Teoria Successioni di funzioni
    2. Esercizi Successioni di funzioni
  14. Serie di funzioni
    1. Teoria Serie di funzioni
    2. Esercizi Serie di funzioni
  15. Serie di potenze
    1. Teoria Serie di potenze
    2. Esercizi Serie di potenze
  16. Serie di Fourier
    1. Teoria Serie di Fourier
    2. Esercizi Serie di Fourier
  17. Trasformata di Fourier
    1. Teoria Trasformata di Fourier
    2. Esercizi Trasformata di Fourier
  18. Funzioni di più variabili
    1. Teoria Funzioni di più variabili
    2. Massimi e minimi liberi e vincolati
    3. Limiti in due variabili
    4. Integrali doppi
    5. Integrali tripli
    6. Integrali di linea di prima specie
    7. Integrali di linea di seconda specie
    8. Forme differenziali e campi vettoriali
    9. Teorema di Gauss-Green
    10. Integrali di superficie
    11. Flusso di un campo vettoriale
    12. Teorema di Stokes
    13. Teorema della divergenza
    14. Campi solenoidali
    15. Teorema del Dini
  19. Equazioni differenziali lineari e non lineari
    1. Teoria equazioni differenziali lineari e non lineari
    2. Equazioni differenziali lineari e non lineari del primo ordine omogenee
  20. Equazioni differenziali lineari
    1. Del primo ordine non omogenee
    2. Di ordine superiore al primo,a coefficienti costanti,omogenee
    3. Di ordine superiore al primo,a coefficienti costanti,non omogenee
    4. Di Eulero,di Bernoulli,di Clairaut,di Lagrange e di Abel
    5. Non omogenee avente per omogenea associata un’equazione di Eulero
    6. Sistemi di EDO
  21. Equazioni differenziali non lineari
    1. A variabili separabiliO
    2. A secondo membro omogeneo
    3. Del tipo y’=y(ax+by+c)
    4. Del tipo y’=y(ax+by+c)/(a’x+b’y+c’)
    5. Equazioni differenziali esatte
    6. Mancanti delle variabili x e y
    7. Cenni sullo studio di un’assegnata equazione differenziale non lineare
    8. Di Riccati
    9. Cambi di variabile: simmetrie di Lie
  22. Analisi complessa
    1. Fondamenti
    2. Funzioni olomorfe
    3. Integrale di Cauchy e applicazioni
    4. Teorema della curva di Jordan e teorema fondamentale dell’Algebra
    5. Teorema di inversione di Lagrange
    6. Teorema dei Residui
    7. Funzioni meromorfe
    8. Prodotti infiniti e prodotti di Weierstrass
    9. Continuazione analitica e topologia
    10. Teoremi di rigidità di funzioni olomorfe
    11. Trasformata di Mellin
  23. Equazioni alle derivate parziali
    1. Equazioni del primo ordine
    2. Equazioni del secondo ordine lineari
    3. Equazioni non-lineari
    4. Sistemi di PDE
  24. Funzioni speciali
    1. Funzione Gamma di Eulero
    2. Funzioni Beta,Digamma,Trigamma
    3. Integrali ellittici
    4. Funzioni di Bessel
    5. Funzione zeta di Riemann e funzioni L di Dirichlet
    6. Funzione polilogaritmo
    7. Funzioni ipergeometriche
  25. Analisi funzionale
    1. Misura e integrale di Lebesgue
    2. Spazi Lp,teoremi di completezza e compattezza
    3. Spazi di Hilbert,serie e trasformata di Fourier
    4. Teoria e pratica dei polinomi ortogonali
    5. Spazi di Sobolev
  26. Complementi
    1. Curiosità e approfondimenti
    2. Compiti di analisi
    3. Esercizi avanzati analisi
  27. Funzioni Convesse

 
 

Tutti gli esercizi di geometria

In questa sezione vengono raccolti molti altri esercizi che coprono tutti gli argomenti di geometria proposti all’interno del sito con lo scopo di offrire al lettore la possibilità di approfondire e rinforzare le proprie competenze inerenti a tali argomenti.

Strutture algebriche.


Algebra lineare.


Geometria analitica.


Geometria differenziale.


 
 

Risorse didattiche aggiuntive per approfondire la matematica

Leggi...

  • Math Stack Exchange – Parte della rete Stack Exchange, questo sito è un forum di domande e risposte specificamente dedicato alla matematica. È una delle piattaforme più popolari per discutere e risolvere problemi matematici di vario livello, dall’elementare all’avanzato.
  • Art of Problem Solving (AoPS) – Questo sito è molto noto tra gli studenti di matematica di livello avanzato e i partecipanti a competizioni matematiche. Offre forum, corsi online, e risorse educative su una vasta gamma di argomenti.
  • MathOverflow – Questo sito è destinato a matematici professionisti e ricercatori. È una piattaforma per domande di ricerca avanzata in matematica. È strettamente legato a Math Stack Exchange ma è orientato a un pubblico con una formazione più avanzata.
  • PlanetMath – Una comunità collaborativa di matematici che crea e cura articoli enciclopedici e altre risorse di matematica. È simile a Wikipedia, ma focalizzata esclusivamente sulla matematica.
  • Wolfram MathWorld – Una delle risorse online più complete per la matematica. Contiene migliaia di articoli su argomenti di matematica, creati e curati da esperti. Sebbene non sia un forum, è una risorsa eccellente per la teoria matematica.
  • The Math Forum – Un sito storico che offre un’ampia gamma di risorse, inclusi forum di discussione, articoli e risorse educative. Sebbene alcune parti del sito siano state integrate con altri servizi, come NCTM, rimane una risorsa preziosa per la comunità educativa.
  • Stack Overflow (sezione matematica) – Sebbene Stack Overflow sia principalmente noto per la programmazione, ci sono anche discussioni rilevanti di matematica applicata, specialmente nel contesto della scienza dei dati, statistica, e algoritmi.
  • Reddit (r/Math) – Un subreddit popolare dove si possono trovare discussioni su una vasta gamma di argomenti matematici. È meno formale rispetto ai siti di domande e risposte come Math Stack Exchange, ma ha una comunità attiva e molte discussioni interessanti.
  • Brilliant.org – Offre corsi interattivi e problemi di matematica e scienza. È particolarmente utile per chi vuole allenare le proprie capacità di problem solving in matematica.
  • Khan Academy – Una risorsa educativa globale con lezioni video, esercizi interattivi e articoli su una vasta gamma di argomenti di matematica, dalla scuola elementare all’università.






Document









Document



error: Il contenuto è protetto!!