Реализация на языке программирования Си решения системы линейных уравнений методом Гаусса

Размещено на http://www.allbest.ru/

Содержание

Задание на проектирование

Введение

1. Обзор предметной области

2. Теоретическая часть

3. Инструкция пользователя

4. Инструкция программиста

5. Тестирование

Заключение

Библиографический список

Приложение

Задание на проектирование

Квадратная система линейных уравнений Ax=b может содержать до 200 переменных. Создать структуру для хранения параметров системы в динамической памяти. Написать отдельную функцию для решения системы. Предусмотреть все возможные ситуации: нет решений, единственное решение, бесконечное количество решений. В последнем случае найти базис векторов, который позволит получить произвольное решение системы.

В методе Гаусса выбор разрешающего элемента реализовать как наибольший по модулю в правой нижней подматрице.

В интерфейсную часть включить возможность ввода данных с клавиатуры, из готового файла и заполнение случайными элементами.

Провести тестирование функции решения. В частности, подставить найденное решение в исходную систему. Сравнить решение с аналогичной функцией в пакете MatLab. Объяснить большие погрешности решения для плохо обусловленных матриц.

Введение

Курсовое проектирование является основной формой самостоятельной работы студента и способствует приобретению студентов навыков теоретически грамотного и логически последовательного изложения рассматриваемой проблемы.

Целью данной курсовой работы является реализация на языке программирования Си решения системы линейных уравнений методом Гаусса. Для реализации задания курсовой работы требуются умение решать системы методом Гаусса, знания основы программирования на зыке Си в частности «динамическая память», «структуры», «массивы», «работа с файлами».

Основу всей этой работы составляет написание отдельной эффективной функции для решения системы линейных уравнений. Провести тестирование этой функции, сравнить результат с другими программами по решению системы линейных уравнений, объяснить погрешности решения.

1. Обзор предметной области

Си (англ. C) - стандартизированный процедурный язык программирования, разработанный в начале 1970-х годов сотрудниками Bell Labs Кеном Томпсоном и Денисом Ритчи как развитие языка Би. Си был создан для использования в операционной системе (ОС) UNIX. С тех пор он был импортирован на многие другие операционные системы и стал одним из самых используемых языков программирования. Си ценят за его эффективность; он является самым популярным языком для создания системного программного обеспечения. Его также часто используют для создания прикладных программ. Несмотря на то, что Си не разрабатывался для новичков, он активно используется для обучения программированию. В дальнейшем синтаксис языка Си стал основой для многих других.

Для языка Си характерны лаконичность, современный набор конструкций управления потоком выполнения, структур данных и обширный набор операций.

Язык программирования Си отличается максимализмом функций. Авторы языка хотели, чтобы программы на нём легко компилировались с помощью однопроходного компилятора, после компиляции каждой элементарной составляющей программы соответствовало весьма небольшое число машинных команд, а использование базовых элементов языка не задействовало библиотеку времени выполнения. Однопроходный компилятор компилирует программу, не возвращаясь назад, к уже откомпилированному тексту. Поэтому использованию функции должно предшествовать её объявление. Код на Си можно легко писать на низком уровне абстракции, почти как на ассемблере. Иногда Си называют «универсальным ассемблером» или «ассемблером высокого уровня», что отражает различие языков ассемблера для разных платформ и единство стандарта Си, код которого может быть скомпилирован без изменений практически на любой модели компьютера. Си часто называют языком среднего уровня или даже низкого уровня, учитывая то, как близко он работает к реальным устройствам.

Компиляторы Си разрабатываются сравнительно легко благодаря относительно низкому уровню языка и скромному набору элементов. Поэтому данный язык доступен на самых различных платформах (возможно, круг этих платформ шире, чем у любого другого существующего языка). К тому же, несмотря на свою низкоуровневую природу, язык позволяет создавать переносимые программы и поддерживает программиста в этом. Программы, соответствующие стандарту языка, могут компилироваться на самых различных компьютерах.

Си (как и ОС UNIX, с которой он долгое время был связан) создавался программистами и для программистов, круг которых был бы ненамного шире круга разработчиков языка. Несмотря на это, область использования языка значительно шире задач системного программирования.

Си создавался с одной важной целью: сделать более простым написание больших программ с минимумом ошибок по правилам процедурного программирования, не добавляя лишних накладных расходов на итоговый код программы компилятором, как это всегда делают языки очень высокого уровня, такие как Бейсик.

2. Теоретическая часть

Метод Гаусса - классический метод решения системы линейных алгебраических уравнений (СЛАУ). Состоит в постепенном понижении порядка системы и исключении неизвестных.

Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.

На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. А именно, среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получавшуюся после перестановки первую строку из остальных строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию.

На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений. Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (а она там всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх. Каждой строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки.

Элементарными преобразованиями называют:

- перестановка местами любых двух строк матрицы;

- умножение любой строки матрицы на константу k, k?0;

- прибавление к любой строке матрицы другой строки, умноженной на константу k, k?0.

3. Инструкция пользователя

Данная программа предназначена для решения систем линейных уравнений методом Гаусса. При запуске программы перед пользователям появляется интерфейс программы. Программа выводит запрос на ввод количество строк в системе, количество столбцов в программе будет всегда на одну больше количества строк. В программе иметься ограничение на количество вводимых строк, нельзя вести больше пятнадцати и меньше одной, если вводиться неверное число или вводиться буква либо любой другой символ, то запрос повторяется снова.

После ввода количества строк появляется следующий запрос, в котором нужно выбрать как заполнить массив. При нажатии на кнопку 1 массив заполниться случайными числами в диапазоне от минус десяти до пятнадцати. Если нажать на кнопку 2 то массив предстоит заполнить в ручную. Если же будет выбран 3 вариант, массив заполнится из файла, нажатие другой кнопки приводит к повтору запроса.

При выборе второго варианта предлагается ввести первое число a[0][0](первый ноль означает номер строки, второй столбца), число должно быть в диапазоне от минус девяноста девяти до девяноста девяти, иначе запрос повториться. Массив заполняется с лева на права.

Если выбрать третий вариант, то массив заполниться из файла text.txt лежащего в этой же директории что и программа. При отсутствии файла появиться сообщение, что файл не открыт и программа завершится. Если в файле кроме цифр будут содержать буквы и символы, то появиться сообщение о том, что не правильное содержимое файла и программа завершится. В файле должно содержаться необходимое количество цифр для заполнения массива иначе появится сообщения, что матрица не заполнена до конца. Например: если ввели 3 строки то 3*4=12 цифр должно содержаться в файле. Цифры в файле должны разделяться пробелом или начинаться с новой строки.

После того как система заполнена она выводится на экран, есть нажать любую кнопку появляется запрос о том показывать ли подробно изменения системы в ходе подсчетов. При нажатии на кнопку Y программа будет выводить систему каждый раз после её изменения это помогает понять как программа решает систему. После каждого вывода системы нужно нажимать любую клавишу, чтобы появилось следующие изменение. Если ответить на вопрос нажатием кнопки N то программа сразу же выведет результат подсчетов. Ответить на вопрос можно только нажатием Y или N иначе запрос повторится.

По окончанию программы после подсчетов выводятся значения всех неизвестных, то есть единственно решение системы. Если систему невозможно решить, то выводиться сообщение о том, что система не имеет решение или имеет множество решений.

4. Инструкция программиста

struct SLU - глобальная структура которая хранить в себе всю систему **a, а также её размер r.

void vivod_matrici(struct SLU *S) функция выводит матрицу на экран, в качестве параметра ей передается структуру для вывода её.

void vihod(SLU *S) функция выхода из программы, вызывается когда нужно завершить программу. В качестве параметра ей передается структуру в которой освобождается память выделенная для системы **a, закрывает все открытые файлы, чистит экран, выходит.

int metod_gaussa(struct SLU *S, int v) функция решает систему методом гаусса. В качестве параметра ей передается структуру и переменная, если значение переменой равно 1 то функция будет выводить подробно подсчеты вычислений. Функция возвращает значение mnogo, net, single.

c=(float *) malloc(S->r * sizeof(float)); выделяем память под массив *c, в него будут скопированы получившиеся в результате подсчета неизвестные с целью дальнейших перестановок таких же как и со столбцами.

b=(int *) malloc(S->r * sizeof(int)); выделяем память под массив *b, его заполняем индексами которые будут переставляться также как и столбцы, с целью того что бы в дальнейшим переставить результаты вычислений также как и столбцы.

Дальше находим наибольший по модулю элемент в подматрицы. Проверяем на данном этапе имеет ли система решение или множество решений, если не имеет или имеет множество решений то освобождается память массивов free(b); free(c); и функция возвращает значение net или mnogo. Когда нашли максимальный элемент переставляем столбцы и строки так что бы поменять местами текущий и максимальный элемент. Меняем индексы также как и столбцы.

После этого идет алгоритм прямого хода метода гаусса, систему приводим к ступенчатой или треугольной форме. Следующий алгоритм находит неизвестные, все получившиеся результаты записывается в самый правый столбец. Дальше меняем неизвестные также как столбцы при помощи массивов b и с. По окончанию освобождается память массивов free(b); free(c); и функция возвращает значение single, которое значит что система имеет единственное решение.

void main() функция начала программы. Выделяется память под переменную *buff, если память не выделена то программа завершается. Запрос на ввод количество строк в системе S.r, количество строк должно соответствовать критерием. Выделяем память под всю систему S.a размером S.r, при ошибки программа закрывается. Вывод запроса на метод заполнения системы, 1-случайным образом, 2-в ручную, 3-из файла. Следующий запрос спрашивает показывать ли подробно подсчеты Y-да(переменой v присваивается 1), N-нет(переменой v присваивается 0). Вызывается функция metod_gaussa(&S, v); ей передается заполненная система и переменная v со значением. В зависимости что возвратит функция такой выведется и результат, если single то покажет единственное решение все найденные неизвестные, если mnogo то система имеет множество решение, если net система не имеет решения. По окончанию программы вызывается функция vihod(&S).

5. Тестирование

void test()

{

SLU T;

T.r=3;

int i=0, j=0;

T.a = (float **) malloc(T.r * sizeof(float*));

for (i=0; i<T.r; i++)

{

T.a[i] = (float *) malloc((T.r+1) * sizeof(float));

}

//----------------------------------------------

{

float B[3][4]={{1,1,1,3},

{0,1,0,1},

{0,0,0,1}};

for (i=0; i<T.r; i++)

{

for (j=0; j<T.r+1; j++)

{

T.a[i][j]=B[i][j];

}

}

int rez = metod_gaussa(&T, 0);

if (rez!=net)

{

printf("error 1\n");

}

}

//----------------------------------------------

{

float B[3][4]={{1,1,1,3},

{0,1,0,1},

{0,0,1,0}};

for (i=0; i<T.r; i++)

{

for (j=0; j<T.r+1; j++)

{

T.a[i][j]=B[i][j];

}

}

int rez = metod_gaussa(&T, 0);

if (rez!=mnogo)

{

printf("error 2\n");

}

}

//----------------------------------------------

{

float B[3][4]={{1,1,1,3},

{0,0,1,1},

{0,0,1,1}};

for (i=0; i<T.r; i++)

{

for (j=0; j<T.r+1; j++)

{

T.a[i][j]=B[i][j];

}

}

int rez = metod_gaussa(&T, 0);

if (rez!=mnogo)

{

printf("error 3\n");

}

}

//----------------------------------------------

{

float B[3][4]={{2,-4,9,28},

{7,3,-6,-1},

{7,9,-9,5}};

for (i=0; i<T.r; i++)

{

for (j=0; j<T.r+1; j++)

{

T.a[i][j]=B[i][j];

}

}

metod_gaussa(&T, 0);

if(fabs(T.a[0][3]-2)>1e-3 ||

fabs(T.a[1][3]-3)>1e-3 ||

fabs(T.a[2][3]-4)>1e-3)

{

printf("error 4\n");

}

}

//----------------------------------------------

{

float B[3][4]={{1,2,1,5},

{-1,3,-2,3},

{-1,-7,4,-5}};

for (i=0; i<T.r; i++)

{

for (j=0; j<T.r+1; j++)

{

T.a[i][j]=B[i][j];

}

}

metod_gaussa(&T, 0);

if(fabs(T.a[0][3]-2)>1e-3 ||

fabs(T.a[1][3]+1)>1e-3 ||

fabs(T.a[2][3]-2)>1e-3)

{

printf("error 5\n");

}

}

//----------------------------------------------

for(i=0; i<T.r; i++)

{

free(T.a[i]);

}

free(T.a);

}

Заключение

программирование линейный уравнение гаусс

Выполнив данную курсовую работу, я повторил основные базовые темы языка программирования Си такие как «динамическая память», «структуры», «массивы», «работа с файлами». Приобрел определенны навыки в работе с методом Гаусса и его особенностями. Данную программу можно использоваться для решения больших систем методом Гаусса за очень маленький промежуток времени.

В некоторых случаях результаты вычислений были с погрешностью из-за того что в компьютере числа представляются посредством комбинаций 0 и 1 (двоичных цифр). Поскольку представление значений определенного типа имеет фиксированное число битов, эти значения могут принадлежать только определенному диапазону. Если присваивается значение, находящееся вне диапазона допустимых значений для данного типа, происходит ошибка переполнения. В значениях с плавающей точкой, кроме того, что в них также имеет место переполнение, возможна потеря разрядов значимости, определяющих степень точности значения. Например, значения типа float допускают 6-7 значащих цифр. Предположим, например, что мы присваиваем переменной типа float значение 1.234567890. Поскольку тип float обеспечивает только 7 значащих цифр, точными будут только первые 7 цифр (1.234567). С другой стороны, значения типа double обеспечивают от 14 до 15 значащих цифр. В результате значение 1.234567890 может быть точно сохранено как значение типа double. При работе со значениями в формате с плавающей точкой следует помнить о том, что эти значения представляются с использованием фиксированного числа битов. Если так, то компьютер не в состоянии всегда представлять значения точно - в некоторых случаях представление значения с плавающей точкой содержит погрешность. Например, компьютер может представить значение 0.4 как 0.3999999 или значение 0.1 как 0.099999 и т.д.

Библиографический список

1. Kris Jamsa (Крис Джамса). 1001 совет по С/С++. Настольная книга программиста М.: Март, БИНОМ, Универсал, 1997. - 784 с

2. Kris Jamsa (Крис Джамса). Учимся программировать на языке C++: Пер. с англ. - М.: Мир, 1999. - 320 с., ил.

Приложение

#include <stdio.h>

#include <conio.h>

#include <iostream.h>

#include <stdlib.h>

#include <math.h>

#include <string.h>

#define single 1

#define mnogo 2

#define net 0

struct SLU

{

float **a;

int r;

};

void test();

void vivod_matrici(struct SLU *S) //funkciia vivodit matricu na ekran

{

for(int i=0; i<S->r; i++)

{

for(int j=0; j<S->r+1; j++)

{

printf ("%.2f\t",S->a[i][j]);

}

printf ("\n");

}

printf ("\n");

if(!getch())

{

getch();

}

}

void vihod(SLU *S) //funkcia vihoda iz programmi, chistit pamiat', zakrivaet faili

{

for(int i=0; i<S->r; i++)

{

free(S->a[i]);

}

free(S->a);

fcloseall();

if(!getch())

{

getch();

}

clrscr();

exit(1);

}

int metod_gaussa(struct SLU *S, int v) //funkciia reshaet cictemu metodom gaussa

{

int i1=0, j1=0;

int *b;

float *c;

c=(float *) malloc(S->r * sizeof(float)); //massiv dlia kopii polu4ivshihsia rezultatov

b=(int *) malloc(S->r * sizeof(int)); //massiv indeksov dlia perestanovok, kak i stolbcov

for (i1=0; i1<S->r; i1++)

{

b[i1]=i1;

}

float buf=0, buf1=0;

int p=0, p1=0, p2=0;

int i=0, j=0, bbb=0;

int abc1=0, abc2=0;

float abc=0;

while(j<S->r)

{

if (v==1)

{

vivod_matrici(S);

}

abc1=j; //nahodim naibol'shii po modulu element v podmatrici

abc2=j;

abc=fabs(S->a[j][j]);

for(j1=j; j1<S->r; j1++)

{

for(i1=j; i1<S->r; i1++)

{

if(abc < fabs(S->a[i1][j1]))

{

abc=fabs(S->a[i1][j1]);

abc1=i1;

abc2=j1;

}

}

}

abc=0;

if (S->a[S->r-1][S->r]==0 && j==S->r-1) //proverka na mnojestvo reshenii

{

free(b);

free(c);

return mnogo;

}

else if (S->a[abc1][abc2]==0) //proverka na net resheniia

{

free(b);

free(c);

return net;

}

else if (S->a[abc1][abc2]!=0 && j==S->r-1) //vishodim iz poslednego cikla, posle proverok

{

break;

}

for(bbb=0; bbb<S->r+1; bbb++) //meniaem stroki mestami

{

buf1=S->a[j][bbb];

S->a[j][bbb]=S->a[abc1][bbb];

S->a[abc1][bbb]=buf1;

}

for(bbb=0; bbb<S->r; bbb++) //meniaem stolbci mestami

{

buf1=S->a[bbb][j];

S->a[bbb][j]=S->a[bbb][abc2];

S->a[bbb][abc2]=buf1;

}

buf1=b[j]; //meniaem indeksi kak i stolbci

b[j]=b[abc2];

b[abc2]=buf1;

if (v==1)

{

vivod_matrici(S);

}

p1++; //primoi hod metoda gaussa

for(p=0; p<S->r-p1; p++)

{

i++;

buf=S->a[i][j]/S->a[j][j];

if((buf*S->a[j][j])+S->a[i][j]!=0)

{

buf=buf*-1;

}

else

{

buf=fabs(buf);

}

for(p2=j; p2<S->r+1; p2++)

{

S->a[i][p2]+=S->a[j][p2]*buf;

}

}

j++;

i=j;

}

int q=0, q1=0, q2=0, q3=0, T=0, T1=0;

float D[20];

float buf2=0;

i=0;

for (q=0; q<S->r; q++) //nahodim neizvestnie

{

for(q1=0; q1<q2; q1++)

{

buf2 += (D[T] * S->a[S->r-q-1][S->r-q3] * (-1));

q3++;

T++;

}

T=0;

q2++;

q3=1;

i++;

D[T1] = (buf2 + S->a[S->r-i][S->r]) / S->a[S->r-i][S->r-i];

buf2 = 0;

S->a[S->r-i][S->r]=D[T1];

T1++;

}

for (i1=0; i1<S->r; i1++) //meniaem otveti kak i stolbci

{

c[i1]=S->a[i1][S->r];

}

for (i1=0; i1<S->r; i1++)

{

S->a[i1][S->r]=c[b[i1]];

}

free(b);

free(c);

return single;

}

void main()

{

clrscr();

test();

int i=0, j=0, v=0, v1=0;

char *buff;

SLU S;

buff = (char *) malloc(2 * sizeof(float));

if (buff==NULL)

{

printf("\nOshibka pri videlenii pamiati");

if (!getch())

{

getch();

}

exit(1);

}

do

{

cout<<"Vvedite kolichestvo strok: ";

cin>>buff;

S.r=atoi(buff);

}

while (S.r<1 || S.r>15);

S.a = (float **) malloc(S.r * sizeof(float*));

if (S.a==NULL)

{

printf("\nOshibka pri videlenii pamiati pod massiv ukazatelei");

if (!getch())

{

getch();

}

exit(1);

}

for (i=0; i<S.r; i++)

{

S.a[i] = (float *) malloc((S.r+1) * sizeof(float));

}

while(v1==0)

{

cout<<"1-rendom, 2-vruchnue, 3-iz faila\n";

v = getch();

switch (v)

{

case '1':

randomize();

for (i=0; i<S.r; i++)

{

for (j=0; j<S.r+1; j++)

{

S.a[i][j]=random(25)-10;

}

}

v1++;

break;

case '2':

for (i=0; i<S.r; i++)

{

for (j=0; j<S.r+1; j++)

{

do

{

printf ("a[%i][%i]=",i,j);

cin>>buff;

S.a[i][j]=atof(buff);

}

while (S.a[i][j]<-99 || S.a[i][j]>99);

}

}

v1++;

break;

case '3':

FILE *fp;

fp=fopen("text.txt", "rb");

if(fp == NULL)

{

cout<<"fail ne otkrit";

vihod(&S);

}

float w;

int t=0;

i=0;

j=0;

while(!feof(fp))

{

int res=fscanf(fp,"%f",&w);

if(res==0)

{

cout<<"Nepravilnoe soderjimoe faila";

vihod(&S);

}

else if(t < ((S.r+1)*S.r))

{

t++;

S.a[i][j]=w;

j++;

if(S.r+1==j)

{

i++;

j=0;

}

}

}

if(t < ((S.r+1)*S.r))

{

cout<<"Matrica ne zapolnena do konca";

vihod(&S);

}

v1++;

break;

}

}

printf ("\n");

vivod_matrici(&S);

v=0;

v1=0;

while(v1==0)

{

cout<<"Pokazivat' podrobno podscheti? (y-da n-net): ";

cin>>buff;

strlwr(buff);

switch (*buff)

{

case 'y':

v=1;

v1++;

break;

case 'n':

v=0;

v1++;

break;

}

}

printf ("\n");

free(buff);

int rez = metod_gaussa(&S, v);

switch(rez)

{

case single:

for (i=0; i<S.r; i++)

{

printf("\nx%i:%f",i+1,S.a[i][S.r]);

}

printf("\n\nedinstvennoe reshenie sistemi");

break;

case mnogo:

printf ("\nsistema imeet mnojestvo reshenii");

break;

case net:

printf ("\nsistema ne imeet resheniia");

break;

default: printf ("\noshibka");

}

vihod(&S);

}

Рис.1

Размещено на Allbest.ru