Полный текст:
Содержание
Введение. 4
1.
Общий раздел. 5
1.1. Классификация моделей. 5
1.2.
Технические средства реализации задачи. 6
1.2.1.
Программные средства реализации. 6
1.2.1.1. Операционная система. 6
1.2.1.2. Язык программирования. 6
1.2.2.
Аппаратные средства реализации. 6
1.2.2.1. Процессор. 6
1.2.2.2. Память и клавиатура. 6
1.2.2.3. Монитор. 6
2.
Специальный раздел. 7
2.1 Постановка задачи. 7
2.2 Технико-математическое описание
задачи. 8
2.3. Описание алгоритма. 10
2.4. Оценка результата. 13
2.5. Тестирование программы. 14
ПРИЛОЖЕНИЕ
А.. 16
Блок схема алгоритма. 16
ПРИЛОЖЕНИЕ
Б. 20
Тест
программы.. 20
Заключение. 24
Список
используемой литературы.. 25
Введение
Решение систем линейных
алгебраических уравнений – одна из основных задач в различных отраслях
деятельности. Хотя задача решения системы линейных уравнений сравнительно редко
представляет самостоятельный интерес для приложений, от умения эффективно
решать такие системы часто зависит сама возможность математического
моделирования самых разнообразных процессов с применением ЭВМ. Значительная
часть численных методов решения различных (в особенности – нелинейных) задач
включает в себя решение систем линейных уравнений как элементарный шаг
соответствующего алгоритма.
Целью данной работы является
рассмотрения всех методов решения систем линейных уравнений, разбор одного из
них – метода Жордана-Гаусса и реализация данного метода в компьютерном
приложении.
1. Общий раздел.
1.1. Классификация моделей.
Основными методами решения систем линейных уравнений являются
методы Крамера, обратной матрицы (матричный метод) и итерационный метод
Жордана-Гаусса (метод последовательного исключения неизвестных).
Рассмотрим кратко первые 2 метода.
Рассмотрим систему уравнений
На первом шаге вычислим определитель:
его называют главным
определителем системы.
Если? = 0, то система имеет бесконечно много решений или
несовместна (не имеет решений). В этом случае правило Крамера не поможет, нужно
использовать метод Гаусса.
Если ? ? 0, то система имеет единственное решение, и для
нахождения корней мы должны вычислить еще два определителя:
На практике вышеуказанные определители также могут
обозначаться латинской буквой .
Корни уравнения находим по формулам:
,
Матричный метод решения является более трудоемким, и
предполагает вычисление не только определителя, но и умножение матриц.
1.2. Технические средства реализации задачи.
1.2.1. Программные средства реализации.
1.2.1.1. Операционная система.
Используемая операционная система – Windows 7 UltimateSP1, архитектура 64 бит.
1.2.1.2. Язык программирования.
Для построения концептуальной модели проектируемой мною
программы, я выбрал объектно-ориентированное проектирование. Это следует из
того, что разрабатываемая мною программа будет написана на
объектно-ориентированном языке программирования C++.
Наиболее современная среда компилирования, позволяющая
создавать приложения на данном языке – VisualStudio 2012.
1.2.2. Аппаратные средства реализации.
1.2.2.1. Процессор.
Используемый процессор: IntelCore 2 QuadQ6600 2,4GHz.
1.2.2.2. Память и клавиатура.
Оперативная память: 4096 MbDDR3
Клавиатура стандартная.
1.2.2.3. Монитор.
Разрешение монитора: 1680х1050 – 32 бит.
Видеокарта: NVIDIAGeForse 9600 GS.
2. Специальный
раздел.
2.1Постановка задачи.
Разработать программу для решения системы линейных уравнений
порядка N методом Жордана-Гаусса. Исходные данные: порядок системы линейных
уравнений N, матрица коэффициентов, вектор правых частей. Разработать тестовый
пример для N=5.
2.2 Технико-математическое описание задачи.
Запишем систему, в развернутом виде
(1)
Метод Гаусса состоит в последовательном исключении
неизвестных из этой системы. Сначала мы выбираем главный элемент i-того
столбца, это будет элемент с наибольшим коэффициентом. Предположим, это ai1.
Переставляем i-тое уравнение на первое место. Последовательно умножаем все
уравнения на множитель t1 = и складываем с первым уравнение. Таким образом
мы исключаем одну переменную из всех уравнений кроме первого.
Получим систему
(2)
где
Аналогичным образом, исключая все неизвестные, получим
систему треугольного вида
(3)
Описанная процедура называется прямым ходом метода Гаусса.
Заметим, что ее выполнение было возможно при условии, что все , не равны нулю.
Выполняя последовательные подстановки в последней системе,
(начиная с последнего уравнения) можно получить все значения неизвестных.
. (4)
Эта процедура получила название обратный ход метода Гаусса.
2.3. Описание
алгоритма.
Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.
·
На первом этапе осуществляется так называемый
прямой ход, когда путём элементарных
преобразований над строками систему приводят к ступенчатой
или треугольной
форме, либо устанавливают, что система
несовместна. А именно, среди элементов первого столбца матрицы выбирают
ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и
вычитают получившуюся после перестановки первую строку из остальных строк,
домножив её на величину, равную отношению первого элемента каждой из этих строк
к первому элементу первой строки, обнуляя тем самым столбец под ним. После
того, как указанные преобразования были совершены, первую строку и первый
столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого
размера. Если на какой-то из итераций среди элементов первого столбца не
нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную
операцию.
·
На втором этапе осуществляется так называемый
обратный ход, суть которого заключается в том, чтобы выразить все получившиеся
базисные переменные через небазисные и построить фундаментальную
систему решений, либо, если все переменные являются
базисными, то выразить в численном виде единственное решение системы линейных
уравнений. Эта процедура начинается с последнего уравнения, из которого
выражают соответствующую базисную переменную (а она там всего одна) и
подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам»
наверх. Каждой строчке соответствует ровно одна базисная переменная, поэтому на
каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет
случай последней строки.
Метод Гаусса требует порядка действий.
Таким образом, требуется
создать программу, выполняющую следующие функции:
Ввод размерности системы;
Ввод коэффициентов уравнения;
Выбор главного элемента столбца;
Последовательное умножение всех уравнений на
множитель t1;
Последовательное сложение всех уравнений с
первым;
Ввод в память полученной матрицы
коэффициентов и вектора правых частей в память;
Повторение пунктов 4 – 6 до тех пор пока не
будет получена матрица треугольного вида (3);
Выполнение последовательных подстановок в
полученной системе по формуле (4) (начиная с последнего уравнения);
Получение всех значений неизвестных;
Вывод результатов пользователю.
Блок-схемы алгоритма метода Гаусса:
Рис. 1 Основной алгоритм решения СЛАУ
методом Гаусса
Более детальный алгоритм приведен в
приложении А.
2.4. Оценка результата.
Для оценки
результата найденные значения переменных подставим в исходную систему, и оценим
результаты.
2.5. Тестирование программы.
Рассмотрим
2 системы размерности 5.
1
система:
Ввод
данных.
Результаты:
Проверяем,
подставляя результат в исходную матрицу.
3,67
+ 2*3,67 + 3*-1,33 + 4*0,33 + 5*0,33 = 10.
2
система:
Ввод
данных.
Результаты:
Проверяем,
подставляя результат в исходную матрицу.
3,45
+ 0,2*4,43 + 3*-1,53 + 0,4*2,55 + 5*1,85 = 10.
Приложение
выдает правильные результаты.
ПРИЛОЖЕНИЕ А
Блок схема алгоритма.
Рис. 1 Основной алгоритм
решения СЛАУ методом Гаусса
Рис. 2 Алгоритм
запоминания коэффициентов
Рис. 3 Алгоритм прямого
хода
Рис. 4 Алгоритм выбора
рабочей строки
Рис. 5 Алгоритм
обратного хода
ПРИЛОЖЕНИЕ Б
Тест программы
#include <windows.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <clocale>
#include <iostream>
#include <cstdlib>
voidShowVector(int n, double **
vec, double * vec1);
voidPryamoiHod(int n, double **a,
double *b);
voidObratniHod(int n, double **a,
double *b, double *x);
int main()
{
setlocale(LC_ALL,
"Russian");
inti,j,n;
double **a, *b, *x;
do
{
printf("Введите
размерность матрицы: ");
scanf("%d",&n);
//Выделяем память под матрицу А и
векторы В и Х
a = (double
**)malloc(n*sizeof(double));
b = (double *)malloc(n*sizeof(double));
x = (double *)malloc(n*sizeof(double));
//Ввод a
printf("Введите элементы
матрицы через пробел построчно\n");
for(i
= 0; i< n; i++)
{
a[i] = (double
*)malloc(n*sizeof(double));
for(j = 0; j < n; j++)
{
scanf("%lf",&a[i][j]);
}
}
//Ввод b
printf("Введите свободные
элементы через пробел \n");
for(i = 0; i< n; i++)
{
scanf("%lf",&b[i]);
}
system("cls");
printf("\Просмотрданных\r\n");
printf("Расширенная
матрица: \r\n\n");
ShowVector(n,a,b);
printf("\Процесс решения
методом Гаусса\r\n");
PryamoiHod(n,
a, b);
printf("Приведение
матрицы к диагональному виду\r\n\n");//Прямой ход
ShowVector(n,a,b);
printf("\n");
ObratniHod(n, a, b, x);
printf("Переменные :\r\n");
for(i=0;i<n;i++)
{
printf("
%2.2f ",x[i]);
}
printf("\n\n");
printf("Нажмите
Enter для выхода\r\n");
//Чистимпамять
free((void *)a);
free((void *)b);
free((void *)x);
}
while(toupper(getch()) == 'Y');
return 0;
}
voidShowVector(int n, double **
vec, double * vec1)
{
inti,j;
for(i=0;i<n;i++)
{
for(j=0;j<n+1;j++)
{
if(j==n)
printf("|
%2.2f ",vec1[i]);
else
printf(" %2.2f",vec[i][j]);
}
printf("\n");
}
printf("\r\n");
}
voidPryamoiHod(int n, double **a,
double *b)
{
double v;
for(int k = 0,i,j,im; k < n -
1; k++)
{
im = k;
for(i = k + 1; i< n; i++)
{
if(fabs(a[im][k])
<fabs(a[i][k]))
{
im = i;
}
}
if(im != k)
{
for(j = 0; j < n; j++)
{
v = a[im][j];
a[im][j] = a[k][j];
a[k][j] = v;
}
v = b[im];
b[im] = b[k];
b[k] = v;
}
for(i = k + 1; i< n; i++)
{
v = 1.0*a[i][k]/a[k][k];
a[i][k] = 0;
b[i] = b[i] - v*b[k];
if(v != 0)
for(j = k + 1; j < n; j++)
{
a[i][j] = a[i][j] - v*a[k][j];
}
}
}
}
voidObratniHod(int n, double **a,
double *b, double *x)
{
double s = 0;
x[n - 1] = 1.0*b[n - 1]/a[n -
1][n - 1];
for(inti = n - 2, j; 0 <= i;
i--)
{
s = 0;
for(j = i + 1; j < n; j++)
{
s = s+a[i][j]*x[j];
}
x[i] = 1.0*(b[i] - s)/a[i][i];
}
}
Заключение
В результате выполнения курсового проекта была разработана программа
«Решение СЛАУ методом Гаусса». Программа написана на языке VisualC++. При реализации интерфейса
была использована стандартная библиотека
MFC среды
программирования MicrosoftVisualStudio2012.
В пояснительной записке содержатся все этапы разработки проекта, схемы
алгоритмов, интерфейс рабочего приложения, исходный код программы и ее
тестирование.
Список используемой литературы
1. Прохоренок Н.А.Программирование на C++ в VisualStudio 2010
Express. –М.: СамИздат, 2010.
2. Ник Рендольф, Дэвид Гарднер,
Майкл Минутилло, Крис АндерсонVisualStudio 2010 для
профессионалов. - М.: «Диалектика», 2011, 1184.