
    9.5.1 ०  ⥬

	       ⨧  ७樠 ࠢ-
      ਢ  ࠧ०  ⥬.  -
    ,  ᬮਬ  㬥    । ⥬-
     , 㥬  . 9-22. 

     9-22. 㬥ୠ
     ᪠ ⮩稢
    ﭨ  室
    । ⥬.










     ⠫쭠 ⨭ 㦠   ஭ "஢
    " ( ⥬ 100' C).  ⢥ ஭ - "-
     " ( ⥬ O'  C).  饥  﫮
    뢠            ⨭.
      室  ⠭訩  । ⥬-
        100  ࠢ୮ ᯮ ⬥⪠, ନ-
     ᨢ  1010   ⨭.  - ਬ   -
    筮 ७樠쭮 ࠢ ண 浪.  
    ⮩稢  ।  ⥬  ﭨ  ,
     ७樠 ࠢ 뢠 祭 ६-
      ᥤ 窠 ᨢ :

	x_i,j = (x_i-1,j + x_i,j-1 + x_i+1,j + x_i,j+1) / 4   (9.25)

		      i    j  
    न⠬  ⮢  ᨢ .      ᮧ
     A   b   ᯮ짮  Jacobi  
    ⮡    x.       x    100
    ⮢,  A 㤥  ࠧ 100 x 100   
    b 㤥  ࠧ 100.  室 䥪⨢,  -
    ⮬   A ࠧ०,  ⮫쪮  ⫨ 
     ⮢  ப.  ﭭ ᫮ ⫨-
       ⮢   ப,    ⨬  
    ६  Q(n), ⮡ 믮  FOR  横  ᫥  -
     祭   x.
		訩 室 - 
    Jacobi ⬠  , ᯮ饣 ।饥 ࠢ,
    ஥ 믮   ᠬ ᫥   䥪⨢.
     ⮩ 楤 祭   ⬥⪠ ᨢ ६-
      ᮣ᭮ 㫥 :

	x'_i,j = (x_i-1,j + x_i,j-1 + x_i+1,j + x_i,j+1) / 4   (9.26)

	   祭   ࠢ  ࠢ -  祭
    ६, 祭    ࠢ.-  ਡ.
    ᫥⥫    襭  㬥୮  -
    襣 । ⥬   . 9-23.
		 ᬮਬ  ࠧࠡ뢠 ࠫ-
      ⮣ ⬠ 室饣    ॠ樨
     ⨪ ⨯ .    㤥
    ⢥⢥  ⢮ ⮢ 㬥୮  x  
    ᮮ⢥ ⮢  newx.    
      ,  ᫥ 祭  newx ॡ ⮫쪮
    祭  ᥤ ⮢ x. ᫨  
    祭 אַ㣮쭠   x    newx,  ᫥
    ⮢  newx   אַ㣮쭨  믮 -
     쭮 㯭 祭 x.  ᫥  -
    ⮢ newx  ࠥ אַ㣮쭨 ॡ 祭  ࠭-
        㣨 ஢. ᫨    砥
     ࠬ ⠪, ⮡  ᥤ  ࠢ-
     ᥤ ﬨ, ⮣ ᠬ   ᥤ 
      믮  ࠫ ⬮.
	      ᫨   ⢥⢥    -
      ப  뢭  ⮫殢 x   newx,
    ⮣    ᫥  newx  ନ
     ᨢ. ᫨   ⢥⢥  
    ⮢,  ନ  㬥 ᨢ.   裡
    ਬ   㡠 .     । 
     ࠬ ਢ    ஬  ?
	  ।,  ⨬ ࠧ n x n   p -
    .  饭 , ਭ  n -  ⥫
     p  SQR(p) . ᬮਬ ᭠砫  奬 ।-
        . 9-24a.    
    ࠢ  ᨢ  ࠧ (n/p) x n.  祭 
    樨  ७   뫠 祭
    n   ᢮ ᥤ   祭 n   ᥤ.
    ᫨  - ६   ᮮ饭   - ६ , 室
    ⮡ ।  筮  祭, ⮣ 饥 ६ ,
    稢   樥  ।饩 祭 -

		4 (  + n*B )                   (9.27)


	 9-23. ᫥⥫쭠  Jacobi ⬠
	 襭 㬥୮  । ⥬.

	JACOBI.ALGORITHM.2(SISD);

     parameter  n                       {⮢   ७}
		e                       {਩ 室}
		north[1..n],south[1..n]
		east[1..n],west[1..n]   {࠭ ᫮}
	global  x[0..(n+1)][0..(n+1)]   {襭}
		newx[0..(n+1)][0..(n+1)]{ 業 襭}
		diff                    {ᨬ쭮 }
		i,j                     {६ 横}
	begin
	   {࠭ ᫮}
	   for i <- 1 to n do
	     x[0][i] <- north[i]
	     x[n+1][i] <- south[i]
	     x[i][0] <- west[i]
	     x[i][n+1] <- east[i]
	   endfor
	   {樠 祭 ⮢ x}
	   for i <- i to n do
	     x[i] <- 50
	   endfor
	   {塞 業 x  祭 室}
	   do
	     diff <- 0
	     for i <- 1 to n do
	       for j <- 1 to n do
		 newx[i][j] <- (x[i-1][j] + x[i][j-1] +
			      + x[i+1][j] + x[i][j+1]) / 4
	       endfor
	     endfor
	     for i <- 1 to n do
	       for j <- 1 to n do
		  diff <- max( diff, | newx[i][j] - x[i][j] | )
		  x[i][j] <- newx[i][j]
	       endfor
	     endfor
	   while diff > e
	end

     9-24.   -
    ।   襭
    㬥o ⠭訩 -
     । ⥬-
      ⨪. -
     (a) । 16x16
    ᨢ  4   -
    筮 ०.  
    ࠢ (N/p) x n .
    ⥭   ।  ᥤ -
    .  (b) । 1616 ᨢ  16 -
    ࠬ  筮-ਥ஢ ०.  
    ࠢ    ࠧ  (n/SQR(p))*(n/SQR(p)). ⥭-
       ।  ᥤ .

		 ᬮਬ  筮-ਥ஢
    奬  ।  , 㥬   . 9-24.
        ࠢ  ᨢ  ࠧ (n/SQR(p))*
    *(n/SQR(p)).  祭  樨   ७
      뫠 祭  n/SQR(p)  ᥬ  ६
    ᥤ   祭 n/SQR(p)   ᥤ.  饥
    祭 ६  ᮮ饭 祭   樨 -

	       8 * (  + n * B / SQR(p) )               (9.28)

		  ।    筮-ਥ-
      室    筮-ਥ஢  室.

	 8 * (  + n * B / SQR(p) ) < 4 * (  + n * B ) =>

		A < ( 1 - 2 / SQR(p) ) * n * B =>       (9.29)

		n > A / ( B - 2*B / SQR(p) )

		ਬ, ।,   믮塞  -
    ࠫ  ⬠  . 9-23   64-୮
    ⨪  ண  = 50*. 筮-ਥ஢-
      ॢ室 筮-ਥ㥬  ,
    

	       n > 50 / ( 1 - 2/8 ) = 66                (9.30)

	   ਭ,  n - ⥫ p, ..  砥,
     筮-ਥ㥬   ॢ室
    筮-ਥ஢    N = 64,    -
    -ਥ஢  ॢ室  n =  128,  192,
    256,....     ᪮業஢  ୮
    裡 室, ⮡  祭 newx. -
    ୠ  - ⠪ ॡ, ⮡  쭮
    祭  diff.  ⨪ ⨯  
    蠣 㬥襭  ᫮ ६  Q(log p). 
    ࠫ樨 ࢮ  Jacobi-⬠  ""
     ⥬,    㦥   ᫮ -
     裡 Q(log p),  蠣 㬥襭  㢥稢 ᫮-
      裡  ⬠.  ன  Jacobi- ᭮
     ᥤ   ।   祭
    x  ஥  ॡ  ᫥ newx.  ⮬ ⬥
     Q(log p) 蠣 裡 㤥   .  -
     믮  ࠫ쭮 .   ஡
       , ⮬ 쭮 祭  diff  -
     ⮫쪮  k- 樨,  k - ஥ 楫
    ᫮ > l. 襥 祭  k  -  㭪 ⥪  ⨯
     . ᫨  k  ᫨誮  쪨, ६  ,
    室 쭮 祭  diff   쭥訥 樨
    室. ᫨  k  ᫨誮 让, ६  ,
    믮 쭥訥 樨  祭 x 㦥 室 
    襭.


    9.6 GAUSS-SEIDEL 

    Jacobi- ⠥  ⥬ ࠢ  Ax  =  b
    १ ७  祭 :

	_i(t+1)= (b_i - SUM_j<>i a_ij * x_j(t) ) / a_ii   (9.31)

     x_j(k) - 祭  x_j, ᫥  祭 樨 k.
    Gauss-Seidel    ⠥ 㢥稢 ᪮
    宦 祭  x   襭, ᥣ ᯮ  
      ᫥ 祭    x_j. -
    ਬ, ᫥饥 ࠢ    祭
    x_j    冷 業 - x1, x2,..., xN:

    _i(t+1) (b_i - SUM_j<i a_ij * x_j(t+1) -
		  - SUM_j>i a_ij * x_j(t) ) / a_ii         (9.32)

    o 冷 業 ⠪ . ਬ,  ६
     ஢  浪  xN, x(N-1), ...,  x1.
    Gauss-Seidel   뤠 ࠧ १
       ᠬ 室 ६, ᫨  冷  業
     . ᬠਢ ࠫ, ᢮⢥ Gauss-
    Seidel . 砫  ᬮਬ 砩,   A
    ⭠. ਬ (   魮),  ६ 業-
      浪 :  x1, x2, ..., xN. ᫨  A ⭠,
    ⮣   ⥫ ᫥⥫ ,
    ⮬  祭  x_i( t + 1 )  o  ।
    । 砭 ᫥ x_i+1(t+1),   1 < i < n.
	      ᫨  A  ࠧ०, ⮣ Gauss-Seidel
     - ee 室  ࠫ樨. ᬮਬ -
    襭  㬥୮  ࠢ ⥯, ᬮ७ ࠧ
    9.5. 祭     ⬥⪠ ᨢ 
    ᮣ᭮ 㫥 :

	x_i,j(t+1) = (x_i-1,j(t+1) + x_i,j-1(t+1) +
		    + x_i+1,j(t+1) + x_i,j+1(t+1)) / 4

    㭮 9-25a  ᨬ    4 x 4
    ᨢ ६. 砫    祭
    x_1,1 .   ⮫쪮  ࠫ  ᫨ x_1,1,
       x_1,2  x_2,1  ࠫ쭮.  ᫥묨
    祭ﬨ x_1,2   x_2,1  ࠫ   -
    ६  x_1,3, x_2,2,  x_3,1.    ᠬ ६
      ᫥e 樮 祭  x_1,1.
		த   ⮬  , ࠫ 
     ᫥饬 蠣   x_1,4, x_2,3, x_3,2, x_4,1,
    x_1,2,  x2,1.  祭  ६ ࠧ  
    .   ।⠢ 㯯 ६, 
     ஢ ६. 㭮  9-25b, -
    騩 ࠧ ६    , 뢠
    ᭮-୮ ᪮  ᨬ .


     9-25.() ᨬ    樨 Gauss-Seidel
    ⬠. (B)   梥  , ⮡ ન஢ 
    設  ᨬ , ⮬   ᬥ
    設   設  梥.  筮 뢠
    "᭮ - ୮"  奬 ᪨. 設,    ᠬ
    梥   ஢ ६  ࠫ쭮 Gauss-
    Seidel ⬥.












    9.7 JACOBI        
	 .

    Jacobi  ५ - ਠ Jacobi ⬠  -
       祭   x_i  १  
    ண 祭 x_i    祭  x_i,  塞
    ᯮ ⠭ Jacobi . Jacobi  ५-
       䨪樨,     ࠢ
    9.24 

      x_i(t+1) = (1-Y)*x_i(t) + Y*(b_i - SUM_j<>i a_ij *
			* xij(t)) / a_ij                  (9.33)

	     ᫥⥫쭠  ५ (SOR) - ਠ
    Gauss-Seidel ⬠,     祭
      x_i  १  ண 祭 x_i  
    祭 x_i, ᫥ ᯮ ⠭ Gauss-Seidel
    . ᫥⥫쭠  ५  -
     䨪樨   ࠢ 9.33 ( 9.32 ? ) 

    _i(t+1) = (1-Y)*x_i(t)+ Y*(b_i - SUM_j<i a_ij * x_j(t+1) -
		  - SUM_j>i a_ij * x_j(t) ) / a_ii         (9.32)

	      Y 롨ࠥ ࠢ쭮, Jacobi   -
      SOR  室  襭  ॥, 祬
    Jacobi    Gauss-Seidel  , ᮮ⢥⢥.



    9.8  

		⮤ ⪨ ନ  樮
    ⬮, ᯮ㥬  ᫮ 襭 
    ७樠 ࠢ.  ⮤ ⪨
       :
       1. 樮  室  襭 ॥ 
	   ⪠ 祬   ⮭ ⪠
       2. 樮  室 ॥, ᫨ 
	  砫 ਡ 祭 ६
    ⮤ ⪨ 室 ⭮ 襭  筮
    ७樠쭮 ࠢ 믮 樨    
    ⮭   묨 ⪠, ᯮ 祭, -
      ।饬  ⪨  樨 砫
    業  祭    祪 ⪨ (. .
    9-26).  ⮬ ࠧ  뢠  ᫥, 믮塞
    ⮤ ⪨  裡, 室  ⮡  믮
     ᫥  ⨪.
	   饭 ᬮਬ 믮 ⮤ ⪨
     㬥 ⪠. ।, 쭠 ⪠ G^0  
    ࠧ୮ n x n,  n - 魮 = 2. 稬 
       G^i,  1 <= i <= log n .   窮
    ⪨ (i,j) ,  ⪥ G^k  易 ६
    x^k_ij .  ⪨ 믮   ᫥:

       1. :  祭  x^ij  ⪥  G^k.
	   ᫥ 믮 ᯮ Jacobi,  Gauss-
	  Seidel, Jacobi  ५, SOR    㣮
	  樮 .
       2. ௮: ᫥ 祭  ⮭ ६-
	   ⪨  ⪥ G^k-1   㭪  
	  ६ ⪨  ⪥ G^k.   ௮-
	  樨    祭  x^(k-1)_ij , ⠭饥
	  ।  祭  G^k , ᠬ   ᯮ-
	   (i,j). ਬ,  ᯮ짮 ⮩ 奬
	  ௮樨, x^0_3,5 㤥 祭o ।ee 祭
	   x^1_2,4 , x^1_4,4 , x^1_2,6    x^1_4,6 .


ࠫ Jacobi -
     