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 40c0f3e..7c1cb4c 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,90 +1,312 @@ { "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", + "Consider the following linear systems in the form $Ax=b$. Compute their solution in the least-squares sense by projecting $b$ onto the image space of $A$ and by solving $Ax = proj_{Im(A)}b$.\n", + "\n", + "1. $A = \\begin{pmatrix}1 & 0 \\\\ 1 & 0\\end{pmatrix} \\qquad b = \\begin{pmatrix}1 \\\\ 3\\end{pmatrix}$\n", + "2. $A = \\begin{pmatrix}1 & 1 \\\\ 1 & -1 \\\\ 2 & 0\\end{pmatrix} \\qquad b = \\begin{pmatrix}1 \\\\ 2 \\\\ -2\\end{pmatrix}$\n", + "3. $A = \\begin{pmatrix}1 & 0 & 0\\\\ 0 & 1 & 1 \\\\ 1 & 0 & 0\\end{pmatrix} \\qquad b = \\begin{pmatrix}-1 \\\\ 2 \\\\ 1\\end{pmatrix}$\n", + "4. $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 = 4 # CHOOSE THE CASE NUMBER HERE!" + ] + }, + { + "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", + "To solve the linear system, you can take andvantage of the following interactive cells that allow to apply the Gauss elimitation method. Notice that you have to **enter the value found for the projection of $\\boldsymbol{b}$ onto the image space of $\\boldsymbol{A}$ in the first line!**" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [ + "proj_b = [[0], [2], [0]] # ENTER HERE THE VALUE FOUND FOR THE PROJECTION OF b ONTO 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": [ - "A = [[0,1], [0,1]]\n", - "b = [1,2]\n", - "al.Plot2DSys(-7,7,15,A,b, with_sol=True, with_sol_lstsq=True)" + "# ENTER THE FINAL SOLUTION HERE\n", + "x,y,z = sp.symbols('x, y, z')\n", + "sol = sp.sets.FiniteSet((0,2-z,z), sp.Reals) # TODO: correction file with plots!" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Exercice 2\n", + "\n", + "Consider the following linear systems in the form $Ax=b$. Compute their solution in the least-squares sense by solving the linear system $A^TAx = A^Tb$.\n", + "\n", + "1. $A = \\begin{pmatrix}1 & 0 \\\\ 1 & 0\\end{pmatrix} \\qquad b = \\begin{pmatrix}1 \\\\ 3\\end{pmatrix}$\n", + "2. $A = \\begin{pmatrix}1 & 1 \\\\ 1 & -1 \\\\ 2 & 0\\end{pmatrix} \\qquad b = \\begin{pmatrix}1 \\\\ 2 \\\\ -2\\end{pmatrix}$\n", + "3. $A = \\begin{pmatrix}1 & 0 & 0\\\\ 0 & 1 & 1 \\\\ 1 & 0 & 0\\end{pmatrix} \\qquad b = \\begin{pmatrix}-1 \\\\ 2 \\\\ 1\\end{pmatrix}$\n", + "4. $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": [ - "A = [[1,0,0], [1,0,0], [1,0,0]]\n", - "b = [1,0.5,2]\n", - "al.Plot3DSys(-7,7,15,A,b, with_sol=True, with_sol_lstsq=True)" + "case_number = 1 # CHOOSE THE CASE NUMBER HERE AND RUN THE NEXT CELL!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], - "source": [] + "source": [ + "if case_number == 1:\n", + " A_cols = [[1,1], [0,0]]\n", + " A = np.array(A_cols).T\n", + " b = [[-1], [0]]\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", + "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", + "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]\")" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Aide\n", + "\n", + "To solve the linear system, you can take andvantage of the following interactive cells that allow to apply the Gauss elimitation method. " + ] + }, + { + "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": [ + "# ENTER THE FINAL SOLUTION HERE\n", + "x,y,z = sp.Symbols('x, y, z')\n", + "sol = FiniteSet((2, y), sp.Reals) # TODO: correction file with plots!" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Exercice 3\n", + "\n", + "To illustrate a practical example of LS, do linear regression. Enrich with a proper scatter plot.\n", + "Make 2 cases (2D and 3D)." + ] } ], "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 }