Решение СЛУ(схема Халецкого)
.docКГТУ им. А. Н. Туполева
Кафедра управления маркетинга и предпринимательства
Самостоятельная работа по курсу высокоуровневые методы информатики и программирования:
«Решение систем линейных алгебраических уравнений методом схемы Халецкого»
Выполнил:
Гайворонский С.О., гр.6205
Проверил:
Семенов П. К.
Казань 2007
ЧАСТЬ 1: Теоретическая основа метода.
Для удобства рассуждений систему линейных уравнений запишем в матричном виде
(1)
где - квадратная матрица порядка и
, - векторы-столбцы.
Представим матрицы в виде произведения нижней треугольной матрицы и верхней треугольной матрицы с единичной диагональю, т.е.
, (2)
где
, .
Тогда элементы и определяются по формулам:
(3)
и
(4)
Отсюда искомый вектор может быть вычислен из цепи уравнений
. (5)
Так как матрицы и - треугольные, то системы (5) легко решаются, а именно:
(6)
и
(7)
Из формул (6) видно, что числа выгодно вычислять вместе с коэффициентами . Этот метод получил название схемы Халецкого.
Заметим, что если матрица А симметрическая, т.е. , то
.
Схема Халецкого удобна для работы на вычислительных машинах, т.к. в этом случае операции "накопления" (3) и (4) можно проводить без записи промежуточных результатов.
Описание файлов программы
Программа состоит из трех файлов:
1)slu.h
В этом файле находится описание класса slu, который имеет следующие общедоступные методы:
-
void input(int M)- осуществляет ввод матрицы системы и свободных членов
-
void syst() – поиск решения
-
void print_x() – вывод решения
Класс slu имеет конструктор и деструктор. Конструктор инициализирует переменные и указатели. Деструктор освобождает память, если она была распределена.
2) slu_realiz.cpp
Данный файл содержит реализацию методов, описанных в файле slu.h.
В метод void input(int M) передаются данные о размерности системы. Затем вводятся начальные матрицы.
Основным методом является void syst(). Здесь происходит поиск решения. Поиск происходит методом формул,описанных в методе Халецкого.
В методе void print_x() программа выводит решение системы.
3) SLU.cpp
Головная программа, в которой представлен пример использования всех методов.
// slu_realiz.cpp
//
#include "stdafx.h"
#include <iostream>
#include "slu.h"
using namespace std;
void slu::input(int M)
{
int i,j,k,v;
double d;
size=M;
double *b;
//Ввод правой части
b = new double[M];
for(i=0;i<M;i++)
{
cout << "b [ " << i << " ] : ";
cin >> b [i];
}
double *a;
//Ввод левой части
a = new double [M*(M+1)];
for(i=0;i<M;i++)
for(j=0;j<M;j++)
{
cout << "a [" << i << "] [ " << j << "] : ";
cin >> a[i*(M+1)+j];
}
//Формирование матрицы,содеражей коэффициенты системы
for(i=0;i<M;i++)
a[i*(M+1)+M]=b[i];
key=1;
for(i=0;i<M;i++)
for(j=i+1;j<M;j++)
{ v=0;
d=a[i*(M+1)+0]/b[j];
for(k=1;k<M+1;k++)
if (a[i*(M+1)+k]!=d*a[j*(M+1)+k])
v=1;
key=key*v;
};
if (key==0)
{cout << "net resheniya";};
}
void slu::syst()
{
int i,j,k,M;
M = size;
double *bb;
bb = new double [M*M];
double *c;
c = new double [M*M];
double s;
//Вычисление 1-ого столбца матрицы b(по формуле(3)1 части)
for ( i=0; i<M; i++ )
bb[i*M+0] = a[i*(M+1)+0];
//Формирование 1-ой строки матрицы c(по формуле(4) 1 части)
for ( i=0; i<=M; i++ )
c[0*M+i] = a[0*(M+1)+i] / bb [0*M+0];
//Формирование остальных столбцов матрицы b и строк матрицы c (по формулам (3) и (4) 2 части)
for ( j = 1; j <M;j++)
{
for ( i=j; i<M; i++ )
{
s = 0;
for ( k=0;k<=j+(-1); k++)
s = s + bb[i*M+k]*c[k*M+j];
bb[i*M+j] = a[i*(M+1)+j]- s;
} ;
for ( i=j; i<=M; i++ )
{
s = 0;
for ( k =0; k<=j +(-1); k ++)
s = s + bb[j*M+k] * c[k*M+i];
c[j*M+i] = ( a[j*(M+1)+i] +(-s) ) / bb[j*M+j];
}
};
//Вычисление вектора y (по формуле(6))
double *y;
y = new double [M];
for (i=0;i<M;i++)
{
s=0;
for(k=0;k<=i-1;k++)
s=s+bb[i*M+k]*y[k];
y[i]=1/bb[i*M+i]*(a[i*(M+1)+M]-s);
}
//Вычисление вектора x (по формуле (7))
double *x;
x = new double [M];
for (i=M-1; i>=0 ;i--)
{ s=0;
for (k=i+1;k<M;k++)
s=s+c[i*M+k]*x[k];
x[i]=y[i]-s;
}
}
void slu::print_x()
//Вывод решения системы
{
int i,M;
M=size;
for(i=0;i<M;i++)
cout <<"x [ " << i << " ] : " << x[i]<< endl;
cin>> M;
}
//slu.h
//
class slu
{
double *a, *b, *x;
int size, key;
public:
// Конструктор
slu (){
size=0;
a=0;
b=0;
x=0;
}
// Деструктор
~slu(){
if (size!=0){
delete [] a;
delete [] b;
delete [] x;
}
}
void input(int M); // Ввод системы
void syst(); // Поиск решения
void print_x(); // Вывод корней системы
};
// SLU.cpp
//
#include "stdafx.h"
#include "slu.h"
#include <conio.h>
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int M;
cout << "Input size of system: "; cin >> M;
slu n;
n.input(M);
cout << "\n";
getch();
n.syst();
cout << "\n";
n.print_x();
getch();
return 0;
Контрольный пример
Input size of system: 4
b[0]:4.84
b[1]:8.89
b[2]:-14.01
b[3]:-20.29
a[0][0]:2.0
a[0][1]:-4.0
a[0][2]:-3.25
a[0][3]:1.0
a[1][0]:3.0
a[1][1]:-3.0
a[1][2]:-4.3
a[1][3]:8.0
a[2][0]:1.0
a[2][1]:-5.0
a[2][2]:3.3
a[2][3]:-20.0
a[3][0]:2.5
a[3][1]:-4.0
a[3][2]:2.0
a[3][3]:-3.0
x[0]:1.15309
x[1]:2.62654
x[2]:-4.19399
x[3]:-0.59049