Вы здесь

Метод Гаусса. Решение систем линейных уравнений

Исходный код на C++: 

Теория

Метод Гаусса прост и широко применим для решения систем линейных уравнений. Рассмотрим систему уравнений (рис. 1).


рис. 1. Метод Гаусса решение систем линейных уравнений. Система уравнений.

Суть работы алгоритма очень проста. Она заключается в последовательности удаления элементов. Умножаем элементы первой строки на элемент A21, а элементы второй строки на элемент A11. Вычитая из первой строки вторую, получим следующее уравнение 0x1+(A21*A12-A11*A22)x2 +(A21*A13-A11*A23)x3+...+(A21*A1n-A11*A2n)xn=A21*b1-A11*b2 второй строки. Обнулив переменную x1 во второй строке, аналогично делаем в третьей 0x1+(A31*A12-A11*A32)x2+(A31*A13-A11*A33)x3+...+(A31*A1n-A11*A3n)xn=A31*b1-A11*b3. Для n-ой строки 0x1+(An1*A12-A11*An2)x2+(An1*A13-A11*An3)x3+...+(An1*A1n-A11*Ann)xn=An1*b1-A11*bn. Заменим выражение (A21*A12-A11*A22) на A22^(1),(A21*A13-A11*A23) на A23^(1),(A21*A1n-A11*A2n) на A2n^(1), (A21*b1-A11*b2) на b2^(1) и т.д. (рис. 2).


рис. 2. Решение систем уравнений метод Гаусса «прямой ход». Удаление переменной x1.

После преобразования системы (рис. 1) переменная x1 осталась только в первом уравнении (рис 2). На втором шаге проделываем аналогичные операции. Умножаем элементы второй строки на элемент A32^1, а элементы третьей строки на элемент A22^1. Вычитая из второй строки третью, получим следующее уравнение 0x2+(A32^1*A23^1-A22^1*A33^1)x3+(A32^1*A24^1-A22^1*A34^1)x3+...+(A32^1*A2n^1-A22^1*A3n^1)x3=A32^1*b2^1- A22^1*b3^1 третьей строки. Удалив переменную x2 из всех уравнений кроме второго, мы получим следующую систему уравнений (рис. 3).


рис. 3. Решение систем уравнений метод Гаусса «прямой ход». Удаление переменной x2.

Продолжаем данный процесс (n-1) раз. В результате получим треугольную матрицу (рис. 4). Данное преобразование называется «прямой ход».


рис. 4. Решение систем уравнений метод Гаусса «прямой ход». Треугольный вид системы уравнений.

Используя треугольную систему уравнений (рис. 4), легко получаем значения неизвестных x, начиная с последнего уравнения (рис. 5). Данный процесс называется «обратный ход» решения систем уравнений методом Гаусса.


рис. 5 Решение системы уравнений метод Гаусса «обратный ход».

Программная реализация

int gaus(int cnt_str,double **mass,double *&x)
{
int i,j,k;
x=new double [cnt_str];//выделение памяти для неизвестных
//прямой ход
for(i=0;i<cnt_str;i++)
{
double a=mass[i][i];
for(j=i+1;j<cnt_str;j++)
{
double b=mass[j][i];
for(k=i;k<cnt_str+1;k++)
mass[j][k]=mass[i][k]*b-mass[j][k]*a;
}
}
//обратный ход
for(i=cnt_str-1;i>=0;i--)
{
double summ=0.;
for(j=i+1;j<cnt_str;j++)
summ+=mass[i][j]*x[j];
summ=mass[i][cnt_str]-summ;
if(mass[i][i]==0)
return 0;
x[i]=summ/mass[i][i];
}
return 1;
}