Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > базисные и опорные решения СЛАУ

Автор: Веталька 24.1.2010, 21:23

подскажите как связать это с решением СЛАУ методом Жордана-Гаусса?
тоисть заставить искать базисные и опорные решения

Код


#include "stdafx.h"
#include <vector>
#include <iostream>
#include <conio.h>
#include <stdlib.h>

using namespace std;

void main()
{
    int n, m;
    cin>>n>>m;
 vector <vector <double> > sist(n, vector <double> (m));
    int i, j, k, p, pos, q, i1, j1, j2, x, x1, y, y1=0;
 double max, g, k1, p1, pos1;
 //double arr[n][m];
 
 for (i=0; i<n; i++)
        for (j=0;j<m; j++)
            cin>>sist[i][j]; 
 for (k=0; k<m-1; k++)
    {
        p=q=k;
        max=sist[k][k];
        for (i=k; i<n; i++)
            for (j=k; j<m-1; j++)
                if (abs(sist[i][j])>max)
                {
                    max=sist[i][j];
                    p=i;
                    q=j;
                }

        for (i=0; i<n; i++)
        {
            pos1=sist[i][k];
            sist[i][k]=sist[i][q];
            sist[i][q]=pos1;
        }
        for (j=0; j<m; j++)
        {
            pos1=sist[k][j];
            sist[k][j]=sist[p][j];
            sist[p][j]=pos1;
        }
 }
 for (i=0; i<n; i++){x1=0;
  for (j=0; j<m; j++){
   if (sist[i][j]==0) {
    x1++;
   if (x1>=m){ 
    y1++;
    /*vector <vector <double> > basis(n-y1, vector <double> (n-y1));
    for (i1=0; i1<n-y1; i1++){
     for (j1=0; j1<n-y1; j1++){
      basis[i1][j1]=sist[i1][j1];
     }
    }*/
   }
   }
   if (i==j && sist[i][j]!=0){
    pos=i;
    g=sist[pos][pos];
    for (i1=0; i1<n; i1++){
      //if (i1!=pos){
        p1=sist[i1][pos];
        for (j1=pos; j1<m; j1++){
         if (i1!=pos) {
         k1=sist[pos][j1]*p1/sist[pos][pos];
         sist[i1][j1]=sist[i1][j1]-k1;
        }else sist[i1][j1]=sist[i1][j1]/g;
      }
      //else for (j2=0; j2<m; j2++)sist[i1][j2]=sist[i1][j2]/g;
     }
   }
   
  }
 }
 cout<<endl<<endl;
 if (y1==0)
    for (i=0; i<n; i++){
            for (j=0; j<m; j++)
                cout<<sist[i][j]<<" ";
            cout<<endl;
    }
 if (y1>0){  
  cout<<"yo moe"<<endl<<endl;
 }
    cout<<endl;  
    getch();
}

Автор: Лешкин 24.1.2010, 21:34

У меня та же тема...
Хотелось бы знать, как реализовать на с++ нахождение базисных решений СЛАУ и как вообще дать программе знать, когда какое решение (общее, базисное, опорное) искать...

Автор: comcon1 24.1.2010, 23:08

Ответьте на вопрос: что такое "общее решение" для вырожденной непротиворечивой СЛАУ?
Просто я даже не знаю, что Вам писать. Просто если вы не понимаете математику, речь о С++ водить бесполезно.

Автор: Лешкин 24.1.2010, 23:19

ну, если слау вырожденая, то нужно проверить систему на совместность. если система совместна, то может быть тривиальное решение или базисное. Вроде так... Если нет, для начала буду рад ссылке на толковое разъяснение даной темы для бестолочи (меня)...

Автор: comcon1 24.1.2010, 23:36

может быть тривиальное решение или базисное?

Нет, решение СЛАУ одно. Если система вырождена и совместна, то решение есть вектор X некоего подпространства. Небоходимо найти
1) размерность подпространства решений
2) выразить решение (вектор X) в виде л.к.:
X = X0 + a1X1 + a2X2 + .. + anXn, где X1 - Xn - базис подпространства, X0 - постоянный вектор, an - произвольные коэффициентики

Деление решений на базисные, небазисные и прочую фигню - исключительно искусственно.

З.Ы. Я не вижу в приведенном коде даже проверки на совместность.

Добавлено через 1 минуту и 22 секунды
Толковой ссылки не знаю. Учебники по ЛинАлу, наверно. Пишите конкретно, чего не ясно, здесь ответят.

Автор: Лешкин 26.1.2010, 01:19

Для точности: дано задание на лабораторную: 1)а) решить СЛУ методом Жордана-Гаусса; б)найти все базисные решения; 2) найти все опорные (неотрицательные базисные) решения СЛУ.
Приведенный вверху код решает систему методом Жордана-Гаусса, если количество уравнений равно количеству неизвестных (или ранг основной матрицы равен количеству неизвестных-так наверное точнее сказано).
Если количество уравнений меньше количества неизвестных, то именно тогда, я так понимаю, нужно искать базисные решения.
По поводу проверки на совместность: нужно сравнить ранг основной матрицы и расширенной. Но как вписать поиск ранга в имеющийся код?

Автор: comcon1 26.1.2010, 02:45

Что значит "как вписать"? У тебя есть матрицы-массивы. Есть гугл и запрос "нахождение ранга матрицы". Что конкретно не понятно?

Автор: Лешкин 26.1.2010, 18:32

Код


#include <vector>
#include <iostream>
#include <conio.h>
#include <stdlib.h>

using namespace std;

void main()
{
    int n, m;
    cin>>n>>m;
    vector <vector <double> > sist(n, vector <double> (m));
    int i, j, k, p, pos, q, i1, j1, j2, x, x1, y, y1=0;
    double max, g, k1, p1, pos1;
    
    for (i=0; i<n; i++)
        for (j=0;j<m; j++)
            cin>>sist[i][j];    
//с сортировкой программа не работает для систем, где количество уравнений меньше количества неизвестных
    /*for (k=0; k<m-1; k++)
    {
        p=q=k;
        max=sist[k][k];
        for (i=k; i<n; i++)
            for (j=k; j<m-1; j++)
                if (abs(sist[i][j])>max)
                {
                    max=sist[i][j];
                    p=i;
                    q=j;
                }

        for (i=0; i<n; i++)
        {
            pos1=sist[i][k];
            sist[i][k]=sist[i][q];
            sist[i][q]=pos1;
        }
        for (j=0; j<m; j++)
        {
            pos1=sist[k][j];
            sist[k][j]=sist[p][j];
            sist[p][j]=pos1;
        }
    }*/
    x=0;
    y=0;
    for (i=0; i<n; i++){
        for (j=0; j<m; j++){
            if (i==j && sist[i][j]!=0){
                x++;//количество единиц на диагонали
                pos=i;
                g=sist[pos][pos];
                for (i1=0; i1<n; i1++){
                    p1=sist[i1][pos];
                    for (j1=pos; j1<m; j1++){
                        if (i1!=pos) {//решение методом ж-г за формулой:
                            k1=sist[pos][j1]*p1/sist[pos][pos];
                            sist[i1][j1]=sist[i1][j1]-k1;
                        }
                        else sist[i1][j1]=sist[i1][j1]/g;
                    }
                }
            }
            if (i==j && sist[i][j]==0) y++;
        }
    }
    cout<<endl<<endl;
   /* for (i=0; i<n-y; i++){
            for (j=0; j<m; j++)
                cout<<sist[i][j]<<" ";
            cout<<endl;
    }*/
    
    if (x==m-1)cout<<"rozv'yazok odun:"<<endl;
    if (x==0){
        cout<<"rang: 1"<<endl;

    }
    else cout<<"rang: "<<x<<endl;

    
    cout<<endl;  
    getch();
}

Ну вот, ранг теперь вычисляется.

Автор: Лешкин 26.1.2010, 19:05

Далее: если ранг равен количеству переменных, то можна выводить результат решения методом ж-г--последний столбец;
если ранг меньше количества переменных, то нужно искать общее решение (в виде выражения базисных неизвестных через свободные) и базисное решение. Это я взял с небольших указаний к лабораторной...
Вы пишете, что:

Цитата

Небоходимо найти
1) размерность подпространства решений

это будет С(n^m), где n-количество неизвестных, а m-количество базисных неизвестных.
базисные неизвестные-это те, которые после прохода массива методом ж-г встречаются только в одном уравнении (тоесть 1 при (i=j) и 0 в других ячейках столбика j).

Цитата

2) выразить решение (вектор X) в виде л.к.:
X = X0 + a1X1 + a2X2 + .. + anXn, где X1 - Xn - базис подпространства, X0 - постоянный вектор, an - произвольные коэффициентики

1)Допустим, система АХ=В. постоянный вектор-это В?
2)Если что не так, прошу исправить меня.
3)Теперь самый важный на сегодня вопрос: мне теперь разбивать вектор, который есть, и потом каким-то образом выражать общее решение (прошу подсказать как), или можно обойтись без этого?

Автор: comcon1 26.1.2010, 20:09

Ну вот смотри:
x+4y+8z = 5

Соответственно ранг = 1
Кол-во переменных = 3

Базис подпространства решений = 3-1 = 2 базисные функции
x = 5 - 4y -8z

Соответственно решение:
(x,y,z) = (5-4y-8z, y, z) =
= (5, 0, 0) + (-4, 1, 0)y + (-8, 0, 1)z

Это чтобы был наглядный пример, на который ориентироваться при работе с общим видом.

Автор: Лешкин 26.1.2010, 20:29

спасибо), пробую дальше...

Автор: Лешкин 26.1.2010, 23:29

Код


#include "stdafx.h"
#include <vector>
#include <iostream>
#include <conio.h>
#include <stdlib.h>

using namespace std;

void main()
{
    int n, m;
    cin>>n>>m;
    vector <vector <double> > sist(n, vector <double> (m));
     
//Для проверочек:
/*
1:
            3 5
    1 -1 3 1 4
    2 3 -1 -1 6
    1 -6 10 4 6
2:    
     4 5
    1 1 -3 2 6
    1 -2 0 -1 -6
    0 1 1 3 16
    2 -3 2 0 6
    */
    //Задание
     /*3 5 
     1  -3   0   -6  9
     2   1  -5    1  8
    3   5  -10   8  7    
    */
    int i, j, k, p, pos, q, i1, j1, j2, x, x1, y, y1=0;
    double max, g, k1, p1, pos1;
    
    for (i=0; i<n; i++)
        for (j=0;j<m; j++)
            cin>>sist[i][j];    
//далее идет сортировка массива для опускания нулей вниз и передвижение максимальных на диагональ.
//она почему то работает только для матрицы "для проверочек 2:" , для других пишет ошибку "vector subscript out of range" 
    /*for (k=0; k<m-1; k++)
    {
        p=q=k;
        max=sist[k][k];
        for (i=k; i<n; i++)
            for (j=k; j<m-1; j++)
                if (abs(sist[i][j])>max)
                {
                    max=sist[i][j];
                    p=i;
                    q=j;
                }

        for (i=0; i<n; i++)
        {
            pos1=sist[i][k];
            sist[i][k]=sist[i][q];
            sist[i][q]=pos1;
        }
        for (j=0; j<m; j++)
        {
            pos1=sist[k][j];
            sist[k][j]=sist[p][j];
            sist[p][j]=pos1;
        }
    }*/
    x=0;
    y=0;
    for (i=0; i<n; i++){
        for (j=0; j<m; j++){
            if (i==j && sist[i][j]!=0){
                x++;//количество единиц на диагонали
                pos=i;
                g=sist[pos][pos];
                for (i1=0; i1<n; i1++){
                    p1=sist[i1][pos];
                    for (j1=pos; j1<m; j1++){
                        if (i1!=pos) {//формула решения методом ж-г:
                            k1=sist[pos][j1]*p1/sist[pos][pos];
                            sist[i1][j1]=sist[i1][j1]-k1;
                        }
                        else sist[i1][j1]=sist[i1][j1]/g;
                    }
                }
            }
            if (i==j && sist[i][j]==0) y++;
        }
    }
    cout<<endl<<endl;
    for (i=0; i<n-y; i++){
            for (j=0; j<m; j++)
                cout<<sist[i][j]<<" ";
            cout<<endl;
    }
    
    /*if (x==0){ 
        cout<<"rang: 1"<<endl;
        cout<<"razmernost basisnogo reshenia: "<<m-1;
    }
    else {
        cout<<"rang: "<<x<<endl;
        cout<<"razmernost basisnogo reshenia: "<<m-1-x<<endl;
    }*/    
    vector <int> a(m-1-x);
    for (i=0; i<m-1-x; i++) 
        a[i]=i+1;
    if (x==m-1){
        cout<<"reshenie odno:"<<endl<<"{";
        for (i=0; i<n-1; i++)
            cout<<sist[i][m-1]<<", ";
        cout<<sist[n-1][m-1];
        cout<<"}"<<endl;
    }
    else {
        cout<<"obshchee reshenie: "<<endl<<"{";
        for (i=0; i<x; i++){
            cout<<sist[i][m-1];
            for (j=m-1-x; j<m-1; j++){
                if (sist[i][j]>=0)
                    cout<<-sist[i][j]<<"·C"<<a[j-x];
                else{
                    cout<<"+"<<-sist[i][j]<<"·C"<<a[j-x];
                }
            }
            cout<<"; ";
        }
        for (k=x; k<m-2; k++){
            cout<<"·C"<<a[k-x]<<"; ";
        }
        cout<<"·C"<<a[m-2-x]<<"}"<<endl;
    }
    cout<<endl;  
    getch();
}

Итак, программа решает системы с рангом равным количеству неизвестных, а также находит общее решение для системы с рангом меньшим за количество неизвестных. Остается найти базисные... Также отреставрировать сортировку...

Вопросы:
1) может кто знает, почему стопорится сортировка?
2) как исходя из общих, найти базисные решения?

Автор: comcon1 27.1.2010, 01:15

базисные ты уже нашел. Базисные - это общие при значениях свободных переменных = 0, вроде бы.

Автор: Лешкин 27.1.2010, 01:23

если взять такую матрицу:
3х5
    1 -1 3 1 4
    2 3 -1 -1 6
    1 -6 10 4 6

то базисных решений здесь будет 6.
Находятся они путем замены поочередно неизвестных нулями. При этом количество заменяемых на ноль (вроде бы) равно рангу матрицы. сейчас мучаю это решение на с++.

Добавлено через 4 минуты и 19 секунд
для предыдущей матрицы базисные решения:
Х1=(9, 2, 0, 0)
Х2=(0, 11, 9, 0)
Х3=(11, 0, -2, 0)
Х4=(10, 0, 0, 5)
Х5=(0, 20, 0, -45)
Х6=(0, 0, 20, 55)

Добавлено через 6 минут и 7 секунд
А как на счет сортировки? Почему вектор ругается?

Автор: comcon1 27.1.2010, 02:08

Подожди.
(С) Базисным решением системой уравнений называется такое решение при котором свободные переменные равны нулю.

Автор: Лешкин 27.1.2010, 07:41

Возможно... Но у меня в методичке в указаниях лабы решен примерчик (тот, который выше, с шестью базисными). Судя по этому решению, нужно заменять все пары по очереди (тоесть, комбинация с m по n). "От руки" такие решения я научился находить (так же как и в методичке). Задача стоит научить программу это делать.