%=====================================================================
% ���Ĺ��� 5E �׻������ѥƥ�����
%�����ơ��ޡ�����������������ˡ�Υץ�����ߥ�
%    �ܥƥ����Ȥ�����
%��������������������������ˡ
%����������
%        ��
%����
%
% last updated 2004.11.16
%    created by  Masashi Yamamoto
%     e-mail yamamoto@akita-nct.jp
%=====================================================================
\documentclass[10pt,a4paper]{jarticle}
\usepackage{graphicx,amsmath,amssymb,ascmac,verbatim,multirow,bigdelim}
\newcommand{\vm}[1]{\boldsymbol{#1}}
\newcommand{\hugesymbol}[1]{\mbox{\strut\rlap{\smash{\Huge$#1$}}\quad}}
\oddsidemargin 0mm  %����;�� 25.4mm-0mm������ڡ���
\evensidemargin 0mm %����;�� 25.4mm-0mm�������ڡ���
\textwidth 160mm
%
\begin{document}
\title{����������������ˡ�Υץ��������ˡ}
\author{���ܾ���\thanks{��Ω���Ĺ��ȹ�������ع����ŵ����ز�}}
\date{2005ǯ11��11��}
\maketitle
%
%
%=====================================================================
\section{����}
%=====================================================================
%---------------------------------------------------------------------
\subsection{�ؿ���Ȥ���}
%---------------------------------------------------------------------
����������������ˡ�ϡ�ϢΩ1���������β򡤤��뤤�ϵչ�����������Ū�ʼ�ˡ�ǡ�
�����뤳�μ�������Ŭ�ѤǤ��롥�ɤ��ץ�������񤱤С������Ѥ���ΤǤ��롥��
�Τ褦�ˡ������ѤǤ������ʥ롼����ϡ��ᥤ��ؿ��ˤϽ񤫤ʤ��ǡ��ؿ��Ȥ�����ǽ��
�ץ��������Ȥ߹���\footnote{��ä��ɤ��Τϡ��饤�֥�꡼�ˤ��Ƥ��ޤ����ȤǤ��롥
����ϡ��ؽ����ϰϳ��ʤΤǶ�̣�Τ���ͤϡ�Ĵ�٤�}����������ȡ��ۤ��ξ���ϢΩ1
����������򤭤������ϡ����δؿ��򥳡��뤹������ǺѤ�Τǥץ����������μ��
���ʤ��롥�ޤ����ۤ��Υץ�������񤯾��Ǥ⡤����򥳥ԡ����ơ������ѤǤ����
�������Ǥ��롥���������櫓�ǡ��ᥤ��ؿ��ǤϤʤ�������������������ˡ�����Ѥδ�
�����뤳�Ȥ�˾�ޤ��������������ץ�������ʬ����䤹���ʤ롥C����ϴؿ�����
Ω�����⤤�Τǡ������դ����Ū��ñ�ˤǤ��롥

����������������ˡ�����Ѥδؿ������硤�ɤ����뤫?���ޤ���������
���Ϥȵ�ǽ��ͤ��롥���Ϥϡ����������$\vm{A}$����Ʊ�����$\vm{b}$��ɬ�פǤ��롥
�����ơ����Ϥϵչ����$\vm{A}^{-1}$�Ȳ�Υ٥��ȥ�$\vm{x}$�Ȥʤ롥
�פ���ˡ���\ref{fig:����������������ˡ�Υ֥�å��ܥå���}�Τ褦�ʵ�
ǽ�δؿ���Ĥ���櫓�Ǥ��롥

\begin{figure}[hbpt]
 \begin{center}
  \includegraphics[keepaspectratio, scale=1.0]{figure/GaussJordan_BlackBox.eps}
  \caption{��������������ˡ��׻�����C����δؿ��Υ֥�å��ܥå���}
  \label{fig:����������������ˡ�Υ֥�å��ܥå���}
 \end{center}   
\end{figure}

���δؿ����Ǥ���ȡ������򤯻���ɬ�פʷ����������Ʊ��������Ϥ�����
��С��չ���Ȳ��׻����Ƥ���롥����������������
ˡ�μ�³���򡤴ؿ��Ǽ¸�������ˡ�ˤĤ��ơ�����ʹߤ���ǫ���������롥
%
%---------------------------------------------------------------------
\subsection{�ؿ��ؤΥǡ����μ����Ϥ�}
%---------------------------------------------------------------------
%-------------------------------------
\subsubsection{�ͤ��Ϥ�����פ��Ф���}
%-------------------------------------
��ǽ�Ϸ�ޤä��Τǡ��Ĥ��ˡ��ؿ��ؤΥǡ����μ����Ϥ���ͤ��ʤ��ƤϤʤ�ʤ���C��
��Υǡ������Ϥ����ϡ�����ʣ���ʤΤǡ������򤹤롥

�����ʤ�ץ���������Ǥ⡤C����δؿ�(main�ǤϤʤ�)���б������Τ�ͭ�ꡤ����
�ϡ����֥롼����ȸƤФ�Ƥ��롥Ʊ���褦�ʽ����������硤1�Ĥ���Ω���������Υ�
���å��Ȥ��ƤޤȤᡤ�ɤ�����Ǥ⥳���뤹�뤳�Ȥ��Ǥ���褦�ˤ���������Ǥ��롥��
�Τ褦�ʡ���ǽ�Υ֥��å��򥵥֥롼����ȸƤ֡��㤨�С�\texttt{sin(x)}�ʤɤǤ��롥
$\sin x$�η׻���ɬ�פ����١����ν�����񤤤Ƥ����ΤǤϤ��ޤ�ʤ��Τǡ���Ω������
���Ȥ��Ƥ��ν������񤯤ΤǤ��롥����ϡ��饤�֥�꡼�ȤʤäƤ���Τǡ����ν�����
�Ƥ��̾��ʬ����ʤ���

���δؿ��ˡ��ǡ�����Ϳ�����ѿ��Τ��Ȥ�����ȸ�������ۤɤ���Ǹ����ȡ�
\texttt{sin(x)}��\texttt{x}�������Ǥ��롥�ץ���������Ǥϡ�\texttt{sin}�ȸ���
̾�����Ĥ��Ƥ��������\text{x}��Ϳ���������������롥

�����ˤϡ�2����(�°����Ȳ�����)��ͭ�롥����ˤĤ��ơ����Υץ��������������롥
���ξ�硤\texttt{main}�ؿ��ǥ����뤹��Ȥ���ʸ��\texttt{add(x,y)}��\texttt{x}��
\texttt{y}��°����ȸƤ֡������ơ����ν�����񤤤Ƥ���ؿ�\texttt{add(double
xin, double yin)}��\texttt{xin}��\texttt{yin}�򲾰����Ȥ������Ƥ������ѿ���°�
�����ƤФ�������ѿ��򲾰����ȸƤ֤ΤǤ��롥

\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	#include <stdio.h>
	double add(double xin, double yin);

	/* ========== main�ؿ� =================*/
	main(){
	   double x, y, wa;

	   ���������ʽ���
		
	   wa=add(x,y);

	   ���������ʽ���

	}

	/* ========== ­�����δؿ� =================*/
	double add(double xin, double yin){
	   double zout;

	   zout = xin+yin;
	   return(zout);
	}	
 \end{verbatim}
\end{quote}

�°������鲾�������ͤ�������ˡ�ϡ�C����Ǥ�2�̤����ˡ�����롥�����ؽ������̤�ǡ�
%
\begin{description}
 \item[���Ϥ�(Call by value)]{�����뤷��(�ƤӽФ���)�ؿ��Ƚ�������ؿ�
	    �Ǥϡ��̡��Υ��꡼�ΰ���Ѱդ��롥�����ơ������뤷����
	    ���˸ƤӽФ�¦�Υ��꡼(�°���)���ͤ��������ؿ��Υ��꡼
	    (������)�˥��ԡ����롥���äơ���������ؿ������������ͤ�
	    �Ѥ��Ƥ⡤�ƤӽФ�¦�μ°������ͤ��Ѥ�뤳�ȤϤʤ���}
 \item[���ɥ쥹�Ϥ�(Call by reference)]{��������ؿ��Ǥ��ͤ�
	    ��Ǽ������꡼�ΰ���Ѱդ��ʤ����°����ϡ������뤷���ؿ���
	    �°������ͤ���Ǽ����Ƥ�����꡼�Υ��ɥ쥹�Ȥʤ롥��
	    �Υ��ɥ쥹�����������Ϥ���롥���äơ���������ؿ��Ϥ�
	    �Υ��ɥ쥹���Ǽ������꡼�ΰ���Ѱդ�������Ǥ��롥������
	    ��ؿ��ϡ��°����Υ��ɥ쥹�˳�Ǽ����Ƥ����ͤ�������뤳�Ȥ�
	    �ʤ롥���ξ��ϡ��ƤӽФ��줿�ؿ������������ͤ��Ѥ���
	    �ȡ��ƤӽФ�¦�μ°������ͤ��Ѥ��ޤ���}
\end{description}
%
�Ǥ��롥

C����ξ�硤�̾���ѿ�(����Ǥʤ�)�ξ�硤���Ϥ��Ǥ��롥������ɤ��Ǥ������ͤ�
���롥��������ؿ����ƤӽФ�¦�Υǡ������Ѥ��뤳�Ȥ�̵���Τǡ��ץ�����ߥ󥰤λ���
;�פʵ���Ȥ�ʤ��Ǥ��ࡥ�ؿ�����Ω�����⤤�Ȥ������ʤǤ��롥�ºݤ���Ǥϡ�
���\texttt{add}�Ȥ����ؿ��ϡ�\text{main}�ؿ�����ƤӽФ���Ƥ��ꡤ\texttt{main}
�μ°�������\texttt{(x,y)}���ͤ���\texttt{add}�β�����\texttt{(xin,yin)}�˥��ԡ�
����롥�����Ǥν����η�̤ϡ������(�ֵ���)\texttt{zout}��������ơ����δؿ�
���᤹�����δؿ���\texttt{wa}�ˡ�\texttt{zout}���ͤ����ԡ������ΤǤ��롥

������������������ؿ����Ϥ����ϡ����ɥ쥹�Ϥ��ˤʤ롥���̤�����Υǡ����ϡ�
�̾���ѿ����⤫�ʤ��礭��������򤤤��������ԡ����Ƥ������ԷкѤȤ������Ȥ���
ͳ�ȸ����Ƥ��롥

�Ȥ������Ȥǡ�����ξ�硤������Ϥ����ᥢ�ɥ쥹�Ϥ��ˤʤ롥��������ؿ��Ǥ�����
����ͤ��Ѥ���ȡ������뤷���ؿ��Τ����ͤ��Ѥ�롥������������������ʤ��Ȥ⤢�롥
������������ͤ�Ϳ����ɬ�פ�̵�������ڤ˸ƤӽФ����ؿ��˷�̤��᤻��(FORTRAN��Ʊ
��)��

���äơ���\ref{fig:����������������ˡ�Υ֥�å��ܥå���}�Τ褦������
�Ϥδؿ���¸����뤿��ΰ����ν����ϡ�

\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	#include <stdio.h>
	void gaussjordan(double a[][100], double b[100],
	                 double inv_a[][100], double x[100]);

	/* ========== main�ؿ� ==============================================*/
	void main(){
	   double a[100][100], b[100];
	   double inv_a[100][100], x[100];

	   ���������ʽ���
		
	   gaussjordan(a,b,inv_a,x);

	   ���������ʽ���
	}

	/* ========== ��������������ˡ�δؿ� =============================*/
	void gaussjordan(double a[][100], double b[100],
	                 double inv_a[][100], double x[100]){

	���������ʽ���

	inv_a[i][j] = ���������ʷ׻�
	b[i] = �����׻�
	
	���������ʽ���

	}
 \end{verbatim}
\end{quote}

�Ȥʤ롥��������ؿ������ϡ����ֺǽ�Υ�����������ƽ�ɬ�פ����롥����ϡ��㤨
��\texttt{z[100][200][300]}���礭���������\texttt{z[23][73][36]}�Ȥ����ǡ�����
���������������ͤ����ʬ���롥���Υǡ��������륢�ɥ쥹�ϡ�[\texttt{Z}�Υ���
�쥹+����1�ĤΥǡ���������$\times(36+73\times300+23\times200\times300)$]�ˤʤ롥
�������äơ��ǽ������Υ�����������ơ�����Υ����������ɥ쥹�׻���ɬ�פȤʤꡤ
��������ؿ�¦����������ɬ�פ����롥

�ºݤΥץ������Ǥϡ��⤦������Ψ�褯�����Ȥ�������ڤϤ����̤�
�Ǥ��롥����ǡ��ؿ����ͤ�Ϳ���������Ͻ���ꡥ
%
%----------------------------------------
\subsubsection{�����ðۤʾ��ηٹ�}
%----------------------------------------
�⤷��������$\vm{A}$���ðۤ��ȡ���$\vm{x}$�ϰ�դ˷�ޤ�ʤ��Τϡ���������θ���
�Ȥ����Ǥ��롥���ξ�硤����������������ˡ�Ƿ׻�����ؿ��ϡ��ƤӽФ�¦�طٹ��
�Ф��ʤ��ƤϤʤ�ʤ����ƤӽФ�¦�إ������֤����ȤǼ¸��Ǥ��롥����ϡ�
%
\begin{itemize}
 \item{�����ðۤʾ�硤\\
      \qquad \texttt{return(0);}}
 \item{������§�ʾ�硤\\
      \qquad \texttt{return(1);}}
\end{itemize}
%
�Ƚ񤱤��ɤ���
%
%----------------------------------------
\subsubsection{����Υ������Ϥɤ������}
%----------------------------------------
�����ˤ�������Ǥ褤�Τ�?��������������ͤ򡤽�������ץ��������Τ餻�뤳��
���Ǥ��뤬����������Ʒ׻��ν��������ä��櫓�ǤϤʤ��������٥��ȥ�Υ��������
�����Τ餻��ɬ�פ����롥����ϡ��礭��������Ѱդ��Ƥ����ơ����ΰ���ʬ�˷�������
Ʊ������ͤ�����뤿�ᡤ��������Ȥ��˹����٥��ȥ���礭����ɬ�פȤʤ롥���Τ�
������ͳ���顤�����٥��ȥ�Υ��������Ϥ��ʤ��ƤϤʤ�ʤ����������θ����ȡ���
��������������ˡ�δؿ��Υץ��ȥ���������ϡ����Τ褦�ˤʤ롥

\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	int gaussjordan(int n, double a[][100], double b[100],
	                double inv_a[][100], double x[100]);
 \end{verbatim}
\end{quote}

%
%=====================================================================
\section{�ºݤΥץ������(����­���)}
%=====================================================================
�����Ǥϡ��ºݤΥץ��������������Ȥ��ιͤ����򼨤����ǽ�ˡ�
���ˤ�ͤ��Ƥ��ʤ�����������������ˡ�����ȯ�����������ĵ�ǽ���ɲä�
�ơ��ǽ�Ū�˥ѥå������Ȥ��ƴ��������ؿ������������ˤ��롥�ʲ��ν���ǥץ�
������֥�å��奢�åפ��롥
\begin{enumerate}
 \item{$\vm{A}$��ñ�̹���ˤ��롥�����ơ�$\vm{x}$����롥}
 \item{�Ԥ�򴹤�������Υԥܥå�����(��ʬ����)�ε�ǽ���ɲä��롥}
 \item{�չ����׻�����롼������ɲä��롥}
 \item{���פ�������ӽ����ơ����꡼��Ψ��夲���¤�򤹤롥}
\end{enumerate}
%
%---------------------------------------------------------------------
\subsection{���Ѥʥ���������������ˡ(������гѲ��Τ�)}
\label{subsec:simple_gauss_jordan}
%---------------------------------------------------------------------
�ޤ��ϡ�������гѲ��ΤߤΥץ�������������롥����ˤ�ꡤ
$\vm{A}$��ñ�̹�����Ѵ����졤��Ʊ����$\vm{b}$�ϲ�٥��ȥ�$\vm{x}$����
������롥

������Υץ������ϡ��ԥܥå����򤬤ʤ����ᡤ���Ѿ������ޤ�Ƥ��뤬���ǽ�γ�
���Ȥ��Ƥ���ϵ��ˤ��ʤ����Ȥˤ��롥����������������ˡ�Υץ������γؽ��ϴ�ñ
�������ɤ��������󤬡��ؽ��ǤϤʤ��ºݤ˻Ȥ��ץ��������Ȥ�Ȥ��ϥԥܥå������
ɬ���Բķ�ȹͤ��ʤ��ƤϤʤ�ʤ���

����ˡ����Υץ������Ϲ����ðۤʾ��Ǥ⡤�׻���³�Ԥ��褦���롥���ξ�硤��
���ǳ�뤳�Ȥ������ޤ��Τǡ��¹Ի����顼��ȯ������Ǥ�������
%
%------------------------------
\subsubsection{�ǳ��̤Υ롼��}
%------------------------------
$N \times N$�ι���$\vm{A}$���гѲ����뤳�Ȥ�ͤ��롥���ξ�硤
$a_{11},\,a_{22},\,a_{33},\,\cdots,\,a_{NN}$��Ʊ�������гѲ���ʤ�뤳�Ȥˤʤ롥
�Ȥ������Ȥϡ�$N$��Υ롼�פ�ɬ�פǤ��롥�ץ������Ǥϡ��ʲ��Υ롼�׹�¤������
��¦�ǲ�뤳�Ȥˤʤ롥�롼�פβ����ʬ���äƤ����硤forʸ��Ȥ��Τ����̤Ǥ��롥
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	for(ipv=1 ; ipv <= n ; ipv++){

	   �гѲ��ν���

	}
 \end{verbatim}
\end{quote}
%
�����ǡ�\texttt{ipv}���гѲ���������$a_{ipv\,ipv}$��ź������ɽ����
n�Ϲ���Υ������Ǥ��롥
%
%----------------------------------------------
\subsubsection{�г���ʬ��1��(�ԥܥåȹԤν���)}
%----------------------------------------------
���ν����ϡ��г���ʬ��$a_{ipv\,ipv}=1$�ˤ��뤳�ȤǤ��롥$a_{ipv-1\,ipv-1}$�֤Ǥ�
�гѲ��Ǥ��Ƥ��ꡤ������ʬ���гѲ�����Ȥ������ȤǤ����⤷��$ipv=1$�ʤ�кǽ��
�г���ʬ��1�ˤ��뤳�Ȥˤʤ롥�ǽ�Ǥ�������������Ǥ�������Ʊ���褦�˥ץ������
�Ͻ񤫤ʤ��ƤϤʤ�ʤ�����������ˤϡ�
%
\begin{equation*}
 \vm{A} =
  \begin{pmatrix}
   1 & 0 & \ast & \ast & \ast & \ast \\
   0 & 1 & \ast & \ast & \ast & \ast \\
   0 & 0 & \ast & \ast & \ast & \ast \\
   0 & 0 & \ast & \ast & \ast & \ast \\
   0 & 0 & \ast & \ast & \ast & \ast \\
   0 & 0 & \ast & \ast & \ast & \ast \\
  \end{pmatrix}
  \qquad
  \Rightarrow
  \qquad
 \vm{A}^{\prime} =
  \begin{pmatrix}
   1 & 0 & \ast & \ast & \ast & \ast \\
   0 & 1 & \ast & \ast & \ast & \ast \\
   0 & 0 & 1 & \ast^{\prime} & \ast^{\prime} & \ast^{\prime} \\
   0 & 0 & \ast & \ast & \ast & \ast \\
   0 & 0 & \ast & \ast & \ast & \ast \\
   0 & 0 & \ast & \ast & \ast & \ast
  \end{pmatrix}\\
\end{equation*}
%
���ѷ��������ΤǤ��롥��������$\vm{A}$���ѷ�������С�Ʊ�����ˤ����Ʊ����
$\vm{b}$��������ʤ��Ƥʤ�ʤ���

���ؤǤϡ��г���ʬ��1�ˤ��뤿��ˡ����ιԤ��г���ʬ�ǳ�롥��������
����ԥ塼�����Υץ������Ǥ�ͽ��տ���׻����ơ������褸�������ɤ�������
�ԥ塼�����Ͻ�������軻���������դʤΤǸ�Ψ���ɤ�����Ǥ��롥��Ʊ����
$\vm{b}$�α黻��1��Ǥ�������������$\vm{A}$������ʤΤ�$N$��α黻��ɬ
�פˤʤ롥�г���ʬ��1�ˤ�������ϡ����Τ褦�ˤ��롥

\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	inv_pivot = 1.0/a[ipv][ipv];

	for(j=1 ; j <= n ; j++){
	   a[ipv][j] *= inv_pivot;
	}

	b[ipv] *= inv_pivot;
 \end{verbatim}
\end{quote}

\begin{itemize}
 \item{$ipv$�Ԥ�$j$��$j=1,2,3,\cdots,n$��������뤿��ˡ�\texttt{for}ʸ���Ѥ�
      ���롼�פˤʤäƤ��롥}
 \item{\texttt{a[ipv][j] $\leftarrow$ inv\_pivot*a[ipv][j]}���̾C����Ǥ�
      \texttt{a[ipv][j] *= inv\_pivot}�Ƚ񤯡����뤤�ϡ�\texttt{a[ipv][j] =
      inv\_pivot*a[ipv][j]}�Ƚ񤤤Ƥ��ɤ������Ԥ������������ä�������}
\end{itemize}
����ǥԥܥåȤΤ���Ԥν����Ͻ���ꡥ
%
%-------------------------------------------------------------
\subsubsection{�ԥܥåȤΤ������0��(�ԥܥåȹ԰ʳ��ιԤν���)}
%-------------------------------------------------------------
���ϡ��ԥܥåȤ�����԰ʳ��ν����Ǥ��롥����ϡ��ԥܥåȤ�����������ƥ�
���ˤ��뤳�Ȥ�¾�ʤ�ʤ����פ���˼��Τ褦�ˡ���������$\vm{A}$���ѷ����롥
%
\begin{equation*}
 \vm{A} =
  \begin{pmatrix}
   1 & 0 & a_{1\,ipv} & \ast & \ast & \ast \\
   0 & 1 & a_{2\,ipv} & \ast & \ast & \ast \\
   0 & 0 & 1          & \ast & \ast & \ast \\
   0 & 0 & a_{4\,ipv} & \ast & \ast & \ast \\
   0 & 0 & a_{5\,ipv} & \ast & \ast & \ast \\
   0 & 0 & a_{6\,ipv} & \ast & \ast & \ast \\
  \end{pmatrix}
  \qquad
  \Rightarrow
  \qquad
  \vm{A}^{\prime} =
  \begin{pmatrix}
   1 & 0 & 0 & \ast^{\prime} & \ast^{\prime} & \ast^{\prime} \\
   0 & 1 & 0 & \ast^{\prime} & \ast^{\prime} & \ast^{\prime} \\
   0 & 0 & 1 & \ast          & \ast          & \ast          \\
   0 & 0 & 0 & \ast^{\prime} & \ast^{\prime} & \ast^{\prime} \\
   0 & 0 & 0 & \ast^{\prime} & \ast^{\prime} & \ast^{\prime} \\
   0 & 0 & 0 & \ast^{\prime} & \ast^{\prime} & \ast^{\prime} \\
  \end{pmatrix} 
\end{equation*}
%
���Τ褦�˷�������$\vm{A}$���ѷ������롥��������������β�$\vm{x}$
���Ѥ��ʤ��褦�ˡ���Ʊ����$\vm{b}$��Ʊ�����򤹤롥

���Τ褦���ѷ�����Τϴ�ñ�Ǥ��롥�㤨�С�$i$�Ԥ�����������ͤ��롥
$i$�Ԥ򡤥ԥܥåȤΤ���$ipv$�Ԥ�$a_{i\,ipv}$�ܤ�����Τǰ������ɤ��ΤǤ��롥
%
\begin{equation*}
 \begin{array}{@{\,}lcccccccccccl@{\,}}
  \text{$i$��} & \Rightarrow
     &
     & 1 & 0 & a_{i\,ipv} & \ast & \ast & \ast & &
      \qquad & & b_i\\
  %
  \text{$ipv$��} & \Rightarrow
  & -a_{i\,ipv}\times(
     & 0 & 0 & 1           & \ast & \ast & \ast & ) &
             & -a_{i\,ipv} \times & b_{ipv} \\ \hline
%
  \text{$��i$��} & \Rightarrow
     &
     & 1 & 0 & 0           & \ast^\prime & \ast^\prime & \ast^\prime & &
      \qquad & \multicolumn{2}{r}{b_i-a_{i\,ipv}b_{ipv}}\\
 \end{array}
\end{equation*}
%
���ν����μºݤΥץ������ϼ��Τ褦�ˤʤ롥����ǡ�
$i=1,2,3,\cdots,n$��$j=1,2,3,\cdots,n$�����Ƥ�$\vm{A}$����ʬ������򤹤롥

\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	for(i=1 ; i<=n ; i++){
	   if(i != ipv){
	      temp = a[i][ipv];
	      for(j=1 ; j<=n ; j++){
	         a[i][j] -= temp*a[ipv][j];
	      }
	      b[i] -= temp*b[ipv];
	   }
	}
 \end{verbatim}
\end{quote}

\begin{itemize}
 \item{2�Ĥ�\texttt{for}ʸ��$i$��$j$���������롥}
 \item{$ipv$�Ԥ��г���ʬ��1�ˤ��뤳�Ȥǽ������Ѥ�Ǥ���Τǡ����ιԤϽ���
      �򤷤ƤϤʤ�ʤ��������ǡ�\texttt{if}ʸ���Ѥ���$i \neq ipv$�λ������
      �����򤹤�롼���󤬼¹Ԥ����褦�ˤʤäƤ��롥$i=ipv$�λ��ϡ����ν�����
      �Ԥ�ʤ��ΤǤ��롥}
\end{itemize}

������гѲ��ν����Ϥ����ޤ���
%
%-----------------------------------------------------------
\subsubsection{���Ѥʥ���������������ˡ�Υ������ץ������}
%-----------------------------------------------------------
�ʾ��ޤȤ��ȡ��ԥܥå������̵���չ������ʤ��Υ�������������
��ˡ���������롥�����ǡ��ҤȤĵ����դ��Ƥۤ����Τϲ�٥��ȥ�$\vm{x}$
�Τ������������פȤ������ȤǤ��롥��Ʊ��������󤬲�ˤʤäƤ��롥����
�ơ����κǤ����Ѥʥ���������������ˡ�Υץ������ϼ��Τ褦�ˤʤ롥

\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	/* ========== ��������������ˡ�δؿ� =================*/
	void gauss_jordan(int n, double a[][100], double b[]){

	   int ipv, i, j;
	   double inv_pivot, temp;

	   for(ipv=1 ; ipv <= n ; ipv++){

	      /* ---- �г���ʬ=1(�ԥܥåȹԤν���) ---- */
	      inv_pivot = 1.0/a[ipv][ipv];
	      for(j=1 ; j <= n ; j++){
	         a[ipv][j] *= inv_pivot;
	      }
	      b[ipv] *= inv_pivot;

	      /* ---- �ԥܥå���=0(�ԥܥåȹ԰ʳ��ν���) ---- */
	      for(i=1 ; i<=n ; i++){
	         if(i != ipv){
	            temp = a[i][ipv];
	            for(j=1 ; j<=n ; j++){
	               a[i][j] -= temp*a[ipv][j];
	            }
	            b[i] -= temp*b[ipv];
	         }
	      }

	   }
	}
 \end{verbatim}
\end{quote}
%
%---------------------------------------------------------------------
\subsection{�ԥܥå�����ǽ�ɲ�(�Ը�)}
\label{subsec:prtial_pivoting}
%---------------------------------------------------------------------
��ۤɤ����Ѥʥ���������������ˡ�ϡ����Ƥ��������ؿ��ˤʤäƤ��롥�⤷���г���
ʬ�˥��������줿�顤�����ǳ�뤳�Ȥˤʤ��������þ����ΤǤ��롥�����ǡ�������
�褹��ԥܥå������о줹��ΤǤ��롥��äȤ⡤��������β��Ф���Ǥʤ������
���٤���夹�롥

�ԥܥå����򡤤����ǤϹԤθ򴹤Τߤ���ʬ�����ͤ��롥���ν����ϡ�
%
\begin{itemize}
 \item{�ԥܥå���ǡ�������ͤ�õ����}
 \item{������ͤΤ���Ԥ�ԥܥåȹԤȸ򴹤��롥}
\end{itemize}
%
��2�Ĥ���ʬ���鹽������롥�����ϡ���Υץ��������г���ʬ��1�ˤ������������
����ʤ��ƤϤʤ�ʤ���
%
%-------------------------
\subsubsection{������õ��}
%-------------------------
�Ը򴹤Τߤ�Ԥ���ʬ����ξ�硤�ԥܥåȤϥԥܥåȹ԰ʲ��κ����ͤȤ��롥����ϡ�
���ޤǽ����������г���ʬ��1�ˤʤäƤ�����ʬ�������ʤ�����Ǥ��롥
%
\begin{equation*}
 \begin{array}{rrcccccc@{\hspace{5pt}}l}
  \ldelim\{{2}{59pt}[�Ԥθ��Բ�]&
   \ldelim({7}{5pt}[]  
     &1 &0 & \ast & \ast & \ast & \ast &
   \rdelim){7}{5pt}[] \\
   & & 0 &1 & \ast & \ast & \ast & \ast & \\
  \ldelim\{{5}{50pt}[�Ԥθ򴹲�]
   & & 0 &0 & \ast & \ast & \ast & \ast & \\
   & & 0 &0 & \ast & \ast & \ast & \ast & \\
   & & 0 &0 & \ast & \ast & \ast & \ast & \\
   & & 0 &0 & \ast & \ast & \ast & \ast & \\
   & &0 &0 & \ast & \ast & \ast & \ast & \\
 \end{array}
\end{equation*}
%
�����ͤϡ�$ipv$�Ԥ��Ⲽ�ιԤǡ�$ipv$��κ����ͤϡ��ʹߤ˼����ץ�����
��ˤ��õ�����Ȥ��Ǥ��롥�����ͤϡ�\texttt{fabs}�Ȥ����ؿ���������
����Ӥ��뤳�Ȥˤ����롥

�����ǡ��⤷�����ͤ������ξ�硤������ð�(���󼰤�����)�Ȥ������Ȥˤ�
�ꡤ��ϰ��Ū�˷�ޤ�ʤ������ξ�硤�ؿ����ͤȤ��ƥ������֤�������
���Ȥ򥳡��뤷��¦��������Τ��ɤ���

\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	big=0.0;
	for(i=ipv ; i<=n ; i++){
	   if(fabs(a[i][ipv]) > big){
	      big = fabs(a[i][ipv]);
	      pivot_row = i;
	   }
	}
	if(big == 0.0){return(0);}
	row[ipv] = pivot_row;
 \end{verbatim}
\end{quote}

���Υץ������ϡ��ʲ��Τ��Ȥ�ԤäƤ��롥
%
\begin{itemize}
 \item{\texttt{big}�ˤ�����������ͤκ��礬���롥}
 \item{������(�������ԥܥå�)������Ԥϡ�\texttt{pivot\_row}�Ǥ��롥}
 \item{�ԥܥåȤ������ξ�硤������ðۤȤʤ롥���ξ�硤���������Ǥ��ơ�
      �ƤӽФ�¦�˥������֤���������§�ʾ�硤1���֤����Ȥˤ��뤬������Ϥ���
      �ؿ��κǸ�˽񤭤���}
 \item{$ipv$���ܤ˺����ͤˤʤä��Ԥ�����\texttt{row[ipv]}������롥
      ����ϡ���ǻȤ����Ȥˤ��롥}
\end{itemize}
%
%-------------------------
\subsubsection{�Ԥθ�}
%-------------------------
�ԥܥåȤȤ��٤��ͤ������(\texttt{pivot\_row})���狼�ä��Τǡ�$ipv$��
�������ؤ��롥
%
\begin{equation*}
 \vm{A} =
  \begin{pmatrix}
   1 & 0 & \ast & \ast & \ast & \ast \\
   0 & 1 & \ast & \ast & \ast & \ast \\
   0 & 0 & \circledcirc & \circledcirc & \circledcirc & \circledcirc \\
   0 & 0 & \ast & \ast & \ast & \ast \\
   0 & 0 & \circledast  & \circledast  & \circledast  & \circledast \\
   0 & 0 & \ast & \ast & \ast & \ast \\
  \end{pmatrix}
  \qquad
  \Rightarrow
  \qquad
 \vm{A}^{\prime} =
  \begin{pmatrix}
   1 & 0 & \ast & \ast & \ast & \ast \\
   0 & 1 & \ast & \ast & \ast & \ast \\
   0 & 0 & \circledast  & \circledast  & \circledast  & \circledast \\
   0 & 0 & \ast & \ast & \ast & \ast \\
   0 & 0 & \circledcirc & \circledcirc & \circledcirc & \circledcirc \\
   0 & 0 & \ast & \ast & \ast & \ast \\
  \end{pmatrix} 
\end{equation*}
%
�����ؤ��ϡ���������$\vm{A}$����Ʊ����$\vm{b}$��ξ���ˤĤ��ƹԤ���
�ѿ��������ؤ����硤���Ū���ѿ��򵭲������꤬ɬ�פǡ������Ǥϡ�
\texttt{temp}�Ȥ����ѿ���ȤäƤ��롥

����������Ȥ�Ⱥ�����ͤ�$ipv$�Ԥˤ�����ϡ��Ԥ������ؤ��ϹԤ�ʤ���

\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	if(ipv != pivot_row){

	   for(i=1 ; i<=n ; i++){
	      temp = a[ipv][i];
	      a[ipv][i] = a[pivot_row][i];
	      a[pivot_row][i] = temp;
	   }

	   temp = b[ipv];
	   b[ipv] = b[pivot_row];
	   b[pivot_row] = temp;
	
	}
 \end{verbatim}
\end{quote}
%
%------------------------------------------------------------------
\subsubsection{��ʬ�ԥܥå������դ�����������������ˡ�Υ������ץ���
   ���}
\label{subsubsec:source_pivot}
%------------------------------------------------------------------
����\ref{subsec:prtial_pivoting}���ޤȤᡤ
\ref{subsec:simple_gauss_jordan}������Ѥʥ���������������ˡ�Ȥ��碌
��ȡ���ʬ�ԥܥå������դ��Υ���������������ˡ���������롥

\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	/* ========= ��������������ˡ�δؿ�====================== */

	int gauss_jordan(int n, double a[][MAXN+10], double b[]){

	   int ipv, i, j;
	   double inv_pivot, temp;
	   double big;
	   int pivot_row, row[MAXN+10];

	   for(ipv=1 ; ipv <= n ; ipv++){

	      /* ---- ������õ�� ---------------------------- */
	      big=0.0;
	      for(i=ipv ; i<=n ; i++){
	         if(fabs(a[i][ipv]) > big){
	            big = fabs(a[i][ipv]);
	            pivot_row = i;
	         }
	      }
	      if(big == 0.0){return(0);}
	      row[ipv] = pivot_row;

	      /* ---- �Ԥ������ؤ� -------------------------- */
	      if(ipv != pivot_row){
	         for(i=1 ; i<=n ; i++){
	            temp = a[ipv][i];
	            a[ipv][i] = a[pivot_row][i];
	            a[pivot_row][i] = temp;
	         }
	         temp = b[ipv];
	         b[ipv] = b[pivot_row];
	         b[pivot_row] = temp;
	      }

	      /* ---- �г���ʬ=1(�ԥܥåȹԤν���) ---------- */
	      inv_pivot = 1.0/a[ipv][ipv];
	      for(j=1 ; j <= n ; j++){
	         a[ipv][j] *= inv_pivot;
	      }
	      b[ipv] *= inv_pivot;

	      /* ---- �ԥܥå���=0(�ԥܥåȹ԰ʳ��ν���) ---- */
	      for(i=1 ; i<=n ; i++){
	         if(i != ipv){
	            temp = a[i][ipv];
	            for(j=1 ; j<=n ; j++){
	               a[i][j] -= temp*a[ipv][j];
	            }
	            b[i] -= temp*b[ipv];
	         }
	      }

	   }

	   return(1);
	}
 \end{verbatim}
\end{quote}
%
%---------------------------------------------------------------------
\subsection{�չ���׻��롼������ɲ�}
%---------------------------------------------------------------------
�չ����׻�����롼������ɲä��񤷤����ǤϤ��뤬���¤Ϥ��󤸤��Ǥ��롥ñ�̹�
��򡤷�������$\vm{A}$��Ʊ�������򤹤�С�����ϵ����롥��������μ��Ȥ�פ�
�Ф�������������$\vm{A}$��ñ�̹�����ѷ����줿�ʤ�С�����ñ�̹���ϵչ���
���Ѵ������ΤǤ��롥����ϡ���ñ�˼¸��Ǥ��롥
%
\begin{equation*}
\begin{aligned}
 \vm{A} =
  \begin{pmatrix}
   \ast & \ast & \ast & \ast & \ast & \ast \\
   \ast & \ast & \ast & \ast & \ast & \ast \\
   \ast & \ast & \ast & \ast & \ast & \ast \\
   \ast & \ast & \ast & \ast & \ast & \ast \\
   \ast & \ast & \ast & \ast & \ast & \ast \\
   \ast & \ast & \ast & \ast & \ast & \ast \\
  \end{pmatrix}
  \qquad
  &\Rightarrow
  \qquad
 \vm{A}^{\prime} =
  \begin{pmatrix}
   1 & 0 & 0 & 0 & 0 & 0 \\
   0 & 1 & 0 & 0 & 0 & 0 \\
   0 & 0 & 1 & 0 & 0 & 0 \\
   0 & 0 & 0 & 1 & 0 & 0 \\
   0 & 0 & 0 & 0 & 1 & 0 \\
   0 & 0 & 0 & 0 & 0 & 1 \\
  \end{pmatrix} \\ \\
 %------------------------
 \vm{A}^{-1^\prime} =
  \begin{pmatrix}
   1 & 0 & 0 & 0 & 0 & 0 \\
   0 & 1 & 0 & 0 & 0 & 0 \\
   0 & 0 & 1 & 0 & 0 & 0 \\
   0 & 0 & 0 & 1 & 0 & 0 \\
   0 & 0 & 0 & 0 & 1 & 0 \\
   0 & 0 & 0 & 0 & 0 & 1 \\
 \end{pmatrix}
 \qquad
 &\Rightarrow
 \qquad
 \vm{A}^{-1} =
  \begin{pmatrix}
   \star & \star & \star & \star & \star & \star \\
   \star & \star & \star & \star & \star & \star \\
   \star & \star & \star & \star & \star & \star \\
   \star & \star & \star & \star & \star & \star \\
   \star & \star & \star & \star & \star & \star \\
   \star & \star & \star & \star & \star & \star \\
  \end{pmatrix}
\end{aligned}
\end{equation*}
%

�����¸����뤿��ˤϡ��ʲ���2�ĤΤ��Ȥ򤹤�Ф褤�����Ǥ��롥
\begin{itemize}
 \item{ñ�̹����������롥}
 \item{�������줿ñ�̹���򡤷�������$\vm{A}$��Ʊ�����򤹤롥}
\end{itemize}
%
%-----------------------------
\subsubsection{ñ�̹���κ���}
%-----------------------------
�ޤ���ñ�̹����������롥����ϡ��ʲ��Τ褦�ˤ���Ф褤�Ǥ�������

\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	for(i=1 ; i<=n ; i++){
	   for(j=1 ; j<=n ; j++){
	      if(i == j){
	         inv_a[i][j]=1.0;
	      }else{
	         inv_a[i][j]=0.0;
	      }
	   }
	}
 \end{verbatim}
\end{quote}
%
%-----------------------------
\subsubsection{�չ���η׻�}
%-----------------------------
ñ�̹���\texttt{inv\_a}���Ǥ����Τǡ�����򷸿�����$\vm{A}$��Ʊ������
�򤹤�С��չ�����Ѵ��Ǥ����롥����Ū�ˤϡ�
\ref{subsubsec:source_pivot}��Υץ�������ʲ��Τ褦�˽񤭴����롥
%
\begin{itemize}
 \item{��ʬ�ԥܥå�����Ƿ�������ιԤθ򴹤�Ԥä��ʤ�С�Ʊ���褦��
      \texttt{inv\_a}��Ԥθ򴹤�Ԥ���������ʬ�ν�����\\
      %
      \begin{quote}
       \setlength{\baselineskip}{12pt}
       \begin{verbatim}
	temp = a[ipv][i];
	a[ipv][i] = a[pivot_row][i];
	a[pivot_row][i] = temp;          	
	temp = inv_a[ipv][i];                 /* -- �����ɲ� -- */
	inv_a[ipv][i] = inv_a[pivot_row][i];  /* -- �����ɲ� -- */
	inv_a[pivot_row][i] = temp;           /* -- �����ɲ� -- */
       \end{verbatim}
      \end{quote}
      %
      �Ƚ񤭴����ޤ���}
      %
 \item{�г���ʬ��1�ˤ��뤿��˥ԥܥåȹԤ�ԥܥåȤ��ͤǳ��Ȥ����Ǥϡ�
      Ʊ���ͤǳ�롥����⡤\\
      %
      \begin{quote}
       \setlength{\baselineskip}{12pt}
       \begin{verbatim}
	a[ipv][j] *= inv_pivot;
	inv_a[ipv][j] *= inv_pivot;          /* -- �����ɲ� -- */
       \end{verbatim}
      \end{quote}
      %
      �Ƚ񤭴����롥}
      %
 \item{�ԥܥåȹ԰ʳ��Υԥܥå����0�ˤ��뤿��ˡ��ԥܥåȹԤ�����ܤ�
      �����Ȥ����Ǥ�Ʊ�����򤹤롥����⡤\\
      %
      \begin{quote}
       \setlength{\baselineskip}{12pt}
       \begin{verbatim}
	a[i][j] -= temp*a[ipv][j];
	inv_a[i][j] -= temp*inv_a[ipv][j];   /* -- �����ɲ� -- */
       \end{verbatim}
      \end{quote}
      %
      �Ƚ񤭴����롥}
\end{itemize}
%
%-------------------------------------------------------------------
\subsubsection{�չ���׻��դ�����������������ˡ�Υ������ץ������}
\label{subsubsec:source_inverse}
%-------------------------------------------------------------------
���ޤޤǽҤ٤����Ȥ��������夷������������������ˡ�η׻��δؿ��ϡ���
�Τ褦�ˤʤ롥
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	/* ========= ��������������ˡ�δؿ�====================== */

	int gauss_jordan(int n, double a[][MAXN+10], double b[],
	                 double inv_a[][MAXN+10]){

	   int ipv, i, j;
	   double inv_pivot, temp;
	   double big;
	   int pivot_row, row[MAXN+10];

	   /* ---- ñ�̹������ ---------------------------- */
	   for(i=1 ; i<=n ; i++){
	      for(j=1 ; j<=n ; j++){
	         if(i==j){
	            inv_a[i][j]=1.0;
	         }else{
	            inv_a[i][j]=0.0;
	         }
	      }
	   }

	   for(ipv=1 ; ipv <= n ; ipv++){

	      /* ---- ������õ�� ---------------------------- */
	      big=0.0;
	      for(i=ipv ; i<=n ; i++){
	         if(fabs(a[i][ipv]) > big){
	            big = fabs(a[i][ipv]);
	            pivot_row = i;
	         }
	      }
	      if(big == 0.0){return(0);}	
	      row[ipv] = pivot_row;

	      /* ---- �Ԥ������ؤ� -------------------------- */
	      if(ipv != pivot_row){
	         for(i=1 ; i<=n ; i++){
	            temp = a[ipv][i];
	            a[ipv][i] = a[pivot_row][i];
	            a[pivot_row][i] = temp;          	
	            temp = inv_a[ipv][i];
	            inv_a[ipv][i] = inv_a[pivot_row][i];
	            inv_a[pivot_row][i] = temp;
	         }
	         temp = b[ipv];
	         b[ipv] = b[pivot_row];
	         b[pivot_row] = temp;
	      }

	      /* ---- �г���ʬ=1(�ԥܥåȹԤν���) ---------- */
	      inv_pivot = 1.0/a[ipv][ipv];
	      for(j=1 ; j <= n ; j++){
	         a[ipv][j] *= inv_pivot;
	         inv_a[ipv][j] *= inv_pivot;          
	      }
	      b[ipv] *= inv_pivot;

	      /* ---- �ԥܥå���=0(�ԥܥåȹ԰ʳ��ν���) ---- */
	      for(i=1 ; i<=n ; i++){
	         if(i != ipv){
	            temp = a[i][ipv];
	            for(j=1 ; j<=n ; j++){
	               a[i][j] -= temp*a[ipv][j];
	               inv_a[i][j] -= temp*inv_a[ipv][j];                	
	            }
	            b[i] -= temp*b[ipv];
	         }
	      }

	   }

	   return(1);
	}
       \end{verbatim}
      \end{quote}
%
%---------------------------------------------------------------------
\subsection{���꡼���׻���Ψ�β���}
%---------------------------------------------------------------------
�Ρ��Ȥ��äƤ⤽��ʤ˲��Τ��ȤǤϤʤ����ץ�����ޡ��Ͻ�����
�����꡼������˻Ȥä����������Ȥ�����꡼���¤��Ƥ����Τǡ�
���λ񸻤�ͭ���˳��Ѥ��ʤ��ƤϤʤ�ʤ��ä������ޤǤ������ѥ������1G
Byte�Υ��꡼��Ȥ��Τϲ��Ǥ�ʤ��������ä�10ǯ�ۤ����Υᥤ���
�졼��ȸ���줿�緿�Υ���ԥ塼�����Ǥ�����1�ĤΥץ�����ब�Ȥ�����
���10M Byte���٤Ǥ��ä���

���꡼�ȹ�碌�ơ��׻���Ψ����פǤ��ä����絬�Ϥʷ׻��ˤʤ�ȡ��׻���
��λ����ޤǲ�������䤹��礬���롥���Τ褦�ʾ�硤�ץ������β�
�ɤˤ�ꡤ®�٤�10\%���åפ���Ȥ��ʤ�Υ��åȤ�����ΤǤ��롥

�����ǡ������Ǥϥ��꡼�θ�ΨŪ�����Ѥ�ͤ��롥�������������Ͼ����񤷤���
%
%-------------------------------------
\subsubsection{���꡼�ȷ׻��θ�Ψ��}
%-------------------------------------
����ޤǤη׻�������ͤ��롥$i$��$ipv$��ޤǤν�������λ�����Ȥ���
��������$\vm{A}$�򼨤�����\texttt{A[i][j]}�ȵչ���$\vm{A}^{-1^\prime}$
���ǽ�Ū�˳�Ǽ���������\texttt{inv\_a[i][j]}�ξ��֤򸫤롥
���줾��ϡ�
%
\begin{equation*}
\begin{aligned}
 \vm{A}^\prime =
  \begin{pmatrix}
   1 & 0 & 0    & \ast & \ast & \ast \\
   0 & 1 & 0    & \ast & \ast & \ast \\
   0 & 0 & 1    & \ast & \ast & \ast \\
   0 & 0 & 0    & \ast & \ast & \ast \\
   0 & 0 & \ast & \ast & \ast & \ast \\
   0 & 0 & \ast & \ast & \ast & \ast \\
  \end{pmatrix} \\ \\
 %------------------------
 \vm{A}^{-1^\prime} =
  \begin{pmatrix}
   \circledast & \circledast & \circledast & 0 & 0 & 0 \\
   \circledast & \circledast & \circledast & 0 & 0 & 0 \\
   \circledast & \circledast & \circledast & 0 & 0 & 0 \\
   \circledast & \circledast & \circledast & 1 & 0 & 0 \\
   \circledast & \circledast & 0           & 0 & 1 & 0 \\
   \circledast & \circledast & 0           & 0 & 0 & 1 \\
 \end{pmatrix}
\end{aligned}
\end{equation*}
%
�ȤʤäƤ���Ϥ��Ǥ��롥���ξ��֤ϡ�\ref{subsubsec:source_inverse}���
\texttt{i=4},\texttt{ipv=3}����λ�����Ȥ��Ǥ��롥���ι�����ɤ�����ȡ���������
$\vm{A}^\prime$�Ǥ�$i$��$ipv$��ޤǤϡ����Ω�ľ�����äƤ��ʤ����Ȥ�ʬ����
\footnote{�ץ�����������ΥǥХå��Ǥ��̤ǡ��ְ㤤��õ���Ȥ��˽��פʾ����⤿
�餹��}��Ʊ�ͤˡ�$\vm{A}^{-1^\prime}$����ϡ�$\vm{A}^\prime$�Ǥ�$i$��$ipv$��ʹ�
�����Ω�ľ���̵�����Ȥ�ʬ���롥�����ξ���Ȥ������Ω���ʤ���ʬ${0,1}$�ϡ�
���꡼��̵�̸����ʤΤǡ�
%
\begin{equation*}
\begin{aligned}
 \vm{A}^\prime =
  \begin{pmatrix}
   \circledast & \circledast & \circledast & \ast & \ast & \ast \\
   \circledast & \circledast & \circledast & \ast & \ast & \ast \\
   \circledast & \circledast & \circledast & \ast & \ast & \ast \\
   \circledast & \circledast & \circledast & \ast & \ast & \ast \\
   \circledast & \circledast & \ast        & \ast & \ast & \ast \\
   \circledast & \circledast & \ast        & \ast & \ast & \ast \\
 \end{pmatrix}
\end{aligned}
\end{equation*}
%
�Ȥ������ʤ롥��������ȡ����꡼��Ⱦʬ�ǺѤࡥ����ϡ�
$n=10000$�ι���Ȥ���ȡ�800M Byte������ˤʤ�ޤ���

�����¸�����Τϡ���ñ�Ǥ��롥���Τ褦�˥ץ�������񤱤Ф褤��
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}

	/* ---- �г���ʬ=1(�ԥܥåȹԤν���) ---------- */
	inv_pivot = 1.0/a[ipv][ipv];
	a[ipv][ipv]=1.0;                /* --- ���ιԤ��ɲ� --- */
	for(j=1 ; j <= n ; j++){
	   a[ipv][j] *= inv_pivot;
	}
	b[ipv] *= inv_pivot;

	/* ---- �ԥܥå���=0(�ԥܥåȹ԰ʳ��ν���) ---- */
	for(i=1 ; i<=n ; i++){
	   if(i != ipv){
	      temp = a[i][ipv];
	      a[i][ipv]=0.0;	        /* --- ���ιԤ��ɲ� --- */
	      for(j=1 ; j<=n ; j++){
	         a[i][j] -= temp*a[ipv][j];
	      }
	      b[i] -= temp*b[ipv];
	   }
	}
\end{verbatim}
\end{quote}

���Τ褦�ˤ����ɬ�פʥ��꡼�ϡ�\ref{subsubsec:source_inverse}��Υץ�����
�����٤�Ⱦʬ�ˤʤ롥����ˡ��׻����֤�Ⱦʬ�ˤʤ롥
\ref{subsubsec:source_inverse}��Ǥϡ��׻���̤�$0$��$1$�ξ���׻���
�Ƥ����������Υץ������ǤϤ����ʤ��Ƥ��롥
%
%-------------------------------------
\subsubsection{�չ������������ؤ�}
%-------------------------------------
����ǡ����꡼�ȷ׻��θ�Ψ�����ޤ줿�������ΤޤޤǤ�
$\vm{A}^{-1}$�򼨤�\texttt{inv\_a[i][j]}������ϡ�$\vm{A}$�εչ���ˤʤ�
�Ƥ��ʤ����ԥܥå�����ˤ�ꡤ�Ԥ������ؤ�������$\vm{A}^\prime$�ε�
����ˤʤäƤ��롥�����ǡ����ι���$\vm{A}$�εչ���ˤ��뤿��ˡ�
$\vm{A}^{-1^\prime}$����������ؤ���ɬ�פ����롥�ʤ�����������ؤ�
��ɬ�פ����뤫?������ϡ��ʲ��Τ褦�˹ͤ��롥

������$\vm{A}$�εչ���Ȥ������Ȥϡ��軻����Ȳ��Τ褦��ñ�̹���ˤʤ롥
%
\begin{equation*}
 \left(
  \begin{array}{@{\,}ccccccc@{\,}}
   \ast   & \ast   & \ast   & \ast   & \ast   & \ldots & \ast   \\ 
   \ast   & \ast   & \ast   & \ast   & \ast   & \ldots & \ast   \\ \hline
   a_{i1} & a_{i2} & a_{i3} & a_{i4} & a_{i5} & \ldots & a_{in} \\ \hline
   \ast   & \ast   & \ast   & \ast   & \ast   & \ldots & \ast   \\
   \vdots &        &        &        &        & \ddots & \vdots  \\
   \ast   & \ast   & \ast   & \ast   & \ast   & \ldots & \ast
  \end{array} 
 \right)
 %------------------------
 \left(
  \begin{array}{@{\,}ccc|c|ccc@{\,}}
   \ast   & \ast & \ast & \alpha_{1j} & \ast & \ldots & \ast   \\
   \ast   & \ast & \ast & \alpha_{2j} & \ast & \ldots & \ast   \\
   \ast   & \ast & \ast & \alpha_{3j} & \ast & \ldots & \ast   \\
   \ast   & \ast & \ast & \alpha_{4j} & \ast & \ldots & \ast   \\
   \vdots &      &      & \vdots      &      & \ddots & \vdots \\
   \ast   & \ast & \ast & \alpha_{nj} & \ast & \ldots & \ast
  \end{array} 
 \right)
 %------------------------
 =\left(
  \begin{array}{@{\,}ccccccc@{\,}}
   1 &                &   &   &                 &        & \\
     & 1              &   &   &   & \hugesymbol{0}       & \\
     &                & 1 &   &                 &        & \\
     &                &   & 1 &                 &        & \\
     &                &   &   & 1               &        & \\
     & \hugesymbol{0} &   &   &                 & \ddots & \\
     &                &   &   &                 &        &1
  \end{array}
  \right)
\end{equation*}
%
���ʤ�������ι���ιԥ٥��ȥ�ȵչ������٥��ȥ�����Ѥ���
\begin{equation*}
 \text{(���ι����$i$�Ԥιԥ٥��ȥ�)}\cdot\text{(�չ����$j$�����٥��ȥ�)}=
 \delta_{ij}
\end{equation*}
�Ȥ����ط����������Ƥ��뤳�Ȥ��̣���롥$\delta_{ij}$�ϡ������ͥå����ε���ǡ�
$i=j$�ΤȤ������ͤ�$1$��$i\neq j$�ΤȤ������ͤ�$0$�Ȥ�����̣�Ǥ��롥

���Τ褦�ʤ櫓�ǡ����ι���ιԤ������ؤ�����硤���εչ���ϸ��ι���εչ������
�������ؤ�����Τˤʤ롥���äơ��ԥܥå�����ˤ�그������ιԤ������ؤ���ȡ���
�������������ؤ���ɬ�פ������롥�ºݤ˥ץ������Ǥϡ��ʲ��Τ褦�ˤ��롥
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}

	/* ---- ��������ؤ�(�չ���) -------------------------- */
	for(j=n ; j>=1 ; j--){
	   if(j != row[j]){
	      for(i=1 ; i<=n ; i++){
	         temp = a[i][j];
	         a[i][j]=a[i][row[j]];
	         a[i][row[j]]=temp;
	      }
	   }
	}
\end{verbatim}
\end{quote}
%
%-------------------------------------------------------------------
\subsubsection{��Ψ����������������������ˡ�Υ������ץ������}
\label{subsubsec:source_effect}
%-------------------------------------------------------------------
����ǡ��ۤȤ�ɥ���������������ˡ�η׻��δؿ��ϡ������Ǥ��롥���δؿ�
�ϡ����ʤ���Ѥ˻Ȥ���Ǥ��������ĤäƤ�������ϡ�
\begin{itemize}
 \item{��򴹤ˤ�봰���ԥܥå�����β��ɡ�����Ϥ���ʤ��񤷤��ʤ���}
 \item{�ݤ�������θ�����ð۹����Ƚ�ꡥ����������񤷤���}
\end{itemize}
���餤�Ȼפ���

����ʾ塤���ɤ���Τ����ѤʤΤǡ��ۤȤ������ʤ��Ȥ���ؿ��Υץ�����
���ʲ��˼�����
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	/* ========= ��������������ˡ�δؿ�====================== */

	int gauss_jordan(int n, double a[][MAXN+10], double b[]){

	   int ipv, i, j;
	   double inv_pivot, temp;
	   double big;
	   int pivot_row, row[MAXN+10];

	   for(ipv=1 ; ipv <= n ; ipv++){

	      /* ---- ������õ�� ---------------------------- */
	      big=0.0;
	      for(i=ipv ; i<=n ; i++){
	         if(fabs(a[i][ipv]) > big){
	            big = fabs(a[i][ipv]);
	            pivot_row = i;
	         }
	      }
	      if(big == 0.0){return(0);}	
	      row[ipv] = pivot_row;

	      /* ---- �Ԥ������ؤ� -------------------------- */
	      if(ipv != pivot_row){
	         for(i=1 ; i<=n ; i++){
	            temp = a[ipv][i];
	            a[ipv][i] = a[pivot_row][i];
	            a[pivot_row][i] = temp;
	         }
	         temp = b[ipv];
	         b[ipv] = b[pivot_row];
	         b[pivot_row] = temp;
	      }

	      /* ---- �г���ʬ=1(�ԥܥåȹԤν���) ---------- */
	      inv_pivot = 1.0/a[ipv][ipv];
	      a[ipv][ipv]=1.0;
	      for(j=1 ; j <= n ; j++){
	         a[ipv][j] *= inv_pivot;
	      }
	      b[ipv] *= inv_pivot;

	      /* ---- �ԥܥå���=0(�ԥܥåȹ԰ʳ��ν���) ---- */
	      for(i=1 ; i<=n ; i++){
	         if(i != ipv){
	            temp = a[i][ipv];
		    a[i][ipv]=0.0;
	            for(j=1 ; j<=n ; j++){
	               a[i][j] -= temp*a[ipv][j];
	            }
	            b[i] -= temp*b[ipv];
	         }
	      }

	   }

	   /* ---- ��������ؤ�(�չ���) -------------------------- */
	   for(j=n ; j>=1 ; j--){
	      if(j != row[j]){
	         for(i=1 ; i<=n ; i++){
	            temp = a[i][j];
	            a[i][j]=a[i][row[j]];
	            a[i][row[j]]=temp;
	         }
	      }
	   }

	   return(1);
	}
\end{verbatim}
\end{quote}
%
%=====================================================================
\section{����夬�ä��ؿ��λȤ���}
%=====================================================================
��������\ref{subsubsec:source_effect}��Υ���������������ˡ��׻���
��ؿ��ϡ����Τ褦�ˤ��ƻȤ����⤷�����ðۤʾ�硤���Τ��Ȥ�ɽ��
���ƥץ�����ब�ߤޤ�褦�ˤʤäƤ��롥
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}

	if(gauss_jordan(n, a, b) == 0){
	   printf("singular matrix !!!\n");
	   exit(0);
	};

 \end{verbatim}
\end{quote}
%
����������ͤϡ����ΤȤ���Ǥ��롥
\begin{itemize}
 \item{\texttt{n}��ϢΩ�������μ����򼨤������Ǥ��롥\texttt{a}��������
      ��򼨤�2��������\texttt{b}��Ʊ����򼨤�1��������Ǥ��롥�׻�
      ��̡��չ���\texttt{a}�ˡ���\texttt{b}�˳�Ǽ����롥}
 \item{���������ðۤξ�硤¨�����󼰤������ξ�硤���δؿ���������
      ����������ͤȤ����֤���}
\end{itemize}
%=====================================================================
\end{document}



