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

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

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

ВВЕДЕНИЕ

Решение систем линейных алгебраических уравнений - одна из основных задач вычислительной алгебры. Хотя задача решения системы линейных уравнений сравнительно редко представляет самостоятельный интерес для приложений, от умения эффективно решить такие системы счисления часто зависти сама возможность математического моделирования самых разнообразных процессов с применением ЭВМ. Значительная часть численных методов для различных (в особенности - нелинейных) задач включает в себя решение систем линейных уравнений как элементарный шаг соответствующего алгоритма.

Одна из трудностей практического решения систем большой размерности связанна с ограниченностью оперативной памяти ЭВМ. Хотя объем оперативной памяти вновь создаваемых вычислительных машин растет очень быстро, тем не менее, еще быстрее возрастают потребности практики в решении задач большой размерности. В значительной степени ограничения на размерность решаемых систем можно снять, если использовать для хранения матрицы внешние запоминающие устройства. Однако в этом случае многократно возрастают как затраты машинального времени, так и сложность соответствующих алгоритмов. Поэтому при создании вычислительных алгоритмов линейной алгебры большое внимание уделяют способам компактного размещения элементов матриц в памяти ЭВМ. К счастью, приложения очень часто приводят к матрицам, в которых число элементов много меньше общего числа элементов матрицы. Такие матрицы принято называть разреженными. Одним из основных источников разреженных матриц являются математические модели технических устройств, состоящие из большего числа элементов, связи между которыми локальны.

Простейшие примеры таких устройств - сложные строительные конструкции и большие электрические цепи.

Известны примеры решенных в последние годы задач, где число неизвестных достигало сотен тысяч. Естественно, это было бы невозможно, если бы соответствующие матрицы не являлись разреженными (матрица системы из 100тыс. уравнений в формате двойной точности заняла бы около 75 Гбайт).

1. ОБЩАЯ ЧАСТЬ

1.1 Постановка задачи

В данной курсовой мне предлагается написать программу для решения линейных уравнений методом Гаусса (метод последовательного исключение неизвестных). Он состоит в следующем: систему уравнений приводят к эквивалентной ей системе с треугольной матрицей (система называется эквивалентными, если множества их решений совпадают). Эти действия называют прямым ходом. Из полученной треугольной системы переменные находят с помощью последовательных подстановок.

При выполнении прямого хода используют следующие преобразования:

- умножение или деление коэффициентов свободных членов на одно и то же число;

- сложение и вычитание уравнений системы;

- перестановку уравнений системы;

- исключение из системы уравнений, в которых все коэффициенты при неизвестных и свободные члены равны нулю.

1.2 Назначение и область применения

Решение СЛАУ методом Гаусса - это один из самых простых и быстрых способов решения систем алгебраических уравнений. В отличие от решения СЛАУ методом Крамера он не требует вычисления множества определителей матриц и затем тяжелого деления, у Вас просто меньше мест для ошибок. По сравнению с методом обратных матриц, метод Гаусса гораздо быстрее и не требует выполнения такой сложной операции, как вычисление обратной матрицы. По признанию многих студентов решении систем алгебраических уравнений методом Гаусса гораздо проще для понимания и вызывает у преподавателей больше симпатий.

Рассмотрим простейший случай:

В простейшем случае алгоритм выглядит так:

Прямой ход:

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

Пример:

Покажем, как методом Гаусса можно решить следующую систему:



Обнулим коэффициенты при x во второй и третьей строчках. Для этого домножим их на и 1 соответственно и сложим с первой строкой:

Теперь обнулим коэффициент при y в третьей строке, домножив вторую строку на -6 и сложив с третьей:

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

На втором этапе разрешим полученные уравнения в обратном порядке. Имеем:

z=-1 из третьего;

y=3 из второго, подставив полученное z;

x=2 из первого, подставив полученные z и y.

Таким образом, исходная система решена.

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

1.3 Технические характеристики

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

Таблица 1 - технические характеристики

Характеристика	Значение
Операционная система	MS-DOS
Оперативная память	2кб
Память на жестком диске	10кб
Микропроцессор	Х86

2 Специальная часть

2.1 Разработка программы

Для того чтобы написать программу решения квадратного уравнения нам необходимо знать:

- Формулу нахождения дискриминанта;

- Формулу нахождения корней квадратного уравнения;

- Алгоритмы решения квадратного уравнения;

- Запись порядка функций в С++;

- Находить ошибки в программе.

Программа пишется на языке программирования Borland С++3, ее можно скомпилировать на другом компиляторе С++.

Компиляция - это процесс преобразования текста программы в машинный код. В результате получается исполняемый файл с расширением .ЕХЕ. Для этого достаточно выполнить команду меню ProjectCompile или нажать комбинацию клавиш Ctrl+F9. Программа учитывает в качестве данных любые числа: целые, числа с плавающей точкой, нули. После написания программы нужно ее отладить, найти ошибки и исправить их, а если ошибок не имеется проверить правильность работы программы.

Описание функции.

void glavelem( int k, double mas[] [N + 1], int n, int otv[] ) { int i, j, i_max = k, j_max = k; double temp; //Ищем максимальный по модулю элемент for ( i = k; i < n; i++ ) for ( j = k; j < n; j++ ) if ( fabs( mas[i_max] [j_max] ) < fabs( mas[i] [j] ) ) { i_max = i; j_max = j; } //Переставляем строки for ( j = k; j < n + 1; j++ ) { temp = mas[k] [j]; mas[k] [j] = mas[i_max] [j]; mas[i_max] [j] = temp; } //Переставляем столбцы for ( i = 0; i < n; i++ ) { temp = mas[i] [k]; mas[i] [k] = mas[i] [j_max]; mas[i] [j_max] = temp; } //Учитываем изменение порядка корней i = otv[k]; otv[k] = otv[j_max]; otv[j_max] = i; }

2.2 Спецификация программы

В программе используются следующие объекты:

Функции:

void glavelem( int k, double mas[] [N + 1], int n, int otv[]) - функция нахождения главного элемента

glavelem( k, mas, n, otv ) - установка главного элемента

Переменные:

double x[N]- корни системы

int otv[N]- отвечает за порядок массивов

int i, j, k, n - ввод данных

2.3 Тестирование программы

При запуске программа просит ввести число уравнений системы (Рис.2). В зависимости от цифры, которую мы введем, будет зависеть число корней уравнения. Потом мы вводим значения этой системы (Рис.3). Вывод на экран системы линейных уравнений в виде матрицы (Рис.4) Далее или система не имеет единственного решение (Рис.5) или выводится ответ (Рис.6)

Рисунок 2 - Ввод числа уравнений системы



Рисунок 3 - Ввод значений системы линейных уравнений.

Рисунок 4 - вывод на экран системы линейных уравнений в виде матрицы

Рисунок 5 - Система не имеет единственного решения



Рисунок 6 - Ответ

2.4 Инструкция по выполнению программы

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

- Ввод исходной информации;

- Обработка данных;

- Вывод результатов.

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

- Запустить программу;

- Ввод числа уравнений системы, т.е. в зависимости от цифры которую мы поставим, будет зависеть число корней уравнения. После ввода каждого числа нажимать ENTER;

1) Уравнение решено:

- Система не имеет единственного решения;

- Мы увидим выведенный на экран ответ.

Заключение

программа уравнение функция

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

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

Список литературы

1. Никольский С.М., Потапов М.К. «Алгебра: Учеб. для 8 кл. общеобразоват. учреждений» - М.: Просвещение, 2003;

2. Шилдт, Герберт. «Полный справочник по С» - М.: Издательский дом «Вильямс», 2002;

3. Павловская Т.А. «С/C++. Программирование на языке высокого уровня» - СПб.: Питер, 2002;

4. Березин Б.И., Березин С.Б. «Начальный курс С и С++» - М.: ДИАЛОГ_МИФИ, 1996.

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ А

#include <stdio.h>

#include <conio.h>

#include <math.h>

#define N 50

void glavelem( int k,

double mas[] [N + 1],

int n,

int otv[] );

void normalize( double *x, int n );

int main()

{

double mas[N] [N + 1];

double x[N]; //корни системы

int otv[N]; //Отвечает за порядок корней

int i, j, k, n; //Ввод данных

clrscr();

do

{

printf( "Введите число уравнений системы: " );

scanf( "%d", &n );

if ( N < n )

printf( "Слишком большое число уравнений. Повторите ввод\n" );

} while ( N < n );

//

printf( "Введите систему:\n" );

for ( i = 0; i < n; i++ )

for ( j = 0; j < n + 1; j++ )

scanf( "%lf", &mas[i] [j] );

//Вывод введенной системы

clrscr();

printf( "Система\n" );

for ( i = 0; i < n; i++ )

{

for ( j = 0; j < n + 1; j++ )

printf( "%7.2f ", mas[i] [j] );

printf( "\n" );

}

//Сначала все корни по порядку

for ( i = 0; i < n + 1; i++ )

otv[i] = i;

//Прямой ход методом Гаусса

for ( k = 0; k < n; k++ )

{ //На какой позиции должен стоять главный элемент

glavelem( k, mas, n, otv ); //Установка главного элемента

if ( fabs( mas[k] [k] ) < 0.0001 )

{

printf( "Система не имеет единственного решения " );

return ( 0 );

}

for ( j = n; j >= k; j-- )

mas[k] [j] /= mas[k] [k];

for ( i = k + 1; i < n; i++ )

for ( j = n; j >= k; j-- )

mas[i] [j] -= mas[k] [j] * mas[i] [k];

}

for ( i = 0; i < n; i++ ) //Обратный ход

x[i] = mas[i] [n];

for ( i = n - 2; i >= 0; i-- )

for ( j = i + 1; j < n; j++ )

x[i] -= x[j] * mas[i] [j];

normalize(x,N);

printf( "Ответ:\n" ); //Вывод результата

for ( i = 0; i < n; i++ )

for ( j = 0; j < n; j++ )

if ( i == otv[j] )

{

printf( "%f\n", x[j] ); //Расставляем корни по порядку

break;

}

return ( 0 );

}

//Описание функции

void glavelem( int k, double mas[] [N + 1], int n, int otv[] )

{

int i, j, i_max = k, j_max = k;

double temp;

//Ищем максимальный по модулю элемент

for ( i = k; i < n; i++ )

for ( j = k; j < n; j++ )

if ( fabs( mas[i_max] [j_max] ) < fabs( mas[i] [j] ) )

{

i_max = i;

j_max = j;

}

for ( j = k; j < n + 1; j++ ) //Переставляем строки

{

temp = mas[k] [j];

mas[k] [j] = mas[i_max] [j];

mas[i_max] [j] = temp;

}

for ( i = 0; i < n; i++ ) //Представляем столбцы

{ temp = mas[i] [k];

mas[i] [k] = mas[i] [j_max];

mas[i] [j_max] = temp;

}

i = otv[k]; //Учитываем изменение порядка корней

otv[k] = otv[j_max];

otv[j_max] = i;

}

void normalize( double *x, int n )

{

for ( int i=0; i<n; i++ )

{

if ( fabs( x[i] ) < 1e-6 )

x[i] =0;

}

}

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