beamer - Vrije Universiteit Amsterdam

Numerieke Methoden I
College 1: A. Introductie & Voorbeeld
B. Matlab
A.A.N. Ridder
Department EOR
Vrije Universiteit Amsterdam
Huispagina: http://personal.vu.nl/a.a.n.ridder/numprog/default.htm
2 september 2014
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
1 / 35
Doel
I
Kennis van standaard/klassieke numerieke methoden voor EOR problemen;
I
Vaardigheid om die methoden te implementeren in een hogere computertaal
(Matlab);
I
Presentatie van resultaten (grafisch!).
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
2 / 35
Opzet
I
6 weken (week 36 t/m 41);
I
dinsdagen (9:00-10:45) hoorcollege in 2A-06;
I
woensdagen (9:00-10:45)
I
drie keer Matlab practicum in 5B-06 (week 36,38,40);
I
drie keer bespreking opgaven (theorie en programmeer) en eventueel Matlab tips in
2A-06 (week 37,39,41).
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
3 / 35
Boek
In dit college wordt gebruikt
E.W. Cheney & David Kincaid
Numerical Mathematics And Computing
Brooks/Cole; International edition of 7th revised edition (2012).
De 6-th edition is ook goed genoeg (weinig inhoudelijke veranderingen, wel andere
nummering en volgorde).
Te verkrijgen bij Kraket of boekhandel.
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
4 / 35
Wat zal behandeld worden uit Boek?
I
Hoofdstuk 1. Floating point representation
I
Hoofdstuk 2. Linear systems [Numerieke Methoden II (periode 5)];
I
Hoofdstuk 3. Nonlinear systems (nulpunten van functies);
I
Hoofdstuk 4. Interpolation;
I
Hoofdstuk 5. Numerical integration;
I
Hoofdstuk 6. Splines;
I
Hoofdstuk 8. More on Linear systems [Numerieke Methoden II (periode 5)];
I
Hoofdstuk 9. Kleinste kwadraten [Numerieke Methoden II (periode 5)];
I
Hoofdstuk 10. Monter Carlo methods [Numerieke Methoden II (periode 5)];
I
Hoofdstuk 13. Minimilizatie [Numerieke Methoden II (periode 5)];
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
5 / 35
Matlab
Bij dit college wordt geprogrammeerd in Matlab.
Drie keer practicum: woensdagen 3/9, 17/9, 1/10 van 9:00 - 10.45 uur in 5B-06.
Verplicht drietal computeropdrachten in te leveren (wordt nader bekend gemaakt).
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
6 / 35
Website
De huispagina is
http://personal.vu.nl/a.a.n.ridder/numprog/default.htm
Bevat
I
slides van de colleges;
I
practicumopgaven en inleveropdrachten;
I
voorbeeldprogramma’s in Matlab;
I
oude tentamens;
I
links naar online Matlab tutorials en handleidingen.
Slides en opdrachten komen ook op de Blackboard pagina.
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
7 / 35
Beoordeling
1. Drie programmeeropdrachten moeten voldoende zijn.
2. Schriftelijk tentamen dinsdag 21 oktober; herkansing dinsdag 9 december.
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
8 / 35
Introductie
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
9 / 35
Wat zijn numerieke Methoden?
Computerberekeningen voor complexe problemen in wetenschappelijke disciplines;
zoals
I
economie/econometrie
I
operations research
I
wiskundige economie
I
financiering
I
natuurkunde/sterrenkunde
I
wiskunde/statistiek
I
techniek (electro, communicatie, ontwerp, etc)
I
...
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
10 / 35
Wetenschappelijke Methode
I
Probleembeschrijving;
I
Abstracte (wiskundige of statistische) modellering: variabelen; relaties; functies;
...;
I
Data verzamelen;
I
Valideer wiskundig model;
I
Ontwikkel een computerprogramma
I
gebaseerd op numerieke methoden (algoritmes);
I
of een simulatiemodel;
I
Verifieer computerprogramma;
I
Voer uit en rapporteer.
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
11 / 35
Veel Onderwerpen
Numerieke methoden zijn ontwikkeld voor
1. Lineaire en nietlineaire stelsels
2. Eigenwaarde probleem
3. Nulpunten van functies
4. Interpolatie en splines
5. Integratie
6. Differentiaalvergelijkingen
7. Kleinste kwadraten
8. Optimalisatie
9. Monte Carlo integratie
10. ...
Niet alle zullen behandeld worden.
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
12 / 35
Programmeren
I
Probleem wordt opgelost door de computer berekeningen te laten uitvoeren;
I
Computer krijgt opdrachten via een computerprogramma;
I
Programma is geschreven in een computertaal;
I
Computertaal is de intermediair tussen de wetenschapper (en programmeur) en
de computer;
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
13 / 35
Keuze van Computertaal
I
Algemeen, laag-niveau: C,C++,Java; alle algoritmes zelf implementeren;
I
Speciaal, hoog-niveau: Matlab, Ox; veel bibliotheekroutines beschikbaar;
gevectoriseerd; ...
I
Computeralgebra: Maple, Mathematica.
Numerieke Methode I (periode 1): Matlab
Programming (periode 2): Java
Numerieke Methoden II (periode 5): Ox
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
14 / 35
Voorbeeld
Uit (wiskundige) economie.
I
Monopolist;
I
Vraagt prijs p per eenheid product;
I
De hoeveelheid vraag naar het product is een functie van de prijs:
d = D(p);
I
Wegens monopolie, kan productiegrootte q evenveel zijn als de vraag:
q = d = D(p);
I
De kosten van productie hangen af van de productiegrootte:
c = C(q);
I
Probleem: bepaal de prijs waarbij de monopolist zijn winst maximaliseert.
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
15 / 35
Voorbeeld (vervolg)
Univariate maximalisatie:
max{W(p) : W(p) = pD(p) − C(D(p))}.
p
Twee mogelijke numerieke methoden:
1. Direct de winstfunctie optimalizeren;
2. De eerste order vergelijking oplossen; dwz stationair punt vinden; dwz afgeleide
opstellen en nulpunt bepalen.
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
16 / 35
Voorbeeld (vervolg)
Data:
D(p) =

100
100
(
C(q) =
c Ad Ridder (VU)
voor 0 < p ≤ 20
log(20)
log(p)
6
500
√
500 + 10 q − 5
voor p ≥ 20
voor 0 < q ≤ 5
voor q ≥ 5
Numerieke Methoden I – Najaar 2014
17 / 35
Winstgrafiek in Voorbeeld 1
Winst als functie van prijs W(p) = pD(p) − C(D(p)).
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
18 / 35
Voorbeeld (vervolg)
Direct optimalizeren. Nodig:
(i). een methode (algoritme) om bij elke prijs p de bijbehorende functiewaarde W(p)
te berekenen;
(ii). voor een berekenbare continue univariate functie f :
(algoritme) om die functie te minimalizeren.
R → R een methode
Merk op dat maxp W(p) een instantie is van minx f (x).
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
19 / 35
Voorbeeld (vervolg)
(i). W(p) uitrekenen als functie van p is simpel. Moet je zelf programmeren.
(ii). Een univariate functie f (x) minimalizeren:
I
Klassiek numeriek onderwerp;
I
Vele methoden;
I
Boek hoofdstuk 13;
I
Internet; bv Wikipedia
http://en.wikipedia.org/wiki/Optimization_(mathematics)
MathWorld http://mathworld.wolfram.com/topics/Optimization.html
I
Wordt later tijdens colleges behandeld;
I
Zelf programmeren of beschikbare codes gebruiken.
I
Matlab heeft beschikbare (geprogrammeerde) methode fminbnd. Je moet opzoeken
hoe die te gebruiken, aanroepen, en wat de output is.
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
20 / 35
Voorbeeld (vervolg)
Schrijf nu een computerprogramma dat al de bovenstaande ingredienten combineert.
I Rekenmodules:
(i). functies om W(p) te berekenen;
(ii). algoritme om univariate f (x) te minimaliseren;
I
Output: prijs p waarbij winst gemaximaliseerd wordt.
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
21 / 35
Matlabprogramma Voorbeeld
% Dit is file voorbeeld1.m
function voorbeeld1
main;
%%%%%%% hoofdfunctie %%%%%%%%%
function main
p = optprijs(0,100); % verwacht dat optimale
% prijs tussen 0 en 100 ligt
w = winst(p);
disp(sprintf(’optimale prijs = %.2f’,p));
disp(sprintf(’winst = %.2f’,w));
end
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
22 / 35
Matlabprogramma Voorbeeld (vervolg)
% vervolg van voorbeeld1.m
%%%%%%%%%% hulpfunctie %%%%%%%%%%
function d = vraag(p)
if p<20
d = 100;
else
d = 100*(log(20)/log(p))ˆ6;
end
end
%%%%%%%%%% hulpfunctie %%%%%%%%%%
function c = kosten(q)
if q<5
c = 500;
else
c = 500 + 10*sqrt(q-5);
end
end
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
23 / 35
Matlabprogramma Voorbeeld (vervolg)
% vervolg van voorbeeld1.m
%%%%%%%%%% hulpfunctie %%%%%%%%%%
function w = winst(p)
d = vraag(p);
w = p*d - kosten(d);
end
%%%%%%%%%% hulpfunctie %%%%%%%%%%
function y = funf(p)
y = -winst(p);
end
%%%%%%%%%% hulpfunctie %%%%%%%%%%
function p = optprijs(a,b)
y = @(p)funf(p); % function handler
p = fminbnd(y,a,b); % aanroep van Matlab routine
end
end
%%%%%%%%%% EOF voorbeeld1.m %%%%%%%%%%
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
24 / 35
Programmeren met Parameters
I
Stel de 20 in de vraagfunctie moet 30 zijn. Dan moet je overal in je programma
nagaan wat je moet vernaderen.
I
Probeer daarom flexibel te programmeren;
I
Maak gebruik van parameters;
I
In de subfuncties blijven (zoveel mogelijk) de parameters staan zonder specifieke
waarden;
I
Het hoofdprogramma controleert deze specifieke waarden.
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
25 / 35
Voorbeeld (Verbeterd Programma)
% Dit is file voorbeeld2.m
function voorbeeld2
main;
%%%%%%% hoofdfunctie %%%%%%%%%%
function main
% verzamel data
p0 = 20; d0 = 100; q0 = 5;
c0 = 500; alpha = 10;
% uitvoer
p = optprijs(p0,d0,q0,c0,alpha,0,200);
w = winst(p,p0,d0,q0,c0,alpha);
disp(sprintf(’optimale prijs = %.2f’,p));
disp(sprintf(’winst = %.2f’,w));
end
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
26 / 35
Matlabprogramma Voorbeeld (vervolg)
% vervolg van voorbeeld2.m
%%%%%%%%%% hulpfunctie %%%%%%%%%%
function d = vraag(p,p0,d0)
if p<p0
d = d0;
else
d = d0*(log(p0)/log(p))ˆ6;
end
end
%%%%%%%%%% hulpfunctie %%%%%%%%%%
function c = kosten(q,q0,c0,alpha)
if q<q0
c = c0;
else
c = c0 + alpha*sqrt(q-q0);
end
end
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
27 / 35
Matlabprogramma Voorbeeld (vervolg)
% vervolg van voorbeeld2.m
%%%%%%%%%% hulpfunctie %%%%%%%%%%
function w = winst(p,p0,d0,q0,c0,alpha)
d = vraag(p,p0,d0);
w = p*d - kosten(d,q0,c0,alpha);
end
%%%%%%%%%% hulpfunctie %%%%%%%%%%
function y = funf(p,p0,d0,q0,c0,alpha)
y = -winst(p,p0,d0,q0,c0,alpha);
end
%%%%%%%%%% hulpfunctie %%%%%%%%%%
function p = optprijs(p0,d0,q0,c0,alpha,a,b)
y = @(p)funf(p,p0,d0,q0,c0,alpha); % function handler
p = fminbnd(y,a,b); % aanroep van Matlab routine
end
end
%%%%%%%%%% EOF voorbeeld2.m %%%%%%%%%%
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
28 / 35
Toelichting Matlabprogramma
Tijdens college.
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
29 / 35
MATLAB
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
30 / 35
Waarom Matlab?
I
Wereldwijde standaard;
I
Schrijven van code gaat veel sneller dan in een algemene taal als C of Java;
I
Vele wiskundige methoden beschikbaar (‘bibliotheekprocedures’) en die zijn
geprogrammeerd met de ‘beste’ algoritmes. Getest op fouten, snelheid,
robustheid, enz;
I
Bv. een stelsel lineaire vergelijkingen Ax = b oplossen doe je door de code x = A\b
I
Hiermee wordt een scala aan bekende procedures aangeroepen zoals Gaussische
eliminatie, LU-factorisatie, kleinste kwadraten, enz.!
I
Gemakkelijk grafische weergave (plotten);
I
Toolboxes voor speciale toepassingen (statistiek; optimalisering; financiering; ...).
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
31 / 35
Waarom niet Matlab?
I
Matlab werkt alleen met Mathworks software Matlab. Je kunt wel executables
compileren; maar dat vereist nodige extra’s;
I
Geen open source;
I
Niet geschikt voor software engineering;
I
Duur;
I
Minder geschikt voor omvangrijke simulatiestudies: langzamer dan C en Java.
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
32 / 35
Beschikbaarheid Matlab
I
In computerzalen van de faculteit (versie 7.12.0 (R2011a)?);
I
Dat is de professionele (full blown) universitaire versie;
I
Persoonlijke versie moet je kopen; bv de Studentversie via boekwinkel;
I
Gratis alternatieven:
(i). (GNU) Octave
(ii). FreeMat
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
33 / 35
Voorkennis van Matlab
I
Heb je opgedaan bij IP 1.3, IP 1.6
I
R. Pratap; Getting started with Matlab 7 (Oxford Press)
I
1.1; 1.2; 1.6: basics;
I
2.1; 2.2: arrays of numbers;
I
3.1; 3.2; 3.3; 3.4: matrices and vectors; inline functions; function handlers;
I
4.1; 4.2; 4.3: script files; function files; loops;
I
6.1; 6.2; 6.5: plotting
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
34 / 35
Matlab Start
Ga naar
http://personal.vu.nl/a.a.n.ridder/numprog/matlab/default.htm
c Ad Ridder (VU)
Numerieke Methoden I – Najaar 2014
35 / 35

Download Report