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

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

Форум программистов > Алгоритмы > решение системы линейных уравнений

Автор: Ivanich 22.3.2007, 22:43

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

Автор: skyboy 22.3.2007, 23:01

метод Крамера
метод обратной матрицы
метод Гаусса
это то, что пришло в голову сходу. а вообще, я бы не гнушался воспользоваться поиском в Wikipedia(http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D1%85_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85_%D1%83%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B9)

Автор: cardinal 23.3.2007, 00:07

Вручную больше не решаю... smile

А вообще, если тривиальная система, то можно и без методов, а просто "подставленим одного в другое"...

Автор: Ivanich 23.3.2007, 14:32

Цитата(cardinal @ 23.3.2007, 00:07)

Вручную больше не решаю... smile

вот и я не хочу, мне надо написать программу. Писать буду на С++, теорию уже почитал и знаю что метод Гаусса и Крамера для этого мне не подойдут. Как я понял мне надо использовать итерационный метод(уже разобрался с методом простых итераций, но он не подходит, так как решать системы мне надо однородные). Подскажите начинающему smile

Автор: skyboy 23.3.2007, 18:28

Ivanich, т.е. ссылки на список из 9 методов - слишком мало?! smile

Цитата

Прямые методы

    * Метод Гаусса
    * Метод Жордана-Гаусса
    * Метод Крамера
    * Матричный метод
    * Метод прогонки - Для трехдиагональных матриц

Приближенные методы

    * Метод Якоби (метод итераций)
    * Метод Зейделя
    * Метод релаксации
    * Многосеточный метод

Автор: SoWa 23.3.2007, 19:39

Цитата(Ivanich @ 23.3.2007, 14:32

)

Как я понял мне надо использовать итерационный метод(уже разобрался с методом простых итераций, но он не подходит, так как решать системы мне надо однородные). Подскажите начинающему

Ой-ли? А тот же метод Жордано-Гаусса не подходит? Не верю!
Чтобы на Cи такую программу написать, много времени не надо.

Автор: sergejzr 23.3.2007, 19:44

Гаусс - молодец был smile

И чем он не подходит?

Автор: Ivanich 24.3.2007, 12:07

Цитата

И чем он не подходит?

Так метод Гаусса же дает серьезную погрешность, в отличии от методов итерации при вычисление СЛАУ на ЭВМ. Или я ошибаюсь?

Автор: sergejzr 24.3.2007, 13:30

Смотря как вычисляешь. если сохранять дроби, то погрешности не будет.

Автор: esperanto 24.3.2007, 15:35

Цитата(Ivanich @ 24.3.2007, 12:07)

Цитата

И чем он не подходит?

Ошибаешься. Есть системы для которых гаус вообще не дает погрешности. Есть системы для которых итеративные методы не сходятся.

Автор: Joss 25.3.2007, 22:14

Цитата

Совсем забыл написать, что СЛАУ мне надо решеть однородные.

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

Автор: skyboy 25.3.2007, 22:50

Цитата(Joss @ 25.3.2007, 21:14

)

Во втором случае описанные методы вообще неприменимы

почему же "неприменимы"? например, метод Крамера.
если "общий" определитель равен нулю и все "частные" определители тоже равны 0, то решений - бесконечное множество.
если "общий" определитель равен нулю и хотя бі один частній определитель не равен нулю, то решений нет; система несовместна
если "общий" определитель не равен нулю, то решение есть и оно единственно.
------------
единственное базовое ограничение для (известных мне) численных методов: количество переменных == количество уравнений в системе.

Автор: Artemios 26.3.2007, 00:33

Ээ...
Сведение матрицы СЛАУ к ступенчатой форме хоть Гауссом, хоть итерационным каким методом...
В случае однородности СЛАУ некоторые строки -- нулевые; соответствующие этим строкам переменные выбираем в качестве свободных переменных, остальные строки дадут зависимости несвободных от свободных.

Автор: Ivanich 26.3.2007, 16:39

Цитата

если "общий" определитель равен нулю и все "частные" определители тоже равны 0, то решений - бесконечное множество.

если так, то тогда как мне найти хотя бы одно нетривиальное решение?

Цитата

если "общий" определитель не равен нулю, то решение есть и оно единственно.

и это тривиальное решение!

Цитата

Сведение матрицы СЛАУ к ступенчатой форме хоть Гауссом, хоть итерационным каким методом...

а что это за итерационные методы приведения матрицы СЛАУ к ступенчатой форме? (я пока знаю только про метод Гаусса)

Цитата

В случае однородности СЛАУ некоторые строки -- нулевые; соответствующие этим строкам переменные выбираем в качестве свободных переменных, остальные строки дадут зависимости несвободных от свободных.

если не трудно, можно пример(не совсем понял)

Автор: Artemios 26.3.2007, 18:18

Цитата(Ivanich @ 26.3.2007, 17:39

)

Ну да, немного попутал: в голове перемешалось с итерационными методами сведения матрицы (не СЛАУ) к треугольной/диагональной форме в задаче поиска собственных значений. Хотя, и те методы, в немного урезанном варианте, кажется, должны быть применимы: там же обнуляет элементы одно преобразование (строк например), а второе преобразование (столбцов) является компенсирующим для сохранения подобности матриц. А при решении СЛАУ подобности матриц не требуется, но требуется неизменность порядка столбцов, то есть компенсирующее преобразование можно опустить...

Цитата(Ivanich @ 26.3.2007, 17:39

)

Цитата
В случае однородности СЛАУ некоторые строки -- нулевые; соответствующие этим строкам переменные выбираем в качестве свободных переменных, остальные строки дадут зависимости несвободных от свободных.
если не трудно, можно пример(не совсем понял)

например получили такую треугольную матрицу:
1 1 1 0
0 1 0 1
0 0 0 0
0 0 0 0
Из последних 2-х уравнений -- x_3 и x_4 -- свободные переменные,
из 2-го сверху уравнения x_2 = -x_4,
из 1-го x_1 = -x_2 - x_3, а с учетом того, что по x_2 уже решено, то x_1 = x_4 - x_3.
Таким образом, решение системы -- 2-мерная плоскость в 4-мерном пространстве: {x_2 = -x_4, x_1 = x_4 - x_3}
А чтобы не гадать, по каким переменным уже разрешено, а по каким еще нет, лучше сразу приводить максимальный ненулевой минор матрицы к диагональному виду:
1 0 1 -1
0 1 0  1
0 0 0  0
0 0 0  0

Кстати,

Цитата(Ivanich @ 24.3.2007, 13:07

)

Цитата(sergejzr @ 24.3.2007, 14:30

)

Смотря как вычисляешь. если сохранять дроби, то погрешности не будет.

Так как писать собрался на C/C++ , ничего не может быть проще, чем скачать библиотеку на длинную арифметику: http://gmplib.org/, и проводить вычисления в дробях произвольной длины с абсолютной точностью.

Автор: Danza 24.12.2007, 21:47

Метод Гаусса на с++:

Код


float det(float [20][20], int);
//___________________________________________________________________
void iskl(float a[20][20], int k, int n) //cyda peredaetsya matrica temp
{
    int i, j;
    float r, b[40];

    r=a[k][k];
    for (j=k; j<n+1; j++) a[k][j]/=r;
    for (i=k+1; i<n; i++)
    {
        r=a[i][k];
        for(j=k; j<n+1; j++) a[i][j]-=a[k][j]*r;
    }
}
//____________________________________________________________________
int _tmain(int argc, _TCHAR* argv[])
{
    int i, j, n, k;
    float a[20][20], d[20][20], b[40], temp[20][20], t, intDet;
    char anyKey;
    //____sozdanie____
    ofstream outfile("matr1.txt");
    cout<<"VVedite razmernost yravneniya: ";
    cin >> n;
    cout<<endl;
    cout<<"Vvedite postro4no matricy:"<<endl;
    for (i=0; i<(n*n+n); i++)
    {
        cin >> t;
        outfile << t <<" ";
    }
    outfile.close();
    cout<<"Poly4ennaya matrica:"<<endl;
    //_____4tinie i pe4at_____
    fstream infile("matr1.txt");
    for (i=0; i<n; i++)        //bilo n+1
    {
    cout<<endl;
    for (j=0; j<n+1; j++)
    {
        infile >> t;
        temp[i][j]=t;
        cout<<t<<" ";
    }
    }
    //_____razbivaem matricy na matrice i vecto
    //matrica
    for (i=0; i<n; i++)
    for (j=0; j<n; j++)
        a[i][j]=temp[i][j];
    //vector
//    for (i=0; i<n; i++) 
//        b[i]=temp[i][n+1];
    //___proveryaem est li reweniya
    intDet=det(a, n);
    if (intDet==0) 
    {
        cout<<"Reweniya net. ";
        goto net;
    }
    else
    {
        cout<<"Sistema rewaema )) YRA ))"<<endl;
        cout<<"det= "<<intDet;
    }
    //____pryamoi xod_______
    cout<<"Treygolnii vid:"<<endl;
    for (i=0; i<n; i++) iskl(temp, i, n);
    for (i=0; i<n; i++)
    {
        cout<<endl;
        for (j=0; j<n+1; j++) cout<<temp[i][j]<<' ';
    }

    //________obratnii xod, t.e. rewenie sistemi
    cout<<"\n";
    for (i=0; i<n+1; i++){b[i]=temp[i][n]; cout<<b[i]<<" ";}
    cout<<"\n"<<"Rewenie SLAY:"<<endl;
    for (i=n; i>-1; i--)
    {
        b[i]/=temp[i][i];
        for (j=i+1; j<n; j++)    b[i]-=b[j]*temp[i][j];
    }
    for (i=0; i<n; i++) cout<<b[i]<<" ";
net:
    cout<<"\nPress anykey to exit.";
    cin>>anyKey;
    return 0;
}
//___________________________________________
float det(float b[20][20], int n)
{
    float x,s;
    int i,j,k;
    for (i=0; i<n-1; i++)
    for (k=i+1; k<n; k++)
    { 
        x=b[k][i]/b[i][i];
        for (j=i; j<n; j++) b[k][j]=b[k][j]-b[i][j]*x; //tyt perepolnenie (((
    }
    s=1;
    for (i=0; i<n; i++) s=s*b[i][i];
    return s;
}

Насколько помню, всё работает.
Можно ещё решать методом Якоби. Но что бы матрица была "решаема" необходимо диагональное преобладание. Могу скинуть код если надо.

Автор: Alleut 12.3.2008, 23:01

Объясните, плиз, как решать неоднородные системы итерационным методом Якоби?
В общем виде это записывается так:

Код


 x{k+1}=Cx{k} + d

Как выбирать x{0} (икс нулевое)?

Автор: cardinal 12.3.2008, 23:50

Пожалуйста, один топик - один вопрос.
Правила форума: http://forum.vingrad.ru/index.php?act=boardrules