Метод Якобі - метод простої ітерації для розв'язання системи лінійних алгебраїчних рівнянь.


1. Постановка завдання

Візьмемо систему лінійних рівнянь:

A \ vec {x} = \ vec {b} , Де 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)

Або \ 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.

2. Опис методу

Для того, щоб побудувати ітеративну процедуру методу Якобі, необхідно провести попереднє перетворення системи рівнянь A \ vec {x} = \ vec {b} до ітераційного увазі \ Vec {x} = B \ vec {x} + \ vec {g} . Воно може бути здійснено по одному з наступних правил:

  • B = ED ^ {-1} A = D ^ {-1} (D - A), \ quad \ vec {g} = D ^ {-1} \ vec {b};
  • B =-D ^ {-1} (L + U) =-D ^ {-1} (A - D), \ quad \ vec {g} = D ^ {-1} \ vec {b}
  • D ^ {-1} _ {ii} = 1 / D_ {ii}, D_ {ii} \ neq 0, \, i = 1,2, ..., n \ quad;


де в прийнятих позначеннях D означає матрицю, у якої на головній діагоналі стоять відповідні елементи матриці A, а всі інші нулі; тоді як матриці U і L містять верхню і нижню трикутні частини A, на головній діагоналі яких нулі, E - одинична матриця.

Тоді процедура знаходження рішення має вигляд:

\ Vec {x} ^ {(k +1)} = B \ vec {x} ^ {(k)} + \ vec {g},

Або у вигляді поелементної формули:

x ^ {(k +1)} _i = \ frac {1} {a_ {ii}} \ left (b_i - \ sum_ {j \ ne i} a_ {ij} x ^ {(k)} _j \ right) , \ quad i = 1,2, \ ldots, n.

де k лічильник ітерації.

На відміну від методу Гауса-Зейделя ми не можемо замінювати x ^ {(k)} _i \, на x ^ {(k +1)} _i в процесі ітераційної процедури, тому ці значення знадобляться для інших обчислень. Це найбільш значуща відмінність між методом Якобі і методом Гауса-Зейделя рішення СЛАР. Таким чином на кожній ітерації доведеться зберігати обидва вектори наближень: старий і новий.


3. Умова збіжності

Наведемо достатня умова збіжності методу.

Logo arte.jpg Теорема.
Нехай \ | B \ | <1 \! . Тоді при будь-якому виборі початкового наближення \ Vec {x} ^ {(0)} \! :
  1. метод сходиться;
  2. швидкість збіжності методу дорівнює швидкості збіжності геометричній прогресії зі знаменником q = \ | B \ | \! ;
  3. вірна оцінка похибки: \ | \ Vec {x} ^ {(k)} - \ vec {x} \ | <q ^ k \, \ | \ vec {x} ^ {(0)} - \ vec {x} \ | \! .

4. Умова зупинки

Умова закінчення ітераційного процесу при досягненні точності \ Varepsilon в спрощеній формі має вигляд:

max_j \ | x_j ^ {(k +1)}-x_j ^ {(k)} \ | / (1-q) <\ varepsilon \!

(Існує більш точне умова закінчення ітераційного процесу, яке більш складно і вимагає додаткових обчислень)


5. Алгоритм

Нижче наведено алгоритм реалізації на C + +

 # Include   const  double  eps  =  0.001  ;  / / / <Бажана точність  ..........................  / / / N - розмірність матриці; A [N] [N] - матриця коефіцієнтів, F [N] - стовпець вільних членів,  / / / X [N] - початкове наближення, відповідь записується також у X [N];  void  Jacobi  (  int  N,  double  **  A,  double  *  F,  double  *  X  )  {  double  *  TempX  =  new  double  [  N  ]  ;  double  norm  ;  / / Норма, обумовлена ​​як найбільша різницю компонент стовпця іксів сусідніх ітерацій.  do  {  for  (  int  i  =  0  ;  i  <  N  ;  i  + +  )  {  TempX  [  i  ]  =  -  F  [  i  ]  ;  for  (  int  g  =  0  ;  g  <  N  ;  g  + +  )  {  if  (  i  !  =  g  )  TempX  [  i  ]  +  =  A  [  i  ]  [  g  ]  *  X  [  g  ]  ;  }  TempX  [  i  ]  /  =  -  A  [  i  ]  [  i  ]  ;  }  norm  =  fabs  (  X  [  0  ]  -  TempX  [  0  ]  )  ;  for  (  int  h  =  0  ;  h  <  N  ;  h  + +  )  {  if  (  fabs  (  X  [  h  ]  -  TempX  [  h  ]  )  >  norm  )  norm  =  fabs  (  X  [  h  ]  -  TempX  [  h  ]  )  ;  X  [  h  ]  =  TempX  [  h  ]  ;  }  }  while  (  norm  >  eps  )  ;  delete  [  ]  TempX  ;  }