    9   


      ᬠਢ ᯠࠫ  ⬮  -
    㥬 ⮡  ⥬  ࠢ. 讥
    ⢮   孨᪨ ஡    
    ⥬  ࠢ.   ⥬  ॠ
      祭 訥,  - 訩
       ⥬ 䥪⨢  ࠫ  -
    .  9.1  ।⠢塞  ਬ   ।⠢塞
    ନ ᯮ㥬  ⠠ .  9.2 -
    9.4 뢠  ⮤  襭    -
    ⥬.  9.2  ᫥㥬 ࠫ ⭮ ⬠
    , ᯮ㥬   襭  孨  㣮
    ⥬.

     9.3 뢠  ⭮-⭮  㬥襭 -  ࠫ-
        襭    tridiagonal    ⥬.
    ࠫ 饨⭮ ᮢ ⬠  㤠
    㦤  9.4.  9.5 - 9.9 뢠  ᢥ-
    ,  樮, ⮤.  9.5  뢠  ꥬ-
     ࠫ Jacobi  .    9.6  㦤
    ᯮᮡ ࠫ樨 Gauss-Seidel ⬠,  -
       室  襭  祬  Jacobi  -
    . Jacobi  ५  ᫥⥫쭠  
    ५, ਠ ।  ⬮, 祭 
    ⮣ ࠧ 9.7.

     9.8 뢠 ⮤ ⪨,    -
        ᫮  襭      ७-
    樠  ࠢ.    祭, ࠧ  9.9  뢠
    ࠫ  ᮯ殮  ⮤  ࠤ,   
    converging    ᯮ짮 ⮡  -
     ⥬  ࠢ  ।  ᢮-
    ⢠.

    9.1 

     ࠧ ।   ᫮  -
      ஡   ࠦ    ⥬  
    ࠢ.

    । 9.1.  ࠢ  n ६  x1, x2,
    x3,..., xN - ࠢ ஥  ࠦ  
	  a1x1+a2x2+ a3x3 +... aNxN= b (9.1)
     a1, a2, a3,...,aN,   b  - ⠭.

    । 9.2. 筮 ⢮    ࠢ  
    ६ x1, x2, x3,..., xN 뢠 ⥬  
    ࠢ   ⥬o.  ஢  s1,  s2,...,
    sN - 襭  ⥬  ࠢ ⮫쪮 ᫨
    ⠭ x1 = s1, x2 = s2, x3 = s3,..., xN  =  sN
    㤮⢮  ࠢ   ⥬.
	     ⥬ n  ࠢ  n ६:
	a11x1+ a12x2+ a13X3... + a1NxN = b1
	a21x1+ a22x2+ a23x3... + a2NxN = b2 (9.2)
	a31X1+ a32X2+ a33X3... + a3NxN = b3
	   . . . . . . .  .  .  .  .  .  .
	aN1x1+ aN2x2+ aN3x3... + aNNxN = bN

    筮 ࠦ  Ax = b,  A -
    n x n  ᮤঠ AijS  x  b - -
     n- ࠭騥 XiS  BiS, ᮮ⢥⢥. ᯮ-
      祭 ⫨   ⮢  A -
    । ᪮쪮 㤭   ⭮⥫쭮 x.   -
     饬 砥, ᫥⥫  騩 ᫮-
     ६ O(n~3)   ⥬  ࠢ.


    । 9.3.  n x n  A -  孥 㣮쭮
		      ଥ , ᫨
			i > j = > Aij = 0

    । 9.4.  n x n  A -   㣮
		      ଥ, ᫨
			i < j = > Aij = 0

     㣮쭠   㣮쭠 ⥬ 蠥 
    ६ (n~2)  ᫥⥫ .

    । 9.5.  n x n  A  -  tridiagonal ଥ, ᫨
		       ⮫쪮 ᫨
			| i -  j | > 1 = > Aij =0

     ⥬ Ax = b 뢠 tridiagonal ᫨  -
     樥⮢ A - tridiagonal.  ᫥⥫
      ᫮ ६  Q(n)    襭
    tridiagonal ⥬.  ᬮਬ,   tridiagonal
     ⥬  ᯮ짮 ⮡   ஡-
    . ।     ⨬  ।  ⠭襥
    । ⥬  ভ ஢饣 ਠ
    ( . 9-2 ).

     9-2. ஢ থ
        䨪஢ 祭 ⥬-
     T1  T2.  ⨬ 㧭 ⥬-
      窠 x1, X2, x3, x4,
          ᥣ-
    ⮢  ࠢ .


		 ਭ  থ
     த 祭, ⮬  窨   몥
    ࠧ   ࠢ  ⥬.    
      뢠 ⥬  㭪  -
        ভ.  ਭ  ⥬ T1 
    T2   ভ ⠭ १ ⠪  ﭭ묨
    筨 ⥯.  祭,  ਭ  থ -
    饭  ஢ ਠ. 㣨 ᫮,  
     ⥯  ஭ ভ   -  ।
    ⥯ ⮫쪮  .
	   宦 ⠭襩 ⥬   -
     ࠢ୮ ᯮ ⬥⪠ x1, x2, x3,  x4 
    ࠧ  ⥬  ࠢ:
		 X1 - 0.5x2                   = 0.5 T1
		 - 0.5x1 + x2 - 0.5x3         = 0
			 - 0.5x2 + x3 - 0.5x4 = 0         (9.4)
				- 0.5x3 + x4  = 0.5 T2

       ।   㤥 ᯮ짮
        ⮩ .

    । 9.6.  n x n   A  ஢  ,
    ᫨
	| Aii | > SUM_i<>j | Aij |    1 <= i <= n.

    । 9.7.  n x n  A - ᨬ筠 , ᫨
		Aij = Aji        1 <= i , j <= n.

    । 9.8.  n x n  A  ⥫ ।,
		 ᫨  ᨬ筠, diagonally ஢ 
			Aij > 0      1 <= i <= n.


    9.2    .

     ⮬ ࠧ  뢠 ࠫ  ⬠,  -
    㥬  襭  ⥬    Ax = b , 
    A -  孥 㣮쭮 ଥ.
		 ⥬  ࠢ Ax = b,
     A -  㣮쭠  n x n , 
    ⭮ ⠭ 蠥  ⥬  ६ Q(n~2).
     ᬮਬ  ᯮ ⮩ ਬ. ।-
    ,   ⨬  ⥬
		1x1 + 1x2 - 1x3 + 4x4 = 8
		     -2x2 - 3x3 + 1x4 = 5
			    2x3 - 3x4 = 0
				  2x4 = 4         (9.5)

       ᫥ ࠢ ।⢥, ⠪ 
      ⮫쪮 筮 ⭮. ᫥ ⮣,  
    ।  x4 = 2,    㣨 ࠢ
    ⠢  x4 祭   ४஢  祭 b
    ମ:
		1x1 + 1x2 - 1x3     = 0
		    - 2x2 - 3x3     = 3
			    2x3     = 6
				2x4 = 4         (9.6)

      ࠢ  ⮫쪮 筮 ⭮,
     ⮥  뤠 x3  =  3.  ,    -
    㥬  ଠ ⮡    ࠢ  
    ⮣:
		1x1 + 1x2           = 3
		    - 2x2           = 12        (9.7)
			   2x3      = 6
				2x4 = 4
     ⨫ ஥ ࠢ ⮡ ᮤঠ  ⮫쪮  -
    筮 ⭮,    b2  a22    x2=-6. ᫥
    ⠭ ( x2 a12 )  b1  
		1x1              = 9
		    -2x2         = 12
			 2x3     = 6
			     2x4 = 4            (9.8)

       x1 = 9.
    ᫥⥫   믮 ⭮ ⠭
      . 9-3.  ६ ⮣ ⬠ - Q(n~2).

      9-3  ᫥⥫    Global    n
     ⭮ ⠭.              a[1..n][1..n]
      㣮쭠                  b[1..n]
    ⥬  ࠧ୮  n, -              x[1..n]
      ᫮ ६                i
    Q(n~2).                                     j
				      begin
					for i <- n downto 1 do
					  x[i] <- b[i] / a [i][i]
					  for j <- 1 to i-1 do
					    b[j] <- b[j] - x[i]a[j][i]
					    a[j][i] <- 0
					  endfor
					endfor
				      end

	    ६  ࠫ     ⭮
    ⠭ ?  㤭 । ᢮⢥  ࠫ-
     ⬠  ⮣ ᫥ .    -
         ࠫ (  -
    ⮪ ࠫ ) 祢.     ᢮-
    ⢠:
      1.  ᮤন  設  祭   ࠧ  
	 ६ 祭 祭.
      2.  ᮤন  設   ६,  ன
	       祭.
      3.  ᮤন  ५   ᯮ㥬 ᨬ
	  ६ ⠢  ࠢ ஭ 
	 祭  ६  祭 祭  
	  . ५ ࠢ   ६  -
	 祭 祭.
		 ᯮ짮  ࠢ ⮡ ᮧ  
      ⭮ ⬠   ਬ⥫쭮    -
    孥 㣮쭮 ⥬ ࠧ 4 ( . . 9-4 ).  -
           ⭠(⭠)  設
    ᮮ⢥  ६ b[i],  ⠪    
    ⭮   ६. ᫨ ⮫쪮  
     ᮧ,  ન㥬  設 ᮣ᭮  ᫥-
    騬 ࠢ:
      1. ᫨  ५  室  設, 設 
	  0.
      2. ᫨ 設   ࠩ   室 ५,
	 ⪠ ࠢ 1  ᨬ쭠 ⪠  設 易-
	   室饩 ५. ⪨  設  . 9-4
	 뫨 祭, ᯮ  ࠢ. ⪨ ।⠢
	 㡨   ᫥   . 
	 ᯮ짮 㦨 㣨 ⮡ 㪠뢠  
	 ᪨  ⥩  .  ᪮ 
	 祢,   x   ६.
    ᭮,   ਠ ਣ  ࠫ樨.
    ࠫ , ࠧࠡ⠭  UMA
    ୮ ⥬, ।⠢   . 9-5.  ⥯
    ⠫樨  쪠;      ࢮ  樨  
    ⮫쪮 n - 1 㬭  n - 1 ⠭.  ᪮  -
     ண,   㬥蠥   1
    㬭  1 ⠭.  ⮩ 稭     
        ⨣ ᮪ ᪮७  -
     த樨.
		㭮 9-6    ᪮७  ᪠
    த樨 ⨣⮥ 訬 ࠫ   -
       ᫥ 㦥 ᫥⥫쭮 ᨬ筮
    UM ୮ ⥬.        䥪
    嫠 (Amdahl): ᪮७ ᪠ த樨  
    䨪஢  ᫥ ஢ 㢥稢  㢥祭
    ࠧ୮ .


		 9-4    ᫥-
    ⥫쭮 ⭮ ⬠  饣  -
     ⥬ ࠧ 4.   b -
    , ⠪  grapp 뢠  設    -
    祭  . ⪠   設  㪠-
     㡨   . ᪨   ᢥ稢-
    .











     9-5 . ࠫ쭠  ⬠ ⭮ ⠭.
		  (ਬ⥫쭮  UMA ⨯).
       Global    n                {୮ ⥬}
		 p                {᫮ ஢}
		 a[1..n][1..n]    { }
		 b[1..n]          { }
		 x[1..n]          { }
		 i                { ⮫殢}
       local     j                {䨪 }
		 k                { ப}
       begin
	 for i <- n downto 2 do
	   x[i] <- b[i] / a [i][i]
	   forall Pj where 1<=j<=p do
	     for k <- j to i-1 step p do
	       b[k] <- b[j] - x[i]a[k][i]
	       a[k][i] <- 0       { ப ⨬쭠}
	     endfor
	   endforall
	 endfor
       end


     9-6 . ᪮७  ᪠
	      த樨  ⨣⮥
	     ࠫ ⬮
	     ⭮ ⠭ 
	   襭 㣮 ⥬
	   ࠧ筮 ࠧ.
                                                                     

    9.3 - 
     ⮬ ࠧ    ᫥
     ⬠  襭	tridiagonal  ⥬  
    ࠢ.  -  אַ  ,  室騩
     믮  ᫥⥫쭮 ,   -
    騩   ࠫ樨.  ன  ,  뢠
    ⭮- 㬥襭  横᪮ 㬥襭, 
     ᮪ ⠭ ய樮쭮,     
    ࠫ.
		  稭   ᬠਢ  אַ
    ᫥⥫쭮   ⬠.   ᬮ      ᫥
    tridiagonal  ⥬:
		16x1 + 4x2             = 8
		4x1 + 11x2 - 5x3       = 7
		      2x2 + 14x3 - 6x4 =13      (9.9)
			    5x3 + 18x4 = 24

      ⫨稥    孥  -
    쭮 ⥬    ⮫㫨    tridiagonal ⥬o,
       ᮤন  ࠢ  
    筮  ६.  ⮩ 稭     ꥤ-
     ࠢ ⮡ । 祭 ६.  -
     믮  樨   ⥬    ࠢ
      祭 襭 (  Anton 1981 ):
	1.   ନ ࠢ  ⫨  
	   ⠭.
	2.   ࠢ.
	3.  ⥫  ࠢ  㣮
	   ࠢ

	砫    ࠭塞  x1   ண  ࠢ ,
      ⢥ ࢮ ࠢ  ண ࠢ:

		16x1 + 4x2             = 8
		      10x2 - 5x3       = 5
		      2x2 + 14x3 - 6x4 = 13      (9.10)
			    5x3 + 18x4 = 24

	⥬    ࠭塞  x2    쥣  ࠢ ,
       ண ࠢ  쥣 ࠢ:

		16x1 + 4x2             = 8
		      10x2 - 5x3       = 5
			    15x3 - 6x4 = 12      (9.11)
			    5x3 + 18x4 = 24

	 祭,  㤠塞  x3    ⢥⮣ ࠢ ,
       쥣 ࠢ  ⢥⮣ ࠢ:
                                                                                                                                
		16x1 + 4x2             = 8
		      10x2 - 5x3       = 5
			    15x3 - 6x4 = 12      (9.11)
				  20x4 = 20

 ஦ 