{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Eliminate from (general) A to (upper triangular) U" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Demonstrate Gaussian Elimination (page 51 of GS)\n", "\n", "(Reminder: Julia programming syntax will not be tested in this class, but that doesn't mean you can't learn from\n", "watching the code being executed)\n", "\n", "(If you are familiar with Jupyter notebooks and wish to execute yourself, you can download this notebook \n", "using the download button in the upper right, but WARNING: right click to \"download as\", or OPTION-click (MAC) or ALT-Click (Linux and Windows I think) on the download icon, or you won't get an ipynb file.) You can then drag into Jupyter." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "using Plots" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "lookat (generic function with 1 method)" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# nice viz for matrices\n", "function lookat(A; redrow=0, rounding=2, showtext=true)\n", " n = size(A,1)\n", " plot(legend=false, axis=false)\n", " rowcolor = redrow > 0 ? :red : :black \n", " for i=1:n, j=1:n \n", " scatter!( [j],[i], ann= showtext ? (j,i,round(A[i,j],digits=rounding), :white ) : (j,i,\"\") ,\n", " color=abs(A[i,j]) > .0001 ? (i==redrow ? rowcolor : :black) : :white, \n", " marker=:square, markersize=30, aspectratio=1, yflip=true, yaxis=[.5,n+.5],xaxis=[.5,n+.5])\n", " end\n", " plot!()\n", "end" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4×4 Array{Float64,2}:\n", " 4.0 9.0 4.0 9.0\n", " 4.0 7.0 6.0 6.0\n", " 2.0 9.0 8.0 6.0\n", " 7.0 1.0 6.0 8.0" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = rand(1.0:9,4,4)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4×4 Array{Float64,2}:\n", " 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = fill(0.0,4,4)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lookat(A)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## What multiple of row 1 must we subtract from row 2 to zero out the (2,1) entry?" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1.0" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L[2,1] = A[2,1] / A[1,1]" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# A[2,:] = A[2,:] - L[2,1] * A[1,:]\n", "A[2,:] -= L[2,1] * A[1,:] # subtract that multiple of the first row from the second\n", "lookat(A, redrow=2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## What multiple of row 1 must we subtract from row 3 to zero out the (3,1) entry?" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.5" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L[3,1] = A[3,1] / A[1,1]" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A[3,:] -= L[3,1] * A[1,:]\n", "lookat(A, redrow=3)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L[4,1] = A[4,1] / A[1,1]\n", "A[4,:] -= L[4,1] * A[1,:]\n", "lookat(A, redrow=4)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-2.25" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L[3,2] = A[3,2] / A[2,2]" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A[3,:] -= L[3,2] * A[2,:]; lookat(A, redrow=3)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L[4,2] = A[4,2] / A[2,2]; A[4,:] -= L[4,2] * A[2,:]; lookat(A, redrow=4)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "n = 5\n", "A = randn(n,n)\n", "L = fill(0.0,n,n)\n", "display(lookat(A))\n", "for j=1:n, i=(j+1):n\n", " L[i,j] = A[i,j]/A[j,j]\n", " A[i,:] -= L[i,j] * A[j,:]\n", " display(lookat(A,redrow=i))\n", "end" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "n = 5\n", "A = randn(n,n)\n", "L = fill(0.0,n,n)\n", "Akeep = [copy(A)]\n", "row = [0]\n", "display(lookat(A))\n", "for j=1:n, i=(j+1):n\n", " L[i,j] = A[i,j]/A[j,j]\n", " A[i,:] -= L[i,j] * A[j,:]\n", " push!(Akeep,copy(A))\n", " push!(row,i)\n", "end" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "
\n", " Unable to load WebIO. Please make sure WebIO works for your Jupyter client.\n", " For troubleshooting, please see \n", " the WebIO/IJulia documentation.\n", " \n", "
\n" ], "text/plain": [ "HTML{String}(\"\\n\\n Unable to load WebIO. Please make sure WebIO works for your Jupyter client.\\n For troubleshooting, please see \\n the WebIO/IJulia documentation.\\n \\n
\\n\")" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "using Interact" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "application/vnd.webio.node+json": { "children": [ { "children": [ { "children": [ { "children": [ { "children": [ { "children": [ "" ], "instanceArgs": { "namespace": "html", "tag": "label" }, "nodeType": "DOM", "props": { "className": "interact ", "style": { "padding": "5px 10px 0px 10px" } }, "type": "node" } ], "instanceArgs": { "namespace": "html", "tag": "div" }, "nodeType": "DOM", "props": { "className": "interact-flex-row-left" }, "type": "node" }, { "children": [ { "children": [], "instanceArgs": { "namespace": "html", "tag": "input" }, "nodeType": "DOM", "props": { "attributes": { "data-bind": "numericValue: index, valueUpdate: 'input', event: {change: function (){this.changes(this.changes()+1)}}", "orient": "horizontal", "type": "range" }, "className": "slider slider is-fullwidth", "max": 11, "min": 1, "step": 1, "style": {} }, "type": "node" } ], "instanceArgs": { "namespace": "html", "tag": "div" }, "nodeType": "DOM", "props": { "className": "interact-flex-row-center" }, "type": "node" }, { "children": [ { "children": [], "instanceArgs": { "namespace": "html", "tag": "p" }, "nodeType": "DOM", "props": { "attributes": { "data-bind": "text: formatted_val" } }, "type": "node" } ], "instanceArgs": { "namespace": "html", "tag": "div" }, "nodeType": "DOM", "props": { "className": "interact-flex-row-right" }, "type": "node" } ], "instanceArgs": { "namespace": "html", "tag": "div" }, "nodeType": "DOM", "props": { "className": "interact-flex-row interact-widget" }, "type": "node" } ], "instanceArgs": { "handlers": { "changes": [ "(function (val){return (val!=this.model[\"changes\"]()) ? (this.valueFromJulia[\"changes\"]=true, this.model[\"changes\"](val)) : undefined})" ], "index": [ "(function (val){return (val!=this.model[\"index\"]()) ? (this.valueFromJulia[\"index\"]=true, this.model[\"index\"](val)) : undefined})" ] }, "id": "17084213940907812968", "imports": { "data": [ { "name": "knockout", "type": "js", "url": "/assetserver/2618192f019dfcc40a9013ef31cb09a511d8ea26-knockout.js" }, { "name": "knockout_punches", "type": "js", "url": "/assetserver/df29ad18e8884e98d1d36dd0c339f642f729bf96-knockout_punches.js" }, { "name": null, "type": "js", "url": "/assetserver/860bb4a9e1927248d6fb4a7d59e926f541e3bfc2-all.js" }, { "name": null, "type": "css", "url": "/assetserver/4b164c07c3632d5e274899a8ab8726c70dab4aff-style.css" }, { "name": null, "type": "css", "url": "/assetserver/67252656a23d4f0f6f4ba7ab8e8eb9ffc4ae9b5d-bulma_confined.min.css" } ], "type": "async_block" }, "mount_callbacks": [ "function () {\n var handler = (function (ko, koPunches) {\n ko.punches.enableAll();\n ko.bindingHandlers.numericValue = {\n init: function(element, valueAccessor, allBindings, data, context) {\n var stringified = ko.observable(ko.unwrap(valueAccessor()));\n stringified.subscribe(function(value) {\n var val = parseFloat(value);\n if (!isNaN(val)) {\n valueAccessor()(val);\n }\n });\n valueAccessor().subscribe(function(value) {\n var str = JSON.stringify(value);\n if ((str == \"0\") && ([\"-0\", \"-0.\"].indexOf(stringified()) >= 0))\n return;\n if ([\"null\", \"\"].indexOf(str) >= 0)\n return;\n stringified(str);\n });\n ko.applyBindingsToNode(\n element,\n {\n value: stringified,\n valueUpdate: allBindings.get('valueUpdate'),\n },\n context,\n );\n }\n };\n var json_data = {\"formatted_vals\":[\"1\",\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\",\"10\",\"11\"],\"changes\":WebIO.getval({\"name\":\"changes\",\"scope\":\"17084213940907812968\",\"id\":\"ob_10\",\"type\":\"observable\"}),\"index\":WebIO.getval({\"name\":\"index\",\"scope\":\"17084213940907812968\",\"id\":\"ob_09\",\"type\":\"observable\"})};\n var self = this;\n function AppViewModel() {\n for (var key in json_data) {\n var el = json_data[key];\n this[key] = Array.isArray(el) ? ko.observableArray(el) : ko.observable(el);\n }\n \n [this[\"formatted_val\"]=ko.computed( function(){\n return this.formatted_vals()[parseInt(this.index())-(1)];\n }\n,this)]\n [this[\"changes\"].subscribe((function (val){!(this.valueFromJulia[\"changes\"]) ? (WebIO.setval({\"name\":\"changes\",\"scope\":\"17084213940907812968\",\"id\":\"ob_10\",\"type\":\"observable\"},val)) : undefined; return this.valueFromJulia[\"changes\"]=false}),self),this[\"index\"].subscribe((function (val){!(this.valueFromJulia[\"index\"]) ? (WebIO.setval({\"name\":\"index\",\"scope\":\"17084213940907812968\",\"id\":\"ob_09\",\"type\":\"observable\"},val)) : undefined; return this.valueFromJulia[\"index\"]=false}),self)]\n \n }\n self.model = new AppViewModel();\n self.valueFromJulia = {};\n for (var key in json_data) {\n self.valueFromJulia[key] = false;\n }\n ko.applyBindings(self.model, self.dom);\n}\n);\n (WebIO.importBlock({\"data\":[{\"name\":\"knockout\",\"type\":\"js\",\"url\":\"/assetserver/2618192f019dfcc40a9013ef31cb09a511d8ea26-knockout.js\"},{\"name\":\"knockout_punches\",\"type\":\"js\",\"url\":\"/assetserver/df29ad18e8884e98d1d36dd0c339f642f729bf96-knockout_punches.js\"}],\"type\":\"async_block\"})).then((imports) => handler.apply(this, imports));\n}\n" ], "observables": { "changes": { "id": "ob_10", "sync": false, "value": 0 }, "index": { "id": "ob_09", "sync": true, "value": 1 } }, "systemjs_options": null }, "nodeType": "Scope", "props": {}, "type": "node" } ], "instanceArgs": { "namespace": "html", "tag": "div" }, "nodeType": "DOM", "props": { "className": "field interact-widget" }, "type": "node" }, { "children": [ { "children": [], "instanceArgs": { "id": "ob_16", "name": "obs-node" }, "nodeType": "ObservableNode", "props": {}, "type": "node" } ], "instanceArgs": { "handlers": {}, "id": "12708210615104101939", "imports": { "data": [], "type": "async_block" }, "mount_callbacks": [], "observables": { "obs-node": { "id": "ob_16", "sync": false, "value": { "children": [ { "children": [], "instanceArgs": { "namespace": "html", "tag": "div" }, "nodeType": "DOM", "props": { "setInnerHtml": "\n\n" }, "type": "node" } ], "instanceArgs": { "namespace": "html", "tag": "div" }, "nodeType": "DOM", "props": { "className": "interact-flex-row interact-widget" }, "type": "node" } } }, "systemjs_options": null }, "nodeType": "Scope", "props": {}, "type": "node" } ], "instanceArgs": { "namespace": "html", "tag": "div" }, "nodeType": "DOM", "props": {}, "type": "node" }, "text/html": [ "