Transformer för beräkningar

Transforms in Computing

Mars - maj 2001, Christer Kiselman och Henrik Brandén

Huvudlärobok är

• Michael W. Frazier, An Introduction to Wavelets Through Linear Algebra, Springer, 1999.

• Sigurdur Helgason, The Radon Transform, Birkhäuser, 1999;
• Jean-Pierre Kahane och Pierre Gilles Lemarié-Rieusset, Séries de Fourier et ondelettes, Cassini, 1998;
• N. N. Lebedev, Special Functions and Their Application, Dover Publications, Inc., New York 1972; och
• H. Groemer, Geometric Applications of Fourier Series and Spherical Harmonics, Cambridge: Cambridge University Press, 1996.

Mål för utbildningen
Kursen syftar till en djupare förståelse för den diskreta Fouriertransformen, utvecklingar i ortogonala baser, liksom för andra transformer, såsom Radontransformen och olika wavelettransformer. Laborationerna syftar till förtrogenhet med alla beräkningarsmässiga aspekter hos dessa transformer.

Kursens innehåll
Den snabba Fouriertransformen. Wavelets och utveckling i olika baser av waveletfunktioner. De klassiska ortogonala funktionssystem som är förknippade med namnen Hermite, Legendre, Jacobi, Tjebysjov, Bessel och Hankel. Radontransformen.

Ordlista
Jag har gjort en ordlista till kursen med några av de termer som förekommer. Den delades ut den 6 april och kan hämtas här. DVI - PS - PDF. De svenska och engelska termerna utgör en obligatorisk del av kursen. Övriga språk är frivilliga.

Föreläsningar och laborationer
Här nedan står det T för föreläsningar (32 timmar, Christer; om ingen tid anges avses alltid 10:15-12:00 - enda undantaget är den 17 maj) och t för laborationer (16 timmar, Henrik). Här redovisas vad som gjorts och (under strecket) vad som planeras.

T1, 21 mars: Kan örat Fouriertransformera? Tid och frekvens. Lagring av fingeravtryck. Representation av signaler med hjälp av Fourierserier och wavelettransformer. Repetition av lineär algebra. Kropparna Q, R, C. Konvergenta följder och serier. Övningar, blad 1, 2001 03 21, delades ut och kan även hämtas här. DVI - PS - PDF.

T2, 23 mars: Moduler över en ring. Vektorrum över en kropp, speciellt R och C. Lineära avbildningar. Baser. Representation av avbildningar medelst matriser. Matriser som representerar samma lineära avbildning: similära matriser. Egenvärden. Matriser utan reella egenvärden.

T3, 28 mars: Egenrum. Egenvektorer. Geometrisk multiplicitet hos ett egenvärde. Algebraisk multiplicitet hos ett egenvärde. Jordans normalform. Inre produkter. Cauchy-Schwarz' olikhet. Triangelolikheten. Projektioner. Ortogonala projektioner.

T4, 30 mars: Ortogonala baser. Hermiteska, unitära och normala matriser. Data är ofta indicerade med cykliska index, vilket leder oss att studera de cykliska grupperna av ändlig ordning: den cykliska gruppen av ordning N betecknas Z_N och är lättast att beskriva som ett kvotrum av gruppen av alla heltal, nämligen Z_N = Z/NZ. Faltningsalgebran på Z_N. Faltningsoperatorer karaktäriseras som lineära operatorer som kommuterar med translationer. Faltningsoperatorer karaktäriseras som lineära operatorer som representeras av cykliska matriser.

T5, 4 april: Den diskreta Fouriertransformen. Fouriertransformen av en faltning är produkten av faktorernas Fouriertransformer. Fouriers inversionsformel. Parsevals relation och Plancherels formel. Exempel på Fouriertransformer. Karaktärisering av translationsinvarianta lineära operatorer medelst Fouriertransformen. Diagonalisering av cykliska matriser. Övningar, blad 2, 2001 03 30, delades ut och kan även hämtas här. DVI - PS - PDF.

T6, 5 april: Exempel på diagonalisering av cykliska matriser. När är svängningarna snabbast? Den snabba Fouriertransformen då N är en potens av 2. Hur många multiplikationer behövs för att Fouriertransformera?

T7, 6 april: Dimensionskalkyl i anslutning till övningsuppgifterna 1.5 och 1.6. Faltning på Z_N jämfört med Z. Beräkning av en faltningsprodukt medelst FFT. Första steget mot fraktala baser.

T8, 18 april: Systemmatrisen A(n) för två vektorer u och v. Systemmatrisen är unitär precis när de jämna translaten av u och v bildar en ON-bas. Första etappens Haarbas. Första etappens Shannonbas. Första etappen för den reella Shannonbasen. Övningar, blad 3, 2001 04 16, delades ut och kan även hämtas här: DVI - PS - PDF.

t1, 19 april: Henrik diskuterade implementationer av den snabba Fouriertransformen, även då N inte är en potens av 2.

t2, 19 april: Henrik handledde den första laborationen, som handlar om den snabba Fouriertransformen.

T9, 20 april: Upplösning av signaler: den analyserande svarta lådan. Den syntetiserande svarta lådan. Perfekt rekonstruktion av signaler genom en analyserande och en syntetiserande svart låda. Wavelet-filterföljder på stadium p. Wavelets.

T10, 25 april: Haarbasen. Shannonbasen; den modifierade (reella) Shannonbasen. Ingrid Daubechies' bas D6. Jämförelse mellan olika baser: euklidisk, Fourier, Shannon, D6; vilken ger bästa resultatet vid kompression? Formelsamlingen (dock endast t.o.m. kapitel 13) delades ut. Se vidare nedan för den 7 maj.

t3, 26 april: Henrik talade om snabba trigonometriska transformer, till exempel den diskreta sinustransformen, och hur dessa kan användas för att konstruera snabba ekvationssystemslösare. I den andra inlämningsuppgiften skall en sådan lösare implementeras i MatLab.

t4, 26 april: Henrik handledde den andra laborationen.

T11, 27 april: Rummet l¹(Z) av alla summabla följder och rummet l²(Z) av alla kvadratsummabla följder på heltalen. Faltning av sådana följder. Olikheter i l^p-norm för faltningar. Fouriertransformationen från l²(Z) till L²([-pi,pi[) och dess invers.

T12, 2 maj: Genomgång av faltning i rummen l^p(Z). Hamelbaser och Schauderbaser. Operatorer som kommuterar med translationer och hur de kan representeras: Fouriertransformationen diagonaliserar dem. Wavelet-baser på Z.

t5, 3 maj: Henrik diskuterade implementationen av filterbanktransformer, vilket är uppgiften för den tredje laborationen.

t6, 3 maj: Henrik handledde den tredje laborationen.

T13, 4 maj: Haar-basen på Z. Daubechies' bas D6. Faltning på reella axeln. Fouriertransformationen på reella axeln.

T14, 7 maj: Wavelet-baser på reella axeln. Mallats sats. Övningar, blad 4, 2001 05 04, delades ut och kan även hämtas här: DVI - PS - PDF. Tentan från 2000 08 23 delades ut. (Se nedan under den 17 maj.) Formelsamlingen delades ut och kan även hämtas här: DVI - PS - PDF.

T15, 11 maj: Ortogonala polynom: Legendre-, Hermite-, Laguerre-, Tjebysjov- och Jacobipolynomen. Definition, induktionsformler, genererande funktion och differentialekvationer som polynomen uppfyller. Tjebysjovpolynomens betydelse för approximation i supremumnorm.

t7, 15 maj: Henrik diskuterade pseudospektrala metoder för numerisk lösning av differentialekvationer. Metoderna är baserade på utvecklingar i ortogonala polynom.

t8, 15 maj: Henrik handledde den fjärde laborationen.

T16, 17 maj: Radontransformationen. Tentan från 2000 05 22 delades ut, nu med svar: DVI - PS - PDF; liksom tentan från 2000 08 23, nu med svar: DVI - PS - PDF.

21 maj: Tentamen. Resultatet blev som väntat mycket bra. Av 16 skrivande fick 10 betyget fem och 6 betyget fyra. För godkänt betyg på hela kursen fordras dock även att alla uppgifter som Henrik delat ut har lösts till belåtenhet. Tentan 2001 05 21 med svar finns nu att hämta här: DVI - PS - PDF.

7 juni: Omtentamen. Resultatet blev som väntat mycket bra. Av 8 skrivande fick 5 betyget fem och 3 betyget fyra. För godkänt betyg på hela kursen fordras dock även att alla uppgifter som Henrik delat ut har lösts till belåtenhet. Tentan 2001 06 07 med svar finns nu att hämta här: DVI - PS - PDF.

24 augusti: Omtentamen. Det finns inte många som inte klarat sig i maj eller juni.

Christer