Решение системы линейных уравнений численным методом

КР 080401.2-1.000 ПЗ

 

Федеральное агентство по образованию

Государственное образовательное  учреждение

высшего профессионального  образования

«Алтайский государственный  технический университет

им. И.И. Ползунова»

 

БИЙСКИЙ ТЕХНОЛОГИЧЕСКИЙ  ИНСТИТУТ (филиал)

 

Кафедра информатики и  вычислительной математики

 

УДК ххххххх

Курсовая работа сдана  на оценку ______________________________ Руководитель работы _______________________ подпись, должность, и.о. фамилия

 

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

 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К КУРСОВОЙ РАБОТЕ

по дисциплине «Информатика»

 

КР 080401.2-3.000 ПЗ

обозначение документа

 

Выполнил

студент   гр. ТИЭТ-91                                                                                А. К. Кавкайкина

    подпись                               и.о. фамилия

Нормоконтролер

профессор                                                                                         Г.И. Севодина

                                                                              подпись                                 и.о. фамилия

 

 

 

 

 

 

 

Бийск 2010

 

 

Федеральное агентство Российской Федерации

Государственное образовательное  учреждение

высшего профессионального  образования

«Алтайский государственный  технический университет

им. И.И. Ползунова»

 

Бийский технологический институт (филиал)

 

Кафедра информатики и  вычислительной математики

 

 

УТВЕРЖДАЮ

Зав. кафедрой ИВМ

__________   Г.И. Севодина

«_15__» __февраля___  2010_ г.

 

 

 

 

 

ЗАДАНИЕ

 

на курсовую работу по дисциплине «Информатика»

студенту Кавкайкиной А. К.____вариант 2.3_____________________________

группа _____ТиЭТ-91________________ факультет __  _ХТиМ_________

Тема проекта: «Решение системы  линейных уравнений численным методом»

Срок сдачи студентом  законченного проекта ___01.06.10_______________

Исходные данные к проекту: (Текст задания)______________________

__Дана СЛУ. Решить СЛУ методом Гаусса в автоматизированной системе MathCad.  ________

_______________________________________________

______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Дата выдачи задания: _____15.02.10_____________________________________

_______________(Ф.И.О.)______________(подпись  студента)

 

 

 

Оглавление

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

1.Описание математической модели…………………………………………………………….5

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

1.2 Метод Гаусса в математическом  варианте………………..6

2.Описание блок-схемы  алгоритма…………………………………………………………9

3. Решение СЛУ методом  Гаусса……………………………………………………………..10

4.Заключение……………………………………………………..12

5. Список литературы……………………………………………13

 

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

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

 

 

 

 

 

 

 

 

 

 

1. Описание математической модели;

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

Матрица A с элементами a_ij называется ступенчатой, если она обладает следующими двумя свойствами:

1. если в матрице есть нулевая строка, то все строки ниже нее также нулевые;
2. пусть a_ij не равное 0 -- первый ненулевой элемент в строке с индексом i, т.е. элементы a_il = 0 при l < j. Тогда все элементы в j-м столбце ниже элемента a_ij равны нулю, и все элементы левее и ниже a_ij также равны нулю: a_kl = 0 при k > i и l =< j.

Ступенчатая матрица выглядит так:

 

 

Здесь тёмными квадратиками отмечены первые ненулевые элементы строк  матрицы. Белым цветом изображаются нулевые элементы, серым цветом - произвольные элементы.

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

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

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

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

1. Ищем сначала ненулевой элемент в первом столбце. Если все элементы первого столбца нулевые, то переходим ко второму столбцу, и так далее. Если нашли ненулевой элемент в k-й строке, то при помощи элементарного преобразования первого рода меняем местами первую и k-ю строки, добиваясь того, чтобы первый элемент первой строки был отличен от нуля;
2. используя элементарные преобразования второго рода, обнуляем все элементы первого столбца, начиная со второго элемента. Для этого от строки с номером k вычитаем первую строку, умноженную на коэффициент a_k1/a₁₁ .
3. переходим ко второму столбцу (или j-му, если все элементы первого столбца были нулевыми), и в дальнейшем рассматриваем только часть матрицы, начиная со второй строки и ниже. Снова повторяем пункты 1) и 2) до тех пор, пока не приведем матрицу к ступенчатому виду.

1.3.Программистский вариант метода Гаусса имеет три отличия от математического:

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–го уравнения на a₁₁  0, затем: 1) умножим на а₂₁ и вычтем из второго уравнения 2) умножим на а₃₁ и вычтем из третьего уравнения и т.д. Получим:, где d_1j = a_1j/a₁₁, j = 2, 3, …, n+1. d_ij = a_ij – a_i1d_1j i = 2, 3, … , n; j = 2, 3, … , n+1. Далее повторяем эти же действия для второго уравнения системы, потом – для третьего и т.д.

 

 

  2.Описание блок-схемы алгоритма

 

 

 

 

 

 

 

 

 

 

 

 

Обратный ход  метода Гаусса

 

 

 

 

 

 

3.Решение  СЛУ методом Гаусса

 

 

М е т о д  Г а у с а                                                            Исходные данные           - детерминант(определитель)               Решение :

 

Комментарии.

  Функция augment(A,В) формирует расширенную матрицу системы добавлением к матрице системы справа столбца правых  частей. Функция rref приводит расширенную матрицу системы к  ступенчатому виду, выполняя прямой и обратный ходы гауссова  исключения. Последний столбец содержит решение системы.

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

 

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

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

В результате проведенных операций над системой линейных алгебраических уравнений в системе МаthCad с помощью метода Гаусса, мы нашли единственное значение, которое удовлетворяет поставленной задаче и записали его с точностью ε = .

 

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

 

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

2) Сулейманов Р. Р. Численные методы в системе MATHCAD, Башкирский институт развития образования, Уфа 2007

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

4) Р. В. Хемминг Численные методы (для научных работников и инженеров) М., 1972 г., 400 стр. с илл. Редактор Г. Я. Пирогова

5) Плис А. И. Сливина  Н.А. MathCAD: Математический практикум для экономистов и инженеров .-М.: финансы и статистика, 2000.656с