diff --git "a/Chapitre 9 - Produits scalaires et espaces euclidens/9.12 Solution au sens du moindres carr\303\251es.ipynb" "b/Chapitre 9 - Produits scalaires et espaces euclidens/9.12 Solution au sens du moindres carr\303\251es.ipynb" index 6d1fe02..061ed98 100644 --- "a/Chapitre 9 - Produits scalaires et espaces euclidens/9.12 Solution au sens du moindres carr\303\251es.ipynb" +++ "b/Chapitre 9 - Produits scalaires et espaces euclidens/9.12 Solution au sens du moindres carr\303\251es.ipynb" @@ -1,407 +1,407 @@ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# **Concept(s)-clé(s) et théorie**\n", "\n", "## Définition 1\n", "Soient $A \\in \\mathcal{M}_{m \\times n}(\\mathbb{R})$, $b \\in \\mathcal{M}_{m \\times 1}(\\mathbb{R})$ et $X = \\left(x_1, \\dots, x_n\\right)^T$. Aussi, désignons par $\\phi: \\mathbb{R}^n \\rightarrow \\mathbb{R}^m$ l'application linéaire associée à $A$. Une **solution du système $\\boldsymbol{AX=b}$ au sens du moindres carrées** est une solution du systeme\n", "\n", "\\begin{equation}\n", "AX = proj_{Im(\\phi)}b\n", "\\end{equation}\n", "\n", "## Théorème 1\n", "Soient $A \\in \\mathcal{M}_{m \\times n}(\\mathbb{R})$, $b \\in \\mathcal{M}_{m \\times 1}(\\mathbb{R})$ et $X = \\left(x_1, \\dots, x_n\\right)^T$. Alors une solution du système $AX=b$ au sens du moindres carrées est une solution du système $A^TAX = A^Tb$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exercises et Examples" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import Librairie.AL_Fct as al\n", "import Corrections.corrections as corrections\n", "import numpy as np\n", "import sympy as sp" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 1\n", "\n", "Considérez les systèmes linéaires suivants, avec forme $Ax=b$. Calculez leur solution au sens des moindres carrés en projetant $b$ sur l'espace image de $A$ et en résolvant $Ax = proj_{Im(A)}b$.\n", "\n", "1. $\\quad A = \\begin{pmatrix}1 & 0 \\\\ 1 & 0\\end{pmatrix} \\qquad \\qquad b = \\begin{pmatrix}1 \\\\ 3\\end{pmatrix}$\n", "2. $\\quad A = \\begin{pmatrix}1 & 1 \\\\ 1 & -1 \\\\ 2 & 0\\end{pmatrix} \\qquad \\qquad b = \\begin{pmatrix}1 \\\\ 2 \\\\ -2\\end{pmatrix}$\n", "3. $\\quad A = \\begin{pmatrix}1 & 0 & 0\\\\ 0 & 1 & 1 \\\\ 1 & 0 & 0\\end{pmatrix} \\qquad \\quad \\ \\ b = \\begin{pmatrix}-1 \\\\ 2 \\\\ 1\\end{pmatrix}$\n", "4. $\\quad A = \\begin{pmatrix}1 & 0 & 1\\\\ -1 & 1 & -1 \\\\ 0 & 1 & 1 \\\\ 1 & 1 & 0 \\\\ -1 & 0 & 1\\end{pmatrix} \\qquad \\ \\ b = \\begin{pmatrix}0 \\\\ 2 \\\\ 0 \\\\ 1 \\\\ 4\\end{pmatrix}$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ - "case_number = 3 # CHOISISSEZ LE NUMÉRO DE CAS ICI ET EXECUTEZ LA CELLULE SUIVANTE!" + "case_number = 1 # CHOISISSEZ LE NUMÉRO DE CAS ICI ET EXECUTEZ LA CELLULE SUIVANTE!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "if case_number == 1:\n", " A_cols = [[1,1], [0,0]]\n", " A = np.array(A_cols).T\n", " b = [1,3]\n", " dim=2\n", "elif case_number == 2:\n", " A_cols = [[1,1,2], [1,-1,0]]\n", " A = np.array(A_cols).T\n", " b = [1,2,-2]\n", " dim=2\n", "elif case_number == 3:\n", " A_cols = [[1,0,1], [0,1,0], [0,1,0]]\n", " A = np.array(A_cols).T\n", " b = [-1,2,1]\n", " dim=3\n", "elif case_number == 4:\n", " A_cols = [[1,-1,0,1,-1], [0,1,1,1,0], [1,-1,1,0,1]]\n", " A = np.array(A_cols).T\n", " b = [0,2,0,1,4]\n", " dim=3\n", "else:\n", " print(f\"{case_number} n'est pas un numéro de cas valide!\" \n", " f\"Numéros de cas disponibles: [1,2,3,4]\")\n", "\n", "step = 0\n", "VectorsList = [A_cols]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Aide\n", "\n", "Pour calculer la projection orthogonal de $b$ sur $Im(A)$, il peut être utile de dériver une base ortogonale (ou orthonormée) pour ce dernier. Vous pouvez utiliser la cellule suivante pour exécuter l'algorithme interactif de Gram-Schmidt.\n", "\n", "#### Instructions\n", "\n", "Pour utiliser la méthode interactive de Gram-Schmidt, procédez comme suit:\n", "\n", "1. Insérez le numéro de dossier souhaité dans la cellule suivante\n", "2. Exécutez la cellule appelée \"SÉLECTION DES PARAMÈTRES\" pour sélectionner le type d'opération et les coefficients nécessaires\n", "3. Exécutez la cellule appelée \"EXÉCUTER L'ÉTAPE DE L'ALGORITHME GRAM-SCHMIDT\" pour exécuter l'étape de l'algorithme de Gram-Schmidt avec les paramètres précédemment sélectionnés\n", "\n", "En outre:\n", "\n", "1. Vous pouvez annuler une opération en sélectionnant le bouton \"Revert\".\n", "\n", "2. Si les coefficients insérés sont incorrects, vous pouvez essayer avec de nouvelles valeurs sans effectuer une opération \"Revert\".\n", "\n", "3. Les coefficients qui ne sont pas liés à l'opération sélectionnée peuvent être définis sur n'importe quelle valeur, car ils ne sont pas utilisés dans le code." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# SÉLECTION DES PARAMÈTRES\n", "print(f\"Current vectors: {A_cols}\")\n", "norm_coeff, proj_coeffs, operation, step_number = al.manual_GS(dim=dim)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# EXÉCUTER L'ÉTAPE DE L'ALGORITHME GRAM-SCHMIDT\n", "A_cols = al.interactive_gram_schmidt(norm_coeff, proj_coeffs,\n", " operation, step_number, \n", " A_cols.copy(), VectorsList)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Aide\n", "\n", "Pour résoudre le système linéaire, vous pouvez tirer parti des cellules interactives suivantes qui permettent d'appliquer la méthode d'élimitation de Gauss. Notez que vous devez **entrer la valeur trouvée pour la projection de $\\boldsymbol{b}$ sur l'espace image de $\\boldsymbol{A}$ dans la première ligne!**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "proj_b = [[0], [2], [0]] # INSEREZ ICI LA VALEUR TROUVÉE POUR LA PROJECTION DE b SUR Im (A)\n", "al.printA(A, proj_b)\n", "[i,j,r,alpha]= al.manualEch(A,proj_b)\n", "m=np.concatenate((A,proj_b), axis=1)\n", "MatriceList=[A]\n", "RhSList=[proj_b]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "m=al.echelonnage(i,j,r,alpha,A,m,MatriceList,RhSList)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# INSEREZ ICI LA SOLUTION\n", "x,y,z = sp.symbols('x, y, z')\n", "sol = sp.sets.FiniteSet((0,y,2-y))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# ÉVALUATION DE LA SOLUTION\n", "corrections.Ex1_Chapitre9_12(sol, case_nb=case_number)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 2\n", "\n", "Considérez les systèmes linéaires suivants, avec forme $Ax = b$. Calculez leur solution au sens des moindres carrés en résolvant le système linéaire $A^TAx=A^Tb$.\n", "\n", "1. $\\quad A = \\begin{pmatrix}0 & 1 \\\\ 0 & -1\\end{pmatrix} \\qquad \\qquad b = \\begin{pmatrix}0 \\\\ 2\\end{pmatrix}$\n", "2. $\\quad A = \\begin{pmatrix}0 & 1 \\\\ 1 & 1 \\\\ 1 & -2\\end{pmatrix} \\qquad \\qquad \\ \\ b = \\begin{pmatrix}1 \\\\ 1 \\\\ 0\\end{pmatrix}$\n", "3. $\\quad A = \\begin{pmatrix}0 & 1 & 0\\\\ 1 & 0 & 1 \\\\ -2 & 0 & 0\\end{pmatrix} \\qquad \\quad b = \\begin{pmatrix}0 \\\\ 2 \\\\ -1\\end{pmatrix}$\n", "4. $\\quad A = \\begin{pmatrix}1 & 0 & 0\\\\ 1 & -1 & -1 \\\\ 0 & 1 & 0 \\\\ 1 & 0 & 0 \\\\ 0 & 1 & -1\\end{pmatrix} \\qquad \\ \\ b = \\begin{pmatrix}2 \\\\ 0 \\\\ 0 \\\\ -1 \\\\ -1\\end{pmatrix}$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "case_number = 1 # CHOISISSEZ LE NUMÉRO DE CAS ICI ET EXECUTEZ LA CELLULE SUIVANTE!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "if case_number == 1:\n", " A_cols = [[0,0], [1,-1]]\n", " A = np.array(A_cols).T\n", " b = [[0], [2]]\n", "elif case_number == 2:\n", " A_cols = [[0,1,1], [1,1,-2]]\n", " A = np.array(A_cols).T\n", " b = [[1], [1], [0]]\n", "elif case_number == 3:\n", " A_cols = [[0,1,-2], [1,0,0], [0,1,0]]\n", " A = np.array(A_cols).T\n", " b = [[0], [2], [-1]]\n", "elif case_number == 4:\n", " A_cols = [[1,1,0,1,0], [0,-1,1,0,1], [0,-1,0,0,-1]]\n", " A = np.array(A_cols).T\n", " b = [2,0,0,-1,-1]\n", "else:\n", " print(f\"{case_number} n'est pas un numéro de cas valide!\" \n", " f\"Numéros de cas disponibles: [1,2,3,4]\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Aide\n", "\n", "Pour résoudre le système linéaire, vous pouvez tirer parti des cellules interactives suivantes qui permettent d'appliquer la méthode d'élimitation de Gauss." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "al.printA(A.T@A, A.T@np.array(b))\n", "[i,j,r,alpha]= al.manualEch(A.T@A, A.T@np.array(b))\n", "m=np.concatenate((A.T@A,A.T@np.array(b)), axis=1)\n", "MatriceList=[A.T@A]\n", "RhSList=[A.T@np.array(b)]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "m=al.echelonnage(i,j,r,alpha,A.T@A,m,MatriceList,RhSList)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# INSEREZ ICI LA SOLUTION\n", "x,y,z = sp.symbols('x, y, z')\n", "sol = sp.sets.FiniteSet((x,-1)) " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# ÉVALUATION DE LA SOLUTION\n", "corrections.Ex2_Chapitre9_12(sol, case_nb=case_number)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 3\n", "\n", "Un scénario important dans lequel le calcul des solutions de systèmes linéaires au sens des moindres carrés est utilisé est celui de la **régression linéaire**. Supposons que l'on donne $N$ mesures de certaines quantités $\\left\\{\\left\\{x_j^i\\right\\}_{j=1}^K, y^i\\right\\}_{i=1}^N$; les variables $x$ sont appelées variables explicatives et $K$ est leur nombre. Par exemple, si $K=1$, ils peuvent être le poids ($x_1$) et la taille ($y$) de $N$ personnes différentes; si $K=2$ ils peuvent être le poids ($x_1$), la longueur des pieds ($x_2$) et la taille ($y$) de $N$ personnes différentes.\n", "\n", "L'objectif est de déterminer la meilleure relation linéaire possible entre ces grandeurs, c'est-à-dire de déterminer les meilleures valeurs possibles pour les coefficients $\\left\\{c_j\\right\\}_{j=0}^K$. En termes mathématiques, cela revient à résoudre le problème de minimisation suivant $$ \\left\\{c_j\\right\\}_{j=0}^K = \\underset{\\tilde{c}_0, \\dots, \\tilde{c}_k}{argmin} \\sum\\limits_{i=1}^N \\left(y^i - \\tilde{c}_0 - \\sum\\limits_{j=1}^K \\tilde{c}_j x_j^i \\right)^2$$ \n", "\n", "S'il existe une relation linéaire entre les données, alors $$y^i = c_0 + \\sum\\limits_{j=1}^K c_j x_j^i \\quad \\forall \\ i \\in \\{1, \\dots, N\\}$$ Cela implique que les coefficients $\\left\\{c_j\\right\\}_{j=0}^K$ sont des solutions au système linéaire suivant:\n", "\n", "\\begin{equation}\n", "\\begin{pmatrix}\n", "1 & x_1^1 & x_2^1 & \\dots & x_K^1 \\\\\n", "1 & x_1^2 & x_2^2 & \\dots & x_K^2 \\\\ \n", "\\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\\n", "1 & x_1^N & x_2^N & \\dots & x_K^N\n", "\\end{pmatrix}\n", "\\begin{pmatrix}\n", "c_0 \\\\ c_1 \\\\ c_2 \\\\ \\vdots \\\\ c_K\n", "\\end{pmatrix} = \n", "\\begin{pmatrix}\n", "y^1 \\\\ y^2 \\\\ \\vdots \\\\ y^N\n", "\\end{pmatrix}\n", "\\end{equation}\n", "\n", "Quoi qu'il en soit, comme $N$ dans les applications du monde réel est beaucoup plus grand que $K$, il est très probable que ce système n'admette aucune solution. Ainsi, c'est une approche commun de recourir au calcul d'une solution au sens des moindres carrés; on peut en fait prouver que la solution au sens des moindres carrés est égal à la solution au problème de minimisation quadratique susmentionné, dont dérive le nom de \"moindres carrés\".\n", "\n", "### Instructions\n", "e but de l'exercice est de montrer un scénario de cas réel où des solutions des moindres carrés aux systèmes linéaires sont employées; ainsi aucun calcul numérique n'est requis et peu de quantités doivent être correctement insérées.\n", "\n", "1. **GÉNÉRATION DE DONNÉES**: la cellule appelée \"GÉNÉRATION DE DONNÉES\" est responsable de la génération des données. En particulier, la méthode \"Ex3_Chapitre9_12_generate_data\" génère les données en superposant du bruit gaussien blanc à des données linéairement dépendantes. Les deux premiers arguments d'entrée régulent l'intensité du bruit. L'argument d'entrée appelée \"K\" définit le nombre de variables explicatives; les seules valeurs disponibles sont K = 1 et K = 2, de sorte que les données peuvent être visualisées via des nuages de points. Essayez les deux! Finalement, les variables X et Y stockent la matrice de gauche et le vecteur de droite du système linéaire précédemment introduit.\n", "\n", "2. **INSERTION DE SOLUTION**: la cellule appelée \"INSERTION DE SOLUTION\" vous permet de saisir les valeurs de la matrice de gauche M et du vecteur de droite f, définissant le système linéaire à résoudre afin de calculer la solution souhaitée. Dans ce but, nous rappelons que, étant donné deux matrices A, B:\n", " * A.T $\\rightarrow$ calcule la transposée de A\n", " * A @ B $\\rightarrow$ calcule le produit matriciel entre A et B\n", " * A * B $\\rightarrow$ calcule le produit élément par élément entre A et B\n", "\n", "\n", "3. **VISUALISATION DE LA SOLUTION**: la cellule appelée \"VISUALISATION DE LA SOLUTION\" vous permet de visualiser la solution au problème donnée." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# GÉNÉRATION DE DONNÉES\n", - "data, fig = corrections.Ex3_Chapitre9_12_generate_data(0.15, 0.075, case_nb=1)\n", + "data, fig = corrections.Ex3_Chapitre9_12_generate_data(0.15, 0.075, K=2)\n", "X = data[0]\n", "Y = data[1]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# INSERTION DE SOLUTION\n", - "M = X # !! inserez ici la matrice !!\n", - "f = Y # !! inserez ici le vecteur de droit !!\n", + "M = X.T @ X # !! inserez ici la matrice !!\n", + "f = X.T @ Y # !! inserez ici le vecteur de droit !!\n", "sys = M, f" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "# VISUALISATION DE LA SOLUTION\n", "corrections.Ex3_Chapitre9_12(sys, data, fig)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Passez au notebook du chapitre 9.13-9.14: La factorisation QR: application à la résolution d'un système au sens du moindres carrées](./9.13-9.14%20La%20factorisation%20QR%20-%20application%20à%20la%20résolution%20d'un%20système%20au%20sens%20des%20moindres%20carrées.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.7.4" } }, "nbformat": 4, "nbformat_minor": 4 }