Beispiel: Numerische Differentation und Integration

Wir betrachten zunächst nochmal numerische Differentation:

die mathematische Definition

 simpleDiff:: (Double->Double)->Double->Double->Double

simpleDiff f x h = (f(x+h)-f(x))/h

Wir erzeugen jetzt eine Folge von Näherungswerten, indem wir simpleDiff auf eine Folge von abnehmenden Intervallbreiten anwenden:

damit dann:

 seqDiff:: (Double->Double)->Double->Double->[Double]

seqDiff f x = map (simpleDiff f x) . iterate (/2)

also:

vgl. Seite

jetzt Problem:
läßt sich die "`Konvergenzgeschwindigkeit"' verbessern?

plausibel:
Fehler eines Näherungswertes hängt ab von Intervallbreite h, also im einfachsten Fall lineare Abhängigkeit:
A_n = W + K*h
wobei:
A_n = n-te Approximation
W = wahrer Wert
K = Koeffizient

also:
A_n = W + K*h
A_n+1 = W + K*h/2
W = 2*A_n+1 - A_n

so definierte W-Werte sind natürlich auch noch ein bißchen falsch, d.h. Näherung
mache daraus wieder eine Folge!

seqDiff:

	[	A1		A2,		A3,	...	]
	[	W1		W2,			...	]

diese zweite Folge wird erzeugt durch:

 betterSeqDiff:: (Double->Double)->Double->Double->[Double]

betterSeqDiff f x = elimFstOrdError . seqDiff f x

wobei:

 elimFstOrdError:: [Double]->[Double]

elimFstOrdError (x1:x2:xs)       -assumes halving of distances

     = (2*x2-x1):(elimFstOrdError (x2:xs))

-      ----unsere Formel

Seite

 -------------------infinite lists: examples






---------------------------numerics

----------------------auxiliary functions






 


withinEps:: Double->[Double]->Double   
withinEps eps (x1:x2:xs)

   |abs(x1 - x2) <= eps = x2

   |otherwise           = withinEps eps (x2:xs)






 


elimFstOrdError:: [Double]->[Double]                                           
elimFstOrdError (x1:x2:xs)       -assumes halving of distances

     = (2*x2-x1):(elimFstOrdError (x2:xs))






-------------------------differentiation

simpleDiff:: (Double->Double)->Double->Double->Double

simpleDiff f x h = (f(x+h)-f(x))/h






seqDiff:: (Double->Double)->Double->Double->[Double]

seqDiff f x = map (simpleDiff f x) . iterate (/2)






betterSeqDiff:: (Double->Double)->Double->Double->[Double]

betterSeqDiff f x = elimFstOrdError . seqDiff f x






{-

Main> take 5 (seqDiff cos 0 0.1)

[-0.0499582, -0.0249946, -0.0125003, -0.00625134, -0.00312805]

Main> take 5 (betterSeqDiff cos 0 0.1)

[-3.09944e-05, -5.96046e-06, -2.38419e-06, -4.76837e-06, 0.0]

Main> withinEps 0.001 (seqDiff cos 0 0.1)

-0.000762939

Main> withinEps 0.001 (betterSeqDiff cos 0 0.1)

-5.96046e-06

-}

---------------------------integration

simpleIntegrate:: (Double->Double)->Double->Double->Double

simpleIntegrate f a b = (f a + f b) * (b-a)/2






seqIntegrate:: (Double->Double)->Double->Double->[Double]

seqIntegrate f a b = (simpleIntegrate f a b)
                      : (zipWith (+) (seqIntegrate f a m)

                                     (seqIntegrate f m b))

where m = (a+b)/2

                      -inefficient: recomputations of fa,fb,fm






{-

Main> take 10 (seqIntegrate sin 0 pi)

[-1.37323e-07, 1.5708, 1.89612, 1.97423, 1.99357, 1.99839, 1.9996, 1.9999, 1.99997, 1.99999]

Main> withinEps 0.001 (seqIntegrate sin 0 pi)

1.9999

-}

mit der Integration verfahren wir ähnlich:

ein grobes Verfahren ist offenbar:

 simpleIntegrate:: (Double->Double)->Double->Double->Double

simpleIntegrate f a b = (f a + f b) * (b-a)/2

Wir gewinnen eine Folge von Approximationswerten, indem wir (wiederholt)

• das Intervall [a,b] halbieren
• die Ergebnisse für beide Hälften addieren

 seqIntegrate:: (Double->Double)->Double->Double->[Double]

seqIntegrate f a b = (simpleIntegrate f a b)
                      : (zipWith (+) (seqIntegrate f a m)

                                     (seqIntegrate f m b))

where m = (a+b)/2

                      -inefficient: recomputations of fa,fb,fm

beachte: Ergebnis wieder Folge von Näherungswerten, aber komplexere Struktur der Rekursion: Baum, (Kaskade)