		 ᫥  ࠢ
     筮 ⭮,      x4
    ।⢥.  x4 ⥭,      
    x2.  த  ⮬ ०  祭 -
    ⠫ ६  ।.  ᬮਬ 
    ࠢ  tridiagonal ⥬. ஬     ᫥
    ࠢ,  ࠢ    ६ .

		g1x1 + h1x2               = b1
		f1 xi-1 + gi xi + h1 xi+1 = bi       2 <= i <= n-1
			  fn xn-1 + gn xn = bn

		᫥⥫     襭
    tridiagonal  ⥬  ࠢ      . 9-7.
        for  横,   믮
    n - 1 樨 ( ਭ ࠧ୮   ⥬ = n).
        for  横 ॡ  ﭭ  ६.
    ⥫쭮, ᫮ ᫥⥫쭮  ⬠  ⮡
     tridiagonal ⥬    ࠢ  -  Q(n).


     9-7 ᫥⥫  襭  ⥬
    tridiagonal ࠢ.  믮 9n - 8  -
    権  饩 窮, ਭ騥 ࠦ f[i+1]/g[i]
    業 ⮫쪮  ࠧ   ࢮ for 横.

    TRIDIAGONAL.SYSTEM.SOLVER (SISD)
    (            ):
    {      蠥  ⢮ ࠢ
		g1x1 + h1x2               = b1
		f1 xi-1 + gi xi + h1 xi+1 = bi       1 <= i <= n
			  fn xn-1 + gn xn = bn
     }
     global     n                             {ࠧ୮ ⥬}
		f[2..n],g[1..n],h[1..(n-1)]   {樥  }
		b[1..n]                       { ⠭}
		x[1..n]                       { 襭}
     begin
	for i <- 1 to n-1 do
	  g[i+1] <- g[i+1] - ( f[i+1]/g[i] ) * h[i]
	  b[i+1] <- b[i+1] - ( f[i+1]/g[i] ) * b[i]
	endfor
	for i <- n downto 2 do
	  x[i] <- b[i] / g[i]
	  b[i-1] <- b[i-1] - x[i] * h[i-1]
	endfor
	x[1] <- b[1]/g[1]
     end



     9-8
    ⮪ ࠬ , -
     ᨬ    
    ࢮ 横 襭 tridiagonal
    ⥬  . 9-7,  ⥬
    ࠧ 4.    -
    設 - ᠬ  ,
    ।饣  設. -
    騥 㣨 ।⠢ 窨,
      祭 ६ -
      ࠦ ᮤঠ饣
    ।饥 祭.

		    ।        
    ᯠࠫ, ᫥  ᨬ . 㭮 9-8 -
    ࠬ ⮪   ࢮ 横 ⬠ , -
    饣 ⥬ ࠧ 4. 뢠騥 㣨  ।⠢
    ࠧ   祭 ६    -
     ᮤঠ饣 ।饥 祭. ⮪  ࠬ
        ,     ᯥ᪨      
      ࠫ . ⮡ ⨣ ண  -
    ࠫ,    㣮  室  襭 .
    砫,  ⨬ ।⠢  n ࠢ ᫥騬
    ࠧ .   ᥢ६ x0  x_n+2,  ࠢ 0.
        :
	fi * x_i-1  +  gi * x_i+1 = bi   1 < i < n   (9.14)

    १ᠢ ࠢ 9.14 ⮡   x,  砥
	xi = (bi - fi * x_i-1 - hi * x_i+1 ) /gi   1 < i < n    (9.15)

    ᫨   
     ᥢ६ x_-1  x+2,  ࠢ 0,
      ᯮ짮 ࠢ 9.15 ⮡   
    x_i-1    x_i+1   ࠢ 9.14:

	fi * (b_i-1 - f_i-1 * x_i-2 - h_i-1 * xi ) / g_i-1 +

	+ gi * xi + hi * (b_i+1 - f_i+1 * xi - h_i+1 * x_i+2 ) /

	/ g_i+1 =  bi          1 <= i <= n             (9.16)

    ⮡   ࠢ  ।塞
	Yi = fi / g_i-1        1 <= i <= n
	Zi = hi / g_i+1        1 <= i <= n             (9.17)

       ९  
	Yi * f_i-1 * x_i-2 + (gi - Yi * h_i-1 - Zi * f_i+1 ) *

	* xi - Zi * Hi+1 * x_i+2 = bi + Yi * h_i-1 + Zi * h_i+1

			       1 <= i <= n              (9.18)

		⨬  ८ࠧ
     ࠧ 祭 x  ax  x_i-2    x_i+2 .
    ࠢ  xq, x4, xq,..., x "  ନ
    tridiagonal ⥬  n/2 ६묨 . ਬ ⮩
    ⮤ ४ᨢ  ,  뢠
    ⭮- 㬥襭  横᪮ 㬥襭,
    騩 tridiagonal ⥬  ࠢ.  -
    -  㬥襭    ᭠砫    Hockney
    (1965).
	    㭮 9-9    ⭮-  
    㬥襭  ⥬ ࠧ୮  8.
     ࢮ 蠣 樥 x1, x3, x5,   x7  㤠;
     ⥬ - tridiagonal   ⮫쪮  ६
     ஢묨 ᠬ.  ஬ 蠣 樥  x2
     x6 㤠.  蠣  x4 㤠,    ⠫  
     ࠢ   .  ᫨  ⮫쪮
    祭 x8 ⭮, 祭 x4      .  
    ᫨ 祭 x8  x4 ,     ।
    祭 x2  x6,   ⮫쪮 x2, x4, x6,  x8 ,
     室 祭  x1, x3, x5,  x7.  ⭮-
       㬥襭 뢥  ᥢ 
    . 9-10.   ६ ⭮-⭮ 㬥襭 =
    Q(n), ⠪   ᫥⥫쭮 ⬠  ࠭.
    , ⭮-⭮  㬥襭    室  
    ᯠࠫ,    .  9-9, ᥣ  
    ७  for  横  믮 ࠫ쭮.  
    믮 ࠫ ⭮-    㬥襭
     ᫥⥫쭮 筮 ⥬  ਫ 䥪⨢-
     襭  tridiagonal  ⥬  ࠧ୮   65536.
    ᮡ  ᯠࠫ  ᪮७  ⮣ -
    ⬠ 뢠  . 9-11.

     9-9    ࠬ   ⭮-
     㬥襭  ࠭ ६  tridiagonal ⥬
    ࠧ୮ 8.















     9-10. ᫥⥫쭠 ॠ ⬠ ⭮-
    ⭮ 㬥襭 .

    ODD.EVEN.REDUCTION (SISD);

    global      n
		f[1..n],g[1..n],h[1..n]
		b[1..n]
		new.f[1..n],new.g[1..n]
		new.h[1..n],new.b[1..n]
		x[1..n]
		d
		Y[1..n],Z[1..n]
    begin
	for i <- 0  to  (log n)-1 do
	  d <- 2~i
	  for j <- 2 * i + 1   to  n-1  step 2*d  do
	    Y[j] <- f[j]/g[j-d]
	    Z[j] <- f[j]/g[j+d]
	    new.f[j] <- -Y[j] * f[j-d]
	    new.g[j] <- -Z[j] * f[j+d] - Y[j] * h[j-i]
	    new.h[j] <- Z[j] * h[j+d]
	    new.b[j] <- b[j] + Z[j] * b[j-d] + Z[j] * h[j+d]
	  endfor
	  Y[n] <- f[n]/g[n-d]
	  f[n] <- -Y[j]/f[n-d]
	  g[n] <- g[n] - Y[n] * h[n-d]
	  b[n] <- b[n] + Y[n] * b[n-d]
	  for  j <- 2*i + 1  to  n-1  step  2*d  do
	    f[j] <- new.f[j]
	    g[j] <- new.g[j]
	    h[j] <- new.h[j]
	    b[j] <- new.b[j]
	  endfor
	  x[n] <- b[n]/g[n]
	  for i <- (log n)-1  downto  0 step  -1  do
	    d <- 2^i
	    x[d] <- (b[d] - h[d] * x[2*d] ) / g[d]
	    for j <- 3*d to n  step  2*d
	      x[j] <- (b[j] - f[j] * x[j-d] - h[j] * x[j+d] ) / g[j]
	    endfor
	  endfor
       end


     9-11. ᪮७ ࠡ (ᯫ譠
    )  ᯠࠫ ( 筠
    ) ࠫ쭮 ⭮-⭮
    㬥襭  ᫥⥫쭮 -
    筮    tridiagonal  ⥬  ࠧ
    65,636.



	 뢠 .9-11,   -  ᯠࠫ-
     ,  ᪮७ 祭.
     ᫥㥬 稭  ⮣. 饥 ᫮ 権 
    饩 ⮩ 믮塞  ᫥⥫  ⬮
     . 9-7 -

						    (9.19)

    饥 ᫮ 権  饩 ⮩ 믮塞 ⭮-
     ⬮ 㬥襭 -




						    (9.20)

      ⭮襭  ࠢ  9.19  9.20   :

						    (9.21)

          ࠫ쭮 ॠ樨 ⭮-⭮
    㬥襭 䥪⨢ 쥥 祬 50 業⮢.


    9.4    

		  ⮬  ࠧ       뢠
    ࠫ ᮢ 㤠, 饨⭮  ⬠
     襭  ⥬ Ax = b    A  
    ⫨        ந  ᯮ.
    ᮢ 㤠 㬥蠥 Ax = b  孨  㣮
    ⥬ Tx = c,    ⭮⥫쭮  ⮤
    ⭠  ⠭.     ப 
    ⥬ 㬬 ⮩  ப   㣮 ப ⥬,
      㫥 ⥫.  ᯮ짮   -
    ⮤  ࠧ 9.3 ⮡ ࠭ ⫨   -
       ᭮     tridiagonal  ⥬.
    ᮢ 㤠 ᯮ   ᠬ ਥ.
	    㭮 9-12    ⬠.
      ⫨        
    ⮫ 㤠.  蠣 i ⫨        
      ⮫ i 㤠塞,    ப  j,
      i+1 <= j <= n,  㬬 ப j  cப i, 
     -a[j,i]/a[i,i] . ᫥ n - 1 ⠪ 樨,  
    ⥬ -  孥 㣮쭮 ଥ.
	     ᠭ אַ ᮢ ⬥ 㤠 ,
    ப  i - pivot ப ,   ப ᯮ㥬 
    ࠢ 㫥  ⫨    ⮢ 
      ⮫ i.   室      
    ᫮  ⠡쭮    ஢  .  ,
    ⮩ ਠ, 뢠 ᮢ 㤠   
    ⮬, ந  १.  蠣  i  -
    ᮢ 㤠    ⮬,  ப  i - n
    饬 ப 祩  i- ⮫   ᠬ  讥
    ᮫⭮ 祭.  ப     ப  i .
		          ᯮ  ⥫
    pivot ப ( ⥯ ப i ) , ⮡   
    ⫨       ⮫ i  ப (i+1) - n.
    ᫥⥫  ᮢ  㤠   .
    9-13.  ॥  祬  pivot ப  ப i    -
    樨,   ᯮ  ᢥ.    ᨢ
    pivot[i] ᮤন ⨢   ஬ ப i -
    짮  pivot ப. 㣮 ᨢ   -
    祭 । ᯮ짮  ᯥ᪠ ப
      pivot  ப;  ᨢ marked[i] ⠭ 
    1  ப  i  롨ࠥ  pivot ப.

    FIGURE 9-12.  祭 樨 i ᮢ ⬠ 㤠,
        ⮫ i   ப j  ப i
     0   ⠭  ப i  ப j.











	    । ᪮쪮  室 ᮢ
    㤠  ࠫ樨. 砫,  ⠥  -
       ࠢ 饥 ᫠  饩
    窮  ⬠  .9-12.
                                                                                                                                
                                                                     



 9-5 . ࠫ쭠  ⬠ ⭮ ⠭.
		  (ਬ⥫쭮  UMA ⨯).
  