Գաուս-Զեյդելի մեթոդ

Գաուս-Զեյդելի մեթոդը (Զեյդելի մեթոդ, Լիբմանի պրոցես, հաջորդական փոխարինումների մեթոդ) հանդիսանում է դասական իտերացիոն մեթոդով հավասարումների համակարգի լուծում ։ Այն անվանվում է ի պատիվ Զեյդելի և Գաուսի։


== Խնդրի դրվածքը ==
Դիտարկենք հավասարումների համակարգը՝

  
    
      
        A
        
          
            
              x
              →
            
          
        
        =
        
          
            
              b
              →
            
          
        
      
    
    {\displaystyle A{\vec {x}}={\vec {b}}}
  , где 
  
    
      
        A
        =
        
          (
          
            
              
                
                  
                    a
                    
                      11
                    
                  
                
                
                  …
                
                
                  
                    a
                    
                      1
                      n
                    
                  
                
              
              
                
                  ⋮
                
                
                  ⋱
                
                
                  ⋮
                
              
              
                
                  
                    a
                    
                      n
                      1
                    
                  
                
                
                  …
                
                
                  
                    a
                    
                      n
                      n
                    
                  
                
              
            
          
          )
        
        ,
        
        
          
            
              b
              →
            
          
        
        =
        
          (
          
            
              
                
                  
                    b
                    
                      1
                    
                  
                
              
              
                
                  ⋮
                
              
              
                
                  
                    b
                    
                      n
                    
                  
                
              
            
          
          )
        
      
    
    {\displaystyle A=\left({\begin{array}{ccc}a_{11}&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}\end{array}}\right),\quad {\vec {b}}=\left({\begin{array}{c}b_{1}\\\vdots \\b_{n}\end{array}}\right)}
  
կամ

  
    
      
        
          {
          
            
              
                
                  
                    a
                    
                      11
                    
                  
                  
                    x
                    
                      1
                    
                  
                  +
                  …
                  +
                  
                    a
                    
                      1
                      n
                    
                  
                  
                    x
                    
                      n
                    
                  
                
                
                  =
                
                
                  
                    b
                    
                      1
                    
                  
                
              
              
                
                
                
              
              
                
                  
                    a
                    
                      n
                      1
                    
                  
                  
                    x
                    
                      1
                    
                  
                  +
                  …
                  +
                  
                    a
                    
                      n
                      n
                    
                  
                  
                    x
                    
                      n
                    
                  
                
                
                  =
                
                
                  
                    b
                    
                      n
                    
                  
                
              
            
          
          
        
      
    
    {\displaystyle \left\{{\begin{array}{rcl}a_{11}x_{1}+\ldots +a_{1n}x_{n}&=&b_{1}\\&&\\a_{n1}x_{1}+\ldots +a_{nn}x_{n}&=&b_{n}\end{array}}\right.}
  
և ցույց տանք, թե ինչպես կարելի է լուծել այն Գաուս-Զեյդելի մեթոդով։


== Մեթոդը ==
Մեթոդի էությունը պարզաբանելու համար առաջադրանքը գրենք հետևյալ տեսքով՝

  
    
      
        
          {
          
            
              
                
                  
                    a
                    
                      11
                    
                  
                  
                    x
                    
                      1
                    
                  
                
                
                  =
                
                
                  −
                  
                    a
                    
                      12
                    
                  
                  
                    x
                    
                      2
                    
                  
                  −
                  
                    a
                    
                      13
                    
                  
                  
                    x
                    
                      3
                    
                  
                  −
                  …
                  −
                  
                    a
                    
                      1
                      n
                    
                  
                  
                    x
                    
                      n
                    
                  
                  +
                  
                    b
                    
                      1
                    
                  
                
              
              
                
                  
                    a
                    
                      21
                    
                  
                  
                    x
                    
                      1
                    
                  
                  +
                  
                    a
                    
                      22
                    
                  
                  
                    x
                    
                      2
                    
                  
                
                
                  =
                
                
                  −
                  
                    a
                    
                      23
                    
                  
                  
                    x
                    
                      3
                    
                  
                  −
                  …
                  −
                  
                    a
                    
                      2
                      n
                    
                  
                  
                    x
                    
                      n
                    
                  
                  +
                  
                    b
                    
                      2
                    
                  
                
              
              
                
                  …
                
                
                
              
              
                
                  
                    a
                    
                      (
                      n
                      −
                      1
                      )
                      1
                    
                  
                  
                    x
                    
                      1
                    
                  
                  +
                  
                    a
                    
                      (
                      n
                      −
                      1
                      )
                      2
                    
                  
                  
                    x
                    
                      2
                    
                  
                  +
                  …
                  +
                  
                    a
                    
                      (
                      n
                      −
                      1
                      )
                      (
                      n
                      −
                      1
                      )
                    
                  
                  
                    x
                    
                      n
                      −
                      1
                    
                  
                
                
                  =
                
                
                  −
                  
                    a
                    
                      (
                      n
                      −
                      1
                      )
                      n
                    
                  
                  
                    x
                    
                      n
                    
                  
                  +
                  
                    b
                    
                      n
                      −
                      1
                    
                  
                
              
              
                
                  
                    a
                    
                      n
                      1
                    
                  
                  
                    x
                    
                      1
                    
                  
                  +
                  
                    a
                    
                      n
                      2
                    
                  
                  
                    x
                    
                      2
                    
                  
                  +
                  …
                  +
                  
                    a
                    
                      n
                      (
                      n
                      −
                      1
                      )
                    
                  
                  
                    x
                    
                      n
                      −
                      1
                    
                  
                  +
                  
                    a
                    
                      n
                      n
                    
                  
                  
                    x
                    
                      n
                    
                  
                
                
                  =
                
                
                  
                    b
                    
                      n
                    
                  
                
              
            
          
          
        
      
    
    {\displaystyle \left\{{\begin{array}{lcr}a_{11}x_{1}&=&-a_{12}x_{2}-a_{13}x_{3}-\ldots -a_{1n}x_{n}+b_{1}\\a_{21}x_{1}+a_{22}x_{2}&=&-a_{23}x_{3}-\ldots -a_{2n}x_{n}+b_{2}\\\ldots &&\\a_{(n-1)1}x_{1}+a_{(n-1)2}x_{2}+\ldots +a_{(n-1)(n-1)}x_{n-1}&=&-a_{(n-1)n}x_{n}+b_{n-1}\\a_{n1}x_{1}+a_{n2}x_{2}+\ldots +a_{n(n-1)}x_{n-1}+a_{nn}x_{n}&=&b_{n}\end{array}}\right.}
  Այստեղ 
  
    
      
        j
      
    
    {\displaystyle j}
  -րդ հավասարումում մենք աջ մաս տեղափոխեցինք բոլոր այն 
  
    
      
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{i}}
   անդամները, որտեղ բավարարում էր 
  
    
      
        i
        >
        j
      
    
    {\displaystyle i>j}
   պայմանը։ Այս գրառումը կարող է ներկայացվել հետևյալ ձևով՝

  
    
      
        (
        
          L
        
        +
        
          D
        
        )
        
          
            
              x
              →
            
          
        
        =
        −
        
          U
        
        
        
          
            
              x
              →
            
          
        
        +
        
          
            
              b
              →
            
          
        
        ,
      
    
    {\displaystyle (\mathrm {L} +\mathrm {D} ){\vec {x}}=-\mathrm {U} \,{\vec {x}}+{\vec {b}},}
  որտեղ ընդունված նշանակումներով 
  
    
      
        
          D
        
      
    
    {\displaystyle \mathrm {D} }
  -ն մատրից է, որում գլխավոր անկյունագծի վրա գրված են  
  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցի համապատասխան անդամները, իսկ մնացած անդամները զրոներ են, այնինչ 
  
    
      
        
          U
        
      
    
    {\displaystyle \mathrm {U} }
   և 
  
    
      
        
          L
        
      
    
    {\displaystyle \mathrm {L} }
   մատրիցները պարունակում են 
  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցի վերևի և ներքևի եռանկյունային մասերը, որոնց գլխավոր անկյունագծի վրա զրոներ են։
Գաուս-Զեյդելի մեթոդում իտերացիոն պրոցեսը ստեղծվում է հետևյալ բանաձևով՝

  
    
      
        (
        
          L
        
        +
        
          D
        
        )
        
          
            
              
                x
                →
              
            
          
          
            (
            k
            +
            1
            )
          
        
        =
        −
        
          U
        
        
          
            
              
                x
                →
              
            
          
          
            (
            k
            )
          
        
        +
        
          
            
              b
              →
            
          
        
        ,
        
        k
        =
        0
        ,
        1
        ,
        2
        ,
        …
      
    
    {\displaystyle (\mathrm {L} +\mathrm {D} ){\vec {x}}^{(k+1)}=-\mathrm {U} {\vec {x}}^{(k)}+{\vec {b}},\quad k=0,1,2,\ldots }
  համապատասխան 
  
    
      
        
          
            
              
                x
                →
              
            
          
          
            (
            0
            )
          
        
      
    
    {\displaystyle {\vec {x}}^{(0)}}
   սկզբնական մոտարկման ընտրությամբ։
Գաուս-Զեյդելի մեթոդը կարելի է դիտարկել որպես Յակոբիի մեթոդի մոդիֆիկացիա։ Մոդիֆիկացիայի հիմնական գաղափարը կայանում է նրանում, որ այստեղ 
  
    
      
        
          
            
              
                x
                →
              
            
          
          
            (
            i
            )
          
        
      
    
    {\displaystyle {\vec {x}}^{(i)}}
   նոր արժեքները օգտագործվում են անմիջապես ստանալուց հետո, այնինչ Յակոբիի մեթոդում այն չի օգտագործվում մինչև հաջորդ իտերացիան՝

  
    
      
        
          {
          
            
              
                
                  
                    
                      
                        x
                        
                          1
                        
                      
                    
                    
                      (
                      k
                      +
                      1
                      )
                    
                  
                
                
                  =
                
                
                  
                    c
                    
                      12
                    
                  
                  
                    
                      x
                      
                        2
                      
                      
                        (
                        k
                        )
                      
                    
                  
                
                
                  +
                
                
                  
                    c
                    
                      13
                    
                  
                  
                    x
                    
                      3
                    
                    
                      (
                      k
                      )
                    
                  
                
                
                  +
                
                
                  
                    …
                  
                
                
                  +
                
                
                  
                    c
                    
                      1
                      n
                    
                  
                  
                    
                      
                        x
                        
                          n
                        
                      
                    
                    
                      (
                      k
                      )
                    
                  
                
                
                  +
                
                
                  
                    d
                    
                      1
                    
                  
                
              
              
                
                  
                    
                      
                        x
                        
                          2
                        
                      
                    
                    
                      (
                      k
                      +
                      1
                      )
                    
                  
                
                
                  =
                
                
                  
                    c
                    
                      21
                    
                  
                  
                    
                      x
                      
                        1
                      
                      
                        (
                        k
                        +
                        1
                        )
                      
                    
                  
                
                
                  +
                
                
                  
                    c
                    
                      23
                    
                  
                  
                    x
                    
                      3
                    
                    
                      (
                      k
                      )
                    
                  
                
                
                  +
                
                
                  
                    …
                  
                
                
                  +
                
                
                  
                    c
                    
                      2
                      n
                    
                  
                  
                    
                      
                        x
                        
                          n
                        
                      
                    
                    
                      (
                      k
                      )
                    
                  
                
                
                  +
                
                
                  
                    d
                    
                      2
                    
                  
                
              
              
                
                  …
                
                
                
                
                
                
                
                
                
                
                
              
              
                
                  
                    
                      
                        x
                        
                          n
                        
                      
                    
                    
                      (
                      k
                      +
                      1
                      )
                    
                  
                
                
                  =
                
                
                  
                    c
                    
                      n
                      1
                    
                  
                  
                    
                      x
                      
                        1
                      
                      
                        (
                        k
                        +
                        1
                        )
                      
                    
                  
                
                
                  +
                
                
                  
                    c
                    
                      n
                      2
                    
                  
                  
                    
                      x
                      
                        2
                      
                      
                        (
                        k
                        +
                        1
                        )
                      
                    
                  
                
                
                  +
                
                
                  
                    …
                  
                
                
                  +
                
                
                  
                    c
                    
                      n
                      (
                      n
                      −
                      1
                      )
                    
                  
                  
                    
                      
                        x
                        
                          n
                          −
                          1
                        
                      
                    
                    
                      (
                      k
                      +
                      1
                      )
                    
                  
                
                
                  +
                
                
                  
                    d
                    
                      n
                    
                  
                
              
            
          
          
        
        ,
      
    
    {\displaystyle \left\{{\begin{array}{ccccccccccc}{x_{1}}^{(k+1)}&=&c_{12}{x_{2}^{(k)}}&+&c_{13}x_{3}^{(k)}&+&{\ldots }&+&c_{1n}{x_{n}}^{(k)}&+&d_{1}\\{x_{2}}^{(k+1)}&=&c_{21}{x_{1}^{(k+1)}}&+&c_{23}x_{3}^{(k)}&+&{\ldots }&+&c_{2n}{x_{n}}^{(k)}&+&d_{2}\\\ldots &&&&&&&&&&\\{x_{n}}^{(k+1)}&=&c_{n1}{x_{1}^{(k+1)}}&+&c_{n2}{x_{2}^{(k+1)}}&+&{\ldots }&+&c_{n(n-1)}{x_{n-1}}^{(k+1)}&+&d_{n}\end{array}}\right.,}
  որտեղ

  
    
      
        
          c
          
            i
            j
          
        
        =
        
          
            {
            
              
                
                  −
                  
                    
                      
                        a
                        
                          i
                          j
                        
                      
                      
                        a
                        
                          i
                          i
                        
                      
                    
                  
                  ,
                
                
                  j
                  ≠
                  i
                  ,
                
              
              
                
                  0
                  ,
                
                
                  j
                  =
                  i
                  .
                
              
            
            
          
        
        
        
          d
          
            i
          
        
        =
        
          
            
              b
              
                i
              
            
            
              a
              
                i
                i
              
            
          
        
        ,
        
        i
        =
        1
        ,
        …
        ,
        n
        .
      
    
    {\displaystyle c_{ij}={\begin{cases}-{\frac {a_{ij}}{a_{ii}}},&j\neq i,\\0,&j=i.\end{cases}}\quad d_{i}={\frac {b_{i}}{a_{ii}}},\quad i=1,\ldots ,n.}
  Այսպիսով, 
  
    
      
        i
      
    
    {\displaystyle i}
  -րդ կոմպոնենտի 
  
    
      
        (
        k
        +
        1
        )
      
    
    {\displaystyle (k+1)}
  -րդ մոտարկման հաշվարկը կատարվում է 

  
    
      
        
          x
          
            i
          
          
            (
            k
            +
            1
            )
          
        
        =
        
          ∑
          
            j
            =
            1
          
          
            i
            −
            1
          
        
        
          c
          
            i
            j
          
        
        
          x
          
            j
          
          
            (
            k
            +
            1
            )
          
        
        +
        
          ∑
          
            j
            =
            i
          
          
            n
          
        
        
          c
          
            i
            j
          
        
        
          x
          
            j
          
          
            (
            k
            )
          
        
        +
        
          d
          
            i
          
        
        ,
        
        i
        =
        1
        ,
        …
        ,
        n
      
    
    {\displaystyle x_{i}^{(k+1)}=\sum _{j=1}^{i-1}c_{ij}x_{j}^{(k+1)}+\sum _{j=i}^{n}c_{ij}x_{j}^{(k)}+d_{i},\quad i=1,\ldots ,n}
  բանաձևով։
Օրինակ, 
  
    
      
        n
        =
        3
      
    
    {\displaystyle n=3}
  -ի դեպքում`

  
    
      
        
          x
          
            1
          
          
            (
            k
            +
            1
            )
          
        
        =
        
          ∑
          
            j
            =
            1
          
          
            1
            −
            1
          
        
        
          c
          
            1
            j
          
        
        
          x
          
            j
          
          
            (
            k
            +
            1
            )
          
        
        +
        
          ∑
          
            j
            =
            1
          
          
            3
          
        
        
          c
          
            1
            j
          
        
        
          x
          
            j
          
          
            (
            k
            )
          
        
        +
        
          d
          
            1
          
        
      
    
    {\displaystyle x_{1}^{(k+1)}=\sum _{j=1}^{1-1}c_{1j}x_{j}^{(k+1)}+\sum _{j=1}^{3}c_{1j}x_{j}^{(k)}+d_{1}}
  , այսինքն 
  
    
      
        
          x
          
            1
          
          
            (
            k
            +
            1
            )
          
        
        =
        
          c
          
            11
          
        
        
          x
          
            1
          
          
            (
            k
            )
          
        
        +
        
          c
          
            12
          
        
        
          x
          
            2
          
          
            (
            k
            )
          
        
        +
        
          c
          
            13
          
        
        
          x
          
            3
          
          
            (
            k
            )
          
        
        +
        
          d
          
            1
          
        
        ,
      
    
    {\displaystyle x_{1}^{(k+1)}=c_{11}x_{1}^{(k)}+c_{12}x_{2}^{(k)}+c_{13}x_{3}^{(k)}+d_{1},}
  

  
    
      
        
          x
          
            2
          
          
            (
            k
            +
            1
            )
          
        
        =
        
          ∑
          
            j
            =
            1
          
          
            2
            −
            1
          
        
        
          c
          
            2
            j
          
        
        
          x
          
            j
          
          
            (
            k
            +
            1
            )
          
        
        +
        
          ∑
          
            j
            =
            2
          
          
            3
          
        
        
          c
          
            2
            j
          
        
        
          x
          
            j
          
          
            (
            k
            )
          
        
        +
        
          d
          
            2
          
        
      
    
    {\displaystyle x_{2}^{(k+1)}=\sum _{j=1}^{2-1}c_{2j}x_{j}^{(k+1)}+\sum _{j=2}^{3}c_{2j}x_{j}^{(k)}+d_{2}}
  , այսինքն 
  
    
      
        
          x
          
            2
          
          
            (
            k
            +
            1
            )
          
        
        =
        
          c
          
            21
          
        
        
          x
          
            1
          
          
            (
            k
            +
            1
            )
          
        
        +
        
          c
          
            22
          
        
        
          x
          
            2
          
          
            (
            k
            )
          
        
        +
        
          c
          
            23
          
        
        
          x
          
            3
          
          
            (
            k
            )
          
        
        +
        
          d
          
            2
          
        
        ,
      
    
    {\displaystyle x_{2}^{(k+1)}=c_{21}x_{1}^{(k+1)}+c_{22}x_{2}^{(k)}+c_{23}x_{3}^{(k)}+d_{2},}
  

  
    
      
        
          x
          
            3
          
          
            (
            k
            +
            1
            )
          
        
        =
        
          ∑
          
            j
            =
            1
          
          
            3
            −
            1
          
        
        
          c
          
            3
            j
          
        
        
          x
          
            j
          
          
            (
            k
            +
            1
            )
          
        
        +
        
          ∑
          
            j
            =
            3
          
          
            3
          
        
        
          c
          
            3
            j
          
        
        
          x
          
            j
          
          
            (
            k
            )
          
        
        +
        
          d
          
            3
          
        
      
    
    {\displaystyle x_{3}^{(k+1)}=\sum _{j=1}^{3-1}c_{3j}x_{j}^{(k+1)}+\sum _{j=3}^{3}c_{3j}x_{j}^{(k)}+d_{3}}
  , այսինքն 
  
    
      
        
          x
          
            3
          
          
            (
            k
            +
            1
            )
          
        
        =
        
          c
          
            31
          
        
        
          x
          
            1
          
          
            (
            k
            +
            1
            )
          
        
        +
        
          c
          
            32
          
        
        
          x
          
            2
          
          
            (
            k
            +
            1
            )
          
        
        +
        
          c
          
            33
          
        
        
          x
          
            3
          
          
            (
            k
            )
          
        
        +
        
          d
          
            3
          
        
        :
      
    
    {\displaystyle x_{3}^{(k+1)}=c_{31}x_{1}^{(k+1)}+c_{32}x_{2}^{(k+1)}+c_{33}x_{3}^{(k)}+d_{3}:}
  


== Զուգամիտության պայման ==
Բերենք զուգամիտության մեթոդի բավարար պայման։


== Դադարեցման պայմանը ==
Զեյդելի պրոցեսի իտերացիայի ավարտի պայմանը անհրաժեշտ 
  
    
      
        ε
      
    
    {\displaystyle \varepsilon }
    ճշգրտության դեպքում կրճատ ձևով ունի այսպիսի տեսք՝

  
    
      
        ∥
        
          x
          
            (
            k
            +
            1
            )
          
        
        −
        
          x
          
            (
            k
            )
          
        
        ∥≤
        ε
      
    
    {\displaystyle \parallel x^{(k+1)}-x^{(k)}\parallel \leq \varepsilon }
  Իտերացիոն պրոցեսի առավել ճշգրիտ պայմանը ունի այսպիսի տեսք՝

  
    
      
        ∥
        A
        
          x
          
            (
            k
            )
          
        
        −
        b
        ∥≤
        ε
      
    
    {\displaystyle \parallel Ax^{(k)}-b\parallel \leq \varepsilon }
  և պահանջում է ավելի շատ հաշվարկներ։ Այն բավականին հարմար է կտրտված մատրիցների համար։


== Իրականացման օրինակ C++ - ում ==


== Իրականացման օրինակ Python - ում ==


== Տես նաև ==
Երկրաչափական պրոգրեսիա
Պարզ իտերացիայի մեթոդ
Յակոբիի մեթոդ
Բանախի թեորեմ
Իտերացիայի մեթոդ


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


== Արտաքին հղումներ ==
https://www.maa.org/press/periodicals/loci/joma/iterative-methods-for-solving-iaxi-ibi-gauss-seidel-method
https://www3.nd.edu/~zxu2/acms40390F12/Lec-7.3.pdf
http://mathworld.wolfram.com/Gauss-SeidelMethod.html