{"cells": [{"cell_type": "markdown", "metadata": {"tags": ["module-nm", "module-ginv"]}, "source": ["# Linear Algebra in Python\n", "[Numerical Methods](module-nm) [Geophysical Inversion](module-ginv) \n", "\n", "## Motivation\n", "\n", "Linear algebra is of vital importance in almost any area of science and engineering and therefore numerical linear algebra is just as important in computational science. Some of the more popular areas of application include machine learning, computer vision, finite element method, optimisation, and many others.\n", "\n", "Computers use a discrete representation of the real numbers, rather than a continuous one, which has several consequences. Most notably, it means that there have to be gaps between adjacent numbers. We will therefore most often want to work with [floating point numbers with double precision](https://en.wikipedia.org/wiki/Double-precision_floating-point_format) (*float* in python) which allow us to represent real numbers with very high precision. However, often in computing we deal with extremely large datasets (e.g. matrices with millions of rows and columns) so even tiny errors can grow and accumulate very fast if our algorithm is [*numerically unstable*](https://en.wikipedia.org/wiki/Numerical_stability). \n", "\n", "For example, we might be tempted to solve $A \\mathbf{x} = \\mathbf{b}$ by calculating an inverse of A, but calculating inverses and determinants of matrices is generally avoided in computing due to round-off errors. Numerical linear algebra therefore aims to come up with fast and efficient algorithms to solve usual linear algebra problems without magnifying these (and other) small errors.\n", "\n", "## Python\n", "\n", "The main library for linear algebra in Python is [SciPy](https://www.scipy.org/) which makes use of NumPy arrays. NumPy also provides plenty of basic functionalities through its functions in [``numpy.linalg``](https://numpy.org/doc/stable/reference/routines.linalg.html), but many advanced capabilities remain reserved for [``scipy.linalg``](https://docs.scipy.org/doc/scipy/reference/linalg.html). "]}, {"cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": ["import numpy as np\n", "import numpy.linalg as la"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Constructing some useful matrices\n", "\n", "### Identity matrix\n", "\n", "NumPy provides us with two almost identical functions to construct identity matrices: ``numpy.identity(n)`` and ``numpy.eye(n, [m=n], [k=0])``. The former constructs a square matrix with n rows and columns with 1s on the main diagonal. The latter constructs an $n \\times m$ matrix with 1s on the kth diagonal (k=0 is the main diagonal). Examples below demonstrate this:"]}, {"cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["identity(5) = \n", " [[1. 0. 0. 0. 0.]\n", " [0. 1. 0. 0. 0.]\n", " [0. 0. 1. 0. 0.]\n", " [0. 0. 0. 1. 0.]\n", " [0. 0. 0. 0. 1.]]\n", "\n", "eye(4, 5) = \n", " [[1. 0. 0. 0. 0.]\n", " [0. 1. 0. 0. 0.]\n", " [0. 0. 1. 0. 0.]\n", " [0. 0. 0. 1. 0.]]\n", "\n", "eye(4, 5, -1) = \n", " [[0. 0. 0. 0. 0.]\n", " [1. 0. 0. 0. 0.]\n", " [0. 1. 0. 0. 0.]\n", " [0. 0. 1. 0. 0.]]\n", "\n", "eye(4, 5, 2) = \n", " [[0. 0. 1. 0. 0.]\n", " [0. 0. 0. 1. 0.]\n", " [0. 0. 0. 0. 1.]\n", " [0. 0. 0. 0. 0.]]\n"]}], "source": ["print('identity(5) = \\n', np.identity(5)) # square 5x5 matrix\n", "print('\\neye(4, 5) = \\n', np.eye(4, 5)) # 4x5 matrix\n", "print('\\neye(4, 5, -1) = \\n', np.eye(4, 5, -1)) # 1st lower diagonal\n", "print('\\neye(4, 5, 2) = \\n', np.eye(4, 5, 2)) # 2nd upper diagonal"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Diagonal matrix\n", "\n", "The function [``numpy.diag(array, [k=0])``](https://numpy.org/doc/stable/reference/generated/numpy.diag.html) either extracts a diagonal from an array or constructs a diagonal array:\n", "\n", "1. if the input array is 2-D, returns a 1-D array with diagonal entries\n", "2. if the input array is 1-D, returns a diagonal 2-D array with entries from the input array on the diagonal."]}, {"cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["diag(M) = [1 4]\n", "diag(v) = \n", " [[6 0]\n", " [0 8]]\n"]}], "source": ["M = np.array([[1, 2],\n", " [3, 4]])\n", "v = np.array([6, 8])\n", "\n", "print('diag(M) = ', np.diag(M))\n", "print('diag(v) = \\n', np.diag(v))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Example: tridiagonal matrix\n", "\n", "Let us show how we could use ``numpy.diag`` to construct a tridiagonal matrix, which is a banded matrix with non-zero entries on the main diagonal and the first off-diagonals above and below the main diagonal."]}, {"cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["[[2 3 0 0]\n", " [1 2 3 0]\n", " [0 1 2 3]\n", " [0 0 1 2]]\n"]}], "source": ["a = [1, 1, 1]\n", "b = [2, 2, 2, 2]\n", "c = [3, 3, 3]\n", "\n", "A = np.diag(a, -1) + np.diag(b, 0) + np.diag(c, 1)\n", "\n", "print(A)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Triangular matrix\n", "\n", "To construct upper or lower triangular matrices we use ``numpy.triu(array, [k=0])`` or ``numpy.tril(array, [k=0])`` functions (u stands for upper, l stands for lower). Returns an array whose entries below or above the kth diagonal are 0 (k=0 is the main diagonal)."]}, {"cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["M = \n", " [[ 1 2 3]\n", " [ 4 5 6]\n", " [ 7 8 9]\n", " [10 11 12]]\n", "\n", "triu(M) = \n", " [[1 2 3]\n", " [0 5 6]\n", " [0 0 9]\n", " [0 0 0]]\n", "\n", "triu(M, -1) = \n", " [[ 1 2 3]\n", " [ 4 5 6]\n", " [ 0 8 9]\n", " [ 0 0 12]]\n", "\n", "tril(M, 1) = \n", " [[ 1 2 0]\n", " [ 4 5 6]\n", " [ 7 8 9]\n", " [10 11 12]]\n"]}], "source": ["M = np.arange(1, 13).reshape(4, 3)\n", "print('M = \\n', M)\n", "\n", "print('\\ntriu(M) = \\n', np.triu(M))\n", "print('\\ntriu(M, -1) = \\n', np.triu(M, -1))\n", "print('\\ntril(M, 1) = \\n', np.tril(M, 1))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Sparse matrices\n", "\n", "A sparse matrix is a matrix with mostly zero-valued entries. Performing operations on sparse matrices can therefore be unnecessarily computationally expensive, since we are unnecessarily adding 0s or multiplying by 0, for example. Therefore, when working with sparse matrices we would like to have an option to simply skip this kind of operations.\n", "\n", "The identity matrix and diagonal matrices are examples of such matrices, although a sparse matrix does not need to have any particular structure. The non-zero entries could be completely random, and this is most often the case in practice.\n", "\n", "SciPy allows us to build such matrices and do operations on them with the [``scipy.sparse``](https://docs.scipy.org/doc/scipy/reference/sparse.html) package. There are several formats how these matrices are stored and users are encouraged to read the documentation and the [Wikipedia page](https://en.wikipedia.org/wiki/Sparse_matrix) for an explanation of them. For example, a sparse matrix in coordinate format is stored in three arrays: one for the values of non-zero entries and two for the row and column index of those entries.\n", "\n", "### Examples: Convert a NumPy array\n", "\n", "We can convert any array to a sparse matrix. For example, we can use the function [`scipy.sparse.coo_matrix`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.coo_matrix.html) to construct a matrix in COOrdinate format. Let us convert a tridiagonal NumPy matrix to a sparse SciPy matrix."]}, {"cell_type": "code", "execution_count": 34, "metadata": {"scrolled": false}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["[[2 3 0 0 0 0 0 0 0 0]\n", " [1 2 3 0 0 0 0 0 0 0]\n", " [0 1 2 3 0 0 0 0 0 0]\n", " [0 0 1 2 3 0 0 0 0 0]\n", " [0 0 0 1 2 3 0 0 0 0]\n", " [0 0 0 0 1 2 3 0 0 0]\n", " [0 0 0 0 0 1 2 3 0 0]\n", " [0 0 0 0 0 0 1 2 3 0]\n", " [0 0 0 0 0 0 0 1 2 3]\n", " [0 0 0 0 0 0 0 0 1 2]]\n", " (0, 0)\t2\n", " (0, 1)\t3\n", " (1, 0)\t1\n", " (1, 1)\t2\n", " (1, 2)\t3\n", " (2, 1)\t1\n", " (2, 2)\t2\n", " (2, 3)\t3\n", " (3, 2)\t1\n", " (3, 3)\t2\n", " (3, 4)\t3\n", " (4, 3)\t1\n", " (4, 4)\t2\n", " (4, 5)\t3\n", " (5, 4)\t1\n", " (5, 5)\t2\n", " (5, 6)\t3\n", " (6, 5)\t1\n", " (6, 6)\t2\n", " (6, 7)\t3\n", " (7, 6)\t1\n", " (7, 7)\t2\n", " (7, 8)\t3\n", " (8, 7)\t1\n", " (8, 8)\t2\n", " (8, 9)\t3\n", " (9, 8)\t1\n", " (9, 9)\t2\n"]}], "source": ["from scipy.sparse import coo_matrix\n", "\n", "\n", "a, b, c = [1] * 9, [2] * 10, [3] * 9\n", "\n", "A = np.diag(a, -1) + np.diag(b, 0) + np.diag(c, 1)\n", "print(A)\n", "\n", "spA = coo_matrix(A)\n", "print(spA)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["In the above example, A has 100 entries, while spA ('sparse A') has only 28. In this case we would not save much computational time since a $10 \\times 10$ matrix is quite small. However, sparse matrices become more useful (and even essential) the larger our matrix is.\n", "\n", "### Examples: Construct a tridiagonal matrix\n", "\n", "Users more comfortable with SciPy may wish to directly construct sparse matrices, instead of converting a NumPy array. Let us construct the same tridiagonal matrix as in the previous example."]}, {"cell_type": "code", "execution_count": 35, "metadata": {"scrolled": true}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["[[2. 3. 0. 0. 0. 0. 0. 0. 0. 0.]\n", " [1. 2. 3. 0. 0. 0. 0. 0. 0. 0.]\n", " [0. 1. 2. 3. 0. 0. 0. 0. 0. 0.]\n", " [0. 0. 1. 2. 3. 0. 0. 0. 0. 0.]\n", " [0. 0. 0. 1. 2. 3. 0. 0. 0. 0.]\n", " [0. 0. 0. 0. 1. 2. 3. 0. 0. 0.]\n", " [0. 0. 0. 0. 0. 1. 2. 3. 0. 0.]\n", " [0. 0. 0. 0. 0. 0. 1. 2. 3. 0.]\n", " [0. 0. 0. 0. 0. 0. 0. 1. 2. 3.]\n", " [0. 0. 0. 0. 0. 0. 0. 0. 1. 2.]]\n", " (1, 0)\t1.0\n", " (2, 1)\t1.0\n", " (3, 2)\t1.0\n", " (4, 3)\t1.0\n", " (5, 4)\t1.0\n", " (6, 5)\t1.0\n", " (7, 6)\t1.0\n", " (8, 7)\t1.0\n", " (9, 8)\t1.0\n", " (0, 0)\t2.0\n", " (1, 1)\t2.0\n", " (2, 2)\t2.0\n", " (3, 3)\t2.0\n", " (4, 4)\t2.0\n", " (5, 5)\t2.0\n", " (6, 6)\t2.0\n", " (7, 7)\t2.0\n", " (8, 8)\t2.0\n", " (9, 9)\t2.0\n", " (0, 1)\t3.0\n", " (1, 2)\t3.0\n", " (2, 3)\t3.0\n", " (3, 4)\t3.0\n", " (4, 5)\t3.0\n", " (5, 6)\t3.0\n", " (6, 7)\t3.0\n", " (7, 8)\t3.0\n", " (8, 9)\t3.0\n"]}], "source": ["from scipy.sparse import diags\n", "\n", "\n", "diagonals = [[1] * 9, [2] * 10, [3] * 9]\n", "\n", "A = diags(diagonals, [-1, 0, 1], format='coo')\n", "print(A.toarray()) # print the entire array\n", "print(A)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Matrix operations\n", "\n", "### Arithmetic operations\n", "\n", "All arithmetic operators (``+``, ``-``, ``*``, ``/ ``, ``%``, ``**``, ``//``) on arrays apply elementwise. If both operands are matrices they need to have the same dimensions (to be conformable for the operation)."]}, {"cell_type": "code", "execution_count": 26, "metadata": {"hide_input": true, "scrolled": false}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["M =\n", " [[1 2]\n", " [3 4]]\n", "M + M =\n", " [[2 4]\n", " [6 8]]\n", "M - M =\n", " [[0 0]\n", " [0 0]]\n", "4 * M =\n", " [[ 4 8]\n", " [12 16]]\n", "M * M =\n", " [[ 1 4]\n", " [ 9 16]]\n", "M / M =\n", " [[1. 1.]\n", " [1. 1.]]\n", "M ** 3 =\n", " [[ 1 8]\n", " [27 64]]\n", "M % 2 =\n", " [[1 0]\n", " [1 0]]\n", "M // 2 =\n", " [[0 1]\n", " [1 2]]\n"]}], "source": ["M = np.array([[1, 2], \n", " [3, 4]])\n", "\n", "print('M =\\n', M)\n", "print('M + M =\\n', M + M) # add\n", "print('M - M =\\n', M - M) # subtract\n", "print('4 * M =\\n', 4 * M) # multiply by a scalar\n", "print('M * M =\\n', M * M) # multiply matrices elementwise\n", "print('M / M =\\n', M / M) # divide elementwise\n", "print('M ** 3 =\\n', M ** 3) # exponentiation elementwise (M**3 = M*M*M)\n", "print('M % 2 =\\n', M % 2) # modulus\n", "print('M // 2 =\\n', M // 2) # integer (floor) division"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Matrix multiplication\n", "\n", "NumPy uses the function [``numpy.matmul(array1, array2)``](https://numpy.org/doc/stable/reference/generated/numpy.matmul.html) to multiply two matrices. Users of Python 3.5 or newer can use the operator ``@`` instead.\n", "\n", "To raise a matrix to some power we need to use the function ``numpy.linalg.matrix_power(array, exp)``.\n", "\n", "**Note:** When one of the operands is a 1-D array (we might initialise a vector this way if we are not careful - see below on reshaping arrays), it will automatically be assumed that it is a row vector if it is left-multiplying or a column vector if it is right-multiplying. The result will be a 1-D array as well."]}, {"cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["M @ M =\n", " [[ 7 10]\n", " [15 22]]\n", "M @ M @ M =\n", " [[ 37 54]\n", " [ 81 118]]\n", "M^3 = \n", " [[ 37 54]\n", " [ 81 118]]\n", "x = [1 2]\n", "x @ M = \n", " [ 7 10]\n", "M @ x = \n", " [ 5 11]\n"]}], "source": ["print('M @ M =\\n', M @ M)\n", "print('M @ M @ M =\\n', M @ M @ M)\n", "print('M^3 = \\n', la.matrix_power(M, 3))\n", "\n", "x = np.array([1, 2]) # 1-D array\n", "print('x = ', x)\n", "\n", "print('x @ M = \\n', x @ M)\n", "print('M @ x = \\n', M @ x)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Inner product\n", "\n", "The function [`` numpy.dot(array1, array2) ``](https://numpy.org/doc/stable/reference/generated/numpy.dot.html) is an alternative matrix product function but we recommend using it only for calculating an inner product of two vectors. Curious readers are encouraged to read the documentation for other uses, although `@` is preferred."]}, {"cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["11\n"]}], "source": ["x = np.array([1, 2])\n", "y = np.array([3, 4])\n", "\n", "print(np.dot(x, y))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Transpose\n", "\n", "A matrix can be transposed using ``numpy.transpose(array)`` or with the array attribute ``array.T``. "]}, {"cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["M.T = \n", " [[1 3]\n", " [2 4]]\n", "numpy.transpose(M) = \n", " [[1 3]\n", " [2 4]]\n"]}], "source": ["print('M.T = \\n', M.T)\n", "print('numpy.transpose(M) = \\n', np.transpose(M))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Reshaping arrays\n", "\n", "Note that 1-D NumPy arrays remain unchanged when transposed. To avoid this kind of issues, column (or row) vectors should be initialised as 2-D $n \\times 1$ (or $1 \\times n$) arrays. Below demonstrates this, as well as how to reshape 1-D arrays to 2-D. A very useful method of doing this is by giving -1 as one of the new shape parameters. We cannot give -1 for more than one shape parameter, as this is the unknown value which NumPy will figure out for us. For example, if we start from a 1-D array of 4 entries, reshaping it to (-1, 1, 2) will generate an array of shape $k \\times 1 \\times 2$ where $k \\in \\mathbb{N}$ has to satisfy $k \\cdot 1 \\cdot 2 = 4$ so that the total number of entries (A.size in NumPy) is preserved. If this $k$ does not exist, the reshaping is not possible."]}, {"cell_type": "code", "execution_count": 30, "metadata": {"hide_input": true}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["x = [1. 2. 3.] , number of dimensions: 1 , shape: (3,)\n", "x.T = [1. 2. 3.]\n", "x = [[1. 2. 3.]] , number of dimensions: 2 , shape: (1, 3)\n", "x.T = \n", " [[1.]\n", " [2.]\n", " [3.]]\n", "[1., 2., 3.].reshape(-1, 1) = \n", " [[1.]\n", " [2.]\n", " [3.]] , number of dimensions: 2 , shape: (3, 1)\n"]}], "source": ["import numpy as np\n", "\n", "x = np.array([1., 2., 3.])\n", "print('x =', x, ', number of dimensions: ', x.ndim, ', shape:', x.shape)\n", "print('x.T =', x.T)\n", "\n", "x = np.array([[1., 2., 3.]])\n", "print('x =', x, ', number of dimensions: ', x.ndim, ', shape:', x.shape)\n", "print('x.T = \\n', x.T)\n", "\n", "x = np.array([1., 2., 3.]).reshape(-1, 1) # reshape \n", "print('[1., 2., 3.].reshape(-1, 1) = \\n', x, ', number of dimensions: ', x.ndim, ', shape:', x.shape)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Complex conjugate\n", "\n", "We use ``numpy.conjugate(array)`` or its alias ``numpy.conj(array)`` to find the complex conjugate of an array containing complex entries. Alternatively we can use the ``.conj()`` attribute of NumPy arrays.\n", "\n", "To get the conjugate transpose (or Hermitian transpose) we would therefore write ``array.T.conj()``."]}, {"cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["C = \n", " [[1.+1.j 2.+2.j]\n", " [3.+3.j 4.+4.j]]\n", "conj(C) = \n", " [[1.-1.j 2.-2.j]\n", " [3.-3.j 4.-4.j]]\n", "C.conj() = \n", " [[1.-1.j 2.-2.j]\n", " [3.-3.j 4.-4.j]]\n", "\n", "C.T.conj() = \n", " [[1.-1.j 3.-3.j]\n", " [2.-2.j 4.-4.j]]\n"]}], "source": ["C = np.array([[1 + 1j, 2 + 2j],\n", " [3 + 3j, 4 + 4j]])\n", "\n", "print('C = \\n', C)\n", "print('conj(C) = \\n', np.conj(C))\n", "print('C.conj() = \\n', C.conj())\n", "\n", "print('\\nC.T.conj() = \\n', C.T.conj())"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Norms\n", "\n", "The function [``numpy.linalg.norm(array, [order])``](https://numpy.org/doc/stable/reference/generated/numpy.linalg.norm.html) returns a matrix or vector norm of specified order. If the order is not specified, it returns the Frobenius matrix norm (or 2-norm for vectors)."]}, {"cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["x = [1 2 3]\n", "M = \n", " [[1 2]\n", " [3 4]]\n", "\n", "norm(x, 1) = 6.0\n", "norm(x) = 3.7416573867739413\n", "norm(x, np.inf) 3.0\n", "\n", "norm(M) 5.477225575051661\n", "norm(M, np.inf) 7.0\n"]}], "source": ["x = np.array([1, 2, 3])\n", "M = np.array([[1, 2],\n", " [3, 4]])\n", "\n", "print('x = ', x)\n", "print('M = \\n', M)\n", "\n", "print('\\nnorm(x, 1) = ',la.norm(x, 1))\n", "print('norm(x) = ', la.norm(x))\n", "print('norm(x, np.inf)', la.norm(x, np.inf))\n", "\n", "print('\\nnorm(M)', la.norm(M))\n", "print('norm(M, np.inf)', la.norm(M, np.inf))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Matrix inverse\n", "\n", "We can find the inverse of a square matrix with the function [``numpy.linalg.inv(array)``](https://numpy.org/doc/stable/reference/generated/numpy.linalg.inv.html). As briefly mentioned in the motivation section, an inverse of large matrix is very likely to be imprecise due to round-off errors. However, we might be able to get away with it with certain smaller matrices."]}, {"cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["inverse(M) = \n", " [[-2. 1. ]\n", " [ 1.5 -0.5]]\n"]}], "source": ["print('inverse(M) = \\n', la.inv(M))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Solving systems of linear equations\n", "\n", "We will most often want to solve a linear matrix equation $A \\mathbf{x} = \\mathbf{b}$.\n", "\n", "As briefly mentioned in the motivation section, we should not solve this by finding an inverse $A^{-1}$ and then multiplying $A^{-1}\\mathbf{b}$ to find $\\mathbf{x}$.\n", "\n", "NumPy provides us with a function [`numpy.linalg.solve(A, b)`](https://numpy.org/doc/stable/reference/generated/numpy.linalg.solve.html) which will solve the equation for $\\mathbf{x}$ but it does it in a different way (see LU decomposition at the end of the notebook). It is required that $A$ is not singular. For singular matrices we need to use the least-squares method."]}, {"cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["[ 0.2 1.8 -0.4]\n"]}], "source": ["A = np.array([[3., 5., -1.],\n", " [1., 4., 1.],\n", " [9., 0., 2.]])\n", "b = np.array([10, 7, 1])\n", "\n", "x = np.linalg.solve(A, b)\n", "print(x)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Example: Runge-Kutta, Wave equation\n", "\n", "Consider the 1-D wave equation \n", "\n", "$$ u_{tt} + u_{xx} = 0, \\qquad u(0) = u(L) = 0,$$\n", "\n", "in the domain [0, L]. To solve it, let us write a standard explicit second order Runge-Kutta time-stepping algorithm. First, we need to discretise the equation with a finite difference approximation,\n", "\n", "$$ \\frac{\\partial^2}{\\partial t^2} u_i - \\frac{u_{i-1} -2u_i + u_{i+1}}{\\Delta x^2} = 0, \\qquad u_0 = u_{N+1}=0,$$\n", "\n", "where $\\Delta x = L / (N + 1)$ and $u_i = u(x_i) = u(i \\Delta x)$, $i = 1, \\dots, N$. Writing $\\mathbf{v} = (u_1, u_2, \\dots, u_N)^T$, we can express this equation as:\n", "\n", "$$ \\frac{\\partial^2}{\\partial t^2} \\mathbf{v} + A \\mathbf{v} = 0, $$\n", "\n", "where $A$ is an $N \\times N$ tridiagonal coefficient matrix:\n", "\n", "$$ A = \\frac{1}{\\Delta x^2}\n", " \\begin{bmatrix}\n", " 2& -1 & 0 &\\cdots & 0 & 0\\\\\n", " -1& 2 & -1 &\\cdots & 0 & 0\\\\\n", " 0 & -1 & 2 & \\cdots & 0 & 0 \\\\\n", " &\\vdots&&&\\vdots&\\vdots\\\\\n", " 0 & 0 & 0 & \\cdots & 2 & -1 \\\\\n", " 0 & 0 & 0 & \\cdots & -1 & 2 \\\\\n", " \\end{bmatrix}. $$\n", " \n", "Now we begin to see how linear algebra can be used to solve our PDE. We want to solve an ODE, so we introduce $\\mathbf{w} = dv / dt$\n", "\n", "\n", "\n", "\n", " \n", "\n", " u(x, 0) = {\\rm e}^{-x^2}, u_t(x, 0) = 0"]}, {"cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["[[ 2. -1. 0. 0. 0. 0. 0. 0. 0. 0.]\n", " [-1. 2. -1. 0. 0. 0. 0. 0. 0. 0.]\n", " [ 0. -1. 2. -1. 0. 0. 0. 0. 0. 0.]\n", " [ 0. 0. -1. 2. -1. 0. 0. 0. 0. 0.]\n", " [ 0. 0. 0. -1. 2. -1. 0. 0. 0. 0.]\n", " [ 0. 0. 0. 0. -1. 2. -1. 0. 0. 0.]\n", " [ 0. 0. 0. 0. 0. -1. 2. -1. 0. 0.]\n", " [ 0. 0. 0. 0. 0. 0. -1. 2. -1. 0.]\n", " [ 0. 0. 0. 0. 0. 0. 0. -1. 2. -1.]\n", " [ 0. 0. 0. 0. 0. 0. 0. 0. -1. 2.]]\n"]}], "source": ["from scipy.sparse import diags\n", "\n", "n = 10\n", "vals = np.array([-np.ones(n-1), 2*np.ones(n), -np.ones(n-1)]) #/ dx**2\n", "A = diags(vals, [-1, 0, 1])\n", "print(A.toarray())"]}, {"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Further reading\n", "\n", "Trefethen, L.N. and Bau III, D., 1997. Numerical linear algebra (Vol. 50). Siam.\n", "\n", "### QR and LU decomposition\n", "\n", "The most common method for finding a numerical solutions of an equation $A \\mathbf{x} = \\mathbf{b}$ make use of [QR](https://en.wikipedia.org/wiki/QR_decomposition) and [LU decompositions](https://en.wikipedia.org/wiki/LU_decomposition).\n", "\n", "**QR decomposition** (or factorisation) decomposes a matrix $A$ into a product $A = QR$, where $Q$ is an orthogonal (or unitary if complex) matrix and $R$ is upper-triangular. An orthogonal matrix $Q$ is a matrix whose transpose is equal to its inverse, i.e. $Q^T = Q^{-1}$. Having found $Q$ and $R$, solving the equation is then performed via a simple back-substitution because the LHS is upper-triangular:\n", "\n", "$$ A \\mathbf{x} = \\mathbf{b} \\\\\n", "QR \\mathbf{x} = \\mathbf{b} \\\\\n", "R \\mathbf{x} = Q^T \\mathbf{b}. $$\n", "\n", "Hence we got away with calculating an inverse of $A$, but rather we found an inverse of $Q$ which does not require any further calculations.\n", "\n", "**LU decomposition** factorises $A$ such that $A = LU$ where $L$ is a lower-triangular matrix and $U$ is an upper triangular matrix. \n", "\n", "$$ A \\mathbf{x} = \\mathbf{b} \\\\ \n", "LU \\mathbf{x} = \\mathbf{b} $$\n", "\n", "First we solve $ L \\mathbf{y} = \\mathbf{b}$ for $\\mathbf{y}$, where $\\mathbf{y} = U\\mathbf{x}$ and then we solve $U\\mathbf{x} = \\mathbf{y}$ for $\\mathbf{x}$. It is very simple to solve these two equations since solving triangular systems involves only back- or forward- substitution."]}, {"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": []}], "metadata": {"celltoolbar": "Tags", "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.8.8"}}, "nbformat": 4, "nbformat_minor": 2}