T825

Promotor: Marc Van Barel en Adhemar Bultheel
Begeleider: Karl Deckers

A is een discretisatie is van de operator -0.1Δ = -0.1(∂x² + ∂y²) (Laplace in 2D) en q is een discretisatie van de functie x(1-x)y(1-y) op het gebied [0,1] x [0,1] met dx = dy = 1/51. Een benadering van de vorm voor de functie met t = 0.01.

relatieve fout van de benadering

Het gebruik van Krylov deelruimten (KDn) is tegenwoordig zeer populair bij het zoeken van numerieke benaderingen voor de vector u = f(A)q, waarbij q een gegeven vector, A een N × N reëel positief-definiete matrix, en f(a) een gegeven functie (bijv. 1/√(a), exp(-t√(a),...) is. Dergelijke functies vindt men o.a. terug bij het oplossen van stelsels differentiaalvergelijkingen (SDVn). Het zoeken van de beste benadering voor u in een KD van dimensie n ≤ N komt dan overeen met het zoeken van de beste veeltermbenadering voor f(a) van graad kleiner of gelijk aan n.

Een nadeel van veeltermbenaderingen is dat deze over het algemeen zeer traag kunnen convergeren naar de eigenlijke functie f(a) naarmate de graad toeneemt. Een aanzienlijke verbetering kan echter bekomen worden door gebruik te maken van rationale benaderingen van de vorm R_n(a)=p_n(a)/[(a-α)...(a-α_n)], waarbij p_n(a) een veelterm is van graad kleiner of gelijk aan n en de α_i's de polen zijn. Dit komt dan overeen met het zoeken van een beste benadering voor u in rationale Krylov deelruimten (RKDn).

Voor dit eindwerk beperken we ons tot het geval dat de matrix A symmetrisch is. Net zoals in het veeltermgeval, kunnen de orthonormale vectoren (OVn), die de RKDn opspannen, berekend worden d.m.v. een 3-term recursiebetrekking. Op deze manier bekomen we het rationale Lanczos algoritme, gebaseerd op het verband dat bestaat tussen de OVn en orthonormale rationale functies (ORFs). De nulpunten van deze ORFs, die gevonden worden als oplossing van het veralgemeend eigenwaarden probleem, zijn benaderende waarden voor de eigenwaarden van A, en dienen bijgevolg als interpolatiepunten.

Het doel van dit eindwerk is om tot een efficiente implementatie te komen van dit rationale Lanczos algoritme en het veralgemeend eigenwaarden probleem. Vervolgens kan de rekenkost onderzocht worden in functie van N (de matrix-grootte), n (het aantal iteraties) en p (het aantal verschillende polen). Voor het oplossen van SDVn kan, tot slot, gegeven een functie f(a) (of een klasse van functies), onderzocht worden hoe men tot een optimale set van polen kan komen, en welke convergentiesnelheid men daarbij dan mag verwachten.

Afhankelijk van de interesse van de student, kan dit eindwerk eerder implementatiegericht ofwel theoretisch gericht zijn.

Convergentiesnelheid rationale benadering van de vorm Rn(a) = pn(a)/[(a+0.6)(a+100)n-1]