diff --git "a/Chapitre 1 - Systemes equations lineaires/1.5-6. Matrices Echelonn\303\251es.ipynb" "b/Chapitre 1 - Systemes equations lineaires/1.5-6. Matrices Echelonn\303\251es.ipynb" new file mode 100644 index 0000000..5f53264 --- /dev/null +++ "b/Chapitre 1 - Systemes equations lineaires/1.5-6. Matrices Echelonn\303\251es.ipynb" @@ -0,0 +1,392 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Concept(s)-clé(s) \n", + "\n", + "DEFINITION 1\n", + "\n", + "Soit $A$ une matrice de taille $m\\times n$ à coefficients réels. On dit que $A$ est *échelonnée* si l'indice de colonne du premier élément non-nul de chaque ligne est supérieur à l'indice de colonne du premier élément non-nul de la ligne précédente. C'est à dire que le nombre de zéros pécédant le premier élément non-nul une ligne augmente ligne par ligne, jusqu'à obtenir peut-être des lignes ne contenant que des zéros.\n", + "\n", + "Le premier élément non-nul de chaque ligne s'appelle un *pivot*, on les dénote par $\\color{red}\\oplus$. Les éléments quelconques sont dénotés par $*$. Attention $\\color{red}\\oplus$ est un élément non-nul, alors que $*$ peut être un élément nul. Les colonnes possédant un pivots s'appellent des *colonnes pivots*.\n", + "\n", + "Voici un exemple d'une telle matrice $A$ (ici de taille $7\\times 9$). Les colonnes $1,3,4,6$ et $9$ sont des colonnes pivots.\n", + "\n", + "$\n", + "A=\\begin{pmatrix}\n", + "\\color{red}\\oplus & * & * & * & * & * & * &* & * \\\\\n", + "0 & 0 &\\color{red}\\oplus & *& * & * & * & *&* \\\\\n", + "0 & 0 & 0 & \\color{red}\\oplus& *& * &* & *& *\\\\\n", + "0 & 0 & 0 & 0 & 0 &\\color{red}\\oplus & * & * & *\\\\\n", + "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\\color{red}\\oplus\\\\\n", + "0 & 0 & 0 & 0 & 0& 0 & 0 &0&0\\\\\n", + "0 & 0 & 0 & 0 & 0& 0 & 0 &0&0\n", + "\\end{pmatrix}\n", + "$\n", + "\n", + "DEFINITON 2\n", + "\n", + "Soit $A$ une matrice de taille $m\\times n$ à coefficients réels. On dit que $A$ est *échelonnée réduite* si $A$ est échelonnée avec les propriétés suivantes\n", + "1. tous ses pivots valent $1$ ($\\color{red}\\oplus=1$ dans ce cas)\n", + "2. les pivots sont les seules valeurs non-nulles de leur colonne pivot (en dessous et en dessous d'un pivot il n'y a que des zéros).\n", + "\n", + "Voici un exemple d'une telle matrice $A$ (ici de taille $7\\times 9$). Les colonnes $1,3,4,6$ et $9$ sont des colonnes pivots et ne contiennent qu'un seul élément non-nul (les pivots valant 1).\n", + "\n", + "$\n", + "A=\\begin{pmatrix}\n", + "\\require{enclose}\\enclose{circle}[mathcolor=\"red\"]{1} & * & 0 & 0 & * & 0 & * &* &0 \\\\\n", + "0 & 0 &\\require{enclose}\\enclose{circle}[mathcolor=\"red\"]{1} &0& * & 0 & * & *&0 \\\\\n", + "0 & 0 & 0 &\\require{enclose}\\enclose{circle}[mathcolor=\"red\"]{1}& *& 0 &* & *& 0\\\\\n", + "0 & 0 & 0 & 0 & 0 &\\require{enclose}\\enclose{circle}[mathcolor=\"red\"]{1} & * & * & 0\\\\\n", + "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\\require{enclose}\\enclose{circle}[mathcolor=\"red\"]{1}\\\\\n", + "0 & 0 & 0 & 0 & 0& 0 & 0 &0&0\\\\\n", + "0 & 0 & 0 & 0 & 0& 0 & 0 &0&0\n", + "\\end{pmatrix}\n", + "$\n" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### **EXERCICE 1**\n", + "Parmi les matrices ci-dessous, indiquez lesquelles sont sous formes échelonnées et échelonnées réduites.\n", + "\n", + "$\n", + "A=\\begin{pmatrix}\n", + "1 & 0 & 0 &1\\\\\n", + "0 & 1 & 1 & 0\\\\\n", + "0 & 1 & 0 & 3\\\\\n", + "0 & 0 & 1 & 0\n", + "\\end{pmatrix}\\hspace{1cm}\n", + "B=\\begin{pmatrix}1&1& 0 & 0 & 1\\\\\n", + " 0& 0 &1 &0 &1\\\\\n", + " 0 & 0& 0& 0& 0\\\\\n", + " 0 & 0 & 0 & 1 & 0\n", + "\\end{pmatrix}\\hspace{1cm}\n", + "C=\\begin{pmatrix}\n", + "1& 0 & 0 & 2\\\\\n", + "0 & 1 & 0 & -2\\\\\n", + "0 & 0 & -1 & 0 \\\\\n", + "0 & 0 & 0 & 0\n", + "\\end{pmatrix}\n", + "\\hspace{1cm}\n", + "D=\\begin{pmatrix}\n", + "0 & 1 & 1 & 0 & 0 & 1\\\\\n", + "0 & 0 & 0 & 1 & 0 & 1\\\\\n", + "0 &0 &0 &0 &1 & 1\n", + "\\end{pmatrix}\n", + "\\hspace{1cm}\n", + "E=\\begin{pmatrix}1 & 1 & 0 \\\\\n", + "0 & 2 &0 &-3\\\\\n", + "0 & 0 & 3& 1\\\\\n", + "0 & 0 & 0 &0\n", + "\\end{pmatrix}\\\\\n", + "F=\\begin{pmatrix}\n", + "1\\\\\n", + "0\\\\\n", + "1\n", + "\\end{pmatrix}\\hspace{1cm}\n", + "G=\\begin{pmatrix}0 & 0 \\\\\n", + "0 & 4\n", + "\\end{pmatrix}\\hspace{1cm}\n", + "H=\\begin{pmatrix}\n", + "0 & 0 \\\\\n", + "0 & 0\n", + "\\end{pmatrix}\\hspace{1cm}\n", + "I=\\begin{pmatrix}1\\end{pmatrix}\\hspace{1cm} \n", + "J=\\begin{pmatrix}\n", + "1 & 0 & 1\\end{pmatrix}\n", + "$" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Théorie\n", + "\n", + "\n", + "La **méthode d'élimination de Gauss** est un algorithme central en algèbre linéaire qui consiste à appliquer une séquence appropriée d'opérations élémentaires à une matrice (voir [Notebook du chapitre 1.3-4: Notation Matricielle](./1.3-4.%20Notation%20Matricielle.ipynb)) jusqu'à ce qu'elle soit échelonnée. On peut continuer à appliquer des opérations élémentaires pour obtenir une matrice échelonnée réduite. \n", + "\n", + "\n", + "La structure de la méthode d'élimination de Gauss est la suivante:\n", + "![title](gauss_elimination.png)\n", + "\n", + "Soit le système linéaire suivant $$A\\overrightarrow{x} = \\overrightarrow{b}$$ où $A$ est la matrice des coefficients de taille $m\\times n$ et $\\overrightarrow{b}$ est le vecteur regrouppant les termes de droite.\n", + "En appliquant la méthode d'élimination de Gauss à la matrice augmentée $(A|b)$ on obtient:\n", + "\\begin{align*}\n", + "\\text{Système Original} \\quad (A|b) \\quad & \\Leftrightarrow \\quad \\text{Système Échelonné} \\quad (\\tilde{A}|\\tilde{b}) \\quad & \\Leftrightarrow \\quad \\text{Système Réduit} \\quad (\\hat{A}|\\hat{b})\\\\\n", + "\\left(\\begin{array}{cccc|c}\n", + "a_{11} & a_{12} & \\dots & a_{1n} & b_1\\\\\n", + "a_{21} & a_{22} & \\dots & a_{2n} & b_2\\\\\n", + "\\vdots & \\vdots & \\ddots & \\vdots & \\vdots \\\\\n", + "a_{m1} & a_{m2} & \\dots & a_{mn} & b_m\n", + "\\end{array}\\right) \\quad & \\Leftrightarrow \\quad \\left(\\begin{array}{cccc|c}\n", + "\\tilde{a}_{11} & \\tilde{a}_{12} & \\dots & \\tilde{a}_{1n} & \\tilde{b}_1\\\\\n", + "0 & \\tilde{a}_{22} & \\dots & \\tilde{a}_{2n} & \\tilde{b}_2\\\\\n", + "\\vdots & \\vdots & \\ddots & \\vdots & \\vdots \\\\\n", + "0 & 0 & \\dots & \\tilde{a}_{mn} & \\tilde{b}_m\n", + "\\end{array}\\right) \\quad & \\Leftrightarrow \\quad \\left(\\begin{array}{cccc|c}\n", + "1 & 0 & \\dots & 0 & \\hat{b}_1\\\\\n", + "0 & 1 & \\dots & 0 & \\hat{b}_2\\\\\n", + "\\vdots & \\vdots & \\ddots & \\vdots & \\vdots \\\\\n", + "0 & 0 & \\dots & 1 & \\hat{b}_m\n", + "\\end{array}\\right)\\\\\n", + "\\end{align*}\n", + "\n", + "**Remarque** Il s'agit d'un exemple, les pivots pouvant êtres à d'autres emplacements. Des lignes de zéros peuvent aussi êtres présentes.\n", + "\n", + "\n", + "Comme seules des opérations élémentaires sur les lignes ont été utilisées, le système linéaire résultant est équivalent au système d'origine. Leur ensemble de solutions sont donc les mêmes. Mais le système resultant est beaucoup plus facile et plus rapide à résoudre. En utilisant d'abord la dernière équation, puis en substituant progressivement les variables dans les équations précédantes.\n" + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + " \n", + " " + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "import Librairie.AL_Fct as al\n", + "import numpy as np\n", + "import ipywidgets as widgets\n", + "import random\n", + "\n", + "from ipywidgets import interact, interactive, fixed, interact_manual" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### **Exercice 1**\n", + "\n", + "À l'aide des opérations élémentaires, échelonner et réduire les matrices ci-dessous.\n", + "\n", + "$$\n", + "\\begin{pmatrix}\n", + "2 & -1\\\\\n", + "1 &2\n", + "\\end{pmatrix}\\hskip2em\n", + "\\begin{pmatrix}\n", + "\\dfrac{1}{2} & 3 & 0\\\\\n", + "2 & -4 & 6\\\\\n", + "1 & 3 &-1\n", + "\\end{pmatrix}\\hskip2em\n", + "\\begin{pmatrix}\n", + "1 & 0 &1\\\\\n", + "0 & 1 & -1\\\\\n", + "1 & 1 &-1\n", + "\\end{pmatrix}\n", + "\\hskip2em\n", + "\\begin{pmatrix}\n", + "1 & 0 &1 & 3\\\\\n", + "0 & 2 & -2&1\\\\\n", + "1 & 1 &-1 & 0\n", + "\\end{pmatrix}\n", + "$$\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [ + "A=[[1,1], [1,1], [1,1]]" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [ + "print('Vous allez échelonner la matrice')\n", + "al.printA(A)\n", + "[i,j,r,alpha]= al.manualEch(A)\n", + "MatriceList=[np.array(A)]\n", + "m=np.array(A)\n", + "print('\\033[1mExecutez la ligne suivante pour effectuer l\\'opération choisie \\033[0m')" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [ + "m=al.echelonnage(i, j, r, alpha, A, m, MatriceList)" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### **Exercice 2**\n", + "\n", + "À l'aide des opérations élémentaires, échelonner et réduire les matrices (augmentées) ci-dessous.\n", + "\n", + "$$A=\n", + "\\begin{pmatrix}\n", + "2 & -1\\\\\n", + "1 &2\n", + "\\end{pmatrix}\\hskip1em\n", + "b=\n", + "\\begin{pmatrix}\n", + "1\\\\\n", + "2\n", + "\\end{pmatrix}\\hskip4em\n", + "A=\n", + "\\begin{pmatrix}\n", + "\\dfrac{1}{2} & 3 & 0\\\\\n", + "2 & -4 & 6\\\\\n", + "1 & 3 &-1\n", + "\\end{pmatrix}\\hskip1em\n", + "b=\n", + "\\begin{pmatrix}\n", + "1\\\\\n", + "2\\\\\n", + "-1\n", + "\\end{pmatrix}\\hskip4em\n", + "A=\n", + "\\begin{pmatrix}\n", + "1 & 0 &1\\\\\n", + "0 & 1 & -1\\\\\n", + "1 & 1 &-1\n", + "\\end{pmatrix}\\hskip1em\n", + "b=\n", + "\\begin{pmatrix}\n", + "1\\\\\n", + "0\\\\\n", + "-1\n", + "\\end{pmatrix}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [ + "A=[[1,1,1], [1,1,1],[1,1,1]]\n", + "b =[[1], [1], [1]]" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [ + "print('Vous allez échelonner la matrice augmenteé')\n", + "al.printAAug(A,b)\n", + "[i,j,r,alpha]= al.manualEch(A)\n", + "MatriceList=[np.array(A)]\n", + "RHSList = [np.array(b)]\n", + "m=np.concatenate((A,b), axis=1)\n", + "print('\\033[1mExecutez la ligne suivante pour effectuer l\\'opération choisie \\033[0m')" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [ + "m=al.echelonnage(i, j, r, alpha, A, m, MatriceList, RHSList)" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### **VERIFICATION**\n", + "À l'aide des cellules ci-dessous, vous pouvez entrer la matrice (des coefficients ou augmentée) de votre choix et obtenir une forme échelonnée et sa forme échelonnée réduite.\n", + "\n", + "Pour **les formes échelonnées** on utilise la syntaxe suivante\n", + "\n", + "1. Pour la matrice $A$ : al.echelonMat('E', A)\n", + "2. Pour la matrice augmentée $(A | b)$ : al.echelonMat('E', A, b)\n", + "\n", + "Pour obenir **les formes échelonnées réduites** mettez 'ER' au lieu de 'E'" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [ + "A=[[2,1,1], [1,-1,1], [1,4,5]]\n", + "b=[[1], [3], [1]]" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [ + "M=al.echelonMat('ER',A,b)" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "[Passez au notebook du chapitre 1.7: Résolutions de système linéarires](./1.7.%20Résolutions%20de%20systèmes%20linéaires.ipynb)" + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Python 3", + "language": "python", + "name": "python3" + }, + "language_info": { + "codemirror_mode": { + "name": "ipython", + "version": 3 + }, + "file_extension": ".py", + "mimetype": "text/x-python", + "name": "python", + "nbconvert_exporter": "python", + "pygments_lexer": "ipython3", + "version": "3.6.9" + } + }, + "nbformat": 4, + "nbformat_minor": 4 +}