Յակոբիի մեթոդ

Յակոբիի մեթոդը գծային հանրահաշվում հավասարումների համակարգերի լուծման պարզ իտերացիայի տարատեսակներից է։ Այն անվանվել է ի պատիվ Կարլ Գուստավ Յակոբիի։


== Խնդրի դրվածքը ==
Վերցնենք գծային հավասարումների համակարգը.

  
    
      
        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}\\\ldots ~~~~~~~~~~~~~~~~~~~~~\\a_{n1}x_{1}+\ldots +a_{nn}x_{n}&=&b_{n}\end{array}}\right.}
  


== Մեթոդի նկարագրությունը ==
Որպեսզի կառուցենք Յակոբիի մեթոդի իտերատիվ ընթացակարգը, անհրաժեշտ է իրականացնել 
  
    
      
        A
        
          
            
              x
              →
            
          
        
        =
        
          
            
              b
              →
            
          
        
      
    
    {\displaystyle A{\vec {x}}={\vec {b}}}
   հավասարումների համակարգի նախնական ձևափոխում 
  
    
      
        
          
            
              x
              →
            
          
        
        =
        B
        
          
            
              x
              →
            
          
        
        +
        
          
            
              g
              →
            
          
        
      
    
    {\displaystyle {\vec {x}}=B{\vec {x}}+{\vec {g}}}
   իտերացիոն տեսքին։ Այն կարող է կատարվել հետևյալ կանոններից որևէ մեկի համաձայն՝

  
    
      
        B
        =
        E
        −
        
          D
          
            −
            1
          
        
        A
        =
        
          D
          
            −
            1
          
        
        (
        D
        −
        A
        )
        ,
        
        
          
            
              g
              →
            
          
        
        =
        
          D
          
            −
            1
          
        
        
          
            
              b
              →
            
          
        
        ;
      
    
    {\displaystyle B=E-D^{-1}A=D^{-1}(D-A),\quad {\vec {g}}=D^{-1}{\vec {b}};}
  

  
    
      
        B
        =
        −
        
          D
          
            −
            1
          
        
        (
        L
        +
        U
        )
        =
        −
        
          D
          
            −
            1
          
        
        (
        A
        −
        D
        )
        ,
        
        
          
            
              g
              →
            
          
        
        =
        
          D
          
            −
            1
          
        
        
          
            
              b
              →
            
          
        
      
    
    {\displaystyle B=-D^{-1}(L+U)=-D^{-1}(A-D),\quad {\vec {g}}=D^{-1}{\vec {b}}}
  

  
    
      
        
          D
          
            i
            i
          
          
            −
            1
          
        
        =
        1
        
          /
        
        
          D
          
            i
            i
          
        
        ,
        
          D
          
            i
            i
          
        
        ≠
        0
        ,
        
        i
        =
        1
        ,
        2
        ,
        .
        .
        .
        ,
        n
        
        ,
      
    
    {\displaystyle D_{ii}^{-1}=1/D_{ii},D_{ii}\neq 0,\,i=1,2,...,n\quad ,}
  որտեղ ըստ ընդունված նշանակումների 
  
    
      
        D
      
    
    {\displaystyle D}
  -ն մատրից է, որի գլխավոր անկյունագծի վրա գտնվում են 
  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցի համապատասխան էլեմենտները, իսկ մնացած բոլոր էլեմենտները զրոներ են, այնինչ 
  
    
      
        U
      
    
    {\displaystyle U}
   և 
  
    
      
        L
      
    
    {\displaystyle L}
   մատրիցները պարունակում են 
  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցի վերևի և ներքևի եռանկյունային մասերը, որոնց գլխավոր անկյունագծի վրա զրոներ են, իսկ 
  
    
      
        E
      
    
    {\displaystyle E}
  -ն միավոր մատրից է։
Այդ դեպքում լուծման գտնելու ընթացակարգը ունիայսպիսի տեսք՝

  
    
      
        
          
            
              
                x
                →
              
            
          
          
            (
            k
            +
            1
            )
          
        
        =
        B
        
          
            
              
                x
                →
              
            
          
          
            (
            k
            )
          
        
        +
        
          
            
              g
              →
            
          
        
        ,
      
    
    {\displaystyle {\vec {x}}^{(k+1)}=B{\vec {x}}^{(k)}+{\vec {g}},}
  կամ ըստ էլեմենտային բանաձևի տեսքով՝

  
    
      
        
          x
          
            i
          
          
            (
            k
            +
            1
            )
          
        
        =
        
          
            1
            
              a
              
                i
                i
              
            
          
        
        
          (
          
            
              b
              
                i
              
            
            −
            
              ∑
              
                j
                ≠
                i
              
            
            
              a
              
                i
                j
              
            
            
              x
              
                j
              
              
                (
                k
                )
              
            
          
          )
        
        ,
        
        i
        =
        1
        ,
        2
        ,
        …
        ,
        n
        ,
      
    
    {\displaystyle x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j\neq i}a_{ij}x_{j}^{(k)}\right),\quad i=1,2,\ldots ,n,}
  որտեղ 
  
    
      
        k
      
    
    {\displaystyle k}
  -ն իտերացիայի հաշվիչն է։
Ի տարբերություն Զեյդելի մեթոդի մենք չենք կարող փոխարինել 
  
    
      
        
          x
          
            i
          
          
            (
            k
            )
          
        
      
    
    {\displaystyle x_{i}^{(k)}}
  -ը 
  
    
      
        
          x
          
            i
          
          
            (
            k
            +
            1
            )
          
        
      
    
    {\displaystyle x_{i}^{(k+1)}}
  -ի իտերացիայի գործընթացի ընթացքում, քանի որ այդ արժեքները անհրաժեշտ են մյուս հաշվարկների համար։
Սա ամենաէական տարբերությունն է գծային հանրահաշվական հավասարումների համակարգի լուծման Յակոբիի և Գաուս-Զեյդել մեթոդների միջև։ Այսպիսով, յուրաքանչյուր իտերացիայի ժամանակ անհրաժեշտություն է առաջանում մոտարկումների երկու վեկտորները՝ հին և նոր, պահպանել։


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


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

  
    
      
        ∥
        
          x
          
            (
            k
            +
            1
            )
          
        
        −
        
          x
          
            (
            k
            )
          
        
        ∥≤
        
          
            
              1
              −
              q
            
            q
          
        
        ε
      
    
    {\displaystyle \parallel x^{(k+1)}-x^{(k)}\parallel \leq {\frac {1-q}{q}}\varepsilon }
  ։
  
    
      
        B
      
    
    {\displaystyle B}
   (երբ 
  
    
      
        ∥
        B
        ∥=
        q
        <
        1
        
          /
        
        2
      
    
    {\displaystyle \parallel B\parallel =q<1/2}
  ) մատրիցի համար առավել լավ այն կատարվում է, երբ

  
    
      
        ∥
        
          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 }
  և պահանջում է լրացուցիչ բազմապատկում մատրիցն վեկտորին յուրաքանչյուր իտերացիայում, որը մոտավորապես երկու անգամ մեծացնում է ալգորիթմի հաշվարկային բարդությունը։


== Ալգորիթմ ==
Ներքևում բերենք ալգորիթմի իրականացումը С++ -ում։


== Տես նաև ==
Գաուս-Զեյդելի մեթոդ


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