Regardez ces quatre (4) vidéos en ordre. La durée totale est de 23 minutes. N'oubliez pas de tester vos connaissances à l'aide des tests de connaissances après chaque vidéo.
Description: Cette vidéo présente les principes de la méthode itérative de Gauss-Seidel et discute également des techniques de relaxation pour aider la solution à converger.
Bonjour, cette vidéo est SE|LV|10 et il s'agit de la théorie de la méthode de Gauss-Seidel pour la résolution de systèmes d'équations.
Examinons d'abord la théorie. Contrairement aux méthodes que nous avons vues précédemment et qui utilisent des techniques d'élimination pour résoudre les valeurs x, la méthode de Gauss-Seidel utilise une approche itérative pour converger vers une solution finale. Vous supposez certaines valeurs de x, comme estimation initiale, et vous itérez jusqu'à ce que cette solution soit résolue. Nous commençons avec notre système d'équations sous forme d'équation et ce que nous pouvons faire ici, c'est réarranger chacune de ces équations de sorte que l'un des termes xi soit explicitement défini. Par exemple, x1 = b1 - a12x2, etc. et la deuxième équation sera exprimée en fonction de x2, et ainsi de suite. Maintenant que nous avons toutes nos équations de réarrangées, nous pouvons les résoudre. Premièrement, il faut supposez certaines valeurs de x comme estimation initiale et nous pouvons utiliser les équations pour commencer à itérer et espérer qu'elles convergent. On peut aussi tester la convergence avec la formule suivante, qui est une estimation de l'erreur εa,j où j est le numéro de l'équation. εa,j est égal à la valeur absolue de (xji-xji-1)/xji. Ce que vous voulez ici, c'est que l’erreur de toutes les équations se rapprochent de 0. Maintenant, comme il s'agit d'un processus itératif, il est possible que la solution diverge et que nous n'atteignions jamais la solution finale. Cela pourrait dépendre de vos suppositions initiales. Cependant, il y a une chance que le système converge. Cela se produit lorsque la magnitude des valeurs de la diagonale est supérieure à la somme de toutes les autres magnitudes des valeurs de cette rangée. C'est ce qu'on appelle un système diagonalement dominant. Dans ce cas, quels que soient les estimés initiales de x que vous utilisez, le système convergera. Dépendant des suppositions initiales, le processus peut prendre plus de temps pour converger, mais il convergera quand même. Heureusement, dans de nombreux problèmes d'ingénierie, le système est habituellement diagonalement dominant et peut aider à la convergence. Voici un exemple de système d'équations qui peut être réarrangé pour devenir diagonalement dominant. Les équations sont les suivantes: la première est x1 + 3x2 -4x3 + x4 = 2, la deuxième équation est 5x1 + 2x2- x3 - x4 = 3, la troisième équation est 3x1 + 3x2 - 2x3 - 6x4 = 1, et la dernière équation est 2x1 +4x2 - x3 +2x4 = 5. Maintenant, si nous prenons les équations et on les réarrange en fonction de x1, de x2, etc., notre solution divergerait probablement, à moins que notre estimé initiale est très proches de la réponse réelle. Cependant, si nous regardons les équations, nous pouvons essayer de les réarranger pour qu'elles soient aussi diagonalement dominantes que possible. Donc, ce que nous avons fait ici, c'est que nous avons déplacé la rangée rouge vers le haut, qui commence avec 5x1, pour être la première rangée parce que 5 est plus grand que les autres coefficients dans cette première rangée. Donc, 5 est plus grand que 2 + 1 + 1. Nous faisons la même chose pour les autres rangées, donc la rangée suivante serait verte et nous continuons ainsi pour que les équations soient aussi diagonalement dominantes que possible. Maintenant, avec de bonne estimés initiales, on peut converger vers les réponses.
La méthode de Gauss-Seidel présente certains avantages. Premièrement, il est en fait très utile pour résoudre de grands systèmes d'équations où la matrice est une matrice creuse. Qu'est-ce qu'une matrice creuse? Une matrice creuse est une matrice où de nombreux coefficients de la matrice sont essentiellement égales à 0. Cela signifie que vous pouvez avoir beaucoup d'équations, mais qu'elles ne sont pas toutes liées les unes aux autres, ce qui est bon. Deuxièmement, comme mentionné précédemment, les matrices diagonalement dominantes peuvent converger très facilement et cela se produit dans de nombreux problèmes d'ingénierie. Troisièmement, l'erreur d'arrondissement qui se produit dans les étapes d'élimination est en fait évitée car nous continuons toujours à itérer pour trouver une meilleure solution. Finalement, cette méthode est très efficace pour les grands systèmes sans avoir beaucoup de contraintes de mémoire si vous le résolvez avec un ordinateur, parce qu’avec le process itératif, vous ne tenez compte qu’un ensemble de valeurs. Par exemple, si vous avez une centaine d'équations, vous n'avez besoin de stocker qu'une centaine de valeurs. Par contre, si vous résolvez le system en format matriciel, vous auriez besoin d'une matrice complète, c'est-à-dire de 100 par 100 ou 10 000 valeurs, et cela peut s'accumuler assez rapidement en termes de contraintes de mémoire.
Examinons 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 méthode Gauss-Seidel dans un problème de pratique, selon une approche étape par étape.
Bonjour, cette vidéo est SE|LV|11 et il s’agit d’un exemple étape par étape de l'utilisation de la méthode de Gauss-Seidel pour résoudre des systèmes d'équations.
Examinons le problème. Résolvez les équations suivantes à l'aide de la méthode de Gauss-Seidel en vous basant sur l'estimation initiale x2 = x3 = 5. Nous avons trois équations. La première équation est 5.6x1 + 3.3x2 +2x3 = 68.98. La deuxième équation est 1.2x1 + 4.2x2 + 2.3x3 = 58.22. L'équation finale est 4.1x1 + 1.8x2 + 6.2x3 = 90.46. Avant de commencer, nous pouvons examiner ces équations et nous remarquerons qu'elles sont en fait déjà définies pour être diagonalement dominantes. C'est-à-dire que 5.6 est supérieur à 3.3 + 2, 4.2 dans la deuxième équation est supérieur à 1.2 + 2.3, et 6.2 est supérieur à 4.1 + 1.8. Donc le système est définitivement diagonalement dominant, ce qui signifie que n’importe quelles valeurs que nous choisissons comme estimation initiales devrait converger. Puisque ce système d'équations est déjà diagonalement dominant, nous pouvons réarranger l'équation 1 en fonction de x1, l'équation 2 en fonction de x2, et l'équation 3 en fonction de x3. Nous avons x1 = (68.98 – 3.3x2 - 2x3)/5.6, x2 = (58.22 -1.2x1 -2.3x3)/4.2, et enfin, nous avons x3 = (90.46 - 4.1x1 -1.8x2)/6.2.
Maintenant que nous avons les équations, nous pouvons établir un tableau itératif contenant six colonnes pour cet exemple. Nous avons la colonne i, x1, x2, x3, εa1, εa2 et εa3, qui représentent l'estimation de l'erreur pour chacune de ces fonctions. À l'itération i = 0, nous supposerons que x2 et x3 sont égales à 5, conformément à l'énoncé du problème et nous n'avons pas besoin d'une estimation initiale pour x1. Pour l'itération 1, nous allons commencer avec l'équation de x1, et nous allons trouver une estimation de x1 en utilisant nos estimations initiales de x2 et x3. Ensuite, nous allons passer à x2 et dans ce cas, nous utiliserons toujours cette estimation initiale de x3 = 5, mais nous utiliserons l'estimation de x1 qui vient d'être calculée. Enfin, nous calculerons x3, et nous utiliserons toutes les nouvelles valeurs que nous avons obtenues pour cette itération, donc x1 = 7.59 et x2 = 8.96. Nous passons à l'itération suivante. On recommence en calculant x1 mais on utilise les nouvelles valeurs de x2 et x3. Nous pouvons calculer x2 de la même manière et ensuite calculer x3. Dans ce cas, nous pouvons maintenant estimer l'erreur approximative pour chaque fonction et vous remarquerez l’erreur est encore élevée avec εa1 qui est 66.7%. Donc, nous devons continuer à itérer. Nous allons trouver nos prochaines valeurs pour l'étape 3 et remarquer que l'erreur diminue lentement. Et nous continuons à parcourir nos itérations en observant les erreurs qui deviennent de plus en plus petites; ce qui est bien. Maintenant, les valeurs commencent à converger un peu et donc x1 converge vers 4, x2converge vers 7, et x3 converge vers 9. Une fois que nous arrivons à notre 10e itération, vous remarquerez que les réponses ont convergées à deux décimales près, x1 est proche de 4.60, x2 est proche de 7.40 et x3 est proche de 9.40. Si vous regardez les estimations de l'erreur, elles sont toutes très proches de 0 % à une décimale près. Nous pouvons donc conclure que la réponse a convergée vers ces valeurs x1 = 4.6, x2 = 7.4 and x3 = 9.4 et nous avons résolu le problème.
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 ce qu’est un système d’équations non linéaire et en quoi il diffère des systèmes d’équations linéaires. La méthode de Newton-Raphson pour résoudre des systèmes d’équations non linéaires est introduite.
Bonjour, cette vidéo est SE|LV|12 et il s’agit de la théorie de la méthode de Newton-Raphson pour la résolution de systèmes d'équations non linéaires.
Examinons la théorie générale de la méthode de Newton-Raphson. Tout d'abord, nous allons discuter de la différence entre un système d'équations linéaires et un système d'équations non linéaires. Dans un système d'équations linéaires, toutes les inconnues, x1, x2 et x3, dans ce cas, sont séparées les unes des autres dans des termes indépendants. Par contre, dans un système d'équations non linéaires, on ne peut peut pas séparer x1, x2 et x3, par exemple pour mettre dans une matrice car ils sont contenue dans les mêmes termes - parfois multipliés ensemble ou dans des fonctions différentes. Ces systèmes sont donc non linéaires et nous ne pouvons pas utiliser les méthodes que nous avons déjà vue. Pour résoudre ce problème, nous devrons manipuler les équations d’une certaine façon et itérer. Ce que nous pouvons faire, c'est commencer avec l'expansion de la série de Taylor généralisée des fonctions f. Nous pouvons exprimer une combinaison de la série avec la formule suivante. La somme de j = 1 jusqu’à n de la dérivée partielle, qui est ∂fk,i/∂xj *(xj,i+1 – xj,i), est égale à -fk,i. Dans ce cas-ci, k représente les différentes fonctions que vous avez, c’est-à-dire chaque équation séparée. Donc si vous avez trois équations, k varie de 1 à 3. j représente le nombre d'inconnues qui varie également de 1 à 3, puisque nous aurons toujours besoin du même nombre d’équations et d’inconnues. Et i représente les itérations que nous avons.
Cela peut également prendre la forme d'une matrice, c'est-à-dire la matrice [J], qui représente la matrice Jacobienne, fois la matrice de [∆X] est égale à la matrice de [-F]. Si nous développons cela, nous obtenons ici les dérivées partielles de chacune des fonctions, que l'on appelle à nouveau la matrice Jacobienne, fois certaines valeurs ∆xj pour chacun des x que nous avons, et elle est égale aux négatifs des fonctions f que nous avons précédemment. Dans ce cas ici, les fonctions f devraient être égale à 0, comme que nous avons fait pour la résolution des équations non linéaires. Le ∆x1, ∆x2, etc., représente en fait le changement de x entre une itération et la suivante. Ce que nous pouvons faire ici pour résoudre le problème, c'est de supposer une estimation initiale pour nos x, calculer toutes les dérivées partielles pour la matrice jacobienne, et calculer tous les valeurs -f1, -f2 en utilisant les mêmes valeurs de notre estimation initiale. Ce que nous avons, c'est un système qui se comporte comme un système linéaire normal. Nous pouvons le résoudre en utilisant des méthodes que nous avons déjà vues auparavant, y compris l'élimination de Gauss, la décomposition LU et la méthode de Gauss-Seidel. Nous allons donc résoudre pour tous les valeurs de ∆x et ensuite isoler pour les nouvelles valeurs de x.
Voici l'algorithme de la méthode de Newton-Raphson.
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 méthode de Newton-Raphson dans un problème pratique, selon une approche étape par étape.
Bonjour, cette vidéo est SE|LV|13 et il s’agit d’un un exemple étape par étape de l'utilisation de la méthode de Newton-Raphson pour résoudre un système d'équations non linéaires.
Tout d'abord, examinons le problème. Résolvez les équations suivantes à l'aide de la méthode de Newton-Raphson avec les valeurs initiales de x1 = 0.5, x2 = 2 et x3 = 1. Les trois équations sont les suivantes. Pour la première équation, x12x3 + 2x22 = 13. La deuxième équation est x1x2x3 – x12x33 = 1.125. Et la troisième équation est 4x1x2 + 2x1x3 = 11. La première étape consiste à réorganiser les équations de façon à ce qu'un côté soit égal à 0, et ce seront nos fonctions f. Par exemple, f1 = x12x3 + 2x22 – 13, qui sera égale à 0. f2 = x1x2x3 – x12x33 - 1.125, qui sera égale à 0. Et enfin, l'équation finale, f3 = 4x1x2 + 2x1x3 - 11, qui est aussi égale à 0. Rappelez-vous que pour la méthode de Newton-Raphson, nous devons calculer la matrice Jacobienne ainsi que la matrice [-F] pour pouvoir résoudre ce problème. La matrice Jacobienne est l'ensemble des dérivées partielles par rapport à chaque variable pour chacune des fonctions et la matrice [-F] est assez simple: il suffit de prendre le négatif des valeurs f que nous avons calculés précédemment. Regardons maintenant les dérivées partielles de f1, ∂f1/∂x1= 2x1x3, ∂f1/∂x2 = 4x2 et ∂f1/∂x3 = x12. Ensuite, pour f2, ∂f2/∂x1 = x2x3+2x1x33, ∂f2/∂x2 = x1x3, ∂f2/∂x3 = x1x2 – 3x12x32. Enfin, pour la troisième équation, ∂f3/∂x1 = 4x2 + 2x3, ∂f3/∂x2 = 4x1, ∂f3/∂x3 = 2x1. Ce sont donc les valeurs que nous pouvons utiliser pour calculer notre matrice Jacobienne. Maintenant que nous avons notre matrice Jacobienne et nos valeurs de -F, nous avons un système matricielle ressemblant à ceci, et nous pouvons y insérer nos premières estimations de x1, x2 et x3. Ce que vous remarquerez c'est que nous obtenons un système d'équations que nous pouvons résoudre pour ∆x1, ∆x2, et ∆x3. Dans ce cas, nous aurons les rangées 1, 8, 0.25, 1, 0.5, 0.75, et 10, 2, 1; et ceci fois la matrice ∆x sera égal à 4.75, 0.375 et 6. Une fois que nous avons trouvé nos valeurs de ∆x, nous pouvons mettre à jour nos estimations de x pour les itérations en trouvant xj,i+1. Par après, on peut revenir dans les formules, remplacer nos nouvelles valeurs de x et résoudre à nouveau. Pour faciliter les calculs, nous allons utiliser un tableau incluant nos valeurs initiales des xj, c'est-à-dire 0.5, 2 et 1. Nous utilisons cela pour calculer les valeurs de [-F] ainsi que la matrice Jacobienne, et nous pouvons utiliser n'importe quelle méthode pour résoudre ce système matriciel, par exemple, l’élimination de Gauss pour trouver nos valeurs de ∆xj. Donc, cela représente le changement des valeurs que nous avons. Nous pouvons en fait déterminer une estimation de l'erreur et il y a encore un peu d'erreur associée avec les valeurs à cette itération. Nous allons donc passer à notre deuxième itération. Ce que nous allons faire ici est de mettre à jour notre colonne xjavec la formule xj,i+1 = xj,i + ∆xj que nous avons ici. Nous allons donc calculer ici 0.5 + 0.516, 2 + 0.53 et 1 – 0.234. Vous verrez que ce sont de nouvelles valeurs et avec ces nouvelles valeurs, nous pouvons calculer notre matrice Jacobienne et les valeurs pour les fonctions [-F] et nous pouvons continuer pour obtenir également nos changements ∆xj. Les itérations vont continuer jusqu'à ce que notre changement ∆xj diminue. En appliquant la même formule pour l'itération suivante où i = 3, on obtient des valeurs qui sont un peu plus proches. On calcule par après la matrice Jacobienne et la matrice [-F] et on obtient de nouvelles valeurs. Encore une fois, vous remarquerez que notre estimation de l'erreur diminue de manière significative pour les équations 1 et 2, qui sont 0.9 % et 0.2 %, mais que l’erreur pour l'équation 3 est encore assez élevée, à 10 %. Nous allons donc continuer à travers nos itérations en appliquant les mêmes étapes. L’erreur ici est en train de diminuer lentement. Nous pouvons faire notre itération numéro 5 de la même manière, pour obtenir une erreur de 6.4%, notre itération 6 pour obtenir une erreur de 4%, notre itération 7, pour obtenir une erreur de 2.3%, notre itération 8, pour obtenir 1.2%, avec les deux autres erreurs étant pratiquement nulles et notre itération 9, où l’erreur descend à 0.6%. Nous allons donc faire une dernière itération. À l’itération 10, nous pouvons observer la convergence dans nos réponses avec des erreurs très petites. Donc après 10 itérations, nos réponses finales sont, x1 = 1, x2 = 2.5, et x3 = 0.5.
Ceci conclut la vidéo. Ce projet n'aurait pu être réalisé sans le soutien d'eCampusOntario et de l'Université d'Ottawa.