<jupyter_start><jupyter_text>Halveringsmetoden--- Figur 1: *En gif som ilustrerer halveringsmetoden* Wikipedia**Halveringsmetoden** er en enkel numerisk metode for å finna et nullpunkt til ein funksjon. Vi finner altså en løsning på likninga $f(x) = 0$. For å bruka metoden må vi kjenne to punkter a og b som er slik at $f(a)$ og $f(b)$ har ulikt fortegn, og  funksjonen må være kontinuerlig i intervallet $[a,b]$. Vi startar med å finne midtpunktet m mellom $a$ og $b$. Hvis  $f(m)$ og $f(a)$ har ulikt fortegn så leter vi videre i intervallet $[a,m]$. Hvis ikke fortsetter vi med intervallet $[m,b]$. **Algoritme**1. Regn ut m, midtpunktet til intervallet $[a,b]$, $m = (a + b)/2$.2. Regn ut funksjonsverdien for midtpunktet, m, $f(m)$.3. Undersøk fortegnet til produktet $f(a) \cdot f(m)$ og erstatt b med m hvis produktet er negativ og a med m hvis det er positivt, slik at nullpunktet eksisterer i det nye intervallet.**Pseudokode:**``` Gitt funksjonen f med parametere a, b, og N. 	gjenta N ganger			Regne ut midt-verdien:		m = (a + b)/2			hvis f(m) = 0			avslutt			hvis f(a)・f(m) < 0			b = m		ellers			a = m```**Flytskjema****Biblioteker**<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
%config InlineBackend.figure_format = 'svg'<jupyter_output><empty_output><jupyter_text>Implementasjon av halveringsmetoden---<jupyter_code>def halveringsmetoden(f, a, b, N):
    m_list = []; 
    for n in range(N):
        m = (a + b)/2
        m_list.append(m);

        if f(m) == 0:
            break
        elif f(a)*f(m) < 0:
            b = m
        else:
            a = m
        
    return m, m_list<jupyter_output><empty_output><jupyter_text>Noen eksempler--- Eksempel 1 **Løs likningen, $f(x)=2x-4=0$, numerisk.**Vi starter med å definere $f(x)=2x-4$<jupyter_code>def f(x):
    return 2*x-4<jupyter_output><empty_output><jupyter_text>Løser likningen $f(x)=0$ ved hjelp av halveringsmetodenFor å bestemme intervallet vi skal lete i tegner vi først grafen:<jupyter_code>x = np.linspace(-5,8,1000) # 1000 x-verdier fra -6 til 6
plt.xlabel('$x$') # Merker x-aksen
plt.ylabel('$f(x)$') # Merker y-aksen
plt.plot(x, f(x), label='$f(x)=2x-4$') # Tegner f(x) 
plt.legend() # Infoboksen øverst i hjørnet. Bruker data fra label
plt.show()<jupyter_output><empty_output><jupyter_text>Vi bestemmer et intervall nullpunktet ligger innenfor, $$x\in[-3, 5]$$og setter $a=-3$ og $b=5$.Maks antall iterasjoner setter vi til 10<jupyter_code>x, steg = halveringsmetoden(f, -3, 5, 10)<jupyter_output><empty_output><jupyter_text>Skriver ut løsningen til likningen<jupyter_code>print(f'x = {x:.4f}')<jupyter_output>x = 2.0000<jupyter_text>Ser vi på stegene til m<jupyter_code>print(steg)<jupyter_output>[1.0, 3.0, 2.0]<jupyter_text>```pythonhalveringsmetoden(f, -3, 5, 8)```Steg 1:$a = -3$ og $b = 5$ så blir$m = \frac{-3 + 5}{2} = \frac{2}{2} = 1$Steg 2:siden $f(-3)\cdot f(1) = -10 \cdot (-2) = 20 > 0$setter vi $a = m = 1$som fører til at $m = 3$Steg 3:siden $f(1)\cdot f(3) = -2 \cdot (2) = -4 < 0$setter vi $b = m = 3$som fører til at $m = 2$siden $f(2)=0$ så avslutter vi Likningen $f(x)=2x-4=0$ har løsningen: $x \approx 2.0000$  Eksempel 2--- **Løs likningen, $f(x)=x^2-16=0$, numerisk.**Vi starter med å definere $f(x)=x^2-16$<jupyter_code>def g(x):
    return x**2 - 16<jupyter_output><empty_output><jupyter_text>Det er lurt å tegne grafen til funksjonen før vi bestemmer området vi skal lete etter nullpunktene.<jupyter_code>x = np.linspace(-6,6,1000) # 1000 x-verdier fra -6 til 6
plt.xlabel('$x$') # Merker x-aksen
plt.ylabel('$g(x)$') # Merker y-aksen
plt.plot(x, g(x), label='$g(x)=x^2-16$') # Tegner g(x) 
plt.legend() # Infoboksen øverst i hjørnet. Bruker data fra label
plt.show()<jupyter_output><empty_output><jupyter_text>Vi ser at $g(x)$ har 2 nullpunkt. Algoritmen vi har brukt finner kun ett nullpunkt. Derfor må vi bestemme et passende intervall for hvert av nullpunktene.Det første nullpunktet finner vi mellom -6 og 0<jupyter_code>x, steg = halveringsmetoden(g, -6, 0, 18)
print(f'x_1 = {x:.4f}')<jupyter_output>x_1 = -4.0000<jupyter_text>Det andre nullpunktet ligger mellom 0 og 6<jupyter_code>x, steg = halveringsmetoden(g, 0, 6, 17)
print(f'x_2 = {x:.4f}')<jupyter_output>x_2 = 4.0000<jupyter_text>Likningen $f(x)=x^2-16=0$ har løsningene:$$x_1 \approx -4.0000 \wedge x_2 \approx 4.0000$$ Plot som viser tilnærmelsen til nullpunktet for hver iterasjon.<jupyter_code>plt.xlabel('$n$') # Merker x-aksen
plt.ylabel('Nullpunkt, $x_2$') # Merker y-aksen
plt.plot(steg, 'r', label='Tilnærmingsverdi for det ene nullpunktet') # Tegner m i de ulike stegene 
plt.legend() # Infoboksen øverst i hjørnet. Bruker data fra label
plt.show()<jupyter_output><empty_output><jupyter_text>Vi ser at algoritmen kommer raskt frem til en god tilnærming til nullpunktet  Eksempel 3--- **Løs likningen, $h(x) = 1.3^x + x^2 − x − 4=0$, numerisk.**Grunnen til at vi løser likninger numerisk er fordi de ikke lar seg løse eksakt.Her ser vi et eksempel på deg i CAS i GeoGebraVi starter med å definere $h(x) = 1.3^x + x^2 − x − 4$<jupyter_code>def h(x):
    return 1.3**x + x**2 - x - 4<jupyter_output><empty_output><jupyter_text>Det er lurt å tegne grafen til funksjonen før vi bestemmer området vi skal lete etter nullpunktene.<jupyter_code>x = np.linspace(-2,3,1000)

plt.xlabel('$x$') # Merker x-aksen
plt.ylabel('$h(x)$') # Merker y-aksen
plt.plot(x, h(x), label='$h(x)= 1.3^x + x^2 − x − 4$') # Tegner g(x) 
plt.legend() # Infoboksen øverst i hjørnet. 
plt.show()
x, steg = halveringsmetoden(h, -2, 0, 17)
print(f'x_1 = {x:.4f}')
x, steg = halveringsmetoden(h, 0, 3, 17)
print(f'x_2 = {x:.4f}')<jupyter_output>x_2 = 2.0877<jupyter_text>Likningen $h(x) = 1.3^x + x^2 − x − 4=0$ løsningene:$$x_1 \approx -1.3854 \wedge x_2 \approx 2.0877$$I GeoGebra kan vi bruke NLøs hvis vi ønsker å løse likninger numerisk:Plot som viser hvordan algoritmen nærmer seg nullpunktet for hver iterasjon.<jupyter_code>plt.xlabel('$n$') # Merker x-aksen
plt.ylabel('Nullpunkt, $x_1$') # Merker y-aksen
plt.plot(steg, 'r', label='Tilnærmingsverdi for nullpunktet') # Stegene 
plt.legend() # Infoboksen øverst i hjørnet. Bruker data fra label
plt.show()<jupyter_output><empty_output><jupyter_text>HalveringsalgoritmefunksjonHalveringsmetoden uten return av liste med stegne og med en "default" verdi for NNår man kaller på funksjonen trenger man da bare de tre første argumentene.F.eks ```halveringsmetoden(f, -1, 2)``` hvis man skal finne nulpunktet til en funksjon $f$ i intervallet $x\in[-1, 2]$.<jupyter_code>def halveringsmetoden(f, a, b, N=17):
    for n in range(N):
        m = (a + b)/2
        if f(m) == 0:
            break
        elif f(a)*f(m) < 0:
            b = m
        else:
            a = m
        
    return m<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14696296296296296, 'fraction_numerical': 0.035555555555555556, 'mean_word_length': 4.3579365079365076, 'pattern_counts': {'":': 0, '<': 64, '<?xml version=': 0, '>': 61, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '16', 'dir': 'jupyter-structured-clean-dedup', 'id': '243053', 'license': 'MIT', 'n_tokens_mistral': 3132, 'n_tokens_neox': 2904, 'n_words': 776, 'path': 'undervisning/Halveringsmetoden.ipynb', 'repo_name': 'mareis/NTNU-Miniprosjekt', 'size': '6750'}