%=====================================================================
% ���Ĺ��� 5E �׻������ѥƥ�����
%�����¸��½��ơ��ޡ�ϢΩ������
%    �ܥƥ����Ȥ�����
%����������ϢΩ������
%����������ϢΩ�������β�ˡ�Τ�������
%��������������������������ˡ
%        ���������õ�ˡ�ȸ�������
%        ��LUʬ��
%        ����������
%
% last updated 2003.10.17
%    created by  Masashi Yamamoto
%     e-mail yamamoto@akita-nct.jp
%=====================================================================
\documentclass[10pt,a4paper]{jarticle}
\usepackage{graphicx,amsmath,amssymb,ascmac,theorem,multicol}
\newcommand{\vm}[1]{\boldsymbol{#1}}
\oddsidemargin 0mm  %����;�� 25.4mm-0mm������ڡ���
\evensidemargin 0mm %����;�� 25.4mm-0mm�������ڡ���
\textwidth 160mm
%
\theoremstyle{plain}
\newtheorem{axion}{����}[section]
\newtheorem{theorem}{����}[section]
\theoremstyle{definition}
\newtheorem{define}{���}[section]
\theoremstyle{plain}
\newtheorem{rem}{����}
\newtheorem{prf}{�ھ�����}
%
\begin{document}
\title{ϢΩ1���������β�ˡ(�õ�ˡ)}
\author{���ܾ���\thanks{��Ω���Ĺ��ȹ�������ع����ŵ����ز�}}
\date{2005ǯ11��11��}
\maketitle
%
%
%=====================================================================
\section{�ؽ�����}
%=====================================================================
�����Ǥϡ�����ԥ塼�����ˤ��ϢΩ�������β�������ˡ��ؽ����롥ϢΩ��������
��������ˡ�ˤϡ��õ�ˡ��ȿ��ˡ�����롥���Υƥ����ȤǤϡ����Ԥξõ�ˡ�Ǥ��롤
\begin{itemize}
 \item �������õ�ˡ�ȸ�������
 \item ����������������ˡ
 \item LUʬ��
\end{itemize}
�ˤĤ����������Ƥ��롥�õ�ˡ�ˤĤ��Ƥϡ���ۤ�¾�Υƥ����Ȥ����ۤ��롥

�����Τ���LUʬ��ˤĤ��Ƥϡ�����򤭤����Τ��������ʤ�����̣�Τ���Ԥ��ϼ�ʬ��
�ٶ����补���ιֵ�������Ƥ���Ԥϡ����ʤ��Ȥ⡤�������õ�ˡ�ȸ���������������������
�����ˡ�����򤷤ơ��ץ�����ब�����Ǥ���褦�ʤ�ɬ�פ����롥

���ιֵ��Ǥϡ�����������������ˡ�Υץ������κ������̤��ơ�ϢΩ�������δ�����
���ȥץ�����������ˡ��ؽ����롥�ȤϤ���������ޤǤηи�����ץ������κ�����
¿��ʻ��֤��פ��뤳�Ȥ�ʬ���äƤ��롥���Τ��ᡤ�ץ�����������ˡ�ˤĤ��Ƥ⡤��
�����Ȥ��ۤ�Τǡ����ɤ���Τ��ɤ���������
%
%=====================================================================
\section{ϢΩ������}
%=====================================================================
%---------------------------------------------------------------
\subsection{ɽ����ˡ}
%---------------------------------------------------------------
�����ޤǤ�̵��ϢΩ1��������(Linear Equations)�ϡ����Τ褦�ʷ��򤷤Ƥ��롣
%
\begin{equation}
 \begin{aligned}
  a_{11}x_1+a_{12}x_2+a_{13}x_3+\cdots+a_{1N}x_N&=b_1\\
  a_{21}x_1+a_{22}x_2+a_{23}x_3+\cdots+a_{2N}x_N&=b_2\\
  a_{31}x_1+a_{32}x_2+a_{33}x_3+\cdots+a_{3N}x_N&=b_3\\
  \vdots\hspace{30mm}&\\
  a_{M1}x_1+a_{M2}x_2+a_{M3}x_3+\cdots+a_{MN}x_N&=b_M
 \end{aligned}
 \label{eq:LinearEquations}
\end{equation}
%
�����Ǥϡ�$M=N$�ξ���ͤ��롣$M \ne N$�Τ褦�ʤ�Τϡ������Ǥιֵ��Υ�٥��Ķ
����Τǡ���̣������ͤϼ�ʬ�ǳؽ����뤳�ȡ����Τ褦��ϢΩ1����������׻����뤳
�Ȥϡ��ºݤ˹��ؤ�����Ǥ��Ф��и���롣�㤨�С�����ʬ��������Υ�������Ʋ򤯾��
�ʤɤǤ��롣���ξ�硢�������μ����������ʤ��礭����100�������餤�����̤Ǥ��롣
100���Ȥ��äƤ⡢3����������ȡ�$100 \times 100 \times 100$���٤Ǥ���Τǡ��ޤ�
�ޤ����٤ϹӤ�������������������������

��(\ref{eq:LinearEquations})�Ϲ���ȥ٥��ȥ�ǽ񤯤ȡ��������ä��ꤷ��
�ͤ��䤹���ʤ롣��ľ���ȡ�
%
\begin{align}
 \vm{A}\boldsymbol{x}=\boldsymbol{b}
 \label{eq:ϢΩ��������ɽ������������}
\end{align}
%
�Ȥʤ�Τϡ������ؽ������Ȥ���Ǥ��롣���줾��ι���ȥ٥��ȥ�ϡ�
%
\begin{equation}
 \begin{aligned}
%
  \vm{A}&=
  \begin{bmatrix}
   a_{11} & a_{12} & a_{13} & \cdots & a_{1N} \\
   a_{21} & a_{22} & a_{23} & \cdots & a_{2N} \\
   a_{31} & a_{32} & a_{33} & \cdots & a_{3N} \\
   \vdots &        &        & \ddots & \vdots \\
   a_{N1} & a_{N2} & a_{N3} & \cdots & a_{NN}
  \end{bmatrix} \qquad
%
  \vm{x}&=
  \begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3 \\
   \vdots\\
   x_N
  \end{bmatrix} \qquad
%
  \vm{b}&=
  \begin{bmatrix}
   b_1 \\
   b_2 \\
   b_3 \\
   \vdots\\
   b_N
  \end{bmatrix}
 \end{aligned}
\end{equation}
%
��ɽ�����������ʸ������ʸ��(bold)�������롢�٥��ȥ�Ͼ�ʸ������ʸ���������롢��
�줾�����ʬ��ɸ�ॹ�������ɽ����뤳�Ȥ�¿����

�����ǡ�������Ϲ���$\vm{A}$��$N \times N$����������ǡ����ι��󼰤������Ǥʤ�
��ΤȤ��롣�פ���ˡ����̤˲򤱤�ϢΩ�������Ǥ��롣�����ǡ��򤯤٤�����ϡ�����
��$\vm{A}$��$\vm{b}$���顢����������(\ref{eq:ϢΩ��������ɽ������������})������
����$\vm{x}$����뤳�Ȥˤʤ롣���ι����������򤯲����ǡ�$\vm{A}$�εչ�������
�����ͤ���뤳�Ȥ��Ǥ��롣�չ������󼰤�ϢΩ��������̩�ܤˤ�����äƤ���Τ�
���롣

�̾ϢΩ1��������(\ref{eq:LinearEquations})��
%
\begin{equation}
 \begin{aligned}
%
  \begin{bmatrix}
   a_{11} & a_{12} & a_{13} & \cdots & a_{1N} \\
   a_{21} & a_{22} & a_{23} & \cdots & a_{2N} \\
   a_{31} & a_{32} & a_{33} & \cdots & a_{3N} \\
   \vdots &        &        & \ddots & \vdots \\
   a_{N1} & a_{N2} & a_{N3} & \cdots & a_{NN}
  \end{bmatrix}
%
  \begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3 \\
   \vdots\\
   x_N
  \end{bmatrix}=
%
  \begin{bmatrix}
   b_1 \\
   b_2 \\
   b_3 \\
   \vdots\\
   b_N
  \end{bmatrix}
 \end{aligned}
 \label{eq:LinearEquations_matrix}
\end{equation}
%
�Ƚ�ɽ���롣���Τ褦�ˤ���ȡ����̤������ʤ��ɤ��ʤ롣������⡢����ϢΩ������
��񤯤Ȥ��ϡ�����ȥ٥��ȥ�ǽ������ɤ��Ǥ�����������äȤФ���ʹ��ɤ���

�����٥��ȥ��Ȥ��ȡ��ʹ��ɤ��Ф���Ǥʤ�����ԥ塼�����ǰ����䤹���ʤ롣�㤨
�С�����$\vm{A}$������$a_{ij}$�ϥץ��������Ǥ�2��������\texttt{a[i][j]}�Ȥ���
�����롣Ʊ�ͤ˥٥��ȥ�$b_k$��1��������\texttt{b[k]}�Ȥ��ư����롣
%
%---------------------------------------------------------------
\subsection{�׻���ˡ}
%---------------------------------------------------------------
ϢΩ1���������ϡ�����᡼��θ����ˤ�ꡢ��Υ٥��ȥ�$\vm{x}$�ϻ�§��
���Ƿ׻��Ǥ��롣����$\vm{A}$����§$(\det A \neq 0)$�ʤ�С����
\begin{align}
 x_j&=\frac{1}{\det A}
 \begin{vmatrix}
   a_{11} & a_{12} & a_{13} & \cdots & a_{1j-1}
  & b_{1j} & a_{1j+1} & \cdots & a_{1N} \\
   a_{21} & a_{22} & a_{23} & \cdots & a_{1j-1}
  & b_{1j} & a_{1j+1} & \cdots & a_{2N} \\
   a_{31} & a_{32} & a_{33} & \cdots & a_{1j-1}
  & b_{1j} & a_{1j+1} & \cdots & a_{3N} \\
   \vdots &        &        & \ddots &
  &        &          & \ddots & \vdots \\
   a_{N1} & a_{N2} & a_{N3} & \cdots & a_{1j-1}
  & b_{1j} & a_{1j+1} & \cdots & a_{NN}
 \end{vmatrix}
\end{align}
%
�Ǥ��롣����ϡ�2�Ĥι��󼰤�׻�����ɬ�פ����ꡢ�׻��̤�����¿���ʤ롣��������
�ơ�$N \geq 4$�ξ��Ͽ侩�Ǥ��ʤ���

���˹ͤ�����Τϡ�$\vm{A}$�εչ���$\vm{A}^{-1}$���Ѥ��ơ�
$\vm{x}=\vm{A}^{-1}\vm{b}$����׻�������ˡ�Ǥ��롣������ˡ�⡢�׻��̤����٤��̤�
���꤬���롣

ϢΩ1���������η׻���ˡ�����̤��ơ�2�̤ꤢ�롣���Ĥϡ������ǳؽ�����õ�ˡ�ǡ�¾
����ȿ��ˡ�ȸ�������ˡ�Ǥ��롣�ɤ��餬�ɤ����ϡ���������$\vm{A}$�������˰�¸��
�롣���̤ˡ�$\vm{A}$��̩�ʤȤ���¨���ۤȤ�ɤ����Ǥ������Ǥʤ��Ȥ��ϡ��õ�ˡ��ͭ
���Ǥ��롣�������ؤɤ����Ǥ������ǡ�$\vm{A}$���¤ΤȤ���ȿ��ˡ��ͭ���Ǥ��롣

�����ǤϾõ�ˡ��ؽ����뤬��ȿ��ˡ�ˤĤ��ƴ�ñ�˾Ҳ𤷤Ƥ������ޤ������������
$\vm{A}=\vm{B}-\vm{C}$���ѷ����ޤ�������ȡ�����ϢΩ1���������ϡ�
$\vm{B}\vm{x}=\vm{C}\vm{x}+\vm{b}$�Ȥʤ롣�����򤯤���ˡ�������
$\vm{B}\vm{x}^{(k+1)}=\vm{C}\vm{x}^{(k)}+\vm{b}$�Ȥ��롣�⤷�������
$\vm{x}^{(0)}$���ɤ���С�$\vm{x}^{(\infty)}$�Ͽ��β�$\vm{x}$�˼�«���롣�����
��$\vm{B}$���ưפ˷׻��Ǥ���ϢΩ1���������ˤʤ�褦�����֡������������ˤ�ꡢ
�䥳�Ӥ�ȿ��ˡ�䥬�����������ǥ�ˡ��SORˡ�ʤɤ����롣��������ˡ�ˤĤ��ƤϾõ�
ˡ��ؽ�������ˡ��ؽ����롥
%
%=====================================================================
\section{�������õ�ˡ�ȸ�������}
%=====================================================================
�������õ�ˡ�ȥ���������������ˡ��ñ��ǡ����������ޤ�ϢΩ1������
����׻����Ƥ�����ˡ��Ʊ���Ǥ��롣

�������õ�ˡ�Ȥ����Τϡ�ϢΩ������
(\ref{eq:LinearEquations_matrix})�򼡤ˤ褦���ѷ������ơ�����ˡ�Ǥ��롣
%
\begin{equation}
 \begin{aligned}
%
  \begin{bmatrix}
   a_{11}^\prime & a_{12}^\prime & a_{13}^\prime & \cdots & a_{1N}^\prime \\
   0             & a_{22}^\prime & a_{23}^\prime & \cdots & a_{2N}^\prime \\
   0             & 0             & a_{33}^\prime & \cdots & a_{3N}^\prime \\
   \vdots        &               &               & \ddots & \vdots \\
   0             & 0             & 0             & \cdots & a_{NN}^\prime
  \end{bmatrix}
%
  \begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3 \\
   \vdots\\
   x_N
  \end{bmatrix}=
%
  \begin{bmatrix}
   b_1^\prime \\
   b_2^\prime \\
   b_3^\prime \\
   \vdots\\
   b_N^\prime
  \end{bmatrix}
 \end{aligned}
\end{equation}
%

���Τ褦�˼����ѷ�������ˡ�򥬥����ξõ�ˡ�ȸ������ºݤ��ѷ���ˡ�ˤĤ��Ƥϡ�����
����������������ˡ�ȤۤȤ��Ʊ���ǤʤΤǡ�����򻲹ͤˤ��뤳�ȡ����Τ褦�˼���
�ѷ��Ǥ���ȸ�ϴ�ñ�ǡ����ˤ褦��$x_N$����$x_1$�ޤǽ缡�׻����롣$\vm{x}$���ͤϡ�
%
\begin{equation}
 \begin{aligned}
  x_N&=\frac{1}{a_{NN}^\prime}b_N^\prime \\
  x_{N-1}&=\frac{1}{a_{N-1N-1}^\prime}
  \left(b_{N-1}^\prime-a_{N-1N}^\prime x_N\right)\\
  x_{N-2}&=\frac{1}{a_{N-2N-2}^\prime}
  \left(b_{N-2}^\prime-a_{N-2N-1}^\prime x_{N-1}-a_{N-2N}^\prime x_N\right)\\
  &\qquad\vdots
 \end{aligned}
\end{equation}
%
�ȵ��뤳�Ȥ��Ǥ��롣���μ��ϡ�
%
\begin{align}
 x_i=\frac{1}{a_{ii}^\prime}\left[
 b_i^\prime-\sum_{j=i+1}^N a_{ij}^\prime x_j
 \right]
\end{align}
%
�ȤޤȤ�뤳�Ȥ��Ǥ��롣�����Ȥäơ�$N$��$0$�ޤǽ������뤳�Ȥ���������ȸ�����
���פʤ��Ȥϡ����$N$����������뤳�Ȥǡ��褷�ơ�$1$����������뤳�ȤϤǤ��ʤ���
�������õ�ˡ�ȸ��������ˤ��ϢΩ1���������ϡ�����ԥ塼�������ưפ˲򤯤��Ȥ���
���롣
%
%=====================================================================
\section{����������������ˡ}
%=====================================================================
�չ������פǤ���С�����������������ˡ���⡢��ǽҤ٤�LUʬ���ˡ���׻�®��
��®����������������Ū���̤�ͤ���ȡ�ξ������ˡ���ΤäƤ����Τ��ɤ����ȤǤ��롣
%
%---------------------------------------------------------------
\subsection{����Ū�ʹͤ���}
%---------------------------------------------------------------
����������������(Gauss-Jordan)ˡ�Ȥ����Τϡ�ϢΩ������
(\ref{eq:LinearEquations_matrix})�򼡤ˤ褦���ѷ������ơ�����ˡ�Ǥ��롣
%
\begin{equation}
 \begin{aligned}
%
  \begin{bmatrix}
   1      & 0      & 0      & \cdots & 0 \\
   0      & 1      & 0      & \cdots & 0 \\
   0      & 0      & 1      & \cdots & 0 \\
   \vdots &        &        & \ddots & \vdots \\
   0      & 0 & 0 & \cdots & 1
  \end{bmatrix}
%
  \begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3 \\
   \vdots\\
   x_N
  \end{bmatrix}=
%
  \begin{bmatrix}
   b_1^\prime \\
   b_2^\prime \\
   b_3^\prime \\
   \vdots\\
   b_N^\prime
  \end{bmatrix}
 \end{aligned}
\end{equation}
%
���μ��������餫�ˡ������$x_{i}=b_{i}^\prime$�Ȥʤ롣�����ɤ���äƵ��뤫?��
����ԥ塼�����Ǽºݤ˷׻��������ˡ����Ϥǥ���������������ˡ�Ƿ׻����Ƥߤ롣��
�Ȥ��ơ�
%
\begin{equation}
 \left\{
  \begin{aligned}
   1x+2y+3&=2\\
   2x+2y+3z&=1\\
   2x+2y+1z&=-1
  \end{aligned}
 \right.
 \label{eq:Gauss-Jordan_example1}
\end{equation}
%
�򥬥�������������ˡ�ǲ����롣

\begin{multicols}{2}
 \setlength{\columnseprule}{0.4pt}
 \setlength{\columnsep}{2zw}
 %
 �򤯤٤���������
 \begin{equation*}
  \begin{bmatrix}
   1 & 2 & 3 \\
   2 & 2 & 3 \\
   2 & 2 & 1 
  \end{bmatrix}
  \begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3
  \end{bmatrix}
  =
  \begin{bmatrix}
   2 \\
   1 \\
   -1
  \end{bmatrix}
 \end{equation*} \\
 %
 2��$-2\times$1��
 %
 \begin{equation*}
  \begin{bmatrix}
   1 & 2 & 3 \\
   0 & -2 & -3 \\
   2 & 2 & 1 
  \end{bmatrix}
  \begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3
  \end{bmatrix}
  =
  \begin{bmatrix}
   2 \\
   -3 \\
   -1
  \end{bmatrix}
 \end{equation*}\\
 %
 3��$-2\times$1��
 %
 \begin{equation*}
  \begin{bmatrix}
   1 & 2 & 3 \\
   0 & -2 & -3 \\
   0 & -2 & -5 
  \end{bmatrix}
  \begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3
  \end{bmatrix}
  =
  \begin{bmatrix}
   2 \\
   -3 \\
   -5
  \end{bmatrix}
 \end{equation*}\\
 %
 $-\frac{1}{2}\times$2��
 %
 \begin{equation*}
  \begin{bmatrix}
   1 & 2 & 3 \\
   0 & 1 & \frac{3}{2} \\
   0 & -2 & -5 
  \end{bmatrix}
  \begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3
  \end{bmatrix}
  =
  \begin{bmatrix}
   2 \\
   \frac{3}{2} \\
   -5
  \end{bmatrix}
 \end{equation*}\\
 %
 1��$-2\times$2��
 %
 \begin{equation*}
  \begin{bmatrix}
   1 & 0 & 0 \\
   0 & 1 & \frac{3}{2} \\
   0 & -2 & -5 
  \end{bmatrix}
  \begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3
  \end{bmatrix}
  =
  \begin{bmatrix}
   -1 \\
   \frac{3}{2} \\
   -5
  \end{bmatrix}
 \end{equation*}\\
 %
 3��$+2\times$2��
 %
 \begin{equation*}
  \begin{bmatrix}
   1 & 0 & 0 \\
   0 & 1 & \frac{3}{2} \\
   0 & 0 & -2 
  \end{bmatrix}
  \begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3
  \end{bmatrix}
  =
  \begin{bmatrix}
   -1 \\
   \frac{3}{2} \\
   -2
  \end{bmatrix}
 \end{equation*}
 %
 $-\frac{1}{2}\times$3��
 %
 \begin{equation*}
  \begin{bmatrix}
   1 & 0 & 0 \\
   0 & 1 & \frac{3}{2} \\
   0 & 0 & 1 
  \end{bmatrix}
  \begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3
  \end{bmatrix}
  =
  \begin{bmatrix}
   -1 \\
   \frac{3}{2} \\
   1
  \end{bmatrix}
 \end{equation*}
 %
 $2��-\frac{3}{2}\times$3��
 %
 \begin{equation*}
  \begin{bmatrix}
   1 & 0 & 0 \\
   0 & 1 & 0 \\
   0 & 0 & 1 
  \end{bmatrix}
  \begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3
  \end{bmatrix}
  =
  \begin{bmatrix}
   -1 \\
   0 \\
   1
  \end{bmatrix}
 \end{equation*}\\
 %
 ����ǡ�����������������ˡ�ˤ���гѲ��κ�Ȥϴ�λ�Ǥ��롣���줫
 �顢$(x_1,x_2,x_3)=(-1,0,1)$��ʬ���롣
\end{multicols}
%
���줬����������������ˡ�Ǥ��롣��äȤ�餷��̾�����դ����Ƥ��뤬���礷����
�ȤʤϤ�����������������衤ϢΩ��������򤤤Ƥ�����ˡ�Ǥ��롥

����ǡ�����������������ˡ������Ǥ����Ȼפ����⤦��������Ū�ˤ������Ƥ�������
��\footnote{�����դε����� ����ɾ���ҤΡ�NUMERICAL RECIPES in C�פ򻲹ͤˤ��Ƥ�
�ޤ�������Ͽ��ͷ׻����ɤ����ʽ�Ǥ���}�����Τ���ˡ���������������������ͤ��롣
�����Ǥϡ����̤δط��Ƿ�������$4 \times 4$�ˤĤ��ƽҤ٤뤬������Ū��$N$�ؤγ�
ĥ���ưפǤ��롣
%
\begin{equation}
 \begin{bmatrix}
  a_{11} & a_{12} & a_{13} & a_{14}\\
  a_{21} & a_{22} & a_{23} & a_{24}\\
  a_{31} & a_{32} & a_{33} & a_{34}\\
  a_{41} & a_{42} & a_{43} & a_{44}
 \end{bmatrix}
 \cdot
 \begin{bmatrix}
  \begin{pmatrix}
   x_{1}\\
   x_{2}\\
   x_{3}\\
   x_{4}
  \end{pmatrix}
  \sqcup
  \begin{pmatrix}
   y_{11} & y_{12} & y_{13} & y_{14}\\
   y_{21} & y_{22} & y_{23} & y_{24}\\
   y_{31} & y_{32} & y_{33} & y_{34}\\
   y_{41} & y_{42} & y_{43} & y_{44}
  \end{pmatrix}
 \end{bmatrix}\\
 =
 \begin{bmatrix}
  \begin{pmatrix}
   b_{1}\\
   b_{2}\\
   b_{3}\\
   b_{4}
  \end{pmatrix}
  \sqcup
  \begin{pmatrix}
   1 & 0 & 0 & 0\\
   0 & 1 & 0 & 0\\
   0 & 0 & 1 & 0\\
   0 & 0 & 0 & 1
  \end{pmatrix}
 \end{bmatrix}
 \label{eq:Gauss-Jordan����������}
\end{equation}
%
�����ǡ�$\sqcup$������硢�Ĥޤꤳ��ξ¦�γ�̤����äƹ���򤯤ä�
�������򹭤����뤳�Ȱ�̣���롣���μ����顢�ưפ�
%
\begin{align}
 \vm{A}\vm{x}&=\vm{b}\\
 \vm{A}\vm{Y}&=\vm{E}
\end{align}
%
��ʬ���롣�������$\vm{E}$��ñ�̹���Ǥ��롣�פ���˹���������
(\ref{eq:Gauss-Jordan����������})��򤯤Ȥ������Ȥϡ�����2�Ĥ�ϢΩ���������
���Ȥ�¾�ʤ�ʤ���$\vm{x}$�Ϥ�Ȥ�������(\ref{eq:LinearEquations})�β�Ȥʤꡢ
$\vm{Y}$��$\vm{A}$�εչ���Ǥ��롣


��(\ref{eq:Gauss-Jordan����������})�ˤĤ��ơ��ʲ��Τ��Ȥ��ưפ�ʬ���롣
%
\begin{itemize}
 \item $\vm{A}$��Ǥ�դ�2�Ԥ������ؤ��ơ�������б�����$\vm{b}$��
       $\vm{E}$�������ؤ�����硢$\vm{x}$��$\vm{Y}$���ͤȽ�����Ѥ��ʤ�����
       ������$\vm{E}$�Ϥ�Ϥ�ñ�̹���ǤϤʤ��������ϢΩ�������ν����������
       ���ƽ񤤤Ƥ��뤳�Ȥ��������Ƥ��롣
 \item $\vm{A}$��Ǥ�դιԤ򡢤��ιԤ��̤ιԤȤ����������֤�������Ʊ
       �����б�����$\vm{b}$��$\vm{E}$��Ʊ�ͤ��֤������롣���ξ�硢$\vm{x}$
       ��$\vm{Y}$���ͤȽ�����Ѥ��ʤ������������ξ���$\vm{E}$�Ϥ�Ϥ�ñ
       �̹���ǤϤʤ���
 \item $\vm{A}$��Ǥ�դ�2��������ؤ��ơ�������б�����$\vm{x}$��
       $\vm{Y}$�ιԤ������ؤ���С�$\vm{b}$��$\vm{E}$�ν���������ؤ���ɬ��
       ��̵�������ξ�硢��ιԤν�����Ѥ��Τǡ��Ǹ�˸����᤹��ɬ��
       �ˤʤ롣
\end{itemize}
%

����3�Ĥ������Ȥ߹�碌�ơ���������$\vm{A}$��ñ�̹�����Ѵ�����Τ�������������
�����ˡ�Ǥ��롣$\vm{A}$��ñ�̹�����Ѵ������С����դ�$\vm{x}$��$\vm{Y}$��ɽ��
�롣�������äơ���ȵչ��󤬵���줿���Ȥˤʤ롣�⤷���չ������פǤ����
$\vm{x}$�����׻������չ���Τ�ɬ�פǤ����$\vm{Y}$�Τ߷׻����롣
%
%---------------------------------------------------------------
\subsection{�ԥܥå�����}
%---------------------------------------------------------------
��˼�����������������������ˡ��3�Ĥδ������Τ�����2���ܤ����Ȥ��
����ˡ��֥ԥܥå�����ʤ��Υ���������������ˡ�פȸ������ǽ顢��
�Ϥ�ϢΩ��������򤤤���ˡ�Ǥ��롣������ˡ�����餫�ˤޤ������ϡ��⤷1��
�������г����Ǥ������ξ�硢�׻����Ǥ��ʤ��ʤäƤ��ޤ��Ȥ����ˤ��롣���γ����
�Ǥ�ԥܥå�(pivot)�ȸ����������Ǥʤ��ˤ��Ƥ⡢���ΥԥܥåȤ����
�˾������ͤξ�硢�ݤ�������礭���ʤ�����Ǥ���\footnote{���ͷ׻��ξ�硢��
���ʿ��ǳ�뤳�Ȥ����˷����ޤ�����������������װ��Ǥ��������ѷ����ơ�
�Ǥ������������򤱤ʤ��ƤϤʤ�ޤ���}�����Τ褦�ʤ��Ȥ��顢���̤�
�ԥܥå�����ʤ��Υ���������������ˡ�Ȥ�����ΤϹͤ����ʤ���

����������򤱤뤿��ˤɤ����뤫�Ȥ����ȡ��ԥܥå�����Ȥ�����ˡ��Ȥ�����ˡ�ϴ�
ñ�ǡ���˼�����3�Ĥδ������Τ�����1���ܤ�3���ܤ�Ȥäơ��гѤ��������ɤ�����
���äƤ��롣1���ܤ����Τߤ��Ѥ��ƹԤ������ؤ�����ˡ����ʬ�ԥܥå�����
(partial pivoting)�ȸ�����1���ܤ�����3���ܤ�����Ȥäơ��Ԥ���������ؤ�
��Τ����ԥܥå�����(full pivoting)�ȸ��������Ǥˤ������ٽ���夬�äƤ���
ñ�̹������������ʤ��Τǡ��ԥܥåȤ���������Ƥ���Ԥβ��ιԤ������Фʤ�
�ƤϤʤ�ʤ���

��ʬ�ԥܥå�������������餫�˴�ñ�Ǥ��롣��ι���������ؤ���ɬ�פ�̵��
����Ǥ��롣���ξ�硢�Ԥ������ؤ��������ʤ��Τǡ��ԥܥåȤϤ����󤫤���
�Фʤ��ƤϤʤ�ʤ��������ԥܥå�������������٤����Ǥ�¿������
�ǽ�Ū�ʲ�����٤Ϥ��ޤ��Ѥ��ʤ��褦�Ǥ��롣�������äơ������Ǥϥץ���
���δ�ñ����ʬ�ԥܥå�����Ƿ׻�������ˤ��롣

���˹ͤ��ʤ��ƤϤʤ�ʤ��Τϡ��ԥܥåȤ����򤹤���Ǥ��롣��ñ�˸����С�
�礭���������򤹤�����Τ褤��������������Ԥ�100���ܤ��ơ������
�б����뱦�դιԤ�100���ܤ��뤳�Ȥ�Ǥ���Τǡ������礭���Ȥ�������
�Ǥ����꤬���ꤽ���Ǥ��롣�ɤ����뤫�ȸ����ȡ����������κ��緸����1�˵�
�ʲ����ơ�����Τ�Τ�ԥܥåȤ����֤��Ȥ��Ԥ��Ƥ��롣������ˡ��
Ū�ԥܥå�����(implicit pivoting)�ȸƤ֡�

����ǡ��ԥܥåȤ���������դ����Τǡ��ե������㡼�Ȥ�񤤤Ƥߤ롣

%---------------------------------------------------------------
\subsection{�ե������㡼��}
%---------------------------------------------------------------
����������������ˡ�Υե������㡼�Ȥ��\ref{fig:flow_gj}�˼�����
%
\begin{figure}[hbtp]
 \begin{center}
  \includegraphics[keepaspectratio, scale=1.0]{figure/flow_gj.eps}
  \caption{����������������ˡ�Υե������㡼��}
  \label{fig:flow_gj}
 \end{center}
\end{figure}
%
%=====================================================================
\section{LUʬ��}
%=====================================================================
%---------------------------------------------------------------
\subsection{LUʬ��ˤ���η׻���ˡ}
%---------------------------------------------------------------
��������$\vm{A}$�������ѹ���$\vm{L}$�Ⱦ廰�ѹ���$\vm{U}$���Ѥ�Ÿ���Ǥ�
���Ȥ��롣
%
\begin{align}
 \vm{A}=\vm{L}\vm{U}
\end{align}
%
�����ѹ���Ⱦ廰�ѹ�������Ǥ�񤭽Ф���
%
\begin{align}
 \begin{bmatrix}
  \alpha_{11} & 0           & 0           & 0          \\
  \alpha_{21} & \alpha_{22} & 0           & 0          \\
  \alpha_{31} & \alpha_{32} & \alpha_{33} & 0          \\
  \alpha_{41} & \alpha_{42} & \alpha_{43} & \alpha_{44}
 \end{bmatrix}
 \cdot
 \begin{bmatrix}
  \beta_{11} & \beta_{12} & \beta_{13} & \beta_{14}\\
  0          & \beta_{22} & \beta_{23} & \beta_{24}\\
  0          & 0          & \beta_{33} & \beta_{34}\\
  0          & 0          & 0          & \beta_{44}\\
 \end{bmatrix}
 =
 \begin{bmatrix}
  a_{11} & a_{12} & a_{13} & a_{14}\\
  a_{21} & a_{22} & a_{23} & a_{24}\\
  a_{31} & a_{32} & a_{33} & a_{34}\\
  a_{41} & a_{42} & a_{43} & a_{44}
 \end{bmatrix}
 \label{eq:LU�ι���������}
\end{align}
%
�Ȥʤ롣

���Τ褦��LUʬ��Ǥ���ȡ�ϢΩ1����������
%
\begin{align}
 \vm{Ax}=(\vm{LU})\vm{x}=\vm{L}(\vm{Ux})=\vm{b}
\end{align}
%
�Ƚ񤱤롣����򤵤�˽񤭴�����ȡ�
%
\begin{align}
 \vm{Ly}=\vm{b}
 \label{eq:LUʬ��L��������}
\end{align}
\begin{align}
 \vm{Ux}=\vm{y}
 \label{eq:LUʬ��U��������}
\end{align}
%
�Ȥʤ롣������ϢΩ�������β�$\vm{y}$��$\vm{x}$�ϡ����줾��η���
�����ѹ���ʤΤ��ưפ˷׻��Ǥ���(�������õ�ˡ�ȸ��������������򸫤�)��
$y$�����ϡ������������ѹ���ʤΤ�$1$��$N$�ޤ����������ˤ��򤱤롣
����Ū�ˤϡ�
%
\begin{equation}
 \begin{aligned}
  y_1&=\frac{1}{\alpha_{11}}b_1\\
  y_i&=\frac{1}{\alpha_{ii}}\left(b_i-\sum_{j=1}^{i-1}\alpha_{ij} y_j\right)
  \qquad i=2,3,\cdots,N
 \end{aligned}
\end{equation}
%
�Ǥ��롣����$y$����ޤä��ʤ�С����٤Ϸ������廰�ѹ���μ�(\ref{eq:LUʬ
��U��������})��$\vm{x}$����롣����ϡ�$N$��$1$�ν���Ƿ׻������
��������Ȥ���
%
\begin{equation}
 \begin{aligned}
  x_N&=\frac{1}{\beta_{NN}}y_N\\
  x_i&=\frac{1}{\beta_{ii}}\left(y_i-\sum_{j=1+1}^N\beta_{ij} x_j\right)
  \qquad i=N-1,N-2,\cdots,1
 \end{aligned}
\end{equation}
%

���������������ȸ��������ϡ�����ԥ塼�����ˤȤä����˴�ñ�˷׻��Ǥ��롣����
�ϡ���������$A$��LUʬ��Ǥ���С�ϢΩ�������ϴ�ñ�˲򤱤�ȸ��äƤ��롣�����LU
ʬ�����ˡ��ܤ����������롣

���ä���LUʬ�򤬽���Ƥ��ޤ��С���(\ref{eq:LinearEquations})�α���$\vm{b}$���Ѥ��
�Ƥ⡢����LUʬ��η����Ѥ���ɬ�פ��ʤ������դ��Ѥ�äƤ⡢LUʬ���1��ǺѤࡣ��
�줬���������ξõ�ˡ�ȸ����������Ȥ߹�碌����ˡ�䥬��������������ˡ����٤ơ�
��Ω�ä�ͥ��Ƥ������Ǥ��롣
%
%---------------------------------------------------------------
\subsection{LUʬ��(���饦�ȤΥ��르�ꥺ��)}
%---------------------------------------------------------------
LUʬ�򤹤�Ȥ������Ȥϡ���(\ref{eq:LU�ι���������})��$\alpha_{ij}$��$\beta_{ij}$
��׻����뤳�Ȥˤۤ��ʤ�ʤ������μ��ι����������ϡ�$N^2+N$��̤�ο���$N^2$�μ���
�ޤࡣ̤�ο��ο����������ο����¿���Τǡ�$N$�Ĥ�̤�ο��򾡼�˷��ƻĤ��׻�
���뤳�Ȥ���ǽ�Ǥ��롣���äơ�LUʬ��ϰ�դ˷�ޤ�ʤ����׻����䤹���褦��$N$��
��̤�ο�����뤳�Ȥ��Ǥ��롣�����Ǥϡ�LUʬ��Υ��饦��(Crout)�Υ��르�ꥺ���
������
%
\begin{align}
 \alpha_{ii}=1 \qquad i=1,2,3,\cdots,N
\end{align}
%
�Ȥ��롣

����Ǥϡ����饦�ȤΥ��르�ꥺ��ˤ��LUʬ��μ��򼨤����Ȥˤ��롣
\begin{enumerate}
 \item{$\alpha_{ii}=1\quad(i=1,\cdots,N)$�Ȥ��ޤ����������ˤ�ꡢ��
      ���٤�����������(\ref{eq:LU�ι���������})��
%
      \begin{align}
       \begin{bmatrix}
	1           & 0           & 0           & 0          \\
	\alpha_{21} & 1           & 0           & 0          \\
	\alpha_{31} & \alpha_{32} & 1           & 0          \\
	\alpha_{41} & \alpha_{42} & \alpha_{43} & 1
       \end{bmatrix}
       \cdot
       \begin{bmatrix}
	\beta_{11} & \beta_{12} & \beta_{13} & \beta_{14}\\
	0          & \beta_{22} & \beta_{23} & \beta_{24}\\
	0          & 0          & \beta_{33} & \beta_{34}\\
	0          & 0          & 0          & \beta_{44}\\
       \end{bmatrix}
       =
       \begin{bmatrix}
	a_{11} & a_{12} & a_{13} & a_{14}\\
	a_{21} & a_{22} & a_{23} & a_{24}\\
	a_{31} & a_{32} & a_{33} & a_{34}\\
	a_{41} & a_{42} & a_{43} & a_{44}
       \end{bmatrix}
       \label{eq:���饦��LU�ι���������}
      \end{align}
%
      ���ѷ��Ǥ��롣}
%
 \item{���μ��򸫤�ȡ�$\beta_{ij}$��$\alpha_{ij}$�����˼�������Ǵ�ñ�˵����
      �뤳�Ȥ�ʬ���롣�ޤ��ϼ��򸫤�ʬ����褦�ˡ�$\beta_{11}$��ľ���˷׻��Ǥ��롣
      ����$\beta_{11}$�����Ѥ��ơ�$\alpha_{21},\alpha_{31},\alpha_{41}$�����
      ���Ȥ��Ǥ��롣����ǡ�$L$��$U$����1���ܤ�����줿��������2���ܤǤ��롣��
      ���$\beta_{12}$��ľ���˷׻��Ǥ��롣�������ơ�����ޤ�ʬ���äƤ���
      $\beta_{ij}$��$\alpha_{ij}$��Ȥ��ȡ�$\beta_{22},\alpha_{32},\alpha_{42}$
      ����뤳�Ȥ��Ǥ��롣�������2���ܤϽ����ǡ�Ʊ�����Ȥ򷫤��֤��ȡ�����
      ��$\beta_{ij}$��$\alpha_{ij}$���׻��Ǥ��롣����򥢥르�ꥺ��ˤ���ȼ���
      �褦�ˤʤ롣\\ $j=1,2,3,\cdots,N$�Ȥ�������Ƿ׻����롣$\vm{L}$��$\vm{U}$
      ��$j$���ܤ�׻����뤳�Ȥˤʤ롣����Ū�ˤϡ��ʲ��Τ褦�ˤ��ơ�$j$���ܤ�
      $\beta_{ij}$��$\alpha_{ij}$����롣
      \begin{itemize}
       \item{�ޤ���$i=1,2,\cdots,j$�ˤĤ��ơ������˽���$\beta_{ij}$��
	    �׻����롣
       \begin{equation}
	\begin{aligned}
	 \beta_{1j}&=a_{1j}\\
	 \beta_{ij}&=a_{ij}-\sum_{k=1}^{i-1}\alpha_{ik}\beta_{kj}
	\end{aligned}
	\label{eq:L��beta�׻�}
       \end{equation}
	    }
%
       \item{���ˡ�$i=j+1,j+2,\cdots,N$�ˤĤ��ơ�$\alpha_{ij}$��׻����롣
       \begin{equation}
	\begin{aligned}
	 \alpha_{ij}&=\frac{1}{\beta_{jj}}\left(
	 a_{ij}-\sum_{k=1}^{j-1}\alpha_{ik}\beta_{kj}
	 \right)
	\end{aligned}
	\label{eq:U��alpha�׻�}
       \end{equation}
	    }
%
       \item{����ǡ�$\vm{L}$��$\vm{U}$��$j$���ܤ����������Τǡ�Ʊ������
	    $j+1$���ܤ˹Ԥ���Ʊ�����Ȥ򷫤��֤��ơ�LUʬ��ι����
	    ���������롣}
      \end{itemize}
      }
\end{enumerate}
%

������ˡ�ˤ�ꡢLUʬ�򤬤Ǥ��롣���˼����ԥܥå�����򤷤ʤ���С����르�ꥺ���
����ñ��Ǥ��롣
%
%---------------------------------------------------------------
\subsection{�ԥܥå�����}
%---------------------------------------------------------------
�����Ǥ⡢�ԥܥå���������꤬�ФƤ��롣��(\ref{eq:U��alpha�׻�})��$\beta_{jj}$
�ǳ����ʬ�Ǥ��롣����ʲ����뤿��ˤϡ��ԥܥå������ɬ���Բķ�Ȥ������Ȥ�
���롣�����ԥܥå������ʣ���ʤΤǡ���ʬ�ԥܥå�����ǽ�ʬ�Ǥ�������

�ǤϤɤ����뤫�Ǥ��������������($j$��)�ޤ�ʬ�򤷤���������������ʤ������Τ���
�ˤϡ�����$\vm{L}$�ιԤ�򴹤���������б���������$\vm{A}$ �ιԤ�򴹤��������
����äȤ⾯�ʤ��ʤ롣����������$\vm{U}$�ϹԤ�����Ѳ����ʤ����ǽ�Ū�ˤϹԤ��
��������$\vm{A}^\prime$��LUʬ�򤬽���롣ϢΩ1����������򤯤Ȥ��ˤϡ�Ʊ�ͤ�
$\vm{b}$�ιԤ�򴹤��Ƥ��������������Ԥθ򴹤Ǥ��뤿�ᡢ��$\vm{x}$�����Ǥν����
�����ؤ��ʤ���

�Ĥ��ˡ��ɤΤ褦�ˤ��Ƹ򴹤���Ԥ���뤫�Ǥ��롣����Ū�ˤϡ�$\beta_{jj}$���礭
���ʤ�褦�����򤹤���ɤ���̤������롣���饦��ˡ�Υԥܥå�����ϡ����Τ褦��
�ʤ�롣$j$���ܤΥԥܥåȤ����򤹤���ˤĤ��ƤǤ��롣
%
\begin{enumerate}
 \item{�ޤ��ϡ�$j-1$���ܤޤǤι���$\vm{L}$�γƹԤ����Ǥκ����ͤ�1�˵�
      �ʲ����롣Ʊ���ˡ��б��������$\vm{A}$�ιԤ�Ʊ��������ݤ��롣}
 \item{�������ơ�
      \begin{equation}
       \begin{aligned}
	\gamma_{i}&=a_{ij}-\sum_{k=1}^{i-1}\alpha_{ik}\beta_{kj}
	\qquad (i=j,j+1,\cdots,N)
       \end{aligned}
	\label{eq:gamma�׻�}
      \end{equation}
      ��׻����롣����ϡ���(\ref{eq:L��beta�׻�})��Ʊ����
      ��(\ref{eq:U��alpha�׻�})��$\beta_{jj}$�ǳ�뤳�Ȱʳ���Ʊ���Ǥ�
      �뤳�Ȥ����դ�ɬ�פǤ��롣
      }
 \item{�����$\gamma_{i}$�Ȥʤ��Τ�ԥܥåȤȤ������򤹤롣}
 \item{����ΥԥܥåȤȤʤ�Ԥ�ʬ���ä��Τǡ���ϸ�(���ʲ���)��
      $\vm{L}$��$\vm{A}$���Ѥ��ơ���(\ref{eq:U��alpha�׻�})��
      $\beta_{jj}$��׻����롣}      
\end{enumerate}
%
���줬�ԥܥå�õ���Υ롼����Ǥ��롣�ºݤˤϡ��ԥܥåȺ����Ѥδؿ������
���ơ��׻��򤹤뤳�Ȥˤʤ롣
%
%=====================================================================
\section{��������}
%=====================================================================
%---------------------------------------------------------------
\subsection{����������������ˡ}
%---------------------------------------------------------------
\begin{enumerate}
 \item{����ϢΩ��������ԥܥå�����̵���Υ���������������ˡ�Ƿ׻�����ץ�����
      ���������ʤ������ץ������ϡ�$N=3$�Τߤʤ餺��$N=100$���٤ޤ��ưפ˷׻�
      �Ǥ���褦������Ū�ˤ��뤳�ȡ�
 \begin{equation*}
  \left\{
   \begin{aligned}
    2x-4y+6z&=5\\
    -x+7y-8z&=-3\\
    x+y-2z&=2
   \end{aligned}
  \right.
 \end{equation*}  
      }
 \item{�ץ�����ब���������顢�չ����׻�����롼������ɲä��ʤ����������ơ�
      �չ���ȸ��ι���򤫤���碌����ñ�̹���ˤʤ뤳�Ȥ��ǧ���ʤ�����}
 \item{�չ��󤬴��������顢�ԥܥå�����Υ롼������ɲä��ʤ�����}
 \item{�ԥܥå�����Υ롼���󤬴��������ʤ�С�����ϢΩ��������׻����ʤ�����
%
      \begin{equation*}
       \begin{aligned}
	a_{ij}&=\cos\left[\frac{\pi (i-1)(j-1)}{N}\right]\qquad
	i,j=1,2,\cdots,N\\
	b_i&=\frac{i-1}{N} \qquad i=1,2,\cdots,N
       \end{aligned}
      \end{equation*}
%
      ����ϡ������ȤΥա��ꥨ�Ѵ�(Υ���ա��ꥨ�Ѵ�)�ˤʤäƤ��롣�Ȥꤢ������
      N=100���٤Ƿ׻����Ƥߤơ��Ǹ��
%
      \begin{equation*}
       \begin{aligned}
	f(x)=\sum_{j=1}^{N}x_i\cos\left[(j-1)x\right]
       \end{aligned}
      \end{equation*}
%
      ��ץ��åȤ��ƻ����ȤˤʤäƤ����뤳�Ȥ��ǧ���衣
      }
\end{enumerate}

%=====================================================================
\end{document}



