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

АСТРАХАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

-----------------------------------

Факультет информатика

Кафедра математики и информатики

КУРСОВАЯ РАБОТА

по дисциплине «Численные методы»

РАЗРАБОТКА АЛГОРИТМА ТОЧНОГО РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДОМ ГАУССА

Выполнил:

студент группы ----------

очного отделения

----------------------

Научный руководитель:

-------------------------------------------------------------------------

------------- – 2010

ОГЛАВЛЕНИЕ

Введение.............................................................................................................. 3

Глава 1. ОБОСНОВАНИЕ АКТУАЛЬНОСТИ И ПОСТАНОВКА ЗАДАЧИ
РАЗРАБОТКИ АЛГОРИТМА ТОЧНОГО РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРОВНЕНИЙ МЕТОДОМ ГАУССА..................................................................

1.1.Актуальность точного решения системы линейных уравнений методом Гаусса

1.2.Существующее состояние темы исследования точного решения системы линейных уравнений методом Гаусса.....................................................

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

Глава 2. РАЗРАБОТКА АЛГОРИМА РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ

2.1. Вывод основных математических соотношений
точного решения системы линейных уравнений методом Гаусса.........

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

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

Глава 3. ИССЛЕДОВАНИЕ РАЗРАБОТАННОГО АЛГОРИТМА ТОЧНОГО РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРОВНЕНИЙ МЕТОДОМ ГАУССА.

3.1. Задачи и условия исследования алгоритма......................................

3.2. Программная реализация алгоритма...............................................

3.3. Результаты исследования алгоритма...............................................

Заключение...........................................................................................................

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

ВВЕДЕНИЕ

Линейная алгебра – часть алгебры, изучающая векторные (линейные) пространства и их подпространства, линейные отображения (операторы), линейные, билинейные, и квадратичные функции на векторных пространствах.

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

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

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

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

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

Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Этот метод (который также называют методом последовательного исключения неизвестных) известен в различных вариантах уже более 2000 лет.

Объектно-ориентированное программирование (ООП) — парадигма программирования, в которой основными концепциями являются понятия объектов и классов (либо, в менее известном варианте языков с прототипированием, - прототипов). ООП представляет собой чуть более автоматизированный способ программирования. Основная идея ООП: программа состоит из группы объектов, часто связанных между собой. В ООП объекты включают в себя не только данные (данные-члены), но и методы (функции-члены) воздействия на эти данные. Эти две части в сочетании образуют функциональную единицу программы. Другими словами, объекты содержат данные и методы работы с этими данными.

Объект исследования –

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

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

Глава 1. ОБОСНОВАНИЕ АКТУАЛЬНОСТИ И ПОСТАНОВКА ЗАДАЧИ
РАЗРАБОТКИ АЛГОРИТМА ТОЧНОГО РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРОВНЕНИЙ МЕТОДОМ ГАУССА

1.1 Актуальность точного решения системы линейных

уравнений методом Гаусса

Метод последовательного исключения неизвестных Гаусса является одним из наиболее универсальных и эффективных методов решения линейных систем. (Карл Фридрих Гаусс (1777-1855) - немецкий математик и физик, работы которого оказали большое влияние на дальнейшее развитие высшей алгебры, геометрии, теории чисел, теории электричества и магнетизма.) Этот метод известен в различных вариантах уже более 2000 лет. Он относится к числу прямых методов.

Процесс решения по методу Гаусса состоит из двух этапов, называемых прямым и обратным ходом. На первом этапе система приводится к треугольному виду; на втором (обратный ход) идет последовательное определение неизвестных из указанной треугольной системы.

В отличие от матричного метода и метода Крамера, метод Гаусса может быть применен к системам линейных уравнений с произвольным числом уравнений и неизвестных.Метод Гаусса - один из основных результатов линейной алгебры и аналитической геометрии, к нему сводятся множество других теорем и методов линейной алгебры (теория и вычисление определителей, решение систем линейных уравнений, вычисление ранга матрицы и обратной матрицы, теория базисов конечномерных векторных пространств и т.д.).

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

1.2 Существующее состояние темы исследования точного решения системы линейных уравнений методом Гаусса

Стандартный алгоритм Гаусса использует элементарные преобразования матрицы двух типов.

· Преобразование первого рода: две строки матрицы меняются местами, и при этом знаки всех элементов одной из строк изменяются на противоположные.

· Преобразование второго рода: к одной строке матрицы прибавляется другая строка, умноженная на произвольное число.

Элементарные преобразования сохраняют определитель и ранг матрицы, а также множество решений линейной системы. Алгоритм Гаусса приводит произвольную матрицу элементарными преобразованиями к ступенчатому виду. Для ступенчатой квадратной матрицы определитель равен произведению диагональных элементов, а ранг - числу ненулевых строк (рангом по определению называется размерность линейной оболочки строк матрицы).

Метод Гаусса в математическом варианте состоит в следующем:

1. ищем сначала ненулевой элемент в первом столбце. Если все элементы первого столбца нулевые, то переходим ко второму столбцу, и так далее. Если нашли ненулевой элемент в k-й строке, то при помощи элементарного преобразования первого рода меняем местами первую и k-ю строки, добиваясь того, чтобы первый элемент первой строки был отличен от нуля;

2. используя элементарные преобразования второго рода, обнуляем все элементы первого столбца, начиная со второго элемента. Для этого от строки с номером k вычитаем первую строку, умноженную на коэффициент a_k1/a₁₁.

3. переходим ко второму столбцу (или j-му, если все элементы первого столбца были нулевыми), и в дальнейшем рассматриваем только часть матрицы, начиная со второй строки и ниже. Снова повторяем пункты 1) и 2) до тех пор, пока не приведем матрицу к ступенчатому виду.

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

1. индексы строк и столбцов матрицы начинаются с нуля, а не с единицы;

2. недостаточно найти просто ненулевой элемент в столбце. В программировании все действия с вещественными числами производятся приближенно, поэтому можно считать, что точного равенства вещественных чисел вообще не бывает. Некоторые компиляторы даже выдают предупреждения на каждую операцию проверки равенства вещественных чисел. Поэтому вместо проверки на равенство нулю числа a_ijследует сравнивать его абсолютную величину _ij‌ с очень маленьким числом е (например, е = 0.00000001). Если _ij‌ =< е, то следует считать элемент a_ijнулевым;

3. при обнулении элементов j-го столбца, начиная со строки i + 1, мы к k-й строке, где k > i, прибавляем i-ю строку, умноженную на коэффициент r = -a_kj/a_ij:

Такая схема работает нормально только тогда, когда коэффициент r по абсолютной величине не превосходит единицы. В противном случае, ошибки округления умножаются на большой коэффициент и, таким образом, экспоненциально растут. Математики называют это явление неустойчивостью вычислительной схемы. Если вычислительная схема неустойчива, то полученные с ее помощью результаты не имеют никакого отношения к исходной задаче. В нашем случае схема устойчива, когда коэффициент r = -a_kj/a_ijне превосходит по модулю единицы. Для этого должно выполняться неравенство Отсюда следует, что при поиске разрешающего элемента в j-м столбце необходимо найти не первый попавшийся ненулевой элемент, а максимальный по абсолютной величине. Если он по модулю не превосходит е, то считаем, что все элементы столбца нулевые; иначе меняем местами строки, ставя его на вершину столбца, и затем обнуляем столбец элементарными преобразованиями второго рода.

Таким образом, основная идея метода Гаусса - привести матрицу систему к диагональному виду, то есть все элементы главной диагонали – нули. Для приведения матрицы к такому виду, мы выбираем самую верхнюю строку матрицы, и вычитаем её из всех остальных строк, умножив её для каждой строки на некий коэффициент, так, что самый левый столбец ниже главной диагонали заполнен нулями. Вычитаемая с коэффициентом строка называется текущей строкой. Выбирая текущую строку вначале верхнюю, а потом всё ниже и ниже, мы добьёмся, что все элементы ниже главной диагонали будет равны нулю. Эту часть метода- обработка строк по текущей строке и предстоит распараллеливать.

Суть метода заключается в последовательном исключении неизвестных.

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

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

Анализ существующей литературы по тематики исследования;

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

Выбор средств реализации;

Применение разработанного алгоритма;

Глава 2. РАЗРАБОТКА АЛГОРИМА РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ

2.1. Вывод основных математических соотношений
точного решения системы линейных уравнений методом Гаусса

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

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

Глава 3.ИССЛЕДОВАНИЕ РАЗРАБОТАННОГО АЛГОРИТМА ТОЧНОГО РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРОВНЕНИЙ МЕТОДОМ ГАУССА.

3.1 Задачи и условия исследования алгоритма

3.2 Программная реализация алгоритма

3.3 Результаты исследования алгоритма

Заключение

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Начальный курс С и С++.: Учебник. /Б.И. Березин. Москва:"ДИАЛОГ-МИФИ",1999г.

2. Язык программирования С++. : Учебник. /. Страуструп. Киев:"ДиаСофт", 1993 г.

3. Введение в язык С++: Учебник. /Бьярн Страустрап.– СПб.: 1995.

4. Структуры и алгоритмы обработки данных: Учебник. / Матьяш В.А., Путилов В.А., Фильчаков В.В. , Щёкин С.В. - Апатиты, КФ ПетрГУ, 2000

5. С++ /Дэвис Стефан Р.,4-е издание : Пер. с англ.:- М.: Издательский дом «Вильямс»,2003

6. Основы программирования: Учеб. Для сред. проф. образования /И.Г.Семакин, А.П. Шестаков. – М., 2006.

7. С++ экспресс курс: Учебник. /Лаптев В.В. – СПб.: БХВ- Петербург 2004.

8. С++ учебный курс: Учебник. /Франка П. – СПб.:Питер 2005.

9. МОДЕЛИ И CТРУКТУРЫ ДАННЫХ:/ Учебное пособие/ Д. Далека, А.С. Деревянко, О.Г. Кравец, Л.Е. Тимановская -Харьков:ХГПУ, 2000

10.Высшая математика для экономистов: учебник для студентов вузов/Н.Ш.Кремер,3-е издание.-М.:ЮНИТИ-ДАНА,2006

1. Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов [Текст] / И.Н. Бронштейн, К.А. Семендяев. – М.: Наука, 2007. – 708 с.

2. Васильев, Ф.П. Численные методы решения экстремальных задач. [Текст] / Ф.П. Васильев – М.: Наука, 2002. C. 415.

3. Высшая документация – Online документация [Электронный ресурс] – Режим доступа: http://vm.psati.ru/online-vmath/index.php?page=8

4. Калиткин, Н.Н. Численные методы. [Электронный ресурс] / Н.Н. Калиткин. – М.: Питер, 2001. С. 504.

5. Кнут, Д.Э. Искусство программирования. Основные алгоритмы [Текст] / Д.Э. Кнут. – М.: Вильямс, 2007. Т.1.– 712 с.

6. Метод Гаусса [Электронный ресурс] – Режим доступа: http://www.wikipedia.org/wiki/Метод_Гаусса.

7. Симанков, В.С. Основы функционального программирования [Текст] / В.С. Симанков, Т.Т. Зангиев, И.В. Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.

8. Степанов, П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А.Степанов, А.В. Бржезовский. – М.: ГУАП, 2003. С. 79.

9. Хювенен Э. Мир Лиспа [Текст] / Э. Хювенен, Й. Сеппянен. – М.: Мир, 1990. – 460 с.

10. Волков Е.А. численные методы: Учебное пособие для вузов. – 2-е изд., испр. – М.:Наука, 1987. – 248 с.

11. Роганин А.М. Основные формулы высшей математики. – Х.:Торсинг, 2002

12. Б.П. Демидович и И.А. Марон. “Основы вычислительной математики”, Москва, 1963г.

13. Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. “Численные методы”, Москва, 1987г.

14. Ю.П. Боглаев. “Вычислительная математика и программирование”, Москва, 1990г.

4) Симонович С.В. и др. Информатика Базовый курс: Учеб, для технических вузов. СПБ: Изд. «Питер», 2004.–640с

5) Калиткин Н.Н. и др. Численные методы. М.: Наука, 1982

6) Турчак Л.И. Основы численных методов. М.: Наука, 1987

7) Дьяконов В.П. Система MathCAD. М.: Радио и связь, 1993