%\input head
\input amssym.def
\input amssym

%\begin{document}
%\section{Appendix}

���忡���� ������ MCNV�˰����� ���� ������ �м��� ����Ѵ�.
���⿡ ���� ������ [Lamp85]�� �����ϴ�.

���� ������ �ʿ��� �������� ����ϸ� ������ ����.

A1) ���  Ŭ�� $c_p,c_q$�� ���� ������ �����Ѵ�. ���⼭ $\delta_0$�� 
����̴�.
\begin{eqnarray*}
	\left| c_p(T^{(0)}) - c_q(T^{(0)}) \right| < \delta_0 .
\end{eqnarray*}

���� A1)�� ���ʿ� ��� Ŭ������ $\delta_0$-����Ǿ������ �ǹ��Ѵ�. 

$C_p^{(i)}$�� ���ϴ� �ð��� $R^{(i)}$ ������ ������ $S$�ʶ�� 
�����Ѵ�. ��, $S^{(i)} \equiv [ T^{(i+1)}$$ - S, T^{(i+1)}]$������ �̷������.

A2) ���� $i$�� ���Ͽ� Ŭ����������S1,S2�� �����ǰ� Ŭ�� $c_p$�� �ð�
$T^{(i+1)}$���� �����̸�, 
������ Ŭ�� $c_q$�� ���� $c_p$�� Ŭ�� ���� $\Delta_{qp}$�� ���� �� �ִ�.
���� $c_q$�� �ð�$T^{(i+1)}$���� �����̸� $S^{(i)}$�� 
��ð� $T_0$�� ���� ������ �����Ѵ�.
\begin{eqnarray*}
	\left| c_p^{(i)}(T_0+\Delta_{qp}) - c_q^{(i)}(T_0) \right| 
	< \varepsilon .
\end{eqnarray*}

���⼭ $p=q$�̸� $\Delta=0$�̴�.  $\varepsilon$�� ���� ���� ������ �ǹ��Ѵ�.

���� �������� ��ü Ŭ�� �ý��ۿ��� �����Ѵٸ� ���� Lemma���� ������ �� �ִ�.

\newcommand{\LEM}{\sc Lemma}
\newtheorem{lemm}{\LEM}

\begin{lemm}.\rm   % 1
 ���� i�� ���� Ŭ���������� S1�� �����ϰ� Ŭ�� $c_p$ �� $c_q$�� 
$T^{(i+1)}$���� �����̶�� ������ �����Ѵ�.
\begin{eqnarray*}
	\left| \Delta_{qp} \right| \lesssim \delta + \varepsilon 
\end{eqnarray*}
{\gr����}: $\Delta_{qp}$~�� $T_0$�� A2������ ���ٰ� �Ҷ�,
\begin{eqnarray*}
  \lefteqn{c_p^{(i)}(T_0)-c_p^{(i)}(T_0+\Delta_{qp}) }\\
  & = &
  c_p^{(i)}(T_0)-c_q^{(i)}(T_0)+c_q^{(i)}(T_0)-c_p^{(i)}(T_0+\Delta_{qp})
\end{eqnarray*}
�̹Ƿ� S1�� A1���� ���� ������ �����ϹǷ�
\begin{eqnarray*}
  \left|{c_p^{(i)}(T_0)-c_p^{(i)}(T_0+\Delta_{qp}) }\right|
  < \delta + \varepsilon 
\end{eqnarray*}
A2�� $\rho \ll 1$�� �������� ���� �������� �� �� �ִ�.\hfill $\blacksquare$
\end{lemm}

\begin{lemm}.\rm %2
 ���� i�� ���� Ŭ���������� S1�� �����ϰ� Ŭ�� $c_p$ �� $c_q$�� 
$T^{(i+2)}$���� �����̶�� ������ �����Ѵ�. ���⼭, $\Pi$�� ������ ���̴�.
\begin{eqnarray*}
	 \left| c_p^{(i)}(T+\Pi)-\left[c_p^{(i)}(T)+\Pi \right]\right| \leq 
	\left( {\rho \over 2} \right) |\Pi| 
\end{eqnarray*}

����, ���� $\rho\Pi$�� ������ ��ŭ ������ ������ �����Ѵ�.
\begin{eqnarray*}
	c_p^{(i)}(T+\Pi) \approx c_p^{(i)}(T)+|\Pi| 
\end{eqnarray*}
{\gr����}: A1���κ��� ���� �����Ѵ�.\hfill $\blacksquare$
\end{lemm}

\begin{lemm}.\rm %3
 ���� i�� ���� Ŭ���������� S1�� �����ϰ� Ŭ�� $c_p$ �� $c_q$�� 
$T^{(i+1)}$���� �����̶�� ������ �����Ѵ�.
\begin{eqnarray*}
	\left| c_p^{(i)}(T_0+\alpha\Delta_{qp})-c_q^{(i)}(T_0) \right| 
	\lesssim 
	\varepsilon +|\alpha-1|\Delta
\end{eqnarray*}
{\gr����}: $\rho$�� ������ ���� ũ��( $10^{-6}$ ) �̹Ƿ�
\begin{eqnarray*}
\lefteqn{\left| c_p^{(i)}(T_0+\alpha\Delta_{qp})-c_q^{(i)}(T_0) \right|} \\
	& = & \left| c_p^{(i)}(T_0+\Delta_{qp}+|\alpha-1|\Delta_{qp})
		- c_q^{(i)}(T_0) \right| \\
	&\approx & \left| c_p^{(i)}(T_0+\Delta_{qp}) - c_q^{(i)}(T_0)\right| 
		+ |\alpha-1|\left|\Delta_{qp}\right| 
		\mbox{\hspace{2em}[by {\sc Lemma 2}]}
		%\mbox{\hspace{5em}[by {\sc Lemma} 2]}
\end{eqnarray*}
$\left|\Delta_{qp}\right|<\Delta$�̰� A2�� $\rho \ll 1$�� �������� ���� 
�������� �� �� �ִ�.
\hfill $\blacksquare$
\end{lemm}

\begin{lemm}. \rm %4
 ���� i�� ���� Ŭ���������� S1�� �����ϰ� Ŭ�� $c_p$ �� $c_q$�� 
$T^{(i+2)}$���� �����̶�� $S^{(i)}$�� ���� �ð� $T$�� ���� ������ 
�����Ѵ�.
\begin{eqnarray*}
	\left| c_p^{(i)}(T+\Pi+\alpha\Delta_{qp})-c_q^{(i)}(T+\Pi) \right| 
	\lesssim \varepsilon+\rho S+ |\alpha-1|\Delta 
\end{eqnarray*}
{\gr����}: $T_0$�� A2������ ����.
\begin{eqnarray*}
 \lefteqn{\left| c_p^{(i)}(T+\Pi+\alpha\Delta_{qp})-c_q^{(i)}(T+\Pi) 
		\right|} \\
  & = & \left| c_p^{(i)}(T_0+\alpha\Delta_{qp}+T-T_0+\Pi)
	-c_q^{(i)}(T_0+T-T_0+\Pi) \right| \\
  & \leq & \left| c_p^{(i)}(T_0+\alpha\Delta_{qp})-c_q^{(i)}(T_0) \right|
  + \rho \left| T-T_0 + \Pi \right|  \mbox{\hspace{1em}[by Lemma 2]} \\
  %+ \rho \left| T-T_0 + \Pi \right|  \mbox{\hspace{5em}[by Lemma 2]} \\
  & \lesssim & \varepsilon+|\alpha-1|\Delta + \rho \left| T-T_0 \right|\\
  &&		\mbox{\hspace{2em}[by {\sc Lemma 3} and the hypothesis that
		 $\rho\Pi$ is negligible]}
 % &&		\mbox{\hspace{5em}[by Lemma 3 and the hypothesis that
 %		 $\rho\Pi$ is negligible]}
\end{eqnarray*}
$T$�� $S^{(i)}$�� ���� �����Ƿ� ���� ���� �����Ѵ�.
\hfill $\blacksquare$
\end{lemm}

\begin{lemm}. \rm
 ���� i�� ���� Ŭ���������� S1�� �����ϰ� Ŭ�� $c_p$ �� $c_q$, $c_r$��ΰ�
$T^{(i+2)}$���� �����̶�� $S^{(i)}$�� ���� �ð� $T$�� ���� ������ 
�����Ѵ�.
\begin{eqnarray*}
	\left| c_p^{(i)}(T)+\alpha\bar{\Delta}_{rp}-
	\left[c_p^{(i)}(T)+\alpha\bar{\Delta}_{rq} \right] \right| \leq 
	2(\varepsilon+\rho S+|\alpha-1|\Delta)
\end{eqnarray*}
{\gr����}: {\sc Lemma 1}�� ���� $\left|\Delta_{rp}\right|$�� $\left|\Delta_{rq}\right|$ 
     �� $\Delta$���� ������ �� �� �����Ƿ�, 
	$\bar{\Delta}_{rp}=\Delta_{rp}$�̰�
	$\bar{\Delta}_{rq}=\Delta_{rq}$�̴�. ���� 
	$\rho\Delta_{rp}$�� $\rho\Delta_{rp}$ �� ������ ��ŭ �����Ƿ�
\begin{eqnarray*}
\lefteqn{ \left| c_p^{(i)}(T)+\alpha\bar{\Delta}_{rp}-
	\left[c_p^{(i)}(T)+\alpha\bar{\Delta}_{rq} \right] \right| } \\
  & = & \left| c_p^{(i)}(T)+\alpha\Delta_{rp}-
	\left[c_q^{(i)}(T)+\alpha\Delta_{rq}\right] \right| \\
  & \approx & \left| c_p^{(i)}(T+\alpha\Delta_{rp})
        -c_q^{(i)}(T+\alpha\Delta_{qp}) \right|
		\mbox{\hspace{4em}[by {\sc Lemma 2}]}\\
		%\mbox{\hspace{5em}[by Lemma 2]}\\
  & \leq & \left| c_p^{(i)}(T+\alpha\Delta_{rp})-c_r^{(i)}(T)\right| 
    + \left| c_r^{(i)}(T)-c_q^{(i)}(T+\alpha\Delta_{qp}) \right|\\
  & \lesssim & 2(\varepsilon+\rho S+|\alpha-1|\Delta) 
		\mbox{\hspace{10em}[by Lemma 4]}
\end{eqnarray*}
�� �����Ѵ�.
\hfill $\blacksquare$
\end{lemm}

\begin{lemm}.\rm
 ���� i�� ���� Ŭ���������� S1�� �����ϰ� Ŭ�� $c_p$ �� $c_q$��
$T^{(i+2)}$���� �����̶�� ������ $c_r$�� $S^{(i)}$�� ���� �ð� $T$�� 
���� ������ �����Ѵ�.
\begin{eqnarray*}
	\left| c_p^{(i)}(T)+\alpha\bar{\Delta}_{rp}-
	\left[c_q^{(i)}(T)+\alpha\bar{\Delta}_{rq} \right] \right|  <
	(\delta+ 2\alpha\Delta)
\end{eqnarray*}
{\gr����}:  $|\bar{\Delta}_{rp}|$�� $|\bar{\Delta}_{rq}|$�� $\Delta$���� 
�۴ٴ� ���� S1���� ���� ���� ���� �� �ִ�.
\hfill $\blacksquare$
\end{lemm}

\noindent{\bf\gr���� 1.}
 A1-A2�� �����ϰ� ���� 
\begin{eqnarray*}
 n & > & { 4\alpha-1 \over 2\alpha-1}m \\
\delta & > &\mbox{max}
	\left\{{ (2-2\alpha)n+(4\alpha-1)m \over n}\delta 
	+ { (4-2\alpha)n + (4\alpha-4)m \over n}\varepsilon \right.\\
     & & \left. \mbox{~~~~~~~~~~~~~~}
	+ \rho \left( {2(n-m)S \over n}+ R \right) 
	, \delta_0+\rho R \right\}
\end{eqnarray*}
�� �����ϸ�, $\Sigma=\Delta$�μ� MCNV�˰������� S1,S2�� �����Ѵ�\vspace{2ex}.

\noindent {\gr����}: ������ induction����� ��� �Ѵ�.
$i=0$�϶��� A1���� ���� �����Ѵ�. S1�� $i$�� ���Ͽ� �����Ѵٰ� 
�����ϰ� $i+1$�϶� �������� ���� Lemma���� ����Ͽ� �����ϰڴ�.

$T^{(i+1)}$�� $T$�� ������ ǥ������.
���� $R^{(i+1)}$�� ���� �ð�$T'$�� ���� ������ �����Ѵ�. 
\begin{eqnarray*}
\lefteqn{ \left| c_p^{(i+1)}(T')- c_q^{(i+1)}(T') \right|  
      <  \left| c_p^{(i+1)}(T)- c_q^{(i+1)}(T) \right| + \rho R } \\
      %\mbox{\hspace{10em}[by A2]}\\ 
  & = & \left | c_p^{(i)}(T+\alpha\Delta_p) 
	       - c_q^{(i)}(T+\alpha\Delta_q) \right | + \rho R 
      \mbox{\hspace{1em}[from the algorithm]}\\ 
      %\mbox{\hspace{4em}[from the algorithm]}\\ 
  & \approx & \left | c_p^{(i)}(T)+\alpha\Delta_p 
	       - \left[c_q^{(i)}(T)+\alpha\Delta_q \right] \right | + \rho R 
      \mbox{\hspace{3em}[by {\sc Lemma 2}]}\\ 
      %\mbox{\hspace{6em}[by Lemma 2]}\\ 
  & = & \left | \left( {1 \over n}\right) \sum_{r=1}^{n}
 	  \left( c_p^{(i)}(T)+\alpha\bar{\Delta}_{rp} 
	- \left[c_q^{(i)}(T)+\alpha\bar{\Delta}_{rq}\right]\right)
	\right | + \rho R \\
  &&  \mbox{\hspace{13em}[by definition of $\Delta_p$ and $\Delta_q$]}\\ 
  %&&  \mbox{\hspace{14em}[by definition of $\Delta_p$ and $\Delta_q$]}\\ 
  & \lesssim & \left( {1 \over n}\right) [ 2(n-m)(\varepsilon + 
  		|\alpha-1|\Delta
	+\rho S) + m(\delta + 2 \alpha\Delta) ] + \rho R\\
  &&    \mbox{\hspace{15em}[by {\sc Lemma 5,Lemma 6}]} 
  %&&    \mbox{\hspace{14em}[by Lemma 5,Lemma 6]} 
\end{eqnarray*}
$\Delta \approx \delta + \varepsilon$�̹Ƿ� ���� ���� �����ϸ� 
$R^{(i+1)}$�� ���� �ð�$T'$�� ���� 
\begin{eqnarray*}
\left| c_p^{(i+1)}(T')- c_q^{(i+1)}(T') \right|  < \delta 
\end{eqnarray*}
�� �������� �� �� �ִ�. ���� {\gr���� 1}�� �����Ѵ�.
\hfill $\blacksquare$
%\end{document}
