{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " 線形代数(Linear Algebra I) \n", "
\n", "
\n", " cc by Shigeto R. Nishitani, 2018-03-15 \n", "
\n", "\n", "* file: /Users/bob/python/doing_math_with_python/linear_algebra/LA-I.ipynb" ] }, { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "

1  LU 分解
2  連立方程式，掃き出しとplot
2.1  拡大係数行列の作成と掃き出し(LU分解)
2.2  3次元の連立方程式の意味とplot
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# LU 分解\n", "\n", "連立方程式を解くときには，**ガウスの掃き出し法(Gaussian elimination)**が利用される．\n", "これはalgorithmとしてはlower, upper triangle matrixに\n", "分ける操作から**LU分解(LU decomposition)**と呼ばれる．\n", "\n", "* **階段行列(echelon form)**は左側に連続して0が並んでいて，行とともにその数が増えていく行列\n", "* r+1以下の行の成分が全て0であるとき，**階数(rank)**がrであるという．\n", "* **係数行列**$A$，**拡大係数行列**$[Ab]$\n", "* 連立一次方程式，\n", "* 解の存在定理$rank[Ab]=rank A$\n", "* $n$次正方行列が**正則(regular)**，**次数**と階数が一致する行列$rank A = n$．連立方程式がただ1組の解を持つ条件．\n", "* **同次連立一次方程式**　$Ax = 0$\n", "* **自明解**$x=0$，**非自明解**$x \\neq 0$，\n", "* 連立方程式$Ax=b$の**一般解**$x$について，$x=x_0+\\alpha x_1+\\beta x_2$としたときの$x_0$が**特殊解**，$x_1, x_2$は**同伴な同次連立方程式**$Ax=0$の**基本解**．$x$はそれらの**線型結合(linear combination)**で表されている．" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 連立方程式，掃き出しとplot\n", "\n", "![LA-I](./figs/LinearAlgebra-I.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 拡大係数行列の作成と掃き出し(LU分解)" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[1 1]\n", " [2 4]]\n", "[[ 0. 1.]\n", " [ 1. 0.]]\n", "[[ 1. 0. ]\n", " [ 0.5 1. ]]\n", "[[ 2. 4.]\n", " [ 0. -1.]]\n" ] } ], "source": [ "import numpy as np\n", "import scipy.linalg\n", "np.set_printoptions(precision=3, suppress=True)\n", "a=np.array([[1,1],[2,4]])\n", "print(a)\n", "P, L, U = scipy.linalg.lu(a)\n", "print(P)\n", "print(L)\n", "print(U)" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[ 0. 1.]\n", " [ 1. 0.]]\n", "[[ 1. 0. ]\n", " [ 0.5 1. ]]\n", "[[ 2. 4. 18.]\n", " [ 0. -1. -4.]]\n" ] } ], "source": [ "a=np.array([[1,1],[2,4]])\n", "b = np.array([5,18])\n", "ab = np.column_stack((a,b))\n", "P, L, U = scipy.linalg.lu(ab)\n", "print(P)\n", "print(L)\n", "print(U)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3次元の連立方程式の意味とplot\n", "例えば，次のような連立方程式を解くと\n", "$$\n", "x - y -z = 1 \\\\\n", "x - y +z = -1 \\\\\n", "x + y -z = -1\n", "$$" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[ 1. -1. -1. 1.]\n", " [ 0. 2. 0. -2.]\n", " [ 0. 0. 2. -2.]]\n" ] } ], "source": [ "a=np.array([[1,-1,-1],[1,-1,1],[1,1,-1]])\n", "b = np.array([1,-1,-1])\n", "ab = np.column_stack((a,b))\n", "P, L, U = scipy.linalg.lu(ab)\n", "#print(P)\n", "#print(L)\n", "print(U)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([-1., -1., -1.])" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a=np.array([[1,-1,-1],[1,-1,1],[1,1,-1]])\n", "b = np.array([1,-1,-1])\n", "scipy.linalg.inv(a).dot(b)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "となり，\n", "$$\n", "x=-1, y=-1, z=-1\n", "$$\n", "が得られる．これの意味はつぎのように理解できる．\n", "\n", "まず，先ほどの連立方程式を$z$について形式的に解く．すると，\n", "$$\n", "z = x - y - 1 \\\\\n", "z = -1-x+y \\\\\n", "z = 1+x+y\n", "$$\n", "となる．これをplot3dしてみると次の通り，表示される．" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "application/javascript": [ "/* Put everything inside the global mpl namespace */\n", "window.mpl = {};\n", "\n", "\n", "mpl.get_websocket_type = function() {\n", " if (typeof(WebSocket) !== 'undefined') {\n", " return WebSocket;\n", " } else if (typeof(MozWebSocket) !== 'undefined') {\n", " return MozWebSocket;\n", " } else {\n", " alert('Your browser does not have WebSocket support.' +\n", " 'Please try Chrome, Safari or Firefox ≥ 6. ' +\n", " 'Firefox 4 and 5 are also supported but you ' +\n", " 'have to enable WebSockets in about:config.');\n", " };\n", "}\n", "\n", "mpl.figure = function(figure_id, websocket, ondownload, parent_element) {\n", " this.id = figure_id;\n", "\n", " this.ws = websocket;\n", "\n", " this.supports_binary = (this.ws.binaryType != undefined);\n", "\n", " if (!this.supports_binary) {\n", " var warnings = document.getElementById(\"mpl-warnings\");\n", " if (warnings) {\n", " warnings.style.display = 'block';\n", " warnings.textContent = (\n", " \"This browser does not support binary websocket messages. \" +\n", " \"Performance may be slow.\");\n", " }\n", " }\n", "\n", " this.imageObj = new Image();\n", "\n", " this.context = undefined;\n", " this.message = undefined;\n", " this.canvas = undefined;\n", " this.rubberband_canvas = undefined;\n", " this.rubberband_context = undefined;\n", " this.format_dropdown = undefined;\n", "\n", " this.image_mode = 'full';\n", "\n", " this.root = $('
');\n", " this._root_extra_style(this.root)\n", " this.root.attr('style', 'display: inline-block');\n", "\n", " $(parent_element).append(this.root);\n", "\n", " this._init_header(this);\n", " this._init_canvas(this);\n", " this._init_toolbar(this);\n", "\n", " var fig = this;\n", "\n", " this.waiting = false;\n", "\n", " this.ws.onopen = function () {\n", " fig.send_message(\"supports_binary\", {value: fig.supports_binary});\n", " fig.send_message(\"send_image_mode\", {});\n", " if (mpl.ratio != 1) {\n", " fig.send_message(\"set_dpi_ratio\", {'dpi_ratio': mpl.ratio});\n", " }\n", " fig.send_message(\"refresh\", {});\n", " }\n", "\n", " this.imageObj.onload = function() {\n", " if (fig.image_mode == 'full') {\n", " // Full images could contain transparency (where diff images\n", " // almost always do), so we need to clear the canvas so that\n", " // there is no ghosting.\n", " fig.context.clearRect(0, 0, fig.canvas.width, fig.canvas.height);\n", " }\n", " fig.context.drawImage(fig.imageObj, 0, 0);\n", " };\n", "\n", " this.imageObj.onunload = function() {\n", " this.ws.close();\n", " }\n", "\n", " this.ws.onmessage = this._make_on_message_function(this);\n", "\n", " this.ondownload = ondownload;\n", "}\n", "\n", "mpl.figure.prototype._init_header = function() {\n", " var titlebar = $(\n", " '
');\n", " var titletext = $(\n", " '
');\n", " titlebar.append(titletext)\n", " this.root.append(titlebar);\n", " this.header = titletext[0];\n", "}\n", "\n", "\n", "\n", "mpl.figure.prototype._canvas_extra_style = function(canvas_div) {\n", "\n", "}\n", "\n", "\n", "mpl.figure.prototype._root_extra_style = function(canvas_div) {\n", "\n", "}\n", "\n", "mpl.figure.prototype._init_canvas = function() {\n", " var fig = this;\n", "\n", " var canvas_div = $('
');\n", "\n", " canvas_div.attr('style', 'position: relative; clear: both; outline: 0');\n", "\n", " function canvas_keyboard_event(event) {\n", " return fig.key_event(event, event['data']);\n", " }\n", "\n", " canvas_div.keydown('key_press', canvas_keyboard_event);\n", " canvas_div.keyup('key_release', canvas_keyboard_event);\n", " this.canvas_div = canvas_div\n", " this._canvas_extra_style(canvas_div)\n", " this.root.append(canvas_div);\n", "\n", " var canvas = $('');\n", " canvas.addClass('mpl-canvas');\n", " canvas.attr('style', \"left: 0; top: 0; z-index: 0; outline: 0\")\n", "\n", " this.canvas = canvas[0];\n", " this.context = canvas[0].getContext(\"2d\");\n", "\n", " var backingStore = this.context.backingStorePixelRatio ||\n", "\tthis.context.webkitBackingStorePixelRatio ||\n", "\tthis.context.mozBackingStorePixelRatio ||\n", "\tthis.context.msBackingStorePixelRatio ||\n", "\tthis.context.oBackingStorePixelRatio ||\n", "\tthis.context.backingStorePixelRatio || 1;\n", "\n", " mpl.ratio = (window.devicePixelRatio || 1) / backingStore;\n", "\n", " var rubberband = $('');\n", " rubberband.attr('style', \"position: absolute; left: 0; top: 0; z-index: 1;\")\n", "\n", " var pass_mouse_events = true;\n", "\n", " canvas_div.resizable({\n", " start: function(event, ui) {\n", " pass_mouse_events = false;\n", " },\n", " resize: function(event, ui) {\n", " fig.request_resize(ui.size.width, ui.size.height);\n", " },\n", " stop: function(event, ui) {\n", " pass_mouse_events = true;\n", " fig.request_resize(ui.size.width, ui.size.height);\n", " },\n", " });\n", "\n", " function mouse_event_fn(event) {\n", " if (pass_mouse_events)\n", " return fig.mouse_event(event, event['data']);\n", " }\n", "\n", " rubberband.mousedown('button_press', mouse_event_fn);\n", " rubberband.mouseup('button_release', mouse_event_fn);\n", " // Throttle sequential mouse events to 1 every 20ms.\n", " rubberband.mousemove('motion_notify', mouse_event_fn);\n", "\n", " rubberband.mouseenter('figure_enter', mouse_event_fn);\n", " rubberband.mouseleave('figure_leave', mouse_event_fn);\n", "\n", " canvas_div.on(\"wheel\", function (event) {\n", " event = event.originalEvent;\n", " event['data'] = 'scroll'\n", " if (event.deltaY < 0) {\n", " event.step = 1;\n", " } else {\n", " event.step = -1;\n", " }\n", " mouse_event_fn(event);\n", " });\n", "\n", " canvas_div.append(canvas);\n", " canvas_div.append(rubberband);\n", "\n", " this.rubberband = rubberband;\n", " this.rubberband_canvas = rubberband[0];\n", " this.rubberband_context = rubberband[0].getContext(\"2d\");\n", " this.rubberband_context.strokeStyle = \"#000000\";\n", "\n", " this._resize_canvas = function(width, height) {\n", " // Keep the size of the canvas, canvas container, and rubber band\n", " // canvas in synch.\n", " canvas_div.css('width', width)\n", " canvas_div.css('height', height)\n", "\n", " canvas.attr('width', width * mpl.ratio);\n", " canvas.attr('height', height * mpl.ratio);\n", " canvas.attr('style', 'width: ' + width + 'px; height: ' + height + 'px;');\n", "\n", " rubberband.attr('width', width);\n", " rubberband.attr('height', height);\n", " }\n", "\n", " // Set the figure to an initial 600x600px, this will subsequently be updated\n", " // upon first draw.\n", " this._resize_canvas(600, 600);\n", "\n", " // Disable right mouse context menu.\n", " $(this.rubberband_canvas).bind(\"contextmenu\",function(e){\n", " return false;\n", " });\n", "\n", " function set_focus () {\n", " canvas.focus();\n", " canvas_div.focus();\n", " }\n", "\n", " window.setTimeout(set_focus, 100);\n", "}\n", "\n", "mpl.figure.prototype._init_toolbar = function() {\n", " var fig = this;\n", "\n", " var nav_element = $('
')\n", " nav_element.attr('style', 'width: 100%');\n", " this.root.append(nav_element);\n", "\n", " // Define a callback function for later on.\n", " function toolbar_event(event) {\n", " return fig.toolbar_button_onclick(event['data']);\n", " }\n", " function toolbar_mouse_event(event) {\n", " return fig.toolbar_button_onmouseover(event['data']);\n", " }\n", "\n", " for(var toolbar_ind in mpl.toolbar_items) {\n", " var name = mpl.toolbar_items[toolbar_ind][0];\n", " var tooltip = mpl.toolbar_items[toolbar_ind][1];\n", " var image = mpl.toolbar_items[toolbar_ind][2];\n", " var method_name = mpl.toolbar_items[toolbar_ind][3];\n", "\n", " if (!name) {\n", " // put a spacer in here.\n", " continue;\n", " }\n", " var button = $('