Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Метод Гаусса - Зейделя



План:


Введення

Метод Гаусса-Зейделя [1] є класичним ітераційним методом вирішення системи лінійних рівнянь.


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

І покажемо, як її можна вирішити з допомогою методу Гаусса-Зейделя.


2. Метод

Щоб пояснити суть методу, перепишемо задачу у вигляді:

\ 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 -М рівнянні ми перенесли в праву частину всі члени, що містять x i , Для i> j . Цей запис може бути представлена:

(\ Mathrm {L} + \ mathrm {D}) \ vec {x} = - \ mathrm {U} \, \ vec {x} + \ vec {b},

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

Ітераційний процес в методі Гаусса-Зейделя будується за формулою (\ Mathrm {L} + \ mathrm {D}) \ vec {x} ^ {(k +1)} = - \ mathrm {U} \ vec {x} ^ {(k)} + \ vec {b} , \ quad k = 0, 1, 2, \ ldots після вибору відповідного початкового наближення \ Vec {x} ^ {(0)} .

Метод Гаусса-Зейделя можна розглядати як модифікацію методу Якобі. Основна ідея модифікації полягає в тому, що нові значення \ Vec {x} ^ {(i)} використовуються тут відразу ж у міру отримання, в той час як у методі Якобі вони не використовуються, до наступної ітерації:

\ 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_ {ij} =- \ frac {a_ {ij}} {a_ {ii}}, \ quad d_i = \ frac {b_i} {a_ {ii}}, \ quad i = 1, \ ldots, n

Таким чином, i-та компонента (K + 1) -Го наближення обчислюється за формулою:

x_i ^ {(k +1)} = \ sum_ {j = 1} ^ {i-1} c_ {ij} x_ {j} ^ {(k +1)} + \ sum_ {j = i +1} ^ {n} c_ {ij} x_ {j} ^ {(k)} + d_i, \ quad i = 1, \ ldots, n

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

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

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

4. Умова закінчення

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

\ Parallel x ^ {(k +1)}-x ^ {(k)} \ parallel \ le \ varepsilon

Більш точне умова закінчення ітераційного процесу має вигляд

\ Parallel Ax ^ {(k)}-b \ parallel \ le \ varepsilon

і вимагає більше обчислень. Добре підходить для розріджених матриць.


5. Приклад алгоритму на с + +

 / / Умова збіжності  bool converge  (  double  *  xk  ,  double  *  xkp  )  {  for  (  int  i  =  0  ;  i  <  n  ;  i  + +  )  {  if  (  fabs  (  xk  [  i  ]  -  xkp  [  i  ]  )  > =  eps  )  return  false  ;  }  return  true  ;  }  / * Хід методу, де: a [n] [n] - Матриця коефіцієнтів x [n], p [n] - Поточне і попереднє рішення * /  do  {  for  (  int  i  =  0  ;  i  <  n  ;  i  + +  )  {  double  var  =  0  ;  for  (  int  j  =  0  ;  j  <  n  ;  j  + +  )  if  (  j  ! =  i  )  var  + =  (  a  [  i  ]  [  j  ]  *  x  [  j  ]  )  ;  p  [  i  ]  =  x  [  i  ]  ;  x  [  i  ]  =  (  b  [  i  ]  -  var  )  /  a  [  i  ]  [  i  ]  ;  }  }  while  (  !  converge  (  x  ,  p  )  )  ; 

6. Приклад алгоритму на pascal (для кв. Системи)

 type  ar2d  =  array  [  1  ..  50  ,  1  ..  50  ]  of  double; ar1d  =  array  [  1  ..  50  ]  of  double;  procedure  seidel  (  n  :  byte  ; E  :  extended; a  :  ar2d; b  :  ar1d; x  :  ar1d  )  ;  var  i  ,  j  :  longint  ; S  ,  v  ,  m  :  double;  begin  / / Перевірка на сумісність  for  i  : =  1  to  n  do  begin  s  : =  0  ;  for  j  : =  1  to  n  do  if  j <> i  then  s  : =  s  +  abs  (  a  [  i  ,  j  ]  )  ;  if  s>  =  abs  (  a  [  i  ,  i  ]  )  then  begin  writeln  (  'SLAE is incompatible'  )  ; Exit  end  ;  end  ;  / / Сам алгоритм  repeat  m  : =  0  ;  for  i  : =  1  to  n  do  begin  s  : =  0  ;  for  j  : =  1  to  n  do  if  i <> j  then  s  : =  s  +  a  [  i  ,  j  ]  *  x  [  j  ]  ; V  : =  x  [  i  ]  ; X  [  i  ]  : =  (  b  [  i  ]  -  s  )  /  a  [  i  ,  i  ]  ; M  : =  abs  (  x  [  i  ]  )  -  abs  (  v  )  ;  end  ;  until  m  / / Висновок коренів  writeln  (  'Roots:'  )  ;  for  i  : =  1  to  n  do  writeln  (  'X ['  ,  i  ,  '] ='  ,  x  [  i  ]  :  0  :  4  )  ;  end  ; 

Примітки

  1. Людвіг Зейдель ( 1821 - 1896) - німецький астроном і математик, Карл Фрідріх Гаусс ( 1777 - 1855) - німецький математик, астроном і фізик

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Метод Гаусса
Метод Гаусса - Жордана
Метод Гаусса (оптимізація)
Ряд Гаусса
Премія Гаусса
Гармата Гаусса
Дискримінант Гаусса
Постійна Гаусса
Кривизна Гаусса
© Усі права захищені
написати до нас
Рейтинг@Mail.ru