{ "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 watching the code being executed)" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "using Plots" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "lookat (generic function with 1 method)" ] }, "execution_count": 4, "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": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4×4 Array{Float64,2}:\n", " 2.0 12.0 4.0 7.0\n", " 29.0 12.0 69.0 24.0\n", " 7.0 7.0 7.0 7.0\n", " 3.0 7.0 5.0 2.0" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = [2 12 4 7; 29 12 69 24 ; 7 7 7 7; 3 7 5 2]\n", "A = A*1.0" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lookat(A)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## What multiple of the first row must i subtract from the second row to zero out the (2,1) entry?" ] }, { "cell_type": "code", "execution_count": 6, "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": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = fill(0.0, 4,4)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "14.5" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L[2,1] = A[2,1]/A[1,1]" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A[2,:] -= L[2,1]*A[1,:]; # subtract the multiplier times the first row from the second row\n", "lookat(A, redrow=2)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3.5" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L[3,1] = A[3,1]/A[1,1] # the diagonal entry that we divide by is called the \"pivot\"" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A[3,:] -= L[3,1]*A[1,:]; # subtract the multiplier times the first row from the second row\n", "lookat(A, redrow=3)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L[4,1] = A[4,1]/A[1,1] \n", "A[4,:] -= L[4,1]*A[1,:]; # subtract the multiplier times the first row from the second row\n", "lookat(A, redrow=4)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L[3,2] = A[3,2]/A[2,2] \n", "A[3,:] -= L[3,2]*A[2,:]; # subtract the multiplier times the first row from the second row\n", "lookat(A, redrow=3)" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L[4,2] = A[4,2]/A[2,2] \n", "A[4,:] -= L[4,2]*A[2,:]; # subtract the multiplier times the first row from the second row\n", "lookat(A, redrow=4)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L[4,3] = A[4,3]/A[3,3] \n", "A[4,:] -= L[4,3]*A[3,:]; # subtract the multiplier times the first row from the second row\n", "lookat(A, redrow=4)" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [], "source": [ "n = 6\n", "A = rand(n,n)\n", "keepA = [copy(A)]\n", "row = [0]\n", "L = fill(0.0,n,n)\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!(keepA,copy(A))\n", " push!(row,i)\n", "end" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [], "source": [ "using Interact" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "application/vnd.webio.node+json": { "children": [ { "children": [ { "children": [ { "children": [ { "children": [ { "children": [ "i" ], "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": 16, "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": "12019567677823032763", "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\",\"12\",\"13\",\"14\",\"15\",\"16\"],\"changes\":WebIO.getval({\"name\":\"changes\",\"scope\":\"12019567677823032763\",\"id\":\"ob_18\",\"type\":\"observable\"}),\"index\":WebIO.getval({\"name\":\"index\",\"scope\":\"12019567677823032763\",\"id\":\"ob_17\",\"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\":\"12019567677823032763\",\"id\":\"ob_18\",\"type\":\"observable\"},val)) : undefined; return this.valueFromJulia[\"changes\"]=false}),self),this[\"index\"].subscribe((function (val){!(this.valueFromJulia[\"index\"]) ? (WebIO.setval({\"name\":\"index\",\"scope\":\"12019567677823032763\",\"id\":\"ob_17\",\"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_18", "sync": false, "value": 0 }, "index": { "id": "ob_17", "sync": true, "value": 8 } }, "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_24", "name": "obs-node" }, "nodeType": "ObservableNode", "props": {}, "type": "node" } ], "instanceArgs": { "handlers": {}, "id": "4433206657539994618", "imports": { "data": [], "type": "async_block" }, "mount_callbacks": [], "observables": { "obs-node": { "id": "ob_24", "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": [ "