Wetenschappelijk rekenen
,2
,Inhoudsopgave
1 Concepten Analyse - Lineaire algebra 5
1.1 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Lineaire Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Foutenanalyse 11
2.1 Fouttypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Getalvoorstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 IEEE standaard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Voorwaartse foutanalyse: elementaire bewerkingen . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Kahan som (1965) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6 Stelling van Sterbenz (1974) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7 Numerieke stabiliteit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.8 Conditionering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Stelsels van lineaire vergelijkingen 25
3.1 Voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Achterwaartse substitutie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Gauss-eliminatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3.1 Gauss-eliminatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3.2 Geassocieerd Gauss-eliminatie algoritme . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.3 Complexiteit Gauss-eliminatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.4 Stabiliteit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.5 Gauss-eliminatie met pivotering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 LU-decompositie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4 QR-ontbinding, eigenwaarden en eigenvectoren 37
4.1 Motivatie probleem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Google Pagerank algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 QR-decompositie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.4 Gram-Schmidt algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5 Stelling van Schur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5 Oplossen van niet-lineaire vergelijkingen 49
5.1 Verdeel-en-Heersstrategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2 Banachs dekpunt iteraties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3 Steffensen iteraties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4 Newtons methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.5 Niet-lineaire stelsels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.6 Extremumvraagstukken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7 Veelterminterpolatie 63
7.1 Wat is interpolatie? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.2 Veelterminterpolatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7.3 Hermite Interpolatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
7.3.1 Conditionering van interpolatieproblemen . . . . . . . . . . . . . . . . . . . . . . . 70
7.4 Stuksgewijze lineaire interpolatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.5 Cubic Spline interpolatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3
, 4 INHOUDSOPGAVE
7.6 Basisfuncties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
8 Lineair programmeren 75
8.1 Motivatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
8.2 Operations research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
8.3 Probleemstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
8.3.1 Standaardvorm / Eerste primale vorm . . . . . . . . . . . . . . . . . . . . . . . . . 76
8.4 Simplex methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.4.1 Slack vorm / Tweede primale vorm . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
8.4.2 Pivoting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
8.4.3 Tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.5 (Mixed) Integer programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.5.1 Branch-and-Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.5.2 Cutting Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.6 Dualiteit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.6.1 Farkas’ lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.7 Oefening - Transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
9 Markov-Chain Monte Carlo (MCMC) 87
9.1 Monte Carlo methodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
9.2 (Pseudo)-random getallen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
9.2.1 Lineaire-congruentiegeneratoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
9.2.2 Randomgetallen uit andere verdelingen . . . . . . . . . . . . . . . . . . . . . . . . 89
9.3 Markov-Chain Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
9.3.1 Bayesiaanse data-analyse / ML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
9.3.2 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
,2
,Inhoudsopgave
1 Concepten Analyse - Lineaire algebra 5
1.1 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Lineaire Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Foutenanalyse 11
2.1 Fouttypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Getalvoorstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 IEEE standaard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Voorwaartse foutanalyse: elementaire bewerkingen . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Kahan som (1965) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6 Stelling van Sterbenz (1974) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7 Numerieke stabiliteit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.8 Conditionering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Stelsels van lineaire vergelijkingen 25
3.1 Voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Achterwaartse substitutie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Gauss-eliminatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3.1 Gauss-eliminatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3.2 Geassocieerd Gauss-eliminatie algoritme . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.3 Complexiteit Gauss-eliminatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.4 Stabiliteit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.5 Gauss-eliminatie met pivotering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 LU-decompositie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4 QR-ontbinding, eigenwaarden en eigenvectoren 37
4.1 Motivatie probleem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Google Pagerank algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 QR-decompositie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.4 Gram-Schmidt algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5 Stelling van Schur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5 Oplossen van niet-lineaire vergelijkingen 49
5.1 Verdeel-en-Heersstrategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2 Banachs dekpunt iteraties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3 Steffensen iteraties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4 Newtons methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.5 Niet-lineaire stelsels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.6 Extremumvraagstukken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7 Veelterminterpolatie 63
7.1 Wat is interpolatie? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.2 Veelterminterpolatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7.3 Hermite Interpolatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
7.3.1 Conditionering van interpolatieproblemen . . . . . . . . . . . . . . . . . . . . . . . 70
7.4 Stuksgewijze lineaire interpolatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.5 Cubic Spline interpolatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3
, 4 INHOUDSOPGAVE
7.6 Basisfuncties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
8 Lineair programmeren 75
8.1 Motivatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
8.2 Operations research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
8.3 Probleemstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
8.3.1 Standaardvorm / Eerste primale vorm . . . . . . . . . . . . . . . . . . . . . . . . . 76
8.4 Simplex methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.4.1 Slack vorm / Tweede primale vorm . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
8.4.2 Pivoting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
8.4.3 Tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.5 (Mixed) Integer programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.5.1 Branch-and-Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.5.2 Cutting Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.6 Dualiteit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.6.1 Farkas’ lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.7 Oefening - Transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
9 Markov-Chain Monte Carlo (MCMC) 87
9.1 Monte Carlo methodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
9.2 (Pseudo)-random getallen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
9.2.1 Lineaire-congruentiegeneratoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
9.2.2 Randomgetallen uit andere verdelingen . . . . . . . . . . . . . . . . . . . . . . . . 89
9.3 Markov-Chain Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
9.3.1 Bayesiaanse data-analyse / ML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
9.3.2 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
