Тема: Яким чином добути корені матриці?

Є код, який зводить елементи під головною діагоналлю до 0. Працює не завжди, але для наочності підійде:

#include <stdio.h>
#include <math.h>

main()
{
    int i, j, k, l, m, col, row;
    float a;
    col = row = 0;

    printf("Gauss Elimination Method to Solve Linear Equations\n");
        printf("   01   02   03   .. =  C\n");
        printf("01 aa + ab + ac + .. = b1\n");
        printf("02 ba + bb + bc + .. = b2\n");
        printf("03 ca + cb + cc + .. = b3\n");
        printf("   .. + .. + .. + .. = ..\n");
        printf(" R tR + tR + tR + .. = tC\n\n");
        printf("\nInput number of Coloumns:\n");
        scanf("%i", &col);
        printf("\nInput number of Rows:\n");
        scanf("%i", &row);

    float matrix[row][col], root[col-1];

    printf("\nInput matrix elements:\n");
    for(i = 0; i < row; i++)
        for(j = 0; j < col; j++)
            scanf("%4f", &matrix[i][j]);
    for(i = 0; i < row; i++){
        for(j = 0; j < col; j++)
            printf("%.3f ", matrix[i][j]);
        putchar('\n');
    }
    printf("\nStep 1: Leading all members under main diagonal to null\n\n");
        
    for(i = 1; i < row; i++){
        for(j = 0; j < i; j++){
            a = - (double) (matrix[j][j] / matrix[i][j]);
            for(k = 0; k < col; k++){
                matrix[i][k] = matrix[i][k] * a + matrix[j][k];
            }
            matrix[i][j] = fabs(matrix[i][j]);
            for(l = 0; l < row; l++){
                for(m = 0; m < col; m++)
                printf("%.3f ", matrix[l][m]);
                putchar('\n');
            }
            putchar('\n');
        }
    }


    printf("%f", a);
    return 0;
}

Якщо матриця нормальна, то до елементи нижче головної діагоналі будуть зведені до нуля правильно.
Залишилось тільки придумати як добути корені.
Проблема в тому що матриця універсальна, тому і алгоритм для кожного розміру буде різний, наприклад:

2x3
[00]    x = ([02] - 00000 - [01]y)/[00]
[11]    y = ([12] - [10]x - 00000)/[11]

3x4
[00]    x = ([03] - 00000 - [01]y - [02]z)/[00]
[11]    y = ([13] - [10]x - 00000 - [12]z)/[11]   
[22]    z = ([23] - [20]x - [21]y - 00000)/[22]

4x5
[00]    x = ([04] - 00000 - [11]y - [12]z - [13]w)/[00]
[11]    y = ([14] - [10]x - 00000 - [12]z - [13]w)/[11]   
[22]    z = ([24] - [20]x - [21]y - 00000 - [23]w)/[22]
[33]    w = ([34] - [30]x - [31]y - [32]z - 00000)/[33]

Можна як варіант сказати що максимальний розмір рядків і стовпчиків там 10x10, написати довгий алгоритм для знаходження 10 коренів, а при підстановці зайві просто будуть дорівнювати нулю, вивести можна буде лише ті що будуть дорівнювати кількості рядків.
Але може є ліпші варіанти? Які ідеї?

Білий Лунь

2

Re: Яким чином добути корені матриці?

Що Ви маєте на увазі під "коренями матриці"? Розв'язок системи лінійних рівнянь?
Якщо так, то, взагалі кажучи, може бути кілька варіантів:
а) один розв'язок;
б) безліч розв'язків;
в) жодного розв'язку.
Для розв'язання можна використати метод Гауса: http://uk.wikipedia.org/wiki/%D0%9C%D0% … 0%BD%D0%B0

Подякували: Ярослав1

3

Re: Яким чином добути корені матриці?

Тут він і задіяний, в цитатах вище я показав яким чином має відбуватись зворотній хід, але описати його програмно не так просто як я думав, у мене уже є пара ідей, але мені цікаво які є іще ідеї. Я не прошу давати код просто метод.
Той який я зараз намагаюсь розробити - такий:
Розглянемо останню цитату:

4x5
[00]    x = ([04] - 00000 - [11]y - [12]z - [13]w)/[00]
[11]    y = ([14] - [10]x - 00000 - [12]z - [13]w)/[11]   
[22]    z = ([24] - [20]x - [21]y - 00000 - [23]w)/[22]
[33]    w = ([34] - [30]x - [31]y - [32]z - 00000)/[33]

на цей момент [30], [31], [32] члени будуть дорівнювати 0. [34] [33] відомі
Проблема в тому що потрібно реалізувати такий метод для універсальної матриці.
Ось що я придумав
Так як не відомо скільки буде коренів (до того моменту як не буде введена кількість рядків і стовпчиків), то необхідно створити масив для коренів, я назвав його root[col-1] так як коренів буде завжди на 1 менше ніж стовпчиків або іще можна root[row], але це не завжди буде коректно.
Зворотній хід починається із останнього рядку, тому потрібно створити цикл, який буде починати своє проходження із останнього рядку і до 0 (першого рядку)
Маючи значення рядка над яким ми працюємо можна починати визначати корінь
розглянемо корінь w із цього прикладу root[3]
Спочатку будемо рахувати те що в дужках
Визначимо root[3] як елемент [34]
Віднімання відбувається 4 рази, тому потрібно створити цикл який буде віднімати таку кількість разів і пропускати 1 віднімання (позначене 0000)
Створимо цей цикл і введемо умову if
Після цього необхідно виконати ділення, це можна зробити в головному циклу після виконання субциклу.
Десь так, я якраз зараз працюю над цим методом ось код якщо кому цікаво:

i = col-2;
    j = 0;
    k = row;
    l = col-1;
    printf("i = %d\nj = %d\nk = %d\nl = %d\n", i, j, k, l);
    while(i>=0){
        root[i] = matrix[i][l];
        printf("\nSTART:root[%d] = matrix[%d][%d] = %f\n", i, i, l, root[i]);
        while(j < col-1){
            if(j != k)
            root[i] = root[i] - matrix[i][j];
            printf("\nSUBCYCLE:root[%d] = root[%d] - matrix[%d][%d] = %f, j = %d\n", i, i, i, j, root[i], j);
            j++;
        }
        root[i] = root[i] / matrix[k][k];
        printf("\nPREFINISH:root[%d] = %f\n k = %d\n", i, root[i], k);
        k--;
        j=0;        
        i--;
        printf("\nFINISH:i = %d, j = %d, k = %d\n", i, j, k);
    }
    for(i = 0; i<row; i++)    printf("\nAnswer #%d: %f\n", i, root[i]);
Білий Лунь

4

Re: Яким чином добути корені матриці?

Раджу все ж спочатку почитати теорію. Бо написане все дуже заплутане, використовується незвична термінологія.
До того, що я зрозумів такі зауваження:
1. Не робиться перевірка, чи діагональний елемент рівний нулю. Якщо він рівний нулю, то треба міняти рядки місцями.
2. При прямому ході робіть діагональні елементи рівними одиниці. Це значно спростить розрахунки.
3. Масив root в принципі не потрібний. Після зворотного ходу розв'язком буде останній стовпець матриці (можливо із протилежним знаком, дивлячись як задано в умові задачі). Це, звичайно, якщо матриця невироджена.
4. Додавайте до коду коментарі.

Подякували: Ярослав1

5 Востаннє редагувалося Ярослав (24.11.2012 16:48:13)

Re: Яким чином добути корені матриці?

#include <stdio.h>
#include <math.h>

main()
{
    int i, j, k, l, m, col, row;
    float a;
    col = row = 0;

    printf("Gauss Elimination Method to Solve Linear Equations\n");
        printf("   01   02   03   .. =  C\n");
        printf("01 aa + ab + ac + .. = b1\n");
        printf("02 ba + bb + bc + .. = b2\n");
        printf("03 ca + cb + cc + .. = b3\n");
        printf("   .. + .. + .. + .. = ..\n");
        printf(" R tR + tR + tR + .. = tC\n\n");
        printf("\nInput number of Coloumns:\n");
        scanf("%i", &col);
        printf("\nInput number of Rows:\n");
        scanf("%i", &row);

    float matrix[row][col], root[col-1];
    for(i = 0; i < col-1; i++)
        root[i] = 0;

    printf("\nInput matrix elements:\n");
    for(i = 0; i < row; i++)
        for(j = 0; j < col; j++)
            scanf("%4f", &matrix[i][j]);
    for(i = 0; i < row; i++){
        for(j = 0; j < col; j++)
            printf("%.3f ", matrix[i][j]);
        putchar('\n');
    }
    printf("\nStep 1: Leading all members under main diagonal to null\n\n");
    for(i = 1; i < row; i++){
        for(j = 0; j < i; j++){
            a = - (double) (matrix[j][j] / matrix[i][j]);
            for(k = 0; k < col; k++){
                matrix[i][k] = matrix[i][k] * a + matrix[j][k];
            }
            for(k = 0; k <= j; k++)
        matrix[i][k] = fabs(matrix[i][k]);
            for(l = 0; l < row; l++){
                for(m = 0; m < col; m++)
                printf("%.3f ", matrix[l][m]);
                putchar('\n');
            }
            putchar('\n');
        }
    }

i = row - 1;  j = 0;  k = row - 1;  l = 2;
printf("i = %d\nj = %d\nk = %d\nl = %d\n", i, j, k, l);

while(i >= 0){
    root[i] = matrix[i][row];
        printf("\nSTART:root[%d] = matrix[%d][%d] = %f\n", i, i, row, root[i]);
    for(j = 0; j < row; j++){
        if(j != k){
        root[i] = root[i] - matrix[i][j] * root[j];
        printf("\nSUBCYCLE:root[%d] = root[%d] - matrix[%d][%d] * root[%d] = %f, j = %d\n", i, i, i, j, j, root[i], j);
        }
    }
    root[i] = root[i] / matrix[i][i];
    printf("\nPREFINISH:root[%d] = root[%d] / matrix[%d][%d] = %f\n k = %d\n", i, i, i, i, root[i], k);
    k--;
    i--;
}
    return 0;
}

Вирішує рівняння виду:
7x + 2y +1z = 5
5x + 2y +4z = 8
6x + 3y +2z = 1

Білий Лунь

6

Re: Яким чином добути корені матриці?

yooll написав:

Раджу все ж спочатку почитати теорію. Бо написане все дуже заплутане, використовується незвична термінологія.
До того, що я зрозумів такі зауваження:
1. Не робиться перевірка, чи діагональний елемент рівний нулю. Якщо він рівний нулю, то треба міняти рядки місцями.
2. При прямому ході робіть діагональні елементи рівними одиниці. Це значно спростить розрахунки.
3. Масив root в принципі не потрібний. Після зворотного ходу розв'язком буде останній стовпець матриці (можливо із протилежним знаком, дивлячись як задано в умові задачі). Це, звичайно, якщо матриця невироджена.
4. Додавайте до коду коментарі.

Дуже дякую! Я використовую в цій програмі просто метод Гауса.
Зауваженя прийняв до уваги.
Програма іще не повністю готова, я тільки нещодавно почав вчити програмування, тому не судіть строго, але до ваших зауважень прислухаюсь.

Білий Лунь

7 Востаннє редагувалося Ярослав (24.11.2012 22:25:44)

Re: Яким чином добути корені матриці?

Враховуючи деякі із зауважень yooll

#include <stdio.h>
#include <math.h>

main()
{
    int i, j, k, l, m, col, row;
    float a;
    col = row = 0;

    printf("Gauss Elimination Method to Solve Linear Equations\n");
        printf("   01   02   03   .. =  C\n");
        printf("01 aa + ab + ac + .. = b1\n");
        printf("02 ba + bb + bc + .. = b2\n");
        printf("03 ca + cb + cc + .. = b3\n");
        printf("   .. + .. + .. + .. = ..\n");
        printf(" R tR + tR + tR + .. = tC\n\n");
        printf("\nInput number of Coloumns:\n");
        scanf("%i", &col);
        printf("\nInput number of Rows:\n");
        scanf("%i", &row);

    float matrix[row][col], root[col-1], temp[col];
    for(i = 0; i < col-1; i++)
        root[i] = 0;

    printf("\nInput matrix elements:\n");
    for(i = 0; i < row; i++)
        for(j = 0; j < col; j++)
            scanf("%4f", &matrix[i][j]);
    for(i = 0; i < row; i++){
        for(j = 0; j < col; j++)
            printf("%.3f ", matrix[i][j]);
        putchar('\n');
    }
    /* Якщо 1-ий член матриці 0 - міняємо 1-ий і 2-ий рядки місцями */
    /* Якщо досі 0 - міняємо 1-ий і 3-ий рядки місцями              */ 
    printf("\nStep 1: Swaping rows\n\n");
    j = 0;
    while(matrix[0][0] == 0 && j<=row){
        j++;
        for(i=0; i<col; i++){
            temp[i] = matrix[0][i];
            matrix[0][i] = matrix[j][i];
            matrix[j][i] = temp[i];
        }
    }
    for(i = 0; i < row; i++){
        for(j = 0; j < col; j++)
            printf("%.3f ", matrix[i][j]);
        putchar('\n');
    }

    /* Визначаємо a як відношення члену попереднього рядка або рядка перед попереднім */
    /* із оберненим знаком. Використовуємо метод Гауса, щоб звести члени під головною */
    /* діагоняллю до нуля. Функція fabs(); приводить елементи -0.0 до 0.0             */
    printf("\nStep 2: Leading all members under main diagonal to null\n\n");
    for(i = 1; i < row; i++){
        for(j = 0; j < i; j++){
            if(matrix[i][j] != 0){
                a = - (double) (matrix[j][j] / matrix[i][j]);
                for(k = 0; k < col; k++){
                    matrix[i][k] = matrix[i][k] * a + matrix[j][k];
                }
                for(k = 0; k <= j; k++){
                    matrix[i][k] = fabs(matrix[i][k]);
                }
            }
            for(l = 0; l < row; l++){
                for(m = 0; m < col; m++)
                printf("%.3f ", matrix[l][m]);
                putchar('\n');
            }
            putchar('\n');
        }
    }

    /* Зворотній хід */
    printf("\nStep 3: Finding the roots of the equation\n");
    i = row - 1;  j = 0;  k = row - 1;  l = 2;
    printf("i = %d\nj = %d\nk = %d\nl = %d\n", i, j, k, l);

    while(i >= 0){
        root[i] = matrix[i][row];
            printf("\nSTART:root[%d] = matrix[%d][%d] = %f\n", i, i, row, root[i]);
        for(j = 0; j < row; j++){
            if(j != k){
            root[i] = root[i] - matrix[i][j] * root[j];
            printf("\nSUBCYCLE:root[%d] = root[%d] - matrix[%d][%d] * root[%d] = %f, j = %d\n", i, i, i, j, j, root[i], j);
            }
        }
        root[i] = root[i] / matrix[i][i];
        printf("\nPREFINISH:root[%d] = root[%d] / matrix[%d][%d] = %f\n k = %d\n", i, i, i, i, root[i], k);
        k--;
        i--;
    }

    /*Вивід відповідей*/
    putchar('\n');
    for(i = 0; i<col-1; i++)    printf("Root #%d: %.3f\n", i+1, root[i]);
    return 0;
}
Білий Лунь

8

Re: Яким чином добути корені матриці?

    
j = 0;
while(matrix[0][0] == 0 && j<=row){
      j++;
      for(i=0; i<col; i++){
          temp[i] = matrix[0][i];
          matrix[0][i] = matrix[j][i];
          matrix[j][i] = temp[i];
      }
}

Формально ви досягнете того, що matrix[0][0] буде ненульовим. Але:
1. Якщо перший ненульовий елемент буде, наприклад, в 5-му рядку, то ви зробите 4 обміни (1 і 2, 1 і 3, 1 і 4, 1 і 5) замість одного (1 і 5). А це все час роботи програми.
2. При цьому ще й перетасуються всі рядки, що ускладнить тестування (зручно, наприклад, спочатку розв'язати приклад на папері, іншою програмою або взяти вже розв'язаний приклад і порівнювати результат покроково).
3. Цю ж дію доведеться виконувати ще row разів. На наступній ітерації, якщо matrix[1][1]==0, то потрібно міняти другий рядок з  першим з тих, в якому  matrix[k][1]!=0 (k=2..row). І т.д.

Тому краще усунути недоліки і винести цю операцію в окремий метод (функцію).

Подякували: Ярослав1

9 Востаннє редагувалося Ярослав (24.11.2012 23:10:48)

Re: Яким чином добути корені матриці?

2. При прямому ході робіть діагональні елементи рівними одиниці. Це значно спростить розрахунки.

Поясніть яким чином це можна зробити.
Був би вдячний тут за допомогу кодом або якісь підказки.

Білий Лунь

10

Re: Яким чином добути корені матриці?

keithfay написав:

2. При прямому ході робіть діагональні елементи рівними одиниці. Це значно спростить розрахунки.

Поясніть яким чином це можна зробити.
Був би вдячний тут за допомогу кодом або якісь підказки.

Ділити кожен елемент рядка на діагональний елемент.

//i-номер рядка в ітерації
for(j=i;j<col;j++)
{
   matrix[i][j]=matrix[i][j]/matrix[i][i];
}
Подякували: Ярослав1