{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# ガウス消去法" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 問題\n", "\n", "以下の連立一次方程式$Ax=b$について，\n", "$$\n", "A=\n", "\\left(\n", "\\begin{array}{cccc}\n", "2& 1 & -2 & 3\\\\\n", "2 & 0 & 4 & 1 \\\\\n", "3 & 0 & 5& 2\\\\\n", "1 & -1 & 2 & 1 \n", "\\end{array}\n", "\\right)\n", "\\quad\n", "b=\\left(\n", "\\begin{array}{cccc}\n", "11\\\\\n", "-5\\\\\n", "-5\\\\\n", "-4\n", "\\end{array}\n", "\\right)\n", "$$\n", "1)ガウス消去法によって，$Ax=b$の解を計算しなさい。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 解答" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "一次方程式$Ax=b$の拡大行列は以下である：\n", "$$\n", "(A|b)=\\left(\n", "\\begin{array}{ccccc}\n", "2& 1 & -2 & 3 & 11 \\\\\n", "2 & 0 & 4 & 1 & -5 \\\\\n", "3 & 0 & 5& 2 & -5 \\\\\n", "1 & -1 & 2 & 1 &-4 \n", "\\end{array}\n", "\\right)\n", "$$\n", "$(A|b)$に左から順に次の$E_1$，$E_2$，$E_3$をかけて、\n", "\n", "$$\n", "E_1=\\left(\n", "\\begin{array}{cccc}\n", "1 & 0 & 0 & 0 \\\\\n", "-1 & 1 & 0 & 0 \\\\\n", "-\\frac{3}{2} & 0 & 1 & 0 \\\\\n", "-\\frac{1}{2} & 0 & 0 & 1 \n", "\\end{array}\n", "\\right)\n", ",\n", "\\quad\n", "E_2=\\left(\n", "\\begin{array}{cccc}\n", "1 & 0 & 0 & 0 \\\\\n", "0 & 1 & 0 & 0 \\\\\n", "0 & -\\frac{3}{2} & 1 & 0 \\\\\n", "0 & -\\frac{3}{2} & 0 & 1 \n", "\\end{array}\n", "\\right)\n", ",\n", "\\quad\n", "E_3=\\left(\n", "\\begin{array}{cccc}\n", "1 & 0 & 0 & 0 \\\\\n", "0 & 1 & 0 & 0 \\\\\n", "0 & 0 & 1 & 0 \\\\\n", "0 & 0 & -6 & 1 \n", "\\end{array}\n", "\\right)\n", "$$\n", "\n", "以下の結果となる、\n", "$$\n", "E_1(A|b)=\\left(\n", "\\begin{array}{ccccc}\n", "2& 1 & -2 & 3 & 11 \\\\\n", "0 & -1 & 6 & -2 & -16 \\\\\n", "0 & -\\frac{3}{2} & 8 & -\\frac{5}{2} & -\\frac{43}{2} \\\\\n", "0 & -\\frac{3}{2} & 3 & -\\frac{1}{2} &-\\frac{19}{2} \n", "\\end{array}\n", "\\right)\n", "$$\n", "\n", "$$\n", "E_2E_1(A|b)=\\left(\n", "\\begin{array}{ccccc}\n", "2 & 1 & -2 & 3 & 11 \\\\\n", "0 & -1 & 6 & -2 & -16 \\\\\n", "0 & 0 & -1 & \\frac{1}{2} & \\frac{5}{2} \\\\\n", "0 & 0 & -6 & \\frac{5}{2} & \\frac{29}{2} \n", "\\end{array}\n", "\\right)\n", "$$\n", "\n", "$$\n", "E_3E_2E_1(A|b)=\\left(\n", "\\begin{array}{ccccc}\n", "2& 1 & -2 & 3 & 11 \\\\\n", "0 & -1 & 6 & -2 & -16 \\\\\n", "0 & 0 & -1 & \\frac{1}{2} & \\frac{5}{2} \\\\\n", "0 & 0 & 0 & -\\frac{1}{2} & -\\frac{1}{2} \n", "\\end{array}\n", "\\right)\n", "$$\n", "最後の行列は\n", "$$\n", "2x_1+x_2-2x_3+3x_4=11,~-x_2+6x_3-2x_4=-16,~-x_3+\\frac{1}{2}x_4=\\frac{5}{2},~-\\frac{1}{2}x_4=-\\frac{1}{2}\n", "$$\n", "ということを表しているので、後の方から順に\n", "$$\n", "x_4=1,~x_3=-2,~x_2=2,~x_1=1\n", "$$\n", "と解くことが出来る。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 問題\n", "\n", "2)$A$のLU分解を計算しなさい。消去法の計算途中の作業行列$E_i$を明記しなさい。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 解答" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$A=LU$,ただし、\n", "$$\n", "L:=E_1^{-1}E_2^{-1}E_3^{-1}=\\left(\n", "\\begin{array}{cccc}\n", "1 & 0 & 0 & 0 \\\\\n", "1 & 1 & 0 & 0 \\\\\n", "\\frac{3}{2} & \\frac{3}{2} & 1 & 0 \\\\\n", "\\frac{1}{2} & \\frac{3}{2} & 6 & 1 \n", "\\end{array}\n", "\\right)\n", "$$\n", "\n", "$$\n", "U:=\\left(\n", "\\begin{array}{ccccc}\n", "2& 1 & -2 & 3 \\\\\n", "0 & -1 & 6 & -2 \\\\\n", "0 & 0 & -1 & \\frac{1}{2} \\\\\n", "0 & 0 & 0 & -\\frac{1}{2} \n", "\\end{array}\n", "\\right)\n", "$$\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# ガウス消去法のプログラム" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$Ax=b$の解を求めるガウス消去法のプログラムを書いてください。\n", "プログラムの使用する言語を自由にしてください。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "以下のコードを使って、$Ax=b$の解を求める。" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false, "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "The solution is\r\n", " 1\r\n", " 2\r\n", " -2\r\n", " 1\r\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%記号：\n", "%A(i,j): 行列の第i行、第j列\n", "%x(i), b(i): ベクトルx,bの第i成分\n", "%B:方程式の拡大行列\n", "%RowNumber, ColNumber: Aの行の数、列の数\n", "EPSILON = 1E-10; %極小の数\n", "%行列Aを下三角形行列Uまで変形する。 bも同時に更新する。\n", "A=[2 1 -2 3;\n", " 2 0 4 1;\n", " 3 0 5 2;\n", " 1 -1 2 1];\n", "b=[11;-5;-5;-4];\n", "B=[A b]; \n", "[RowNumber,ColNumber]=size(A);\n", "x=zeros(RowNumber,1);\n", "for i= 1:RowNumber-1\n", " if (abs(B(i,i))<= EPSILON)\n", " Print \"対角成分が０なので、消去法が終了する。\"\n", " exit\n", " end\n", "%以下はBの第i行のalpha倍を第ｊ行に加える。そうすると、B(j,i)が０になる。\n", " for j=i+1:RowNumber\n", " Scale= B(j,i)/ B(i,i);\n", " B(j,i:ColNumber+1)= B(j,i:ColNumber+1)-Scale* B(i,i:ColNumber+1);\n", " end\n", "end\n", "b=B(1:RowNumber,ColNumber+1);\n", "A=B(1:RowNumber,1:ColNumber);\n", "%後退代入法\n", "x(RowNumber)=b(RowNumber)/A(RowNumber,RowNumber);\n", "for i=RowNumber-1:-1:1\n", " for j=i+1:ColNumber\n", " x(i)=x(i)- A(i,j)*x(j);\n", " end\n", "x(i)=b(i)+x(i);\n", "x(i)=x(i)/A(i,i);\n", "end\n", "disp('The solution is')\n", "disp(x)" ] } ], "metadata": { "kernelspec": { "display_name": "Octave", "language": "octave", "name": "octave_kernel" }, "language_info": { "codemirror_mode": "Octave", "file_extension": ".m", "help_links": [ { "text": "MetaKernel Magics", "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md" } ], "mimetype": "text/x-octave", "name": "octave_kernel" } }, "nbformat": 4, "nbformat_minor": 0 }