Вы здесь

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

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

Теория

Метод вращений, решения систем линейных уравнений имеет одно замечательное свойство. Он не допускает роста элементов матрицы в отличии от метода Гаусса. Используя метод Гаусса при решении систем уравнений, мы последовательно сокращаем количество переменных (приводим матрицу к треугольному виду), тем самым увеличиваем разрядность элементов. При большой размерности системы возникают погрешности округления. Что приводит к переполнению разрядной сетки компьютера. Метод вращений позволяет сократить погрешности вычислений путём нормирования элементов матрицы. Рассмотрим систему уравнений (рис.1).

Система линейных уравнений
рис. 1.Система линейных уравнений.

Преобразуем первое и второе уравнения системы (рис. 1) таким образом: первое — (c1*A11+s1*A21)*x1+(c1*A12+s1*A22)*x2+...+(c1*A1n+s1*A2n)*xn=c1*b1+s1*b2, второе- (-s1*A11 + c1*A21)*x1 + (-s1*A12+c1*A22)*x2+...+(-s1*A1n+c1*A2n)*xn=-s1*b1+c1*b2. Где s1- синус угла fi, c1-косинус угла fi. Их можно посчитать по формуле (рис. 2).

Формула расчёта значений c1 и s1
рис.2. Нахождение значений c1 и s1.

На значения с1,s1 накладываются следующие ограничения: 1. -s1*A11+c1*A21=0 — исключения переменной x1 из второго уравнения 2. c1^2+s1^2=1- нормировка элементов. Заменяем выражение (c1*A11+s1*A21) на A11^(1) ,а (c1*A12+s1*A22) на A12^(1) и т.д. Система уравнений рис. 1 примет следующий вид рис. 3.

Сокращение переменной x1 из 2 уравнения
рис. 3. Удаление переменной x1 из второго уравнения.

После того как мы сократили переменную x1 из второго уравнения, сократим переменную x1 из третьего уравнения. Изменим значения с,s следующим образом рис.4.

Формула расчёта значений c2 и s2
рис.4. Нахождение значений c2 и s2.

Преобразуем первое и третье уравнения системы (рис. 3) таким образом: первое — (c2*A11^(1)+s2*A31)*x1+(c2*A12^(1)+s2*A32)*x2+...+(c2*A1n^(1)+s2*A3n)*xn= c2*b1^(1)+s2*b3, третье - (-s2*A11^(1) + c2*A31)*x1 + (-s2*A12^(1)+c2*A32)*x2+...+(-s2*A1n^(1)+c2*A3n)*xn=-s2*b1^(1)+c2*b3. Заменим выражение (c2*A11^(1)+s2*A31) на A11^(2) ,а (c2*A12^(1)+s2*A32) на A12^(2) и т.д. Система уравнений (рис. 3) примет следующий вид (рис.5).

Сокращение переменной x1 из 3 уравнения
рис.5. Удаление переменной x1 из третьего уравнения.

Далее подобным образом сократим переменную x1 из всех остальных уравнений. Затем переходим ко второму уравнению и сокращаем переменную x2 с 3-его по n-ое уравнение. Продолжаем так до тех пор, пока не получим треугольный вид системы уравнений (рис.6). Используя «обратный ход» метода Гаусса, получим значение неизвестных xn,xn-1,..x1(более подробно о методе Гаусса смотрите Метод Гаусса. Решение систем линейных уравнений).

 Треугольный вид системы линейных уравнений
рис.6. Треугольный вид системы линейных уравнений.

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

int rotation(int cnt_str,double **mass,double *&x)
{
int i,j,k;
x=new double [cnt_str];//выделение памяти для неизвестных
//прямой ход методом вращений
double a,b,c,s,t;
for(i=0;i<cnt_str;i++)
{
for(j=i+1;j<cnt_str;j++)
{
b=mass[j][i];
a=mass[i][i];
c=a/sqrt(a*a+b*b);
s=b/sqrt(a*a+b*b);
for(k=i;k<cnt_str+1;k++)
{
t=mass[i][k];
mass[i][k]=c*mass[i][k]+s*mass[j][k];
mass[j][k]=-s*t+c*mass[j][k];
}
}
}
//обратный ход метод Гаусса
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;
}