Scilab in FRENCH Maths-S-Specialite_207893

7/23/2019 Scilab in FRENCH Maths-S-Specialite_207893

1/63

Ressources pour la classe terminalegnrale et technologique

MathmatiquesSrie S

Enseignement de spcialit

Ces documents peuvent tre utiliss et modifis librement dans le cadre des activitsd'enseignement scolaire, hors exploitation commerciale.

Toute reproduction totale ou partielle dautres fins est soumise une autorisationpralable du Directeur gnral de lenseignement scolaire.

La violation de ces dispositions est passible des sanctions dictes larticle L.335-2du Code la proprit intellectuelle.

14 fvrier 2012

MENJVA/DGESCO eduscol.education.fr/progRessources

pour

le

lyc

e

gn

ralettechno

logique

duSCOL


2/63

Introduction

Un enseignement qui prend appui sur la rsolution de problmes

Le programme de lenseignement de spcialit de la terminale scientifique rintroduit lalgbre

linaire au lyce. Mais lalgbre linaire du lyce des annes 1980 sappuyait sur les vecteurs du planet de lespace, et lintroduction des espaces vectoriels. Lentre propose aujourdhui est matricielle :il sagit de faire jouer un rle des tableaux de nombres, lorsquils sont particulirement adapts lcriture et la rsolution de certains problmes.

La premire partie du prsent document prsente donc des problmes o lintroduction des matricesvient naturellement et apparat comme une simplification dcriture et de lecture. Le vocabulairenouveau est introduit en situation. Les dfinitions et les thormes auxquels il est ncessaire de fairerfrence ne sont pas sortis du contexte du problme, au moins dans un premier temps.

Une petite mise en ordre des notions nouvelles est propose dans la seconde partie. Des dfinitionsconvenables et des thormes bien rdigs sont en effet indispensables au jalonnement des avancesmathmatiques. Les professeurs sont invits, conformment la recommandation du programme, ne

pas dmarrer directement par la prsentation des contenus thoriques exposs dans la seconde partie,mais essayer la dmarche propose consistant introduire les notions dans le cadre de problmes rsoudre. Cette dmarche semble aujourdhui susceptible daccrocher des lves quil sagit deconqurir et de convaincre de lintrt pour eux de la poursuite dtudes scientifiques.

La base de connaissances introduite en seconde partie permet ensuite une prsentation dautrescontenus du programme, en se situant de nouveau dans le contexte de problmes. Ainsi la troisime

partie dveloppe plus compltement certains thmes mentionns comme exemples dans le programmeet ouvre des perspectives pour aborder dautres sujets. On y trouvera notamment des connexions

possibles avec la partie arithmtique du programme.

Des liens vers des ressources sont rgulirement proposs. Il sagit dans certains cas doutils

permettant de se librer de quelques phases de calcul dont la conduite et lachvement loigneraienttrop les lves du problme trait. On doit pouvoir insister le temps quil faut sur certains points decalcul dont la matrise est un rel objectif de lenseignement, quitte sen remettre dautres momentsaux outils dont on dispose aujourdhui pour pouvoir concentrer lattention des lves sur le problme rsoudre et les raisonnements ncessaires pour y parvenir.

Ministre de lducation nationale, de la jeunesse et de la vie associative (DGESCO) Fvrier 2012

Mathmatiques Srie S Enseignement de spcialit Matrices

http://eduscol.education.fr


3/63

TabledesmatiresI. Quelques problmes faisant apparatre des matrices .................................................... 4

A. Un problme deux compartiments 4

1. Le problme............................................................................................................................. 42. Commentaires sur le problme................................................................................................ 43. Dautres faons dcrire le problme ...................................................................................... 5

B. tude, gestion et prvision conomiques 6

1. Des tableaux de nombres pour la gestion................................................................................ 62. laboration dun indice de prix ............................................................................................... 73. Gestion des admissions et sorties dans un hpital................................................................... 8

C. Le modle durnes de T. & P. Ehrenfest 11

1.

Prsentation du problme ...................................................................................................... 112. tude du cas N = 2 ................................................................................................................ 11

D. Reprsentation dun graphe. Notion de connexit 15

1. Parcourir un graphe ............................................................................................................... 152. Matrice dadjacence dun graphe .......................................................................................... 163. Lire la connexit dun graphe sur sa matrice dadjacence..................................................... 17

E. Marches alatoires 17

1. Marche alatoire sur un segment........................................................................................... 17

2. Marche alatoire aux sommets dun ttradre....................................................................... 193. Un retour en arrire est-il possible ?...................................................................................... 20

F. Pertinence dune page web 20

1. De la recherche dans une bibliothque la recherche dans un graphe.................................. 202. Un exemple............................................................................................................................ 213. Mesurer la pertinence ............................................................................................................ 214. Pertinence et probabilits ...................................................................................................... 23

G. Traitement de limage 25

1. Numriser des images imager les nombres ....................................................................... 252. Oprations sur les images...................................................................................................... 253. Comment modifier la forme dune image ? .......................................................................... 264. Des matrices pour raliser des transformations..................................................................... 27

II. Dfinitions et premiers calculs avec des matrices ..................................................... 28

A. Matrices. Oprations 28

1. Quelques dfinitions, quelques notations .............................................................................. 282. Addition, produit par un scalaire ........................................................................................... 283. Produits de matrices .............................................................................................................. 294. Proprits du produit des matrices carres dordre n ............................................................ 30

Ministre de lducation nationale, de la jeunesse et de la vie associative (DGESCO) Page 2 sur 62




4/63

B. Les matrices sont-elles inversibles ? 30

C. Puissances de matrices carres dordre 2 ou 3 31

1. Quelques matrices particulires............................................................................................. 312. Diagonalisation ventuelle dune matrice carre dordre 2................................................... 33

D. Traitement matriciel des suites de Fibonacci 341. Recherche dune formule close pour le terme gnral .................................................... 342. Trouve-t-on toujours une combinaison linaire de suites gomtriques ? ............................ 35

E. Retour sur les marches alatoires 35

III. Loutil matrices luvre Complments et exemples ..............................................37

A. Matrices en arithmtique 37

1. Cryptographie : le chiffrement de Hill .................................................................................. 372. Approximation des nombres rels ......................................................................................... 39

B. Matrices et probabilits 44

1. La fougre de Barnsley.......................................................................................................... 442. Triangles rectangles pseudo-isocles. Points coordonnes entires sur une hyperbole.................. 463. Le problme du collectionneur.............................................................................................. 484. Retour sur le modle durnes de T. & P. Ehrenfest............................................................... 51

C. Suites lies par une relation non linaire 53

1. Discrtisation......................................................................................................................... 54

2. Recherche dun quilibre....................................................................................................... 563. Linarisation autour du point dquilibre (d/c , a/b).............................................................. 564. Modle perturb .................................................................................................................... 57

IV. Annexe : utiliser Scilab pour numriser des images................................................. 59

A. sLes matrices 59

1. criture .................................................................................................................................. 592. Oprations ............................................................................................................................. 59

B. Les couleurs 59

1. Principe du codage ................................................................................................................ 592. Affichage du dessin en 256 teintes de gris ............................................................................ 59

C. Les transformations 60

D. Les codes Scilab 60

1. Pour afficher une matrice M.................................................................................................. 602. Oprations ............................................................................................................................. 60





5/63

I. Quelques problmes faisant apparatre des matrices

Dans cette partie, le vocabulaire spcifique aux matrices et les oprations sur les matrices ne sont passupposs connus. Lorsque la ncessit sen fait sentir, des matrices sont introduites, sur lesquelles on

peut faire des oprations (le produit de Cayley notamment, couramment utilis sous le simple nom deproduit, et qui est celui propos par la calculatrice scientifique). La partie II proposera une tude plus

systmatique, mais la recommandation du programme est de commencer par des rsolutions deproblmes motivant une introduction des matrices et non par une introduction ex nihilo de cesdernires et encore moins de lalgbre linaire.

A. Un problme deux compartiments

1. Le problme

On conserve dans une enceinte une population dtres unicellulaires qui ne peuvent se trouver que

dans deux tats physiologiques dsigns par A et B. On dsigne par et les effectifs exprims en

milliers dindividus des deux sous-populations (correspondant chacun des deux tats A et B) linstant n. Des observations menes sur une assez longue priode permettent destimer que 95% des

unicellulaires se trouvant linstant n dans ltat A nont pas chang dtat linstant n + 1, non plusque 80% de ceux se trouvant linstant n dans ltat B ce qui se traduit par le systme suivant :

na nb

1

1

0,95 0,2

0,05 0,8n n n

n

b

bn n

a a

b a+

+

= += +

( )

Leffectif total slve 500 000 individus.

1 La population linstant 0 satisfait 0 375a = . Faire le calcul des effectifs et pourn 0. On a bien srX0 = 0 et pour tout entierkX

Notons :Aklvnement ltape k, la rpartition est r1 , autrement dit Xk= 0 ;

Bk lvnement ltape k, la rpartition est r2 , autrement dit Xk= 1 ;

Cklvnement ltape k, la rpartition est r3 , autrement dit Xk= 2 .On a alors : ( ) ( ) ( ) ( )1 1 1 1k k k k k k k p A p A A p A B p A C+ + + += + +

( ) ( ) ( ) ( ) ( ) ( )1 1k kk A k k B k k C k p A p A p B p A p C p A+ += + + 1k +

,kA k

p A p+ =

.

Or ( )1 11 ( )1 2kB kp A p+ = 1 et ( )1 3kC kp A p+ = 1 .

Do : ( ) ( ) ( ) ( )1 11 21 31k k k k p A p p A p p B p p C+ = + + .

On tablit des relations analogues pourp (Bk+1) etp (Ck+1). On obtient finalement le systme suivant :

( ) ( ) ( ) ( )

( ) ( ) ( ) (( ) ( ) ( ) (

1 11 21 31

1 12 22 32

1 13 23 33

k k k

k k k

k k k

))

k

k

k

p A p p A p p B p p C

p B p p A p p B p p C

p C p p A p p B p p C

+

+

+

= + +

= + + = + +

En notant Vk = (p(Ak) p(Bk) p(Ck)) pour tout entier k strictement positif, le systme de relationsprcdent correspond lgalit matricielle Vk+1 = VkP.

A ltape initiale, la rpartition est r1, donc V0 = (1 0 0).

A lissue de la premire tape, la rpartition est et V1 = V0P= (0 1 0).2r





14/63

On tablit par rcurrence que :

o pour tout entier naturel knon nul : 0 kkV V P=

o 2 21 1

02 20 1 0

1 10

2 2

kP P

= =

et que 2 1kP + P= pour tout entier .1k

On en dduit facilement que :

o pour tout entierkimpair, Vk = (0 1 0), ce qui correspond au fait qu tout instant impair,la rpartition est toujours r2

o pour tout entierkpair, non nul, , ce qui correspond au fait qu tout instantpair, la rpartition est soit r1 soit r3.

Le calcul de lesprance de kX conduit ( ) 1kE X = , pour tout entier naturel k, ce qui signifie quau

bout de ktapes, le nombre moyen de boules dans lurne B est gal 1. La rpartition des boules dansles deux urnes a tendance squilibrer.

b) Utilisation dun arbre

A la kime tape, on obtient les arbres suivants :

Si kest impair Si kest pair

On retrouve alors les rsultats du paragraphe prcdent.

Remarque :

Le recours au calcul matriciel nest vraiment utile que pour un grand nombre de particules mais le caso N= 2 permet dapprhender le problme en expliquant lutilisation des matrices et en comparantles rsultats obtenus avec ceux que lon obtient avec lutilisation dun arbre.





15/63

c) Calcul du temps de retour moyen dans le casN= 2

Considrons un processus de diffusion correspondant 2n tapes et notons Tn la variable alatoire quicompte le nombre dtapes pour revenir ltat initial.

Daprs ltude prcdente, on a :

( ) ( )1 0, 3 0n np T p T= = = = et, pour tout entier naturel k, ( )2 1 0np T k= + = ;

( ) ( )1

2 , 42 4n n

p T p T= = = =1

et, pour tout entier naturel knon nul, ( )1

22n k

p T k= = .

Calculons lesprance de Tn :

2

11 1

( ) ( ) 2 ( 2 )2

n n

n n n kk k

kE T k p T k k p T k

1

n

k

= =

= = = = = =

Calculons cette somme de deux faons diffrentes.

o Premire mthodeOn calcule successivement les sommes gomtriques :

1 1 11 2 1

1 1 1, , ...,

2 2 2

n n n

k k kk k k n

= = =

et 11

2

n

kk n

=

En ajoutant ces sommes, on obtient :

1

2( ) 4

2n nn

E T

+=

oDeuxime mthode

On considre la fonction dfinie surRpar1

( )2

kn

kk

xf x

=

= . On peut galement crire :

1

1 12( )1

2

n

n

x

f xx

+

+ =

1 si 2x et (2)f n= .

Pour , les deux expressions de2x ( )f x permettent dexprimer ( )f x de deux faons diffrentes.

On obtient alors deux expressions de (1)f , ce qui permet de calculer .( )nE T

On en dduit que ( )lim 4nn E T+ = . On revient donc en moyenne ltat initial au bout de 4 tapes.

Remarque :

Il est intressant de constater que siN= 2, le processus est rversible.

Cette tude est reprise et complte dans la partie III.





16/63

D. Reprsentation dun graphe. Notion de connexit

1. Parcourir un graphe

Chacun connat lhistoire du parcours impossible empruntant une et une seule fois les sept ponts de laville de Koenigsberg (aujourdhui Kaliningrad), ponts reliant les rives (B et D) du fleuve qui traverse laville, la Pregel, aux deux les (A et C) que celle-ci forme, et les deux les entre elles.

On dit que Lonard Euler (1707 1783) rsolut le problme et mit en vidence labsence de solution.Lhumanit lavait rsolu en pratique avant lui, mais le gnie dEuler fut de fabriquer des mathmatiquesavec cette question, cest--dire de donner des dfinitions donnant naissance des thormesrutilisables dans dautres situations.

Les ponts de Koenigsberg

Le problme des ponts de Koenigsberg consiste en fait savoir si un certaingraphe est eulrien (cest--dire si on peut en parcourir toutes les artes sans passer deux fois sur la mme).

Voici quelques dfinitions.

Un graphe (non orient) n sommets est une suite finie de points distincts (M1, M2, , Mn), appelssommets, et dartes, dontles extrmits sont des sommets.On considreraici quil nexiste pas de

boucle, c'est--dire darte ayant pour extrmits le mme sommet, et quil nexiste pas non plus depoint isol, c'est--dire reli aucun autre point.

Une chane de longueurp > 2reliant Mi Mj est une suite de sommets ( )1 2 1, ,..., ,p pS S S S + telle queS1 = Mi , Sp+1 = Mj , et que, pour tout entierkcompris entre 1etp, il existe une arte reliant Sk Sk+1.Dans le graphe associ au problme des Ponts de Koenigsberg, il nexiste pas de chane de longueur 1reliant B D.

Dans le graphe ci-dessous, (M5, M1, M2) est une chane de longueur 2 reliant M5 M2, (M5, M4, M6,M2) en est une de longueur 3, (M5, M6, M4, M2) une de longueur 4, etc.

Un graphe en forme d enveloppe

Il nexiste pas de chane de longueur 1 reliant M5 lui-mme, mais il en existe une de longueur 2 :(M5, M1, M5). Dailleurs, quand le graphe ne contient pas de point isol (ce qui est notre hypothse detravail), il existe toujours une chane reliant un point lui-mme.

Un graphe est dit connexe quand, deux points quelconques tant donns, il existe une chane qui les relie.





17/63

2. Matrice dadjacence dun graphe

Un graphe n sommets est caractris par les artes qui relient certains sommets entre eux. On peut doncreprsenter un graphe n sommets (M1, M2, , Mn) par un tableau n lignes et n colonnes dans lequel, lintersection de la ligne i et de la colonnej, on crit 0 si aucune arte ne relie Mi et Mj, et 1 si une arteles relie. Ainsi pour le graphe prcdent ( lenveloppe ), on obtient le tableau suivant :

M1 M2 M3 M4 M5 M6

M1 0 1 0 0 1 0

M2 1 0 1 0 1 1

M3 0 1 0 1 0 1

M4 0 0 1 0 1 1

M5 1 1 0 1 0 1

M6 0 1 1 1 1 0

En notant ai j le coefficient situ lintersection de la ligne i et de la colonnej, on dfinit un tableau 6lignes et 6colonnes (matrice de format (6, 6)), appele matrice dadjacence du graphe :

La matrice prcdente contient de nombreux zros, traduisant labsence dartes reliant certainssommets du graphe. Par exemple, la lecture de la matrice, on peut dire quil ny a pas darte reliantles sommets M2 et M4.

Afin dtudier la connexit dun graphe, on peut sintresser lexistence de chaines de longueur 2

entre deux sommets.Soient i et j deux entiers compris entre 1 et n (ici n = 6). Lexistence dune chaine de longueur 2 entreles sommets MietMj correspond lexistence dau moins un indice ktel que ai k 0 et ak j 0 cest--dire tel que ai kak j 0.

On observe alors que le nombre est la somme de six termes dont chacun est leproduit de deux nombres choisis parmi 0 et 1 ; chacun des termes non nuls de cette somme estassocie une chane de longueur 2 joignant Mi et Mj et une seule. Leur somme est donc le nombre dechanes de longueur 2 joignant Mi et Mj.

Les coefficients bi j dfinissent une nouvelle matrice B et les n2 relations prcdentes peuvent se

traduire par la relation matricielle suivante :





18/63

qui dfinit le produit de la matriceApar elle-mme.

Numriquement, la relation scrit ici :

On peut ainsi lire dans la matrice de droite quil y a 3 chanes de longueur 2 joignant le sommet M 3 ausommet M5.

On peut ensuite dfinir les puissances successives de la matrice dadjacence A et montrer parrcurrence que, pour tout entierp > 1, les coefficients de la matriceAp donnent les nombres de chanesde longueurp allant dun sommet du graphe un autre.

3. Lire la connexit dun graphe sur sa matrice dadjacence

Le calcul numrique prcdent a pour rsultat une matrice B dont aucun coefficient nest nul, ce quisignifie que chaque fois quon se donne deux sommets, il existe une chane de longueur 2 qui les relie.On peut donc conclure que le graphe de l enveloppe est connexe.

Cela pouvait, bien sr, se voir mais il faut imaginer des graphes possdant un grand nombre desommets o voir nest plus aussi vident.

Ce qui prcde montre surtout quun graphe peut tre donn par sa matrice.

En consultant les puissances successives de la matrice dadjacence, on peut savoir sil y a des chanesde longueur 2, 3, reliant tel sommet tel autre. Mais jusquo calculer pour tablir la connexitdun graphe dans un cas quelconque ?

Considrons un graphe n sommets (n > 2). Si une chane de longueur ne passe pas par tous lessommets du graphe, alors elle passe au moins deux fois par le mme sommet et on peut rduire la boucle quelle formait. Cet argument montre que pour tudier la connexit, il suffit de pousser larecherche jusqu la puissance n-ime. Do le rsultat suivant :

n

un graphe associ une matrice dadjacenceA de format (n, n) (on dit aussi matrice carre dordre n)est connexe si et seulement si, pour tout couple (i,j) dentiers compris entre 1 et n, il existe un entierpcompris entre 1 et n tel que le coefficient de la ligne i et de la colonnej de la matriceAp soit non nul.

E. Marches alatoires

Dans cette partie, on sintresse au comportement long terme dune marche alatoire. Il sagit decalculer les probabilits pour le hros dune marche alatoire dans un rseau de se trouver aprs n pasen tel ou tel sommet (ou nud) du rseau.

1. Marche alatoire sur un segment

Le personnage se dplace dun sommet lautre du graphe ci-dessous. Sil est en A ou en B, il ne peutaller quen P, sil est en P, il peut aller en A ou en B avec des probabilits que nous considronscomme identiques.

On peut reprsenter la situation par une matrice M (dite de transition) qui indique non les artesexistantes comme dans les matrices dadjacence, mais les probabilits de passage dun sommet unMinistre de lducation nationale, de la jeunesse et de la vie associative (DGESCO) Page 17 sur 62




19/63

autre. Lesmatrices de transition ne sont pas systmatiquement symtriques. La matrice Mci-dessousreprsente la marche dans le rseau (A, P, B).

A P B

0 0A

1 1

P 02 2B 0 1 0

1

Les coefficients figurant sur chaque ligne donnent les probabilits de passage du sommet qui donne sonnom la ligne celui qui donne son nom la colonne. La diagonale ne contient de ce fait que des 0.

Pour aller de A A en deux pas, le personnage peut aller de A A puis de A A (les probabilits sont0 et 0), ou de A P puis de P A (probabilits 1 et ), ou de A B puis de B A (probabilits 0 et 0).

La probabilit pour quil aille de A A en deux pas est donc :1 1

0 0 1 0 02 2

+ + = .

Pour aller de A B en deux pas, le personnage peut aller de A A puis de A B (probabilits 0 et 0),ou de A P puis de P B (probabilits 1 et ), ou de A B et de B B (probabilits 0 et 0). La

probabilit pour quil aille de A B en deux pas est donc :1 1

0 0 1 0 02 2

+ + = .

La premire probabilit sobtient en additionnant terme terme les produits des coefficients de la lignecorrespondant aux dplacements partant de A par ceux de la colonne correspondant aux dplacementsarrivant en A.

La seconde sobtient en faisant la somme des produits terme terme des coefficients de la ligne A par ceux de la colonne B .

En itrant le procd on obtient la probabilit de chacun des trajets de deux pas. Cela revient calculerle produit de la matrice prcdente (note M) par elle-mme, cest--dire la matrice M 2. Lescoefficients qui figurent dans cette matrice M2 sont les probabilits pour que le personnage situ ausommet qui donne son nom la colonne se soit trouv deux coups auparavant au sommet qui donneson nom la ligne.

On obtient :

On constate queM3 = M.

On peut interprter ce rsultat : par exemple, partant du sommet A, le personnage est srement en P

aprs un nombre impair de pas, en B ou en A avec des probabilits1

2aprs un nombre pair de pas.





20/63

2. Marche alatoire aux sommets dun ttradre

la diffrence de la situation prcdente, dans la marche aux sommets dun triangle comme dans lamarche aux sommets dun ttradre, on peut passer, chaque tape, de tout sommet donn tout autresommet donn.

Dans lhypothse dquiprobabilit, la matrice de transition (donnant les probabilits de passage dunsommet un autre) scrit :

1 1 10

3 3 3

1 103 3

1 1 10

3 3 3

1 1 10

3 3 3

M

=

1

3

On peut dmontrer par rcurrence que, pour tout entiern strictement positif, la puissance nime de lamatriceMscrit :

n n n n

n n n n

n n n n

n n n n

n

u v v v

v u v vM

v v u vv v v v

=

o les termes gnraux des suites ( et)nu ( )nv sont :1

1 11

4 3

n

nu =

et1 1

14 3

n

nv =

.

La lecture de ces matrices de transition est naturellement la mme quau paragraphe prcdent : lecoefficient gnrique celui situ sur la ligne iet la colonnej de la matrice n donne la probabilitquune chane de longueurnpermette de passer du sommet i au sommetj (on peut supposer que lessommets A, B, C, D sont numrots 1, 2, 3, 4).Il ny a pas dambigut dans ce cas, la matrice est

symtrique (les puissances dune matrice symtrique sont symtriques).Les diffrences entre les diffrentes probabilits sestompent rapidement : sil nest pas possible depasser dun sommet lui-mme en un pas, les probabilits daller dun sommet quelconque unsommet quelconque sont trs voisines ds que n est grand. En effet, la limite commune des deux suites

et( )nu ( )nv est1

4





21/63

3. Un retour en arrire est-il possible ?

Ayant quitt un sommet du ttradre, au bout de combien de pas alatoires le personnage peut-ilcompter y revenir ?

SoitXla variablealatoire donnant, pour chaque marche, ce nombre de pas.On a : ( ) ( ) ( )

1 21 0, 2 , 33 3P X P X P X= = = = = =

1

3 . En effet, pour que le personnage soit en A,

par exemple, aprs n pas sans y avoir t dans aucune de ses positions prcdentes, il est ncessairequ chacun de ses dplacements prcdents il soit pass dun sommet qui ntait pas A un autre quintait pas A non plus, choisissant donc lun de deux sommets sur trois possibles.

On peut vrifier par rcurrence que ( )2

2

3 3

n

P X n

1= =

, pour tout entiern suprieur ou gal 2

et observer que :

La variableXsuit donc une loi gomtrique.

Ressources : http://euler.ac-versailles.fr/wm3/pi2/marche/marche1.jsp

http://euler.ac-versailles.fr/wm3/pi2/marche/marche2.jsp



F. Pertinence dune page web

1. De la recherche dans une bibliothque la recherche dans un graphe

Un moteur de recherche doit fournir chaque utilisateur une liste de pages o apparaissent des mots-cls

donns dans la requte de celui-ci. On peut avoir lide de classer les milliards de pages disponibles dansun ordre permettant le tri partir des mots-cls fournis. Cela demande des moyens de stockageconsidrables et la rorganisation continuelle (en temps rel, comme on dit) de ces archives. Il faut deplus assurer aux milliers de requtes simultanes des rponses rapides, mais aussi des rponses fiables.

Un moteur de recherche copie dans un premier temps les pages web sur des milliers dordinateurs etles trie par ordre alphabtique des mots cls. La premire ide simple consisterait pour chaque requte fournir la liste de pages contenant le (ou les) mots cls de la requte. Mais il y en a des dizaines demilliers ! Aussi lordre alphabtique napparat pas le meilleur pour assurer un service rapide et dequalit. Les pages rfrences pour le client doivent donner une ide aussi juste que possible delinformation disponible au moment de la requte et faire apparatre en premires citations celles qui yrpondent le mieux, les pluspertinentes.

Le web nest pas une simple bibliothque de pages web. Les pages web comportent des liens quipermettent daccder directement de lune dautres. On peut donc considrer le web comme ungraphe orient, dont chaque page web est un sommet et chaque lien est un arc. Lide pour dterminerla pertinence dune page en lien avec un mot cl va tre de sappuyer sur lexistence de ces liens, enpartant de lide basique que plus une page est cite, plus elle estpertinente.

Dans la suite, les pages web sont numrotes 1, 2, , i, , n et un lien de la page i vers la pagej estnot i j.

Ainsi on cherche attribuer chacune des pages une mesure de pertinence (un nombre rel > 0).



http://euler.ac-versailles.fr/wm3/pi2/marche/marche1.jsphttp://euler.ac-versailles.fr/wm3/pi2/marche/marche2.jsphttp://euler.ac-versailles.fr/wm3/pi2/marche/marche3.jsphttp://euler.ac-versailles.fr/wm3/pi2/marche/marche4.jsphttp://euler.ac-versailles.fr/wm3/pi2/marche/marche4.jsphttp://euler.ac-versailles.fr/wm3/pi2/marche/marche3.jsphttp://euler.ac-versailles.fr/wm3/pi2/marche/marche2.jsphttp://euler.ac-versailles.fr/wm3/pi2/marche/marche1.jsp


22/63

2. Un exemple

Pour la suite, nous allons considrer un exemple excessivement simple avec seulement 12 pages webet les liens suivants :

Le graphe ci-dessus, qui ne comporte pourtant que 12 sommets, nest pas trs lisible. Les sommets lesplus frquents ny sont pas facilement identifiables.

Une nouvelle reprsentation de ce graphe, plus buissonnante dfaut dtre arborescente, metmieux en vidence limportance des sommets 1, 6 et 10, vers lesquels pointent un nombre levdautres sommets.

3. Mesurer la pertinence

Dans ce qui suit, on note j la mesure de pertinence de la page j, pour tout entierj compris entre 1 et n,nombre de pages web disponibles linstant considr, en rapport avec la requte considre.

o Comptage naturel des liensA chaque pagej, on associe le nombre de liens ijqui pointent vers elle.

Dans notre exemple, les pages 6 et 10 reoivent chacune 3 liens, tandis que la page 1 en reoit 5. Onobtient donc : 6= 3, 10= 3 et 1= 5.

Mais ce comptage nest pas suffisamment discriminant et il est de plus trs facile manipuler,puisquil suffit de crer des fausses pages pointant vers la page ipour en augmenter limportance.





23/63

o Comptage pondrOn peut tenter de pondrer les liens : certaines pages mettent beaucoup de liens ce qui dune certainefaon diminue leur poids.

Notons, pour chaque entieri, i le nombre de liens mis par la page i.

On peut alors dfinir la mesure de pertinence de la page jen comptant le nombre de liens pondrs quipointent vers elle :

Dans notre exemple, 6= 1,45, 10= 1,5 et 1= 2,5.

Mais cette mesure prsente toujours le mme risque dtre manipule.

o Comptage rcursifLa pertinence dune page est renforce par la pertinence des pages qui pointent vers elle et elle est

diminue par la dispersion ventuelle des liens issus de ces dernires.

En reprenant la pondration prcdente, on peut dfinir la pertinence dune page jde la faon suivante :

Le risque de manipulation consistant en lajout de pages vides de sens est ici annul puisquune tellepage recevrait une mesure de pertinence nulle.

Avec le graphe prsent dans le paragraphe prcdent, on obtient par exemple :

7 613= , 12 11 1012

= + , etc.

On obtient ainsi un systme dquations linaires.

On rcrit les formules (*) pour tout entier icompris entre 1 et n avec des coefficients nots ai j, lecoefficient ai j

valant si la pageipointe vers la page j, 0 sinon. On obtient ainsi le systme linaire

de n quations n inconnues (les i). :

Les coefficients ai j dfinissent une matrice n lignes et n colonnes (de format (n, n)), que lon peutnoterA.

Le systme linaire de n quations prcdent correspond lquation matricielle suivante :

W= WA,

o West une matrice ligne n colonnes(format(1, n), dont les coefficients sont les j :

W= ( 1 2 n)

Il ny a plus qu rsoudre ce systme, sauf que dans le cas du web il y a des milliards

dinconnues. Dans notre exemple, on obtient une matrice de format (12,12).





24/63

4. Pertinence et probabilits

Dans le systme dquations prcdent, on peut remarquer la propritsuivante des coefficients ai j :

En fait, pour un indice ifix (c'est--dire dans la ligne ide la matrice) tous les coefficients non nulssont gaux linverse du nombre de liens mis par la page i,ce nombre correspondant galement dece fait linverse du nombre de coefficients non nuls de la ligne i.

Les coefficients ai j (tous positifs ou nuls) peuvent donc sinterprter comme la probabilit, pour un surfeur qui se trouverait la page ide suivre le lien qui lamnerait la page j. Cette probabilitest dfinie de la manire suivante : si i liens sont issus de la page i, la probabilit pour que le surfeuralatoire du web passe de la page i une des pages vers lesquelles elle pointe est , la probabilitpour quil se dirige vers une autre est 0.

Notons Xp la variable alatoire indiquant la position (numro de page) du surfeur alatoire aprs pclics. On a :

En notant Up la matrice ligne n colonnes admettantP(Xp = i) pour coefficient la colonne ipour toutentier i compris entre 1 et n, les relations prcdentes peuvent se traduire par la relation matriciellesuivante :

Up+1 = UpA

On en dduit par rcurrence que, pour tout entierp strictement positif, Up = U0Ap, avec U0 donnant la

position du surfeur alatoire au dpart (U0 est donc une matrice ligne n lments tous nuls sauf unqui vaut 1 et dont lindice correspond au numro de la page de dpart).

Toutefois, il peut arriver que certaines pages ne comportent aucun lien vers dautres pages ; dans cecas, lorsque le surfeur alatoire arrive sur lune dentre elles, il lui est impossible de la quitter. La lignede la matrice correspondant cette page ne comporte alors que des 0. Afin de remdier ce dfaut etsans doute coller mieux la ralit, on introduit la possibilit de quitter tout instant une pagequelconque pour se diriger vers une autre choisie au hasard, et ce avec une probabilit gale c.

Dans ces conditions, le modle correspond au systme de relations suivant pour tout entierp

strictement positif et tout entiericompris entre 1 et n (puisque ) :

qui se traduit par la relation matricielle suivante (pour tout entierp> 0) :

o J dsigne la matrice carre de format (n, n) dont tous les coefficients sont gaux 1.

Notons .

On a alors, pour tout entierp strictement positif, Up = U0B p.





25/63

Il resterait prouver que la suite de matrice (Bp) converge (dans un sens prciser) lorsque lentierptend vers linfini et expliquer comment rcuprer les mesures de pertinence 1, 2,,n.

Il nest pas question de traiter ici le cas gnral. Nous allons nous contenter dobserver ce qui se passesur un exemple lmentaire.

Dans lexemple ci-dessous, le graphe reprsente les liens existant entre quatre pages web numrotes

de 1 4 (M1, M2, M3, M4) :

La matriceA associe ce graphe, telle que dfinie dans le paragraphe prcdent, est :

On observe ici que la matrice nest pas symtrique contrairement la matrice dadjacence dfinie dansla partie d. Cela tient au fait quici le graphe est orient.

On peut montrer que les puissances de la matriceA ont pour limite la matriceL ci-dessous. On a alors,

quelle que soit la situation initiale U0,

En consquence, on attribue aux pages 1, 2, 3, 4 les indices de pertinence respectifs3 1 4

, ,13 13 13

et5

13

3 1 4 5

13 13 13 133 1 4 5

13 13 13 133 1 4 5

13 13 13 133 1 4 5

13 13 13 13

L

=





26/63

Dans le deuxime modle, avec c = 1 / 5, on obtient la matrice :

On dmontre que les puissances de la matrice Bconduisent une matrice limite et des indices de

pertinence qui sont135 323 171

, ,572 2860 572

et1007

2860, comparer aux indices trouvs prcdemment.

Page 1 2 3 4

Sans saut alatoire 0,23 0,08 0,31 0,38

Avec saut alatoire 0,24 0,11 0,3 0,35

Ressource : http://euler.ac-versailles.fr/wm3/pi2/pertinence/pertinence.jsp

G. Traitement de limage

1. Numriser des images imager les nombres

On a extrait limage ci-contre dune photographie dAlan Turing disputantune course de 3 miles en 1946. Cette photographie a t reproduite sur unsite web consacr lun des inventeurs de linformatique dont ladresseest donne ci-dessous. Elle a donc t numrise , cest--dire

transforme en une suite de 0 et de 1. Le rectangle est dcompos en uncertain nombre de petits carrs, et chacun de ces carrs a t attribu unnombre qui reprsente une nuance de gris. La finesse de la dcomposition(le nombre de carrs) est la dfinition de limage. La dfinition de cetteimage particulire nest pas bonne : on devine les pixels (mot fabriqu avecles dbuts des mots anglaispicture element).

Toute image nutilisant que le noir et le blanc peut ainsi tre reprsente par un tableau contenantautant de cases que limage contient de pixels, chacune de ces cases tant occupe par 0 ou 1. Limageest donc reprsente par une matrice dont tous les lments sont 0 ou 1.

Ladresse du site consacr Turing est : http://www.turing.org.uk/turing/scrapbook/run.html

2. Oprations sur les images1 0 0 1 1 0

1 1 0 0 0 1

1 0 0 0 1 0

1 0 0 0 0 0

0 1 1 0 1 0

A

=

0 1 1 0 0 1

0 0 1 1 1 0

0 1 1 1 0 1

0 1 1 1 1 1

1 0 0 1 0 1

B

=

On transforme la matrice A associe limage de gauche en remplaant 1 par 0 et 0 par 1, on obtientla matrice B, associe limage de droite, qui est le ngatif de limage de gauche.



http://euler.ac-versailles.fr/wm3/pi2/pertinence/pertinence.jsphttp://www.turing.org.uk/turing/scrapbook/run.htmlhttp://www.turing.org.uk/turing/scrapbook/run.htmlhttp://euler.ac-versailles.fr/wm3/pi2/pertinence/pertinence.jsp


27/63

On peut galement coder des images en nuances de gris en attribuant chaque pixel un nombrecompris entre 0 et 1, proche de 1 si la case est gris fonc, proche de 0 si elle est gris clair. On peutgalement dfinir limage ngatif de limage de dpart en lui associant la matrice dont les lmentssont les complments 1 des lments de la matrice de dpart.

Les deux images ci-dessus sont le ngatif lune de lautre. Dautres critres peuvent tre enregistrsdans les lments de la matrice associe une image, la luminosit par exemple. Une multiplication detous les lments de la matrice reprsentant la luminosit par un mme facteur modifie la luminositde lensemble.

Si deux images ont le mme format et la mme dfinition (associes aux matrices A et B), il estpossible de leur faire correspondre leursomme, associe la somme des matrices qui les dfinissent,

en convenant quun coefficient suprieur 1 donne un pixel de couleur noire. On peut aussi leur fairecorrespondre leurdiffrence, avec cette fois la convention que tout pixel associ un nombre ngatifest blanc, ou restituer l'image positive |A B| en particulier pour diffrentier les images et faireapparatre la trame des contours, horizontaux, verticaux, obliques.

Ressources : http://euler.ac-versailles.fr/wm3/pi2/image/image1.jsp,

http://euler.ac-versailles.fr/wm3/pi2/image/image2.jsp,



Le logiciel Scilab peut galement permettre des oprations sur les images, en lien avec les matrices.Lannexe 1 fournit quelques complments ce propos.

3. Comment modifier la forme dune image ?

On se propose de transformer limage de droite en sa symtrique par rapport laxe vertical, limagede gauche. Pour cela, il suffit de reprsenter le symtrique de tout pixel de limage de droite. Chaquepixel tant dune seule couleur, limage obtenue est bien la symtrique de limage de dpart.

Des photos de la spirale de Fibonacci dans le mtro de Naples se trouvent ladresse suivante :www.danpiz.net/napoli/trasporti/StazioneVanvitelli.htm, page dun site touristique sur Naples.



http://euler.ac-versailles.fr/wm3/pi2/image/image1.jsphttp://euler.ac-versailles.fr/wm3/pi2/image/image2.jsphttp://euler.ac-versailles.fr/wm3/pi2/image/image4.jsphttp://euler.ac-versailles.fr/wm3/pi2/image/image6.jsphttp://www.danpiz.net/napoli/trasporti/StazioneVanvitelli.htmhttp://www.danpiz.net/napoli/trasporti/StazioneVanvitelli.htmhttp://euler.ac-versailles.fr/wm3/pi2/image/image6.jsphttp://euler.ac-versailles.fr/wm3/pi2/image/image4.jsphttp://euler.ac-versailles.fr/wm3/pi2/image/image2.jsphttp://euler.ac-versailles.fr/wm3/pi2/image/image1.jsp


28/63

4. Des matrices pour raliser des transformations

tout point du plan, de coordonnes ( ),y donnes dans un repre (que nous choisirons orthonormalpour que laction sur les figures soit mieux visible), on peut associer un autre point, de coordonnes

( , )x y dfinies par laction dune matrice carre sura b

c d

x

, ce qui scrit :

x a b x

c d y

=

, ou encorex ax by

y cx dy

= + = +

.

Si, par exemple, , , et1a = 0b = 1c = 0d= , les coordonnesx et y dun point quelconque sonttransformes en x ety, qui sont les coordonnes de son symtrique par rapport laxe vertical.

Les images suivantes fournissent sur une vue de la Bivre aux Gobelins extraite dune carte postaledpoque, des exemples dactions dune matrice sur une image.

Exercice : Trouver les coefficients correspondants.

Rflexion daxe (Oy) Symtrie centrale

Rduction (multiplication des dimensions par 0,5) Affinit orthogonale de base laxe (Oy) de rapport 0,5





29/63

II.Dfinitions et premiers calculs avec des matrices

Dans cette partie, le vocabulaire spcifique aux matrices, les oprations sur les matrices et quelquesrsultats thoriques sont prsents aprs une introduction intuitive des notions dans le cadre de larsolution de problmes comme dans les exemples proposs dans la premire partie. Dans la partie III,dautres problmes seront rsolus et on sautorisera alors lutilisation des matrices et la rfrence directe

aux rsultats thoriques noncs dans la partie II.

A. Matrices. Oprations

1. Quelques dfinitions, quelques notations

Deux entiers naturels m et n tant donns non nuls, on appelle matrice de format (m, n) tout tableaurectangulaire de m lments, disposs surm lignes et n colonnes. Dans les situations abordes ici,les lments en question sont des nombres rels.

n

La matrice peut aussi tre note

11 12 1

1,1 1,2 1,

1 2

...

... ... ... ...

...

...

n

m m m

m m mn

a a a

A

a a aa a a

=

n

( )i jA a= , la notation dsigne

le coefficient (llment, le terme) situ lintersection de la i-ime ligne et de la j-ime colonne.Cest le coefficient gnrique de la matriceA.

i ja

Lorsque , on dit que la matrice est carre (carre dordre n si ncessaire). Les lmentssont les lments de la diagonale principale de la matrice.

m n=

11 22 33 1, 1, , ,..., ,n n nna a a a a

La matrice identit dordren est la matrice carre dordre n dont tous les coefficients sont nuls lexception de ceux situs sur la diagonale principale qui sont gaux 1. Elle est souvent noteIn.

Lgalit ne peut intervenir quentre deux matrices Aet Bde mme format : elle signifie que, pourtout indice i et pour tout indicej, . Une matrice dont tous les coefficients sont nuls est dite

matrice nulle (mais deux matrices nulles qui nont pas le mme format ne sont pas gales).i j i ja b=

Ressources : http://euler.ac-versailles.fr/wm3/pi2/matrice/coefficient1.jsp

http://euler.ac-versailles.fr/baseeuler/recherche_fiche.jsp?theme=4

2. Addition, produit par un scalaire

On peut faire la somme de deux tableaux de nombres ayant mme nombre de lignes et de colonnes enprocdant par addition place par place. Cest ce procd qui est retenu pour dfinir laddition dematrices de mme format. Dire que les matricesA,Bet C, de format ( ),m n , sont telles que

, cest dire que :pour tout entiericompris entre 1 et m,pour tout entierj compris entre 1 et n, .C A B= +

i j i j i jc a b= +

On peut de mme multiplier tous les lments dun tableau de nombres par un mme nombre (pourappliquer une taxe, par exemple). Cest ce procd qui est utilis pour multiplier une matriceA par un

scalaire(un nombre rel). On note A la matrice obtenue. On a donc (avec une simplification de lanotation) : A = (ai j).

Ressources : http://euler.ac-versailles.fr/wm3/pi2/matrice/somme1.jsp

http://euler.ac-versailles.fr/wm3/pi2/matrice/produit4.jsp

http://euler.ac-versailles.fr/wm3/pi2/matrice/pdf/somme1.jsp http://euler.ac-versailles.fr/wm3/pi2/matrice/somme2.jsp



http://euler.ac-versailles.fr/wm3/pi2/matrice/coefficient1.jsphttp://euler.ac-versailles.fr/baseeuler/recherche_fiche.jsp?theme=4http://euler.ac-versailles.fr/wm3/pi2/matrice/somme1.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/produit4.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/pdf/somme1.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/somme2.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/somme2.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/pdf/somme1.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/produit4.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/somme1.jsphttp://euler.ac-versailles.fr/baseeuler/recherche_fiche.jsp?theme=4http://euler.ac-versailles.fr/wm3/pi2/matrice/coefficient1.jsp


30/63

3. Produits de matrices

Dans la partie I, nous avons rencontr :

o des produits de matrices de format (m, n) par des matrices colonnes de format (n, 1) tel :

,

2

30 1 5 2 3 4 1

29,2 1,1 4,7 1,8 3,1 3,8 330,2 0,9 5,1 1,9 3,2 4 3

2

=

o des produits de matrices lignes de format (1, m) par des matrices de format (m, n) tel :

( ) ( )

0,6 0, 2 0 0, 2

0,1 0 0,8 0,110,7 2, 4 6 3,9 12 5 6 3

0,5 0 0,33 0,17

0 0 0 0

=

o et des produits de matrices carres par elles-mmes, illustr par le schma suivant :0 1 0

1 10

2 20 1 0

0 1 0

1 10

2 20 1 0

=1 1

02 20 1 0

1 10

2 2

Plus gnralement, soitA une matrice de format (m, n)etBune matrice de format (n,p). Le produitdeAparB est la matrice Cde format (m,p), noteAB, dont, pour tout icompris entre 1 et met pourtoutj compris entre 1 etp, llment est la somme des produits terme terme des lments de la

i-ime ligne deApar les lments de laj-ime colonne deB : .

i jc

1

n

i j i k k jk

c a b=

=

Par exemple le produit dune matrice de format ( )2, 3 parune matrice de format ( )3, 4 donne une

matrice de format ( )2, 4 :

4 1 0 1

1 0 2 1

1 3 0 0

1 2 0

0 1 3

= 6 1 4 12 9 2 1

Lutilisation du logiciel Scilab, qui dit si oui ou non la multiplication est possible, peut treextrmement intressante.





31/63

Il peut galement tre riche denseignements de diffrencier les produits de Hadamard (produit termes termes de deux matrices) et produit de Cayley prcdemment dfini, ce que permet aussi le logicielScilab

Ressources : http://euler.ac-versailles.fr/wm3/pi2/matrice/produit3.jsp


http://euler.ac-versailles.fr/wm3/pi2/matrice/pdf/produit3.jsp

http://euler.ac-versailles.fr/wm3/pi2/matrice/pdf/produit2.jsp


4. Proprits du produit des matrices carres dordre n

Nous nous intressons prsent au produit des matrices carres dordre n. Ce produit nest pascommutatif, ce qui signifie que, dans le cas n = 2 par exemple, il existe des couples de matrices (A,B)

tels que AB BA . Voici un exemple : .et1 2 2 0 8 2 2 0 1 2 2 4

3 4 3 1 18 4 3 1 3 4 6 10

= =

Certaines matrices ne sont pas inversibles pour ce produit. On a, par exemple :

et1 2 2 1 10 5 3 1 2 1 10 5

3 4 4 2 22 11 9 1 4 2 22 11

= =

.

On observe sur cet exemple que le produit de deux matrices distinctes par une mme matrice donnedeux matrices identiques.

En revanche les proprits dassociativit (effectuerBCpuis multiplier gauche parA revient aumme queffectuerABpuis multiplier droite parC) et de distributivit par rapport laddition (leproduit deApar la somme deBet Cest la somme des produits deA parBet de A parC) font delensemble des matrices carres dordre 2 un cadre assez confortable pour les calculs.

Enfin on peut vrifier que, pour toute matriceA carre dordre n,AIn =InA =A.

B. Les matrices sont-elles inversibles ?

Nous avons vu que le produit des matrices carres dordre 2 nest pas commutatif. Le problme de larecherche dun inverse pour une matrice donneMsexprime donc de la manire suivante : existe-t-ilune matriceNtelle que :NM=MN = I2?

Nous avons vu que les matrices ne sont pas toujours inversibles: en effet, il existe des matricesA,B etC telle que A B A C = , bien que B soit distincte de C. Ce rsultat met en vidence la noninversibilit de la matriceA (sinon on pourrait multiplier par linverse deA et obtenirB = C). En vertu

de la distributivit voque plus haut, il vient ( ) 2A B C O = (O2 matrice nulle dordre 2) ; il y adonc des diviseurs de O dans lensemble des matrices carres dordre 2.

Condition pour quune matrice carre dordre 2 soit inversible

On se donne une matrice et on cherche sil existe une matrice11 12

21 22

a aA

a a

=

x yB

z t

=

telle que

A B =B A = I2.

La premire galit scrit : ou encore .11 12

21 22

1 0

0 1

a a x y

a a z t

=

11 12 11 12

21 22 21 22

1 0

0 1

a x a z a y a t

a x a z a y a t

+ + = + +



http://euler.ac-versailles.fr/wm3/pi2/matrice/produit3.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/produit2.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/pdf/produit3.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/pdf/produit2.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/produit5.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/produit5.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/pdf/produit2.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/pdf/produit3.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/produit2.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/produit3.jsp


32/63

On obtient deux systmes dquations du premier degr deux inconnues :

11 12

21 22

1

0

a x a z

a x a z

+ =

+ = et

11 12

21 22

1

0

a y a t

a y a t

+ =

+ =.

Les seconds membres des quations de chacun de ces deux systmes nous indiquent que la condition

ncessaire pour quils admettent des solutions (et en loccurrence, ce sera un couple de solutionsunique) scrit : a11a22 a12a21 0 (D)

La quantit est appele dterminantde la matrice A. On vrifie que si le dterminant est

non nul et si on pose = , les produits AB et BA sont tous les

deux gaux I2. La condition (D) est donc une condition ncessaire et suffisante dinversibilit.

11 22 12 21a a a a

La matrice B est appele matrice inverse de la matrice A et on la noteA1.

C. Puissances de matrices carres dordre 2 ou 3

Les problmes rencontrs dans la premire partie nous ont amens calculer des puissances dematrices. On peut faire les calculs avec une calculatrice pour des matrices de petite taille et despuissances raisonnables, on peut faire les calculs laide dun logiciel pour des puissances explicites, laide dun logiciel de calcul formel pour obtenir, dans les bons cas, des formules closes , donnantlexpression des coefficients en fonction de lexposant, mais il est plus difficile dobtenir, dans le casgnral, ce que nous avons appel des limites.

1. Quelques matrices particulires

a) Les matrices triangulaires

Les matrices triangulaires ont des puissances triangulaires.

Considrons par exemple la matrice .

Une telle matrice est dite triangulaire suprieure, car ses coefficients situs sous la diagonaleprincipale sont nuls.

On obtient : T b . On pourrait poursuivre par une dmonstration par

rcurrence pour prouver que, pour tout entierp strictement positif, Tp est une matrice triangulairesuprieure.

Les matricesstrictement triangulaires comme U ont leurs puissances nulles compter

de la troisime au plus. En effet : U et U

0

0 0

a d f

T b

c

=

e

be ec

c

+ + +

= +

e

=

=

O

2

2 2

2

0

0 0

a ad bd af de cf

0

0 0

0 0 0

d f

2

0 0

0 0 0

0 0 0

ed3

3= . Les matrices dont les puissances





33/63

sont nulles partir de lune dentre elles sont dites nilpotentes.Une application des matrices triangulaires est prsente au II. F.

b) Les matrices diagonales

Les matrices diagonales (dont tous les coefficients non situs sur la diagonale principale sont nuls) ontdes puissances diagonales dont les coefficients sont les puissances des coefficients initiaux.

c) Les matrices creuses

Dune faon gnrale, les matrices creuses , celles dont beaucoup de coefficients sont nuls, sontrecherches, car cette particularit permet de gagner du temps de calcul machine. Ce gain de temps estaussi d la possibilit de raliser des produits de matrices par blocs .

Considrons les matrices

2 7 8 4

11 0 5 0

0 4 3 9

1 7 2 8

A

=

et

1 7 8 3

0 2 5 0

0 4 2 11

1 5 7 2

B

=

. Les lignes

horizontales ou verticales traces font apparatre des matrices :

11 12

21 22

A AA

A A

=

et

11 12

21 22

B BB

B B

=

.

Par exemple, , . Les produits envisags ayant tous un sens (il y a

compatibilit entre les tailles des matrices multiplier chaque tape), on souhaite crire que :

11

2 7

11 0A

=

22

2 11

7 2B

=

11 12 11 12 11 11 12 21 11 12 12 22

21 22 21 22 21 11 22 21 21 12 22 22

A A B B A B A B A B A BAB

A A B B A B A B A B A B

+ + = = + +

Et, constatant que les sommes de produits de matrices sont elles aussi ralisables :

2 52 31 86

11 57 78 22

9 41 49 51

9 27 95 3

AB

=

2 32 4 20 19 6 12 80

11 57 0 0 88 33 10 55

0 8 9 33 20 0 69 51

1 21 8 48 43 3 55 6

AB

+ + = + +

Beaucoup de systmes de calcul numrique travaillent, en interne, sur des listes ordonnes ou sur destableaux. Si ces tableaux contiennent beaucoup de 0, les calculs seront plus faciles et sans doute plus

justes, mais pas forcment moins longs si on na pas pris en compte labondance de ces 0.

Dans les situations de problmes compartiments , par exemple, il est frquent qu partir dun taton ne puisse passer qu un tat voisin, ce qui se traduit par une matrice de transition contenantbeaucoup de 0.

Mais il y a naturellement des situations, trs nombreuses, dans lesquelles les premires puissancesdune matrice ne laissent pas conjecturer la forme de sa puissance n-ime. On peut alors avoir recours la diagonalisation, voque dans le paragraphe qui suit.

Ressources : http://euler.ac-versailles.fr/wm3/pi2/matrice/puissance2.jsp



http://euler.ac-versailles.fr/wm3/pi2/matrice/puissance2.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/puissance2.jsp


34/63

2. Diagonalisation ventuelle dune matrice carre dordre 2

Les matrices considres dans ce paragraphe sont toutes coefficients rels.

Nous adoptons la dfinition suivante :

on dit quune matrice carre A est diagonalisable sil existe une matrice carreP inversible et des

rels et tels que .

Compte-tenu de ce qui a t dit sur les matrices diagonales, on voit que, si la matriceA peut scrire :

A =PD P1,

o D est diagonale, alors, pour tout entier naturel non nul n :

An =PDnP1,

ce qui facilite considrablement les calculs.

Cherchons une condition ncessaire et suffisante pour que la matrice A soit diagonalisable.

Notons une matrice inversible ralisant lgalitA =PD P1.

LgalitA =PD P1 est quivalente lgalitA P=PD qui donne :

Considrons les matrices colonnes et .

On observe que lgalitA P=PD est quivalente au systme suivant : .

Par ailleurs, on a vu prcdemment que la matrice Pest inversible si et seulement si ad bc 0 ce quiquivaut dire que les vecteurs (a, c) et (b, d) ne sont pas colinaires, cest--dire que les matricescolonnes Vet W ne sont pas proportionnelles.

Remarque :

On observe que si les matrices colonnes Vet W ne sont pas proportionnelles, alors ncessairementelles sont toutes deux non nulles.

En conclusion, on peut noncer la condition ncessaire et suffisante suivante :

Une matrice carreA dordre 2 ( coefficients rels) est diagonalisable si et seulement sil existedeux rels et (non ncessairement distincts) et deux matrices colonnes coefficients rels nonproportionnelles Vet W

telles queAV= V

etAW= W.

Les rels et (sils existent) sappellent les valeurs propres de la matriceA.

Remarque :

Les matrices carres dordre 2 ne sont pas toutes diagonalisables.

En effet, si on crit la matriceA sous la forme : , dire que le produit de la matriceA

par la matrice colonne Vnon nulle est proportionnel V, cest dire quil existe un rel et un couplede rels non tous les deux nuls (v1, v2) tels que .

11 12

21 22

a aA

a a

=





35/63

Cette dernire condition traduit aussi lexistence de rels , 1 et 2 tels que :

.

Si le dterminant du systme dquations linaires en 1 et 2crit ci-dessus nest pas nul, alors il naque le couple nul comme solution, ce qui ne satisfait pas lhypothse.

Lhypothse exige donc que ce dterminant soit nul, cest--dire que :

Lexistence des matrices colonnes Vet Wexige donc que lquation du second degr en ci-dessusadmette des solutions relles, ce qui nest pas toujours le cas, cest pourquoi on peut dire que lesmatrices carres dordre 2 coefficients rels ne sont pas toutes diagonalisables.

Considrons par exemple la matrice . Pour elle, lquation en scrit 2 + 1 = 0, qui

nadmet pas de solutions relles. Donc la matriceJnest pas diagonalisable.

On pourrait galement vrifier que la matrice pour laquelle lquation en scrit2= 0 nest pas non plus diagonalisable, mettant ainsi en vidence le fait que lexistence de solutionsde cette quation en est une condition ncessaire non suffisante de diagonalisabilit.

D. Traitement matriciel des suites de Fibonacci

On sintresse dans ce paragraphe la suite de Fibonacci, dfinie par :

0 1,u = et, pour tout entier : u u1 1,u = n 2 1n n nu+ += + .

1. Recherche dune formule close pour le terme gnral

Spirale de Fibonacci dans le mtro de NaplesOn peut crire, avec des notations prsent mieux matrises :

2 1

1

1 1

1 0n n

n n

u u

u u+ +

+

=

.





36/63

La matrice peut tre crite comme le produit1 1

1 0F

=

1PDP , o :

Un raisonnement par rcurrence donne, pour tout n : ,1 1

0

1 1

1 0n

n

nu u

u u+ =

ou encore :

1 1

0

1 5 1 5 105 1 1 5 2 5 2 52 2

1 5 11 51 1 05 2 52

n

n

n

n

u u

u u+

+ + = +

Tous calculs faits, pour tout n suprieur ou gal 2 :

1 1

1 1 5 1 1 5

2 25 5

n n

nu

+ + +

=

.

Certains pourraient trouver ce rsultat tonnant, remarquant que, du fait de la dfinition, tous lestermes de la suite sont entiers. Pour se convaincre que la formule ci-dessus donne bien des entiers, ilsuffit de comparer les termes dordre pair et les termes dordre impair des puissances dvelopper.

2. Trouve-t-on toujours une combinaison linaire de suites gomtriques ?

Nous avons crit le terme gnral de la suite de Fibonacci de premiers termes 1 et 1 comme unecombinaison linaire des termes de deux suites gomtriques.

Les calculs prcdents sont adaptables toute suite u dont les deux premiers termes sont donns, ettelle quil existe deux rels a et b pour lesquels pour tout n > 0, 2 1n nu au b+ + nu= + , pourvu que la

matrice associe soit diagonalisable.1 0

a bM

=

E. Retour sur les marches alatoires

Dans ce paragraphe, nous nous intressons de nouveau des marches alatoires, dans le but demontrer quon peut, dans certains cas, dcouvrir des formules de rcurrence pour dterminer lespuissances n-imes de matrices de forme particulire.

Marche alatoire sur un cube





37/63

Dans la marche alatoire aux sommets dun cube, le personnage peut passer chaque tape dunsommet un des trois sommets voisins. Nous supposons quil y a quiprobabilit dans les passagesdun sommet un autre. On associe cette situation la matrice de transition suivante dans laquelle lecoefficient situ lintersection de la i-ime ligne et de la j-ime colonne est la probabilit quunmouvement partant du sommet i sachve au sommet j.

Cette matrice est :

0 1 0 1 1 0 0 0

1 0 1 0 0 1 0 0

0 1 0 1 0 0 1 0

1 0 1 0 0 0 0 11

1 0 0 0 0 1 0 13

0 1 0 0 1 0 1 0

0 0 1 0 0 1 0 1

0 0 0 1 1 0 1 0

M

=

Les particularits de cette matrice (elle est symtrique, cest--dire symtrique par rapport la

diagonale principale, elle est dcomposable en quatre blocs dont deux sont la matrice identit dordre4) permettent de trouver intuitivement la forme de sa puissance n-ime.

On peut prouver par rcurrence lexistence de quatre suites (un), (vn), (wn), (xn), dont les termes sont lescoefficients de la matriceMn de la forme suivante :

, oA,B, CetD sont les quatre matrices carres dordre 2 dfinies par :

Aprs calculs, on obtient :





38/63

III. Loutil matrices luvre Complments et exemples

Dans cette partie, nous serons amens utiliser des proprits des matrices, ou des reprsentationsmatricielles de situations sans revenir sur ce qui a t dvelopp dans la partie II. Tous les rsultats nesont pas tablis, et ce point nest pas ncessairement prcis chaque fois. Certaines des applicationsproposes devraient motiver les lves et, esprons-le, susciter des vocations : aider les lves

affirmer leur choix dtudes suprieures scientifiques longues est le but de lenseignement despcialit mathmatiques.

A. Matrices en arithmtique

1. Cryptographie : le chiffrement de Hill

a) Introduction et principe

Dans les plus anciens systmes de cryptographie, chaque lettre est remplace par une autre lettre,toujours la mme. Les premires amliorations consistrent remplacer une lettre donne par uneautre, choisie en fonction de la place de la lettre coder dans le texte de dpart (en utilisant un mot-clef, par exemple). Le systme de Hill (Lester S. Hill, Concerning certain linear transformation

apparatus of cryptography, in American mathematical monthly, vol 38, (1931), p135 154)transforme des chanes de caractres de longueur donne, chaque lettre tant alors transforme enfonction de sa valeur et de sa place dans la chane de caractres.

On se donne un entier naturel n suprieur ou gal 2. Le texte chiffrer est dcoup en blocssuccessifs de n lettres. Sil y a un reste, on peut complter arbitrairement le texte ou lamputer du blocincomplet. Les lettres de chaque bloc sont remplaces par des nombres (gnralement A = 0, B = 1,C = 2, , Z = 25), et chaque bloc de lettres est associe une matrice colonne Bi n lignes. On sedonne une matrice carre Mdordre n, appele matrice de chiffrement, connue de lexpditeur et du

destinataire du message, coefficients entiers naturels. Le produit iC MBi= est une matrice colonnequi peut son tour tre transforme en une suite de n lettres, chacun de ses lments tant ramen

son reste modulo 26 puis transform en la lettre correspondante de lalphabet. Pour dcoder, il faudrafaire le chemin inverse (si toutefois la suite des deux oprations produit de la colonne par la matricesuivie de dtermination du reste modulo 26 est inversible ).

b) Exemple

Utilisons la matrice . Soit chiffrer le texte CODAGE DE HILL. Le dcoupage en blocs

de deux lettres et leur transformation en matrices colonnes donne : .

2 5

3 4M

=

2 3 6 3 7 11

14 0 4 4 8 11

Les matrices colonnes obtenues par laction deMsur les matrices colonnes prcdentes sont :74 6 32 26 54 77

62 9 34 25 53 77

, qui, modulo 26, donnent : .22 6 6 0 2 25

10 9 8 25 1 25

Le texte crypt est donc WK GJ GI AZ CB ZZ. Nous verrons par la suite comment le dcrypter.

Utilisons la matrice . Soit chiffrer le texte AMER. Les mmes procds donnent les

matrices colonnes , transformes en , ou encore en , le texte

4 2

3 8N

=

0 4

12 17

24 50

96 148

24 24

18 18





39/63

crypt est donc YS YS, ce qui pose un problme puisque deux groupes de deux lettres diffrents ontt crypts de la mme manire. On peroit ici les difficults que va soulever le dcryptage

c) Rversibilit du cryptage

Si les deux matrices colonnes, produits respectifs de deux matrices colonnes distinctesx

etX

Y

par

sont formes dlments ayant respectivement mme reste modulo 26, on peut crire :a bc d

mod26

mod26

ax by aX bY

cx dy cX dY

+ +

+ +,

On suppose par exemple que x et X sont distincts. Le systme prcdent conduit, en vertu desproprits des congruences, ( ) ( ) 0 mod 26ad bc x X .

Cette relation exprime le fait que 26 est un diviseur de ( ) (ad bc x X ) ), or (x X est en valeur

absolue strictement infrieur 26 et non nul. Les diviseurs premiers de 26 (2 et 13) ne peuvent donc

tous deux diviser (xX). Il sensuit que ( )ad bc et 26 ne sont pas premiers entre eux.

La condition (ad- bd) est premier avec 26 est donc une condition ncessaire pour que deux blocsde deux lettres diffrents soient crypts diffremment.

Nous admettons que cette condition est suffisante pour assurer le dcryptage de tout message.

d) Exemple de dcodage

La matrice M = est certes inversible, mais sa matrice inverse, telle quelle a t dfinie

prcdemment ne rpond pas au problme pos, mais ses coefficients vont tre une aide pour rpondreau problme pos. En effet, on trouve :

2 5

3 4

Pour assurer le dcryptage, on cherche une matrice N coefficients entiers telle que les coefficientsdes matricesMN,NMetI2

soient congrus modulo 26.

Le calcul prcdent deM1 fait apparatre que :

22 5 4 5 4 5 2 5 7 0 7I3 4 3 2 3 2 3 4 0 7 = =

=

1

.

Il ne reste donc plus qu dterminer linverse de 7 modulo 26, cest--dire un entier u tel quemod 26. Comme 7 et 26 sont premiers entre eux, il existe un unique entieru compris entre 0 et

25 et on trouve .7u

15u =

On a donc 15 mod 26 ce qui se traduit par 15 est linverse de 7 modulo 26.7 1





40/63

La matrice inverse modulo 26 de est donc la matrice . Cette matrice est

gale modulo 26.

2 5

3 4M

=

22 6 6 0 2 25

626 315 292 575 59 1025

4 515

3 2M

=

18 23

19 22

Le texte crypt, scind en blocs de deux lettres est WK GJ GI AZ CB ZZ.

Les rangs correspondants sont .10 9 8 25 1 25

Le bloc dcrypt est obtenu en multipliant M par chacune des matrices colonnes prcdentes et enretenant le rsultat modulo 26, soit :

638 312 290 550 60 1025

ce qui donne, modulo 26

2 3 6 3 7 11

14 0 4 4 8 11

et qui permet de retrouver le texte initial CODAGEDEHILL.

Ressources : http://euler.ac-versailles.fr/wm3/pi2/crypto/hill1.jsp

http://euler.ac-versailles.fr/wm3/pi2/matrice/inverse8.jsp

2. Approximation des nombres rels

a) Quelques rappels sur les fonctions homographiques

Nous nous intressons aux fonctions homographiques coefficients entiers dfinies surR+, c'est--dire auxfonctionsfdfinies surR+pour lesquelles il existe des entiers naturels a, b, c, et dtels que,

pour tout rel positifx, ( )ax b

f xcx d

+=

+ Parmi ces fonctions, certaines sont constantes (celles pour

lesquelles ), certaines sont affines (celles pour lesquelles0ad bc = 0c = ).

Il peut donc y avoir dbat dauteurs sur la dfinition.

Pour linstant, nous nous contentons dcarter la situation c=d=0, pour laquelle il ny a toutsimplement pas de fonction. On peut aussi observer que le quadruplet servant

caractriser une fonction comme homographique nest pas unique. Bref, nous ne travaillons pas dansun cadre assur. La proprit intressante, que nous souhaitons utiliser pour cette tude, est quunefonction homographique coefficients entiers naturels est monotone sur R+ et prend toutes les

valeurs comprises entre

( , , ,a b c d )

b

det

a

csi elle est croissante, toutes les valeurs comprises entre

a

cet

b

dsi

elle est dcroissante (on peut aussi dire que le sens de variation est donn par le signe de ).ad bc

b) Le calendrier : approximation dun rationnel par un rationnel plus simple

Au dbut de lanne 2000, lanne tropique (intervalle de temps sparant deux passages du soleildans la mme position sur son orbite apparente lcliptique) tait mesure 365,242 190 517 jours.



http://euler.ac-versailles.fr/wm3/pi2/crypto/hill1.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/inverse8.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/inverse8.jsphttp://euler.ac-versailles.fr/wm3/pi2/crypto/hill1.jsp


41/63

Comment faire varier le nombre (entier) de jours dans une anne sans bouleverser les habitudes de vie ?

Cest la question que des gouvernants ont eu rsoudre (en gypte antique, Rome sous Jules Csar,en Europe au XVIe sicle).

Les galits suivantes, obtenues en utilisant lalgorithme dEuclide :

1000000000 4 242190517 31237932242190 517 7 31237 932 23524 993

31237 932 1 23524 993 7 712 939

23524 993 3 7 712 939 386176

7 712 939 19 386176 375 595

386176 1 375595 10 581

= += +

= +

= +

= +

= +

permettentdcrire

242190517 111000000000 41

71

11

31

1910581

1375595

=+

++

++

+

Remarque : On peut naturellement poursuivre lalgorithme, mais cela naurait pas de lien aveclobjectif, qui est de fournir des approximations permettant de fabriquer un calendrier. Lecalendrier grgorien prvoit dajouter 97 jours tous les 400 ans (1 jour tous les 4 ans sauf pour les

millsimes multiples de 100 mais pas de 400). Rappelons que le rapport entre la dure de lannetropique et celle du jour sidral dure de la rotation de la Terre sur elle-mme subit des variationstelles quil est illusoire de les prvoir sur plusieurs milliers dannes.

Comme dit prcdemment, pour tout rel positifx,1

4x +est compris entre 0 et

1

4. Lajout dun jour

tous les quatre ans lanne calendaire est donc exagr. Si on poursuit les calculs, on peut crire :242190517 1 7

11000000000 4 2947

y

yy

+= =

+++

, ce qui permet daffirmer que 242190517

1000000000est suprieur

7

29.

Ajouter 7 jours tous les 29 ans lanne calendaire nest pas suffisant. Poursuivons les calculs

ltape suivante :

242190517 7 8

1000000000 29 33

z

z

+=

+montre que

8

33est une nouvelle approximation, meilleure que

1

4bien

quencore exagre.

Les fractions suivantes,31

128et

597

2465sont successivement des approximations par dfaut et par excs

des modifications apporter au calendrier pour sapprocher du rapport entre la dure de lannetropique et celle du jour sidral. Les valeurs approches fournies sont (dun certain point de vue quisera dvelopp dans la partie III) les meilleures possibles, mais on ne retrouve pas parmi elles les

97400

du calendrier grgorien.

Il est possible dcrire ces calculs autrement : chaque nouvel tage de la fraction crite plus haut

peut tre interprt comme lintervention dune fonction homographique. En appelant nf la fonction

dfinie surR+par ( )1

nf x n=

+, on peut crire :

4 7 1 3 19 1

242190517 10581

1000000000 375595f f f f f f

=

o o o o o

. Cette dcomposition montre que les

approximations trouves le sont sous forme irrductible, et alternativement par excs et par dfaut (lesfonctions quon compose sont toutes dcroissantes).





42/63

Il est possible de placer les coefficients des fonctions homographiques intervenant dans des tableaux,

de sorte que, nf tant reprsente par ,0 1

1 n

n pf fo le serait par ,

forme qui illustre le fait que

0 1 0 1 1

1 1 1

p

n p n n

=

p

+

pnf fo est diffrente de p nf fo ds que n etp sont diffrents.

c) Lexemple de 2

Le nombre 2 est la solution positive de lquation 2 2 0x = , qui peut encore scrire2

1

xx

x

+=

+,

puisque 1 nen est pas solution. Ce nombre est donc sa propre image par lapplication de R+dans R

qui donne de tout rel positif limage2

1

x +

+Les paragraphes prcdents fournissent un premier

rsultat : 2 est compris entre 1 et 2. Mais on peut aussi crire que 2 est solution de

22

12

1

1

xxxx

x

++

+=+

+

+

,

par une substitution lgitime. Tous calculs faits, on obtient :3 4

2 3

xx

x

+=

+, qui nous montre cette fois

que 2 est compris entre4

3et

3

2. ltape suivante, en reprenant lgalit

2

1

xx

+=

+, on trouvera

que 2 est solution de7 10

5 7

xx

x

+=

+, et que ce nombre est compris entre

7

5et

10

7(lcart est infrieur

3 centimes).

d) Lien avec le produit des matricesLes calculs prcdents nous ont donn lide que la compose de deux fonctions homographiques est elle-mme

une fonction homographique. En effet, si on a :

Alors on obtient par composition :

pour toutx, g(f(x)) =( )( )

ax ba b a a b c x a b b d

cx dax b c a d c x c b d d c dcx d

+ + + + ++ =+

+ + +++

,

avec les prcautions voques au paragraphea.).On observe que si on associe la matrice la fonctionfet la matrice

la fonctiong, alors la matriceBA est prcisment la matrice associe la fonctiongof.

Cela fournit une technique de calcul des coefficients de la compose de deux fonctionshomographiques.

Ressources : http://euler.ac-versailles.fr/wm3/pi2/matrice/homographique1.jsp

http://euler.ac-versailles.fr/wm3/pi2/matrice/homographique2.jsp





http://euler.ac-versailles.fr/wm3/pi2/matrice/homographique1.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/homographique2.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/homographique4.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/homographique5.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/homographique5.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/homographique4.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/homographique2.jsphttp://euler.ac-versailles.fr/wm3/pi2/matrice/homographique1.jsp


43/63

e) Le cas du nombre dOr

Le nombre dor, not , est la racine positive de lquation 2 1x= + . Il peut galement tre

considr comme unpoint fixe de lapplicationf, dfinie sur[ [1,+ par ( )1x

f x+

= .

La fonction fest dcroissante sur[ [1,+ et prend des valeurs comprises entre 1 et 2. tant un

point fixe de cette fonction, on peut obtenir un premier encadrement : 1 < < 2.

La relation ( ) ( )f f f = = o montre que est compris entre les extremums de la fonction

f fo . Comme, pour toutx lment de [ [1,+ , ( )

11 2 1

1 1

xxf f xx x

x

++ +

= =+ +

o , on dduit que :

Nous avons donc amlior lapproximation par dfaut de . Litration suivante consiste composer unefonction croissante ( fo ) par une fonction dcroissante f. On obtient une fonction dcroissantefournissant une nouvelle approximation par excs de . La poursuite du procd nous donne deux

suites adjacentes convergeant lune et lautre (bien sr) vers .

f) Les rduites

Lanalogie matricielle introduite prcdemment conduit considrer la suite des matrices

associes aux fonctions homographiquesfn.1 1

1 0n n

n n

na b

c d

=

Ces matrices satisfont la relation de rcurrence ,

o on voit poindre les suites de Fibonacci.

1 1

1 1

1 1

1 0n n n n n n n

n n n n n n n

a b a b a b a

c d c d c d c+ +

+ +

+ = = +

Le quotient du premier terme de la premire colonne de la matrice par le second est une

valeur approche de , alternativement par excs et par dfaut. Ces nombres sont appels rduites dudveloppement en fraction continue de .

1 1

1 0

n

Le termefraction continue lui-mme provient de lcriture possible :

1

1 111

11

1

1

1

= + ++

+

++

.

Les rduites du dveloppement de en fraction continue sont donnes par le tableau :

1 2 3 5 8 13 21 34 55 89 144 233

1 1 2 3 5 8 13 21 34 55 89 144





44/63

g) Les rduites comme meilleures approximations rationnelles

Plus gnralement, considrons un nombre rel irrationnel positifx. Soit le plus grand entier

infrieur ou gal x. On peut crire :

1a

1 1

1x a u a= + = + Le nombre y est son tour un

Documents

Scilab in FRENCH Maths-S-Specialite_207893