Форум программистов, компьютерный форум CyberForum.ru

Решить систему алгебраических линейных неоднородных уравнени - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 70, средняя оценка - 4.66
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
22.07.2011, 15:58     Решить систему алгебраических линейных неоднородных уравнени #1
У меня есть система линейных уравнений. В ней 4000 уравнений.
Киньте плиз код для её решения. Желательно, чтобы он был максимально быстрым.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
Заблокирован
Автор FAQ
02.08.2011, 17:20     Решить систему алгебраических линейных неоднородных уравнени #41
Цитата Сообщение от hello19 Посмотреть сообщение
По этому надо, чтобы и порядок матрицы коэффициентов тоже уменьшился...
если a[i][i] == 0 вычёркивать буду i-e. строку и i-й столбец а также i-й элемент в В, я так и собираюсь сжимать А
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
02.08.2011, 17:30  [ТС]     Решить систему алгебраических линейных неоднородных уравнени #42
да да, это я и имел ввиду.. сейчас постараюсь переписать код, который вот из такого вида (1;2)(2;3)..
делает нормальную матрицу, но уже с удаленным "плохим" столбцом и "плохой" строчкой.
-=ЮрА=-
Заблокирован
Автор FAQ
02.08.2011, 17:32     Решить систему алгебраических линейных неоднородных уравнени #43
Ещё обрати внимание что индексы в твоей матрице А начинаются с единицы, самаже матрица имеет индексирование с нуля!
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
02.08.2011, 17:41  [ТС]     Решить систему алгебраических линейных неоднородных уравнени #44
Я это учел в том коде...
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
04.08.2011, 11:58  [ТС]     Решить систему алгебраических линейных неоднородных уравнени #45
Что-то у меня небольшой косяк с кодом, который удаляет строку\столбец
-=ЮрА=-
Заблокирован
Автор FAQ
04.08.2011, 12:15     Решить систему алгебраических линейных неоднородных уравнени #46
Устал искать баг
Я пробовал функции которые предлагали там - они кривые
Вот ковыряюсь в коде, введи число строк 4 или 5 и посмотри что почти довёл алгоритм до готовности. Работу над твоей СЛАУ я не окончил
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <windows.h>
#include <stdio.h>
#include <conio.h>
 
int ** a = (int **)malloc(sizeof(int));
int * b = (int *)malloc(sizeof(int));
 
void out_massiv(int n, int *mass);
int compress(int m, int **a, int *b);
int * compress(int m, int i, int * vec);
 
void main()
{
    srand(0);
    int n,m,i,j,k;
    do
    {
        printf("Enter num of rows in massiv: ");
        scanf("%d",&m);
        a = (int **)realloc((void *)a,m*sizeof(int));
        b = (int *)realloc((void *)b,m*sizeof(int));
        printf("\tMatrix A\r\n");
        for(i = 0,k = 0; i < m; i++)
        {
            b[i] = /*rand()*/i;
            a[i] = (int *)malloc(m*sizeof(int));
            for(j = 0; j < m; j++)
            {
/*              a[i][j] = rand();
                while(1000 < a[i][j])
                    a[i][j] = rand();*/
                a[i][j] = k++;
            }
            if(i % 2 == 0)
                a[i][i] = 0;
            out_massiv(m, a[i]);
        }
        printf("\tVector B\r\n");
        out_massiv(m, b);
        printf("Compressing\r\n");
        printf("Moved %d rows\r\n",n = compress(m, a, b));
        m -= n;
        printf("\tMatrix A\r\n");
        for(i = 0; i < m; i++)
            out_massiv(m, a[i]);
        printf("\tVector B\r\n");
        out_massiv(m, b);
        printf("[Y/N] Y - enter new input data\r\n");scanf("%d",m);
    }
    while(toupper(getch()) == 'Y');
}
 
void out_massiv(int n, int *mass)
{
    for(int i = 0;i < n; i++)
        printf("%02d ",mass[i]);
    printf("\r\n");
}
 
int compress(int m, int **a, int *b)
{
    int n = 0;
    for(int i = m - 1,j; 0 <= i; i--)
    {
        if(a[i][i] == 0)
        {
            printf("TEMP A\r\n");
            for(j = 0; j < m; j++)
            {
                a[j] = compress(m, i, a[j]);
                out_massiv(m - 1, a[j]);
            }
            for(j = i; j < m; j++)
                memmove((void *)&a[j],(void *)&a[j + 1],m);
            b = compress(m, i, b);
            printf("TEMP B\r\n");
            out_massiv(m, b);
            n++;
            m = m - n;
        }
    }
    return n;
}
 
int * compress(int m, int i, int * vec)
{
    memmove((void *)&vec[i],(void *)&vec[i + 1],m - (i + 1));
    return vec;
}
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
04.08.2011, 12:28  [ТС]     Решить систему алгебраических линейных неоднородных уравнени #47
))) как код то на мой вчерашний похож))) Вчера, к сожаления мало что написал, приболел.. но вот сегодня неплохо так устроил мозговой штурм
слушай, я тут подумал.. вот если встречаем нулевую строку\столбец.. может просто стоит удалить все целиком из массива?
Вот что сегодня напоял:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int main()
{
    int range = 5;
 
    // Allocate 2 matrix
    double **matrix = new double*[range]();
    for (int i = 0; i < range; i++) 
    {
        matrix[i] = new double[range]();
    }
 
    // reading from file
    ifstream ifs("aa.txt");
    double q;
    int i = 0;
    int j = 0;
    while ( ifs >> q )
    {
        matrix[i][j] = q;
        j++;
        if ( j % range == 0 ) { i++; j = 0;}
    }
    ifs.close();
    // delete nessesary colums and rows
 
    // счетчик количества нулевых строк/столбцов
    int k = 0;
    ofstream inf("inf.txt");
 
    // Тут я просто хочу удалить из массива нулевую строчку\столбец.
    for ( int i = 0; i < range; i++ )
    {
        if ( matrix[i][i] == 0 )
        {
            inf << i << endl;
            k++;
            delete matrix[i];
        }
    }
    inf.close();
 
    // output matrix 
    ofstream ofs("bb.txt");
    for (int i = 0; i < range-k; i ++)
    {
        for (int j = 0; j < range-k; j++)
        {
            ofs << matrix[i][j] << " ";
        } ofs << endl;
    }
    for ( int i =0; i < range-k; i++)
    delete[] matrix[i];
    delete[] matrix;
Вообще изначально я тоже хотел просто все передвинуть.. но ведь это может занять время немало.
Может лучше сразу удалять этот "перекресток" из массива...
-=ЮрА=-
Заблокирован
Автор FAQ
04.08.2011, 12:57     Решить систему алгебраических линейных неоднородных уравнени #48
Хорошо я учту твои соображения, нужно время...
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
04.08.2011, 13:49  [ТС]     Решить систему алгебраических линейных неоднородных уравнени #49
Просто у меня пока что не рабочий код мальца... ковыряюсь в нем

Добавлено через 46 минут
Можно например просто удалить вот так delete[] matrix[i]. Это строку/столбец не удалит - только освободит память, где она лежала. Но все указатели (и место в массиве под нее) останется.
а при выводе можно делать так:
C++
1
2
3
4
5
6
7
8
9
10
        for (int i = 0; i < range-k; i ++)
        {
                if ( matrix[i][i]!=NULL)
                {
                        for (int j = 0; j < range-k; j++)
                        {
                                ofs << matrix[i][j] << " ";
                        } ofs << endl;
                }
        }
Т.е. мы просто не выводим пустые строчки....
Вроде неплохая идея(это намного производительней, чем сдвигать строчки\столбцы), а вот реализация хромает.. падает прога
-=ЮрА=-
Заблокирован
Автор FAQ
04.08.2011, 13:59     Решить систему алгебраических линейных неоднородных уравнени #50
Цитата Сообщение от hello19 Посмотреть сообщение
Но все указатели (и место в массиве под нее) останется.
поэтому я и использую memmove
Цитата Сообщение от hello19 Посмотреть сообщение
Т.е. мы просто не выводим пустые строчки....
Это идея, можно переадть в функцию решения СЛАУ индексы нулевых элементов и алгоритм просто не будет их принимать при вычислениях, наверное лучше так, потому что двигать в памяти матрицу размером 105 Мб весьма проблематично
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
04.08.2011, 14:06  [ТС]     Решить систему алгебраических линейных неоднородных уравнени #51
Прогресс)
Сейчас код подниму на ноги...
-=ЮрА=-
Заблокирован
Автор FAQ
04.08.2011, 14:13     Решить систему алгебраических линейных неоднородных уравнени #52
У меня тоже прилив сил, уже набиваю оптимизированный метод Гаусса
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
04.08.2011, 14:16  [ТС]     Решить систему алгебраических линейных неоднородных уравнени #53
На самом деле просто перекусил)
-=ЮрА=-
Заблокирован
Автор FAQ
04.08.2011, 15:04     Решить систему алгебраических линейных неоднородных уравнени #54
Вобщем этот код прогрыз СЛАУ за 25 мин, на тормознутой машшине. Вконце я уж было отчаялся и подумал что алгоритм ничего не решал, ноооо в векторе Х есть корни - например один вокнце точно сразу можно увидеть
Миниатюры
Решить систему алгебраических линейных неоднородных уравнени  
Вложения
Тип файла: rar SLAU_cpp.rar (1.7 Кб, 17 просмотров)
Тип файла: rar X.rar (212 байт, 16 просмотров)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.08.2011, 15:11     Решить систему алгебраических линейных неоднородных уравнени #55
Тоже заинтересовался этой темой..
Моя реализация алгоритма Гаусса-Жордана:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
using namespace std;
const int INF = 123456789;
const double EPS = numeric_limits<double>::epsilon();
int gauss (vector < vector<double> > a, vector<double> & ans) {
    int n = (int) a.size();
    int m = (int) a[0].size() - 1;
    vector<int> where (m, -1);
    for (int col=0, row=0; col<m && row<n; ++col) {
        int sel = row;
        for (int i=row; i<n; ++i)
            if (abs (a[i][col]) > abs (a[sel][col]))
                sel = i;
        if (abs (a[sel][col]) < EPS)
            continue;
        for (int i=col; i<= m; ++i)
            swap (a[sel][i], a[row][i]);
        where[col] = row;
 
        for (int i=0; i<n; ++i)
            if (i != row) {
                double c = a[i][col] / a[row][col];
                for (int j=col; j<= m; ++j)
                    a[i][j] -= a[row][j] * c;
            }
        ++row;
    }
 
    ans.assign (m, 0);
    for (int i=0; i<m; ++i)
        if (where[i] != -1)
            ans[i] = a[where[i]][m] / a[where[i]][i];
    for (int i=0; i<n; ++i) {
        double sum = 0;
        for (int j=0; j<m; ++j)
            sum += ans[j] * a[i][j];
        if (abs (sum - a[i][m]) > EPS)
            return 0;
    }
 
    for (int i=0; i<m; ++i)
        if (where[i] == -1)
            return INF;
    return 1;
}
int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int n;
    std::cin >> n;
    std::vector < std::vector<double> > vec(n);
    for (int i = 0; i < n; ++i)
    {
        vec[i].resize(n + 1);
        for (int j = 0; j <= n; ++j)
            cin >> vec[i][j];
    }
    vector<double> res(n);
    gauss(vec, res);
    for (vector<double>::iterator it = res.begin(); it != res.end(); ++it)
        std::cout << static_cast<int> (*it + (*it < 0 ? -0.5 : 0.5)) << ' ';
    return 0;
}
Заточена под эту задачу, проходит все тесты.
Алгоритм взят отсюда и немного исправлен.
-=ЮрА=-
Заблокирован
Автор FAQ
04.08.2011, 15:22     Решить систему алгебраических линейных неоднородных уравнени #56
diagon , речь идёт о СЛАУ размерностью 4000х4000, речь не в том что методы не работают - а речь о скорости выполнения, полистай этот топик чтобы полностью вникнуть
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.08.2011, 15:25     Решить систему алгебраических линейных неоднородных уравнени #57
Ну я понял, у меня же не простой Гаусс =) Там пара оптимизаций есть... За http://www.cyberforum.ru/cgi-bin/latex.cgi?O({n}^{3}) примерно работает.
P.S. если матрица по модулю 2 - можно в 32 раза быстрее сделать =)
-=ЮрА=-
Заблокирован
Автор FAQ
04.08.2011, 15:37     Решить систему алгебраических линейных неоднородных уравнени #58
Ну как по мне он почти ничем не отличается
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
void PryamoiHod(int n, double **a, double *b)
{
        double v;
        for(int k = 0,i,j,im; k < n - 1; k++)
        {
                printf("UPDATING %04d ROW\r\n",k + 1);
                im = k;
                for(i = k + 1; i < n; i++)
                {
                        if(fabs(a[im][k]) < fabs(a[i][k]))
                        {
                                im = i;
                        }
                }
                if(im != k)
                {
                        for(j = 0; j < n; j++)
                        {
                            
                                v                = a[im][j];
                                a[im][j] = a[k][j];
                                a[k][j]  = v;
                        }
                        v     = b[im];
                        b[im] = b[k];
                        b[k]  = v;
                }
                for(i = k + 1; i < n; i++)
                {
                        v               = 1.0*a[i][k]/a[k][k];
                        a[i][k] = 0;
                        b[i]    = b[i] - v*b[k];
                        for(j = k + 1; j < n; j++)
                                a[i][j] -= v*a[k][j];
                }
        }
}
 
void ObratniHod(int n, double **a, double *b, double *x)
{
        double s = 0;
        x[n - 1] = 1.0*b[n - 1]/a[n - 1][n - 1];
        for(int i = n - 2, j; 0 <= i; i--)
        {
                printf("UPDATING %04d ROW\r\n",n - i - 1);
                s = 0;
                for(j = i + 1; j < n; j++)
                {
                        s = s+a[i][j]*x[j];
                }
                x[i] = 1.0*(b[i] - s)/a[i][i];
        }
}
Добавлено через 2 минуты
Введением EPS мы можем что то выграть, но не факт

Цитата Сообщение от diagon Посмотреть сообщение
if (abs (a[i][col]) > abs (a[sel][col]))
* * * * * * * * sel = i;
* * * * if (abs (a[sel][col]) < EPS)
* * * * * * continue;
* * * * for (int i=col; i<= m; ++i)
* * * * * * swap (a[sel][i], a[row][i]);
* * * * where[col] = row;
for (int i=0; i<n; ++i)
* * * * * * if (i != row) {
* * * * * * * * double c = a[i][col] / a[row][col];
* * * * * * * * for (int j=col; j<= m; ++j)
* * * * * * * * * * a[i][j] -= a[row][j] * c;
* * * * * * }
* * * * ++row;


Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
if(fabs(a[im][k]) < fabs(a[i][k]))
* * * * * * * * * * * * {
* * * * * * * * * * * * * * * * im = i;
* * * * * * * * * * * * }
* * * * * * * * }
* * * * * * * * if(im != k)
* * * * * * * * {
* * * * * * * * * * * * for(j = 0; j < n; j++)
* * * * * * * * * * * * {
v * * * * * * * *= a[im][j];
* * * * * * * * * * * * * * * * a[im][j] = a[k][j];
* * * * * * * * * * * * * * * * a[k][j] *= v;
* * * * * * * * * * * * }
* * * * * * * * * * * * v * * = b[im];
* * * * * * * * * * * * b[im] = b[k];
* * * * * * * * * * * * b[k] *= v;
* * * * * * * * }
* * * * * * * * for(i = k + 1; i < n; i++)
* * * * * * * * {
* * * * * * * * * * * * v * * * * * * * = 1.0*a[i][k]/a[k][k];
* * * * * * * * * * * * a[i][k] = 0;
* * * * * * * * * * * * b[i] * *= b[i] - v*b[k];
* * * * * * * * * * * * for(j = k + 1; j < n; j++)
* * * * * * * * * * * * * * * * a[i][j] -= v*a[k][j];
* * * * * * * * }
Цитата Сообщение от diagon Посмотреть сообщение
for (int i=0; i<n; ++i) {
* * * * double sum = 0;
* * * * for (int j=0; j<m; ++j)
* * * * * * sum += ans[j] * a[i][j];
* * * * if (abs (sum - a[i][m]) > EPS)
* * * * * * return 0;
* * }
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
x[n - 1] = 1.0*b[n - 1]/a[n - 1][n - 1];
* * * * for(int i = n - 2, j; 0 <= i; i--)
* * * * {
* * * * * * * * printf("UPDATING %04d ROW\r\n",n - i - 1);
* * * * * * * * s = 0;
* * * * * * * * for(j = i + 1; j < n; j++)
* * * * * * * * {
* * * * * * * * * * * * s = s+a[i][j]*x[j];
* * * * * * * * }
* * * * * * * * x[i] = 1.0*(b[i] - s)/a[i][i];
* * * * }
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
04.08.2011, 16:14  [ТС]     Решить систему алгебраических линейных неоднородных уравнени #59
Ну на самом же деле, алгоритм решения СЛУ методом Гаусса быстрее чем за О(n^3) решить не получиться. Но тем не менее, это неплохая скорость.
Вообще, если вести разговор о скорости выполнения алгоритма, то я где-то вычитал.. ах да - на википедии, что есть алгоритм "Копперсмита-Винограда", требующий времени О(n^2.375)
Думаю, неплохо было бы найти и его.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.08.2011, 17:09     Решить систему алгебраических линейных неоднородных уравнени
Еще ссылки по теме:

C++ Необходимо решить систему уравнений(C++)
C++ Система линейных алгебраических уравнений
C++ Решение системы линейных алгебраических уравнений методом Гаусса

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
04.08.2011, 17:09     Решить систему алгебраических линейных неоднородных уравнени #60
hello19, там же в википедии написано, что этот алгоритм имеет очень большую константу пропорциональности, так что для реальных матриц он неэффективен. Ведь О(n^2.375) это не скорость.
Yandex
Объявления
04.08.2011, 17:09     Решить систему алгебраических линейных неоднородных уравнени
Ответ Создать тему
Опции темы

Текущее время: 01:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru