Delingsmetode - Bisection method

Noen få trinn av skjæringsmetoden brukt over startområdet [a ₁ ; b ₁ ]. Den større røde prikken er roten til funksjonen.

I matematikk , at halverings metode er en rot-finne metode som gjelder for alle kontinuerlige funksjoner for hvilke man vet to verdier med motsatt fortegn. Metoden består av gjentatte halverer den intervallet definert av disse verdiene, og deretter velge subintervallet, hvor funksjonen endrer fortegn, og derfor må inneholde en rot . Det er en veldig enkel og robust metode, men den er også relativt treg. På grunn av dette brukes det ofte for å få en grov tilnærming til en løsning som deretter brukes som utgangspunkt for raskere konvergerende metoder. Metoden kalles også intervallhalvingsmetoden , den binære søkemetoden eller dikotomimetoden .

For polynomer finnes det mer utførlige metoder for å teste eksistensen av en rot i et intervall ( Descartes tegnregel , Sturms teorem , Budans teorem ). De gjør det mulig å utvide biseksjonsmetoden til effektive algoritmer for å finne alle virkelige røtter til et polynom; se Real-root isolasjon .

Metoden

Metoden er anvendelig for numerisk løsning av ligningen f ( x ) = 0 for den reelle variabelen x , hvor f er en kontinuerlig funksjon definert på et intervall [ a ,  b ] og hvor f ( a ) og f ( b ) har motsatte tegn . I dette tilfellet sies a og b å brakette en rot siden den mellomliggende verdisetningen , den kontinuerlige funksjonen f må ha minst en rot i intervallet ( a , b ).

Ved hvert trinn deler metoden intervallet i to deler / halvdeler ved å beregne midtpunktet c = ( a + b ) / 2 av intervallet og verdien av funksjonen f ( c ) på det punktet. Med mindre c i seg selv er en rot (som er svært usannsynlig, men mulig), er det nå bare to muligheter: enten f ( a ) og f ( c ) har motsatte tegn og braketter en rot, eller f ( c ) og f ( b ) ha motsatte tegn og fest en rot. Metoden velger delintervallet som garantert er en parentes som det nye intervallet som skal brukes i neste trinn. På denne måten reduseres et intervall som inneholder et null av f i bredden med 50% ved hvert trinn. Prosessen fortsetter til intervallet er tilstrekkelig lite.

Eksplisitt, hvis f ( a ) og f ( c ) har motsatte tegn, setter metoden c som den nye verdien for b , og hvis f ( b ) og f ( c ) har motsatte tegn, setter metoden c som den nye a . (Hvis f ( c ) = 0 så kan c tas som løsningen og prosessen stopper.) I begge tilfeller har den nye f ( a ) og f ( b ) motsatte tegn, så metoden gjelder for dette mindre intervallet .

Iterasjonsoppgaver

Inngangen for metoden er en kontinuerlig funksjon f , et intervall [ a , b ], og funksjonsverdiene f ( a ) og f ( b ). Funksjonsverdiene har motsatt fortegn (det er minst ett nullovergang innenfor intervallet). Hver iterasjon utfører disse trinnene:

1. Beregn c , midtpunktet for intervallet, c = a + b/2.
2. Beregn funksjonsverdien ved midtpunktet, f ( c ).
3. Hvis konvergens er tilfredsstillende (det vil si c - a er tilstrekkelig liten, eller | f ( c ) | er tilstrekkelig liten), returnerer du c og slutter å gjenta.
4. Undersøk tegnet på f ( c ) og erstatt enten ( a , f ( a )) eller ( b , f ( b )) med ( c , f ( c )) slik at det er et nullovergang innenfor det nye intervallet.

Når du implementerer metoden på en datamaskin, kan det være problemer med begrenset presisjon, så det er ofte ytterligere konvergens -tester eller grenser for antall iterasjoner. Selv om f er kontinuerlig, kan endelig presisjon forhindre at en funksjonsverdi noensinne er null. Tenk for eksempel på f ( x ) = x - π ; det vil aldri være en endelig representasjon av x som gir null. I tillegg er forskjellen mellom a og b begrenset av flytpunktets presisjon; dvs. ettersom forskjellen mellom a og b avtar, vil midtpunktet til [ a ,  b ] på et tidspunkt være numerisk identisk med (innenfor flytende presisjon på) enten a eller b .

Algoritme

Metoden kan skrives i pseudokode som følger:

INPUT: Function f, 
       endpoint values a, b, 
       tolerance TOL, 
       maximum iterations NMAX
CONDITIONS: a < b, 
            either f(a) < 0 and f(b) > 0 or f(a) > 0 and f(b) < 0
OUTPUT: value which differs from a root of f(x) = 0 by less than TOL
 
N ← 1
while N ≤ NMAX do // limit iterations to prevent infinite loop
    c ← (a + b)/2 // new midpoint
    if f(c) = 0 or (b – a)/2 < TOL then // solution found
        Output(c)
        Stop
    end if
    N ← N + 1 // increment step counter
    if sign(f(c)) = sign(f(a)) then a ← c else b ← c // new interval
end while
Output("Method failed.") // max number of steps exceeded

Eksempel: Finne roten til et polynom

Anta at biseksjonsmetoden brukes til å finne en rot av polynomet

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

Først to tall og må finnes slik at og har motsatte tegn. For ovennevnte funksjon, og tilfredsstille dette kriteriet, som ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle f (a)}$${\ displaystyle f (b)}$${\ displaystyle a = 1}$${\ displaystyle b = 2}$

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

og

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

Fordi funksjonen er kontinuerlig, må det være en rot innenfor intervallet [1, 2].

I den første iterasjonen er sluttpunktene for intervallet som braketten for roten er, og så er midtpunktet ${\ displaystyle a_ {1} = 1}$${\ displaystyle b_ {1} = 2}$

${\ displaystyle c_ {1} = {\ frac {2+1} {2}} = 1.5}$

Funksjonsverdien på midtpunktet er . Fordi er negativ, erstattes med for neste iterasjon for å sikre det og ha motsatte tegn. Etter hvert som dette fortsetter, vil intervallet mellom og bli stadig mindre, og konvergerer på roten til funksjonen. Se dette skje i tabellen nedenfor. ${\ displaystyle f (c_ {1}) = (1.5)^{3}-(1.5) -2 = -0.125}$${\ displaystyle f (c_ {1})}$${\ displaystyle a = 1}$${\ displaystyle a = 1.5}$${\ displaystyle f (a)}$${\ displaystyle f (b)}$${\ displaystyle a}$${\ displaystyle b}$

Iterasjon	${\ displaystyle a_ {n}}$	${\ displaystyle b_ {n}}$	${\ displaystyle 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
1. 3	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

Etter 13 iterasjoner blir det tydelig at det er en konvergens til omtrent 1.521: en rot for polynomet.

Analyse

Metoden vil garantert konvergere til en rot av f hvis f er en kontinuerlig funksjon på intervallet [ a , b ] og f ( a ) og f ( b ) har motsatte tegn. Den absolutte feilen halveres ved hvert trinn, slik at metoden konvergerer lineært . Spesielt hvis c ₁ =a + b/2er midtpunktet for det opprinnelige intervallet, og c _n er midtpunktet for intervallet i det n. trinnet, så er forskjellen mellom c _n og en løsning c begrenset av

${\ displaystyle | c_ {n} -c | \ leq {\ frac {| ba |} {2^{n}}}.}$

Denne formelen kan brukes til på forhånd å bestemme en øvre grense for antall iterasjoner som biseksjonsmetoden trenger for å konvergere til en rot til innenfor en viss toleranse. Antallet n av iterasjoner som trengs for å oppnå en nødvendig toleranse ε (det vil si en feil garantert å være høyest ε), er begrenset av

${\ displaystyle n \ leq n_ {1/2} \ equiv \ left \ lceil \ log _ {2} \ left ({\ frac {\ epsilon _ {0}} {\ epsilon}} \ right) \ right \ rceil ,}$

hvor den opprinnelige brakettstørrelsen og den nødvendige parentesstørrelsen Hovedmotivasjonen for å bruke biseksjonsmetoden er at over settet med kontinuerlige funksjoner, kan ingen annen metode garantere å produsere et estimat c _n til løsningen c som i verste fall har en absolutt feil med mindre enn n _1/2 iterasjoner. Dette er også sant under flere vanlige forutsetninger om funksjon f og oppførselen til funksjonen i nærheten av roten. ${\ displaystyle \ epsilon _ {0} = | ba |}$${\ displaystyle \ epsilon \ leq \ epsilon _ {0}.}$${\ displaystyle \ epsilon}$

Til tross for at biseksjonsmetoden er optimal med hensyn til ytelse i verste fall under absolutte feilkriterier, er den suboptimal med hensyn til gjennomsnittlig ytelse under standardforutsetninger så vel som asymptotisk ytelse . Populære alternativer til halveringsmetoden, for eksempel secant-metoden , Ridders metode eller Brents metode (blant annet), fungerer vanligvis bedre siden de bytter ut verste tilfelle for å oppnå høyere konvergensordner til roten. Og en streng forbedring av halveringsmetoden kan oppnås med en høyere konvergensrekkefølge uten å bytte ut de verste tilfellene med ITP-metoden .

Se også

• Binær søkealgoritme
• Lehmer – Schur -algoritme , generalisering av biseksjonsmetoden i det komplekse planet
• Nested intervaller

Referanser

• Burden, Richard L .; Faires, J. Douglas (1985), "2.1 The Bisection Algorithm", Numerical Analysis (3. utg.), PWS Publishers, ISBN 0-87150-857-5

Videre lesning

• Corliss, George (1977), "Hvilken rot finner biseksjonsalgoritmen?", SIAM Review , 19 (2): 325–327, doi : 10.1137/1019044 , ISSN  1095-7200
• Kaw, Autar; Kalu, Egwu (2008), Numerical Methods with Applications (1. utg.), Arkivert fra originalen 2009-04-13

Eksterne linker

• Weisstein, Eric W. "Biseksjon" . MathWorld .
• Halveringsmetode Notes, PPT, Mathcad, Maple, Matlab, Mathematica fra Holistic Numerical Methods Institute