КГТУ им. А. Н. Туполева

Кафедра управления маркетинга и предпринимательства

Самостоятельная работа по курсу высокоуровневые методы информатики и программирования:

«Решение систем линейных алгебраических уравнений методом схемы Халецкого»

Выполнил:

Гайворонский С.О., гр.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