Назад Зміст Вперед

Алгоритми розв’язання n систем лінійних рівнянь з m невідомими

Вступ

Системи лінійних рівнянь широко застосовуються у математиці та техніці. Мета — знайти значення m невідомих за n рівняннями.

Основні алгоритми

  1. Метод Гаусса

    Зведення системи до трикутного вигляду з подальшим зворотним ходом.

    1. Коли застосовується?

    Метод Гаусса (прямий хід + зворотній хід) використовується для розв'язання систем лінійних рівнянь будь-якого розміру, якщо матриця не вироджена.

    2. Алгоритм Гаусса (покроково)

    1. Прямий хід: перетворення матриці до трикутного вигляду (елімінація).
    2. Зворотній хід: знаходження невідомих починаючи з останнього рівняння.

    3. Приклад (2x2)

    Система:

    2x + 3y = 8
    -1x + 2y = 3

    Множимо 1-е рівняння на 0.5 та додаємо до 2-го, щоб обнулити x у 2-му рівнянні.

    Отримаємо трикутну систему, далі розв'язуємо зворотнім ходом.

    4. Реалізація C++ (з коментарями)

    
#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

int main() {
    int n;
    cout << "Введіть кількість рівнянь n: ";
    cin >> n;

    vector<vector<double>> a(n, vector<double>(n+1)); // розширена матриця (A|b)

    cout << "Введіть коефіцієнти та вільні члени (A|b):\n";
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= n; j++) {
            cin >> a[i][j];
        }
    }

    // Прямий хід (елімінація Гаусса)
    for(int i = 0; i < n; i++) {
        // Пошук головного елемента
        double maxEl = abs(a[i][i]);
        int maxRow = i;
        for(int k = i+1; k <n; k++) {
            if(abs(a[k][i]) > maxEl) {
                maxEl = abs(a[k][i]);
                maxRow = k;
            }
        }
        // Обмін рядків
        swap(a[maxRow], a[i]);

        // Приведення під головною діагоналлю до нулів
        for(int k = i+1; k < n; k++) {
            double c = -a[k][i] / a[i][i];
            for(int j = i; j <= n; j++) {
                if(i == j) {
                    a[k][j] = 0;
                } else {
                    a[k][j] += c * a[i][j];
                }
            }
        }
    }

    // Зворотній хід (обчислення x)
    vector<double> x(n);
    for(int i = n-1; i >= 0; i--) {
        x[i] = a[i][n] / a[i][i];
        for(int k = i-1; k >= 0; k--) {
            a[k][n] -= a[k][i] * x[i];
        }
    }

    // Вивід розв'язку
    cout << "Розв'язок системи:\n";
    for(int i = 0; i < n; i++) {
        cout << "x" << i+1 << " = " << x[i] << endl;
    }

    return 0;
}

    ✅ Коментарі до коду:
    – swap() використовується для вибору головного елемента (стійкість).
    – Прямий хід обнуляє нижню частину матриці.
    – Зворотній хід послідовно знаходить невідомі.

    5. Особливості методу

    • Прямий метод, завжди дає точний результат (за умови det(A) ≠ 0).
    • Широко використовується у чисельних методах.
    
#include <iostream> // бібліотека для вводу/виводу
#include <vector>     // бібліотека для роботи з векторами (динамічними масивами)
#include <cstdlib>    // бібліотека для функцій rand(), srand()
#include <ctime>      // бібліотека для ініціалізації генератора випадкових чисел
#include <cmath>      // бібліотека математичних функцій

using namespace std;

// Типи для зручності
typedef vector<double> Vector;   // Вектор дійсних чисел
typedef vector<Vector> Matrix;   // Матриця (вектор векторів)

// Функція ініціалізації випадковими числами
// n – кількість рядків, m – кількість стовпців
void initRandom(Matrix &mat, int n, int m) {
    for(int i = 0; i < n; i++) {          // цикл по рядках
        for(int j = 0; j < m; j++) {      // цикл по стовпцях
            mat[i][j] = rand() % 10 + 1;  // випадкові цілі від 1 до 10
        }
    }
}

// Функція виводу матриці на екран
void printMatrix(const Matrix &mat) {
    for(const auto &row : mat) {        // перебір рядків
        for(auto val : row) {           // перебір елементів у рядку
            cout << val << "\t";        // виведення числа з табуляцією
        }
        cout << endl;                   // перехід на новий рядок
    }
}
int main() {
    srand(time(0)); // ініціалізація генератора випадкових чисел
    int n;
    cout << "Введіть кількість рівнянь n: ";
    cin >> n;

    // Розширена матриця (A | b): n рядків, n+1 стовпців
    Matrix A(n, Vector(n+1));
    initRandom(A, n, n+1);
    cout << "Розширена матриця (A|b):" <<endl;
    printMatrix(A);

    // Прямий хід (елімінація Гаусса)
    for(int i = 0; i < n; i++) {
        // Пошук головного елемента у стовпці i
        double maxEl = abs(A[i][i]);
        int maxRow = i;
        for(int k = i+1; k < n; k++) {
            if(abs(A[k][i]) >= maxEl) {
                maxEl = abs(A[k][i]);
                maxRow = k;
            }
        }

        swap(A[maxRow], A[i]); // Обмін рядків

        // Приведення під головною діагоналлю до нулів
        for(int k = i+1; k < n; k++) {
            double c = -A[k][i] / A[i][i];
            for(int j = i; j <= n; j++) {
                if(j == i) {
                    A[k][j] = 0;
                } else {
                    A[k][j] += c * A[i][j];
                }
            }
        }
    }
}

    // Зворотній хід (обчислення x)
Vector x(n);
for(int i = n-1; i >= 0; i--) {
    x[i] = A[i][n] / A[i][i];
    for(int k = i-1; k >= 0; k--) {
        A[k][n] -= A[k][i] * x[i];
    }
}

// Вивід результату
cout << "Розв'язок системи:" << endl;
for(int i = 0; i < n; i++) {
    cout << "x" << i+1 << " = " << x[i] << endl;
}
return 0;
 
    
 
    Результат:

  2. Метод Крамера

    Використання визначників для знаходження розв’язків (застосовний лише для квадратних систем з ненульовим визначником).

    1. Коли застосовується?

    Метод Крамера використовується для розв'язання систем лінійних рівнянь, де кількість рівнянь дорівнює кількості невідомих, і визначник матриці коефіцієнтів det(A) ≠ 0.

    2. Формула Крамера

    Для кожної змінної xi:

    xi = det(Ai) / det(A),

    де Ai – матриця, отримана заміною i-го стовпця матриці A вектором вільних членів b.

    3. Алгоритм (покроково)

    1. Скласти матрицю коефіцієнтів A та вектор b.
    2. Обчислити det(A). Якщо det(A) = 0, система не має єдиного розв'язку.
    3. Для кожної змінної xi:
      • замінити i-й стовпець A на b та отримати Ai;
      • обчислити det(Ai);
      • знайти xi = det(Ai) / det(A).

    4. Приклад (2x2)

    Система:

    2x + 3y = 8
    -1x + 2y = 3

    det(A) = (2)(2) - (-1)(3) = 4 + 3 = 7

    x = det(Ax)/det(A) = 7/7 = 1
    y = det(Ay)/det(A) = 14/7 = 2

    5. Реалізація C++ 

    
#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<double>> Matrix;
typedef vector<double> Vector;

// Функція для обчислення визначника матриці (рекурсивно)
double determinant(const Matrix& mat) {
    int n = mat.size();
    if (n == 1) return mat[0][0]; // базовий випадок для 1x1

    double det = 0;
    for (int p = 0; p < n; p++) {
        Matrix subMat(n - 1, Vector(n - 1)); // підматриця без 1-го рядка та p-го стовпця
        for (int i = 1; i < n; i++) {
            int colIndex = 0;
            for (int j = 0; j < n; j++) {
                if (j == p) continue;
                subMat[i - 1][colIndex] = mat[i][j];
                colIndex++;
            }
        }
        det += mat[0][p] * determinant(subMat) * (p % 2 == 0 ? 1 : -1); // розклад за Лапласом
    }
    return det;
}

// Функція заміни i-го стовпця матриці на вектор b
Matrix replaceColumn(const Matrix& mat, const Vector& b, int col) {
    Matrix res = mat;
    for (int i = 0; i < mat.size(); i++) {
        res[i][col] = b[i];
    }
    return res;
}

int main() {
    int n;
    cout << "Введіть розмірність системи n: ";
    cin >> n;

    Matrix A(n, Vector(n));
    Vector b(n);

    cout << "Введіть коефіцієнти матриці A пострічково:\n";
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> A[i][j];

    cout << "Введіть вільні члени b:\n";
    for (int i = 0; i < n; i++)
        cin >> b[i];

    double detA = determinant(A);
    if (detA == 0) {
        cout << "Система не має єдиного розв'язку (det = 0)." << endl;
        return 0;
    }

    Vector x(n);
    for (int i = 0; i < n; i++) {
        Matrix Ai = replaceColumn(A, b, i);
        double detAi = determinant(Ai);
        x[i] = detAi / detA;
    }

    cout << "Розв'язок системи:\n";
    for (int i = 0; i < n; i++)
        cout << "x" << i+1 << " = " << x[i] << endl;

    return 0;
}
 
    #include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

typedef vector<double> Vector;
typedef vector<Vector> Matrix;

// Ініціалізація матриці випадковими значеннями
void initRandom(Matrix &mat, int n, int m) {
    for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
    mat[i][j] = rand() % 10 + 1;
}

// Ініціалізація вектора випадковими значеннями
void initRandom(Vector &vec, int n) {
    for(int i = 0; i < n; i++)
    vec[i] = rand() % 10 + 1;
}

// Вивід матриці
void printMatrix(const Matrix &mat) {
    for(const auto &row : mat) {
    for(auto val : row) {
    cout << val << "\t";
    }
    cout << endl;
}
    // Вивід вектора
void printVector(const Vector &v) {
    for(auto val : v) {
        cout << val << " ";
    }
    cout << endl;
}

// Рекурсивний розрахунок визначника
double determinant(const Matrix& mat) {
    int n = mat.size();
    if (n == 1) return mat[0][0];

    double det = 0;
    for (int p = 0; p < n; p++) {
        Matrix subMat(n - 1, Vector(n - 1));
        for (int i = 1; i < n; i++) {
            int colIndex = 0;
            for (int j = 0; j < n; j++) {
                if (j == p) continue;
                subMat[i - 1][colIndex++] = mat[i][j];
            }
        }
        det += mat[0][p] * determinant(subMat) * ((p % 2 == 0) ? 1 : -1);
    }
    return det;
}
    // Замінити стовпець матриці на вектор
Matrix replaceColumn(const Matrix& mat, const Vector& b, int col) {
    Matrix res = mat;
    for (int i = 0; i < mat.size(); i++) res[i][col] = b[i];
    return res;
}

int main() {
    srand(time(0)); // Ініціалізація генератора випадкових чисел
    int n;
    cout << "Введіть розмірність системи n: "; cin >> n;
    Matrix A(n, Vector(n)); Vector b(n);
    // Автоматичне заповнення
    initRandom(A, n, n); initRandom(b, n);
    cout << "\nЗгенерована матриця A:\n"; printMatrix(A);
    cout << "\nЗгенерований вектор b:\n"; printVector(b);
    
    double detA = determinant(A);
    cout << "\nВизначник det(A) = " << detA << endl;
    
    if (detA == 0) {
        cout << "Система не має єдиного розв'язку (det = 0)." << endl;
        return 0;
    }
    
    Vector x(n);
    for (int i = 0; i < n; i++) {
        Matrix Ai = replaceColumn(A, b, i);
        double detAi = determinant(Ai);
        cout << "Визначник det(A" << i+1 << ") = " << detAi << endl;
        x[i] = detAi / detA;
    }
    
    cout << "\nРозв'язок системи:\n";
    for (int i = 0; i < n; i++)
        cout << "x" << i+1 << " = " << x[i] << endl;
    
    return 0;
}

    Результат:

Висновки

Вибір методу залежить від розміру системи, структури матриці коефіцієнтів і необхідної точності результату.

Назад Зміст Вперед