Ռելակսացիայի մեթոդ

Ռելակսացիայի մեթոդ, գծային հանրահաշվական հավասարումների լուծման իտերացիոն մեթոդ։


== Մեթոդի նկարագրությունը ==
Գծային հավասարումների համակարգը

  
    
      
        
          {
          
            
              
                
                  
                    a
                    
                      11
                    
                  
                  
                    x
                    
                      1
                    
                  
                  +
                  …
                  +
                  
                    a
                    
                      1
                      n
                    
                  
                  
                    x
                    
                      n
                    
                  
                
                
                  =
                
                
                  
                    b
                    
                      1
                    
                  
                
              
              
                
                  
                    a
                    
                      21
                    
                  
                  
                    x
                    
                      1
                    
                  
                  +
                  …
                  +
                  
                    a
                    
                      2
                      n
                    
                  
                  
                    x
                    
                      n
                    
                  
                
                
                  =
                
                
                  
                    b
                    
                      2
                    
                  
                
              
              
                
                
                  …
                
                
              
              
                
                  
                    a
                    
                      n
                      1
                    
                  
                  
                    x
                    
                      1
                    
                  
                  +
                  …
                  +
                  
                    a
                    
                      n
                      n
                    
                  
                  
                    x
                    
                      n
                    
                  
                
                
                  =
                
                
                  
                    b
                    
                      n
                    
                  
                
              
            
          
          
        
      
    
    {\displaystyle \left\{{\begin{matrix}a_{11}x_{1}+\ldots +a_{1n}x_{n}&=&b_{1}\\a_{21}x_{1}+\ldots +a_{2n}x_{n}&=&b_{2}\\&\ldots &\\a_{n1}x_{1}+\ldots +a_{nn}x_{n}&=&b_{n}\\\end{matrix}}\right.}
  
բերենք այսպիսի տեսքի՝

  
    
      
        
          {
          
            
              
                
                  
                    P
                    
                      11
                    
                  
                  
                    x
                    
                      1
                    
                  
                  +
                  
                    P
                    
                      12
                    
                  
                  
                    x
                    
                      2
                    
                  
                  +
                  …
                  +
                  
                    P
                    
                      1
                      n
                    
                  
                  
                    x
                    
                      n
                    
                  
                  +
                  
                    c
                    
                      1
                    
                  
                
                
                  =
                
                
                  0
                
              
              
                
                
                  …
                
                
              
              
                
                  
                    P
                    
                      n
                      1
                    
                  
                  
                    x
                    
                      1
                    
                  
                  +
                  
                    P
                    
                      n
                      2
                    
                  
                  
                    x
                    
                      2
                    
                  
                  +
                  …
                  +
                  
                    P
                    
                      n
                      n
                    
                  
                  
                    x
                    
                      n
                    
                  
                  +
                  
                    c
                    
                      n
                    
                  
                
                
                  =
                
                
                  0
                
              
            
          
          
        
      
    
    {\displaystyle \left\{{\begin{matrix}P_{11}x_{1}+P_{12}x_{2}+\ldots +P_{1n}x_{n}+c_{1}&=&0\\&\ldots &\\P_{n1}x_{1}+P_{n2}x_{2}+\ldots +P_{nn}x_{n}+c_{n}&=&0\\\end{matrix}}\right.}
  
որտեղ 

  
    
      
        
          P
          
            i
            j
          
        
        =
        −
        
          
            
              a
              
                i
                j
              
            
            
              a
              
                i
                i
              
            
          
        
      
    
    {\displaystyle P_{ij}=-{\frac {a_{ij}}{a_{ii}}}}
  , 
  
    
      
        
          c
          
            i
          
        
        =
        
          
            
              b
              
                i
              
            
            
              a
              
                i
                i
              
            
          
        
      
    
    {\displaystyle c_{i}={\frac {b_{i}}{a_{ii}}}}
  Կգտնվի 
  
    
      
        
          R
          
            j
          
        
      
    
    {\displaystyle R_{j}}
   կապը այնպես, որ

  
    
      
        
          {
          
            
              
                
                  
                    R
                    
                      1
                    
                    
                      (
                      0
                      )
                    
                  
                
                
                  =
                
                
                  
                    c
                    
                      1
                    
                  
                  −
                  
                    x
                    
                      1
                    
                    
                      (
                      0
                      )
                    
                  
                  +
                  
                    ∑
                    
                      j
                      =
                      2
                    
                    
                      n
                    
                  
                  
                    P
                    
                      1
                      j
                    
                  
                  
                    x
                    
                      j
                    
                    
                      (
                      0
                      )
                    
                  
                
              
              
                
                  
                    R
                    
                      2
                    
                    
                      (
                      0
                      )
                    
                  
                
                
                  =
                
                
                  
                    c
                    
                      2
                    
                  
                  −
                  
                    x
                    
                      2
                    
                    
                      (
                      0
                      )
                    
                  
                  +
                  
                    ∑
                    
                      j
                      =
                      1
                      ,
                      j
                      ≠
                      2
                    
                    
                      n
                    
                  
                  
                    P
                    
                      2
                      j
                    
                  
                  
                    x
                    
                      j
                    
                    
                      (
                      0
                      )
                    
                  
                
              
              
                
                
                  …
                
                
              
              
                
                  
                    R
                    
                      n
                    
                    
                      (
                      0
                      )
                    
                  
                
                
                  =
                
                
                  
                    c
                    
                      n
                    
                  
                  −
                  
                    x
                    
                      n
                    
                    
                      (
                      0
                      )
                    
                  
                  +
                  
                    ∑
                    
                      j
                      =
                      1
                    
                    
                      n
                      −
                      1
                    
                  
                  
                    P
                    
                      n
                      j
                    
                  
                  
                    x
                    
                      j
                    
                    
                      (
                      0
                      )
                    
                  
                
              
            
          
          
        
      
    
    {\displaystyle \left\{{\begin{matrix}R_{1}^{(0)}&=&c_{1}-x_{1}^{(0)}+\sum \limits _{j=2}^{n}P_{1j}x_{j}^{(0)}\\R_{2}^{(0)}&=&c_{2}-x_{2}^{(0)}+\sum \limits _{j=1,j\neq 2}^{n}P_{2j}x_{j}^{(0)}\\&\ldots &\\R_{n}^{(0)}&=&c_{n}-x_{n}^{(0)}+\sum \limits _{j=1}^{n-1}P_{nj}x_{j}^{(0)}\\\end{matrix}}\right.}
  
Ընտրվում է սկզբնական 
  
    
      
        
          X
          
            (
            0
            )
          
        
        =
        0
      
    
    {\displaystyle X^{(0)}=0}
   մոտարկումը։ Յուրաքանչյուր քայլում անհրաժեշտ է առավելագույն կապը տանել զրոյի 
  
    
      
        
          R
          
            s
          
          
            (
            k
            )
          
        
        =
        δ
        
          x
          
            s
          
          
            (
            k
            )
          
        
        ⇒
        
          R
          
            s
          
          
            (
            k
            +
            1
            )
          
        
        =
        0
        ,
        
          R
          
            i
          
          
            (
            k
            +
            1
            )
          
        
        =
        
          R
          
            i
          
          
            (
            k
            )
          
        
        +
        
          P
          
            i
            s
          
        
        δ
        
          x
          
            s
          
          
            (
            k
            )
          
        
      
    
    {\displaystyle R_{s}^{(k)}=\delta x_{s}^{(k)}\Rightarrow R_{s}^{(k+1)}=0,R_{i}^{(k+1)}=R_{i}^{(k)}+P_{is}\delta x_{s}^{(k)}}
  ։
Դադարեցման պայմանը՝ 

  
    
      
        
          |
        
        
          R
          
            j
          
          
            (
            k
            )
          
        
        
          |
        
        <
        ε
        ,
        ∀
        j
        =
        
          
            
              1
              ,
              n
            
            ¯
          
        
      
    
    {\displaystyle |R_{j}^{(k)}|<\varepsilon ,\forall j={\overline {1,n}}}
  ։Պատասխանը գտնվում է այս բանաձևով՝

  
    
      
        
          x
          
            i
          
        
        ≈
        
          x
          
            i
          
          
            (
            0
            )
          
        
        +
        
          ∑
          
            j
          
        
        δ
        
          x
          
            i
          
          
            (
            j
            )
          
        
      
    
    {\displaystyle x_{i}\approx x_{i}^{(0)}+\sum _{j}\delta x_{i}^{(j)}}
  ։


== Օրինակ ==
Դիտարկենք գծային հավասարումների հետևյալ համակարգը՝

  
    
      
        
          
            
              
                4
                
                  x
                  
                    1
                  
                
                −
                
                  x
                  
                    2
                  
                
                −
                6
                
                  x
                  
                    3
                  
                
                +
                0
                
                  x
                  
                    4
                  
                
                =
                2
                ,
              
            
            
              
                −
                5
                
                  x
                  
                    1
                  
                
                −
                4
                
                  x
                  
                    2
                  
                
                +
                10
                
                  x
                  
                    3
                  
                
                +
                8
                
                  x
                  
                    4
                  
                
                =
                21
                ,
              
            
            
              
                0
                
                  x
                  
                    1
                  
                
                +
                9
                
                  x
                  
                    2
                  
                
                +
                4
                
                  x
                  
                    3
                  
                
                −
                2
                
                  x
                  
                    4
                  
                
                =
                −
                12
                ,
              
            
            
              
                1
                
                  x
                  
                    1
                  
                
                +
                0
                
                  x
                  
                    2
                  
                
                −
                7
                
                  x
                  
                    3
                  
                
                +
                5
                
                  x
                  
                    4
                  
                
                =
                −
                6.
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}4x_{1}-x_{2}-6x_{3}+0x_{4}=2,\\-5x_{1}-4x_{2}+10x_{3}+8x_{4}=21,\\0x_{1}+9x_{2}+4x_{3}-2x_{4}=-12,\\1x_{1}+0x_{2}-7x_{3}+5x_{4}=-6.\end{aligned}}}
  Հավասարումների համակարգը լուծելու համար որպես մոտարկման արժեք ընդոունենք՝ 
  
    
      
        ω
        =
        0.5
      
    
    {\displaystyle \omega =0.5}
   և նախնական մոտարկման վեկտոր՝ 
  
    
      
        ϕ
        =
        (
        0
        ,
        0
        ,
        0
        )
      
    
    {\displaystyle \phi =(0,0,0)}
  ։ Համաձայն ռելակսացիայի մեթոդի հաջորդական քայլերին անցման ստանում ենք հետևյալ աղյուսակը, որն իրենից ներկայացնում է մոտարկումների հաջորդականություն։ Այն իդեալականորեն, սակայն ոչ պարտադիր մոտենում է ճիշտ լուծմանը՝ (3, −2, 2, 1), 38 քայլերով։

Վերևում բերված հավասարումների համակարգի լուծումը ներկայացնենք Python ծրագրավորման լեզվով՝


== Հղումներ ==
Աբրահամ Բերման, Ռոբերտ Պլեմմոնս, «Ոչբացասական մատրիցները մաթեմատիկական գիտություններում»', 1994, SIAM. 0-89871-321-8.
Black, Noel and Moore, Shirley, "Successive Overrelaxation Method", MathWorld.
Netlib-ի պատճեի օրինակով «Գծային հավասարումների համակարգերի լուծման կաղապարներ», Բարեթ և այլն։


== Ծանոթագրություններ ==


== Արտաքին հղումներ ==
Module for the SOR Method