{"nbformat": 3, "worksheets": [{"metadata": {}, "cells": [{"metadata": {}, "cell_type": "markdown", "source": ["# Coding Back-Substitution"]}, {"outputs": [], "prompt_number": 1, "cell_type": "code", "metadata": {}, "input": ["import numpy as np"], "collapsed": false, "language": "python"}, {"metadata": {}, "cell_type": "markdown", "source": ["Here's an upper-triangular matrix $A$ and two vectors $x$ and $b$ so that $Ax=b$.\n", "\n", "See if you can find $x$ by computation."]}, {"outputs": [{"text": ["[[-1.26236737 -0.8644523   1.55110419 -0.94165954 -0.71166821]\n", " [-0.         -1.89991829 -1.12215066  0.16162471 -0.5094088 ]\n", " [-0.         -0.         -0.52611369  1.03649351 -1.03046035]\n", " [-0.         -0.          0.          0.22869562 -0.45786146]\n", " [-0.         -0.          0.         -0.          0.19889282]]\n", "[ 1.35615426 -0.7539793  -0.04295377  0.12033124 -1.9996183 ]\n"], "stream": "stdout", "output_type": "stream"}], "prompt_number": 11, "cell_type": "code", "metadata": {}, "input": ["n = 5\n", "\n", "A = np.random.randn(n, n) * np.tri(n).T\n", "print(A)\n", "\n", "x = np.random.randn(n)\n", "print(x)\n", "\n", "b = np.dot(A, x)"], "collapsed": false, "language": "python"}, {"outputs": [], "prompt_number": 16, "cell_type": "code", "metadata": {}, "input": ["xcomp = np.zeros(n)\n", "\n", "for i in range(n-1, -1, -1):\n", "    tmp = b[i]\n", "    for j in range(n-1, i, -1):\n", "        tmp -= xcomp[j]*A[i,j]\n", "        \n", "    xcomp[i] = tmp/A[i,i]"], "collapsed": false, "language": "python"}, {"metadata": {}, "cell_type": "markdown", "source": ["Now compare the computed $x$ against the reference solution."]}, {"outputs": [{"text": ["[ 1.35615426 -0.7539793  -0.04295377  0.12033124 -1.9996183 ]\n", "[ 1.35615426 -0.7539793  -0.04295377  0.12033124 -1.9996183 ]\n"], "stream": "stdout", "output_type": "stream"}], "prompt_number": 19, "cell_type": "code", "metadata": {}, "input": ["print(x)\n", "print(xcomp)"], "collapsed": false, "language": "python"}, {"metadata": {}, "cell_type": "markdown", "source": ["Questions/comments:\n", "\n", "* Can this fail?\n", "* What's the operation count?"]}]}], "metadata": {"signature": "sha256:dd587cd93c7152a55a10d17595eff2b2884b42158906c780672645acd341a6d9", "name": ""}, "nbformat_minor": 0}