Курсовая работа по дисциплине:

«Информатика и программирование»

на тему:

«Система линейных алгебраических уравнений с матрицей порядка n методом Гаусса в среде программирования Turbo Pascal»

Задачей данной курсовой работы является создание программы решения систем линейных алгебраических уравнений с матрицей порядка n методом Гаусса в среде программирования Turbo Pascal.

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

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

- метод Гаусса;

- метод обращения матрицы;

- итерационные методы.

Матрица 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:

Рис.1. Ступенчатый вид матрицы

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

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

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

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

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

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

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-го уравнения на 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.1 Описание алгоритма решения СЛУ методом Гаусса

Пусть у нас есть система N линейных уравнений:

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + ... a_1Nx_N = b₁

a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + ... a_2Nx_N = b₂

a₃₁x₁ + a₃₂x₂ + a₃₃x₃ + ... a_3Nx_N = b₃

...

a_N1x₁ + a_N2x₂ + a_N3x₃ + ... a_NNx_N = b_N

где x_i - неизвестные, a_ij - коэффициенты при неизвестных, b_i - свободные члены в уравнениях, i,j пробегают значения от 1 до N.

Цель задачи - зная a_ij и b_i найти x_i.

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

Особенность этой системы - в строках с номером i все коэффициенты a_ij при j<i равны нулю.

Если мы смогли привести нашу систему уравнений к такому треугольному виду, то решить уравнения уже просто. Из последнего уравнения находим x_N= b_N / a_NN. Дальше подставляем его в предпоследнее уравнение и находим из него x_N-1. Подставляем оба найденных решения в следующее с конца уравнение и находим x_N-2. И так далее, пока не найдем x₁, на чем решение заканчивается. Такая процедура называется обратной прогонкой.

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

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

Нужно, чтобы во второй строке получилось уравнение, в которой отсутствует член при x₁. Прибавим к этой строке первую строку, умноженную на некоторое число M.

(a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + ... a_1Nx_N = b₁)*M +

a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + ... a_2Nx_N = b₂

Получим

(a₁₁*М + a₂₁) x₁ + ... = b₁*M + b₂

Для того, чтобы член при x₁ равнялся нулю, нужно, чтобы M = - a₂₁ / a₁₁. Проделав эту операцию, получившееся уравнение запишем вместо второго и приступим к третьему уравнению. К нему мы прибавим первое уравнение, умноженное на M = - a₃₁ / a₁₁ и тоже получим ноль вместо члена при x₁. Такую операцию нужно проделать над всеми остальными уравнениями. В результате получим систему такого вида:

После этого будем избавляться от членов при x₂ в третьем, четвертом, N-ом уравнении. Для этого нужно к уравнению с j-м номером прибавить 2-ое уравнение, умноженное на M = - a_j2 / a₂₂. Проделав эту операцию над всеми остальными уравнениями, получим систему где нет членов с x₂ в уравнениях с номером больше 2.

И так далее... Проделав это для третьего члена, четвертого... до тех пор, пока не кончатся уравнения, получим в итоге систему треугольного вида.

2.2 Блок-схема алгоритма решения задачи

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

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

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

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

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

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

Глава 3. Практическая реализация задачи

алгебраический уравнение гаусс turbo рascal

Program - оператор ввода заголовка программы.

ClrScr - процедура очистки экрана и возврата курсора в верхний левый угол.

Var - зарезервированное слово, которое означает, что далее будут описаны одна или несколько переменных.

Array [диапазон] of <тип данных> - массив. При описании массива используются зарезервированные слова Array и of (массив, из). За словом Array в квадратных скобках указывается диапазон, с помощью которого компилятор определяет общее число элементов массива. После слова of пишется тип данных, из которых будет состоять массив.

Begin … End - составной оператор, указывающий на начало и конец программы или составляющей части программы. Именно в этом разделе происходят все действия. Фактически, весь раздел операторов, обрамленный словами Begin . . . End, представляет собой один составной оператор. Поскольку зарезервированное слово End является закрывающей операторной скобкой, оно одновременно указывает и конец предыдущего оператора.

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

ReadLn - оператор используется для вызова встроенной процедуры ввода данных, и программа останавливается в ожидании ввода. В этот момент необходимо набрать на клавиатуре нужное число и нажать клавишу Enter. Сразу после этого программа продолжит работу: проанализирует введенное число и перейдет к вводу следующего числа или вычислению результата. Таким образом, сигналом окончания подготовки очередного числа является нажатие на клавишу Enter, до этого момента можно стирать любой ошибочно введенный символ клавишей Backspace.

:= (знак присваивания) - один из основных операторов. Пара символов «:=» означает «присвоить значение». Из толкования смысла оператора видно, что он используется для присваивания символу какого-либо значения, которое может быть выражено как набором символов, так и математическим выражением.

If <условие> then <оператор1> else <оператор2> - составной оператор, позволяющий проверить некоторое условие и в зависимости от результатов проверки выполнить то или иное действие. If, then, else - зарезервированные слова (если, то, иначе); <условие> - произвольное выражение логического типа; <оператор1>, <оператор2> - любые операторы языка Turbo Pascal. Условный оператор работает по следующему алгоритму. Вначале вычисляется условное выражение <условие>.

Если результат есть TRUE (истина), то выполняется <оператор1>, а <оператор2> пропускается; если результат есть FALSE (ложь), наоборот, <оператор1> пропускается, а выполняется <оператор2>.

For <пар_цик> := <нач_знач> to <кон_знач> do <оператор> - составной оператор. Здесь for, to, do - зарезервированные слова (для, до, выполнить);

<пар_цик> - параметр цикла - переменная типа integer;

<нач_знач> - начальное значение - выражение того же типа;

<кон_знач> - конечное значение - выражение того же типа;

<оператор> - произвольный оператор Borland Pascal.

При выполнении оператора For вначале вычисляется выражение <нач_знач> и осуществляется присваивание <пар_цик>: = <нач_знач>. После этого циклически повторяется:

1. проверка условия <пар_цик> <= <кон_знач>; если условие не выполнено, оператор For завершает свою работу;

2. выполнение оператора <оператор>;

3. наращивание переменной <пар_цик> на единицу.

3.2 Реализация программы

max:=abs(a[i,k]); { сохраняем его значение в max }

В результате решения поставленной задачи получили программу, решающую системы линейных уравнений методом Гаусса. Процесс набора программы в среде Turbo Pascal показан на рисунках 2 и 3.

Рис.2. Процесс набора программы в среде Turbo Pascal

Рис.3. Процесс набора программы в среде Turbo Pascal

При проверке на наличие ошибок - ошибок не найдено (рис.4).

Рис.4. Проверка на наличие ошибок

Для проверки работы программы рассмотрим конкретный пример.

Пусть дана система линейных уравнений размерностью 4:

Составим расширенную матрицу системы.

А* =

Таким образом, исходная система может быть представлена в виде:

,

откуда получаем: x₃ = 2; x₂ = 5; x₁= 1.

Теперь введем размерность и коэффициенты при неизвестных заданной системы в программу. Получим решение: x₁= 1; x₂ = 5; x₃ = 2 (рис.5). Таким образом, результаты тестирования на ЭВМ и ручного счета совпали, программа работает правильно.

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

Заключение

1. Ильин В. А., Позняк Э. Г. Линейная алгебра: Учебник для вузов/6-е изд., стер. - М.: ФИЗМАТЛИТ, 2004. - 280 с.

2. Кассера В.Ф. Turbo Pascal 7.0. - Диасофт, 2003. - 345 с.

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

4. Культин Н.Б. Turbo Pascal в задачах и примерах. - СПб:БХВ - Петербург, 2002. - 256с.: ил.

5. Моргун А. Н. Программирование на языке Паскаль (Pascal). Основы обработки структур данных. - М.: Диалектика, 2006. - 608 с.

6. Фаронов В.В. Turbo Pascal. Наиболее полное руководство. - BHV-Санкт-Петербург, 2007. - 571 с.

7. http://ru.wikipedia.org/wiki/Turbo_Pascal

Приложение