Metoda bisecției

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 23 august 2021; verificările necesită 5 modificări .

Metoda bisecției sau metoda împărțirii unui segment la jumătate este cea mai simplă metodă numerică de rezolvare a ecuațiilor neliniare de forma f ( x )=0. Se presupune doar continuitatea funcției f ( x ). Căutarea se bazează pe teorema valorii intermediare .

Motivație

Algoritmul se bazează pe următorul corolar din teorema Bolzano-Cauchy :

Fie o funcție continuă , atunci, dacă , atunci . $f(x)\in \mathrm {C} ([a,\;b])$ $semn(f(a))\neq semn(f(b))$ $\există c\în [a,\;b]:\;f(c)=0$

Astfel, dacă căutăm zero, atunci la capetele segmentului, funcția trebuie să fie de semne opuse. Împărțiți segmentul în jumătate și luați-l pe cel al jumătăților, la capetele cărora funcția încă mai ia valorile semnelor opuse. Dacă valoarea funcției la punctul de mijloc s-a dovedit a fi zero dorit, atunci procesul se termină.

Precizia calculului este stabilită într-unul din două moduri:

$\varepsilon _{{f(x)}}$ de-a lungul axei , care este mai aproape de condiția din descrierea algoritmului; sau $y$ $f(x)=0$
$\varepsilon _{x}$ , de-a lungul axei , ceea ce poate fi convenabil în unele cazuri. $X$

Procedura trebuie continuată până când se obține precizia specificată.

Pentru a căuta o valoare arbitrară, este suficient să scazi valoarea dorită din valoarea funcției și să cauți zero al funcției rezultate.

Descrierea algoritmului

Problema este de a găsi rădăcinile ecuației neliniare

f(x)=0.\qquad (1)

Pentru a începe iterațiile, este necesar să cunoașteți intervalul de valori , la capetele cărora funcția ia valori de semne opuse. $[x_{L},x_{R}]$ $X$

Opusul semnelor valorilor funcției de la capetele segmentului poate fi determinat în mai multe moduri. Una dintre multe dintre aceste moduri este de a înmulți valorile funcției la capetele segmentului și de a determina semnul produsului comparând rezultatul înmulțirii cu zero:

f(x_{L})\cdot f(x_{R})<0,\qquad (2.1)

în calculul real, acest mod de a verifica semnele opuse pe funcțiile abrupte duce la depășire prematură .

Pentru a elimina depășirea și a reduce costurile de timp, adică pentru a crește performanța, pe unele sisteme software și computerizate, opusul semnelor valorilor funcției de la capetele segmentului trebuie determinat prin formula:

semn(f(x_{L}))\neq semn(f(x_{R})),\qquad (2.2)

întrucât o operație de comparare a două semne a două numere necesită mai puțin timp decât două operații: înmulțirea a două numere (în special virgulă mobilă și lungimea dublă) și compararea rezultatului cu zero. Cu această comparație, valorile funcției în puncte și nu pot fi calculate, este suficient să calculați doar semnele funcției în aceste puncte, ceea ce necesită mai puțin timp de calculator. $f(x)$ $x_{L}$ $x_{R}$ $f(x)$

Din continuitatea funcției și a condiției (2.2) rezultă că există cel puțin o rădăcină a ecuației pe interval (în cazul unei funcții nemonotone , funcția are mai multe rădăcini, iar metoda conduce la găsirea uneia dintre ei). $f(x)$ $[x_{L},x_{R}]$ $f(x)$

Găsiți valoarea în mijlocul segmentului: $X$

x_{M}=(x_{L}+x_{R})/2,\qquad (3)

în calculele efective, pentru a reduce numărul de operații, la început, în afara buclei, se calculează lungimea segmentului după formula:

x_{D}=(x_{R}-x_{L}),

iar în buclă, lungimea următoarelor noi segmente este calculată conform formulei: iar noul punct de mijloc conform formulei: $x_{D}=x_{D}/2$

x_{M}=x_{L}+x_{D}.

Calculați valoarea funcției din mijlocul segmentului : $f(x_{M})$ $x_M$

Dacă sau, în calculele reale, , unde este precizia specificată de-a lungul axei , atunci rădăcina este găsită. $f(x_{M})=0$ $|f(x_{M})|\leq \varepsilon _{{f(x)}}$ $\varepsilon _{{f(x)}}$ $y$
În caz contrar , sau, în calcule reale, , atunci împărțim segmentul în două segmente egale: și . $f(x_{M})\neq 0$ $|f(x_{M})|>\varepsilon _{{f(x)}}$ $[x_{L},x_{R}]$ $[x_{L},x_{M}]$ $[x_{M},x_{R}]$

Acum să găsim un nou segment pe care funcția își schimbă semnul:

Dacă valorile funcției de la capetele segmentului au semne opuse pe segmentul din stânga sau , atunci, respectiv, rădăcina se află în interiorul segmentului din stânga . Apoi luăm segmentul din stânga ca atribuire și repetăm procedura descrisă până când se atinge precizia necesară de-a lungul axei . $f(x_{L})\cdot f(x_{M})<0$ $semn(f(x_{L}))\neq semn(f(x_{M}))$ $[x_{L},x_{M}]$ $x_{R}=x_{M}$ $\varepsilon _{{f(x)}}$ $y$
În caz contrar, valorile funcției de la capetele segmentului au semne opuse pe segmentul din dreapta, sau , atunci, respectiv, rădăcina se află în interiorul segmentului din dreapta . Apoi luăm segmentul potrivit prin alocare și repetăm procedura descrisă până când se atinge precizia necesară de-a lungul axei . $f(x_{M})\cdot f(x_{R})<0$ $semn(f(x_{M}))\neq semn(f(x_{R}))$ $[x_{M},x_{R}]$ $x_{L}=x_{M}$ $\varepsilon _{{f(x)}}$ $y$

Pentru numărul de iterații , împărțirea în jumătate se efectuează o dată, astfel încât lungimea segmentului final este de ori mai mică decât lungimea segmentului original. $N$ $N$ $2^N$

Există o metodă similară, dar cu un criteriu de oprire a calculelor de-a lungul axei [1] , în această metodă, calculele continuă până când, după următoarea bisectie, noul segment este mai mare decât precizia specificată de-a lungul axei : . În această metodă, segmentul de pe axă poate atinge o valoare dată , iar valorile funcțiilor (în special cele abrupte) de pe axă pot fi foarte departe de zero, în timp ce cu funcții plate, această metodă duce la un număr mare de calcule inutile. $\varepsilon _{x}$ $X$ $X$ $(x_{R}-x_{L})>\varepsilon _{x}$ $X$ $\varepsilon _{x}$ $f(x)$ $y$ $f(x)$

În funcțiile discrete , și sunt numerele de elemente de matrice care nu pot fi fracționale, iar, în cazul celui de-al doilea criteriu de oprire, diferența nu poate fi mai mică de . $x_{L},x_{M}$ $x_{R}$ $(x_{R}-x_{L})$ $\varepsilon _{x}=1$

Pseudocod

;Lăsa

x n - începutul segmentului de-a lungul x;
x k este capătul segmentului de-a lungul x;
x i - mijlocul segmentului de-a lungul x;
eps y este precizia necesară a calculelor în y (dată o aproximare a intervalului [x n ; x k ] : x k - x n la zero).

Apoi algoritmul metodei bisecției poate fi scris în pseudocod după cum urmează:

Start.
Intrare x n , x k , eps y .
Dacă F(x n ) = 0, atunci Concluzie (rădăcina ecuației este x n ).
Dacă F(x k ) = 0, atunci Concluzie (rădăcina ecuației este x k ).
În timp ce x k - x n > eps y se repetă:
dx := (x k - x n )/2;
x i := x n + dx;
dacă sgn(F(x n )) ≠ sgn(F(x i )), atunci x k := x i;
altfel x n := x i .
sfârșitul repetă
Concluzie (Găsit rădăcina ecuației - x i cu o precizie de y - eps y ).
Sfârşit.

Găsirea valorii rădăcinii unei funcții discrete monotone

Căutarea valorii cele mai apropiate de rădăcină într-o funcție discretă monotonă dată într-un tabel și scrisă într-un tablou constă în împărțirea matricei în jumătate (în două părți), alegând din două părți noi partea în care valorile lui elementele matricei își schimbă semnul comparând semnele elementului din mijloc al matricei cu semnul valorii de limită și repetând algoritmul pentru jumătatea în care valorile elementelor matricei își schimbă semnul.

Fie variabilele leftBorder și rightBorder să conțină, respectiv, left- leftGran și right- rightGran a graniței matricei, în care se află aproximarea la rădăcină. Studiul începe cu împărțirea matricei în jumătate (în două părți) prin găsirea numărului elementului din mijloc al matricei mid .

Dacă semnele valorilor matricei [leftBorder] și array [middle] sunt opuse, atunci aproximarea la rădăcină este căutată în jumătatea stângă a matricei, adică valoarea rightBorder devine mijlocul și doar stânga jumătate din matrice este examinată la următoarea iterație. Dacă semnele matricei[leftBorder] și ale matricei[middle] sunt aceleași, atunci se efectuează tranziția la căutarea unei aproximări la rădăcina din jumătatea dreaptă a matricei, adică mijlocul devine valoarea variabilei leftBorder și numai jumătatea dreaptă a matricei este examinată la următoarea iterație. Astfel, în urma fiecărei verificări, zona de căutare este înjumătățită.

De exemplu, dacă lungimea matricei este de 1023, atunci după prima comparație, zona este restrânsă la 511 elemente, iar după a doua - la 255. Astfel. pentru a căuta o aproximare a rădăcinii într-o matrice de 1023 de elemente, 10 treceri (iterații) sunt suficiente.

Pseudocod :

leftBorder = levGran rightBorder = rightGran în timp ce ( rightBorder - leftBorder > 1 ) { lungimea segmentului \ u003d rightgrand - liongrand jumătate din linie = int ( lungimea liniei / 2 ) middle = leftBorder + jumătate din linie dacă ( semn ( matrice [ margine stângă ]) ≠ semn ( matrice [ mijloc ])) marginea dreapta = mijlocul altfel marginea stângă = mijloc } printf mijloc

Vezi și

Note

↑ Yu. Gubar, Curs „Introducere în modelarea matematică” Cursul 4: Metode numerice de rezolvare a ecuațiilor neliniare : Metoda semidiviziunii // Intuit.ru , 15/03/2007

Literatură

Volkov EA Capitolul 4. Metode de rezolvare a ecuațiilor și sistemelor neliniare. § 26. Metoda împărţirii în jumătate a unui segment // Metode numerice. - Manual. indemnizație pentru universități. - ed. a II-a, Rev. - M . : Nauka, 1987. - S. 190. - 248 p.
Burden, Richard L. & Faires, J. Douglas (1985), 2.1 The Bisection Algorithm , Numerical Analysis (ed. a treia), PWS Publishers, ISBN 0-87150-857-5 , < https://archive.org/details /numericalanalys00burd >

Link -uri

Metoda bisecției pe serverul de aplicații Mathcad.
Metoda bisectării Mathcad, Maple, Matlab, Mathematica
Utilizarea metodei Bisecției în programare Un program gratuit pentru calcularea punctului izoelectric .