Algorithmes numériques pour les polynomiales.pdf

8/10/2019 Algorithmes numriques pour les polynomiales.pdf

1/110

Algorithmes numriques pour les

matrices polynomiales avec applicationsen commande

(Numerical algorithms for polynomialmatrices with applications in control)

Thse prpare au Laboratoire dAnalyse et dArchitecture des Systmes du CNRSen vue de lobtention du titre de Docteur delInstitut National des Sciences Appliques de Toulouse

parJuan Carlos Ziga Anaya

Date de la soutenance: le 14 septembre 2005.Composition du jury:

Germain Garcia, INSA Toulouse (Prsident)Didier Henrion, LAAS-CNRS Toulouse (Directeur de these)

Paul Van Dooren, UCL Louvain-la-Neuve (Rapporteur)Hisham Abou-Kandil, ENS Cachan (Rapporteur)

Michael ebek, VUT Prague (Examinateur)Javier Ruiz Len, CINVESTAV Guadalajara (Examinateur)


2/110

Rsum

Dans cette thse nous dveloppons de nouveaux algorithmes de calcul numriquepour les matrices polynomiales. Nous abordons le problme du calcul de la structurepropre (rang, espace nul, structures finie et infinie) dune matrice polynomiale etnous appliquons les rsultats obtenus au calcul de la factorisation J-spectrale desmatrices polynomiales. Nous prsentons galement quelques applications de ces al-gorithmes en thorie de la commande. Tous les nouveaux algorithmes dcrits ici sontbass sur le calcul despaces nuls constants de matrices bloc Toeplitz associes lamatrice polynomiale analyse. Pour calculer ces espaces nuls nous utilisons des m-thodes standard de lalgbre linaire numrique comme la dcomposition en valeurssingulires ou la factorisation QR. Nous tudions aussi lapplication de mthodes

rapides comme la mthode gnralise de Schur pour les matrices structures. Nousanalysons les algorithmes prsents au niveau complexit algorithmique et stabilitnumrique, et effectuons des comparaisons avec dautres algorithmes existants dansla littrature.

Mots cls: Matrices polynomiales, Analyse numrique, Algbre linaire num-rique, Thorie de la commande, Structure propre, Factorisation spectrale, Logicielsde CACSD.

Abstract

In this thesis we develop new numerical algorithms for polynomial matrices. We ta-ckle the problem of computing the eigenstructure (rank, null-space, finite and infinitestructures) of a polynomial matrix and we apply the obtained results to the matrixpolynomial J-spectral factorization problem. We also present some applications ofthese algorithms in control theory. All the new algorithms presented here are based onthe computation of the constant null-spaces of block Toeplitz matrices associated tothe analysed polynomial matrix. For computing these null-spaces we apply standardnumerical linear algebra methods such as the singular value decomposition or theQR factorization. We also study the application of fast methods like the generalized

Schur method for structured matrices. We analyze the presented algorithms in termsof algorithmic complexity and numerical stability, and we present some comparisonswith others algorithms existing in the literature.

Keywords: Polynomial matrices, Numerical analysis, Numerical linear algebra,Control theory, Eigenstructure, Spectral factorization, CACSD software.


3/110

ma femme Sofia...To my wife Sofia...


4/110


5/110

Prface

Cette thse sinscrit dans la problmatique du dveloppement dalgorithmes nu-

mriques fiables pour la commande. Cela dit, et bien que nos motivations soient lesproblmes numriques en commande (en particulier dans lapproche polynomiale), ilne sagit pas dune thse o le lecteur trouvera des rsultats nouveaux sur la tho-rie de la commande des systmes. Il ne sagit pas non plus dune thse danalysenumrique pure. Nous cherchons plutt appliquer les rsultats de lanalyse num-rique et de lalgbre linaire numrique pour dvelopper de nouveaux algorithmesqui rsoudront, de manire fiable, des problmes connus en commande.

Cette thse se situe donc la frontire entre la commande et lanalyse numrique,l o toutes les thories et toutes les approches la commande rencontrent les mmesproblmes lis lutilisation dun systme numrique (lordinateur par exemple): ceuxdus la prcision finie des calculs arithmtiques.

Ainsi, nous supposons connus les concepts classiques danalyse numrique. Cepen-dant, nous rappelons quelques notions et dtails quand ncessaire 1. Dans la section2.1.1, nous prsentons de faon pratique et laide dexemples quelques ides ba-siques de lanalyse numrique. Bien sr cette section nest pas une tude exhaustivedu sujet, le lecteur intress peut consulter labondante bibliographie existante. Oncite ici par exemple [14, 33, 43, 80, 99] qui sont, lextrieur de la communaut desanalystes numriques, quelques-uns des travaux les plus connus et par consquentles plus accessibles.

Nous supposons aussi que le lecteur est familiaris avec la thorie de la com-mande et ses diffrentes approches. De la mme faon nous rappelons quelques ides,

en particulier de la thorie des matrices polynomiales, quand cela peut aider lacomprhension de nos rsultats. Les polynmes, les matrices polynomiales et leuralgbre est assez thorique, et il y a beaucoup de rsultats dans la littrature disonsmathmatique, voir par exemple [27, 31].

Nous avons construit un index la fin de ce document comme outil pour trouverrapidement les pages o les informations importantes sur les concepts cls de cettethse sont donnes. La premire fois quun de ces concepts cls apparat dans cedocument il est crit en italique.

1. La plupart du temps sous forme de note de pied de page.

v


6/110

Dans la mesure du possible, pour un sujet donn, nous donnons les rfrences

bibliographiques originales ou celles o la thorie est compile. Cependant, ce nestpas la rgle gnrale, et le lecteur dcouvrira quil y a peut-tre des rfrences destravaux qui ne sont pas les premiers ou les originaux sur un sujet donn. Dans cecas sachez que la seule cause de cette omission est que la rfrence cite est la seuleporte notre connaissance, ou en tout cas la seule que nous avons consulte.

Le sujet de cette thse est relativement nouveau et semble intresser de plusen plus de gens dans la communaut internationale. Alors, pour assurer sa possiblediffusion dans la communaut non-francophone, lindex, ainsi que les chapitres 3, 4et 5, qui contiennent les contributions techniques, ont t rdigs en anglais.

Des conclusions techniques sur les rsultats de chaque chapitre ainsi comme les

conclusions gnrales de cette thse sont exposes dans le dernier chapitre en franais.Un concentr des contributions et de perspectives (travail futur) est aussi prsent.

Cette thse a t ralise au Laboratoire dAnalyse et dArchitecture des Sys-tmes (LAAS-CNRS), dans le cadre dun doctorat lInstitut National des SciencesAppliques (INSA) de Toulouse, France.

Je tiens remercier Didier Henrion pour son soutien inconditionnel comme mondirecteur de recherche tout au long de ma formation doctorale, pour son intereten trouver toujours les bonnes solutions aux differents problemes que jai eu. MerciDidier pour ton amiti.

Je remercie les commentaires prcis de Paul Van Dooren et Isham Abou-Kandil

pour amliorer ce document. Je remercie aussi tous les autres membres du jury: Ger-main Garcia, Michael Sebek et Javier Ruiz pour son soutien. galement je remercie la direction du LAAS-CNRS et du groupe de recherche MAC dans lequel jai travaillces 4 annes.

En tant que boursier du programme de coopration CONACYT-SFERE, je re-mercie le soutien conomique du Conseil National de la Science et de la Technologiedu Mexique (CONACYT) et de la Socit franaise dexportation des ressources du-catives (SFERE). Je remercie aussi le soutien conomique du Secrtariat dEducationPublique du Mexique (SEP).

Finalement, mais surtout, je remercie ma famille, mes parents et spcialement

ma femme pour avoir pris part avec moi de cette aventure qui termine, pour sonsoutien et pour tous les sacrifices quils ont dus raliser par ma faute.

Juan Carlos Ziga Anaya.Toulouse, France, septembre 2005.

vi


7/110

Table des matires

Prface v

1 Introduction 1

1.1 Objectif de cette thse . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Organisation des chapitres . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Mthodes numriques et logiciels de CACSD 11

2.1 Approche espace dtat . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.1 Application des logiciels de CACSD . . . . . . . . . . . . . . 14

2.2 Approche polynomiale . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.1 Problmes numriques et polynmes . . . . . . . . . . . . . . 23

2.3 Mthodes pour les matrices polynomiales . . . . . . . . . . . . . . . . 27

2.3.1 Dcomposition en valeurs singulires . . . . . . . . . . . . . . 30

2.3.2 Factorisation LQ . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.3.3 Forme EchelonL . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.3.4 Mthode gnralise de Schur . . . . . . . . . . . . . . . . . . 33

3 Zero structure of polynomial matrices 35

3.1 Computing the finite zeros . . . . . . . . . . . . . . . . . . . . . . . . 41

3.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.3 Algorithmic analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.3.1 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.3.2 Stability and accuracy . . . . . . . . . . . . . . . . . . . . . . 56

vii


8/110

4 Null-space of polynomial matrices 59

4.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61


4.2.1 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4.2.2 Stability and accuracy . . . . . . . . . . . . . . . . . . . . . . 72

4.2.3 Extension of the Toeplitz algorithms . . . . . . . . . . . . . . 74

5 PolynomialJ-spectral factorization 77

5.1 Factorization of the eigenstructure . . . . . . . . . . . . . . . . . . . 77

5.1.1 Extraction of a set of zeros . . . . . . . . . . . . . . . . . . . 79

5.1.2 Extraction of the null-space . . . . . . . . . . . . . . . . . . . 80

5.2 J-spectral factorization . . . . . . . . . . . . . . . . . . . . . . . . . . 81

5.2.1 Existence conditions . . . . . . . . . . . . . . . . . . . . . . . 82

5.2.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83


6 Conclusions 896.1 Contexte scientifique . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

6.2 Contribution et perspectives . . . . . . . . . . . . . . . . . . . . . . . 90

viii


9/110

Chapitre 1

Introduction

Lexcution ordonne dun ensemble de pas (instructions ou oprations) vers lasolution dun problme quelconque est quelque chose que lhomme a fait depuis lanuit des temps, mme avant quil existe le mot algorithme (algorithm) pour dfinir ceprocessus [13]. Le mot algorithme garde une connotation mathmatique qui convientparfaitement tant donne la thmatique de ce travail. Cependant, dautres pos-sibles synonymes comme processus, mthode, technique, procdure, rgle ou recettemettent en vidence que tout le monde applique des algorithmes mme inconsciem-ment.

Le mot algorithme est driv de larabe Al-Khwarizm qui tait le nom du ma-thmaticien auteur du plus ancien travail connu dalgbre. Dans son travail, Al-Khwarizm soulignait limportance dappliquer une procdure mthodique pour r-soudre des problmes comme certains types dquations quadratiques. Ce travailet beaucoup dautres, bases de ce que lon appelle lalgbre, sont traduits en latinau 12me sicle. ce moment, et cause de lintroduction du nouveau systmede numrotation, on utilisait le mot algorithme pour nommer certaines procduresarithmtiques. Quand la numration arabe a t finalement adopte, appliquer un al-gorithme signifiait simplement faire de lalgbre. Avec le temps, lalgbre est devenueune discipline beaucoup plus complique que la solution dquations quadratiqueset les algorithmes sont devenus simplement des outils pour rsoudre des problmes

spcifiques de manire mthodique, systmatique.Actuellement la liste des algorithmes qui servent rsoudre un problme donn

peut tre, pour certains problmes, interminable. Les algorithmes ont volu. Unetendance naturelle est de les rendre chaque fois plus gnraux. Cette tendance estaussi encourage par le dveloppement de la science qui impose, chaque fois, desproblmes plus compliqus. Prenons par exemple la solution dun systme dqua-tions Ax = b. En 1750 Cramer a formul une procdure gnrale pour rsoudre cesystme. Avec la rgle de Cramer, le problme paraissait rsolu. Cependant, quandon a voulu appliquer cette rgle aux nouveaux problmes en astronomie de cettepoque, o le nombre dquations tait grand, le nombre de multiplications quon

1


10/110

2 CHAPITRE 1. INTRODUCTION

devait faire tait norme 1. Face ce problme, dautres algorithmes, qui rduisaient

le nombre doprations, ont t dvelopps. Cest le cas, par exemple, de lliminationGaussienne en 1810.

Les algorithmes nont pas seulement volu grce aux problmes poss par lascience, mais aussi la science a avanc grce ltude, lanalyse et lapplication desalgorithmes. Par exemple, ce nest quen 1815 que Cauchy a dmontr la rgle deCramer pour la premire fois, en donnant lorigine ltude des dterminants. Demanire similaire, cest en 1850 que Sylvester a introduit le terme "matrice", desannes aprs que ses proprits fondamentales aient t tablies [13].

Avec le dveloppement des ordinateurs dans les dernires dcennies, ltude etlanalyse des algorithmes ont pris de nouveau beaucoup dimportance. Malgr la

capacit de calcul que les ordinateurs offrent, la qualit de la solution obtenue nestpas toujours ce que lon peut esprer. En particulier, on peut vrifier que la plupartdes algorithmes de facile excution la main et qui donnent de bons rsultats nedeviennent plus fiables si on les codifie dans lordinateur. La cause: la prcisionfinie (finite precision) prsente dans tous les systmes numriques. Cette prcisionfinie limite la quantit de nombres rels que lordinateur peut reprsenter, et parconsquent des erreurs dues larrondi (rounding) sont introduites [116].

Exemple 1.1

La solution de lopration 0.3 0.2 0.1 calcule par Matlab 2 [68] en double pr-cision3 est2.77... 1017 = 0. La cause est simplement quaucun des nombresqui intervient dans le reste ne peut tre reprsent exactement par lordinateur. Cetexemple extrait de [10] montre que les erreurs darrondi apparaissent ds les pro-blmes les plus simples.

Avec la prcision finie, quelques proprits des oprations arithmtiques basiquescomme la somme ou la multiplication ne sont pas vrifies. Tel est le cas de laproprit associative de la somme comme dmontr dans lexemple suivant.

Exemple 1.2

Considrons un schma arithmtique double prcision. Lopration 1 + 1020 1020peut tre effectue par lordinateur comme 1 + (1020

1020) qui donne le rsultat

correct, ou bien comme(1 +1020)1020 qui donne0 car les nombres 1+ 1020 et1020sont reprsents de la mme manire par lordinateur avec la prcision donne.

Intuitivement on peut deviner quelle est la faon correcte deffectuer lopration.Mme quand il y a plusieurs oprations, on peut dcider la prcision avec laquellechaque opration est effectue en prdisant leffet de chaque erreur dans le rsultatfinal.

1. Environ 300 millions de multiplications pour 10 quations [13].2. MATrix LABoratory, voir www.themathworks.com3. Il sagit du format classique de reprsentation de nombres virgule flottante, avec environ 14

chiffres significatifs [32, 43, 80].


11/110

3

Exemple 1.3

On veut calculer les racines x = et x = de lquation quadratique p(x) =ax2 + bx + c. laide de la formule classique quon apprend lcole, on peut vrifierque

=b + d

2a , =

b d2a

o d =

b2 4ac. Supposons que b > 0 est tel que b2 4ac. Ainsi, au momentde calculer , on peut considrer que db et choisir =b/acomme une bonneapproximation de la valeur relle de . Par contre, au moment de calculer on aintrt obtenir d avec le plus grand nombre de chiffres significatifs de telle sorteque la diffrenceb + dne se perde pas.

Malheuresement, quand des milliers doprations sont effectues automatique-ment par lordinateur, avec une mme prcision finie, ce contrle manuel de lerreurnest plus possible. Pour lexemple prcdent, en fonction des valeurs numriques dea,b,cet de la prcision utilise, il est possible quune soustraction destructive [43] seproduise et que la valeur obtenue de soit trs mauvaise. Voici un dernier exempletrs illustratif extrait de [74].

Exemple 1.4

Supposons quon veuille calculer eA, lexponentielle de la matrice

A= 49 2464 31 en simple prcision 4. Lalgorithme classique consiste dvelopper la srie de Taylor

eA =

j=0

1

j!Aj

jusqu que les termes soient infrieurs en valeur absolue 107. Lalgorithme estfacilement programmable et le rsultat est

eA

22.2588 1.4327761.4993 3.47428 .Malheureusement le rsultat correct, arrondi 6 chiffres significatifs, est

eA 0.735759 0.551819

1.47152 1.10364

et donc mme les signes de certains lments calculs par lordinateur sont incorrects.En observant chaque terme de la srie on peut noter que quelques termes du milieusont proches de 107 mais de signe contraire. Par consquent, des soustractionsdestructives [43] ont lieu et linformation significative est perdue.

4. Environ 6 chiffres significatifs [32, 43, 80].


12/110


13/110


14/110

6 CHAPITRE 1. INTRODUCTION

Un phnomne qui a aussi contribu normment au dveloppement de lalgbre

linaire numrique sont les relations symbiotiques que cette discipline a eu avecdautres disciplines en science et en ingnierie. Un exemple trs clair est la thoriede la commande des systmes linaires reprsents sous la forme matricielle (espacedtat). Dune part la thorie des systmes est pleine de problmes dalgbre linairenumrique, et dautre part beaucoup dalgorithmes de lalgbre linaire numriquetrouvent des applications intressantes dans la thorie des systmes. Cette interac-tion entre algbre linaire numrique et commande a t trs fructueuse. Lapprocheespace dtat (state space approach) [50, 90], suite aux travaux de Rudolf Kalmandans les annes 1960, est devenue lapproche largement prfre en ce qui concernelobtention de rsultats numriques. Beaucoup de logiciels de CACSD ont t dve-lopps dans ce cadre. On approfondit ce sujet dans le chapitre suivant.

Par contre, dautres disciplines mathmatiques ont moins dvelopp leurs ctsnumriques. Cest le cas de lalgbre non linaire et de la gomtrie algbrique quisont rests assez thoriques [98]. Pourtant, actuellement il est devenu de plus en plusncessaire dtendre cette thorie des rsultats numriques. Les polynmes parexemple sont devenus des outils naturels pour modliser les systmes dynamiques,qui, dans le monde rel, ont des coefficients numriques avec une prcision limite.

Grce la capacit des ordinateurs modernes 14 le calcul symbolique (symbo-lic computing) est devenu possible et lalgbre calculatoire (computer algebra) a tdveloppe comme outil informatique pour faire des mathmatiques pures avec lor-dinateur. Quelques exemples de logiciels qui permettent le calcul symbolique sont:

MAPLE15

[113] et MATHEMATICA16

[117]. Cependant, les rsultats obtenus par lecalcul symbolique sont en gnral inadquats pour les problmes rels. Par exemple,le rsultat dun systme dquations coefficients numriques peut tre donn commedes fractions dentiers avec des centaines de chiffres. Le passage au monde numriquenest pas toujours adquat.

Des efforts pour raccourcir le chemin entre lalgbre calculatoire et lanalyse nu-mrique sont faits ces dernires annes. Diffrents groupes de recherche dans lesuniversits ont commenc dvelopper des logiciels numriques pour les problmessur les polynmes 17. Quelques bibliothques, comme par exemple NAG18, ont t d-veloppes. Ces bibliothques incluent plusieurs routines pour rsoudre des problmesnumriques qui ne sont pas de lalgbre linaire, comme par exemple: lextraction de

racines de polynmes, les quations diffrentielles, linterpolation, loptimisation, etc.Des logiciels comme MAPLE basent leurs capacits numriques sur les bibliothquesNAG. Malheureusement, les bibliothques NAG ne sont pas de libre distribution(contrairement LAPACK ou BLAS) et il reste encore beaucoup de travail faire,tant au niveau thorique que pratique, pour pouvoir parler dune algbre non linairenumrique (numerical non-linear algebra).

14. Surtout au niveau de mmoire de stockage.15. MAthematical PLEasure, voir www.maplesoft.com.16. Voir www.wolfram.com.17. Voir par exemple www.dm.unipi.it/ananum/polynomial.html. [8]

18. Numerical Algorithms Group, voirwww.nag.co.uk.


15/110

1.1. OBJECTIF DE CETTE THSE 7

Par rapport la thorie de la commande des systmes, ces dernires dcen-

nies dautres approches ont t dveloppes comme alternatives lapproche espacedtat: lapproche polynomiale (polynomial approach) [58] et lapproche comporte-mentale (behavioural approach) [83]. Avec ces approches les systmes sont reprsen-ts laide de polynmes et de matrices polynomiales. Il devient alors ncessairede raliser plusieurs tches numriques comme la manipulation des polynmes etdes matrices polynomiales, la solution dquations polynomiales et lextraction deproprits structurelles.

Malheureusement, et malgr le fait que lapproche polynomiale est actuellementun des plus puissants outils thoriques pour la commande des systmes (voir parexemple [48]), au niveau des logiciels de CACSD son dveloppement est beaucoupplus faible que celui de lapproche espace dtat. La raison principale, comme on leverra dans le prochain chapitre, est le manque dune thorie numrique consolidepour les polynmes et les matrices polynomiales, et par consquent un manque delogiciels de base comme LAPACK pour lalgbre linaire numrique.

Rcemment, sous le pseudonyme dalgbre polynomiale numrique (numericalpolynomial algebra), la thorie de lanalyse numrique a finalement t adapte auxpolynmes par Hans Stetter [98]. Il sagit dune des premires contributions versla consolidation dune algbre non linaire numrique. Dans la communaut de lacommande de systmes, beaucoup denthousiastes des mthodes polynomiales ontfait aussi des efforts pour combler la manque de logiciels de CACSD pour lapprochepolynomiale (voir le chapitre suivant). Plusieurs algorithmes modernes pour les poly-

nmes et les matrices polynomiales sont maintenant bass sur des oprations stablesde lalgbre linaire numrique, voir [5, 38, 107] par exemple. Des rsultats rcentscomme [97, 119], bien quils ne soient pas encore trs diffuss et appliqus, prdisentque beaucoup de problmes polynomiaux mal conditionns ou mal poss peuvent trersolus de manire satisfaisante dans le sens de lanalyse numrique et de lalgbrepolynomiale numrique. Ainsi nous croyons quil nest quune question de temps pourquon puisse appliquer la thorie de lanalyse numrique aux problmes polynomiauxen commande et pour que le dveloppement de logiciels de CACSD pour lapprochepolynomiale soit comparable celui de lapproche espace dtat.

1.1 Objectif de cette thse

Lobjectif de cette thse est de contribuer au dveloppement dalgorithmes nu-mriques fiables pour les matrices polynomiales en ayant comme motivation les pro-blmes de commande. Le contenu de la thse est rsum par les points suivants:

Etablissement de ltat de lart des logiciels de CACSD tant pour lapprochepolynomiale que pour lapproche espace dtat. On montre comment lalgbrelinaire numrique aide rsoudre plusieurs problmes numriques en com-mande.

Dveloppement de nouveaux algorithmes numriques pour lobtention de la

structure propre des matrices polynomiales et pour la solution du problme


16/110


17/110

1.2. ORGANISATION DES CHAPITRES 9

lalgorithme est prsente ainsi que des comparaisons avec dautres algorithmes

existants. On illustre les rsultats avec quelques exemples dapplications lacommande.

Chapitre 5: Le problme de la factorisation des matrices polynomiales est in-troduit. On montre comment les algorithmes prsents dans les chapitres pr-cdents peuvent tre appliqus pour factoriser la matrice polynomiale analyse.On montre quon peut extraire des facteurs qui ne contiennent quune partiede la structure propre de la matrice polynomiale. Finalement, on prsente unnouvel algorithme pour la factorisation J-spectrale des matrices polynomialesainsi que des comparaisons avec dautres algorithmes existants.

Chapitre 6: Dans ce chapitre on trace les conclusions gnrales, un rsum descontributions de la thse et les perspectives et ides de travaux futurs.


18/110


19/110

Chapitre 2

Mthodes numriques et logiciels

de CACSD

Dans ce chapitre on prsente les diffrentes approches la commande de sys-tmes linaires. Ensuite on prsente quelques caractristiques des logiciels de CACSD(Computer-Aided Control System Design) existant pour lapproche espace dtat etpour lapproche polynomiale. On analyse les problmes numriques associs aux ma-trices polynomiales et on introduit les mthodes qui servent traiter ces problmes.Il faut rappeler que lanalyse numrique est le fil conducteur de la discussion, mais

ce nest pas le thme central ni lobjectif de la thse. Les concepts gnraux de cettethorie sont rappels dans les diffrents exemples prsents dans ce chapitre, mais leslecteurs intresss par une tude plus systmatique, formelle et approfondie devrontconsulter labondante littrature sur le sujet.

Le processus de la commande dun systme dynamique commence par sa modli-sation en termes dquations mathmatiques. En particulier, dans le cas des systmeslinaires invariants dans le temps, on a un ensemble dep quations diffrentielles dutype

a1d1y(d1)1 (t) + + a10y1(t) + a1+ + apdPy(dp)p (t) + + ap0yp(t) + ap =

b1f1u(f1)1 (t) +

+ b10u1(t) + b1+

+ bmfmu

(fm)m (t) +

+ bm0um(t) + bm (2.1)

o(q)(t)reprsente laq-ime drive du signal scalaire (t)par rapport au temps.Les paramtres aij etbkl pouri= 1:p, j = 0:di, k = 1:met l = 0:fk sont constants.Par convention, toutes les variables sur lesquelles on a un contrle et qui serviront commander le systme sont appeles les entres ui(t), i = 1:m. Dautre part, toutesles variables sur lesquelles on observe leffet de la commande sont appeles les sortiesyi(t), i = 1:p.

Il existe diffrentes approches pour interagir avec ce modle mathmatique. Avecchaque approche, le modle est reprsent ou reformul dune faon particulire o lesdiffrentes proprits du systme sont plus ou moins dvoiles. On peut par exemplecrire chaque quation de type (2.1) comme un ensemble dquations diffrentielles

dordre 1 laide de linclusion de variables dtat (state variables) [50]. Aprs des

11


20/110

12 CHAPITRE 2. MTHODES NUMRIQUES ET LOGICIELS DE CACSD

manipulations algbriques, le modle du systme peut tre crit de la manire sui-

vante:

x(1)(t) =Ax(t) + Bu(t),

y(t) =C x(t) + Du(t). (2.2)

Le vecteurx(t) Rn est le vecteur des variables dtat et sert donc relier le vecteurdentres u(t) Rm et le vecteur de sorties y(t) Rp. Les matrices A Rnn,B Rnm, C Rpn et D Rpm sont constantes. La reprsentation (2.2) estutilise par lapproche espace dtat [50, 90]. Notons quen appliquant la transformede Laplace sur la reprsentation (2.2) on peut liminer x(t)et en dduire la fonctionde transfert T(s)du systme [50]

y(s) = [C(sI A)1B+ D]u(s) =T(s)u(s)

dans lhypothse de conditions initiales nulles.

Une autre manire de rcrire lensemble des p quations de type (2.1) qui re-prsentent le systme dynamique est la forme matricielle. En regroupant toutes lesentres et sorties dans les vecteurs correspondants u et y on obtient:

D(s)y(s) =N(s)u(s). (2.3)

Les matrices D(s)et N(s)sont des matrices polynomiales (polynomial matrices) enla variables, de dimensionsp pet p mrespectivement. Rapellons que dans le cascontinu, la variable s est loprateur de Laplace. Si le systme est temps discret,alors la variable devient loprateur de dcalage.

tant donn que la fonction de transfert du systme est unique [50], on vrifieque

T(s) =D1(s)N(s) =C(sI A)1B+ D.

La reprsentation (2.3) est utilise par lapproche polynomiale [58] ou encore parlapproche comportementale [83].

Chaque reprsentation a ses points forts et ses points faibles, et implique unefaon diffrente danalyser le mme systme. Par consquent chaque approche lacommande des systmes a aussi ses particularits et utilise ses propres mthodeset outils mathmatiques. Une discussion des avantages ou dsavantages de chaqueapproche impliquerait beaucoup defforts pour nen tirer aucune conclusion. En fait,le vrai avantage consiste disposer de plusieurs faons diffrentes de rsoudre unproblme. Pour certains problmes lapproche espace dtat sera plus efficace, pourdautres problmes lapproche polynomiale ou lapproche comportementale serontplus adquates. Actuellement, au niveau thorique, quelle approche utiliser restesimplement une question de prfrence personnelle. Cependant, au niveau des logi-ciels de CACSD, lapproche espace dtat est beaucoup plus dveloppe. On illustre

ceci dans les sections suivantes.


21/110

2.1. APPROCHE ESPACE DTAT 13

2.1 Approche espace dtat

On considre un systme donn sous la forme (2.2). Lobjet mathmatique dumodle sont des matrices constantes valeurs relles. Par consquent, lalgbre li-naire et lalgbre linaire numrique sont les outils mathmatiques de base pourlanalyse et la synthse de la commande des systmes dcrits par lapproche espacedtat. Linteraction entre algbre linaire et commande a t trs fructueuse cesdernires annes. Beaucoup de problmes numriques en commande sont rsolus demanire satisfaisante grce lapplication des mthodes numriques de lalgbre li-naire. Lutilisation des librairies numriques comme LAPACK ou BLAS a permis laconception de centaines de logiciels de CACSD. Plusieurs logiciels furent initialementprsents dans un numro spcial de la revue IEEE Control Systems Magazine en

1982 [41]. Actuellement, certains de ces logiciels sont mis jour et de nouveaux appa-raissent. On peut mentionner, par exemple, laControl System Toolboxpour Matlab 1

et la bibliothque Slicot2 qui sont deux outils assez connus et utiliss.

Les critres pour juger de la supriorit dun logiciel de CACSD ne sont pastablis dune faon unifie et accepte par tout le monde. Chaque concepteur ouutilisateur souligne certains critres plus que dautres et base ses points forts surdiffrentes caractristiques. Cependant, quelques rflexions gnrales peuvent se faire ce propos:

Les logiciels de CACSD peuvent tre regroups en deux grandes catgories.Le niveau infrieur contient les logiciels numriques comme les bibliothquesLAPACK, BLAS, etc. et les fonctions basiques programmes avec un langagegnrant du code machine (FORTRAN est le plus utilis). Le niveau suprieurcontient les procdures danalyse et de synthse de commande mises en ouvreen appelant des fonctions de plus bas niveau. Ce niveau suprieur constituesurtout linterface qui permet lutilisateur dappliquer les outils numriquespour rsoudre son problme de commande.

Aucun logiciel de CACSD ne peut tre plus performant que le logiciel num-rique sur lequel il est construit. Dans ce sens, la meilleure prcision (accuracy)des oprations quon peut esprer provient des routines de niveau infrieur.Cependant, cette prcision nest pas toujours obtenue et cela dpend, entre

autres, de la faon et du moment auquel le logiciel numrique de base est uti-lis: si la plupart du calcul numrique est mis en oeuvre bas niveau, le tempsdexcution sera srement plus court et il y aura plus de chances pour quuneprcision satisfaisante soit obtenue.

Linterface est un aspect qui peut diffrencier un logiciel CACSD dun autre etqui est particulirement importante pour lutilisateur qui nest pas familiarisavec les problmes et les algorithmes numriques. Certains logiciels de CACSDfournissent leur propre interface [41], dautres logiciels utilisent Matlab pourcrer cette interface avec lutilisateur. En tout cas, notons quune bonne inter-face rend plus facile lutilisation mais peut aussi compromettre largement le

1. Voir www.mathworks.com/products/control.

2. Cre par The Numerics in Control Network NICONET. Voir www.win.tue.nl/niconet.


22/110


temps dexcution et parfois mme la prcision.

Lutilisation de logiciels de CACSD a permis dtendre lutilisation de lapprocheespace dtat dans la communaut. Ainsi, beaucoup de gens ont pu appliquer decomplexes thories de commande en obtenant des rsultats numriques mais sanssoccuper de la problmatique numrique et algorithmique. Indiscutablement cesttrs positif. Cependant, il faut rappeler que derrire tout logiciel il y a beaucoupde travail et de dveloppement. Dune part il y a la thorie des mathmatiquesappliques (lalgbre linaire numrique) qui nest pas propre lapproche espacedtat, et dune autre part ladaptation des rsultats et algorithmes classiques encommande pour prendre en compte les problmes numriques.

2.1.1 Application des logiciels de CACSD

Par la suite on illustre lapplication des algorithmes classiques en commande,en utilisant les outils de lalgbre linaire numrique, pour faire face aux problmesnumriques et obtenir des rsultats satisfaisants. Les algorithmes quon prsente ici nesont pas nouveaux, ils sont dcrits titre illustratif. Les rsultats originaux peuventse trouver, par exemple dans [45, 50, 61, 82, 108] et leurs rfrences. Un deuximeobjectif de cette section est de prsenter de manire pratique les concepts danalysenumrique quon utilisera dans le reste de cette thse. Pour un approfondissementsur ces concepts voir par exemple [33, 43, 99, 115, 116].

Pour atteindre les objectifs de cette section, on tudie un des problmes classiquesen commande: le placement de ples. Etant donn un systme sous la forme (2.2),lobjectif est de trouver une commande linaire statiqueu = F xtelle que le systmeen boucle ferme ait des ples donns, cest--dire, telle que la matrice A+BF aitle polynme caractristique dsir

det(sI A BF) =sn + fn1sn1 + + f0= f(s).

Algorithme classique et ses problmes numriques

Thoriquement ce problme nest pas compliqu. Une manire mthodique de le

rsoudre consiste exprimer la forme canonique

A= T1AT =

an1 an1 a01 0

. . . . . .1 0

, B = T1B =

10...0

(2.4)

avec la transformation linaire

T = CT = B AB An1

1 an1 a11

. . . ...

. . . an11

, (2.5)


23/110


24/110


Pour illustrer ces ides on retourne au problme de placement de ples et la

solution de M y = b, en supposant Mrgulire, cest--dire inversible. Le condition-nement de la matrice Mpour le problme M y = b est donn par

p(M) = M1pMp (2.7)pour des perturbations arbitraires limites en norme p, ou par

(M) = |M1||M| (2.8)pour le cas o chaque lment de M et/oub est perturb 3.

Exemple 2.1

Pour rsoudre un problme de placement de ples, on veut calculer la solution ydusystmeM y = b avec

M=

100 0 00 85 52

0 0.003 0.003

, b=

085

0.003

.

Supposons que les calculs soient effectus dans un systme arithmtique virguleflottante 16 bits de prcision, cest--dire, avec une unit darrondi = 0.57.63106. Le paramtreest la distance entre le nombre 1 et le nombre suprieur leplus proche. Dans cette thse, sera dnomm prcision machine (machine precision).Alors, pour des raisons pratiques, on considre les rsultats donns par Matlab (avecune unit darrondi

m= 0.5eps

1.11

1016) comme exacts. Considrons quon

applique un algorithme stable 4 (backward stable) cest--dire que la solution calculey est la solution exacte du systme lgrement perturb

(M+ )y= b,

o est une perturbation arbitraire (erreur arrire) telle que

O()M.Pour ce type de perturbation, la matrice Mest trs mal conditionne avec (M) =28334.333...Alors, mme si la mthode numrique utilise pour rsoudre le systmeM y = b est stable, tant donne lquation (2.6), il peut arriver que lerreur avant

y ysoit grande. Soit = rand(3, 3)M, = 0.0017... 0.002...= M

lerreur arrire introduite par lalgorithme. Alors, y est la solution exacte

y= (M+ )1b=

1.499... 10

6

1.111...0.182...

.

3. En gnral M1 nest pas connu ou il est coteux de lobtenir en termes calculatoires. Alorslestimation du conditionnement par des mthodes approximatives est ncessaire [43]. LAPACKcontient de trs bonnes mthodes pour estimer le conditionnement dune matrice [3].

4. Plusieurs algorithmes stables pour la solution des systmes dquations sont prsents dans

[33] par exemple.


25/110


26/110


o max(M), min(M) sont la plus grande et la plus petite valeur singulire de M

respectivement. Cette relation met en vidence que1/2(M)est bien une mesure dela distance la singularit du problmeM y= b. Autrement dit, si2(M)est grand,M est peut tre singulire. Pour une unit darrondi = 0.5, la matrice M estsingulire si 2(M)> 1/n. De manire quivalente, lapproximation numrique durang 6 de Mest gal au nombre de ses valeurs singulires suprieures nmax. Lesvaleurs singulires deMpour lExemple 2.1 sontmax= 100, = 99.644...etmin=0.0041...Alors, le rang de cette matrice, pour la prcision utilise, est seulement deuxcar min < 3max = .0045... Par contre, aprs le scaling, min(P M) = 96.719... >0.019...= 3max(P M)ce qui rend la matrice Mrgulire.

Par rapport au problme de placement de ples, la restriction que la matrice Tdonne par (2.5) soit de rang plein est naturelle car elle implique tout simplementque le systme est commandable. Cependant, tester la commandabilit du systmeen observant les valeurs singulires de la matrice T ouC nest pas une mthodefiable. Etant donne sa construction, on peut attendre que les normes des colonnesde la matrice de commandabilit Csoient trs dsquilibres pour une matrice dtatarbitraire de dimension grande. Par consquent, on peut attendre un grand cartentre max(C)et min(C), cest--dire, que la matrice C soit singulire pour la prcisiondonne.

Exemple 2.2

Soit un systme sous la forme (2.2) avec n = 7, m = 1et les lments de A,bchoisisalatoirement uniformment entre 0 et 1. Soit

C = b Ab A6b sa matrice de commandabilit. On considre toujours une unit darrondi = 0.5 7.63 106. Les valeurs singulires deC sont:

1= 2180.718..., 2= 0.886..., 3= 0.300..., 7= 0.000...Alors, pour la prcision donne, Cest singulire car2(C) = 2462878.095... >1/7=9362.285... En fait, notons qu partir de i = 4, i < 71. Donc lapproximationnumrique du rang deC est 3.

On a vu que le scaling peut servir rgulariser notre problme F T = F pourtrouver une solution plus ou moins exacte, cf. lExemple 2.1. Cependant, il fautconsidrer les remarques suivantes:

Dans lExemple 2.1 il est relativement facile de dterminer la matrice de scalingP. En fait, il suffit dobserver que la dcomposition en valeurs singulires de Mest donne parM=IV. Alors, si on veut modifier la magnitude demin(M)de telle sorte que min(M) max(M), il suffit de multiplier la dernire lignedeMpar une constante adquate. Dans ce casP= diag{1, 1, 2(M)}. Malheu-reusement, en gnral il est beaucoup plus compliqu de dterminer la matriceP.

6. Voir la documentation de la fonction rank de Matlab, et la section 2.3.1 de cette thse.


27/110

2.1. APPROCHE ESPACE DTAT 19

En plus, il existe une limite pour les effets du scaling: on peut vrifier que, avec

un scaling optimal, (P M) = (M), o le conditionnement est dfini en(2.8). Noter que la valeur de (M) est indpendante du scaling, cest--dire,(M) = (P M), cf. [43, Chapitre 7]. Daprs les proprits des normes, onpeut vrifier que si(M)> 1/, alors la matrice P Mpour toute Pdiagonalesera toujours singulire pour la prcision donne. Dans lexemple 2.2 (C) =2168168.553... > 65536 = 1/donc on ne pourra pas rgulariser le problmeavec un scaling mme si on arrive trouver la matrice Poptimale.

Donc notons que malgr les techniques de scaling et lexistence dalgorithmesstables pour la solution du systmeF T = F, une solution satisfaisante du problmede placement de ples nest pas assure. En fait il faut comprendre que si un algo-rithme numrique est compos de plusieurs sous-algorithmes ou sous-problmes, etque si lun de ces sous-problmes est mal conditionn ou mal pos, alors la fiabilit dursultat final est compromise. Pour notre exemple, nous avons deux sous-problmes,dabord la transformation dtat qui emmne la construction de la matrice T, etensuite la solution du systme F T = F. Pour construire une matrice de transfor-mation despace dtat mieux conditionne et ainsi avoir plus de chances dobtenirun bon rsultat, dautres techniques dalgbre linaire numrique sont utilises, enparticulier les transformations orthogonales [17].

Transformations orthogonales

Une matrice Q Rnn est orthogonale (orthogonal matrix) siQTQ= QQT =I.Ainsi, toutes les valeurs singulires de Q sont gales 1. La matrice Q est donc bienconditionne:

2(Q) = 1, (Q)< (Q)< n.

Une autre proprit importante des matrices orthogonales est quelles conservent parmultiplication le conditionnement 2 dune matrice quelconque:

2(AQ) =2(QA) =2(A).

Supposons quon applique une transformation dtat orthogonale Q telle que

A= QAQT =

an1

an1

a0

1 . . . . . .

n1

, B = QB =

b1

0...0

(2.9)

o reprsente un lment quelconque possiblement diffrent de zro. Supposonsaussi que F soit choisie telle que la boucle ferme ait le polynme caractristiquedsir

det(sI A BF) =f(s).Alors, la solution au problme de placement de ples est simplementF = F Q. Reste dterminer F. partir de la dfinition des valeurs et vecteurs propres, on peutvrifier que

A + BF =VV1


28/110


avec

= diag{1, . . . , n}, V = v1 vn o i, i = 1:n sont les valeurs propres de A+ BF (racines de f(s)) et vi, i = 1:nsont les vecteurs propres correspondants. Notons quon peut construire les vecteursvi partir des n 1dernires lignes de A + BF

1 i. . . . . .

n1 i

vi= ivi= 0, (2.10)

et donc, extraire facilementF

en divisant la premire ligne deA

VV1

parb1.

La solution de (2.10) peut tre obtenue aussi grce des transformations or-thogonales et ainsi assurer de bonnes proprits numriques. En particulier on peutappliquer sur i une factorisation LQ, duale de la factorisation QR [33] (voir 2.3.1de cette thse) pour obtenir une base de son espace nul.

Le systme transform (2.9) est nomm la forme commandable de Hessenberg (comparer avec la forme commandable (2.4)). La matrice orthogonale Q nest quunecomposition de matrices de Householder (Householder matrix) [33] (voir 2.3.1 decette thse) appliques pour annuler les lments dsirs dans A et B [17].

Cette mthode pour le placement de ples est prsente dans [70, 71]. Les ides

dans ces articles sont la base de plusieurs autres algorithmes, en particulier de ceuxprsents dans [53] sur lesquels est base la fonction place de la Control SystemToolbox.

Commandabilit du systme

La matriceQ en (2.9) est aprs tout une transformation de similarit pour ltatdu systme. Alors, les proprits du systme original (A, B) sont aussi celles dusystme transform ( A, B). En particulier, notons que

C = QB QAQTQB (QAQT)n1QB = QC. (2.11)La commandabilit du systme reste invariante car le rang de Cest gal au rang de C.La diffrence est que lalgorithme orthogonal pour le placement ples ne dpend pasde linversibilit deC. Une fois que Fest dtermine, on peut toujours calculer F.Alors, o intervient la condition que le systme doit tre commandable? La rponsese trouve, bien sr, dans la partie o la plupart du calcul numrique est effectu, cest--dire, dans la solution du systme (2.10) pour les nvaleurs propres dsires. Notonsque si i na pas de rang plein par lignes, alors le calcul de son espace nul devientun problme mal pos car une petite perturbation des lments de i peut changerla dimension de lespace nul. Alors, on requiert que i ait rang plein, autrement dit,

quei,i = 1:n1soient diffrents de zro. Maintenant, si on observe soigneusement


29/110

2.2. APPROCHE POLYNOMIALE 21

la matrice de commandabilit

C =

b1 b11

b112 b1123

.... . .

b11 n1

(2.12)

on peut vrifier que la condition i= 0, i = 1:n 1 implique que le systme estcommandable,rank(C) =n.

Finalement, partir de (2.11) et (2.12) notons que QT

C =

C. Alors, Q peut

tre obtenue partir de la factorisation QR deC. Pour des raisons numriques, onconstruitQdirectement partir deAetB. Cependant, il est important de noter quela factorisation QR peut nous donner une approximation plus utile du rang de C(oude la commandabilit du systme) que celle obtenue partir des valeurs singulires.

Exemple 2.3

Considrons la matrice de commandabilit C de lexemple (2.2). En obtenant sa facto-risation QR, on observe les valeurs suivantes sur la diagonale du facteur triangulaireC:

-1.476..., 3.417..., -1.836..., 1.447..., -0.311..., -0.142..., 0.008...

Ainsi le systme est commandable et on peut appliquer lalgorithme dcrit ci-dessuspour le placement de ses ples. Le systme est commandable, mais a nempchepas queCsoit trs mal conditionne. Autrement dit, si par contre on veut placer lesples avec la formule dAckermann, on nobtiendra pas de rsultats satisfaisants.

En conclusion, le calcul du rang dune matrice est un exercice dinterprtationdes rsultats numriques, et cette interprtation ainsi que les mthodes numriquesutilises dpendent du contexte. Si on compte inverser la matrice analyse alors il vautmieux estimer son rang partir de ses valeurs singulires car elles sont directementlies au conditionnement et la distance la singularit de la matrice.

2.2 Approche polynomiale

Comme brivement rappel dans la section antrieure, le succs des logiciels deCACSD par approche espace dtat est fortement bas sur la thorie bien consolidede lalgbre linaire numrique et les logiciels de calcul numrique existants. Cepen-dant, notons que cette thorie nest pas propre lapproche espace dtat. Cest lefait que le systme soit reprsent par des matrices et vecteurs constants qui nouspermet de lappliquer. Par contraste, avec lapproche polynomiale 7 on reprsente le

7. On regroupe ici lapproche par quations polynomiales [58] et lapproche comportementale

[83].


30/110


systme sous la forme (2.3). Les objets mathmatiques du modle sont alors les po-

lynmes et les matrices polynomiales, et malheureusement il nexiste pas encore dethorie danalyse numrique solide pour ces objets.

Le dveloppement de logiciels de CACSD pour les polynmes est trs restreint. notre connaissance, parmi les logiciels existants qui permettent la manipulationdes polynmes et matrices polynomiales 8 seulement la Polynomial Toolbox pourMatlab 9 [84] est oriente vers les systmes en commande et nexcute quasiment quedes calculs numriques, et non symboliques 10.

Quelques autres exemples de logiciels numriques de CACSD pour lapprochepolynomiale sont issus des efforts de quelques groupes de chercheurs et tudiants 11

mais leur diffusion est encore trs limite et il manque une analyse rigoureuse des

proprits numriques. Comme pour lapproche espace dtat, mais une petitechelle, la varit des interfaces, des mthodes et des types dimplmentation rend trsdifficile la definition dun logiciel standard pour lapproche polynomiale. Cependant,les mmes caractristiques gnrales nonces dans la section 2.1 peuvent sappliqueraux logiciels de CACSD pour lapproche polynomiale.

Par rapport linterface pour lutilisateur, la conception dun logiciel de CACSDpour les mthodes polynomiales implique de mettre en place une structure qui permet lordinateur daccepter, de stocker et de reprsenter les variables (indetermines)des polynmes 12. Il est clair que cette interface peut ncessiter des temps de calculimportants dans certains cas.

Exemple 2.4

Prenons les cas de la multiplication C(s) =A(s)B(s)avec A(s) =A0+ A1s + R1515[s]etB(s) =B0 + B1s + R1515[s]deux matrices polynomiales de degrs

10 et 12respectivement. En gnral C(s) =C0+C1s+ Rnn[s]a degr 22 etpeut sobtenir numriquement avec lopration quivalente

C0 C22

=

A0 A10

B0 B12. . . . . .

B0 B12

sur les matrices relles. Avec une machine SUN Microsystems Ultra 5 (SunOS 5.9)

et Matlab 7, la version 3 de la Polynomial Toolbox a besoin de 16.3 secondes pour8. Par exemple: Maple, Mathematica, MACSYMA, Reduce, MuMath, etc...9. Voir www.polyx.com.

10. Comme on a mentionn dans le Chapitre 1, le calcul symbolique nest pas toujours adquatpour rsoudre des problmes avec des coefficient prcision finie. Il vaut mieux (au niveau prcisionainsi que temps de calcul) transformer le problme polynomial en un problme constant quivalentsur lequel on peut appliquer des mthodes numriques, cf. la section 2.3 de cette thse. Malheureu-sement, tous les problmes en commande avec des polynmes ou des matrices polynomiales ne sontpas numriquement rductibles (numerically reducible). Par consquent, lapplication et lanalysedes algorithmes symboliques reste importante pour certaines mthodes polynomiales en commande[76].

11. Voir http://ar.c-a-k.cz/polynomial/software.html.12. Noter cependant quaucun calcul symbolique nest considr, on se restreint aux logiciels nu-

mriques.


31/110


excuter linstruction mtimes(A,B)et dvoiler le rsultat, alors que le temps dex-

cution de la multiplication matricielle relle ci-dessus est seulement de 0.3 secondes.Les 16 secondes de diffrence sont utilises uniquement pour linterface (majoritaire-ment pour reprsenter C(s)sous la forme dune matrice avec ses lments qui sontdes polynmes).

Evidemment, une programmation soigne peut amliorer linterface. On peut mmela rduire au minimum (si lutilisateur est initi) et prsenter les matrices polyno-miales comme un ensemble de coefficients.

La plupart des logiciels de CACSD pour lapproche polynomiale utilisent oupeuvent utiliser les bibliothques numriques de base comme LAPACK ou BLAS.

Malheureusement la capacit de ces bibliothques numriques nest pas toujoursexploite au maximum. Pour illustrer ceci prenons le cas de la multiplication delExemple (2.4). LAPACK (BLAS) est appel travers Matlab quand la PolynomialToolbox excute linstructionmtimes(a,b). Lopration excute par lordinateur estune opration du niveau 3 de BLAS 13. Notons, nanmoins, quen utilisant la capa-cit de LAPACK (BLAS) pour manipuler les matrices avec un motif de zros dfini(matrices creuses,sparse matrices) et avec une structure particulire (matrices struc-tures,structured matrices), le calcul de C(s)pourrait tre plus efficace. Ainsi, unemeilleure exploitation des bibliothques ne peut tre assure que par lintermdiairedune meilleure mis en ouvre (programmation).

2.2.1 Problmes numriques et polynmes

Quel est le vrai problme des logiciels de CACSD pour lapproche polynomiale?On essaiera de rpondre cette question dans les paragraphes suivants. Dans lalittrature technique sur les problmes numriques en commande, deux critiquessont gnralement faites aux mthodes polynomiales :

1. Avec lapproche polynomiale, les problmes danalyse et de synthse en com-mande des systmes linaires sont gnralement rduits lanalyse des propri-ts des matrices polynomiales en tant quobjets algbriques (obtention de la

structure propre, le rang, etc.), la manipulation de ces matrices polynomiales(factorisation, triangularisation, etc.) et la solution dquations polynomialesou quations Diophantiennes [59]. Traditionnellement les mthodes pour ac-complir ces tches sont bases sur les oprations lmentaires dans lanneaudes polynmes (elementary polynomial operations) et il est prouv que ces op-rations peuvent causer une instabilit numrique [27, 108].

2. Bien quau niveau thorique les reprsentations (2.2) et (2.3) sont quivalentes,au niveau numrique la rputation des polynmes comme objets de modlisa-tion est plutt mauvaise. Les polynmes sont vus, en gnral, comme des objetsqui gnrent des problmes mal conditionns (voir mal poss) [45].

13. Une opration du niveau 3 signifie une opration matricematrice.


32/110


Linstabilit est spcifique lalgorithme utilis. Dans ce sens l, linstabilit

est due lapplication des oprations lmentaires et non pas lapproche polyno-miale elle-mme. On peut, donc, en utilisant dautres types doprations, concevoirdes algorithmes numriques stables. Malheureusement, la stabilit dun algorithmenassure pas lexactitude de la solution calcule, cette proprit dpend aussi duconditionnement du problme, cf. Exemple 2.1. Le conditionnement des problmespolynomiaux quon rencontre en commande (via lapproche polynomiale) est en g-nral lev. Cependant, comme on le verra par la suite, de nouveaux rsultats laissentsupposer quon peut contourner ces inconvnients.

Linstabilit potentielle des oprations lmentaires sur lanneau des polynmesest concentre dans le choix dun pivot14. Le choix du pivot polynomial se baseessentiellement sur son degr, et ne pas considrer ses coefficients peut introduiredes erreurs numriques importantes.

Exemple 2.5

On veut obtenir la forme de Smith S(s)de la matrice polynomiale

F(s) =

s 0 1 0 s 1 11 0 s + 1 00 1 1 s + 1

.

Aprs quelques oprations polynomiales lmentaires par lignes et par colonnes grou-pes dans L1(s)et C1(s)respectivement on obtient

L1(s)F(s)C1(s) =

0 0 1 00 0 0 11 0 s 00 1 0 s

F(s)

1 0 s 1 00 1 1 s 10 0 1 00 0 0 1

1 0 0 00 1 0 00 0 s2 s + 1 0 0 1

s

s2

2 + 1

=S1(s).

Jusquici nous navons pas de problmes numriques. Pour continuer jusqu lob-tention de la forme de Smith, on choisit comme pivot suivant llment de plus petitdegr dans la sous-matrice S1(3:4, 3:4), cest--dire. Avec ce pivot on introduit deszros dans les positions correspondantes. Ainsi on obtient

L(s)F(s)C(s) =

1 0 0 00 1 0 00 0 00 0 0 s4 2s3 + s2 + (2 1)s + (1 )

=S(s)

14. Un lment sur une ligne ou colonne partir duquel on peut introduire des zros sur une

matrice ou vecteur laide doprations par lignes ou colonnes.


33/110


avec = 1/et

L(s) =

0 0 1 00 0 0 11 0 s 0

s2 + s 1 s3 s2 + s s

,

C(s) =

1 0 0 s 10 1 s 1 s3 2s2 + 10 0 0 10 0 1 s2 + s

.

Si est trs petit, alors devient trs grand. Dans ce cas notons que, suivant la

prcision utilise, aprs larrondi invitable de lordinateur, les matrices calculesdeviennent L(s) =L(s), C(s) =C(s)et

S(s) =

1 0 0 00 1 0 00 0 00 0 0 s4 2s3 + s2 + 2s

ce qui dmontre linstabilit de lalgorithme. En fait la matrice S(s) nest pas laforme de Smith de A(s)lgrement perturbe,

L1(s)S(s)C1(s) =

s 0 1 0 s s 11 0 s + 1 00 1 1 s + 1

=F(s),

car linformation sur llment (2, 3)de F(s)sest compltement perdue.

Les oprations polynomiales lmentaires ont leur intrt et leur importance carelles constituent loutil mathmatique avec lequel sexplique la thorie de lapprochepolynomiale. Cependant, il est clair que malgr cet intrt acadmique, les algo-rithmes polynomiaux classiques doivent sadapter pour prendre en compte les pro-

blmes numriques. Ce besoin dadaptation a aussi t observ dans lapproche espacedtat et lalgbre linaire numerique, cf. la section 2.1. Notons que le phnomneillustr dans lexemple antrieur ressemble ce que lon observe avec lliminationGaussienne [33], o choisir un pivot uniquement par sa position sur la diagonale peutcauser les mmes problmes numriques 15.

La solution donne ces problmes par lalgbre linaire numrique se dnommestratgie de pivot (pivoting) [33]. Il y a plusieurs stratgies de pivot mais lidegnrale consiste choisir comme pivot llment de plus grande magnitude. Mal-heureusement ces stratgies de pivot ne sont pas toujours applicables dans le cas desoprations polynomiales lmentaires, comme pour lExemple 2.5.

15. Considrer par exemple la matrice 1

1 1

avec trs petit.


34/110


35/110

2.3. MTHODES POUR LES MATRICES POLYNOMIALES 27

alternative qui peut tre tout aussi efficace quune autre, voire parfois meilleure. On

peut toujours trouver des exemples pour lesquels les mthodes polynomiales ont unemeilleure performance. Evidemment, pour chaque exemple il existera srement uncontrexemple, raison pour laquelle nous ne poursuivrons pas cette discussion quenous croyons sans intrt.

Il est vraiment important de noter que, tout comme au niveau thorique chaqueapproche a ses avantages et dsavantages et surtout sa propre procdure danalyse,au niveau numrique on doit rsoudre des problmes diffrents qui doivent sanalyserde faon diffrente.

Reprenons lExemple 2.6, pour lequel on a dcrit deux problmes diffrents dontles solutions, avec une prcision infinie, sont quivalentes. Dun ct on a le problme

de lobtention des valeurs propres pour lequel la matrice Aest trs bien conditionne,et de lautre ct le problme du calcul des racines du polynme caractristique.Cest en analysant ce dernier problme quon conclut que le polynme p(s)est malconditionn pour le problme de lobtention de ses racines. Par contre, si on compareles racines de p(s)avec les valeurs propres de A, la seule chose quon peut conclurecest que la mthode qui consiste obtenir les valeurs propres dune matrice encalculant les racines du polynme caractristique nest pas stable.

En conclusion si on a dcid dappliquer lapproche polynomiale ou sil on a unproblme reprsent avec des polynmes, lanalyse doit tre faite dans le cadre despolynmes. Cela dit, il est important de consolider une thorie dalgbre polynomialenumrique qui adapte lanalyse numrique aux polynmes. On a vu que cette thorie

est actuellement en train de se dvelopper sur les bases de la gomtrie algbriqueet de lalgbre commutative [98].

Nous croyons donc quen contournant les oprations polynomiales lmentaires,et avec une algbre polynomiale numrique comme outil danalyse, il est unique-ment une question de temps pour que le dveloppement de logiciels de CACSD pourlapproche polynomiale rattrape celui de lapproche espace dtat.

2.3 Mthodes pour les matrices polynomiales

Il existe diffrentes approches pour rsoudre numriquement les problmes encommande par approche polynomiale. Ici nous les regroupons en deux grandes cat-gories17:

Exprimer le problme polynomial comme un problme de commande dun sys-tme en espace dtat et appliquer les mthodes numriques et logiciels deCACSD propres cette approche, cf. la section 2.1 de cette thse. Ensuitela solution au problme en espace tat est reformule en termes du problme

17. Voir [37] pour une classification plus dtaille. Ici on parle uniquement des problemes poly-nomiaux qui sont numriquement rductibles. Cependant ils existent des problemes, qui nont pascette proprit, pour lesquels le calcul symbolique est appliqu mais on ne les tude pas dans cette

thse, voir [76].


36/110


37/110


sont gales aux zros recherchs. Le premier pas de lAlgorithme 2.1 est la construc-

tion de F(s). Ensuite les pas 2 et 3 consistent obtenir la factorisation QZ de F(s)F1= QF1Z, F0 = QF0Z

et evaluer le quotient des valeurs diagonales de F0 et F1 [72]. Notons que pour cetexemple, la forme compagne de A(s) rsulte en la matrice F(s) de lExemple 2.5.Donc, la solution notre OPP est simplement lensemble des valeurs propres de F0.

La complexit algorithmique 21 (algorithmic complexity) dpend du nombre dop-rations arithmtiques lmentaires en virgule flottante (floating point operations,

flops) comme la multiplication ou la somme, effectues chaque pas. Par cons-

quent, on souhaite que le CEP admette une formulation simple et galement que sasolution soit facilement traduite en la solution du OPP. Lide est donc de concentrerle gros du calcul sur la solution du CEP. Cet objectif nest pas toujours atteint. Ainsidans le Chapitre 4 nous dcrirons des algorithmes o le calcul ralis pour les pas 1et 3 de lAlgorithme (2.1) peut tre plus coteux que celui requis pour le pas 2.

Pour analyser la stabilit de lAlgorithme 2.1 on le divise en 3 sous-algorithmes.Il est facile de montrer que si lun des sous-algorithmes est instable, alors lalgo-rithme global est instable [43, 45]. On sintresse donc la stabilit de chaque sous-algorithme. En particulier, il est dsirable que lalgorithme de solution du CEP (pas2) soit stable. Malheureusement cet objectif ne garantit pas la stabilit de lalgo-rithme global. Comme rappel dans la section 2.2.1., lanalyse doit tre faite partirdes polynmes. Par consquent, non seulement la solution du CEP, mais aussi ler-reur arrire de la mthode numrique applique au CEP doivent tre traduites entermes des coefficients des polynmes ou des matrices polynomiales analyses. Par-fois on verra que de petites erreurs dans les coefficients du CEP sont traduites endes erreurs considrables dans les coefficients du OPP [101], cf. la section 3.1 danscette thse.

Il est possible dobtenir une borne suprieure de lerreur arrire pour le OPP partir de lerreur arrire pour le CEP. Dans cette thse (Chapitre 4) on fait cetype danalyse. Cependant, on peut vrifier que cette borne suprieure est parfoispessimiste. Cest lanalyse de la gomtrie du problme et lalgbre polynomiale nu-

mrique qui permettront dobtenir des bornes plus prcises, ainsi que de comprendrela sensibilit (conditionnement) des polynmes ou des matrices polynomiales analy-ses. Cette tude dpasse les objectifs de cette thse. Nanmoins on consacre quelqueslignes dans la section 3.1 pour illustrer ces ides, en analysant quelques algorithmesexistants pour le problme des valeurs propres dune matrice polynomiale. Lappli-cation de ces techniques aux nouveaux algorithmes prsents dans cette thse estpropose comme travail futur.

On a vu dans lExemple 2.7 que la linarisation dune matrice polynomiale est uneprocdure qui entre dans le cadre du pas 1 de lAlgorithme 2.1. Le CEP quon analyse

21. Estimation du nombre doprations effectues par lordinateur en excutant un algorithme.Cette estimation est reprsente comme O(nN): de lordre de nN o n est un paramtre du problme,

comme la dimension, et Nest un entier positif [33].


38/110


ensuite se pose sur le faisceau obtenu et peut tre rsolu en appliquant des mthodes

numriques comme lobtention dune forme canonique de Kronecker, ou une facto-risation QZ par exemple [105]. Cette approche appele par la suite lapproche desfaisceaux (pencil approach) est trs rpandue dans la littrature technique, en parti-culier pour lobtention de la structure propre dune matrice polynomiale, problmeque lon analyse dans les Chapitres 3 et 4 de cette thse. Dautre part, le CEP peuttre formul aussi laide des matrices de Sylvester. Les matrices de Sylvester sontdrives naturellement des matrices polynomiales. Elles sobtiennent en arrangeantles coefficients de la matrice polynomiale dans une matrice Toeplitz par blocs, cf.lExemple 2.4. Dans les Chapitres 3 et 4 on montre que cette approche, appele parla suite lapproche Toeplitz (Toeplitz approach) est trs efficace pour le problme ducalcul de la structure propre dune matrice polynomiale, et que cest une alternative

fiable lapproche des faisceaux.Les oprations quon effectue sur les matrices Toeplitz sont en gnral des fac-

torisations pour obtenir les rangs, les espaces nuls ou pour rsoudre des systmesdquations. Pour accomplir ces tches plusieurs mthodes numriques peuvent treutilises: la dcomposition en valeurs singulires, llimination Gaussienne avec pi-vot, les factorisations orthogonales comme la factorisation QR, ou encore dautresmthodes qui servent a dvoiler le rang dune matrice (rank revealing methods, RRM)[15]. Toutes ces mthodes sont trs bien tudies dans la littrature [33] et leur bonnesproprits numriques sont prouves [43, 99]. Ici on dcrit brivement quelques pro-prits des mthodes quon utilise dans cette thse.

2.3.1 Dcomposition en valeurs singulires

La dcomposition en valeurs singulires (singular value dcomposition, SVD)

=PTM Q

dune matrice constante M Rmn peut tre implmente comme un algorithmenumriquement stable22 [33]. Dans ce cas, si P, Qet sont les matrices calcules,on peut dmontrer [99] que

= PT(M+ )Q

avec2 O()M2.

De plus, si i, i = 1:min(m, n)sont les valeurs singulires calcules de M, alors

|i i| O()M2.

Alors, on peut dterminer le rang de M, dnot = rank(M), en appliquant la SVDet en comptant le nombre de valeurs singulires infrieures M2, o est unseuil dpendant de , cf. lExemple 2.2. Il en dcoule que MQ(:, + 1 : n)2 est

22. Limplmentation fiable de la SVD nest pas facile. Il existe diffrentes implmentations, mais

cela dpasse le cadre de cette thse. Pour plus de dtails voir par exemple [33].


39/110


40/110


dterminer le rang deMen appliquant la factorisation LQ et en comptant le nombre

de colonnes de L22 telles queL222 M2 avec un seuil qui dpend de .Si rank(M) = , alorsMQ(:, + 1 : n)2 est suffisamment faible et la matriceQ(:, + 1 :n)constitue une base calcule de lespace nul de M.

Linconvnient de la factorisation LQ en tant que RRM est que la normeL222ne diminue pas toujours suffisamment rapidement. Heureusement, ce problme seprsente seulement pour des matrices soigneusement choisies, cf. lExemple 5.5.1dans [33].

2.3.3 Forme Echelon L

Supposons quon veuille rduire encore plus la complexit algorithmique par rap-port aux mthodes SVD et LQ des sections prcdentes. Une possibilit est de calculerla factorisation LQ sans mettre jour et stocker la matriceQ, qui est une successionde matrices de Householder Hi appliques la matrice M. Le calcul de la matriceL uniquement requiert 2(mn2 13n3) flops [33]. Noter quavec cette mthode, ap-pele forme chelon L, on ne peut pas rcuprer une base orthogonale de lespacenul droite de M. Cependant, partir de Lon peut construire une base naturelle(non orthogonale en gnral) de lespace nul gauche en rsolvant quelques systmesdquations triangulaires. Par exemple supposons que pour une matriceMdonne,aprs lapplication de 3 matrices de Householder, on obtienne la forme chelon

L= M H1H2H3

11 0 0 021 22 0 031 0 0 041 42 43 051 52 53 0

.

Cela veut dire que les troisime et cinquime lignes de M sont linairement d-pendantes. partir de L notons que les coefficients de la combinaison linaire quignre la cinquime ligne peuvent tre rcuprs en rsolvant, via une procdure desubsitution arrire [33], le systme triangulaire suivant

k1 k2 k4 11 0 0

21 22 041 42 43

51 52 53 , (2.15)

et donc k1 k2 0 k4 1

M= 0.

La procdure de substitution est galement numriquement stable [43], et donc laqualit de la solution de (2.15) est aussi bonne que celle de la matrice calcule L.

Notons quavec une permutation de lignes adquate, la matrice L peut tre misesous la forme classique chelon par colonnes (Column Echelon Form, CEF). Parfoisdonc on dit que L est la CEF de M. On a utilis cette notation dans quelques

travaux comme [124, 126] issus de cette thse. Finalement notons que par dualit,


41/110


la factorisation LQ de MT est aussi la factorisation QR de Mavec une stratgie de

pivot par colonnes. Alors, on peut aussi dfinir une forme chelon R pour calculerune base naturelle de lespace nul droite de M.

2.3.4 Mthode gnralise de Schur

Comme on le dmontrera dans les chapitres suivants, un des avantages de lap-proche Toeplitz est la possibilit dexploiter la structure matricielle. Une faon consiste utiliser les mthodes bases sur la thorie du dplacement de rang [51] comme lamthode gnralise de Schur (Generalized Schur Method, GSM) [52]. Ici on prsentebrivement les rsultats quon utilise dans cette thse.

Dans le cas particulier dune matrice symtrique M Rnn

on peut dfinir ledplacement (displacement)

M =M F M FT =XXT (2.16)avec

= diag{Ip, Iq} =

Ip 00 Iq

op et qsont des dimensions appropries. La matrice Fqui est strictement triangu-laire infrieure est appele loprateur de dplacement (displacement operator). Onappelle la matrice Xle gnrateur symtrique (symmetric generator) deM. Le rangdu dplacement (displacement rank) est r = p + q= rank(M).

Le gnrateurXnest pas unique, nimporte quelle matrice Ttelle que TTT =TTT = donne un autre gnrateur XT. En particulier, on peut chercher unematriceTtelle que le nouveau gnrateur ait la forme suivante

XT = X=

x11 0X21 X22

(2.17)

o x11 est un scalaire et la matrice X22 est de dimension (n 1) (r 1). On ditque Xest un gnrateur propre (proper generator). Dans la section 4.4.2 de [51], unalgorithme est dcrit pour rendre propre un gnrateur quelconque. Cet algorithmese base sur lapplication de matrices de Householder et de transformations hyperbo-liques [33]. Les gnrateurs propres ont un rle clef dans la mthode gnralise de

Schur. Il existe plusieurs versions de cette mthode, dans la section 7.4 de [51] onpeut trouver une version trs gnrale. Ici on utilise le rsultat suivant.

Supposons quon ait un gnrateur symtrique propreXsous la forme (2.17) quivrifie lquation de dplacement (2.16). Alors, la matrice

M=M

x11X21

[xT11 X

T21] =

0

M22

a ses premires colonne et ligne gales zro. La matrice M22 est le complment deSchur de M. Un gnrateur pour M est donn par X = [F X1 X2] o F est lemme oprateur de dplacement que dans (2.16), cest--dire

M FM FT = XXT. (2.18)


42/110


Maintenant, commeFest strictement triangulaire infrieure, cest--dire que sa pre-

mire ligne est nulle, partir de (2.18) on peut vrifier quen liminant les premiresligne et colonne de Met la premire ligne de Xon obtient lquation de dplacement

M22 FM22FT = X2XT2,

o Fsobtient en liminant les premires ligne et colonne de F. Donc, si on obtientune reprsentation propre de X2 ( laide de lalgorithme dans la section 4.4.2 de[51]), alors on peut obtenir le complment de Schur de M22. Avec cette procdureitrative, la fin on peut obtenir la factorisation de Cholesky M =LLT.

Limportance de la mthode gnralise de Schur est lie la possible rductiondun ordre de magnitude de la complexit algorithmique quand on factorise des ma-

trices structures. Formellement, on dit quune matrice est structure si le rang de sondplacement est petit. Par exemple, le rang du dplacement dune matrice Toeplitzest 2. Supposons que M R100100 soit Toeplitz et symtrique. Si on veut obtenirsa factorisation de Cholesky laide de la mthode gnralise de Schur dcrite ci-dessus, alors le nombre de colonnes du gnrateur est seulement 2. Evidemment lenombre doprations excutes sera plus petit que si lon considre les 100 colonnesde M.

Si la mis en oeuvre de la mthode gnralise de Schur est faite en considrant les4 perfectionnements proposs dans la section 2.5 de [52], alors sa stabilit numriquepeut tre garantie pour le cas des matrices Toeplitz symtriques et dfinies positives.


43/110

Chapitre 3

Zero structure of polynomial

matrices

Our objective in this chapter is to develop a numerical algorithm to obtain thefinite and infinite structures of polynomial matrices. The theory of polynomial ma-trices is extendedly treated in the literature, so here we present only a few resultsformulated in a form and with a notation convenient for the sequel. Interested rea-ders can consult mathematical books on polynomial matrices like [31]. In [12, 50, 109]some results on polynomial matrices related with systems theory are well explained.

LetA(s) Rmn[s]be a polynomial matrix withm rows and n columns, degreedand rankr min(m, n). We write A(s)as the matrix polynomial

A(s) =A0+ A1s + + Adsd, (3.1)

with coefficients Aj Rmn forj = 1:dand s a complex indeterminate 1.The structural information of polynomial matrices has important applications in

control and systems theory. If a linear system is represented with polynomial matricesin the form (2.3), then the locations of its zeros and poles, which determine thedynamics of the system, are contained in the zero structure 2 of polynomial matricesN(s) and D(s) [50]. In the problem of decoupling of linear systems for example,

infinite structural indices of a suitable polynomial matrix are needed to determine ifthe system is decouplable [21], and also to determine the structure that could have thedecoupled closed loop system [122]. Model matching [67] and disturbance rejection[7] are other examples of control problems where the zero structure of polynomialmatrices plays a fundamental role. The zero structure of a polynomial matrix is alsoinstrumental to its spectral factorization which has applications in several optimaland robust control problems [34, 60], cf. Chapter 5 in this thesis.

1. All the results presented in this chapter are straightforwardly extended to complex-valuedmatrix coefficients.

2. The zero structure is also sometimes called the eigenstructure.

35


44/110

36 CHAPITRE 3. ZERO STRUCTURE OF POLYNOMIAL MATRICES

The classical tool to analyse the structure of a polynomial matrix is the canonical

Smith form [50, 109].

Definition 3.1

LetA(s)be as in (3.1). Its canonical Smith formis given by

SA(s) =U(s)A(s)V(s) =

f1(s). . . 0

fr(s)

0 0

(3.2)

where matrices U(s) and V(s) are unimodular3. Monic polynomials fi(s), i = 1:r,

called the invariant polynomialsof A(s), are such that fi(s) divides fi+1(s). Theroots of the invariant polynomials are called the finite zerosof A(s). The numbermAof times that a given zeros = z appears as a root in the invariant polynomials ofA(s) is its algebraic multiplicity. The number mG of distinct invariant polynomialsfor whichz is a root is its geometric multiplicity.

From the above definition and for a given zero z , the Smith form (3.2) could bewritten as follows:

SA(s) =SAz(s)Sz(s) =

1. . .

1 0(s z)k1

. . .(s z)kmG

0 0

f1(s). . .

frmG(s) 0frmG+1(s)

. .. fr(s)

0 0

(3.3)

where fi(s), i = 1:rhave no roots at s = z. Notice that integerski, i = 1:mG, calledhere thestructural indicesassociated to z are such that ki ki+1. We say thatA(s)has a zero at z of orderki. MatrixSAz(s)will be called in this thesis the Smith format z ofA(s).

Now let U(s) = U1(s) be the inverse ofU(s). Matrix U(s) is also polynomialbecause U(s) is unimodular. In the following expressions, let Xi(s) denote the ith

3. A polynomial matrix is unimodular if its determinant is a non-zero constant. Matrices U(s)

and V(s) here gather the elementary row and column polynomial operations, cf. Example 2.5.


45/110

37

column of a matrix X(s). From (3.2) and (3.3) we can check that

A(s)V1(s) = U1(s)f1(s)...

A(s)VrmG(s) = UrmG(s)

frmG(s)A(s)VrmG+1(s) =

UrmG+1(s)(s z)k1frmG+1(s)...

A(s)Vr(s) = Ur(s)(s z)kmG fr(s)A(s)Vr+1(s) = 0

...A(s)Vn(s) = 0.

(3.4)

From (3.4) notice that a finite zero z can also be defined as a value ofs such thatrankA(z) < r. The geometric multiplicity of z is mG = r rankA(z), and thealgebraic multiplicity is mA =k1+k2+ +kmG . Structural indices ki, i= 1:mGare interpreted as the number of times thatA(s)V(s)has to be differentiated (w.r.t.s) in order that column r mG+ ibecomes non-zero when evaluated at s= z. Wesummarize these results in the following Lemma. For more details see [4, 106] andthe proof of Proposition 3.1 in this Chapter. Notice the analogy with the constantcase of Jordan canonical forms [27], see also [31].

Lemma 3.1

LetA(s) be as in (3.1). For a given finite zero z with geometric multiplicity mG =r rank A(z), there exists structural indiceski> 0,i = 1:mGsuch that the algebraicmultiplicity ofz is mA= k1+ k2+ + kmG, and a series of vectorsvi1, vi2, . . . , viki ,i= 1:mG, called eigenvectorsassociated to z such that

A0 A1 Aki1A0 Aki2

. . . ...

A0

viki...

vi2vi1

=TkiV= 0 (3.5)

withv11, v21, . . . , vmG1 linearly independent and where

Aj = 1

j!

djA(s)

dsj

s=z

. (3.6)

Integer ki is the length of the ith chain of eigenvectors associated to z, mG is thenumber of chains of eigenvectors associated to z. Matrix Tki in (3.5) is in a blockToeplitz form.

Definition 3.2

We define the finite structure of A(s) as the set of finite zeros, their respective

multiplicities and the chains of associated eigenvectors.


46/110


Example 3.1

The polynomial matrixA(s) =

s2 42 3s s 6

has a Smith form SA(s) = diag{1, s3 6s2 + 12s 8}, so a finite zero at s = 2with algebraic multiplicity 3 and geometric multiplicity 1. Now, from Lemma 3.1and equation (3.5) it holds

4 4 4 0 1 04 4 3 1 0 0

0 0 4 4 4 00 0

4

4

3 1

0 0 0 0 4 40 0 0 0 4 4

0.75010

11

= 0.

Hence, the 3 eigenvectors associated to s = 2are

v1=

11

, v2=

10

, v3=

0.750

.

Theoretically speaking, s = can also be an eigenvalue ofA(s). Traditionally

the structure at infinity ofA(s)is analyzed via its canonical Smith MacMillan format infinity.

Definition 3.3

LetA(s)be as in (3.1). Its canonical Smith MacMillan form at infinityis given by

SA(s) =U(s)A(s)V(s) =

s1

. . . 0sr

0 0

, (3.7)

with possible negative integers i i+1, i = 1:r called structural indices at infinityand where U(s) and V(s) are biproper 4 rational matrices. Ifi is negative, we saythatA(s)has apole at infinityof orderi, if it is positive then we have a MacMillanzero at infinityof order i. The sum denoted by

z =r

i=t

i, (3.8)

with index t such that i > 0 for i tis called the MacMillan degree at infinity(ornumber of MacMillan zeros at infinity) ofA(s).

4. A rational matrix is biproper if it is non-singular when s. Matrices U(s) and V(s) here

group the elementary row and column operations over the ring of rational functions.


47/110

39

In practice, in order to analyze the behavior at infinity, we use the change of

variable s= s1

. Notice that s 0whens , so the structure at infinity ofA(s)is related to the structure at zero of the dual polynomial matrix

A(s) =A0+ A11

s+ + Ad 1

sd =

1

sd(A0s

d + A1sd1 + + Ad) = 1

sdAdual(s).

In other words,

SA(s) =SA0(s) =

1

sdSAdual0 (s)|s=s1 . (3.9)

Notice that A(s) is a rational matrix in the indeterminate s. The extension of theSmith form to rational matrices yields the Smith Macmillan form which allows toconsider not only zeros but also poles 5 of the analyzed matrix [50, 109]. As a conse-quence, a polynomial matrix can be considered as a rational matrix whose poles are

all located at infinity.

From (3.3), (3.7) and (3.9), we can check that the structure at infinity dependson the number and lengths of the chains of associated eigenvectors at s = 0 of thedual matrixAdual(s). LetmG =r rank Adbe the geometric multiplicity ofs = 0in Adual(s), and li, i = 1:mG be the structural indices at s = 0 in Adual(s). Thestructural indices at infinityi,i = 1:rare thus given byi= dfor i = 1:r mG,andi+rmG =lidfori = 1:mG. The algebraic multiplicity ofs = 0inAdual(s)is m = l1+ +lmG . In the remainder of this thesis we simply consider thatA(s)has m zeros at infinityand thatmG is the geometric multiplicity at infinity.This notation will be very useful in Chapter 5 for example. In the present Chapter,

this notation allows us to define the structure at infinity by extending the results ofLemma 3.1.

Lemma 3.2

Let A(s) be as in (3.1). Let mG = r rankAd be the geometric multiplicity atinfinity. Then there exists a series of integers li > 0 for i = 1:mG such that thealgebraic multiplicity at infinity is m = l1+ l2+ +lmG . There also exists aseries of eigenvectors at infinityvi1, vi2, . . . , vili fori = 1:mG such that

Ad Ad1 Adli+1Ad Adli+2

. . . ..

.Ad

vili...

vi2vi1

=TliV= 0 (3.10)

withv11, v21, . . . , vmG1linearly independent. Integerliis the length of theith chainof eigenvectors at infinity, mG is the number of chains of eigenvectors at infinity.Notice that block Toeplitz matrix Tli in (3.10) is obtained from (3.5) and (3.6) withAdual(s)and z = 0.

Definition 3.4

We define the infinite structureofA(s) as the multiplicities and the chains of asso-ciated eigenvectors ats = 0of the dual matrix Adual(s) =Ad+ Ad1s + + A0sd.

5. A pole is a value of the indeterminate for which a rational function tends to infinity.


48/110


Remark 3.1

From themzeros at infinity ofA(s), only those corresponding to a chain of eigen-vectors at infinity of length greater than d are also MacMillan zeros at infinity as inDefinition 3.3. So, equation (3.8) giving the MacMillan degree at infinity ofA(s)canalso be written as

z =

mGi=q

(li d),

with index q= t r+ mG such that li> dfor i q.

Finally, from Section 3.6 in [109], we extract the following result involving the

structure of polynomial matrices. It will be useful in the remainder of this thesis.

Lemma 3.3

LetA(s)be as in (3.1). Let pbe the number of poles ofA(s)(it has only poles atinfinity),mfthe number of finite zeros (including multiplicities) andzthe numberof MacMillan zeros at infinity (MacMillan degree at infinity), then

p= z+ mf+ nr+ nl

wherenrand nlare, respectively, the sums of the degrees of the vectors in a minimalpolynomial basis of the right and left null-spaces ofA(s)6.

Considering our definition of zeros at infinity as the zeros at s = 0 of the dualmatrixAdual(s), we can easily reformulate the last Lemma as follows:

Corollary 3.1

Under the assumptions of Lemma 3.3, it holds

rd= m+ mf+ nr+ nl (3.11)

wherem is the number of zeros at infinity.

Example 3.2

The dual matrix ofA(s)in Example 3.1 is given by

Adual(s) =

1 4s2

3s + 2s2 s 6s2

.

Its Smith form at s = 0 is SAdual0 (s) = diag{1, s}, so matrix A(s) has one zero atinfinity and, from (3.10), one eigenvectorw1= [0 1]T at infinity such thatA2w1 = 0.Notice that equation (3.11) is verified withm = 1, mf = 3 and nr =nl = 0.

6. For more details about minimal polynomial null-space bases, see Chapter 4.


49/110

3.1. COMPUTING THE FINITE ZEROS 41

Example 3.3

Here is an example of a control application of the concepts introduced in this section.Consider a linear system represented by the transfer matrix

s 3 s2 + s + 1

0 s2 1

s3 00 s3 1

1=N(s)D1(s)

parametrized by a real scalar. The above polynomial matrices are right coprime, sothe finite poles and zeros of the system are, respectively, the finite zeros ofD(s)andN(s) [50]. The system has therefore poles at s = 0 (triple), s = 1 and s =0.5 0.866i. The Smith form ofN(s)is SN(s) = diag{1, s3 3s2 2s + 6}, so the systemhas zeros at s = 3, s =1.4142. Now, suppose we want to determine the values ofparameter for which the system is decouplable by static state feedback. This is thecase if and only if the sum of zeros at infinity is eq

Documents

Algorithmes numériques pour les polynomiales.pdf