{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# EART97012 \n", " \n", "# Geophysical Inversion \n", " \n", "## Lecture 2 " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Today's learning objectives \n", " \n", " \n", "1. To introduce concepts underlying the computational tasks of optimisation and inversion\n", "\n", "\n", "2. To review some more key linear algebra results, especially on the solvability of square problems, rank and range etc\n", "\n", "\n", "3. To introduce some simple examples of over- and under-determined problems\n", "\n", " \n", "
\n", "\n", "
\n", "\n", "Note that the linear algebra thory and associated simple code examples unpin huge parts of computer/computational science, data science, machine learning and AI, etc. So these are very valuable and universal concepts both within and outside of the relatively narrow focus of this module on inversion methods.\n", " \n", "
\n", " \n", "I'll skip over some of the longer text sections to focus on explaining the linear algebra concepts using the whiteboard. Please read these through in your own time." ] }, { "cell_type": "markdown", "metadata": { "toc": true }, "source": [ "

Table of Contents

\n", "
" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "scrolled": false }, "outputs": [], "source": [ "%matplotlib inline\n", "%precision 6\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "import scipy.linalg as sl\n", "from pprint import pprint" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Introductory comments \n", "\n", "In this lecture we will consider some more important linear algebra theory, in particular what it tells us about solutions to *square* problems.\n", "\n", "We will introduce some simple examples of non-square systems - the case of over- and under-determined problems - with solution procedures coming in future weeks." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Examples (continued)\n", "\n", "At the end of the last lecture we ended with the curve-fitting example, where we had more equations/constraints that unknowns (an example of an *over-determined* problem) and introduced the concept of the least squares solution. \n", "\n", "Let's consider some more examples.\n", "\n", "
\n", "\n", "## Inversion example (more complex)\n", "\n", "In this example from some current research we have a model for tides in the Bristol Channel and Severn Estuary, there are multiple numerical and physical \"parameters\" that go into the model, including incoming tidal boundary conditions, bathymetry etc, some of which are known to varying levels of uncertainty. \n", "\n", "In this example we consider bed roughness (or bottom friction) as the parameters we wish to invert for, given the data of time series of tidal heights at tide gauges indicated by the red dots in the following image which also shows the discretised domain and the computational mesh\n", "\n", "\n", "\n", "Using *a priori* information on the approximate distribution of sediment grain sizes on the seabed, we partition the domain into three zones: rock, gravel and sand, and assign one parameter value to each. In this case we therefore have more data than parameters.\n", "\n", "In this case an iterative approach is taken and the following figure shows how the inversion progresses\n", "\n", "\n", "\n", "$J$ is a misfit function between modelled tides and observations and we solve the inversion problem by seeking to minimse $J$ - we see it drop as the model fit to data improves with iteration. How the three parameter values vary with iteration is also shown.\n", "\n", "The quality of the prediction can then be compared at the green squares where data was not used in the inversion. We find that the error in prediction at these independent locations is indeed reduced within the same numerical model. We have also found that the prediction is improved when these physical values are used in a completely independent tidal model. This latter fact gives us some indication that our inversion is telling us something useful physically and not simply correcting for biases in the first model.\n", "\n", "
\n", "\n", "For publications on this topic see \n", "\n", "- \n", "\n", "- " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Seismic inversion\n", "\n", "The more practical half of this module will focus on seismic inversion and similar applications, which you will already be somewhat familiar with from other modules." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Optimisation\n", "\n", "Optimisation, in a single real variable, seeks to find a value for $x$ such that a scalar function \n", "\n", "$$f(x)$$\n", "\n", "has a minimum value (or equivalently that $-f(x)$ has a maximum value). \n", "\n", "For example, $f(x)$ might be the energy of a particle at position $x$. The value of $x$ for which this is a minimum will provide a rest position for the particle. \n", "\n", "Or we could have a problem where we are seeking a design of something that minimises cost or maximises profit.\n", "\n", "There are many ways to solve such problems, and again there is no general solution. In practical real problems, there may be no solution, a single unique solution, several solutions or infinitely many solutions. \n", "\n", "### Optimisation as an inversion problem\n", "\n", "One way to address the optimisation problem is to try to solve \n", "\n", "$$f'(x)=0$$\n", "\n", "for $x$. With this approach note that we have converted an optimisation problem into an inversion problem (we are looking for the $x$ values that satisfy this equation - this will give us the [stationary points](https://en.wikipedia.org/wiki/Stationary_point) of the problem).\n", "\n", "\n", "### Inversion as an optimisation problem\n", "\n", "In practice, it is often the case that in order to solve an inversion problem, it is instead converted into an optimisation problem. \n", "\n", "For example, we can define a scalar misfit function measuring in some sense the difference between model predictions and observations and seek to iteratively minimise this misfit. \n", "\n", "The least squares error is an example of this. We showed previously (*) that we could write down the general solution to this problem. But it's only feasible to use that approach for small cases. For larger problems we will need iterative solution methods such as in the tidal example above. \n", "\n", "
\n", "\n", "(*) From last lecture an over-determined problem $V\\boldsymbol{a} = \\boldsymbol{y}$ has least-squares approximate solution $\\boldsymbol{a} = (V^TV)^{-1}V^T\\boldsymbol{y}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Optimisation - simple example\n", "\n", "Consider the problem: find $\\boldsymbol{x}\\equiv (x,y)$ which minimises the function\n", "\n", "$$ f(\\boldsymbol{x}) = 1+2x + 4y + x^2+2xy+3y^2$$\n", "\n", "\n", "The following image shows a contour plot of the function, and the red star indicates the $(x,y)$ location of the minima\n", "\n", "\n", "\n", "A homework exercise asks you to compute the minima and to generate this image." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Optimisation (more complex)\n", "\n", "The following movie shows iterations from an optimisation problem where our task is to maximise the power generated by an array of 256 individual tidal turbines. At every iteration a shallow water solver computes the flow field and the power of the array. The design parameters are then the $(x,y)$ location of each of the turbines.\n", "\n", "
\n", "\n", "For a publication on this see\n", "\n", "- \n", "\n", "
\n", "
\n", "\n", "