Intervallhalveringsmetoden

[kjey]

Driver å titter på numeriske metoder for å finne røtter til funksjoner, og da spesielt intervallhalveringsmetoden som kort sagt går ut på å minske et intervall i en funksjon helt til man kommer fra til en "god nok" tilnærming.

Uansett, selve teknikken for å minske intervallet er jo ganske greit, men man er jo også interessert i hvor stor feil tilnærmingen kan lage, og det er der jeg sitter littegran fast. Se på s.209 her: http://www.uio.no/studier/emner/matnat/ ... /zeros.pdf

Der står det en teknikk ( ved hjelp av observasjon 10.5) for å vite at tilnærmingen din er så god som du vil ha den. Problemet mitt oppstod i eksempel 10.6 hvor forfatteren skriver at

[tex]\frac{\ln{(b-a)} - \ln{\epsilon}} {\ln{2}} - 1 = \frac{10\ln{10}} {\ln{2}} - 1[/tex].

Er det noen som kan forklare hvordan man kommer fram til likheten ovenfor?

På forhånd takk!

[Gnome]

Hei!

Jeg prøvde meg på en utredelse, som burde vise det

Vi vet at størrelsen på intervallet vårt er lik [tex]\frac{|b-a|}{2^{n+1}[/tex]

der n er antall iterasjoner (halveringer) og b og a er start-maks og min på intervallet.

Og ettersom den største feilen vi kan få etter n interasjoner er størrelsen på intervallet vi får, vil det stemme at:

[tex]\frac{|b-a|}{2^{n+1}} \leq \epsilon[/tex]

Ønsket vårt er jo å isolere n'en, slik at vi får et uttrykk for hvor mange iterasjoner vi trenger før vi er fornøyde:

Så jeg starter med å gange med [tex]2^{n+1}[/tex] på begge sider:

[tex]|b-a| \leq \epsilon \cdot 2^{n+1}[/tex]

Ta logaritmen på begge sider, og bruke regneregel for å separere uttrykkene på høyresiden.

Etter dette er det en rimelig grei utregning

[tex]ln(|b-a|) \leq ln\epsilon + ln(2^{n+1})[/tex]

[tex]ln(|b-a|) \leq ln\epsilon + (n+1)ln2[/tex]

[tex]ln(|b-a|) - ln\epsilon \leq (n+1)ln2[/tex]

[tex]\frac{ln(|b-a|) - ln\epsilon}{ln2} \leq n+1[/tex]

[tex]\frac{ln(|b-a|) - ln\epsilon}{ln2} -1 \leq n[/tex]

[kjey]

Beklager hvis jeg var litt uklar, var nemlig ikke heelt det jeg lurte på, men veldig nyttig utledning, takk! (lurte faktisk på hvor formelen kom fra, så var bra at du tok det opp) Det som forvirrer meg mest er hvor [tex]10\ln{10}[/tex] kommer fra? Altså skal jeg putte inn en spesiell verdi for [tex]\epsilon[/tex]? I så fall, hvor kommer denne verdien fra?

[Gnome]

Hei igjen!

Hvis du prøver å sette inn verdiene i formelen, finner du fort ut hvorfor det blir som det blir. Hvis vi setter [tex]\epsilon = 10^{-10}[/tex] og intervallet [a, b] til å være [1, 2], får vi følgende:

[tex]\frac{ln(2-1) - ln(10^{-10})}{ln2} - 1[/tex]

Dette blir:

[tex]\frac{-ln(10^{-10})}{ln2} - 1[/tex]

Vi flytter ned potensen i logaritmeuttrykket og får:

[tex]\frac{10ln10}{ln2} - 1[/tex]

[tex]\epsilon[/tex] er en betegnelse på feilmargin. I dette tilfellet setter vi epsilon til å være den minste feilen vi tillater. Uttrykket i boka sier jo da at hvis man forlanger en feilmargin mindre enn [tex]10^{-10}[/tex] må man gjøre minst 33 utregninger.

Epsilonen er altså et tall vi bestemmer selv, utifra hvor høy "kvalitet" vi vil ha på beregningene våre.

[kjey]

Aha, så klart! Rart det stod så lite detaljert... Tusen takk for hjelp!