Newtons metode (R)

Newtons metode (R)#

Du bør være kjent med Numerisk derivasjon (R) før du starter her.

Newtons metode er en algoritme som kan finne nullpunkter for en funksjon.

Påminnelse: Finner vi nullpunkter, kan vi også løse likninger!

La oss si at vi har en likning

\(x^2 = 3x - 2\)

For å løse denne likningen kan vi enkelt skrive den om til

\(x^2 - 3x + 2 = 0\)

Deretter kan vi løse likningen ved å finne nullpunktene til funksjonen \(f(x)=x^2 - 3x + 2\)

Dersom vi kan finne nullpunkter, kan vi også løse likninger.

Newtons metode

Hvis man velger et punkt \(x_0\) i nærheten av nullpunktet til \(f(x)\), vil en bedre approksimasjon være gitt ved

\[x_{n+1}=x_n - \frac{f(x_n)}{f'(x_n)}\]

Merk deg: Algoritmen finner bare ett nullpunkt om gangen.

Newtons metode for hånd#

Prinsippet bak metoden er å gjette en verdi \(x_0\) for nullpunktet, så finne nullpunktet \(x_1\) til tangenten. Dette nullpunktet er som regel nærmere nullpunktet til funksjonen enn den forrige verdien. Gjentar vi dette så får vi en bedre og bedre approksimasjon.

La oss utlede formelen. Hvis vi starter med en verdi \(x_n\) får vi at stigningstallet til tangenten blir \(f'(x_n)=\frac{f(x_n) - 0}{x_n-x_{n+1}}\).

Dette kan vi skrive om til formelen

\(x_{n+1}=x_n - \frac{f(x_n)}{f'(x_n)}\).

La oss prøve dette på en funksjon \(f(x)=x^2-2\). Jeg gjetter at det første nullpunktet er i nærheten av \(1\). Vi kan også finne at \(f'(x)=2x\).

Den første iterasjonen blir:

\(x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}= 1 - \frac{f(1)}{f'(1)} = 1 - \frac{(1^2-2)}{2\cdot 1} = 1 - \frac{-1}{2} = \frac{3}{2} = 1.5\)

Den andre iterasjonen blir:

\(x_2 = x_1 - \frac{f(x_1)}{f'(x_1)} = \frac{3}{2} - \frac{f(\frac{3}{2})}{f'(\frac{3}{2})} = \frac{17}{12} \approx 1.4166...\)

Newtons metode med Python#

La oss først se på en implementasjon av Newtons metode når vi har den deriverte funksjonen \(f'(x)\).

def f(x):
    return x**2 - 2

def df(x):
    return 2*x

x = 1
for n in range(5):
    x = x - f(x)/df(x)
    print(x)

1.5
1.4166666666666667
1.4142156862745099
1.4142135623746899
1.4142135623730951

Ganske greit, hva? Okei. Det er ikke alltid at vi klarer å finne den deriverte funksjonen. Da må vi bruke numerisk derivasjon. La oss implementere dette også.

def f(x):
    return x**2 - 2

# Numerisk derivasjon med fremoverdifferanse
def df(x):
    dx = 1e-8
    return (f(x + dx) - f(x))/(dx)

x = 1
for n in range(5):
    x = x - f(x)/df(x)
    print(x)

1.5000000030387355
1.4166666661602108
1.4142156862852249
1.4142135623746772
1.414213562373095

Nice! Da trenger vi ikke å derivere funksjonen vi jobber med for hånd.

La oss se på en siste versjon hvor vi bruker en while-løkke for å stoppe når vi har fått en ønsket nøyaktighet.

def f(x):
    return x**2 - 2

# Numerisk derivasjon med fremoverdifferanse
def df(x):
    dx = 1e-8
    return (f(x + dx) - f(x))/(dx)

forrige = 1
neste = forrige - f(forrige)/df(forrige)
print(neste)

while abs(neste - forrige) > 1e-8:
    forrige = neste
    neste = forrige - f(forrige)/df(forrige)
    print(neste)

1.5000000030387355
1.4166666661602108
1.4142156862852249
1.4142135623746772
1.414213562373095

Oppgaver#

Oppgave 1

(For hånd) Finn en approksimasjon for et nullpunkt med to iterasjoner av Newtons metode (til \(x_2\)). Sammenlikn med en eksakt løsning.

  1. \(f(x)=x^2-4\) med \(x_0 = 1\)

  2. \(f(x)=x^2-4\) med \(x_0 = -1\)

Har du funnet alle nullpunktene til funksjonen \(f(x)=x^2 - 4\)?

Oppgave 2

Bruk Newtons metode i Python til å finne nullpunktet til \(f(x)=e^x - 2\).

  1. Hvilken verdi er det du egentlig har funnet en approksimasjon for?

  2. Finn en approksimasjon for \(ln(3)\) og \(ln(5)\) ved å bruke programmet ditt.

Oppgave 3

Forklar at du bruke Newton’s metode til å finne approksimere kvadratroten \(\sqrt{N}\) av et hvilket som helst positivt tall \(N\).

Bonus: Vis at dette er ekvivalent med Herons metode (se: Kvadratrøtter)

Contents