Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.61/152: Рейтинг темы: голосов - 152, средняя оценка - 4.61
1 / 1 / 1
Регистрация: 19.07.2009
Сообщений: 54

Проверка на линейную зависимость / независимость набора векторов

10.09.2011, 18:03. Показов 32618. Ответов 11
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Линейная независимость векторов - задача по определению линейной зависимости / независимости заданного набора векторов стара, но мне приходится изучать её с самых азов. В связи с этим возникают как страшно банальные и возможно совершенно глупые вопросы, так и вопросы - какое из решений данной задачи является наиболее универсальным с точки зрения как метода, так и программирования ?

ЗАДАЧА: Конкретно в моём случае заключается в нахождении максимального числа линейно независимых векторов заданной длинны из данного набора векторов.

1) Первое что попалось на глаза было следующее решение:
Составить из данных векторов матрицу, и провести проверку на то обращается ли в нуль определитель (детерминант) данной матрицы.
Если определитель равен нулю, то векторы считаются линейно зависимыми.
Если определитель данной матрицы не равен нулю, соответственно векторы линейно независимы.
Алгоритмически задача нахождения определителя квадратной матрицы N*N не так сложна, много где описана, хоть и содержит в себе рекурсию, но разобраться в этом можно.

НО данный метод применим лишь для КВАДРАТНОЙ матрицы N*N.

2) Второй более универсальный метод нашёлся следующий:
Составить из данных векторов матрицу, вычислить ранг данной матрицы.
Если ранг меньше количества векторов значит векторы - линейно зависимы.
Алгоритм вполне рабочий, много где встречающийся, основанный на элементарных преобразованиях, и приведении матрицы к треугольному виду.

НО, и тут интересует случай с неквадратной матрицей, т.е. в случае, когда число векторов меньше длины этих векторов, т.е. 3 вектора длины 1х4.
Для первого случая а1=https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix} 3\\  5\\  4\\  6 \end{pmatrix}, а2=https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix} 1\\  2\\  4\\  3 \end{pmatrix}, а3=https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix} 4\\  6\\  3\\  2 \end{pmatrix} и тогда матрица (4х3): А=https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix} 3 & 1 & 4\\  5 & 2 & 6\\  4 & 4 & 3\\  6 & 3 & 2 \end{pmatrix}

Либо наоборот, когда число векторов больше, чем длинна векторов, 5 векторов длины 1х4.
Для данного случая а1=https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix} 3\\  5\\  4\\  6 \end{pmatrix}, а2=https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix} 1\\  2\\  4\\  3 \end{pmatrix}, а3=https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix} 4\\  6\\  3\\  2 \end{pmatrix}, а4=https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix} 2\\  1\\  5\\  2 \end{pmatrix}, а5=https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix} 5\\  3\\  2\\  4 \end{pmatrix} и тогда матрица (4х5): A=https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix} 3 & 1 & 4 & 2 & 5\\  5 & 2 & 6 & 1 & 3\\  4 & 4 & 3 & 5 & 2\\  6 & 3 & 2 & 2 & 4  \end{pmatrix}

Подскажите какой же алгоритм является универсальным для моей задачи. И на сколько применим второй метод для случаев произвольного кол-ва и произвольной длины векторов.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
10.09.2011, 18:03
Ответы с готовыми решениями:

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

Доказать линейную независимость системы векторов
Помогите решить задачу из задачника по алгебре Кострикина. Вот задача: Пусть дана система векторов...

Исследовать на линейную зависимость систему векторов
Здравствуйте. Впервые на вашем форуме, решил попросить совет у знающих людей! Нашел у вас подобные темы, но они непосредственно с...

11
Эксперт С++
 Аватар для grizlik78
2382 / 1666 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
10.09.2011, 18:48
По-моему метод с рангом вполне применим к любым матрицам. Квадратность матрицы здесь роли не играет.

Добавлено через 39 секунд
Только здесь, видимо, правильнее говорить о приведении не к треугольному виду, а к ступенчатой форме матрицы.
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
10.09.2011, 19:36
Проще привести к ступенчатому виду и проверить есть ли хотя бы одна нулевая строка. Если да, то ЛЗ, иначе ЛНЗ. Теорема Кронекера-Капелли (вернее, следствие теоремы)

Добавлено через 11 минут
Цитата Сообщение от Omnio Посмотреть сообщение
НО, и тут интересует случай с неквадратной матрицей
Абсолютно не важно какая матрица
1
1 / 1 / 1
Регистрация: 19.07.2009
Сообщений: 54
11.09.2011, 20:28  [ТС]
Цитата Сообщение от Thinker Посмотреть сообщение
Проще привести к ступенчатому виду и проверить есть ли хотя бы одна нулевая строка. Если да, то ЛЗ, иначе ЛНЗ. Теорема Кронекера-Капелли (вернее, следствие теоремы)

Добавлено через 11 минут


Абсолютно не важно какая матрица
Последовал вашему совету. Уже отдельное за него Спасибо.
Итак написал код. Хотелось бы уточнить верно ли я вас понял, ну и соответсвенно если не сложно чуток покритиковать сам код на работоспособность, и верность реализации вашей мысли. Буду рад дальнейшим комментариям касательно моей задачи, если возможно ещё что сказать есть.

Реализовал на С++ используя класс вектор.

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <cctype>
 
#include <iostream>
#include <vector>
#include <iterator>
#include <iomanip>
 
#include <conio.h>
 
using namespace std;
 
float rndup(float n)//round up a float type and show one decimal place
{
      float t;
      t=n-floor(n);
      if (t>=0.5)    
      {
              n*=10;//where n is the multi-decimal float
              ceil(n);
              n/=10;
              }
      else 
      {
              n*=10;//where n is the multi-decimal float
              floor(n);
              n/=10;
              }
      return n;
}     
 
void main(void)
{
 
    int row = 4;
    int col = 5;
    int i, j, k = 0;
vector <vector <double>> vmatrix(row);
    vector <vector <double>> cmatrix(row);
 
// Создаём исходную матрицу нужного размера и заполняем нулями
for(i=0; i<row; ++i)
{
        vmatrix[i].resize(col);
        cmatrix[i].resize(col);
 
        for(j=0; j<col; ++j)
        {
vmatrix[i][j] = 0;
        cmatrix[i][j] = 0;
}
}
        
/* 3x3
vmatrix[0][0]= 3 ;vmatrix[0][1]= 2 ;vmatrix[0][2]= 1 ;
vmatrix[1][0]= 2 ;vmatrix[1][1]= 1 ;vmatrix[1][2]= 3 ;
vmatrix[2][0]= 1 ;vmatrix[2][1]= 3 ;vmatrix[2][2]= 2 ;
//*/
 
/* 5x3
vmatrix[0][0]= 3 ;vmatrix[0][1]= 2 ;vmatrix[0][2]= 1 ;
vmatrix[1][0]= 2 ;vmatrix[1][1]= 1 ;vmatrix[1][2]= 3 ;
vmatrix[2][0]= 1 ;vmatrix[2][1]= 3 ;vmatrix[2][2]= 2 ;
vmatrix[3][0]= 4 ;vmatrix[3][1]= 1 ;vmatrix[3][2]= 3 ;
vmatrix[4][0]= 2 ;vmatrix[4][1]= 3 ;vmatrix[4][2]= 4 ;
//*/
 
//* 4x5 Задаём топорным методом
vmatrix[0][0]= 3 ;vmatrix[0][1]= 5 ;vmatrix[0][2]= 7 ;vmatrix[0][3]= 6 ;vmatrix[0][4]= 2 ;
vmatrix[1][0]= 1 ;vmatrix[1][1]= 2 ;vmatrix[1][2]= 3 ;vmatrix[1][3]= 4 ;vmatrix[1][4]= 1 ;
vmatrix[2][0]= 1 ;vmatrix[2][1]= 3 ;vmatrix[2][2]= 5 ;vmatrix[2][3]= 34 ;vmatrix[2][4]= 12 ;
vmatrix[3][0]= 4 ;vmatrix[3][1]= 1 ;vmatrix[3][2]= 3 ;vmatrix[3][3]= 3 ;vmatrix[3][4]= 11 ;
//*/
 
cmatrix = vmatrix; // Копируем значения из той что оставим не тронутой – vmatrix
// в ту, с котрой будем далее работать и производить
// преобразования и подсчёты - cmatrix
 
 
// Печать числа столбцов и числа строк в матрице
cout <<"col = "<< col <<" | row = "<< row <<"\n\n";
 
//*
cout <<"Matrix V:";
    cout <<"\n";
    for(i=0;i<row;i++)
    {
        for(j=0;j<col;j++)
        {
            cout << vmatrix[i][j] << "  ";
        }
    cout <<"\n";
    }
cout <<"\n";
//*/
 
system("pause");
 
 
// Нахождение РАНГА Матрицы и приведение к ступенчатому виду.
 
//*
// Приведение к ступенчатому виду путём элементарных преобразований
int count = 0;
int til = 0;
bool key = true;
double i2j = 0;
double mulxmj = 0;
//double mj = 0;
 
if(row <= col)
til = row;
else
til = col;
for (unsigned m = 0; m < til; ++m)
{
    if (cmatrix[m][m] == 0.0)
    {
        key = false;
        for (unsigned i1 = m+1; i1<row; ++i1)
        {
            if (cmatrix[i1][m] != 0.0)
            {
                key = true;
                swap(cmatrix[m], cmatrix[i1]);
                break;
            }
        }
    }
    if (!key)
    break; 
    
    for (unsigned i2 = m+1; i2<row; ++i2)
    {
        double multi = cmatrix[i2][m] / cmatrix[m][m];
        for (unsigned j = 0; j<col; ++j)
        {
            i2j = cmatrix[i2][j];
            i2j = rndup(i2j);
//          mj = cmatrix[m][j];
            mulxmj = (multi * cmatrix[m][j]);
            mulxmj = rndup(mulxmj);
            cmatrix[i2][j] = i2j - mulxmj;
        }
    }
}
 
//* ПОДСЧЁТ РАНГА
 
int rang = 0;
key = true;
 
for (unsigned i=0; i<row; ++i)
{
    key = false;
    for (unsigned j=0; j<col; ++j)
        if (cmatrix[i][j] != 0.0)
            key = true;
        if (!key)
            count++;
}
//*/
 
rang = row - count;
 
cout <<"rang = "<< rang << "\n";
cout <<"\n";
 
//*
cout <<"Matrix C:";
    cout <<"\n";
    for(i=0;i<row;i++)
    {
        for(j=0;j<col;j++)
        {
            cout << cmatrix[i][j] << "  ";
        }
    cout <<"\n";
    }
cout <<"\n";
//*/
 
 
system("pause");
 
}
0
Эксперт С++
 Аватар для grizlik78
2382 / 1666 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
12.09.2011, 21:46
Сначала немного по синтаксису.
Цитата Сообщение от Omnio Посмотреть сообщение
C++
1
void main(void)
Функция main должна возвращать int
C++
1
int main()
Цитата Сообщение от Omnio Посмотреть сообщение
C++
1
2
vector <vector <double>> vmatrix(row);
        vector <vector <double>> cmatrix(row);
Здесь нужен пробел между > и >
C++
1
2
vector <vector <double> > vmatrix(row);
vector <vector <double> > cmatrix(row);
Что касается реализации.
Если я правильно понял, break в строке 134 прекращает преобразование матрицы к ступенчатому виду, если в очередном столбце все оставшиеся элементы нулевые. На самом деле, если задача состоит в нахождении ранга, то надо перейти к следующему столбцу и продолжить преобразование (с той же строки).

Далее, в коде несколько раз встречаются сравнения с 0.0. Из-за погрешности представления чисел и вычислительных ошибок эта проверка может давать результат отличный от ожидаемого. Тут надо решить, считать ли зависимыми два вектора у которых лишь один элемент отличается на какую-то миллионную или миллиардную долю. Скорее всего да, и тогда сравнения надо производить с учётом "эпсилон".

Ну и хотя обращения матрицы не требуется, я бы всё-равно подумал бы об использовании выбора ведущего коэффициента, как при решении СЛАУ.
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.09.2011, 22:07
Цитата Сообщение от Thinker Посмотреть сообщение
Проще привести к ступенчатому виду и проверить есть ли хотя бы одна нулевая строка. Если да, то ЛЗ, иначе ЛНЗ. Теорема Кронекера-Капелли (вернее, следствие теоремы)
Все же уточню, мало ли что. Пусть A(m,n) - матрица размера m на n. Приводим к ступенчатому виду. Тогда ЛЗ тогда и только тогда, когда количество ступенек после приведения к ступенчатому виду < min(m,n)
Но, думаю, это было понятно.
0
Эксперт С++
 Аватар для grizlik78
2382 / 1666 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
12.09.2011, 22:11
Thinker, изначально задача ставилась в нахождении максимального количество лин. независимых векторов из набора. Понятно, что их не может быть больше, чем размер вектора, но может быть меньше. Эта задача сводится к определению ранга матрицы из этих векторов.
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.09.2011, 22:14
Цитата Сообщение от grizlik78 Посмотреть сообщение
Thinker, изначально задача ставилась в нахождении максимального количество лин. независимых векторов из набора. Понятно, что их не может быть больше, чем размер вектора, но может быть меньше. Эта задача сводится к определению ранга матрицы из этих векторов.
Ранг матрицы (неформально) - количество ступенек после приведения к ступенчатому виду, это очевидно
0
12.09.2011, 22:16

Не по теме:

Цитата Сообщение от grizlik78 Посмотреть сообщение
Здесь нужен пробел между > и >
в новом стандарте не нужен
может автор на 2010 студии пишет

0
Эксперт С++
 Аватар для grizlik78
2382 / 1666 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
12.09.2011, 22:16
Цитата Сообщение от Thinker Посмотреть сообщение
Ранг матрицы (неформально) - количество ступенек после элементарных преобразований, это очевидно
Сообщение, на которое я отвечал, выглядело по-другому
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.09.2011, 22:18
Цитата Сообщение от grizlik78 Посмотреть сообщение
Сообщение, на которое я отвечал, выглядело по-другому
Все течет, все меняется
0
12.09.2011, 22:20

Не по теме:

Цитата Сообщение от sandye51 Посмотреть сообщение
в новом стандарте не нужен
Не нужен в русском языке несколько неоднозначно звучит. Либо можно не ставить, либо нельзя ставить. Но новый стандарт ещё не опубликован, а компиляторов не поддерживающих его пока больше, чем поддерживающих. Даже в GCC приходится дополнительную опцию указывать.
Цитата Сообщение от sandye51 Посмотреть сообщение
может автор на 2010 студии пишет
Может. А я, может, не в ней проверяю :)

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
12.09.2011, 22:20
Помогаю со студенческими работами здесь

Исследовать системы векторов a и b на линейную зависимость
Исследовать системы векторов a и b на линейную зависимость. В случае линейной зависимости привести пример нетривиальной линейной...

Исследовать на линейную зависимость систему векторов
a={2, -3,1}, b={3,- 1,5}, c={1,-4,3} помогите пожалуйста решить

Задание по алгебре на линейную зависимость векторов
Доброго времени суток) помогите пожалуйста с заданием по алгебре. Выяснить линейную зависимость системы векторов: 1 , sinx , cosx. ...

Линейная алгебра. Линейная зависимость-независимость векторов
Являются ли вектора пространства L линейно независимыми? Если линейно зависимые, то выбрать из них линейно независимые вектора,...

Доказать линейную независимость
Доказать, что система E:={e1,e2,e3} линейно независима, где: e1=(a11,0,0,0) e2=(a21,a22,a23,0) e3=(a31,a32,a33,a34) ...


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
Архитектура слоя интернета для сервера-слоя.
Hrethgir 11.04.2026
В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа
Maks 10.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .
Очистка реквизитов документа при копировании
Maks 09.04.2026
Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий
anaschu 08.04.2026
https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI
Блокировка документа от изменений, если он открыт у другого пользователя
Maks 08.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка.
Hrethgir 08.04.2026
Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов.
anaschu 08.04.2026
работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики.
Hrethgir 07.04.2026
Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru