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

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

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

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

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

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

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

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

      Выполнил:

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

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

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

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

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

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

 

      ОГЛАВЛЕНИЕ 

Введение 3

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

1. Актуальность точного решения системы линейных уравнений методом Гаусса 
2. Существующее состояние темы исследования точного решения системы линейных уравнений методом Гаусса 
3. Постановка задачи разработки алгоритма точного решения системы линейных уравнений методом Гаусса 

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

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

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

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

1. Задачи и условия исследования алгоритма 
2. Программная реализация алгоритма 
3. Результаты исследования алгоритма 

Заключение 

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

 

ВВЕДЕНИЕ 

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

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

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

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

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

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

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

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

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

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

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

 

     

Глава 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-м столбце необходимо найти не первый попавшийся ненулевой элемент, а максимальный по абсолютной величине. Если он по модулю не превосходит е, то считаем, что все элементы столбца нулевые; иначе меняем местами строки, ставя его на вершину столбца, и затем обнуляем столбец элементарными преобразованиями второго рода.

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

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