Epsilon og delta og store O

Når jeg har vejledt projekter, hvor studerende skulle anvende asymptotisk notation til at analysere funktioners vækstrate, er der altid nogle hindringer for forståelsen. Definitionen er egentlig enkel nok.

Lad f og g være funktioner over de naturlige tal. Vi siger at f = O(g), hvis der findes en positiv reel konstant c og et naturligt tal n_0 således at f(n) \leq c \cdot g(n) for alle n > n_0.

Hvis betingelsen gælder, når det bløde ulighedstegn ovenfor gøres skarpt, har vi at f = o(g).

Vi kan så indføre notationen O(f) for at skrive et led h, hvorom vi blot ved at h = O(f) og skrive f.eks.

(x+4)^2 = x^2 + O(x)

Asymptotisk notation stammer fra talteori og dukker op første gang hos Paul Bachmann helt tilbage i 1894. Datalogistuderende kender dog asymptotisk notation fra algoritmeteori, hvor de funktioner, der bliver sammenlignet, er kompleksitetsfunktioner. Derfor kan man opleve forbløffende mange studerende sige at “O-notationen bruges til at måle kompleksitet” eller, om muligt endnu værre, at “O-notationen bruges til at måle funktioners kompleksitet”.

Den legendariske amerikanske matematiker og datalog Donald Knuth skrev i 1988 et kort brev til AMS (American Mathematical Society), hvori han slog til lyd for, at man skulle lære de studerende differential- og integralregning ved brug af netop O-notation. Hans tanke er, at dette skulle være nemmere i læringssammenhæng. Om det er rigtigt, ved jeg ikke. Men når man skal definere f.eks. den afledede af en reel funktion, bliver det nemmere. For da kan vi sige, at f for værdien x er differentiabel med afledet f'(x), hvis der for et tilstrækkeligt lille \epsilon gælder at

f(x+\epsilon) = f(x) + f'(x)\epsilon + O(\epsilon^2)

Nu er det nemt at finde den afledede af f(x) = x^2, for

(x+\epsilon)^2 = x^2 + 2x\epsilon + \epsilon^2

Kontinuitet kan formuleres således: f er kontinuert i x hvis

f(x+\epsilon) = f(x) + o(1)

Jeg ved som sagt ikke, om ideen er god i didaktisk sammenhæng. Men den giver en interessant vinkel på reel analyse. Det gode er, at de kvantorer, der hærger epsilon-delta-definitionerne i analyse, nu i stort omfang er skjult i definitionen af asymptotisk notation. Det er stadig mandag formiddag, og jeg har ikke tænkt over, om det ved brug af asymptotisk notation bliver nemmere at forstå f.eks. den kontraponerede udgave af kontinuitetsdefinitionen, som trækker tænder ud på mange matematikstuderende. Men nogen bør tænke over det.

Man kan finde \TeX-filen med Knuths brev her (og husk, at det er \TeX, ikke \LaTeX!).

(Visited 199 times, 1 visits today)
Loading Facebook Comments ...

Skriv et svar