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

Найти обратную матрицу и умножить ее на вектор - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 204, средняя оценка - 4.91
Карина!
0 / 0 / 0
Регистрация: 08.11.2010
Сообщений: 9
08.11.2010, 20:49     Найти обратную матрицу и умножить ее на вектор #1
Очень нужна помощь для нахождения обратной матрицы на С++.
Дело в том что мне нужно реализовать такую задачу:
найти обратную матрицу и умножить ее на вектор.
каким методом лучше находить обратную матрицу и какой алгоритм нахождения...помогите пожалуйста.
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Unforgiven_00
60 / 60 / 2
Регистрация: 12.10.2010
Сообщений: 129
08.11.2010, 20:52     Найти обратную матрицу и умножить ее на вектор #2
Метод Гаусса—Жордана
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
09.11.2010, 00:14     Найти обратную матрицу и умножить ее на вектор #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
 
void inversion(double **A, int N)
{
    double temp;
 
    double **E = new double *[N];
 
    for (int i = 0; i < N; i++)
        E[i] = new double [N];
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            E[i][j] = 0.0;
 
            if (i == j)
                E[i][j] = 1.0;
        }
 
    for (int k = 0; k < N; k++)
    {
        temp = A[k][k];
 
        for (int j = 0; j < N; j++)
        {
            A[k][j] /= temp;
            E[k][j] /= temp;
        }
 
        for (int i = k + 1; i < N; i++)
        {
            temp = A[i][k];
 
            for (int j = 0; j < N; j++)
            {
                A[i][j] -= A[k][j] * temp;
                E[i][j] -= E[k][j] * temp;
            }
        }
    }
 
    for (int k = N - 1; k > 0; k--)
    {
        for (int i = k - 1; i >= 0; i--)
        {
            temp = A[i][k];
 
            for (int j = 0; j < N; j++)
            {
                A[i][j] -= A[k][j] * temp;
                E[i][j] -= E[k][j] * temp;
            }
        }
    }
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            A[i][j] = E[i][j];
 
    for (int i = 0; i < N; i++)
        delete [] E[i];
 
    delete [] E;
}
 
int main()
{
    int N;
 
    std::cout << "Enter N: ";
    std::cin >> N;
 
    double **matrix = new double *[N];
 
    for (int i = 0; i < N; i++)
        matrix[i] = new double [N];
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            std::cout << "Enter matrix[" << i << "][" << j << "] = ";
            std::cin >> matrix[i][j];
        }
 
    inversion(matrix, N);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            std::cout << matrix[i][j] << "  ";
 
        std::cout << std::endl;
    }
 
    for (int i = 0; i < N; i++)
        delete [] matrix[i];
 
    delete [] matrix;
 
    std::cin.get();
    return 0;
}
Карина!
0 / 0 / 0
Регистрация: 08.11.2010
Сообщений: 9
09.11.2010, 00:26  [ТС]     Найти обратную матрицу и умножить ее на вектор #4
а можно написать коротко алгоритм этой проги....какую максимальную матрицу она может расчитать..
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
09.11.2010, 00:35     Найти обратную матрицу и умножить ее на вектор #5
На счёт максимальной не знаю... Думаю, ограничение идёт только по доступной памяти. А алгоритм основан на методе Гаусса (вернее на его модификации - метода Гаусса-Жордана - т.н. методе полного исключения неизвестных). Мы просто-напросто с помощью элементарных преобразований приводим начальную матрицу к единичной. А вся фишка в том, что если те же преобразования в том же порядке применить к единичной матрице - получим матрицу, обратную для начальной.
Карина!
0 / 0 / 0
Регистрация: 08.11.2010
Сообщений: 9
09.11.2010, 00:38  [ТС]     Найти обратную матрицу и умножить ее на вектор #6
а этод метод можно распаралелить через портфель задач и мютексы?а потом еще и умножить на вектор?

Добавлено через 1 минуту
и на счет метода:
не могу найти нормальный словесный алгорит, что умножаем что делим и вычитаем...
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
09.11.2010, 00:39     Найти обратную матрицу и умножить ее на вектор #7
Ух ты, вот это спросили))) Я не в курсе, параллельным программированием никогда не занимался... По идее тут цикл, поэтому чисто теоретически распараллелить можно... Но вот как - это уже вопрос не ко мне.
Ну а кто мешает умножить матрицу на вектор? По-моему никто.
Карина!
0 / 0 / 0
Регистрация: 08.11.2010
Сообщений: 9
09.11.2010, 00:41  [ТС]     Найти обратную матрицу и умножить ее на вектор #8
а можете хотя бы на словах описать программу.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
09.11.2010, 00:42     Найти обратную матрицу и умножить ее на вектор #9
http://ru.wikipedia.org/wiki/Метод_Гаусса_—_Жордана
Irkira
Сообщений: n/a
24.01.2012, 11:01     Найти обратную матрицу и умножить ее на вектор #10
Метод Гаусса—Жордана
silent_1991, спасибо за код, очень помог
7rubin
-43 / 0 / 1
Регистрация: 18.03.2012
Сообщений: 22
20.04.2012, 03:47     Найти обратную матрицу и умножить ее на вектор #11
да, спасибо)
пожалуй единственная прога просто реализованная, и хорошо работающая из тех что лежат в нете
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
12.09.2012, 13:20     Найти обратную матрицу и умножить ее на вектор #12
Котаны, автозаменой переделал под Qt...
C++ (Qt)
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
template <int N, typename T> QGenericMatrix<N,N,T> invert(QGenericMatrix<N,N,T> matrix)
{
    T temp;
 
    QGenericMatrix<N,N,T> ret;
    ret.setToIdentity();
    T* rM = ret.data();
    T* sM = matrix.data();
 
 
 
    for (int k = 0; k < N; k++)
    {
        temp = sM[k + k * N];
 
        for (int j = 0; j < N; j++)
        {
            sM[k + j * N] /= temp;
            rM[k + j * N] /= temp;
        }
 
        for (int i = k + 1; i < N; i++)
        {
            temp = sM[i + k * N];
 
            for (int j = 0; j < N; j++)
            {
                sM[i + j * N] -= sM[k + j * N] * temp;
                rM[i + j * N] -= rM[k + j * N] * temp;
            }
        }
    }
 
    for (int k = N - 1; k > 0; k--)
    {
        for (int i = k - 1; i >= 0; i--)
        {
            temp = sM[i + k * N];
 
            for (int j = 0; j < N; j++)
            {
                sM[i + j * N] -= sM[k + j * N] * temp;
                rM[i + j * N] -= rM[k + j * N] * temp;
            }
        }
    }
    return ret;
}
Добавлено через 23 минуты
Ну и до кучи коротенький пример решения СЛАУ н-ого порядка:
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
    QGenericMatrix<2,2,qreal> matrix;
    matrix(0,0) = 1;
    matrix(0,1) = 7;
    matrix(1,0) = 1;
    matrix(1,1) = 2;
    QGenericMatrix<1,2,qreal> b;
    b(0,0) = 9;
    b(1,0) = 4;
 
    QGenericMatrix<1,2,qreal> solution = invert(matrix) * b;
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
16.11.2012, 02:09     Найти обратную матрицу и умножить ее на вектор #13
Мне тут в личке сообщили о баге, выкладываю новую версию обращения матрица. Писал тоже давно, особо не тестировал, так что баги также не исключены.
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <cmath>
 
// Функция, производящая обращение матрицы.
// Принимает:
//     matrix - матрица для обращения
//     result - матрица достаточного размера для вмещения результата
//     size   - размерность матрицы
// Возвращает:
//     true в случае успешного обращения, false в противном случае
bool inverse(double **matrix, double **result, int size)
{   
    // Изначально результирующая матрица является единичной
    // Заполняем единичную матрицу
    for (int i = 0; i < size; ++i)
    {
        for (int j = 0; j < size; ++j)
            result[i][j] = 0.0;
        
        result[i][i] = 1.0;
    }
    
    // Копия исходной матрицы
    double **copy = new double *[size]();
    
    // Заполняем копию исходной матрицы
    for (int i = 0; i < size; ++i)
    {
        copy[i] = new double [size];
        
        for (int j = 0; j < size; ++j)
            copy[i][j] = matrix[i][j];
    }
    
    // Проходим по строкам матрицы (назовём их исходными)
    // сверху вниз. На данном этапе происходит прямой ход
    // и исходная матрица превращается в верхнюю треугольную
    for (int k = 0; k < size; ++k)
    {
        // Если элемент на главной диагонали в исходной
        // строке - нуль, то ищем строку, где элемент
        // того же столбца не нулевой, и меняем строки
        // местами
        if (fabs(copy[k][k]) < 1e-8)
        {
            // Ключ, говорязий о том, что был произведён обмен строк
            bool changed = false;
            
            // Идём по строкам, расположенным ниже исходной
            for (int i = k + 1; i < size; ++i)
            {
                // Если нашли строку, где в том же столбце
                // имеется ненулевой элемент
                if (fabs(copy[i][k]) > 1e-8)
                {
                    // Меняем найденную и исходную строки местами
                    // как в исходной матрице, так и в единичной
                    std::swap(copy[k],   copy[i]);
                    std::swap(result[k], result[i]);
                    
                    // Взводим ключ - сообщаем о произведённом обмене строк
                    changed = true;
                    
                    break;
                }
            }
            
            // Если обмен строк произведён не был - матрица не может быть
            // обращена
            if (!changed)
            {
                // Чистим память
                for (int i = 0; i < size; ++i)
                    delete [] copy[i];
                
                delete [] copy;
                
                // Сообщаем о неудаче обращения
                return false;
            }
        }
        
        // Запоминаем делитель - диагональный элемент
        double div = copy[k][k];
        
        // Все элементы исходной строки делим на диагональный
        // элемент как в исходной матрице, так и в единичной
        for (int j = 0; j < size; ++j)
        {
            copy[k][j]   /= div;
            result[k][j] /= div;
        }
        
        // Идём по строкам, которые расположены ниже исходной
        for (int i = k + 1; i < size; ++i)
        {
            // Запоминаем множитель - элемент очередной строки,
            // расположенный под диагональным элементом исходной
            // строки
            double multi = copy[i][k];
            
            // Отнимаем от очередной строки исходную, умноженную
            // на сохранённый ранее множитель как в исходной,
            // так и в единичной матрице
            for (int j = 0; j < size; ++j)
            {
                copy[i][j]   -= multi * copy[k][j];
                result[i][j] -= multi * result[k][j];
            }
        }
    }
    
    // Проходим по вернхней треугольной матрице, полученной
    // на прямом ходе, снизу вверх
    // На данном этапе происходит обратный ход, и из исходной
    // матрицы окончательно формируется единичная, а из единичной -
    // обратная
    for (int k = size - 1; k > 0; --k)
    {
        // Идём по строкам, которые расположены выше исходной
        for (int i = k - 1; i + 1 > 0; --i)
        {
            // Запоминаем множитель - элемент очередной строки,
            // расположенный над диагональным элементом исходной
            // строки
            double multi = copy[i][k];
            
            // Отнимаем от очередной строки исходную, умноженную
            // на сохранённый ранее множитель как в исходной,
            // так и в единичной матрице
            for (int j = 0; j < size; ++j)
            {
                copy[i][j]   -= multi * copy[k][j];
                result[i][j] -= multi * result[k][j];
            }
        }
    }
    
    // Чистим память
    for (int i = 0; i < size; ++i)
        delete [] copy[i];
    
    delete [] copy;
    
    // Сообщаем об успехе обращения
    return true;
}
AlexP11223
36 / 37 / 4
Регистрация: 20.04.2011
Сообщений: 288
16.11.2012, 11:11     Найти обратную матрицу и умножить ее на вектор #14
А проверка обмена строк (changed) зачем? Если детерминант всегда не 0, то он не нужен?
XRuZzz
Антикодер
577 / 478 / 23
Регистрация: 15.09.2012
Сообщений: 2,429
16.11.2012, 11:38     Найти обратную матрицу и умножить ее на вектор #15
а этод метод можно распаралелить через портфель задач и мютексы?а потом еще и умножить на вектор?
а вы супер компьютер строите?

обычно делается две задачи (или потока) один для пользовательского интерфейса, чтоб кнопки не подвисали, а другой для мат. вычислений.

а распределять мат вычисления в железе это задача не для новичков, думаю что есть смысл посмотреть это
http://ru.wikipedia.org/wiki/Intel_T...uilding_Blocks
(в том смысле, что кто лучше интела сможет работать с их процом?)

возможно видяху тоже можно как то подключить для мат вычислений.

в любой случае надо сначала посчитать программно сколько времени вы теряете на каждом цикле

мьютекс это просто ограничитель для использования данных

Добавлено через 15 минут
в параллельном программировании у меня маленький опыт, но думаю это делается так
надо для начала разбить долгие вычисления на две части, у которых есть что то на входе и выходе.
Получается например две задачи будут выполнять сложные вычисления, третья будет делать остальные вычисления и четвертая задача может ожидать например от пользователя отмены вычислений.

Все данные которые мы получаем в первом потоке мы не напрямую отправляем во второй поток, а пользуемся конструкцией типа почтового ящика которая отправляет сообщения, и в сообщении просто указываем адрес где находится результат.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
16.11.2012, 16:15     Найти обратную матрицу и умножить ее на вектор #16
Цитата Сообщение от AlexP11223 Посмотреть сообщение
Если детерминант всегда не 0, то он не нужен?
Если уверены, что матрица не вырожденная - проверка не нужна. Но лучше её всё же оставить (я бы оставил), универсальность никогда не повредит.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
07.05.2013, 21:03     Найти обратную матрицу и умножить ее на вектор #17
Написал вот. Работает правильно, но не проверял на контесторах, так что, если найдёте баги пишите.
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
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <deque>
#include <set>
#include <string>
#include <limits>
#include <fstream>
 
using namespace std;
 
vector < vector <double> > inverse(vector < vector <double> > a) {
    int n = a.size();
    vector < vector <double> > ans(n, vector <double> (n, 0));  
    for (int i = 0; i < n; i++){
        ans[i][i] = 1.0;
    }  
    for (int i = 0; i < n; i++){
        int row = i;
        double mx = a[i][i];
        for(int k = i + 1; k < n; k++){
            if (abs(a[k][i]) > mx){
                row = k;
                mx = abs(a[k][i]);
            }
        }
        if (row != i) {
            swap(a[row], a[i]);
            swap(ans[row], ans[i]);
        }
        for (int j = i+1; j < n; j++){
            double e = a[j][i]/a[i][i];
            for (int k = 0; k < n; k++){
                a[j][k] -= e*a[i][k];
                ans[j][k] -= e*ans[i][k];
            }
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i - 1; j >= 0; j--){
            double e = a[j][i]/a[i][i];
            for (int k = 0; k < n; k++){
                a[j][k] -= e*a[i][k];
                ans[j][k] -= e*ans[i][k];
            }
        }
        for (int j = 0; j < n; j++) {
            ans[i][j] /= a[i][i];
        }
    }
    return ans;
}
 
int main(){
    int n;
    cin >> n;
    vector < vector <double> > a(n, vector <double> (n, 0)), ans;
 
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            scanf("%lf", &a[i][j]);
        }
    } 
 
    ans = inverse(a);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%.15lf ", ans[i][j]);
        }
        puts("");
    }
    return 0;
}
Добавлено через 5 минут
Обновил код

Добавлено через 34 минуты
Лично протестировал несколько матриц, всё сходилось. Особенно удобно проверять так : сделали матрицу, нашли обратную, затем нашли обратную к обратной и сверились.
Sabijan
0 / 0 / 0
Регистрация: 21.02.2013
Сообщений: 7
23.02.2014, 14:17     Найти обратную матрицу и умножить ее на вектор #18
извините, если придирчиво проверять(как делает это мой препод по кодингу), ваш код не работает в случае с нулевыми элементами, например для такой матрицы:
0 0 2
0 5 4
6 4 6

Добавлено через 15 минут
Цитата Сообщение от Ternsip Посмотреть сообщение
Лично протестировал несколько матриц, всё сходилось. Особенно удобно проверять так : сделали матрицу, нашли обратную, затем нашли обратную к обратной и сверились.
я пробовал проверять через excel
матрица
0 0 2
0 5 4
6 4 6
первая строка матрицы, найденной юзая ваш код не совпадает
в прочем другие две строки выводятся правильно
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
23.02.2014, 14:51     Найти обратную матрицу и умножить ее на вектор #19
Цитата Сообщение от Sabijan Посмотреть сообщение
если придирчиво проверять
Это не придирчивость, а вполне обычная проверка стандартной ситуации. У произвольной матрицы на главной диагонали запросто могут быть нулевые элементы. Поэтому правильный метод и включает шаг с перестановкой строк в случае, если очередная строка на главной диагонали содержит нулевой элемент.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.02.2014, 15:11     Найти обратную матрицу и умножить ее на вектор
Еще ссылки по теме:

C++ Найти обратную матрицу
в матрице А(n x m) найти первый столбец, не содержащий отрицательных элементов, и умножить его как вектор на матрицу А C++
Умножить матрицу 10х10 на вектор из 10 элементов C++

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

Или воспользуйтесь поиском по форуму:
Sabijan
0 / 0 / 0
Регистрация: 21.02.2013
Сообщений: 7
23.02.2014, 15:11     Найти обратную матрицу и умножить ее на вектор #20
извините, пытался реализовать ваш код на dev cpp вышла проблема с std::swap. какую библиотеку подключить?

Добавлено через 55 секунд
или можно заменить swap чем-нибудь?
Yandex
Объявления
23.02.2014, 15:11     Найти обратную матрицу и умножить ее на вектор
Ответ Создать тему
Опции темы

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