{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# EART 70013 \n", " \n", "# Geophysical Inversion \n", " \n", "## Lecture 4 - Homework " ] }, { "cell_type": "markdown", "metadata": { "toc": true }, "source": [ "

Table of Contents

\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%matplotlib inline\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "import scipy.linalg as sl\n", "from pprint import pprint\n", "import scipy.interpolate as si" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Homework" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Homework - Row operations on an over-determined problem\n", "\n", "Consider the following example from the lecture\n", "\n", "$$\n", "\\begin{align*}\n", " 2x + 3y &= 7 \\\\[5pt]\n", " x - 4y &= 3 \\\\[5pt]\n", " -3x - 10y & = -11\n", "\\end{align*}\n", " \\quad \\iff \\quad\n", " \\begin{pmatrix}\n", " 2 & 3 \\\\\n", " 1 & -4 \\\\\n", " -3 & -10 \n", " \\end{pmatrix}\n", " \\begin{pmatrix}\n", " x \\\\\n", " y \n", " \\end{pmatrix}=\n", " \\begin{pmatrix}\n", " 7 \\\\\n", " 3 \\\\\n", " -11\n", " \\end{pmatrix} \n", "$$\n", "\n", "Use row operations on the augmented system in an attempt to solve this problem.\n", "\n", "
\n", "\n", "In doing this you will be able to also establish the rank of $A$ and the rank of the augmented matrix.\n", "\n", "What relationship do you need between these two values in order for the problem to have a solution?\n", "\n", "Can you think of an example where this wouldn't be the case and you have a system without an exact solution?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Homework - An over-determined system with (by construction) an exact solution\n", "\n", "Recall the simple over-determined problem from the lecture\n", "\n", "`A = np.array([[2, 3], [1, -4], [1, 10]])`\n", "\n", "You were asked to think about how you could change the RHS vector only in order to come up with a version of the over-determined problem that has an exact solution. You were given the hint to think about the range of the LHS matrix $A$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Homework - Least squares solution as a compromise between all constraints\n", "\n", "At the end of the lecture we showed an example and noted that the least squares solution was attempting to satisfy all three constraint equations, and that the specific value found was the one which minimised $\\| A\\boldsymbol{x} - \\boldsymbol{b}\\|_2$.\n", "\n", "By perturbing the values of the obtained least squares solution, show that it is indeed the case that these lead to $\\| A\\boldsymbol{x} - \\boldsymbol{b}\\|_2$ growing." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Homework - An even simpler over-determined case\n", "\n", "In the lecture, and above, we considered the simple case of three equations, two unknowns.\n", "\n", "Of course there is an even simpler case - two-equations, one unknown.\n", "\n", "An example might be\n", "\n", "$$\n", "\\begin{align*}\n", " 2x &= 8 \\\\[5pt]\n", " 3x &= 9\n", "\\end{align*}\n", " \\quad \\iff \\quad\n", " \\begin{pmatrix}\n", " 2 \\\\[5pt]\n", " 3\n", " \\end{pmatrix}\n", " \\begin{pmatrix}\n", " x \n", " \\end{pmatrix}=\n", " \\begin{pmatrix}\n", " 8 \\\\\n", " 9 \n", " \\end{pmatrix} \n", "$$\n", "\n", "Does this have a solution?\n", "\n", "No clearly not. What solution does the least square approach return?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Homework - Outer-product\n", "\n", "Comnpute the outer-product ($\\boldsymbol{a}\\boldsymbol{b}^T$) of the column vectors\n", "\n", "$$\\boldsymbol{a} = \n", "\\begin{pmatrix}\n", "1 \\\\\n", "2\\\\\n", "3 \n", "\\end{pmatrix}, \n", "\\qquad\n", "\\boldsymbol{b} = \n", "\\begin{pmatrix}\n", "4 \\\\\n", "5\\\\\n", "6 \n", "\\end{pmatrix}.\n", "$$\n", "\n", "What is the resulting matrices rank?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Homework - Matrix rank and RREF (a non-square case)\n", "\n", "Consider the rectangular matrix\n", "\n", "$$\n", "\\begin{pmatrix}\n", "3 & 1 & 9 & 4 \\\\\n", "2 & 1 & 7 & 3 \\\\\n", "5 & 2 & 16 & 7 \n", "\\end{pmatrix}\n", "$$\n", "\n", "convert to REF and RREF. \n", "\n", "From these what is the rank of this matrix?\n", "\n", "What is the null space?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Homework - Minimal-norm solution to under-determined problem\n", "\n", "Let's begin this example from a problem already in RREF, the augmented form of the matrix with zero RHS being\n", "\n", "$$\n", "\\left(\n", " \\begin{array}{cccc|c}\n", "1 & 0 & 4 & 0 & 0 \\\\\n", "0 & 1 & -2 & 0 & 0 \\\\\n", "0 & 0 & 0 & 1 & 0 \n", " \\end{array}\n", "\\right)$$\n", "\n", "Show that the null space is given by any multiple of the following vector.\n", "\n", "$$\\boldsymbol{v}\n", "=\n", "\\begin{pmatrix}\n", "-4\\\\\n", "2\\\\\n", "1\\\\\n", "0\n", "\\end{pmatrix}\n", "$$\n", "\n", "Now consider the solution to the problem with RHS vector\n", "\n", "$$\\boldsymbol{b} = \\begin{pmatrix}\n", "1 \\\\\n", "-2\\\\\n", "3\n", "\\end{pmatrix} $$\n", "\n", "Use the minimum norm solution formula from the lecture to compute the solution.\n", "\n", "Establish that it is indeed the minimal-norm solution, i.e. that all other possible solutions you obtain by adding multiples of the null vector have a larger norm." ] } ], "metadata": { "celltoolbar": "Slideshow", "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.13" }, "latex_envs": { "LaTeX_envs_menu_present": true, "autoclose": true, "autocomplete": true, "bibliofile": "biblio.bib", "cite_by": "apalike", "current_citInitial": 1, "eqLabelWithNumbers": true, "eqNumInitial": 1, "hotkeys": { "equation": "Ctrl-E", "itemize": "Ctrl-I" }, "labels_anchors": false, "latex_user_defs": false, "report_style_numbering": false, "user_envs_cfg": true }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": false, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": true, "toc_position": {}, "toc_section_display": true, "toc_window_display": false } }, "nbformat": 4, "nbformat_minor": 1 }