Алгоритм
Метод Гаусса - классический метод решения системы линейных алгебраических уравнений (СЛАУ). Рассмотрим систему линейных уравнений с действительными постоянными коэффициентами
\begin{align*}
\left\{
\begin{array}{ccc}
a_{11} \cdot x_{1} + a_{12} \cdot x_{2} + & \cdots & + a_{1 n} \cdot x_{n}=y_{1} \\
a_{21} \cdot x_{1} + a_{22} \cdot x_{2} + & \cdots & + a_{2 n} \cdot x_{n}=y_{2} \\
& \cdots & \\
a_{n 1} \cdot x_{1} + a_{n 2} \cdot x_{2} + & \cdots & + a_{n n} \cdot x_{n}=y_{n}
\end{array}
\right.
\end{align*}
или в матричной форме
\begin{align*}
A x = y,
\end{align*}
где
\begin{align*}
A=\left(
\begin{array}{ccc}
a_{11} & \dots & a_{1 n} \\
& \dots & \\
a_{n 1} & \dots & a_{n n}
\end{array}
\right),
\quad x=\left(
\begin{array}{c}
x_{1} \\
\vdots \\
x_{n}
\end{array}
\right),
\quad y=\left(
\begin{array}{c}
y_{1} \\
\vdots \\
y_{m}
\end{array}
\right).
\end{align*}
Метод Гаусса решения системы линейных уравнений включает в себя 2 стадии:
- последовательное (прямое) исключение;
- обратная подстановка.
Последовательное исключение
Исключения Гаусса основаны на идее последовательного исключения переменных по одной до тех пор, пока не останется только одно уравнение с одной переменной в левой части. Затем это уравнение решается относительно единственной переменной. Таким образом, систему уравнений приводят к треугольной (ступенчатой) форме. Для этого среди элементов первого столбца матрицы выбирают ненулевой (а чаще максимальный) элемент и перемещают его на крайнее верхнее положение перестановкой строк. Затем нормируют все уравнения, разделив его на коэффициент ai1, где i– номер столбца.
\begin{align*}
\left\{
\begin{array}{ccc}
x_{1}+\frac{a_{12}}{a_{11}} \cdot x_{2} + & \cdots & + \frac{a_{1 n}}{a_{11}} \cdot x_{n}=\frac{y_{1}}{a_{11}} \\
x_{1}+\frac{a_{22}}{a_{21}} \cdot x_{2} + & \cdots & + \frac{a_{2 n}}{a_{21}} \cdot x_{n}=\frac{y_{2}}{a_{21}} \\
& \cdots & \\
x_{1}+\frac{a_{n 2}}{a_{n 1}} \cdot x_{2} + & \cdots & + \frac{a_{n n}}{a_{n 1}} \cdot x_{n}=\frac{y_{n}}{a_{n 1}}
\end{array}
\right.
\end{align*}
Затем вычитают получившуюся после перестановки первую строку из остальных строк:
\begin{align*}
\left\{
\begin{array}{r c r c r c l}
x_{1} & + & \frac{a_{12}}{a_{11}} \cdot x_{2} & + \cdots + & \frac{a_{1 n}}{a_{11}} \cdot x_{n} & = & \frac{y_{1}}{a_{11}} \\
0 & + & \left(\frac{a_{22}}{a_{21}}-\frac{a_{12}}{a_{11}}\right) \cdot x_{2} & + \cdots + & \left(\frac{a_{2 n}}{a_{21}}-\frac{a_{1 n}}{a_{11}}\right) \cdot x_{n} & = & \left(\frac{y_{2}}{a_{21}}-\frac{y_{1}}{a_{11}}\right) \\
&& & \cdots & \\
0 & + & \left(\frac{a_{n 2}}{a_{n 1}}-\frac{a_{12}}{a_{11}}\right) \cdot x_{2} & + \cdots + & \left(\frac{a_{n n}}{a_{n 1}}-\frac{a_{1 n}}{a_{11}}\right) \cdot x_{n} & = & \left(\frac{y_{n}}{a_{n 1}}-\frac{y_{1}}{a_{11}}\right)
\end{array}
\right.
\end{align*}
Получают новую систему уравнений, в которой заменены соответствующие коэффициенты.
\begin{align*}
\left\{
\begin{array}{r c r c r c r}
x_{1} & + & a_{12}^{\prime} \cdot x_{2} & + \cdots + & a_{1 n}^{\prime} \cdot x_{n} & = & y_{1}^{\prime} \\
0 & + & a_{22}^{\prime} \cdot x_{2} & + \cdots + & a_{2 n}^{\prime} \cdot x_{n} & = & y_{2}^{\prime} \\
&& & \cdots & \\
0 & + & a_{n 2}^{\prime} \cdot x_{2} & + \cdots + & a_{n n}^{\prime} \cdot x_{n} & = & y_{n}^{\prime}
\end{array}
\right.
\end{align*}
После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают указанный процесс для всех последующих уравнений пока не останется уравнение с одной неизвестной:
\begin{align*}
\left\{
\begin{array}{r c r c r c r c r}
x_{1} & + & a_{12}^{\prime} \cdot x_{2} & + & a_{13}^{\prime} \cdot x_{3} & + \cdots + & a_{1 n}^{\prime} \cdot x_{n} & = & y_{1}^{\prime} \\
0 & + & x_{2} & + & a_{23}^{\prime \prime} \cdot x_{3} & + \cdots + & a_{2 n}^{\prime \prime} \cdot x_{n} & = & y_{2}^{\prime \prime} \\
0 & + & 0 & + & x_{3} & + \cdots + & a_{3 n}^{\prime \prime \prime} \cdot x_{n} & = & y_{3}^{\prime \prime \prime} \\
&& && & \cdots & \\
0 & + & 0 & + & 0 & + \cdots + & x_{n} & = & y_{n}^{n \prime}
\end{array}
\right.
\end{align*}
Обратная подстановка
Обратная подстановка предполагает подстановку полученного на предыдущем шаге значения переменной \(xn\) в предыдущие уравнения:
\begin{align*}
\begin{array}{rcl}
x_{n-1} & = & y_{n-1}^{(n-1)^{\prime}}-a_{(n-1) n}^{(n-1) \prime} \cdot x_{n} \\
x_{n-2}+a_{(n-2)(n-1)}^{(n-2) \prime} \cdot x_{n-1} & = & y_{n-2}^{(n-2)^{\prime}}-a_{(n-2) n}^{(n-2) \prime} \cdot x_{n} \\
\cdots \\
x_{2}+a_{23}^{\prime \prime} \cdot x_{3}+\cdots+a_{2(n-1)}^{\prime \prime} \cdot x_{n-1} & = & y_{2}^{\prime \prime}-a_{2 n}^{\prime \prime} \cdot x_{n} \\
x_{1}+a_{12}^{\prime} \cdot x_{2}+a_{13}^{\prime} \cdot x_{3}+\cdots+a_{1(n-1)}^{\prime} \cdot x_{n-1} & = & y_{1}^{\prime}-a_{1 n}^{\prime} \cdot x_{n}
\end{array}
\end{align*}
Эта процедура повторяется для всех оставшихся решений:
\begin{align*}
\begin{array}{rcl}
x_{n-2} & = & \left(y_{n-2}^{(n-2)^{\prime}}-a_{(n-2) n}^{(n-2)^{\prime}} \cdot x_{n}\right)-a_{(n-2)(n-1)}^{(n-2) \prime} \cdot x_{n-1} \\
& \cdots & \\
x_{2}+a_{23}^{\prime \prime} \cdot x_{3}+\cdots & = & \left(y_{2}^{\prime \prime}-a_{2 n}^{\prime \prime} \cdot x_{n}\right)-a_{2(n-1)}^{\prime \prime} \cdot x_{n-1} \\
x_{1}+a_{12}^{\prime} \cdot x_{2}+a_{13}^{\prime} \cdot x_{3}+\cdots & = & \left(y_{1}^{\prime}-a_{1 n}^{\prime} \cdot x_{n}\right)-a_{1(n-1)}^{\prime} \cdot x_{n-1}
\end{array}
\end{align*}
Использование
Представьте, что мы хотим решить следующую линейную систему уравнений:
\begin{align*}
\left(
\begin{array}{cc}
2 & 1 \\
-1 & 1
\end{array}
\right)
\left(
\begin{array}{c}
x_{1} \\
x_{2}
\end{array}
\right)
=
\left(
\begin{array}{c}
5 \\
2
\end{array}
\right).
\end{align*}
Тогда код будет выглядеть так:
// example_gauss_elimination.cpp
#include <iostream>
#include "../src/numerary.hpp" // Numerary library
using namespace std;
using namespace numerary;
/* The main function */
int main() {
double **a = new double*[2];
double *y = new double[2];
double *x = new double[2];
short int is_solved;
for (int i = 0; i < 2; i ++)
a[i] = new double[2];
// Initialize matrix A
a[0][0] = 2;
a[0][1] = 1;
a[1][0] = -1;
a[1][1] = 1;
// Initialize vector y
y[0] = 5;
y[1] = 2;
is_solved = Numerary::linear_systems_of_equations(a, y, x, 2, "gauss");
if (is_solved == 1) {
cout << "System solved!" << endl;
cout << "x = (" << x[0] << ", " << x[1] << ")" << endl;
} else {
cout << "Method is not allowed!";
}
for (int i = 0; i < 2; i++) delete[] a[i];
delete[] a;
delete[] x;
delete[] y;
return 0;
}