Regardez ces quatre (4) vidéos en ordre. La durée totale est de 27 minutes. N'oubliez pas de tester vos connaissances à l'aide des tests de connaissances après chaque vidéo.
Description: Cette vidéo explique comment décomposer une matrice en matrice triangulaire supérieure et inférieure, puis résoudre le problème en utilisant la substitution vers avant et arrière. Ces trois étapes forment la décomposition de Crout.
Bonjour, cette vidéo est SE|LV|06 et il s’agit de la théorie de la décomposition de Crout pour la résolution des systèmes d'équations.
Parlons d'abord de la théorie générale de la décomposition de Crout. Le système d'équations standard que nous avons est généralement [A][X]=[B]. Dans le passé, nous avons utilisé l'élimination de Gauss pour le résoudre. Cependant, il se peut que différentes matrices B doivent être résolues pour la même matrice [A]. Dans ce cas, l'élimination de Gauss n'est pas très efficace. Il existe d'autres méthodes appelées décomposition LU qui sont en fait excellentes pour résoudre les systèmes avec plusieurs matrices [B]. Ce que nous faisons ici est d'abord de décomposer [A] en deux matrices différentes, [L] la matrice inférieure et [U] la matrice supérieure. Une fois cette étape de décomposition est complète, nous passons à l'étape suivante, la substitution vers l’avant. Dans la substitution vers l’avant, nous utilisons cette matrice inférieure [L] et la matrice [B] pour trouver une matrice intermédiaire [D]. Avec [D] et [U], nous pouvons résoudre pour [X] en faisant la substitution vers l’arrière, ce qui est la troisième étape. Ce qui est bien ici, c'est qu'une fois que la matrice a été décomposée, tout ce qu'il faut faire, c'est une substitution vers l’avant, puis une substitution vers l’arrière pour chaque nouvelle valeur de [B]. Cela devient beaucoup plus efficace que l'élimination de Gauss pour ces types de problèmes.
Pour rappel, on a la matrice [A] qui est égale à tous les coefficients a11, a12, etc, jusqu'à ann. La matrice [L] est une matrice inférieure et elle représente la matrice triangulaire inférieure, c'est-à-dire que tous les coefficients sur la diagonale et en dessous sont remplies de valeurs et tous les coefficients au-dessus de la diagonale sont toutes 0. La matrice triangulaire supérieure est [U], et elle se présente comme suit: tous les coefficients au-dessus de la diagonale on comme valeurs u12, u1n, etc et tous les coefficients en dessous de la diagonale sont égales à 0. Tous les coefficients sur la diagonale sont égales à 1. Ce type de méthode de décomposition est la méthode de décomposition de Crout. Vous pouvez aussi combiner les matrices [L] et [U] ensemble dans une matrice [A'] où les valeurs des coefficients de L et U ne se chevauchent pas. Si vous décidez de programmer cela, elles seront également stockées ensemble.
La question maintenant est de savoir comment décomposer la matrice. Il existe une série d'équations que vous pouvez utiliser pour la décomposition de Crout et nous allons les revoir ensemble maintenant. La première étape consiste à commencer avec votre matrice [A]. L'étape 1a est que li1 = ai1. Une fois que vous avez ces valeurs, nous allons passer à l'étape 1b. Pour 1b, u1j = a1j/l11. Ceci la première étape. Pour tous les prochains points intérieurs, nous allons utiliser des formules différentes. Ainsi, pour 2a, nous utiliserons lij = aij - la somme de k = 1 à j - 1 de likukj. Cela fait partie de l'étape de décomposition et ce que vous remarquerez ici, c'est qu'il y a en fait une soustraction dans l’équation, donc ce que vous faites est en fait une méthode d'élimination, comme pour l'élimination de Gauss. Après 2a nous passons à 2b, qui est ujk = ajk - somme de i = 1 à j -1 de ljiuik tous divisés par ljj. Ceci était l'étape pour la partie supérieure de la matrice. Ensuite, nous allons utiliser la même formule pour 3a que celle utilisée pour 2a et continuer avec la même formule pour 3b que celle utilisée pour 2b et ainsi de suite jusqu'à ce que vous arriviez au dernier coin de la matrice à ann. Pour la dernière valeur n, nous utiliserons lnn = ann - somme de k =1 à n -1 de lnkukn. Maintenant, cela peut sembler complexe, mais en prenant un exemple, vous remarquerez que c'est relativement simple et répétitif. Nous couvrirons l’exemple dans une prochaine vidéo.
Une fois que nous avons complété la décomposition, nous pouvons effectuer la substitution vers l'avant en utilisant la relation suivante: [L][D] = [B]. Vous remarquerez que si nous prenons la matrice [L], pour disons une matrice 4x4 ici, vous remarquerez que vous pouvez obtenir des relations assez facilement à partir des équations ici. Donc, d1 = b1/l11et ainsi de suite jusqu'à d4. Il s'agit donc d'une substitution vers l’avant. Une fois que nous avons cette matrice intermédiaire [D], nous pouvons maintenant résoudre [X] en utilisant la matrice [U]. Donc [U][X] = [B]. Ce que vous remarquerez ici est que, si nous utilisons la matrice supérieure, le processus sera très similaire à ce qui a été fait auparavant. Nous pouvons résoudre les valeurs de x. Donc par exemple, x4 = d4, x3 = d3 -u34x4, etc., jusqu'à ce que vous obteniez les valeurs finales.
Examinons maintenant l'algorithme.
Ceci conclut la vidéo. Ce projet n'aurait pu être réalisé sans le soutien d'eCampusOntario et de l'Université d'Ottawa.
Description: Cette vidéo met en œuvre la théorie de la décomposition de Crout dans un problème pratique, selon une approche étape par étape.
Bonjour, cette vidéo est SE|LV|07 et il s'agit d'un exemple étape par étape de la décomposition de Crout pour résoudre des systèmes d'équations.
Examinons maintenant le problème. Résolvez les systèmes d'équations suivants en utilisant la décomposition de Crout. Vous remarquerez que nous avons deux ensembles de systèmes d'équations, mais que les deux partagent la même matrice [A]. La seule chose qui diffère est que les matrices [B] ont des valeurs différentes. Il s'agit d'un excellent exemple de l’utilisation de la décomposition de Crout. Donc, pour récapituler, nous avons la matrice [A] ou la première rangée est, 5, 4, 4, 8, la deuxième rangée est 7, 8, 6, 8, la troisième rangée est 6, 10, 8, 9 et la quatrième rangée est 3, -3, 7, 9. Nous avons une matrice [B], que nous appellerons [B1], qui est -26.5, -13.5, -17, et -65 et une autre matrice [B], que nous appellerons [B2], qui est -20, -10, -30 et -40. Rappelez-vous que nous voulons créer une matrice triangulaire inférieure appelée [L], où il y a des coefficients L dans la partie triangulaire inférieur de la matrice, y compris la diagonale et des zéros au-dessus. Nous voulons aussi créer une matrice triangulaire supérieure [U], où il y a des coefficients 1 sur la diagonale, des valeurs U dans la partie triangulaire supérieure et des 0 dans la partie triangulaire inférieure de la matrice. Pour cet exemple, nous allons utiliser [A'], qui sera une combinaison de [L] et [U], pour stocker les valeurs et observer les changements. Ce n'est pas une vraie matrice, mais c'est une bonne technique temporaire pour résoudre ces problèmes.
Pour cet exemple, nous n'utiliserons pas de pivotement partiel ni déplacement de rangée afin de nous concentrer sur la décomposition LU. La première étape consiste à utiliser l'équation 1a qui est li1= ai1. Ce qu'on va faire ici, c'est résoudre la première colonne qui est 5, 7, 6, 3. Essentiellement, les valeurs de la matrice [L] sont les mêmes. Donc les valeurs de la matrice [L] exprimées ici dans la matrice [A'] sont remplacées. L'équation suivante est 1b, c'est-à-dire u1j = a1j /l11. Nous allons le faire en commençant par la colonne j = 2 dans la première rangée. Pour ce faire, nous allons utiliser la valeur L que nous avons trouvé, qui est 5, et avec ceci nous pouvons calculer ces trois valeurs, qui seront 4/5, 4/5 et 8/5. Maintenant que nous avons complété la première colonne et la première rangée, on va passer à l'équation 2a, qui est lij = aij - somme de k = 1 à j - 1 de likukj. Mais, à quoi cela ressemble-t-il si nous utilisons des valeurs? Nous allons premièrement chercher pour l22. Si on introduit les valeurs, on obtient l22 = a22 - l21u12. Si vous regardez une matrice [A'] ici, vous verrez les valeurs surlignées que nous utilisons. Nous pouvons faire la même chose pour le coefficient suivant, qui est l23 = a23 - l21u12, et l24 = a24 - l41u12. Une fois que nous avons trouvé ces valeurs et décomposé la colonne, nous allons continuer et passer à l'équation 2b. Dans ce cas, l'équation à utiliser est ujk = ajk - somme de i = 1 à j - 1 de ljiuik tous divisés par ljj. Nous commencerons avec u23 et ce sera égal à (a23-l21u13)/l22. Vous remarquerez dans la matrice [A'] ici, les valeurs surlignées qui sont utilisées pour calculer u23. Nous pouvons faire la même chose pour u24 qui est égal à (a24-l21u14)/l22. Maintenant nous avons résolu jusqu'à la deuxième rangée de la matrice [A']. Et nous continuons comme avant, avec l’étape 3a, qui utilise la même équation que l’étape 2a. Nous allons commencer à chercher l33 au début et ce que vous remarquerez c'est que puisque j = 3, nous allons avoir plusieurs termes dans notre sommation. Donc l33 = a33 -l31u13 - l32u23. Si vous regardez la matrice [A'], nous cherchons la valeur de l33 et elle est liée aux valeurs situées à sa gauche et au-dessus d'elle dans la matrice. Nous pouvons faire la même chose pour l43 qui sera égal à a43 - l41u13 - l42u23. Nous avons maintenant la matrice [A'] avec les valeurs que nous avons résolues pour les trois premières colonnes. Continuons en utilisant l'équation 3B, qui est la même que 2b. Ce que nous allons faire ici est de trouver la valeur de u34. À nouveau, comme dans l'équation 3a, nous avons plusieurs termes dans notre sommation ici. u34 = (a34 - l31u14 - l32u24)/l33. Vous remarquerez que nous cherchons la valeur de u34 et qu'elle est liée à toutes les valeurs à sa gauche et au-dessus d'elle dans la matrice [A']. Après avoir calculer ceci, il nous reste qu'une dernière valeur à trouver. Pour la dernière valeur, nous utiliserons l'équation 4, qui sera le coin ici, qui est lnn = ann - somme de k = 1 à n - 1 de lnkukn. Puisque n =4, nous aurons en fait trois termes dans notre sommation. Donc l44 = a44 - l41u14 - l42u24 - l43u34. Comme précédemment, si vous regardez la valeur que nous recherchons dans [A'], l44 est lié à toutes les valeurs situées à sa gauche et au-dessus. Avec cette dernière valeur de calculée, nous avons décomposé la matrice.
Vous pouvez maintenant prendre cette matrice [A'] et la séparer de manière appropriée dans les matrices [L] et [U]. Si vous le souhaitez, vous pouvez vous assurer que [L][U] = [A] grâce à la multiplication matricielle. En les multipliant, vous devriez obtenir la matrice [A] si vous avez effectué la décomposition correctement.
Maintenant nous allons utiliser la substitution vers l’avant avec [L][D]=[B]. Ce que nous recherchons ici, c'est la matrice [D], une matrice intermédiaire que nous allons utiliser plus tard. Nous allons donc faire apparaître notre matrice L et notre matrice [B1]. Ce que vous remarquerez ici, c'est que nous pouvons les convertir en équations et les résoudre. Nous pouvons également regarder l'autre matrice [B] que nous avions, qui est la matrice [B2] et nous pouvons également trouver ses équations. Vous remarquerez que le côté gauche, avec tous les termes 5d1, etc. sont égales et la seule partie qui est différente est le côté droit de ces équations. Voici les équations et nous pouvons prendre le côté gauche et trouver notre matrice [D1] qui est égale à -5.3, 9.8333, -15.57, -5. Nous pouvons ensuite appliquer la même technique pour trouver votre matrice [D2], qui est -4, 7.5, -19.286, -6.6136. Notez que ces matrices [D] sont intermédiaires, elles ne sont pas les réponses.
Nous allons utiliser notre matrice triangulaire supérieure pour résoudre ce problème. Maintenant que nous avons nos matrices [D] intermédiaires, nous pouvons utiliser la relation [U][X] = [D]. Nous pouvons donc résoudre les valeurs de x que nous recherchons. Pour rappel, [U] est la matrice triangulaire supérieure et nous avons nos valeurs de [D1]. Si vous observez ici, la meilleure équation à utiliser est la quatrième équation et nous pourrions faire une substitution vers l’arrière pour trouver que x4 = 5 et résoudre le restant des équations basées sur les autres valeurs de x. On peut faire la même chose pour [D2]. Comme précédemment, le côté gauche de l'équation, dans ces deux ensembles, est égal et tout ce qui change est le côté droit. Résolvons les équations en commençant par la première. Lorsque nous résolvons les valeurs, notre estimation de la matrice [X1] est de 1.5, 3.5, -2, -5 et notre estimation de la matrice [X2] est de 8.5259, -1.0956, -1.3347, et -6.6136. Ce sont les réponses finales et vous pouvez les réévaluer dans les équations originales et pour vérifier qu’elles fonctionnent.
Ceci conclut la vidéo. Ce projet n'aurait pu être réalisé sans le soutien d'eCampusOntario et de l'Université d'Ottawa.
Description: Cette vidéo explique comment utiliser un cas particulier de décomposition pour résoudre des matrices tridiagonales appelée l’algorithme de Thomas. Cette méthode ne peut être utilisée que pour les matrices tridiagonales.
Bonjour, cette vidéo est SE|LV|08 et il s’agit de la théorie de l'algorithme de Thomas pour résoudre les matrices tridiagonales.
Examinons la théorie générale de l'algorithme de Thomas. L'algorithme de Thomas est un algorithme spécial, qui est en fait un cas particulier de la décomposition LU, mais qui s'applique juste aux matrices qui ont des valeurs que sur la diagonale principale et les diagonales supérieure et inférieure. Tout le reste de la matrice doit être égal à 0. C'est en fait assez courant dans de nombreux problèmes d'ingénierie et donc très utile pour un ingénieur. Nous avons une certaine notation pour cela. Nous avons la diagonale inférieure, appelée E, qui commence à e2, car elle commence à la rangée 2, jusqu’à en. Nous avons la diagonale supérieure, appelée G, commençant à g1 jusqu’à gn-1. Nous avons la diagonale principale, appelée F, allant de f1 jusqu’à fn. Et finalement nous avons ce qui était les valeurs de b, que nous appelons R dans ce cas.
Comme pour la décomposition LU, nous allons commencer par la décomposition de la matrice. Donc pour k = 2 jusqu’à n, nous avons deux équations. Tout d'abord, nous avons ek = ek/fk-1 puis nous avons fk = fk-ekgk-1. Ce qui est important de noter ici, c'est que vous mettez à jour les valeurs de e et de f au fur et à mesure que vous progressez. Par exemple, si vous aviez e2, il serait mis à jour dans la première équation et ce e2 serait aussi utilisé pour mettre à jour f2 dans la deuxième équation ici. Une bonne façon d'organiser cela est d'utiliser des matrices. Nous aurons donc la matrice [E], la matrice [G] et la matrice [F]. Vous remarquerez qu’il n'y a pas de valeur de e à e1, puisque la matrice [E] représente la diagonale inférieure et a une valeur de moins que la diagonale principale. La même chose s’applique pour la matrice [G]. Elle commence de g1 jusqu’à g4, et il n'y a pas de valeur à la fin pour g5. Nous pouvons remplir ces matrices en utilisant les valeurs de nos diagonales de nos équations. Ainsi, la matrice [E] peut être remplie, notre matrice [G] peut être remplie, et notre matrice [F] peut être remplie. Lorsqu’on fait cela, nous obtiendrons ces matrices ici. Donc [E] est égal à valeur vide ou 0, 2, 2, 7, 8, [G] est égal à 4, 1, 2, 8, 0, et [F] est égal à 1, 6, 9, 9, 1. Lorsque nous aurons terminé de passer à travers des équations et de mettre à jour les valeurs, les matrices ressemblerons à ceci. Vous remarquerez que [G] ne change pas et que l’élément 1 de la matrice [F], c’est-à-dire f1, ne change pas non plus. Par contre tout le reste des valeurs changent au fur et à mesure du processus de mise à jour.
L'étape suivante est la substitution vers l’avant. Encore une fois, nous allons passer de k = 2 jusqu’à n et la formule ici est rk = rk – ekrk-1. Comme précédemment, nous allons continuellement mettre à jour nos valeurs. Donc par exemple, nous allons calculer r2 et r2 sera utilisé pour calculer r3. Ce sera la valeur mise à jour. Premièrement, nous pouvons obtenir nos valeurs et les placer à nouveau dans une matrice. Dans ce cas-ci, c'est essentiellement égal à la matrice [B] que nous avons vue auparavant. Donc la matrice [R] se présentera comme suit : 21, 37, 39 ,47, 17. Lorsque nous appliquons la formule ci-dessus, nous obtiendrons est la matrice [R‘] dans ce cas. La première valeur de r1 reste la même, 21, mais les autres valeurs vont changer.
La dernière étape est la substitution vers l’arrière. La première étape consiste à trouver la dernière valeur, dans ce cas, xn = rn/fn. Puis, pour toutes les autres valeurs de k = n-1 jusqu’à 1, nous utiliserons la formule suivante : xk = (rk-gk*xk+1)/fk. Ce que vous remarquerez ici, c'est que nous utiliserons chaque valeur de x calculée au fur et à mesure que nous avancerons. Par exemple, si nous cherchons x2, nous devons connaître x3 et si nous cherchons x3, nous devons connaître x4 et ainsi de suite. C'est le processus de substitution vers l’arrière que nous utilisons normalement. Dans ce cas, pour vous donner un aperçu, la première équation pour xn nous donne la dernière valeur et l'autre équation pour xk nous donnera les autres.
Parlons de l'algorithme.
Ceci conclut la vidéo. Ce projet n'aurait pu être réalisé sans le soutien d'eCampusOntario et de l'Université d'Ottawa.
Description: Cette vidéo met en œuvre la théorie de l’algorithme de Thomas dans un problème pratique, selon une approche étape par étape.
Bonjour, cette vidéo est SE|LV|09 et il s’agit d’un exemple étape par étape de l'algorithme de Thomas pour résoudre des matrices tridiagonales.
Tout d'abord, examinons le problème. Résolvez la matrice suivante en utilisant l'algorithme de Thomas. Il s'agit d'une matrice tridiagonale car nos seules valeurs se trouvent sur la diagonale principale et les diagonales supérieure et inférieure également. Le reste de la matrice est constitué de zéros. Ici, nous avons sept équations et sept inconnues. Cela semble assez grand, mais avec cet algorithme, on peut les résoudre assez rapidement.
La première étape consiste à convertir la matrice tridiagonale en matrices séparées. Nous avons donc la matrice [E] et nous avons la matrice [G]. Notez que chacune d'entre elles a un élément de moins, mais nous l'avons écrit avec des espaces vides pour qu'elle ait la même taille que les matrices [F] et [R]. Nous avons la matrice [F] et nous avons la matrice [R]. La première étape est la décomposition. Nous le faisons en passant de k = 2 jusqu’à n avec ces deux équations, ek = ek/fk-1, et fk = fk – ekgk-1. Commençons d’abord. Vous allez remarquer que ces étapes sont répétitives. Nous commençons par ek, qui sera 2 divisé par 4 et nous allons remplacer immédiatement cette valeur par la réponse, qui est 0.5. Ensuite, nous allons calculer fk = fk – ekgk-1 et nous remplacerons immédiatement cette valeur par la réponse, qui est 1. Puis nous descendrons dans les matrices et nous utiliserons les nouvelles valeurs au fur et à mesure qu’elles sont calculées. Ainsi, nous aurons e3 ici, qui sera égal à 3. Ensuite, nous ferons f3, où 4 devient -2. Puis nous avons e4, qui devient -0.5 et nous continuons à travailler jusqu'à ce que nous arrivions au bas des matrices. Ce que vous remarquerez également, c'est que lorsque nous utilisons les éléments de la matrice [G], nous ne changeons pas les valeurs au fur et à mesure des calculs. En fait, la matrice [G] ne change jamais. Ce sont seulement les matrices [E], [F] et [R] que nous allons utiliser. Nous calculerons les derniers éléments ici, qui sont e7 et f7, et nous avons fini de remplacer les matrices avec les nouvelles valeurs. Ceci est la fin de l'étape de décomposition.
La deuxième étape consiste à utiliser la substitution vers l’avant. Nous pouvons le faire pour k = 2 jusqu’à n en utilisant la formule suivante, rk = rk- ekrk-1. Pour la première équation, nous obtenons r2 = r2 - e2r1. Comme précédemment, nous allons continuer à mettre à jour les valeurs au fur et à mesure que nous descendons dans la matrice. Donc, le deuxième 32 devient 16 et nous descendons à r3, qui devient -5. Puis nous convertissons r4 de 49 à 41.5, 38 devient 23.565, 22 devient 85.764, et 15 devient 0.493. Ceci est la fin de l'étape de substitution vers l’avant.
Maintenant, nous allons faire l'étape finale, qui est la substitution vers l’arrière pour trouver nos valeurs de x. Nous allons faire cela d'abord avec xn = rn/fn. Dans ce cas, nous allons trouver x7 et x7 sera égal à 1. Ensuite, nous allons utiliser, pour k = n-1 jusqu’à 1, la formule xk = rk – gkxk+1 ,donc la valeur que nous venons de trouver, le tout divisé par fk. Si nous faisons cela, nous pouvons trouver que x6 = 7, x5 = 6, x4 = 1, x3 = 5, x2 = 6, et enfin x1 = 5. Nous venons donc de trouver les réponses à notre problème et nous avons terminé l'algorithme Thomas.
Ceci conclut la vidéo. Ce projet n'aurait pu être réalisé sans le soutien d'eCampusOntario et de l'Université d'Ottawa.