Les méthodes itératives de résolution des systèmes d'équations non linéaires peuvent être classifiées. Cette classification permet de les retrouver toutes dans un cadre unifié et d'en obtenir d'autres.

Le but de ce travail est d'étudier ces méthodes et cette classification.

On particularisera ensuite cette classification au cas des systèmes d'équations linéaires afin, d'une part, de comprendre comment se répartissent les méthodes itératives connues et, d'autre part, d'étudier si des méthodes nouvelles en émergent.

Des documents seront fournis.

Il existe des procédés pour estimer l'erreur quand on connaît une approximation de la solution d'un système d'équations linéaires.

Or, quand on sait estimer l'erreur d'une suite convergente, on sait accélérer sa convergence.

Le but de ce travail est d'étudier les procédés d'accélération de la convergence des méthodes itératives de résolution des systèmes d'équations linéaires qui découlent de telles estimations de l'erreur. Cette étude devra être réalisée tant sur le plan théorique que sur le plan expérimental.

Des documents seront fournis.

Lorsqu'on veut résoudre numériquement une EDO sur un intervalle [a,b]  (a,b Î \mathbb R ,  a < b), la première étape consiste typiquement à découper cet intervalle en sous-intervalles, en commençant par une décomposition grossière que nous supposons équidistante:

Une telle approche est souvent possible lorsqu'on discrétise des EDO. Par contre, une EDP est posée sur un domaine de \mathbb R ⁿ, avec n Î \mathbb N, n ³ 2, au lieu d'un intervalle, et on obtient des solutions approchées d'une EDP à partir de décompositions - appelées ``grilles'' - d'un tel domaine. Ces décompositions mènent souvent à des systèmes linéaires dont la résolution est très gourmande en temps de calcul lorsqu'on fait tourner une méthode itérative jusqu'au niveau de l'erreur de discrétisation.

Dans beaucoup de situations, les méthodes multigrilles permettent de contourner ce problème. Dans le cas des systèmes linéaires introduits ci-dessus, une telle méthode consiste à effectuer seulement quelques pas d'une méthode itérative appliquée à chaque système avec indice l Î {2, ..., k} , et de ne résoudre exactement que le système à indice l = 1, c'est-à-dire, le système à la taille la plus petite. Afin qu'une telle approche donne un résultat, les deuxièmes membres de tous les systèmes à l'exception de celui à indice k doivent être modifiés, et il faut appliquer une méthode itérative aux systèmes à indice 2 à l dans un ordre approprié.

Un mémoire sur les méthodes multigrilles traiterait les aspects suivants:
· description et analyse de la méthode par référence à un problème modèle dont on connaît des solutions approchées explicites;
· définition de méthodes multigrilles liées à des problèmes variationnels; démonstration de la convergence de ces méthodes;
· éventuellement la programmation d'une méthode multigrille pour résoudre un problème modèle.
· Si le mémoire comporte une partie de programmation, on pourrait bien sûr en diminuer la partie théorique.

Références:

D. Braess: Finite elements. Cambridge University Press, 1997.

S. C. Brenner, L. R. Scott: The mathematical theory of finite element methods. Springer, 1994.

A. Quarteroni, A. Valli: Numerical approximation of partial differential equations. Springer, 1994.

Une solution du système de Navier-Stokes incompressible stationnaire peut être considérée comme un point fixe d'une application entre certains espaces de Banach. Ce point de vue donne lieu à des estimations de l'erreur qui surgit lorsqu'on discrétise le système de Navier-Stokes par des méthodes d'éléments finis mixtes.

Un mémoire sur ce sujet consisterait essentiellement d'une démonstration de ces estimations d'erreur.

Références:

V. Girault, P.-A. Raviart: Finite element methods for the Navier-Stokes equations. Springer, Berlin e.a., 1986.

A. Quarteroni, A. Valli: Numerical approximation of partial differential equations. Springer, Berlin e.a., 1994.

On considère un domaine extérieur [`( W)]<sup>c</sup>: = \mathbb R <sup>3</sup> \[`( W)], où W Ì \mathbb R ³ est un domaine borné. Le calcul variationnel fournit une solution faible (u,p) du système de Navier-Stokes incompressible stationnaire

Le mémoire que je propose traite le comportement asymptotique de u et p pour |x| ® ¥. Il s'agit de démontrer que u, Ñu et p appartiennent à certaines espaces L^p et remplissent certaines estimées en norme L^p .

Références:

Galdi, G. P.: On the asymptotic structure of D-solutions to the steady Navier-Stokes equations in exterior domains. Dans: Galdi, G. P. (ed.): Mathematical problems related to the Navier-Stokes equations. Advances in Mathematics for Applied Sciences 11, World Scientific 1992, 81 - 105.

Galdi, G. P.: An introduction to the mathematical theory of the Navier-Stokes equations. Vol. II. Nonlinear stationary problems. Springer, New York e.a., 1994.

Joachim von Below
Université du Littoral
Joachim.von.Below@lmpa.univ-littoral.fr

Stabilité de solutions non constantes stationnaires des équations d'évolution non linéaires, d'après N. Cònsul & J. Solà-Morales, Stability of local minima and stable nonconstant equilibria, J. Differential Equations, 157 (1999) 61-81.

Méthodes des différences finies pour les équations paraboliques, d'après J. W. Thomas, Numerical PDE Chap. 4 pp. 147-203, L. Collatz, The numercial treatment of PDE 1960, Th. Meis & P. Markowitch Numercial solution of PDE e.a.

Le laplacien sur un réseau topologique, d'après Joachim von Below, A characteristic equation associated to an eigenvalue problem on c²-networks, Linear Algebra and its applications, 71 (1985) 309-325, e.a.

Résumé : La méthode ADI standart de résolution iterative de l'équation matricielle de Sylvester A X - X B = C produit une suite d'approximations X\sb j, j = 1,2,¼, vers la solution exacte X, en alternant entre les 2 equations de base

Le Bailly, B.; Thiran, J. P. Optimum parameters for the generalized ADI method. Numer. Math. 80 (1998), no. 3, 377-395.

Le Bailly, B; Thiran, J. P., Optimal rational functions for the generalized Zolotarev problem in the complex plane. SIAM J. Numer. Anal. 38 (2000), no. 5, 1409-1424

Levin, A. L.; Saff, E. B. Optimal ray sequences of rational functions connected with the Zolotarev problem. Constr. Approx. 10 (1994), no. 2, 235-273.

Starke, G., Fejér-Walsh points for rational functions and their use in the ADI iterative method. Computational complex analysis. J. Comput. Appl. Math. 46 (1993), no. 1-2, 129-141.

Varga, Richard S. Matrix iterative analysis. Springer Series in Computational Mathematics, 27. Springer-Verlag, Berlin, 2000.

Méthodes iteratives pour l'approximation des espaces propres d'une matrice hamiltonniene

Beaucoup d'applications requièrent l'approximation numérique des espaces propres (valeurs et vecteurs propres) d'une matrice hamiltonienne. C'est le cas par exemple des équations de Riccati dans la théorie du controle. Une matrice hamiltonienne a une structure particulière. Dans [1,2], des méthodes itératives ont été proposées pour l'approximation d'un espace propre d'une matrice hamiltonienne creuse et de grande taille, avec une certaine optimalité.

L'objet de ce mémoire est de faire une synthèse des travaux [1,2] et de mettre en oeuvre une comparison numérique des methodes qui s'y trouvent.

Ce travail peut déboucher sur un sujet de thèse.

Keywords: Linear systems, Krylov subspace methods, symplectic Lanczos methods, Hamiltonian matrix eigenvalue problem.

[1] P. Benner, and H. Fažbender, An Implicitly restarted symplectic Lanczos method for the Hamiltonian eigenvalue problem, 263 (1997) 75-111.

[2]A. Salam, A. Bouhamidi, A Symplectic Arnoldi method for Hamiltonian matrix eigenvalue problem, soumis Numer Algo.

Ahmed Salam
LMPA, Université du Littoral
Ahmed.Salam@lmpa.univ-littoral.fr

Estimation d'erreur d'un approximant de Padé d'une fonction de transfert via la méthode de Lanczos

Les approximants de Padé, via la méthode de Lanczos, sont devenus des outils efficaces dans la théorie des circuits éléctriques. [1] presente une approche, basée uniquement sur l'algèbre linéaire. Le but de ce mémoire est de
1. se familiariser avec ce nouveau aspect, en mettant en évidence les avantages de cette méthode et éventuellement des extensions possibles.
2. valider certains tests numériques.

Ce travail peut être considéré comme une initiation à un sujet de thèse.

Keywords: Linear systems, transfer function, Padé approximation, linear system.

[1] Zhaojun Bai, Qiang Ye Error estimation of the Padé approximation of transfer functions via the Lanczos process, ETNA (1998) vol7, pp.1-17.

Dans ce travail, nous proposons d'étudier les équations de Navier-Stokes incompressible. Dans un premier temps on établira des résultats d'existence et d'unicité du problème continu. Ensuite on considèrera différentes méthodes d'éléments finis pour l'approximation de ces équations. Finalement les algorithmes classsiques d'Uzawa et d'Arrow-Hurwicz seront analysés tant du point de vue théorique que numérique. Des tests numériques seront effectués pour montrer leur efficacité et les comparer.

Références:

F. Brezzi et M. Fortin, Mixed and hybrid finite element methods, Springer, New York, 1991.

V. Girault et P.-A. Raviart, Finite element methods for Navier-Stokes equations, Theory and algorithms, Springer Series in Computational Mathematics, 5, Springer, Berlin, 1986.

J. Lazaar et S. Nicaise, A nonconforming finite element method with anisotropic mesh grading for the incompressible Navier-Stokes equations in domains with edges, Calcolo, à paraitre.

R. Temam, Navier-Stokes equations, North-Holland, Amsterdam, 1984.

Directeur: S. Nicaise

Dans ce travail, on étudiera les équations de Stokes dans des domaines non-réguliers (polygones, polyèdres). Après avoir établi des résultats de régularité des solutions on considèrera différentes méthodes d'éléments finis raffinées pour l'approximation de ces équations. Des tests numériques seront effectués pour comparer l'efficaté des maillages raffinés par rapport aux maillages uniformes.

Références:

F. Brezzi et M. Fortin, Mixed and hybrid finite element methods, Springer, New York, 1991.

H. El Bouzid et S. Nicaise, Refined mixed finite element method for the Stokes problem, in M. Bach, C. Constanda, G. C. Hsiao, A.-M. Sändig, and P. Werner, editors, Analysis, numerics and applications of differential and integral equations, 379, Pitman Research Notes in Mathematics, 158-162, Harlow, 1998. Longman.

V. Girault et P.-A. Raviart, Finite element methods for Navier-Stokes equations, Theory and algorithms, Springer Series in Computational Mathematics, 5, Springer, Berlin, 1986.

R. Temam, Navier-Stokes equations, North-Holland, Amsterdam, 1984.

Le sujet de ce mémoire concerne l'analyse numérique des équations aux dérivées partielles.

Il s'agit de considérer des problèmes elliptiques du type laplacien ou Stokes (éventuellement évolutifs et non linéaires, comme le problème de Navier-Stokes à faible Reynolds), définis dans un domaine non borné W^C = \mathbb R³\W, étant W un ouvert borné de \mathbb R³. La méthode numérique consiste à approcher le problème d'origine dans un domaine tronqué de diamètre R, en imposant des conditions aux limites appropriées dans le bord fictif.

Dans ce contexte, on regardera les estimations d'erreur lorsque le problème va être résolu par la méthode des éléments finis. Les outils de l'analyse fonctionnelle seront les espaces de Sobolev classiques et à poids.

D'un point de vue numérique, il s'agira de prendre en considération les méthodes multigrilles, actuellement les plus performantes pour l'approximation de la solution du problème elliptique. Il faudra regarder dans la très nombreuse littérature, pour étudier l'ordre de convergence de ces méthodes ainsi que leur mise en uvre effective. On simplifiera le problème en considérant le cas de maillages non-uniformes, mais emboî tés (i.e. la grille raffinée est obtenue en découpant l'élément de la grille grossière en m sous-éléments équivalents).

La partie pratique se fera à l'aide du logiciel Matlab.

La bibliographie sur le sujet sera mieux précisée ultérieurement.

References

[]

Goldstein (SIAM J. Num. Anal., 1993)

[]

Brenner-Scott (Springer, 1994)

[]

Briggs, Henson, McCormick (S.I.A.M. Phidalelphia, 2000)

[]

McCormick (S.I.A.M. Phidalelphia, 1992)

Preconditionnement par changement des conditions au bord

Dans la résolution de l'équation de Helmholtz sur un domaine W du R² avec des conditions au bord mixtes par les différences finies, on rencontre des matrices d'ordre N qui sont autoadjoints à une perturbation de rang o(N) pres (provenant des conditions au bord). Dans [1] on propose de preconditioner en utilisant d'autres conditions au bord.

Le but de ce mémoire est d'analyser le comportement de convergence de la méthode GMRES [2] pour ce type de matrices non symétriques. On analysera différentes idées classiques basées sur : le spectre, l'ensemble de valeurs, le pseudo-spectre. Cette étude est complétée par une vérification numérique (Matlab).

Bibliographie :
[1] H.C. Elman, D.P. O'Leary, Eigenanalysis of some preconditionned Helmholz problems, Numer. Math. 83 (1999) 231-257.
[2] Y. Saad, Iterative methods for sparse linear systems, PWS Publishing, Boston, MA (1996).

En algèbre linéaire, on dispose souvent d'une suite de matrices (par variation d'un paramètre de discretisation) ayant un spectre asymptotique commun. On cherche à approcher le spectre d'une telle matrice d'ordre N par les zéros du nième polynôme orthogonal associé (avec mesure d'orthogonalité a N points). Pour n,N ® ¥, n/N® t Î (0,1), des résultats de convergence ont été proposés dans [1]. On compara ces résultats avec la convergence des zéros des polynômes extremaux par rapport à une norme Hölderienne [2], et présentera des résultats numériques (Matlab).

Bibliographie :
[1] A.B.J. Kuijlaars, Which eigenvalues are found by the Lanczos method? SIAM J. Matrix Anal. Appl. 22 (2000), 306-321.
[2] P.D. Dragnev and E.B. Saff, Constrained energy problems with applications to orthogonal polynomials of a discrete variable, J. d'Analyse Math. 72 (1997), pp. 223-259.

1) Construire une chaîne de Markov qui converge vers une diffusion solution de l'équation différentielle stochastique

2) L'EDS dX = b(X,t) dt + s(X,t) dB admet une unique solution lorsque les coefficients b, s sont Lipschtziennes et à croissance linéaire. La preuve repose sur la méthode d'itération de Picard.

Cette méthode ne marche plus si b ou s ne sont plus Lipschtziennes. Dans ce cas on utilise la méthode de problème des martingales qui consiste à trouver pour chaque (x,s) une mesure de probabilité P^x,s sur l'espace des trajectoires continues C telle que

3) Il s'agit de construire l'intégrale de Itô par rapport à une martingale, et d'établir la formule de Itô.

Référence: D. Williams, Diffusions, Markov Processes, and Martingales, John Wiley & Sons 1987.

Processus Multivariés.

C'est une extension relativement directe du cours de statistique des processus au cas de processus à valeurs dans \mathbb R^d. Il faut redéfinir les notions (covariance croisée, co-spectre, Processus ARMA multivariés etc..) et comprendre les proprietes élémentaires des indices et des processus ainsi revisités. L'étude se fera à l'aide du livre de Brockwell et Davis (chapitre 11). Si le travail avance assez vite, on peut envisager une incursion dans le chapitre 12 consacré au filtrage de Kalman, directement connecté a ce qui précède.

Bibliographie: Brockwell P.J. Davis R.A. (1987) Time series: theory and methods. Springer-Verlag.

Inéfficacité du quantile empirique par rapport au quantile lissé pour des données censurées

Considérons une procédure statistique A nécessitant n observations et une autre procédure B nécessitant k_n observations (k_n plus grand que n) et conduisant à la performance selon un certain critère (disons le EQM Erreur Quadratique Moyenne) Pour comparer les deux méthodes, Hodges et Lehmann (1970) proposent la quantité k_n -n qui est une quantité naturelle de comparaison, appelée inéfficacité de la méthode B par rapport à la méthode A. Une autre facçon de comparer est de calculer la différence entre les probabilités que les deux estimateurs appartiennent à un même intervalle donné ( appelée coverage probability). Des résultats de convergence de la différence des probabilités nomalisée par la fenêtre de lissage ont été obtenu par Xiang (1995) ainsi que la fenêtre optimale. Le but du mémoire est d'étudier en détail l'article de Xiang et d'effectuer des simulations pour les différentes valeurs de p Î ]0,1[ et pour les deux estimateurs.

Références: X. Xiang (1995). "Deficiency of the sample quantile estimator with respect to kernel quantile estimatos for censored data" Annals of Statistics vol 23, pp 836-854.

Almost sure limit theorem (ASLT) for a sequence of random variables {z_k} means that under a reasonable choice of the weights b_k, the empirical measures Q_n = [1/( g_n)]å_{k = 1}ⁿ b_k d_zk almost surely weakly converge to a limit law G. Various interesting links between ASLT and classical weak limit theorem were found during the last decade, mainly for the case when z_k are normalized sums of independent variables or sample paths of partial sum process. There is a number of surveys on ASLT, see [1,2,3]. While the classical ASLT has very slow (logarithmic) convergence rate, it is suggested to develop some new versions of ASLT with polynomial rates and try to find out the optimal ones.

1. Atlagh M., Weber, M. (2000) Le théorème central limite presque sûr. Expositiones Mathematicae, 18, 97-126.
2. Berkes, I. (1998), Results and problems related to the pointwise central limit theorem, In: Asymptotic Methods in Probability and Statistics, Elsevier, 59-97.

3. Lifshits, M.A. (2001), Lecture Notes on Almost Sure Limit Theorems. Publ. IRMA Lille, 54-VIII, 1-25.

Laboratoire de Statistique et Probabilités
e-mail:lifshits@jacta.univ-lille1.fr; lifts@mail.rcom.ru

L'objet de ce mémoire est d'étudier le problème de l'interpolation de points par une courbe B-spline polynomiale. Suivant le degré et les contraintes géométriques imposées, il n'y pas toujours unicité de la solution. Pour garantir la qualité ''esthétique'' du résultat, la courbe B-spline interpolante est obtenue comme la solution à un problème de minimisation d'une fonctionnelle. Le choix de cette fonctionnelle devra être argumenté. Ce travail pourra s'appuyer sur l'article de John Lavery [1] et nécessite le développement d'algorithmes qui permettront de valider les choix réalisés. De plus, il sera possible d'intégrer ces algorithmes dans un environnement de CAO.

mots clefs : Interpolation, Courbes B-splines, Norme Lp, Optimisation

Références :

[1] John E. Lavery, Univariate cubic Lp splines and shape preserving, multiscale interpolation by univariate cubic L₁ splines, Computer Aided Geometric Design, 17 (2000), 319-336.

[2] J.C. Fiorot, P. Jeannin. Courbes et Surfaces Rationnelles. Applications à la CAO, RMA12, Masson, Paris, 1989. English version : Rational Curves and Surfaces. Applications to CAD, Wiley and Sons, Chichester, 1992.

[3] Carl de Boor, A Practical guide to Splines, Applied Mathematical Sciences, vol 27, Springer-Verlag, 1978.

Encadrement : Olivier GIBARU

Laboratoire L2MA de l'ENSAM de Lille, 8 Bld Louis XIV, 59046 Lille Cedex

email : Olivier.Gibaru@lille.ensam.fr

tél : 03 20 62 27 51

Jean-Louis Bon
Labo Stat-Proba, Université de Lille
Jean-Louis.Bon@eudil.fr

Approximations de sommes aléatoires de variables aléatoires positives

En fiabilité des systèmes, le processus décrivant le fonctionnement peut être modélisé sous forme de processus régénératif. La durée de vie du système se décompose alors sous forme d'une somme aléatoire (nombre de variables de distributiion géométrique) de variables représentant des durées de vie (avec des propriétés de vieillissement adaptées). Le but est d'avoir le maximum d'informations sur cette somme aléatoire. On pourra prendre comme reférence des lois gamma pour les durées de vie. Pour la variable aléatoire " nombre de termes" on peut supposer une distribution discrète quelconque. Deux parties sont prévues. L'une théorique (plus probabiliste) pour avoir des encadrements les plus fins possibles en fonction d'hypothèses de vieillissement, l'autre (plus statistique) pour orgnaiser des simulations de Monte-Carlo afin de mesurer la qualité des approximations trouvées.

L'étude des systèmes à requête interactive dans des bases d'images est un sujet de recherche récent. Le premier prototype est à ma connaissance celui de []. L'utilisateur cherche une image dans une base d'images. La seule composante aléatoire considérée est la similarité choisie par l'utilisateur lui permettant d'affirmer qu'une image est plus proche d'une autre que d'une troisième. Le système procède alors de manière séquentielle et adaptative. A chaque étape, le système propose à l'utilisateur deux images. L'utilisateur indique celle qui est la plus proche de celle souhaitée. L'arrêt a lieu, soit lorsque l'utilisateur identifie une image qui le satisfait, soit en cas d'échec après un nombre fixé d'itérations. Lorsque le modèle est spécifié, le système présente à chaque étape deux nouvelles images en fonction d'un critère de réduction d'entropie résiduelle calculé on-line. C'est un algorithme d'optimisation locale et dans [], Donald Geman et moi-même avons précisé ses frontières d'applicabilité en identifiant des situations où ses performances sont qualitativement éloignées de l'optimum global. Toutefois, dans le cas d'une base d'images structurée en arbre, et pour une famille de questions consistant pour un noeud donnée de l'arbre à interroger l'utilisateur sur la présence de la cible sous le noeud, Alain Trouvé et Yong Yu dans [] et [] établissent un très bon comportement de cet algorithme.

L'objet du stage sera, à la lecture de ces articles, d'identifier plus précisément les situations de succès de cette approche.