{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Homework 6"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"INSERT YOUR NAME HERE"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Directions:__ Add work to this notebook to solve the problems below.\n",
"\n",
"Be careful to name the objects you create as described in the problem. Some problems may include some tests you can run to test your code.\n",
"\n",
"This assignment will not be collected.\n",
"\n",
"Some problems are derived from problems in these books:\n",
"* __LL__: *Programming for Computations - Python* by Svein Linge and Hans Petter Langtangen, 2nd edition.\n",
"* __L__: *A Primer on Scientific Programming with Python* by Hans Petter Langtangen, 2nd edition.\n",
"* __TAK__: *Applied Scientific Computing With Python* by Peter R. Turner, Thomas Arildsen, and Kathleen Kavanagh."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Standard imports"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1. Manipulating matrices 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Write a function `manipulate1(M)`, which takes as input an $m \\times n$ matrix with both $m \\geq 2$ and $n \\geq 2$. The function should make a copy of $M$ (so that the original matrix does not change). Then the function should perform the following operations on the copy in the order below.\n",
"1. It should double the entries in column $1$ (the second column).\n",
"2. It should switch rows $0$ and $1$ (the first and second rows).\n",
"3. It should add three times column $0$ to column $1$.\n",
"\n",
"The function should then return the modified copy.\n",
"\n",
"*Check that your function works properly!*"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Manipulating matrices 2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Write a function `manipulate2(m)` which takes as input a $2$-dimensional numpy array `m` representing a matrix $M$. The function should make a copy of `m` (so that `m` is not changed). Then the following operations should be performed, in order:\n",
"* All diagonal entries should be doubled.\n",
"* The top right and bottom left entries should be swapped.\n",
"* The entries which are strictly closer to the bottom right corner than any other corner should be negated.\n",
"\n",
"For example, the if the following matrix is input for `manipulate2(m)`\n",
"$$\\left(\\begin{matrix}\n",
"2 & 3 & 4 \\\\\n",
"1 & -1 & 3 \\\\\n",
"8 & 5 & 11\n",
"\\end{matrix}\\right)$$\n",
"then the following matrix should be output:\n",
"$$\\left(\\begin{matrix}\n",
"4 & 3 & 8 \\\\\n",
"1 & -2 & 3 \\\\\n",
"4 & 5 & -22\n",
"\\end{matrix}\\right).$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Test suggested in the problem\n",
"m_in = np.array( [ [ 2, 3, 4 ],\n",
" [ 1, -1, 3 ],\n",
" [ 8, 5, 11] ] )\n",
"m_out = np.array( [ [ 4, 3, 8 ],\n",
" [ 1, -2, 3 ],\n",
" [ 4, 5, -22] ] )\n",
"assert (manipulate2(m_in) == m_out).all()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Manipulating matrices 3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Write a function `manipulate3(m)` which takes as input a $2$-dimensional numpy array `m` representing a matrix $M$. The function should return the matrix \n",
"$$\\left(\\begin{array}{r|r}\n",
"4I & 3 M \\\\\n",
"\\hline\n",
"M^T & M^T M\n",
"\\end{array}\\right).$$\n",
"Here, $M^T$ represents the transpose of $M$. The matrix $I$ represents the identity matrix whose sizes are chosen to make the above block matrix form well-defined. The matrix should be returned as a $2$-dimensional numpy array."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. Inverting a matrix"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We have seen that you can solve the matrix equation $A x = b$ using Gaussian elimination, where $A$ is an invertible square matrix. We didn't quite do it this way, but row reduction can turn the block matrix $[A | b]$ into $[I | x]$, where $x$ is the solution.\n",
"\n",
"You can obtain the inverse of a matrix $A$ in this way. Applying row reduction to the block matrix $[A | I]$ leads to the block matrix $[I | A^{-1}]$. Write a function `inverse(A)` which takes as input a invertible square matrix of floats, $A$, and returns the inverse $A^{-1}$. You must find this inverse using row reduction. Recall that allowed moves in row reduction are:\n",
"* Swapping two rows. \n",
"* Adding a multiple of one row to another row.\n",
"* Multiplying a row by a scalar.\n",
"\n",
"*Remarks:* You need to use pivoting to deal with the fact that some pivots might be zero. You can check your work easily. If $M$ is an invertible $n \\times n$ matrix, then the following should return a small matrix:\n",
"```python\n",
"np.abs( M @ inverse(M) - np.identity(n) )\n",
"```\n",
"Some tests are provided below."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 5. Tridiagonal matrices"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Write a function `tridiagonal_matrix(a,b,c)` which takes as input a vector $a$ with some length $n$ and vectors $b$ and $c$ with length $n-1$. The function should return the matrix\n",
"$$\\left[\\begin{array}{rrrrrr}\n",
"a_0 & b_0 & & & & \\\\\n",
"c_0 & a_1 & b_1 & & & \\\\\n",
" & c_1 & a_2 & b_2 & & \\\\\n",
" & & \\ddots & \\ddots & \\ddots & \\\\\n",
" & & & c_{n-3} & a_{n-2} & b_{n-2} \\\\\n",
" & & & & c_{n-2} & a_{n-1}\n",
"\\end{array}\\right].$$\n",
"\n",
"(This matrix appears in equation (4.10) of TAK on page 94, but I have shifted the indices to match Python conventions that we start indexing at zero rather than $1$.)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert \\\n",
" ( tridiagonal_matrix(np.arange(3),np.arange(3,5),np.arange(5,7)) == \\\n",
" np.array([[0., 3., 0.],\n",
" [5., 1., 4.],\n",
" [0., 6., 2.]]) ).all(), \\\n",
" \"Error. The matrix returned is incorrect.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 6. Solving tridiagonal systems"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Read about tridiagonal systems in TAK § 4.2.2. \n",
"\n",
"Write a function `tridiagonal_solve(a, b, c, r)` to solve a tridiagonal system using Gauss elimination. \n",
"The program should take as input four vectors: A vector $a$ in ${\\mathbb R}^n$ for some $n$, vectors $b$ and $c$ in ${\\mathbb R}^{n-1}$ and $r \\in {\\mathbb R}^n$. The function should return a vector $x$ that solves the equaion $Mx=r$, where $M$ is the $n \\times n$ matrix with $a$ on the diagonal, $b$ above the diagonal, and $c$ below the diagonal. See equation (4.10) on page 94 of TAK. \n",
"\n",
"Test that your function works on a $50 × 50$ system with any diagonal entries of your choice and a right hand\n",
"side so that the exact solution vector is the vector of all ones.\n",
"\n",
"*Hint:* The algorithm is spelled out as algorithm 6 on page 94 of TAK, but be wary of the indexing changed mentioned in the previous problem. You may assume that there are no zero pivots ($a_{i} \\neq 0$) as you row reduce. This is what TAK assumes. You can check your work using the prior problem. For reasonable inputs $a$, $b$, $c$ and $r$, the following test should pass:\n",
"```python\n",
"M = tridiagonal_matrix(a, b, c)\n",
"x = tridiagonal_solve(a, b, c, r)\n",
"assert (np.abs(M @ x - r) < 10**-8).all()\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = np.array([2., 2., 2.])\n",
"b = np.array([1., 1.])\n",
"c = np.array([1., 1.])\n",
"r = np.array([4., 8., 8.])\n",
"M = tridiagonal_matrix(a, b, c)\n",
"x = tridiagonal_solve(a, b, c, r)\n",
"assert (np.abs(M @ x - r) < 10**-8).all()\n",
"print(\"Passed!\")\n",
"# The solution should be [1 2 3]\n",
"print(x)"
]
}
],
"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.8.5"
}
},
"nbformat": 4,
"nbformat_minor": 4
}