Logique - Condition nécessaire ; condition suffisante
Qui est suffisant à qui ? Exercice 7 : Si A B
Fiche AP – Condition nécessaire et suffisante
Dans cet exemple la condition suffisante est faire une omelette donc : Exercice : Trouver dans chaque cas la condition nécessaire et la condition ...
Logique : vrai/faux ; condition nécessaire suffisante ou nécessaire
"Trouver une condition nécessaire et suffisante pour que A soit vraie" il s'agit de trouver une condition B telle que A ?? B. 2. Page 3. Exercice 1. 1.
Induction: corrigés
Condition suffisante et nécessaire. On parle souvent en philosophie
Corrigés des exercices
g) r ? ¬x (la « condition » est ici nécessaire et suffisante) aux mêmes conclusions que précédemment (voir corrigé de l'exercice 20).
Exercices de logique I Un peu de bon sens Exercice 1 Complétez
Exercice 3. 1 La proposition « arriver à la gare avant 10h » est-elle une condition « nécessaire » / « suffisante » /. « nécessaire et suffisante » pour
Chapitre 6: Graphes eulériens et hamiltoniens 6.1 Introduction et les
Exercice 71 Parmi les graphes suivants lesquels contiennent un chemin eulérien 6.2 Conditions nécessaires et suffisantes pour l'existence de cycles ...
Chapitre 19 POLYNÔMES Enoncé des exercices
Exercice 19.11 Donner une CNS (Condition nécessaire et suffisante) pour que X2+1 divise X4+X3+?X2+µX+2 dans C[X]. Exercice 19.12 Soit t ? R n ? N
Analyse Numérique 0 0
Sous quelle condition nécessaire et suffisante L est-elle inversible ? On revient sur la premi`ere matrice donnée dans l'exercice 2 :.
Corrigé exercices 7 et 10 feuille 2
L'ensemble ?i?IHi est donc un sous-groupe de G. 2. Donner une condition nécessaire et suffisante pour que l'union de deux sous-groupes de G soit un sous-
[PDF] Logique - Condition nécessaire ; condition suffisante
Exercice 1 : Dire si les affirmations suivantes sont vraies ou fausses : a) Pour avoir son permis de conduire il faut réussir son examen de conduite b) Pour
[PDF] Logique : vrai/faux ; condition nécessaire - Denis Vekemans
"Trouver une condition nécessaire et suffisante pour que A soit vraie" il s'agit de trouver une condition B telle que A ?? B 2 Page 3 Exercice 1 1
[PDF] Corrigés des exercices - De Boeck Supérieur
d) Le travail n'est pas une condition suffisante pour la réussite e) Être aimable est une condition nécessaire pour être aimé
[PDF] Logique
Vous devrez chercher à en cerner l'aspect pratique et en particulier à bien maîtriser les quelques exercices corrigés Le programme officiel de mathématiques
Exercices corrigés -Bases de la logique - propositions - quantificateurs
Trouver des conditions suffisantes (pas forcément nécessaires) à chacune des propositions suivantes : Avoir son bac Le point A A appartient
[PDF] Exercices de logique - Dimension K
Plus grand ou égal à 6 est nécessaire mais pas suffisant car 7 n'est pas divisible par 6 Exercices 4 Les conditions A et B sont en relation dire de chacune d
[PDF] Induction: corrigés - Julien Dutant
Condition suffisante et nécessaire On parle souvent en philosophie de conditions nécessaires et/ou suffisantes (Ou du moins on
[PDF] Exercices_logique_raisonnementpdf
Exercice transversal ( exercice 11) Conditions nécessaire et suffisante ? Inéquations et carrés ( exercice 12) ? Configurations et vecteurs
[PDF] Exercices de logique : corrigé - Normale Sup
24 sept 2007 · Exercices de logique : corrigé Exercice 1 : Y Vérifions par contraposée que cette condition suffisante est également nécessaire
Logique - Mathraining
Un des points souvent mal compris en mathématique est la différence cruciale entre une condition nécessaire et une condition suffisante
![Analyse Numérique 0 0 Analyse Numérique 0 0](https://pdfprof.com/Listes/17/43295-17CTD3-6.pdf.pdf.jpg)
Analyse Num´eriqueCorrig´e du TD 6
EXERCICE 1
Matrices diagonales, triangulaires
1.1 Matrices diagonales
SoitD= (dii)i=1,...,nune matrice diagonale d"ordren >0. Donner une condition n´ecessaire et suffisante pour queDsoit inversible. On peut repr´esenterDsous forme du tableau suivant : (d 11 ...0 d ii0 d nn))))))))Commedet D=n?
i=1d ii, on aDinversible??det D?= 0??dii?= 0,?i= 1,...,n.
1.2 Matrices triangulaires inf´erieures
SoitL= (lij)i,j=1,...,nune matrice triangulaire inf´erieure d"ordren >0. a. Sous quelle condition n´ecessaire et suffisanteLest-elle inversible?La matriceLpeut se mettre sous la forme suivant :
(l 11 l21l22......
l1ilijlii0
.ln-1n-1 l n1lnj···lnn-1lnn)))))))))))))) d"o`u la matrice triangulaire inf´erieureLpeut ˆetre caract´eris´ee par : 1 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009 lij= 0 sii < j,?i,j= 1,...,n.Puisquedet L=n?
i=1l ii, on aLinversible??det L?= 0??lii?= 0,?i= 1,...,n.
b. On suppose que la matrice triangulaire inf´erieureLest inversible. Soitb un vecteur colonne ayantncomposantes. Donner un algorithme qui permet de r´esoudre l"´equation d"inconnuey:Ly=b.(1.1)
Commelii?= 0,?i= 1,...,n, la r´esolution du syst`eme (1.1) s"´ecrit y1=b1l11, y i=1 lii? b i-i-1? j=1l ijyj? ,?i= 2,...,n. (1.2) Quel est le coˆut de cet algorithme en termes d"op´erations ´el´ementaires (addi- tions, multiplications, divisions) ? Le calcul dey1demande 1 division (div) dans l"algorithme (1.2). Pourifix´e dans{1,...,n}, le calcul deyipar l"algorithme (1.2) requiert 1 division (div), i-1 additions (add) eti-1 multiplications (mult).Au total le coˆutCLde l"algorithme (1.2) est
CL= 1 div +n?
i=2? (i-1) add + (i-1) mult + 1 div? = 1 div + n? i=21 div +n-1? k=1kadd +n-1? k=1kmult (n-1)n2add +(n-1)n2mult +ndiv.
Le nombre d"op´erations ´el´ementairesCLest de l"ordre den2,i.e.CL=O(n2). 2 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/20091.3 Matrices triangulaires sup´erieures
On consid`ere une matrice triangulaire sup´erieureUd"ordren >0 . a. Donner une condition n´ecessaire et suffisante pour queUsoit inversible.La matriceUpeut se mettre sous la forme suivant :
(u11u12···u1ju1n-1u1n
u22u2n-1u2n......
u iiuijuin 0 u n-1n-1un-1n u nn)))))))))))))) d"o`u la matrice triangulaire inf´erieureUpeut ˆetre caract´eris´ee par : u ij= 0 sii > j,?i,j= 1,...,n.Commedet U=n?
i=1u ii, on aUinversible??det U?= 0??uii?= 0,?i= 1,...,n.
b. On suppose que la matrice triangulaire sup´erieureUest inversible. Soity un vecteur colonne donn´e ayantncomposantes. Ecrire un algorithme qui permet de r´esoudre l"´equation d"inconnuex:U x=y .(1.3)
Lesuii´etant non nuls, l"inconnuexsolution du syst`eme lin´eaire (1.3) est donn´ee par xn=ynunn, x i=1 uii? y i-n? j=i+1u ijyj? ,?i= 1,...,n-1. (1.4)Donner la complexit´e de cet algorithme.
Le calcul dexnrequiert 1 multiplication (mult) dans l"algorithme (1.4). Pourifix´e dans{1,...,n}, le calcul dexipar l"algorithme (1.4) demande 1 division (div), n-iadditions (add) etn-imultiplications. 3 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009Par suite le coˆutCUde l"algorithme (1.4) est
CU= 1 div +n-1?
i=1? (n-i) add + (n-i) mult + 1 div? n-1? k=1kadd +n-1? k=1kmult + 1 div +n-1? i=11 div (n-1)n2add +(n-1)n2mult +ndiv.
Le nombre d"op´erations ´el´ementairesCUest de l"ordre den2,i.e.CU=O(n2)..Vocabulaire
L"algorithme (1.2) pour inverser les syst`emes triangulaires inf´erieurs est ditdescente ousubstitution directe. L"algorithme (1.4) pour r´esoudre les syst`emes triangulaires sup´erieurs est ditremont´eeousubstitution r´etrograde.EXERCICE 2
M´ethode d"´elimination de Gauss
2.1 Des exemples
Effectuer une ´elimination de Gauss sur les syst`eme lin´eaires suivants (2 4 41 3 11 5 6)) (x 1 x 2 x 3)) =((21 -6)) (1 0 6 28 0-2-22 9 1 3
2 1-3 10))))
(x 1 x 2 x 3 x 4)))) =((((6 -2 -8 -4))))Premier exemple
Nous ´ecrivons le premier syst`eme sous la forme du tableau (2 4 4 21 3 1 11 5 6-6)) L 1 L 2 L 3 On effectue l"´elimination de Gauss. On a successivement (2 4 4 20 1-1 00 3 4-7))
L2←L2-0.5L1
L3←L3-0.5L1(2.1)
4 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009 (2 4 4 20 1-1 00 0 7-7))
L3←L3-3L2
On obtient alors le syst`eme triangulaire suivant
?2x1+ 4x2+ 4x3= 2 x2-x3= 0
7x3=-7
En utilisant l"algorithme de remont´ee (1.2) on a successivement x3=-1,x2=-1,x1= 5.
L"´elimination de Gauss ci-dessus est ditesans permutation. On peut par exemple `a l"´etape (2.1) ci-dessus, remplacer le pivot 1 par le coefficient 3 dex2de la derni`ere ligne, parce que 3>1 donne plus de stabilit´e num´erique. Dans ce cas on dit que l"on fait une ´elimination de Gauss avecpivot partiel. Dans ce contexte on obtient (2 4 4 20 3 4-70 1-1 0))
L3←→L2
(2 4 4 20 3 4-7 0 0-7373)))
L3←L3-13×L2
D"o`u on obtient le syst`eme triangulaire sup´erieur suivant ?2x1+ 4x2+ 4x3= 23x2+ 4x3=-7
73x3=73
En appliquant l"algorithme de remont´ee `a ce syst`eme on obtient x3=-1,x2=-1,x1= 5.
On peut enfin par exemple `a l"´etape (2.1) ci-dessus, remplacer le pivot 1 par le coefficient
le plus grand en module dans la sous-matrice 1-1 3 4 Ceci rend la m´ethode plus stable num´eriquement. Ici on trouve 4 comme nouveau pivot. Dans ce cas on dit que l"on fait une ´elimination de Gauss avecpivot partiel. Dans ce 5 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009 contexte on obtient((2 4 4 20 3 4-70 1-1 0))
L2←→L3
(2 4 4 20 4 3-70-1 1 0))
c2←→c3 (2 4 4 20 4 3-7 0 0 74-74)))
L3←-L3+14L2
Cette derni`ere transformation donne le syst`eme lin´eaire suivant ?2x1+ 4x3+ 4x2= 2 + 4x3+ 3x2=-7 74x2=-74
Par application de l"algorithme de remont´ee au syst`eme triangulaire ci-dessus on obtient : x2=-1,x3=-1,x1= 5.
Deuxi`eme exemple
On met le deuxi`eme exemple sous forme du tableau suivant (1 0 6 2 68 0-2-2-22 9 1 3-8
2 1-3 10-4))))
L 1 L 2 L 3 L 4 puis on effectue (1 0 6 2 60 0-50-18-500 9-11-1-20
0 1-15 6-16))))
L2←L2-8L1
L3←L3-2L1
L4←L4-2L1(2.2)
La matrice obtenue apr`es la 1
i`ere´etape d"´elimination (2.2) a pour pivot 0. Pour continuerla m´ethode de Gauss, on peut soit utiliser la strat´egie de pivot partiel ou soit celle de pivot
total. Pivot partiel: on prend comme pivot le plus grand ´el´ement de la colonne (091)) 6 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009 Cela revient `a ´echanger la 2i`emeet la 3i`emelignes. On obtient (1 0 6 2 60 9-11-1-200 0-50-18-50
0 1-15 6-16))))
L2←→L3
On continue l"´elimination :
(1 0 6 2 60 9-11-1-200 0-50-18-50
0 0-124
9559-1249)))))
L4←L4-19L2
(1 0 6 2 60 9-11-1-200 0-50-18-50
0 0 0 24912250)))))
L4←L4-1501249L3
On d´eduit le syst`eme triangulaire sup´erieur suivant ?x1+ 6x3+ 2x4= 6
9x2-11x3-x4=-20
-50x3-18x4=-50 2491225x4= 0
D"o`u par la formule de remont´ee on trouve
x4= 0,x3= 1,x2=-1,x1= 0.
Pivot total: On part de l"´etape (2.2) de l"´elimination de Gauss. Le plus grand ´el´ement
en module de la sous-matrice0-50-18
9-11-1
1-15 6
est-50, qui se trouve `a la 2i`emeligne et `a la 3i`emecolonne de la matrice de d´epart. On positionne-50 en pivot, en ´echangeant la 2i`emecolonne et la 3i`emecolonne : (1 6 0 2 60-50 0-18-500-11 9-1-20
0-15 1 6-16))))
c2←→c3
7 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009On continue l"´elimination :
(1 6 0 2 60-50 0-18-50 0 0 9 7425-9
0 0 1 285
25-1)))))))
L3←→L3-11
50L2L
4←→L4-15
50L2(1 6 0 2 60-50 0-18-50 0 0 9 74
25-9
0 0 0 2491
2250)))))))
L4←→L4-19L3
Ce qui conduit au syst`eme lin´eaire suivant
?x1+ 6x3+ 2x4= 6
-50x3-18x4=-509x2+74
25x4=-9
2491225x4= 0
dont la solution est x4= 0,x2=-1,x3= 1,x1= 0.
2.2 Cas g´en´eral
On consid`ere maintenant le cas g´en´eral d"un syst`eme lin´eaireAx=b. a. ´Ecrire un algorithme de r´esolution de ce syst`eme par la m´ethode deGauss.
On ´ecrit l"algorithme dans le cas avec pivot partiel. En modifiant l"´etape de la recherche de pivot, on obtient soit l"algorithme de pivot total ou soitl"´elimination de Gauss sans permutation. 8 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009 //Triangulation pouriallant de1`an-1faire //Recherche du pivot partiel numlignepiv=i pourkallant dei`anfaire si|A(k,i)|>|A(numlignepiv,i)|alors numlignepiv=k finsi //On met le pivot `a sa place sinumlignepiv?=ialors //On ´echange les lignes numlignepiv et i pourjallant dei`anfaire tampon=A(numlignepiv,j)A(numlignepiv,j) =A(i,j)
A(i,j) =tampon
finpour finsi finpour //Elimination pivot=A(i,i) pourkallant dei+ 1`anfaire factpivot=A(k,i) pivot pourjallant dei`anfaireA(k,j) =A(k,j)-factpivot?A(i,j)
finpour b(k) =b(k)-factpivot?b(i) finpour 9 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009 //R´esolution par la remont´eeX(n) =b(n)
A(n,n)
pouriallant den-1`a1par pas de-1faire pourjallant dei+ 1`anfaire b(i) =b(i)-A(i,j)?X(j) finpourX(i) =b(i)
A(i,i)
finpour b. Donner la complexit´e de cet algorithme. Le coˆut des op´erations calcul´e ici ne tient pas compte de la recherche du pivot.On s"int´eresse `a la partie "´elimination" de l"algorithme ci-dessus. Consid´erons la i`eme
´etape de l"´elimination,i? {1,...,n}. Pour chaque lignekallant dei+ 1 `anon fait les op´erations suivantes : - une division (div) afin de calculer une fois pour toute le coefficient permettant d"ob- tenir des z´eros sous le pivot; - une adddition (add) et une multiplication (mult) permettant de mettre `a jour chaque coefficient de la lignek, ce qui correspond `a toutes les colonnes de num´erosjvariant dei`an; - une addition (add) et une multiplication (mult) permettant de mettre `a jour le second membre de la lignek,i.e.b(k). Le nombre d"op´erations pour l"´elimination de Gauss avec prise en compte du second membre s"´ecrit donc CE=n-1?
i=1n k=i+1?1 div +?
n? j=i(1 add + 1 mult)? + 1 add + 1 mult? n-1? i=1n k=i+1?1 div + (n-i+ 1) add + (n-i+ 1) mult?
n-1? i=1? (n-i)div + (n-i)(n-i+ 1) add + (n-i)(n-i+ 1) mult? 10 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009CE=n-1?
i=1(n-i) div +n-1? i=1(n-i)(n-i+ 1)add +n-1? i=1(n-i)(n-i+ 1) mult n-1? i=1(n-i) div +? n-1? i=1(n-i) +n-1? i=1(n-i)2? add +? n-1? i=1(n-i) +n-1? i=1(n-i)2? n-1? l=1ldiv +? n-1? l=1l+n-1? l=1l 2? add +? n-1? l=1l+n-1? l=1l 2? mult (n-1)n2div +(n-1)n2add +n(n-1)(2n-1)6add
(n-1)n2mult +n(n-1)(2n-1)6mult.
Il vient le nombre d"op´erations de la partie ´elimination de l"algorithme de Gauss est dequotesdbs_dbs31.pdfusesText_37[PDF] condition suffisante definition
[PDF] conditions nécessaires et suffisantes linguistique
[PDF] condition suffisante philo
[PDF] exercice condition nécessaire et suffisante
[PDF] la condition ouvrière au 19ème siècle en france
[PDF] condition ouvriere au 21eme siecle
[PDF] etre ouvrier au 20eme siecle
[PDF] évolution des conditions de travail des ouvriers
[PDF] quelle est la principale revendication des ouvriers entre 1880 et 1910
[PDF] conditions standard thermodynamique
[PDF] loi des gaz parfaits
[PDF] condition standard de température et de pression volume molaire
[PDF] masse d'un gaz
[PDF] relation entre pression et température