Samenvatting Wetenschappelijk Rekenen
Contents
Hoofdstuk 2: Foutenanalyse ......................................................................................................... 3
Inleidend voorbeeld ............................................................................................................................ 3
Fouttypes ............................................................................................................................................ 4
Getalvoorstelling ................................................................................................................................. 4
Relatieve en absolute fout .................................................................................................................. 5
IEEE floating point standaard .............................................................................................................. 5
Voorwaartse foutenanalyse ................................................................................................................ 6
Elementaire bewerkingen ................................................................................................................... 6
Voorbeeld........................................................................................................................................ 6
Kahan Som .......................................................................................................................................... 7
Voorbeeld........................................................................................................................................ 8
Stelling van Sterbenz........................................................................................................................... 8
Numerieke stabiliteit .......................................................................................................................... 9
Voorbeeld........................................................................................................................................ 9
Conditionering .................................................................................................................................... 9
Zwak stabiel ...................................................................................................................................... 10
Voorbeeld...................................................................................................................................... 10
Stabilisatie ......................................................................................................................................... 10
Hoofdstuk 3: Stelsels van lineaire vergelijkingen ......................................................................... 11
Inleidend voorbeeld .......................................................................................................................... 11
Doelstelling ....................................................................................................................................... 11
Onder- en bovendriehoekstelsels ..................................................................................................... 11
Achterwaartse substitutie voor het stelsel Uy = c ............................................................................ 11
Gauss eliminatie ................................................................................................................................ 12
Analyse .......................................................................................................................................... 13
Stabiliteit ....................................................................................................................................... 13
Pivotering ...................................................................................................................................... 14
LU-decompositie ............................................................................................................................... 14
Algoritme Crout-Doolittle ................................................................................................................. 15
Oplossing van een stelsel .................................................................................................................. 16
Hoofdstuk 4: QR-ontbinding, eigenwaarden en eigenvectoren .................................................... 16
Inleidend voorbeeld .......................................................................................................................... 16
1
Samenvatting WR - Lennert Saerens
, QR-decompositie .............................................................................................................................. 17
Algoritme ...................................................................................................................................... 17
Analyse .......................................................................................................................................... 19
Berekening eigenwaarden en eigenvectoren ................................................................................... 19
Hoofdstuk 5: Oplossen van niet-lineaire vergelijkingen ............................................................... 20
Banachs dekpunt iteraties ................................................................................................................ 21
Steffensens iteraties ......................................................................................................................... 21
Newtons methode ............................................................................................................................ 23
Gedempte methoden ....................................................................................................................... 23
Oplossen van niet-lineaire stelsels.................................................................................................... 23
Hoofdstuk 6: Numerieke integratie............................................................................................. 23
Inleidend voorbeeld .......................................................................................................................... 23
Trapeziumregel ................................................................................................................................. 23
Simpsonregel..................................................................................................................................... 24
Newton-Cotes formules .................................................................................................................... 24
Stabiliteit ....................................................................................................................................... 25
Samengestelde integratie ................................................................................................................. 26
Samengestelde trapeziumregel .................................................................................................... 26
Samengestelde Simpsonregel ....................................................................................................... 27
Romberg integratie(driehoek) .......................................................................................................... 27
Hoofdstuk 7: Veelterminterpolatie ............................................................................................. 28
Wat is interpolatie?........................................................................................................................... 28
Veelterminterpolatie ........................................................................................................................ 28
Voorbeeld...................................................................................................................................... 29
Conditionering .............................................................................................................................. 29
Hermite interpolatie ......................................................................................................................... 30
Voorbeeld...................................................................................................................................... 30
Lineaire stuksgewijze interpolatie .................................................................................................... 30
Conditionering .............................................................................................................................. 30
Voor- en nadelen .......................................................................................................................... 31
Cubic spline ....................................................................................................................................... 32
Basisfuncties ..................................................................................................................................... 33
Hoofdstuk 8: Lineair programmeren ........................................................................................... 34
Probleemstelling in standaardvorm.................................................................................................. 34
Eerste primale vorm (primal form) ............................................................................................... 34
Conversie....................................................................................................................................... 35
2
Samenvatting WR - Lennert Saerens
, Tweede primale vorm (slack form) ............................................................................................... 35
Simplex methode .............................................................................................................................. 36
Pivoting ............................................................................................................................................. 37
Tableau.............................................................................................................................................. 37
(Mixed) integer programming........................................................................................................... 39
Branch-and-bound ............................................................................................................................ 40
Cutting planes ................................................................................................................................... 42
Gomory cut ....................................................................................................................................... 42
Dualiteit............................................................................................................................................. 42
Hoofdstuk 9: Markov-chain Monte Carlo methodes .................................................................... 43
Monte Carlo methodes ..................................................................................................................... 43
Pseudo-random getallen................................................................................................................... 43
Lineaire-congruentiegeneratoren..................................................................................................... 43
Random getallen uit andere verdelingen ......................................................................................... 44
Inverse transform.......................................................................................................................... 44
Accept-reject sampling ................................................................................................................. 45
Ad-hoc methodes (vb. Box-Muller) ............................................................................................... 45
Monte Carlo integratie.................................................................................................................. 45
Variantie ........................................................................................................................................ 45
Markov-chain Monte Carlo ............................................................................................................... 46
Motivatie: Bayesiaanse data analyse / ML ................................................................................... 46
Markov chains ............................................................................................................................... 46
Metropolis-Hastings .......................................................................................................................... 47
Hoofdstuk 2: Foutenanalyse
Inleidend voorbeeld
Wiskundig equivalente voorstellingen → numeriek niet equivalent.
Voorbeeld:
𝑥
𝑓(𝑥) = 𝑥(√𝑥 + 1 − √𝑥) 𝑚𝑒𝑡 𝑥 ≥ 0 𝑒𝑛 𝑔(𝑥) = 𝑚𝑒𝑡 𝑥 ≥ 0
√𝑥 + 1 + √𝑥
• Equivalente voorstellingen → nu gebruiken op rekentoestel met 4 decimale cijfers voor x =
500
𝑓(500) = 500(22,3830 − 22,3607) = 500 ∗ 0,0223 = 11.1500
500 500
𝑔(500) = = = 11,1748
22,3830 − 22,3607 44,7437
3
Samenvatting WR - Lennert Saerens
, • Welke uitdrukking correcter?
o Functies nu evalueren met 1 decimaal nauwkeuriger
o We merken dat f maar een decimaal nauwkeurig gaf terwijl g tot op drie decimalen
nauwkeurig was
▪ We noemen g daarom numeriek stabieler.
Fouttypes
In de numerieke wiskunde onderscheiden we 4 fouttypes:
• Invoerfouten: De numerieke methode wordt toegepast op een foutieve invoer. Dit kan zijn
door ruis of statistische fouten.
• Onvermijdelijke fout: Dit zijn fouten die verschijnen door de uitgevoerde bewerkingen.
• Methodefout: Dit zijn fouten door benaderingen in de numerieke methode zelf. (H5 en H6)
• Afrondfout: Dit zijn fouten door de numerieke voorstelling van de getallen.
Inleidend voorbeeld 2 fouttypes:
• Afrondfout: verschil tussen 4 en 5 decimalen nauwkeurigheid
• Onvermijdelijke fout: De onvermijdelijke fout bij de tweede methode is kleiner. Merk op dat
dit niets te maken heeft met de afrondfout of de precisie van de getalvoorstelling.
Komen vaak samen voor: ontknoping leidt tot begrippen conditionering en numerieke stabiliteit (zie
later)
Getalvoorstelling
Begrippen:
Laat 𝑥 ∈ ℝ dan wordt dit getal numeriek voorgesteld door een floating point of een zwevende
kommavoorstelling als:
𝑓𝑙(𝑥) = ±𝑖0 , 𝑖1 𝑖2 … 𝑖𝑝 ∗ 𝑏 𝑒
We kunnen zeggen dat fl(x) x projecteert op de dichtstbijzijnde floating point voorstelling. Hier bij is
𝑖𝑘 ∈ {0,1,2, , … ,9} met 𝑘 ∈ {0,1,2, … , 𝑝}. Opdat deze voorstelling uniek is mag 𝑖0 ≠ 0.
We noemen 𝑖0 , 𝑖1 𝑖2 … 𝑖𝑝 de mantisse, b de getalbasis, e de exponent en p de precisie.
Afspraak: De volledige mantisse wordt weergegeven, behalve indien 𝑏 = 2. In dit geval is impliciet
𝑖0 = 1.
1. Beschouw een systeem in basis 10 met een mantisse van precisie 6
Het volgende voorbeeld kan niet exact worden voorgesteld in dit systeem:
Dit getal heeft een precisie nodig van 11. De moeilijkheid van getalvoorstellingen is niet de grootte
van de getallen maar de lengte van de mantisse.
4
Samenvatting WR - Lennert Saerens
Contents
Hoofdstuk 2: Foutenanalyse ......................................................................................................... 3
Inleidend voorbeeld ............................................................................................................................ 3
Fouttypes ............................................................................................................................................ 4
Getalvoorstelling ................................................................................................................................. 4
Relatieve en absolute fout .................................................................................................................. 5
IEEE floating point standaard .............................................................................................................. 5
Voorwaartse foutenanalyse ................................................................................................................ 6
Elementaire bewerkingen ................................................................................................................... 6
Voorbeeld........................................................................................................................................ 6
Kahan Som .......................................................................................................................................... 7
Voorbeeld........................................................................................................................................ 8
Stelling van Sterbenz........................................................................................................................... 8
Numerieke stabiliteit .......................................................................................................................... 9
Voorbeeld........................................................................................................................................ 9
Conditionering .................................................................................................................................... 9
Zwak stabiel ...................................................................................................................................... 10
Voorbeeld...................................................................................................................................... 10
Stabilisatie ......................................................................................................................................... 10
Hoofdstuk 3: Stelsels van lineaire vergelijkingen ......................................................................... 11
Inleidend voorbeeld .......................................................................................................................... 11
Doelstelling ....................................................................................................................................... 11
Onder- en bovendriehoekstelsels ..................................................................................................... 11
Achterwaartse substitutie voor het stelsel Uy = c ............................................................................ 11
Gauss eliminatie ................................................................................................................................ 12
Analyse .......................................................................................................................................... 13
Stabiliteit ....................................................................................................................................... 13
Pivotering ...................................................................................................................................... 14
LU-decompositie ............................................................................................................................... 14
Algoritme Crout-Doolittle ................................................................................................................. 15
Oplossing van een stelsel .................................................................................................................. 16
Hoofdstuk 4: QR-ontbinding, eigenwaarden en eigenvectoren .................................................... 16
Inleidend voorbeeld .......................................................................................................................... 16
1
Samenvatting WR - Lennert Saerens
, QR-decompositie .............................................................................................................................. 17
Algoritme ...................................................................................................................................... 17
Analyse .......................................................................................................................................... 19
Berekening eigenwaarden en eigenvectoren ................................................................................... 19
Hoofdstuk 5: Oplossen van niet-lineaire vergelijkingen ............................................................... 20
Banachs dekpunt iteraties ................................................................................................................ 21
Steffensens iteraties ......................................................................................................................... 21
Newtons methode ............................................................................................................................ 23
Gedempte methoden ....................................................................................................................... 23
Oplossen van niet-lineaire stelsels.................................................................................................... 23
Hoofdstuk 6: Numerieke integratie............................................................................................. 23
Inleidend voorbeeld .......................................................................................................................... 23
Trapeziumregel ................................................................................................................................. 23
Simpsonregel..................................................................................................................................... 24
Newton-Cotes formules .................................................................................................................... 24
Stabiliteit ....................................................................................................................................... 25
Samengestelde integratie ................................................................................................................. 26
Samengestelde trapeziumregel .................................................................................................... 26
Samengestelde Simpsonregel ....................................................................................................... 27
Romberg integratie(driehoek) .......................................................................................................... 27
Hoofdstuk 7: Veelterminterpolatie ............................................................................................. 28
Wat is interpolatie?........................................................................................................................... 28
Veelterminterpolatie ........................................................................................................................ 28
Voorbeeld...................................................................................................................................... 29
Conditionering .............................................................................................................................. 29
Hermite interpolatie ......................................................................................................................... 30
Voorbeeld...................................................................................................................................... 30
Lineaire stuksgewijze interpolatie .................................................................................................... 30
Conditionering .............................................................................................................................. 30
Voor- en nadelen .......................................................................................................................... 31
Cubic spline ....................................................................................................................................... 32
Basisfuncties ..................................................................................................................................... 33
Hoofdstuk 8: Lineair programmeren ........................................................................................... 34
Probleemstelling in standaardvorm.................................................................................................. 34
Eerste primale vorm (primal form) ............................................................................................... 34
Conversie....................................................................................................................................... 35
2
Samenvatting WR - Lennert Saerens
, Tweede primale vorm (slack form) ............................................................................................... 35
Simplex methode .............................................................................................................................. 36
Pivoting ............................................................................................................................................. 37
Tableau.............................................................................................................................................. 37
(Mixed) integer programming........................................................................................................... 39
Branch-and-bound ............................................................................................................................ 40
Cutting planes ................................................................................................................................... 42
Gomory cut ....................................................................................................................................... 42
Dualiteit............................................................................................................................................. 42
Hoofdstuk 9: Markov-chain Monte Carlo methodes .................................................................... 43
Monte Carlo methodes ..................................................................................................................... 43
Pseudo-random getallen................................................................................................................... 43
Lineaire-congruentiegeneratoren..................................................................................................... 43
Random getallen uit andere verdelingen ......................................................................................... 44
Inverse transform.......................................................................................................................... 44
Accept-reject sampling ................................................................................................................. 45
Ad-hoc methodes (vb. Box-Muller) ............................................................................................... 45
Monte Carlo integratie.................................................................................................................. 45
Variantie ........................................................................................................................................ 45
Markov-chain Monte Carlo ............................................................................................................... 46
Motivatie: Bayesiaanse data analyse / ML ................................................................................... 46
Markov chains ............................................................................................................................... 46
Metropolis-Hastings .......................................................................................................................... 47
Hoofdstuk 2: Foutenanalyse
Inleidend voorbeeld
Wiskundig equivalente voorstellingen → numeriek niet equivalent.
Voorbeeld:
𝑥
𝑓(𝑥) = 𝑥(√𝑥 + 1 − √𝑥) 𝑚𝑒𝑡 𝑥 ≥ 0 𝑒𝑛 𝑔(𝑥) = 𝑚𝑒𝑡 𝑥 ≥ 0
√𝑥 + 1 + √𝑥
• Equivalente voorstellingen → nu gebruiken op rekentoestel met 4 decimale cijfers voor x =
500
𝑓(500) = 500(22,3830 − 22,3607) = 500 ∗ 0,0223 = 11.1500
500 500
𝑔(500) = = = 11,1748
22,3830 − 22,3607 44,7437
3
Samenvatting WR - Lennert Saerens
, • Welke uitdrukking correcter?
o Functies nu evalueren met 1 decimaal nauwkeuriger
o We merken dat f maar een decimaal nauwkeurig gaf terwijl g tot op drie decimalen
nauwkeurig was
▪ We noemen g daarom numeriek stabieler.
Fouttypes
In de numerieke wiskunde onderscheiden we 4 fouttypes:
• Invoerfouten: De numerieke methode wordt toegepast op een foutieve invoer. Dit kan zijn
door ruis of statistische fouten.
• Onvermijdelijke fout: Dit zijn fouten die verschijnen door de uitgevoerde bewerkingen.
• Methodefout: Dit zijn fouten door benaderingen in de numerieke methode zelf. (H5 en H6)
• Afrondfout: Dit zijn fouten door de numerieke voorstelling van de getallen.
Inleidend voorbeeld 2 fouttypes:
• Afrondfout: verschil tussen 4 en 5 decimalen nauwkeurigheid
• Onvermijdelijke fout: De onvermijdelijke fout bij de tweede methode is kleiner. Merk op dat
dit niets te maken heeft met de afrondfout of de precisie van de getalvoorstelling.
Komen vaak samen voor: ontknoping leidt tot begrippen conditionering en numerieke stabiliteit (zie
later)
Getalvoorstelling
Begrippen:
Laat 𝑥 ∈ ℝ dan wordt dit getal numeriek voorgesteld door een floating point of een zwevende
kommavoorstelling als:
𝑓𝑙(𝑥) = ±𝑖0 , 𝑖1 𝑖2 … 𝑖𝑝 ∗ 𝑏 𝑒
We kunnen zeggen dat fl(x) x projecteert op de dichtstbijzijnde floating point voorstelling. Hier bij is
𝑖𝑘 ∈ {0,1,2, , … ,9} met 𝑘 ∈ {0,1,2, … , 𝑝}. Opdat deze voorstelling uniek is mag 𝑖0 ≠ 0.
We noemen 𝑖0 , 𝑖1 𝑖2 … 𝑖𝑝 de mantisse, b de getalbasis, e de exponent en p de precisie.
Afspraak: De volledige mantisse wordt weergegeven, behalve indien 𝑏 = 2. In dit geval is impliciet
𝑖0 = 1.
1. Beschouw een systeem in basis 10 met een mantisse van precisie 6
Het volgende voorbeeld kan niet exact worden voorgesteld in dit systeem:
Dit getal heeft een precisie nodig van 11. De moeilijkheid van getalvoorstellingen is niet de grootte
van de getallen maar de lengte van de mantisse.
4
Samenvatting WR - Lennert Saerens
