{ "metadata": { "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Gaussian Elimination" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this notebook, we walk you through the steps that take you from applying Gauss transforms to a matrix to an algorithm that performs these steps.\n", "\n", " Be sure to make a copy!!!! \n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
laff.invscal( alpha, x )
$x := x / \\alpha$ (See note below)\n",
"laff.axpy( alpha, x, y )
$y := \\alpha x + y$\n",
"laff.ger( alpha, x, y, A )
$A := \\alpha x y^T + A$\n",
"laff.invscal( alpha, x)
was added after the course started. If you're having problems with git and are manually downloading the notebooks, check the wiki page for notebooks for help on getting updated laff routines."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" x[1]
and x[0]
."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"x[ 3 ] = b[ 3 ] / A[ 3,3 ]\n",
"x[ 2 ] = ( b[ 2 ] - A[ 2,3 ] * x[ 3 ] ) / A[ 2,2 ]\n",
"\n",
"# You finish it!"
],
"language": "python",
"metadata": {},
"outputs": []
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print( 'x = ' )\n",
"print( x )\n",
"\n",
"print( 'x - xold' )\n",
"print( x - xold )"
],
"language": "python",
"metadata": {},
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" x - xold
should yield a zero vector"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" GaussianElimination( A )
\n",
"with the Spark webpage for the algorithm given above.\n",
"\n",
"\n",
"\n",
"\n",
"Recall from the explanation that a Gauss transform needs to be computed so that\n",
" ForwardSubstitution_unb( A, b )
\n",
"with the Spark webpage for the algorithm."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# Insert code here"
],
"language": "python",
"metadata": {},
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Apply the Gauss transforms to the right-hand side\n",
"\n",
" Important: if you make a mistake, rerun ALL cells above the cell in which you were working before you rerun the one in which you are working. "
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print( A )\n",
"print( b )\n",
"ForwardSubstitution_unb( A, b )\n",
"\n",
"print( 'updated b' )\n",
"print( b )"
],
"language": "python",
"metadata": {},
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, perform back substitution\n",
"\n",
" Important: if you make a mistake, rerun ALL cells above the cell in which you were working before you rerun the one in which you are working. "
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"x[ 3 ] = b[ 3 ] / A[ 3,3 ]\n",
"x[ 2 ] = ( b[ 2 ] - A[ 2,3 ] * x[ 3 ] ) / A[ 2,2 ]\n",
"x[ 1 ] = ( b[ 1 ] - A[ 1,2 ] * x[ 2 ] - A[ 1,3 ] * x[ 3 ] ) / A[ 1,1 ]\n",
"x[ 0 ] = ( b[ 0 ] - A[ 0,1 ] * x[ 1 ] - A[ 0,2 ] * x[ 2 ]- A[ 0,3 ] * x[ 3 ] ) / A[ 0,0 ]"
],
"language": "python",
"metadata": {},
"outputs": []
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print( 'x = ' )\n",
"print( x )\n",
"\n",
"print( 'x - xold' )\n",
"print( x - xold )"
],
"language": "python",
"metadata": {},
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" x - xold
should yield a zero vector"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}