
       3. ஥: ᫥ 祭   ६
	  ⪨  ⪥ G^k,  㭪  ⮭ ६-
	   ⪨  ⪥ G^(k-1). ⮩  ஥樨,
	  뢠  樥, 砥 ଥ x^(k-1)_ij
	  ६ x^k_ij . ਬ, ᯮ    奬
	  ௮樨 ६ x^2_4,4 㤥 祭o -
	   ६ x^1_4,4.


     9-26. ਬ ⮪, -
    㥬  ⬥ -
    ⪨. 砫쭠 (16x16) ⪠ -
    G^0. G^1 - 8x8 ⪨, G^2 - 4x4
    ⪠,  G^3 - 2 x 2 ⪠.



	   Tॡ  裡  ⬠ ५樨 ᠭ 
    ।  ࠧ.  뢠 裡 ॡ㥬 
    প ௮樨  ஥樨  㬥 ᨢ  
    㡠.
		।,   ⮡ࠦ  砫
     G^0  n x n ᨢ ஢. 믮  ५-
    樨  G^0 ॡ ⮫쪮 ᠬ  ᥤ 裡. -
    ,    뢠  ⮡  믮
    ५    ⪠ G^1, G^2,..., G^(log n) 
    ᬥ. 饭 ஢ -  ﭨ   믮-
     ५樨  G^1,  ﭨ   믮
    ५樨  G^2,  ⠪ .  ᨬ  
    । ⥪,           
    ⥫쭮 ⢨   䥪⨢  ⬠.  -
      ᬮਬ ⪨ ⮡ࠦ  G^0...G^(log n -1)
     㡥.   㬥 ᨢ  
     ᯮ짮 筮   (Gray).   -
    ,   ⮡ࠦ ⬥⪨ ⪨ G  㧫 㡠
    ⮬   ᥤ ⮢ ᨢ ⮡ࠦ
     ᥤ 㧫 㡠. ,   室 -
    ࠦ ( o ୮   ⪨, G^0...G^(log n -1)),
    ⮬   筮 ⢠ ᮥ.   -
     宬 砥, 㧥   4* log n - 2  ᥤ
     n x n 筮 ᨢ,   ६  
    ⮫쪮  2 * log n  ᥤ    㡥  ࠧ୮
    n * n. ਬ, ᬮਬ 8 x 8   -
    㥬  . 9-27.  18  10 ᥤ. 
      㧥    64-㧫  㡥    ⮫쪮
     ᥤ, ᨢ       
    ७ 1.


     9-27. ⮡ࠦ -
     ⪨  
    ᯥ稢,   ᥤ
      G^0 ⮡ࠦ
     ᥤ 㧫  㡥,
     ᥤ   G^1 
     G^2 ⮡ࠦ  㧫 
    ﭨ 2  㡥.



	     ⮩ 稭  砥  ᨢ 
     ⠪, ⮡ ᥤ 㧫  G^0 뫨 ᥤ 
    㡥,  ⮡ ᥤ 㧫   G^1 ... G^(log n) 뫨
     ﭨ 2  㡥.    
    ஢   ,  ।⠢饥 ப 
    㣮 ।⠢饥 ⮫.  ᯮ  
    ⮡ ⮡ࠦ ᬥ ப  ⮫    ᬥ
    㧫 㡠 .


    9.9  

		 ⮬ ࠧ  뢠 ᮯ-
     ⮤ ࠤ, ᯮ㥬 ⮡ 㢥稢 ᪮-
     室 襭   ⥬   -
     樥⮢ ⥫쭠 ।.   ᮯ-
    殮 ⮤ ࠤ   :

	x(t) = x(t-1) + s(t)d(t)                 (9.35)

		 祭    x  -  㭪 ண
    祭  x, ᪠୮ ࠧ 蠣 s,  
    ࠢ d. 祭 x ࠭஢ 室,  設-
    ⢥ 砥,  n 権. ।  樥  1,  祭
    x(0), d (0)  g (0)   ⠭.  襩  ॠ-
    樨 ⬠ x (0)  d (0) 樠  㫥
     ,  g (0) 樠  - b.    t
     x (t)   蠣.

	 1:  ᫥  ࠤ
		  g (t) = Ax ( t - 1 ) - b

	 2: ᫥  ࠢ
	  d(t) = - g(t) + ( g(t)^ * g() * d(t-1) ) /
		     / ( g(t-1)^T * g(t-1) )

	 g(t)^T * g(t) ।⠢ ७ த
	࠭ᯮ஢ ஢ g(t)  g(t).

	 3: ᫥ ࠧ 蠣
	   s(t) = - d(t)^T * g(t) / ( d(t)^T * Ad(t) )

	 4: ᫥  ਡ x :
		x(t) = x(t-1) + s(t) * d(t)

	     殮  ࠤ 室  -
     ᫥ ,  襬 ⢥, n 権 ( Bertsekas
    & Tsitsiklis 1989 ).  ᥢ ᮯ殮 -
     ࠤ   . 9-28.  ணࠬ  뢠
    ணࠬ INNER.PRODUCT  MATRIX.VECTOR.PRODUCT .
		  ᬮਬ  ࠫ
    ॠ ᮯ殮 ⬠ ࠤ  ।-
     ⥪ . ਬ,     
     쭮     ப A, ⠪  ᮮ-
     ⮢ ஢ b, d,  g. ᭮ ⮩ -
    樨 , ⢥ ୠ   ந-
      㭪権 INNER.PRODUCT  MATRIX.VECTOR.PRODUCT.
	       ࠫ쭮 ᨨ 㭪樨 INNER.PRODUCT,
        㬬    १⮢.
      ᫨  ஬  㬬,  
    믮 㬥襭 㬬  㣨 ࠬ ⮡ -
    । ७ १.  ࠫ쭠  
    㭪樨  ᫮ ६ 裡  Q(n/p + log p) , 
    n - ࠧ  ⥬    p  -  ᫮  ஢.
		㭪  MATRIX.VECTOR.PRODUCT  ॡ
    ⮡        b 
    㣮   ன ⬥⪥  祭 ᫥-
    .  ᯮᮡ ᤥ  - ꥤ  b -
    ஢    , ⥬  
    ।  ᨢ b  㣨 .  ⥣
    ਢ   ᫮ ६ 裡 Q(n * log p).


     9-28. ᫥⥫ ਠ ⬠ ᮯ殮
		  ࠤ.

    CONJUGATE.GRADIENT(SISD);
     Parameter  n               {ࠧ ⥬}
		e               {਩ 室}
	input   a[1..n][1..n]   {䨨業  ⥬}
		b[1..n]         {ࠢ  ࠢ}
	output  x[1..n]         { 襭}
	global  d[1..n]         { 㪠⥫}
		g[1..n]         { ࠤ⮢}
		i               {}
		iteration       {樮 ᫮}
		s               {ࠧ 蠣}
		denom1,denom2   {६ ६}
		num1,num2
		tmpvec[1..n]
	begin
	  for i <- 1 to n do
	    d[i] <- 0
	    x[i] <- 0
	    g[i] <- -b[i]
	  endfor
	  for iteration <- 1 to n do
	    denom1 <- INNER.PRODUCT(g[1..n],g[1..n])
	    g[1..n] <- MATRIX.VECTOR.PRODUCT(a[1..n][1..n],x[1..n])
	    for i <- 1 to n do
	    g[i] <- g[i] - b[i]
	  endfor
	  num1 <- INNER.PRODUCT(g[1..n],g[1..n])
	  if num1 < e
	     break
	  endif
	  for i <- 1 to n do
	    d[i] <- -g[i] + (numerator/denominator) * d[i]
	  endfor
	  num2 <- INNER.PRODUCT(d[1..n],g[1..n])
	  tmpvec[1..n] <- MATRIX.VECTOR.PRODUCT(a[1..n][1..n],d[1..n])
	  denom2 <- INNER.PRODUCT(d[1..n],tmpvec[1..n])
	  s <- -num2 / denom2
	  for i <- 1 to n do
	    x[i] <- x[i] + s * d[i]
	  endfor
	endfor
      end

      INNER.PRODUCT(a[1..n],b[1..n]);
       value    a[1..n],b[1..n]
       Local    i,result
       begin
	 result <- 0
	 for i <- 1 to n do
	   result <- result + a[i] * b[i]
	 endfor
	 return result
       end

      MATRIX.VECTOR.PRODUCT(a[1..n][1..n],b[1..n]);
       value    a[1..n][1..n],b[1..n]
       local    i,j, result[1..n]
       begin
	 for i <- 1 to n do
	   result[i] <- 0
	   for j <- 1 to n do
	     result[i] <- result[i] + a[i][j] * b[j]
	   endfor
	 endfor
	 return result[1..n]
       end




    9.10. 祭.

		讥 ⢮ ஡  㪥   孨
     ࠦ  ⥬    ࠢ.    ⮩
      ᬮ५ ᪮쪮 ᫥⥫ ⬮,
    ᯮ㥬  襭 ⥬  ࠢ,   
    ᬮ५  믮 ࠫ ᨨ  -
       饤㯭     ।  ⥬
    .


 ।   祭
    x  