Beräkningsvetenskap (f.d. Numerisk analys)

Matematiska institutionen, MAI

Här forskar man bl.a. kring algoritmer för lösning av linjära ekvationssystem. Vid omfattande simuleringar av teknisk eller vetenskaplig natur går en stor del av tiden till ekvationssystemlösning. Ett annat forskningsområde är inversa problem, som kan användas exempelvis för att rekonstruera bilder. Ett välkänt exempel där bildrekonstruktion används är vid skiktröntgen inom medicinen. Forskarna utvecklar också numeriska algoritmer för användning inom signalbehandling. Ämnesföreträdare är Lars Eldén.

 

Numerisk linjär algebra

Mer än 80% av beräkningstiden för stora tekniska och vetenskapliga simuleringar går till lösning av linjära ekvationssystem eller s.k. egenvärdesproblem. Denna proportion har i stort sett varit oförändrad de senaste 30 åren. Detta ställer stora krav på effektivitet, stabilitet och robusthet hos lösningsmetoderna. Förbättringar av algoritmerna för lösning av matrisproblem är därför av stor betydelse.

En snabb utveckling sker av datorsystemen mot vektor- och parallellprocessorer samt minneshierarkier på flera nivåer. Detta medför att traditionella algoritmer måste omstruktureras och optimeras för de nya arkitekturerna. Storleken på de problem som löses ökar också kraftigt. Inom flygplans- och bilkonstruktion, petroleumindustri och kemisk industri samt halvledarkonstruktion förekommer idag inte sällan simuleringar av system med en miljon eller fler obekanta. Nya tillämpningsområden har tillkommit - biomedicin, modellering av finansiella instrument, "data mining" samt, mer exotiskt, animering av filmer. Dessa stora problem kan inte lösas med direkta metoder som exempelvis bygger på s.k. Gausselimination även om strukturen på systemen utnyttjas. I stället måste approximativa direkta lösningsmetoder kombineras med iterativa metoder. Tyvärr finns ingen universell teori för dessa metoder och de är heller ännu inte tillräckligt robusta.

Inom numerisk linjär algebra utvecklas generella algoritmer och matematisk programvara som har mycket bred användning. En trend det senaste decenniet är mot s.k. "verktygslådor" med programvara, som kan användas interaktivt med stöd av god grafik. En stor del av utvecklingen sker emellertid i symbios med olika tillämpningsområden. Så har exempelvis reglerteknik och signalbehandling berikat linjär algebra med nya problemställningar, samtidigt som dessa områden själva utvecklats kraftigt genom införandet av moderna algoritmer från numerisk linjär algebra. Andra aktuella områden där en liknande utveckling skett är bildbehandling och tomografi.

Ovanstående beskrivning ger en förklaring till varför numerisk linjär
algebra fortfarande är ett centralt och vitalt matematiskt forskningsområde.
Ett problem, som ämnet delar med matematik i allmänhet, är att det sällan
får del av förtjänsten av tekniska och vetenskapliga framsteg trots att
matematiken ofta har haft en viktig del i dessa.

Inversa (illa ställda) problem

Fransmannen Hadamard definierade i början av detta sekel vad som menas med att ett problem är rätt ställt. Hans definition är, något förenklad och utan matematiska formler:

- problemet skall ha entydig lösning

- små störningar i problemets indata skall ge små ändringar i lösningen

Ett problem i den klass som inte uppfyller Hadamards villkor kallas illa ställt. En alternativ benämning är inverst problem. I själva verket finns det en skala av sådana problem. Det går alltså att kvantifiera begreppet illa ställt problem och därigenom avgöra om ett problem är mer illa ställt än ett annat. Under de senaste årtiondena har det framkommit flera olika tillämpningar där inversa problem uppträder. För att definiera entydiga och stabila lösningar krävs olika former av tilläggsvillkor.

Vi ger några exempel på inversa problem och börjar med bildrekonstruktion. Med detta menas en teknik för att undersöka ett objekts inre struktur genom att utsätta objektet för någon typ av strålning. Vidare antas att strålningen utbreds längs en rät linje genom objektet. Ett välkänt exempel är skiktröntgen inom medicinen, som utförs med en datortomograf. I tomografen finns mjukvara som bygger på en inversionsmetod. Utifrån den uppmätta strålning som passerat genom objektet räknar man fram den struktur som gav upphov till dessa mätdata. Beroende på hur mycket mätdata som finns är problemet mer eller mindre illa ställt. Med ett ändligt antal indata (som man ju i praktiken alltid måste ha) finns det i själva verket oändligt många strukturer som kan ge upphov till dessa. Ett fall där det kan vara svårt att få tillräckligt mycket data är när man på grund av patientens allmänna hälsoläge vill ge en minskad strålningsdos. I sådana fall fungerar inte standardmetoden för inversion så bra. I stället kan man använda s.k. algebraiska inversionsmetoder . De har bl.a. fördelen att tilläggsvillkor relativt lätt kan införas, t.ex. i form av undre och övre gränser på strålningsintensiteten. Sådana tilläggsvillkor är speciellt viktiga när man vill säkerställa en bra bildkvalitet trots att antalet data är litet.

Området bildrestaurering omfattar en annan typ av bildproblem. Här består de givna data av en bild eller en serie av bilder som har utsatts för någon typ av degradering, t.ex. rörelseoskärpa eller ofrivilliga kamerarörelser under exponeringen. En annan typ av degraderade bilder kommer från satelliter. Vid överföring till jorden kan atmosfärens turbulens degradera bildsignalen. I denna klass av problem utgör ett viktigt första steg att matematiskt modellera själva degraderingsprocessen. Nästa steg blir då att försöka räkna fram den ursprungliga bilden. I praktiken kombineras ofta dessa två steg (eng. "blind deconvolution" ). Det finns flera föreslagna metoder för rumsoberoende degradering, vilket innebär att alla bildpunkter har degraderats på samma sätt. Detta är emellertid ofta ett orealistiskt antagande. Inom forskargruppen studeras därför metoder för restaurering av bilder som utsatts för rumsberoende degraderingar.

Inversa problem förekommer också i samband med värmeledning. Antag att man vill ta reda på temperaturen i en ugn eller förbränningskammare, där temperaturen är så hög eller miljön så aggressiv att en värmesensor snabbt skulle förstöras. Man placerar då i stället sensorn en bit in i materialet, löser en s.k. differentialekvation (i detta fall värmeledningsekvationen) och beräknar på så sätt temperaturen på det önskade stället. Detta problem är illa ställt på grund av att ett stort antal mycket olika temperaturfördelningar kan ge upphov till närliggande data. Problemet kan lösas endast genom att man använder extra antaganden om att lösningen är "snäll'' i någon mening. Läs mer om det matematiska problemet.

Ett tredje exempel är ytrekonstruktion med formbevarande. Här utgörs data av ett antal uppmätta höjdvärden. Utifrån detta vill man finna värden i mellanliggande punkter. I vissa tillämpningar, t.ex. vid konstruktion av ytor inom bilindustrin, önskar man att den framräknade ytan inte bara är en bra anpassning till givna data utan också har viss form, t.ex. att den är konvex i vissa delar. Just detta problem och motsvarande endimensionella problem studeras inom gruppen.

Numeriska algoritmer inom signalbehandling

När man vill simulera en process eller reglera ett system behövs en matematisk modell för att beskriva händelseförloppet. En sådan modell byggs upp utifrån data från mätningar av signaler i det aktuella systemet. Eftersom man aldrig kan uppnå idealiska förhållanden finns det alltid slumpmässiga fel i mätvärdena, så kallat brus. Detta gör att man aldrig kan bestämma modellerna exakt.

I ett par forskningsprojekt studeras numeriska metoder för att eliminera bruset. Mätvärdena arrangeras i en matris och genom att beräkna en så kallad partiell singulärvärdesfaktorisering av matrisen kan man approximera det signalrum ur vilket modellen bestäms. Man studerar också metoder för att på ett effektivt sätt uppdatera signalrumsapproximationen då nya data kommer in eller systemet förändras. De nyutvecklade metoderna är mycket snabbare än de algoritmer som man finner i standardbibliotek.

Sidan skapades 1999-03-22