Metoda de bisecție

Unele pasaje ale metodei de bisecție, aplicate intervalului [a ₁ ; b ₁ ]. Punctul roșu este rădăcina funcției.

În analiza numerică , metoda bisecției (sau algoritmul dihotomic) este cea mai simplă metodă numerică pentru a găsi rădăcinile unei funcții . Eficiența sa este slabă și are dezavantajul de a necesita ipoteze deosebit de restrictive. Cu toate acestea, are avantajul considerabil de a fi stabil cu fiecare ocazie și, prin urmare, de a garanta întotdeauna succesul operațiunii. ^[1]

Descriere

Având în vedere ecuația $f(x)=0$ ${\ displaystyle f (x) = 0}$ $f (x) = 0$ definit și continuă într-un interval $[a,b]$ ${\ displaystyle [a, b]}$ $[a, b]$ , astfel încât $f(a)\cdot f(b)<0$ ${\ displaystyle f (a) \ cdot f (b) <0}$ ${\ displaystyle f (a) \ cdot f (b) <0}$ , este apoi posibil să se calculeze o aproximare în $[a,b]$ ${\ displaystyle [a, b]}$ $[a, b]$ (vezi teorema zero ).

Procedăm împărțind intervalul în două părți egale și calculând valoarea funcției la punctul mediu al abscisei ${\frac {a+b}{2}}.$ ${\ displaystyle {\ frac {a + b} {2}}.}$ ${\ displaystyle {\ frac {a + b} {2}}.}$ Dacă se dovedește $f\left({\frac {a+b}{2}}\right)=0$ ${\ displaystyle f \ left ({\ frac {a + b} {2}} \ right) = 0}$ ${\ displaystyle f \ left ({\ frac {a + b} {2}} \ right) = 0}$ asa de ${\frac {a+b}{2}}$ ${\ displaystyle {\ frac {a + b} {2}}}$ ${\ frac {a + b} {2}}$ este rădăcina căutată; altfel între cele două intervale $\left[a,{\frac {a+b}{2}}\right]$ ${\ displaystyle \ left [a, {\ frac {a + b} {2}} \ right]}$ ${\ displaystyle \ left [a, {\ frac {a + b} {2}} \ right]}$ Și $\left[{\frac {a+b}{2}},b\right]$ ${\ displaystyle \ left [{\ frac {a + b} {2}}, b \ right]}$ ${\ displaystyle \ left [{\ frac {a + b} {2}}, b \ right]}$ se alege cel la extremele căruia funcția își asumă valori de semn opus. Procedura de înjumătățire se repetă pentru acest interval. Continuând astfel obținem o succesiune de intervale $[a_{1},b_{1}],[a_{2},b_{2}],\ldots ,[a_{n},b_{n}],\ldots ,$ ${\ displaystyle [a_ {1}, b_ {1}], [a_ {2}, b_ {2}], \ ldots, [a_ {n}, b_ {n}], \ ldots,}$ ${\ displaystyle [a_ {1}, b_ {1}], [a_ {2}, b_ {2}], \ ldots, [a_ {n}, b_ {n}], \ ldots,}$ încapsulat , adică fiecare inclus în cel precedent. Aceste intervale au ca amplitudini $b_{n}-a_{n}={\frac {b-a}{2^{n}}}$ ${\ displaystyle b_ {n} -a_ {n} = {\ frac {ba} {2 ^ {n}}}}$ ${\ displaystyle b_ {n} -a_ {n} = {\ frac {b-a} {2 ^ {n}}}}$ pentru $n=1,2,3,\ldots$ ${\ displaystyle n = 1,2,3, \ ldots}$ ${\ displaystyle n = 1,2,3, \ ldots}$

Valori $a_{i}$ ${\ displaystyle a_ {i}}$ $la}$ sunt valori aproximative până la rădăcină, valorile lui $b_{i}$ ${\ displaystyle b_ {i}}$ $bi}$ în schimb, acestea sunt valorile rădăcinii aproximate de exces. The $a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ formează o secvență crescătoare limitată și i $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$ formează o secvență descrescătoare limitată. Cele două secvențe admit aceeași limită care este rădăcina ecuației examinate.

Ca o aproximare a rădăcinii $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ considerăm punctul de mijloc al intervalelor, adică $c_{n}={\frac {a_{n}+b_{n}}{2}},$ ${\ displaystyle c_ {n} = {\ frac {a_ {n} + b_ {n}} {2}},}$ ${\ displaystyle c_ {n} = {\ frac {a_ {n} + b_ {n}} {2}},}$ pentru $n=1,2,\ldots$ ${\ displaystyle n = 1,2, \ ldots}$ ${\ displaystyle n = 1,2, \ ldots}$

Algoritmul este oprit când $f(c_{n})$ ${\ displaystyle f (c_ {n})}$ ${\ displaystyle f (c_ {n})}$ este suficient de aproape de și / sau când lățimea intervalului $[a_{n},b_{n}]$ ${\ displaystyle [a_ {n}, b_ {n}]}$ ${\ displaystyle [a_ {n}, b_ {n}]}$ este mai puțin decât o anumită toleranță $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ . Deci, ca o estimare a $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ în cele din urmă vom avea o anumită $c_{n}.$ ${\ displaystyle c_ {n}.}$ ${\ displaystyle c_ {n}.}$ Se arată cu ușurință că pentru greșeala comisă $e_{n}$ ${\ displaystyle e_ {n}}$ $e_n$ urmează următoarea relație:

|e_{n}|=|c_{n}-\alpha |\leq {\frac {b-a}{2^{n+1}}}.

{\ displaystyle | e_ {n} | = | c_ {n} - \ alpha | \ leq {\ frac {ba} {2 ^ {n + 1}}}.}

{\ displaystyle | e_ {n} | = | c_ {n} - \ alpha | \ leq {\ frac {b-a} {2 ^ {n + 1}}}.}

Un corolar important este acela

\lim _{n\to \infty }|e_{n}|=0,

{\ displaystyle \ lim _ {n \ to \ infty} | e_ {n} | = 0,}

{\ displaystyle \ lim _ {n \ to \ infty} | e_ {n} | = 0,}

de aceea convergența metodei este globală .

Dacă avem nevoie $|e_{n}|\leq \varepsilon$ ${\ displaystyle | e_ {n} | \ leq \ varepsilon}$ ${\ displaystyle | e_ {n} | \ leq \ varepsilon}$ obținem următoarea condiție pentru $n$ ${\ displaystyle n}$ $n$ :

n\geq log_{2}{\frac {b-a}{\varepsilon }}-1.

{\ displaystyle n \ geq log_ {2} {\ frac {ba} {\ varepsilon}} - 1.}

{\ displaystyle n \ geq log_ {2} {\ frac {b-a} {\ varepsilon}} - 1.}

Fiind $log_{2}10\approx 3,32$ ${\ displaystyle log_ {2} 10 \ aproximativ 3.32}$ ${\ displaystyle log_ {2} 10 \ aproximativ 3.32}$ este nevoie de mai mult de trei bisecții în medie pentru a îmbunătăți precizia rădăcinii cu o cifră semnificativă, astfel încât convergența este lentă. Mai mult, reducerea erorii la fiecare pas nu este monotonă, adică nu înseamnă neapărat asta $|e_{n+1}|<|e_{n}|$ ${\ displaystyle | e_ {n + 1} | <| e_ {n} |}$ ${\ displaystyle | e_ {n + 1} | <| e_ {n} |}$ pentru fiecare $n=1,2,\ldots$ ${\ displaystyle n = 1,2, \ ldots}$ ${\ displaystyle n = 1,2, \ ldots}$ Prin urmare, nu este posibil să se definească o ordine reală de convergență pentru această metodă.

Algoritm

Pseudocodul acestei metode este furnizat mai jos: ^[2]

 N ← 1
În timp ce N ≤ NMAX # se limitează la iterații pentru a preveni bucle infinite
  c ← ( a + b ) / 2 # nou punct mediu
  Dacă f ( c ) = 0 sau ( b - a ) / 2 < TOL atunci # soluție găsită
    Ieșire ( c )
    Stop
  EndIf
  N ← N + 1 # creșterea contorului
  Dacă semn ( f ( c )) = semn ( f ( a )) atunci a ← c altul b ← c # interval nou
EndWhile
Ieșire („Operațiunea nu a reușit.”) # A depășit numărul maxim de iterații

Exemplu

Puteți utiliza metoda bisecției pentru a găsi rădăcina următorului polinom:

f(x)=x^{3}-x-2\,.

{\ displaystyle f (x) = x ^ {3} -x-2 \,.}

{\ displaystyle f (x) = x ^ {3} -x-2 \,.}

Mai întâi trebuie să identificăm două numere $la$ ${\ displaystyle a}$ $la$ Și $b$ ${\ displaystyle b}$ $b$ astfel încât $f(a)$ ${\ displaystyle f (a)}$ $face)$ Și $f(b)$ ${\ displaystyle f (b)}$ $f (b)$ au un semn discordant. Pentru funcția de mai sus, $a=1$ ${\ displaystyle a = 1}$ ${\ displaystyle a = 1}$ Și $b=2$ ${\ displaystyle b = 2}$ ${\ displaystyle b = 2}$ îndeplinesc acest criteriu, ca

f(1)=(1)^{3}-(1)-2=-2

{\ displaystyle f (1) = (1) ^ {3} - (1) -2 = -2}

{\ displaystyle f (1) = (1) ^ {3} - (1) -2 = -2}

Și

f(2)=(2)^{3}-(2)-2=+4\,.

{\ displaystyle f (2) = (2) ^ {3} - (2) -2 = + 4 \,.}

{\ displaystyle f (2) = (2) ^ {3} - (2) -2 = + 4 \,.}

Deoarece funcția este continuă, ipotezele teoremei Bolzano sunt respectate și trebuie să existe o rădăcină între $\left[1,2\right]$ ${\ displaystyle \ left [1,2 \ right]}$ ${\ displaystyle \ left [1,2 \ right]}$ .

Fiind extremele domeniului pe care l-am considerat $a_{1}=1$ ${\ displaystyle a_ {1} = 1}$ ${\ displaystyle a_ {1} = 1}$ Și $b_{1}=2$ ${\ displaystyle b_ {1} = 2}$ ${\ displaystyle b_ {1} = 2}$ , punctul de mijloc va fi:

c_{1}={\frac {2+1}{2}}=1,5

{\ displaystyle c_ {1} = {\ frac {2 + 1} {2}} = 1,5}

{\ displaystyle c_ {1} = {\ frac {2 + 1} {2}} = 1,5}

Valoarea funcției la punctul mediu va fi $f(c_{1})=(1,5)^{3}-(1,5)-2=-0,125$ ${\ displaystyle f (c_ {1}) = (1,5) ^ {3} - (1,5) -2 = -0,125}$ ${\ displaystyle f (c_ {1}) = (1,5) ^ {3} - (1,5) -2 = -0,125}$ . Fiind $f(c_{1})$ ${\ displaystyle f (c_ {1})}$ ${\ displaystyle f (c_ {1})}$ negativ, $a=1$ ${\ displaystyle a = 1}$ ${\ displaystyle a = 1}$ se înlocuiește cu $a=1,5$ ${\ displaystyle a = 1.5}$ ${\ displaystyle a = 1.5}$ pentru următoarea iterație astfel încât $f(a)$ ${\ displaystyle f (a)}$ ${\ displaystyle f (a)}$ Și $f(b)$ ${\ displaystyle f (b)}$ ${\ displaystyle f (b)}$ au un semn discordant. Odată cu continuarea acestui proces, intervalul dintre $la$ ${\ displaystyle a}$ $la$ Și $b$ ${\ displaystyle b}$ $b$ va deveni drastic din ce în ce mai mic, până când converge în rădăcina căutată. În acest sens, consultați următorul tabel:

Repetare	$a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$	$b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$	$c_{n}$ ${\ displaystyle c_ {n}}$ $c_ {n}$	$f(c_{n})$ ${\ displaystyle f (c_ {n})}$ ${\ displaystyle f (c_ {n})}$
1	1	2	1.5	−0,125
2	1.5	2	1,75	1.6093750
3	1.5	1,75	1.625	0,6660156
4	1.5	1.625	1,5625	0,2521973
5	1.5	1,5625	1.5312500	0,0591125
6	1.5	1.5312500	1.5156250	−0,0340538
7	1.5156250	1.5312500	1.5234375	0,0122504
8	1.5156250	1.5234375	1.5195313	−0.0109712
9	1.5195313	1.5234375	1.5214844	0,0006222
10	1.5195313	1.5214844	1.5205078	−0,0051789
11	1.5205078	1.5214844	1.5209961	−0,0022794
12	1.5209961	1.5214844	1.5212402	−0.0008289
13	1.5212402	1.5214844	1.5213623	−0.0001034
14	1.5213623	1.5214844	1.5214233	0,0002594
15	1.5213623	1.5214233	1.5213928	0,0000780

După treisprezece iterații este evident că convergența are loc la 1.521 ca rădăcină a polinomului.

Notă

^ Burden & Faires 1985, p. 35.
^ Burden & Faires 1985, p. 29.

Bibliografie

Burden, Richard L.; Faires, J. Douglas (1985), „2.1 The Bisection Algorithm”, Analiza numerică (ediția a treia), PWS Publishers, ISBN 0-87150-857-5 .

Elemente conexe

Alte proiecte

Wikiversitatea conține resurse privind metoda bisecării

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Burden & Faires 1985, p. 35.

[2] Burden & Faires 1985, p. 29.

[1]

[2]