Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 12.02.2010, 20:24
Новичок

Отправить личное сообщение для d.dragon.n76 Посмотреть профиль Найти все сообщения от d.dragon.n76
 
Регистрация: 26.12.2008
Сообщений: 24

обратить матрицу
Порекомендуйте алгоритм обращения матрицы. Желательно ссылку с подробным описанием алгоритма или какую-нибуть стандартную команду на с++ (например, отсыда boost.org).
  #2  
Старый 13.02.2010, 00:12
гость

 
Сообщений: n/a

гаусс
  #3  
Старый 14.02.2010, 00:47
Новичок

Отправить личное сообщение для d.dragon.n76 Посмотреть профиль Найти все сообщения от d.dragon.n76
 
Регистрация: 26.12.2008
Сообщений: 24

Сообщение от гость Посмотреть сообщение
гаусс
идея понятна. Но возникли проблемы:
1. когда Гаусс применим
2. помогите найти ошибку(и) вкоде

Код:
#include <iostream>
#include <vector>
#include <iomanip>
#define debugInverseMatrix 1

void inverse_matrix(std::vector<std::vector<double> > & );

main(){
int n = 3;
std::vector<std::vector<double> > A(n,std::vector<double>(n));
A[0][0]=1.0;A[0][1]=2.0;A[0][2]=1.0;
A[1][0]=3.0;A[1][1]=1.0;A[1][2]=1.0;
A[2][0]=2.0;A[2][1]=3.0;A[2][2]=1.0;
inverse_matrix(A);
}


void inverse_matrix(std::vector<std::vector<double> > & A)
{
  int k,i,j;
  double koef;
  int n = A.size();

#if debugInverseMatrix
  std::cerr << "a.size()=" << n << std::endl;
#endif

  std::vector<std::vector<double> > a(n,std::vector<double>(n+n));
  for( i=0; i<n; ++i){
        for( j=0; j<n; ++j){
              a[i][j] = A[i][j];
        }// for_j
        for( j=n; j<n+n; ++j){
              if(i+n==j) a[i][j] = 1.0;
              else a[i][j] = 0.0;
        }
  } // for_i
  
#if debugInverseMatrix
std::cerr << "Begin matrix\n";
  for(int i=0; i<n; ++i, std::cerr<<std::endl)
       for(int j=0; j<n+n; ++j)
            std::cerr<< std::fixed << std::setprecision(6)<< std::setw(10) << a[i][j] << ' ' << std::flush;
#endif

  for( k=0; k<n; ++k ) {
      for( i=k+1; i<n; ++i){
           koef = -a[i][k]/a[k][k];
           for( j=k; j<n+n; ++j ){
                a[i][j] += koef*a[k][j];
           }// for_j
      }// for_i
  } // for_k



  for(int i=0; i<n; ++i){
       koef = a[i][i];
       for(int j=0; j<n+n; ++j){
           a[i][j] /= koef;
       }
  }
            

#if debugInverseMatrix
std::cerr << "Triang. matrix\n";
  for(int i=0; i<n; ++i, std::cerr<<std::endl)
       for(int j=0; j<n+n; ++j)
            std::cerr << std::fixed << std::setprecision(6) << std::setw(10) << a[i][j] << ' ' << std::flush;
#endif

 for(int k=n-1; k>0; --k)
   for(int i=k-1; i>=0; --i)
        for(int j=0; j<n+n; ++j)
            a[i][j] -= a[k][j]*a[i][k];

#if debugInverseMatrix
std::cerr << "Result matrix\n";
  for(int i=0; i<n; ++i, std::cerr<<std::endl)
       for(int j=0; j<n+n; ++j)
            std::cerr << std::fixed << std::setprecision(6) << std::setw(10) << a[i][j] << ' ' << std::flush;
#endif
}

a.size()=3
Begin matrix
1.000000 2.000000 1.000000 1.000000 0.000000 0.000000
3.000000 1.000000 1.000000 0.000000 1.000000 0.000000
2.000000 3.000000 1.000000 0.000000 0.000000 1.000000
Triang. matrix
1.000000 2.000000 1.000000 1.000000 0.000000 0.000000
-0.000000 1.000000 0.400000 0.600000 -0.200000 -0.000000
-0.000000 -0.000000 1.000000 2.333333 0.333333 -1.666667
Result matrix
1.000000 0.000000 0.000000 1.000000 0.000000 0.000000
0.000000 1.000000 0.000000 0.600000 -0.200000 0.000000
-0.000000 -0.000000 1.000000 2.333333 0.333333 -1.666667


octave выдает

octave:1> A=[1 2 1; 3 1 1; 2 3 1]
A =

1 2 1
3 1 1
2 3 1

octave:2> inv(A)
ans =

-0.66667 0.33333 0.33333
-0.33333 -0.33333 0.66667
2.33333 0.33333 -1.66667
  #4  
Старый 14.02.2010, 02:14
гость

 
Сообщений: n/a

зачем вам тут обратный ход? вы что, мазохист, получаете удовольствие от отладки программ?

оставляю это удовольствие вам. а серьезные люди сегодня, когда слышат "метод гаусса", с этим дурацким "обратным ходом", как написано во всяких там совковых учебниках по вычметодам, не заморачиваются. ну кому это нах*р надо - один и тот же алгоритм дважды писать??? время = деньги. может, в то время когда делали водородную бомбу и между делом писали эти учебники, машинное время и ценилось гораздо больше времени программиста, но сейчас 21 век, и все ровно наоборот.

короче - твой кусок "обратный ход метода гаусса" ф топку, баг у тебя скорее всего там.

основной кусок кода меняй так, чтоб он обрабатывал каждую строчку сразу и ниже, и выше текущей. т.е. так:

for( k=0; k<n; ++k ) {
for( i=0; i<n; ++i){
if (i == k) continue;
koef = -a[i][k]/a[k][k];
for( j=0; j<n+n; ++j ){
a[i][j] += koef*a[k][j];
}// for_j
}// for_i
} // for_k

(это иногда называется gauss-jordan, чтобы отличить от "гаусса с обратным ходом")

По хорошему, еще бы надо pivoting прикрутить, тогда всё ващще будет просто здорово.



> 1. когда Гаусс применим
с pivoting'ом (т.е. перестановкой строк) применим всегда.

без pivoting'а, если мне не изменяет память, 100% работает только для положительно-определённых/отрицательно-определенных
(и желательно, конечно, еще хорошо-обучловленных) матриц. иначе есть шанс нарваться на деление на ноль и прочую дрянь.
  #5  
Старый 22.04.2010, 19:25
гость

 
Сообщений: n/a

зыдесь http://drobotenko.com/code_rus.html
  #6  
Старый 14.06.2010, 02:31
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
зачем вам тут обратный ход? вы что, мазохист, получаете удовольствие от отладки программ?

оставляю это удовольствие вам. а серьезные люди сегодня, когда слышат "метод гаусса", с этим дурацким "обратным ходом", как написано во всяких там совковых учебниках по вычметодам,
В современных буржуйских тоже самое написано
  #7  
Старый 14.06.2010, 03:25
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
В современных буржуйских тоже самое написано
в буржуйских обычно рассказывают про LU-разложение. Это штука пополезнее гаусса с обратным ходом буде
  #8  
Старый 20.09.2010, 15:39
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
в буржуйских обычно рассказывают про LU-разложение. Это штука пополезнее гаусса с обратным ходом буде
Это очень древние исходники с которых пошла популярность LU http://netlib.org/cgi-bin/netlibfile...ouble/dgetri.f на текущий момент актуальность потеряли. Попробуйте в них разобраться если есть желание
  #9  
Старый 25.09.2010, 13:33
Новичок

Отправить личное сообщение для d.dragon.n76 Посмотреть профиль Найти все сообщения от d.dragon.n76
 
Регистрация: 26.12.2008
Сообщений: 24

Сообщение от гость Посмотреть сообщение
Это очень древние исходники с которых пошла популярность LU http://netlib.org/cgi-bin/netlibfile...ouble/dgetri.f на текущий момент актуальность потеряли. Попробуйте в них разобраться если есть желание

Спасибо!

ошибки отладил, а сейчас использую lu_factorize из пакета boost. Правда при тестировании на скорость особых различий между в методе с LU-разложением, и методе Гаусса не заметил.

P.S. Правда насчет критерия вопрос интересен . Без выбора главного элемента : LU - главные миноры отличны от нуля, простой Гаусс - диагональное преобладание ... наверно LU выгоднее.
  #10  
Старый 25.09.2010, 20:14
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>при тестировании на скорость особых различий между в методе с LU-разложением, и методе Гаусса не заметил.

А особых и нет. LU заметно выгоднее, если нужно решить несколько СЛАУ с одинаковой левой частью
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как свести такую рекурсию в матрицу MatrixForever Математические алгоритмы (другое) 4 25.07.2009 02:45
Вывод пути через матрицу последовательности узлов Алгоритм Флойда Cerberus Реализация, исходники, языки 1 18.11.2008 16:53
Заполнить матрицу случайными числами GroW Математические алгоритмы 6 16.02.2008 11:19