Instructies voor Lineaire Algebra 2 - Matlabsessies in week 9-12 De laatste vier weken bij Lineaire Algebra 2 zijn van dubbele instensiteit. Er zijn zes contacturen, verdeeld over een hoor-/instructie-college op woensdag van 2×45 minuten, en een begeleide programmeersessie van 4×45 minuten. In de tijd tussen de beide bijeenkomsten maak je enkele ook theoretisch geori¨enteerde opgaven en oefen je intensief met de nieuwe Matlabvaardigheden die op de woensdag zijn behandeld. De problemen die je daarbij ondervindt kan je op vrijdag bespreken met je werkgroepleider, waarna je aan het eind van de sessie al je werk inlevert: de theoretische opgaven op schrift, en Matlabcodes per e-mail. Inleverdeadline: deze is dus op vrijdag om 12:45 bij afloop van de programmeersessie. Uitzondering hierop wordt alleen gemaakt als het vak voor jou niet tot je verplichte curriculum behoort: je volgt het vak als bijvak, of uit interesse; in dat geval is de deadline vrijdagavond 23:59.
Dit onderdeel van Lineaire Algebra 2 is grotendeels een doe-vak. Wees actief, ervaar een zekere mate van urgentie, alsof je bij een bedrijf werkt en de baas wil dat je vrijdag om 12:45 iets belangrijks af hebt. Verspil geen tijd met digitale en andere afleidingen!
Algemene opmerking: over integriteit en zelfwerkzaamheid De door jou ingeleverde opgaven heb je naar eer en geweten zelf gemaakt en geprogrammeerd. Je mag natuurlijk om hulp en hints vragen aan je werkgroepleider en aan medestudenten, maar uiteindelijk lever je jouw eigen uitwerkingen van de opgaven in. Aangezien je werk mede bepalend is voor het slagen voor het vak, zijn docenten en wekgroepleiders verplicht om incidenten te melden bij de examencommissie om zo de kwaliteit van de opleiding en het diploma te garanderen. Realiseer je dat een onvoldoende halen voor dit vak, hoe vervelend en/of beschamend dat voor sommige ook kan zijn, nooit erger is je integriteit verliezen, zelfs niet als je er mee weg komt. Het eerste kan je herstellen, het tweede kan je blijven achtervolgen!
9. Beschrijving van de stof en opdeling van de opgaven voor week 9 Op woensdag demonstreren we een flinke portie basis-commando’s van de programmeertaal Matlab. Deze commando’s voer je live uit op je eigen laptop. Het overzicht is summier: je zal ook worden geleerd om Matlab-functionaliteit zelf te vinden uit bronnen zoals de Matlab help-files, de Matlab website, en web-searches met een geschikte zoekmachine. In opgaven 4.1.1, 4.1.2, en 4.1.3 word je gevraagd om op creatieve wijze, ondersteund door Matlab, exacte wiskunde te doen. Deze opgaven zijn niet geheel eenvoudig en zijn zeer individueel: de verwachting is dat ieder van jullie met een andere oplossing komt. En als het meezit ook met zodanig mooie oplossingen, dat we ze kunnen gebruiken voor het hertentamen! 9.1. Thema: de deelruimte van magische vierkanten Het thema van week 9 is magische vierkanten. Matlab heeft een (behoorlijk nutteloos) ingebouwd commando waarmee je voor iedere n een n×n magisch vierkant kunt produceren. Deze vierkanten lenen zich echter uitstekend voor bepaalde onderzoekingen die de basisvaardigheden met Matlab trainen, en die wat betreft lineaire algebra-niveau blijven steken in de stof van Lineaire Algebra 1. De inleidende opgaven hiervoor zijn 4.2.1, 4.2.2 (theoretisch) en 4.2.3, 4.2.4 (Matlab-technisch). Deze laatste twee kunnen kort en beknopt worden beantwoord. De
1
opgaven 4.2.5, 4.2.6, 4.2.7, en 4.2.8, in het bijzonder de laatste hiervan, zijn wat geavanceerder. Deze zijn in principe bedoeld voor tijdens de vrijdagochtendsessie. 9.2. Jouw tijdsindeling en planning Op woensdag doe je actief mee met de Matlab-demonstraties. Je hebt je laptop bij je, en Matlab is daarop geinstalleerd. Je hebt het programma al eens opgestart dus je weet zeker dat het werkt. Je maakt aantekeningen van handige commando’s. Daarnaast doe je alle basiskennis op over de wiskunde achter magische vierkanten. Op donderdag neem je ruim de tijd om eerst opgaven 4.1.1, 4.1.2, 4.1.3, 4.2.2 en 4.2.3 te maken. Ondanks dat je Matlab gebruikt om de opgaven te maken, documenteer je je resultaten gewoon op schrift, door in zeker detail te omschrijven hoe je met behulp van Matlab tot je resultaten bent gekomen. Tot slot, maak opgave 4.2.4 en sla het resultaat op als .jpg-file. Nadat je dit gedaan hebt, lees je ter voorbereiding op opgaven 4.2.7 en 4.2.8 de tekst over roteren en spiegelen van migische vierkanten, en het deel over de dimensie van de deelruimte van magische vierkanten nog eens door. Als je dit hebt gedaan ben je goed voorbereid voor de sessie van vrijdagochtend. Nadat je op vrijdag de eenvoudigere opgaven 4.2.5 en 4.2.6 hebt gemaakt, kan je aan de slag met opgaven 4.2.7 en 4.2.8. Ervaren programmeurs zijn vaak halverwege de vrijdagsessie al klaar met de opgaven. Speciaal voor hen zijn er nog twee moeilijke opgaven, 4.2.9 en 4.2.10 die facultatief maar wel leuk zijn. 9.3. Wat lever je in, wanneer, en hoe Je levert opgaven 4.1.1, 4.1.2, 4.1.3, 4.2.3, 4.2.5, 4.2.6 in op papier. De rest lever je per e-mail in, en wel als volgt: van opgave 4.2.4 stuur je alleen de jpg-file. Van opgave 4.2.7 de script-file (met hierin ook je vermoeden over de berekende resultaten als commentaar, dat wil zeggen, iedere regel hiervan begint met een procent-teken) en de jpg-file. Van opgave 4.2.8 alleen de scriptfile voor algemene waarden van n, met daarin ook als commentaar je vermoeden. In het bijzonder: stuur je werkgroepleider ´e´en e-mail, met daarin maximaal vier attachte files. Je levert alles in bij je werkgroepleider en zoals eerder gezegd, uiterlijk vrijdag om 12:45.
10. Beschrijving van de stof en opdeling van de opgaven voor week 10 Woensdag demonstreren we enkele belangrijke standaard constructies om de zogeheten flow van een Matlabprogramma te bepalen. Hieronder vallen de herhalingsstatements for-loop en de while-loop, waarvan de laatste gekenmerkt wordt door een conditie. Deze condities spelen ook een rol in de if-then-else-end constructie die keuzes kan bewerkstelligen tussen verschillende opties. Combinaties van deze paar mechanismen geven al een zeer grote flexibiliteit in het schrijven van computerprogramma’s. Als illustratie bekijken we in Sectie 4.3.4 de Collatzrijtjes, ook wel het 3x + 1 probleem genaamd. Ondanks dat het bewijzen van het Vermoeden van Collatz geen milleniumprobleem is, en dus geen miljoen dollar oplevert, zal de roem die een eventuele oplosser ten deel valt bijna vergelijkbaar zijn. 10.1. Thema: berekenen van de SVD middels slim gekozen vlakke rotaties De singulierewaardendecompositie (SVD) van een matrix A ∈ Rn×n is een matrixdecompositie met veel toepassingen. Omdat singuliere waarden gerelateerd zijn aan nulpunten van 2
polynomen kunnen deze voor n ≥ 5 niet meer in gesloten vorm worden bepaald, net zomin als voor eigenwaarden. Gegeven dit feit, hoe kom je dan in de praktijk aan de SVD van grotere matrices? We bekijken deze vraag eerst voor 2 × 2 matrices (waarvoor dergelijke formules nog w´el bestaan) in Sectie 4.4.3, nadat we in Secties 4.4.1 en 4.4.2 de 2 × 2 rotatiematrices en hun eigenschappen in de herinnering hebben geroepen. Het algoritme in Sectie 4.4.3 vermenigvuldigt A ∈ R2×2 afwisselend van links en van rechts met rotatiematrices. Omdat rotatiematrices unitair zijn, zullen de singuliere waarden na iedere vermenigvuldiging ongewijzigd blijven. We tonen aan dat er convergentie plaats vindt naar een diagonaalmatrix, waarvan de singuliere waarden triviaal de absolute waarden van de diagonaalentries zijn. Vervolgens laten we in Sectie 4.4.5 zien hoe een willekeurige n × k matrix A door middel van links- en rechtsvermenigvuldiging met hooguit (n − 2)k + 1 rotatiematrices, bidiagonaal kan worden getransformeerd. Behalve dat we onderzoeken hoe dit in Matlab kan worden bewerkstelligd, benadrukken we dat als je pen en papier en geduld hebt, je een matrix dus altijd volledig exact kunt bidiagonaliseren. En dat terwijl diagonaliseren alleen exact kan als n ≥ 4, en zelfs dan nog niet altijd. Tot slot laten we zien hoe je een iteratief proces kunt opzetten dat, heen-en-weer flippend tussen een boven-bidiagonaalmatrix en een onder-bidiagonaalmatrix, convergeert naar een diagonaalmatrix, waarvan de diagonaalentries in absolute waarde de singuliere waarden zijn van de oorspronkelijke n × k matrix A. 10.2. Jouw tijdsindeling en planning Op woensdag doe je actief mee met de Matlab-demonstraties. Je maakt aantekeningen van handige commando’s in de context van de flow van een programma, zoals loops en conditionele statements. Je ziet hoe je Collatz-rijtjes kunt bepalen met een niet al te ingewikkeld script, en hoe de resultaten te visualiseren. Verder kijken we in detail naar Givens-rotaties, rotaties die zich afspelen in twee-dimensionale vlakken in Rn . Deze rotaties vormen h´et ingredi¨ent van algoritmes, onder andere om eigenwaarden en singuliere waarden te berekenen, maar ook om kleinste kwadratenproblemen op te lossen (zie Numerieke Lineaire Algebra, jaar 3). Deze rotaties worden ook live gedemonstreerd, en je kan live meedoen met de demonstratie om gevoel te krijgen voor het onderwerp. De uitleg van de convergentie van het iteratieve proces om de SVD van een 2 × 2 matrix te bewijzen begrijp je, en je ziet in hoe dezelfde rotaties kunnen worden gebruikt om een matrix de bidiagonaliseren, en ook om singuliere waarden van grotere matrices te benaderen. Op donderdag maak je de opgaven 4.3.1, 4.3.2, en 4.3.3. Deze zijn bedoeld om je bewust te maken van de problemen die ontstaan als je lineaire algebra doet op een computer, in eindige precisie, zoals Matlab die in 16 decimalen rekent (16 is eindig). De limiet van differentiequoti¨enten zou de afgeleide in een punt moeten zijn, maar al rekenend blijkt dat slechts ten dele waar. Het Gram-Schmidt proces zou een orthonormale basis voor het opspansel van een gegeven stel vectoren moeten geven, maar Matlab maakt daar soms een potje van. Maar als dat zo is, hoe betrouwbaar is dan een industrieel ontwerpproces waarin software kritiekloos wordt gebruikt om een vliegtuig te ontwerpen? Durf je nog te vliegen na Opgave 4.3.3? Verder reproduceer je Voorbeeld 4.4.4 uit de Lecture Notes en maak je vervolgens de bijbehorende Opgaven 4.5.1, 4.5.2, en 4.5.3. Je reproduceert het voorbeeld dat begint op bladzijde 25, en maakt Opgave 4.5.4. Op vrijdag ben je goed voorbereid voor Opgaven 4.5.6-7-8.
3
10.3. Wat lever je in, wanneer, en hoe Van de opgaven aan het eind van Sectie 4.3 lever je van Opgaven 4.3.1 en 4.3.3 alleen het plaatje in. Opgaven 4.3.2 en 4.3.4 (inclusief tabel) lever je in op schrift. Van Sectie 4.5 lever je van 4.5.6 en 4.5.7 je code in (gebruik makend van het commando givens uit Opgave 4.5.2, of desgewenst met het alternatief planerot). De vragen in Opgaven 4.5.6 en 4.5.7 om je code te testen beantwoord je door voor een door jouw gekozen matrix A met Opgave 4.5.7 zijn bidiagonaal-gedaante B te berekenen, en die iteratief met 4.5.6 op diagonaalvorm C te transformeren. Kopieer A en B en C vanuit Matlab als commentaar in je code voor Opgave 4.5.7. Vergelijk de door jouw code berekende singuliere waarden expliciet met de singuliere waarden van A die door Matlab middels svd(A) worden berekend, door deze laatste eveneens als commentaar toe te voegen aan Opgave 4.5.7. Samengevat e-mail je je werkgroepleider dus twee jpg-files, en twee m-files, en lever je de rest of op schrift in, of als je wilt als vijfde bestand per e-mail, uiterlijk vrijdag om 13:00.
11. Beschrijving van de stof en opdeling van de opgaven voor week 11 We bekijken Matlab function files, en hoe je daarmee ook recursieve functies kunt implementeren. Recursie is vaak een elegante, en soms ook erg effici¨ente wijze om een oplossing voor een probleem te verkrijgen. Daarnaast maken we kennis met de Matlab profiler, verstopt onder het pull-down menu genaamd desktop van Matlab. Door een commando uit te voeren in de command line van de profiler, krijg je na executie van de code een rapport dat een analyse van de code bevat: hoe lang deze draaide, hoe vaak bepaalde regels werden aangeroepen, enzovoorts. De profiler is onontbeerlijk bij het verbeteren en stroomlijnen. Opgaven waarbij deze onderwerpen centraal staan zijn 4.6.1 t/m 4.6.5. De laatste hiervan is interessant omdat het zoel je kennis van de Schurdecompositie test, als je begrip van recursie. 11.1. Thema: het detecteren van reducibiliteit middels rij- en kolompermutaties Het wiskundige thema van deze week is reducibiliteit. Niet alle matrices die veel nullen bevatten zijn reducibel. Het vergt enige moeite, vooral bij wat grotere matrices, om erachter te komen of deze nullen wel op de juiste plaats staan opdat de betreffende matrix reducibel is. We bekijken drie verschillende algoritmes om de rijen en kolommen van een matrix zodanig te permuteren, dat er nullen komen te staan in kolommen 1, . . . k, rijen n − k + 1, . . . n. Dit is dus een (linksonder-)blok nullen van afmetingen (n − k) × k. We kiezen ervoor om op zoek te gaan naar de waarde van k waarvoor het product (n − k)k maximaal is: een zo groot mogelijk blok met nullen. Hiervoor hebben we natuurlijk een functie nodig die, gegeven een matrix A, vertelt wat het grootste (n − k) × k linksonderblok met nullen in A is, indien er dergelijke blokken in A bestaan. Dit gebeurt in Opgave 4.7.1, waarna je gewapend met deze functie, de drie algoritmes implementeert in opgaven 4.7.2, 4.7.3, en 4.7.4. Vervolgens zullen we in Opgave 4.7.6 de matrix recursief verder transformeren, zodanig dat de nulstructuur optimaal zichtbaar is. Opgave 4.7.5 is een bonusopgave. Het eerste correcte bewijs of tegenvoorbeeld verdient een element uit het carthesische product (bloemen,wijn) X (rood,wit) naar keuze.
4
11.2. Jouw tijdsindeling en planning Bij de Matlabdemonstratie op woensdag ben je aandachtig bezig om de recursieve voorbeelden (sommeren, permuteren) te begrijpen en gevoel te krijgen voor het concept. Daarnaast neem je wat nuttige informatie tot je betreffende reducibiliteit en permuteren van rijen en kolommen van matrices, en zie je de drie algoritmes die worden voorgesteld om een matrix optimaal, met een zo groot mogelijk (n−k)×k blok met nullen, op blok-bovendriehoeksvorm te brengen, oftewel, een matrix van de vorm A B , met A en C vierkant. 0 C Op donderdag oefen je met het concept recursie en maak je de opgaven 4.6.1 t/m 4.6.5. De eerste drie hiervan vragen nauwelijks om programmeren, en des te meer om kritisch te kijken naar gegeven programma’s met behulp van de Matlab profiler. Opgave 4.6.5 is de lastigste, maar geeft als resultaat een code die kan concurreren van Matlab’s ingebouwde functie schur. Het kan geen kwaad ook al naar Opgave 4.7.1 te kijken. Op vrijdag implementeer je de drie algoritmes in Opgaven 4.7.2, 4.7.3, en 4.7.4 en vergelijk je hun snelheden met de Matlab profiler. Tot slot denk je na over recursief verder reduceren van je matrix en maak je Opgave 4.7.6. Tijd en/of ambitie over? Probeer ook Opgave 4.7.5! 11.3. Wat lever je in, wanneer, en hoe De tabellen met commentaar van Opgaven 4.6.2 en 4.6.3 lever je in op schrift, evenals je aangepaste versie van het programma Pascal.m. De code MySchur.m uit Opgave 4.6.5 stuur je op als m-file, en zo ook de m-files van Nullen.m, Reduce1.m, Reduce2.m, Reduce3.m uit Opgaven 4.7.1 t/m 4.7.4. Op schrift vermeld je hoe groot de matrices maximaal zijn die je met deze codes binnen tien seconden nog kon reduceren. Tot slot stuur je de m-file van de recursieve functie uit Opgave 4.7.6 op. Samengevat stuur je deze week dus zes m-files op, en de rest op schrift, voor vrijdag 12:45.
12. Beschrijving van de stof en opdeling van de opgaven voor week 12 Deze week komen er geen echt nieuwe Matlab functionaliteiten meer aan bod. Wel zullen we een wat moelijker lineair-algebra¨ısch thema bekijken dan in de eerste drie weken. 12.1. Thema: de permanent: eigenschappen, berekening, en P=NP De permanent is het lastige kleine broertje van de determinant. Enerzijds is de permanent eenvoudiger te defini¨eren, omdat je geen rekening hoeft te houden met min-tekens; anderzijds zorgt het ontbreken van deze min-tekens er nu juist voor dat de permanent van een matrix A met twee gelijke kolommen niet altijd gelijk is aan nul. Dit heeft tot gevolg dat de permanent niet imddels rijvegen bepaald kan worden. De tot op heden snelst bekendste methodes om per(A) van A ∈ Rn×n uit te rekenen hebben exponentieel veel tijd nodig in n: ongeveer O(2n ) vermenigvuldigingen en optellingen. Toegegeven, dat is beter dan O(n!) (zoals we vorige week bij het reduceren van een matrix al merkten) maar in vergelijking met de O(n3 ) die nodig is om de determinant uit te rekenen is het een zeer matig resultaat. Er wordt breed verondersteld dat het niet mogelijk is om per(A) uit te rekenen in O(p(n)) tijd, waarbij p 5
een polynoom is van ´e´en of andere willekeurige, maar vaste graad. Zou dit wel lukken, dan zou dat betekenen dat zo ongeveer alle belangrijke exponenti¨ele tijd vergende algoritmes ook tot polynomiale tijd verbeterd zouden kunnen worden, oftewel, dat de complexiteitsklassen P en NP aan elkaar gelijk zijn. Bewijzen of dat al dan niet zo is levert een miljoen dollar op: het is ´e´en van de zeven Milleniumproblemen uit de wiskunde. Tot slot beschouwen we ´e´en van de bekendste wiskundige inmiddels-niet-meer-open-problemen vernoemd naar een Nederlands wiskundige, namelijk het vermoeden van Van de Waerden. Deze beweerde dat de permanent, gezien als functie op de verzameling van alle dubbelstochstische matrices, zijn absolute minimum aanneemt op de constante dubbelstochastische matrix, voor iedere vaste afmeting. Dit lijkt intu¨ıtief duidelijk (als je er even over nadenkt) maar toch duurde het ruim een halve eeuw voordat het rond 1980 werd bewezen. 12.2. Jouw tijdsindeling en planning Op hoorcollege defini¨eren we de permanent en bekijken enkele eenvoudige eigenschappen. Deze komen voornamelijk voort uit de combinatoriek en de discrete wiskunde. We bekijken hoe de permanent uitgerekend kan worden, vervolgens hoe dat iets sneller kan, waarna we het algoritme van Ryser in detail bestuderen. Dit laatste algoritme heeft lang bekend gestaan als de snelste manier om de permanent te berekenen, maar deze eer lijkt inmiddels te zijn overgegaan op andere formules (die overigens ’slechts’ een constante factor sneller zijn). Zonder verder bewijs presenteren we de formule van Glynn uit 2010 om de permanent te berekenen. Na hoorcollege maak je de eenvoudigere opgaven 4.8.1 en 4.8.2, die niets met programmeren van doen hebben, maar wel inzicht in de materie geven. Opgave 4.8.3 zal verderop nuttig blijken, en vereist niet veel meer dan kennis van recursie. Opgave 4.8.4 is de eerste opgave waarin de permanent wordt berekend, en wel direct uit de definitie, wat niet erg effici¨ent is, maar weinig programmeervaardigheid vereist. Ook de methode van ontwikkeling naar rijen of kolommen, geheel in analogie naar de berekening van de determinant, is een erg trage methode. Zie Opgave 4.8.5. De snellere methoden van Ryser en Glynn zijn het centrale deel van de programmeeropgaven, die het best onder begeleiding op vrijdag gemaakt kunnen worden. Beide zijn slimme truuks om bepaalde grootheden in een alternatieve volgorde te berekenen. Alleen van de methode van Ryser doen we een poging deze duidelijk te maken. De methode van Glynn is een formule die op Wikipedia wordt gepresenteerd als een misschien sneller alternatief voor Ryser. Het woordje misschien verdient onze aandacht. Door beide algoritmes te implementeren in Matlab (Opgaven 4.8.6 en 4.8.7) en te draaien voor enkele voor de hand liggende voorbeelden, kunnen we deze claim nader onderzoeken (Opgave 4.8.8). In Opgave 4.8.9 en 4.8.10 onderzoek je het vermoeden van van der Waerden door de permanent uit te rekenen van een aantal random gegenereerde dubbelstochastische matrices. 12.3. Wat lever je in, wanneer, en hoe Opgaven 4.8.2, 4.8.3 en 4.8.8 (tabel met commentaar) lever je in op schrift. De functie van 4.8.3 kan je desgewenst inbouwen in je code voor Opgave 4.8.7, of je kan deze code aanroepen vanuit perm4. Verder stuur je de m-files perm1, perm2, perm3, perm4 uit Opgaven 4.8.4, 4.8.5, 4.8.6, en 4.8.7 op. Ook stuur je je m-file op van Opgave 4.8.9 en tot slot je gepersonaliseerde plaatjes van Opgave 4.8.10. Samengevat dus 3 jpg-files, en 5 functies, en de rest op schrift. 6
