/>/>/>Федеральное агентство по образованию
Государственное образовательноеучреждение высшего профессионального образованияТульскийгосударственный университет
Кафедра “Автоматика и телемеханика”
ПОЯСНИТЕЛЬНАЯ ЗАПИСКАК КУРСОВОЙ РАБОТЕ
по дисциплине:«Программирование на языке высокого уровня»
на тему: «Вычисление определителя матрицы прямым методом»
Выполнил: студент группы 260661
Ю.В. Красов
Проверил: ассистент кафедры АТМ
А.С. Карцева
Тула 2008
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1. ВЫБОР И ОБОСНОВАНИЕЧИСЛЕННОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ
1.1 Определение матрицы
1.2 Определение детерминанта
1.3 Метод исключенияГаусса. Вычисление определителя методом исключения
2. АЛГОРИТМ РАБОТЫПРОГРАММЫ
2.1 Структура алгоритма иданных
2.2 Схема алгоритма
3. ТЕКСТ ПРОГРАММЫ
3.1 Описание переменных иструктур данных
3.2 Текст программы наязыке Pascal
4. ТЕСТОВАЯ ЗАДАЧА
4.1 Математическое решение задачи
4.2 Решение, полученное с использованиемразработанного программного обеспечения
5. ИНСТРУКЦИЯПОЛЬЗОВАТЕЛЮ
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ВВЕДЕНИЕ
Современная математика ориентирована наиспользование компьютеров для прикладных расчетов. Любые математические приложенияначинаются с построения модели явления (изделия, действия, ситуации или другогообъекта), к которому относится изучаемый вопрос. Классическими примерамиматематических моделей могут служить определенный интеграл, уравнение колебаниймаятника, уравнение теплообмена, уравнения упругости, уравненияэлектромагнитных волн и другие уравнения математической физики и даже модель формальныхрассуждений – алгебру Буля.
Основополагающими средствами изученияматематических моделей являются аналитические методы: получение точных решенийв частных случаях (например, табличные интегралы), разложения в ряды. Определеннуюроль издавна играли приближенные вычисления. Например, для вычисленияопределенного интеграла использовались квадратурные формулы.
Появления в начале XX века электронных вычислительных машин(компьютеров) радикально расширило возможности приложения математическихметодов в традиционных областях (механике, физике, технике) и вызвало бурноепроникновение математических методов в нетрадиционные области (управление,экономику, химию, биологию, психологию, лингвистику, экологию и т.п.).
Компьютер дает возможность запоминатьбольшие (но конечные) массивы чисел и производить над ними арифметическиеоперации и сравнения с большой (но конечной) скоростью по заданной вычислителемпрограмме. Поэтому на компьютере можно изучать только те математические модели,которые описываются конечными наборами чисел, и использовать конечныепоследовательности арифметических действий, а также сравнений чисел по величине(для автоматического управления дальнейшими вычислениями).
С использованием компьютера стал возможенвычислительный эксперимент, т. e. расчет вцелях проверки гипотез, а также в целях наблюдения за поведением модели, когдазаранее не известно, что именно заинтересует исследователя. В процессечисленного эксперимента происходит по существу уточнение исходной математическойпостановки задачи. В процессе расчетов на компьютере происходит накоплениеинформации, что дает возможность в конечном счете произвести отбор наиболее интересныхситуаций. На этом пути сделано много наблюдений и открытий, стимулирующихразвитие теории и имеющих важные практические применения.
С помощью компьютера возможно применениематематических методов и в нетрадиционных областях, где не удается построитькомпактные математические модели вроде дифференциальных уравнений, но удаетсяпостроить модели, доступные запоминанию и изучению на компьютере. Модели длякомпьютеров в этих случаях представляют собой цифровое кодирование схемы,изучаемого объекта (например, языка) и отношений между его элементами (словами,фразами). Сама возможность изучения таких моделей на компьютере стимулируетпоявление этих моделей, а для создания обозримой модели необходимо выявлениезаконов, действующих в исходных объектах. С другой стороны, получаемые накомпьютере результаты (например, машинный перевод упрощенных текстов с одногоязыка на другой) вносят критерий практики в оценку теорий (например,лингвистических теорий), положенных в основу математической модели.
Благодаря компьютерам стало возможнымрассматривать вероятностные модели, требующие большого числа пробных расчетов,имитационные модели, которые отражают моделируемые свойства объекта безупрощений (например, функциональные свойства телефонной сети).
Разнообразие задач, где могут бытьиспользованы компьютеры, очень велико. Для решения каждой задачи нужно знатьмногое, связанное именно с этой задачей.
Численные методы решения систем линейных алгебраическихуравнений в линейной алгебре называют первой основной задачей. К ней примыкаютзадачи вычисления определителей и элементов обратной матрицы, которые иногданазывают второй и третьей основными задачами линейной алгебры. В данной работеописаны методы вычисления определителя матрицы и разработана программа для еговычисления с использованием компьютера, основанная на применении метода Гауссас выбором главного элемента.
1. ВЫБОР И ОБОСНОВАНИЕ ЧИСЛЕННОГО МЕТОДАРЕШЕНИЯ ЗАДАЧИ
1.1 Определениематрицы
Матрицейназывают совокупность чисел, расположенных в прямоугольной таблице
/>,
состоящей из m строк и n столбцов.
Числа />называют элементами матрицы.Первый индекс в обозначении элемента ( i ) указывает на номер строки, а второй индекс ( j )- на номер столбца, в которых расположен этот элемент.
В нашем случае (/>) матрица называется прямоугольной размера />. Если число строк вматрице равно числу столбцов (m=n), то матрицу называют квадратной порядка m.
1.2 Определениедетерминанта
Для квадратной матрицы может быть введенопонятие детерминанта (определителя). Детерминант матрицы [A] обозначают />
6 или />.
Детерминантом матрицы /> порядка n>1 называют число
/> , (1)
где /> - детерминант матрицы порядка n-1, полученной из матрицы [A] вычеркиванием первой строки и k -ого столбца.
Матрица порядка 1 состоит из одного числа,и ее детерминант по определению считают равным этому числу:
/> (2)
Детерминант матрицы второго порядка всоответствии с (1) и (2) можно вычислить по следующей формуле:
/>.
Для матрицы третьего порядка
/>
В соответствии с определением детерминантматрицы четвертого порядка может быть выражен через определитель третьегопорядка, тот в свою очередь через определители второго порядка и т.д.
Число /> называют дополнительным миноромэлемента />.Для произвольного элемента /> матрицы также можно ввестипонятия дополнительного минора: /> - это определитель матрицы,получаемой из исходной вычеркиванием i -ойстроки и j-ого столбца. Например, для матрицы [A] третьего порядка дополнительным минором элемента /> будетопределитель
/>
Одним из важных свойств определителейявляется то, что при перестановке местами двух строк или двух столбцовопределителя, он должен быть умножен на -1:
/>.
При непосредственном вычисленииопределителей вышеприведенным способом, для отыскания решения системы линейныхуравнений по правилу Крамера требуется приблизительно /> арифметических операций типаумножения. Использование метода исключения Гаусса позволяет уменьшить время,необходимое для решения задачи, до величины менее одной секунды.
1.3 Методисключения Гаусса. Вычисление определителя методом исключения
Пусть дана матрица
/>
Метод Гаусса можно интерпретировать какметод, в котором матрица приводится к верхней треугольной форме (прямой ход).
Приведем матрицу к верхней треугольной.Вычтем из второй строки первую, умноженную на такое число, при котором первыйэлемент второй строки обратится в нуль. То же проделаем со всеми остальнымистроками. В результате все элементы первого столбца, лежащие ниже главнойдиагонали, обратятся в нуль. Затем, используя вторую строку, обратим в нульсоответствующие элементы второго столбца. Последовательно продолжая этотпроцесс, приведем матрицу систему к верхней треугольной форме.
Запишем общие формулы метода Гаусса. Пустьпроведено исключение к элементов из (k-1)-гостолбца. Тогда останутся строки с ненулевыми элементами ниже главной диагонали.
Умножим k-ю строку на число
/>/> m > k (3)
и вычтем из m-й строки. Первый ненулевой элемент этой строки обратится в нуль,а остальные изменятся по формулам
/>(4)
/> k
Проведя вычисления по этим формулам привсех указанных индексах, обратим в нуль элементы k-го столбца, лежащие ниже главной диагонали. Аналогичная процедураприводит матрицу системы к верхней треугольной форме, при этом весь процессприведения называется прямым ходом метода Гаусса.
Определитель треугольной матрицы равенпроизведению диагональных элементов. В результате выполнения прямого ходаметода исключения система линейных уравнений приводится к верхней треугольнойматрице. Следовательно, определитель матрицы системы может быть вычислен какпроизведение диагональных элементов:
/>(6)
где k- количество перестановок строк при использовании методаисключения с выбором главного элемента.
На некотором шаге прямого хода можетоказаться, что коэффициент /> но мал по сравнению с остальнымиэлементами матрицы системы и, в частности, мал по сравнению с элементамипервого столбца. Деление коэффициентов системы на малую величину может привестик значительным ошибкам округления.
/>Для уменьшения ошибок округленияпоступают следующим образом. Среди элементов первого столбца /> каждой промежуточнойматрицы выбирают наибольший по модулю (главной) элемент и путем перестановки i-го строки со строкой, содержащей главный элемент, добиваютсятого, что главный элемент становится ведущим. Такая модификация методаисключения Гаусса называется методом Гаусса с выбором главного элемента. Случайпоявления нулевых элементов обходится при этом сам собой.
Важным достоинством данного метода,является то, что вычисление определителя требует примерно (2/3)n³ операций, что несравнимо меньше с /> операциями, привычислении определителя по правилу Крамера, поэтому метод Гаусса с выборомглавного элемента наиболее применим при обработке данных на компьютере.
2. АЛГОРИТМРАБОТЫ ПРОГРАММЫ
2.1 Структураалгоритма и данных
Задача вычисления определителя матрицыразбивается на несколько подзадач:
1) Заполнение массиваначальными данными;
2) Изменение порядкаматрицы по желанию пользователя и заполнение нового массива;
3) Ввод и фильтрациявводимых пользователем данных в массив;
4) Вычислениедетерминанта;
4.1) Ввод исходных данных в массив
4.2) Выбор главного элемента;
4.3) Замена строк местами;
4.4) Заполнение нового массива;
4.5) Приведение матрицы к верхнемутреугольному виду;
4.6) Вычисление определителя матрицы.
Согласно вышеприведенной структуре,программа будет состоять из четырех подпрограмм:
1) Подпрограмма созданияформы и ввода начальных данных в массив.
В данной подпрограмме задается начальноечисло столбцов и строк матрицы (ее порядок), вводятся заголовки матрицы, строки столбцов в соответствии с заданным размером.
2) Подпрограмма измененияпорядка матрицы;
В данной подпрограмме формируется новаяматрица, исходя из данных, введенных пользователем, вводятся новые заголовкиматрицы, строк и столбцов в соответствии с заданным размером.
3) Подпрограммафильтрации вводимых пользователем данных, при нажатии на кнопки клавиатуры;
Данная подпрограмма разрешает пользователювводить в матрицу только цифры, разделитель дробной и целой части и знак «-».Ввод других символов запрещается. Также в этой подпрограмме производится заменаневерного разделителя на верный.
4) Подпрограммавычисления определителя.
В данной подпрограмме происходитзаполнение массива данных, поочередно для каждого столбца производится выборглавного элемента (наибольшего по модулю), затем строки меняются местами ипроизводится приведение матрицы к верхней треугольной форме, т.е. когда нижеглавной диагонали содержатся только нулевые элементы. Согласно вышеприведеннымформулам производится вычисление значения детерминанта и полученный результатвыводится на экран.
2.2 Схемаалгоритма
На рисунке 1 представлен алгоритм работыпрограммы при возникновении события OnCreate.Процедура TForm1.FormCreate(Sender: TObject).
/>
Рис. 1. Алгоритм работы программы при возникновениисобытия OnCreate
На рисунке 2 представлен алгоритм работыпрограммы при нажатии на кнопку «Изменить размерность массива». ПроцедураTForm1.Button2Click(Sender: TObject).
/>
Рис. 2. Алгоритм работы программы принажатии на кнопку «Изменить размерность массива»
На рисунке 3 представлен алгоритм работыпрограммы при вводе данных с клавиатуры (событие OnKeyPress). Процедура TForm1.StringGrid1KeyPress(Sender: TObject; varKey: Char).
/>
Рис. 3. Алгоритм работы программы при привводе данных с клавиатуры (событие OnKeyPress).Процедура TForm1.StringGrid1KeyPress(Sender: TObject; var Key: Char)
На рисунке 4 представлен алгоритм работыпрограммы при нажатии на кнопку «Расчет». Процедура TForm1.Button1Click(Sender:TObject).
алгоритм программа pascalматрица определитель
/>
/>
/>
/>
Рис. 4. Алгоритм работы программы принажатии на кнопку «Расчет»
3. ТЕКСТПРОГРАММЫ
3.1 Описание переменных иструктур данных
При выполнении программы используются следующие переменные:N – максимальное число строк (столбцов)массива; r, c, max, j, z, p, s, zam – номера строк и столбцов и количествопроизводимых замен строк – все они являютсяпеременными типа integer (целое), переменные detA, k, buf – детерминант,коэффициент и буфер, используемый при замене строк – переменные типа extended(действительное число), а также переменная А – массив, тип массива – двумерный(Massiv = array[1..Nmax,1..Nmax] of extended).
При запуске программы возникает событие «создание формы»(OnCreate), процедура TForm1.FormCreate(Sender: TObject). При этом задаетсяколичество строк и столбцов двумерного массива (по умолчанию 4 и 4)StringGrid1.RowCount := N+1; StringGrid1.ColCount := N+1; но ячейки первойстроки и первого столбца не редактируемые, они используются для вывода надписейнад строками и столбцами, для чего используются функции StringGrid1.Cells [0,r]:= ' r = ' + IntToStr(r) и StringGrid1.Cells [c,0] := ' c = ' + IntToStr(c).Вывод данных поочередно в каждую из этих ячеек производится посредствомстандартной инструкции for … to … do begin … end.
Нажатие на кнопку /> влечет за собой возникновениесобытия OnClick процедура TForm1.Button2Click(Sender: TObject). Данные околичестве строк и столбцов массива считываются из поля Edit1. Так какчисленное значение переменной N имеет целочисленный тип для преобразования строковойзаписи числа, находящегося в переменной Edit1.Text в целое, используется стандартнаяфункция N:=StrToInt(Edit1.Text).
20 При вводе пользователем данных в полеStringGrid1 происходит событие OnKeyPress, процедура TForm1.StringGrid1KeyPress(Sender: TObject; varKey: Char). Посредством стандартной инструкции case Key of, которая позволяетреализовать множественный выбор, происходит фильтрация вводимых пользователемданных. Разрешается ввод только цифр, разделителя (DecimalSeparator), знака«минус» и нажатие клавиши Backspace. Посредством инструкции if Key DecimalSeparator thenпроизводится выбор одиного из двух возможных вариантов развития программы:разделитель заменяется на правильный, если он введен неверно (Key :=DecimalSeparator), либо разделитель оставляется без изменений. Ввод остальныхсимволов запрещается (else key := Chr(0)).
При нажатии на кнопку /> возникает событие (OnClick),процедура TForm1.Button1Click(Sender: TObject). Задаются начальные значения переменныхmax:= 1, detA := 1, zam:=0. Производится заполнение массива(A[c,r]:=StrToFloat(StringGrid1.Cells[c,r])), свойство StringGrid1.Cells[c,r] определяет содержимое ячейки с табличными координатами (c,r), строковые значения переменных,находящихся в ячейках (c,r) преобразуются в вещественный типпосредством стандартной инструкции StrToFloat. Стандартнаяинструкция for … to … do begin … end позволяет выполнять несколько раздействия, заключенные в этой инструкции. Функция abs(A[c,j]) возвращает модульаргумента.
Инструкция if (stringgrid1.cells [c,r] > stringgrid1.cells [c-1,r]) and (stringgrid1.cells [c,r]
Выход из программы осуществляется нажатием кнопки />.
3.2 Текст программы на языкеPascal
unit Unit1;
interface
uses
Windows, Messages, SysUtils,Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids,Menus, Buttons;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Button1: TButton;
Edit1: TEdit;
Label1: TLabel;
Label3: TLabel;
Button2: TButton;
BitBtn1: TBitBtn;
BitBtn2: TBitBtn;
procedure FormCreate(Sender:TObject);
procedure Button2Click(Sender:TObject);
procedure Button1Click(Sender:TObject);
procedure BitBtn1Click(Sender:TObject);
procedureStringGrid1KeyPress(Sender: TObject; var Key: Char);
private
{ Private declarations }
public
{ Public declarations }
end;
const
Nmax=10;
Type
Massiv1 =array[1..Nmax,1..Nmax] of extended;
var
Form1: TForm1;
A: Massiv1;
N, r, c: integer;
implementation
{$R *.dfm}
procedureTForm1.FormCreate(Sender: TObject);
begin
N := 4;
Edit1.Text := FloatToStr(N);
StringGrid1.RowCount := N+1;
StringGrid1.ColCount := N+1;
Label3.Caption := ' для вычисления определителя матрицынажмите расчет';
StringGrid1.Cells [0,0] := 'Матрица А';
for r := 1 to N do begin
StringGrid1.Cells [0,r] := ' строка ' + IntToStr(r);
end;
for c := 1 to N do begin
StringGrid1.Cells [c,0] := ' столбец ' + IntToStr(c);
end;
end;
procedureTForm1.Button2Click(Sender: TObject);
begin
N:=StrToInt(Edit1.Text);
StringGrid1.RowCount:=N+1;
StringGrid1.ColCount:=N+1;
for r := 1 to N do begin
StringGrid1.Cells [0,r] := ' строка ' + IntToStr(r);
end;
for c := 1 to N do begin
StringGrid1.Cells [c,0] := ' столбец ' + IntToStr(c);
end;
end;
procedureTForm1.Button1Click(Sender: TObject);
var
detA, k, buf: extended;
max, j, z, p, s, zam:integer;
begin
max:= 1;
detA := 1;
zam:=0;
for c := 1 to N do
for r := 1 to N do
A[c,r]:=StrToFloat(StringGrid1.Cells[c,r]);
for c := 1 to N-1 do begin
for z := c to N-1 do begin
max:=z;
for j := z+1 to N do begin
if abs(A[c,j]) >abs(A[c,max]) then
max:=j;
end;
for p := 1 to N do begin
buf:=A[p,z]; A[p,z]:=a[p,max];A[p,max]:=buf;
end;
end;
for r := c+1 to N do begin
k := A[c,r]/A[c,c];
for s := 1 to N do begin
A[s,r]:= A[s,r]-A[s,c]*k;
end;
end;
if cmax then begin
zam := zam+1;
end;
end;
for c := 1 to N do
detA := detA*A[c,c];
if zam mod 2 0 then
detA := (-1)*detA;
label3.Caption := 'Детерминант матрицы равен:' + FloatToStrF(detA,fffixed,6,3);
end;
procedureTForm1.BitBtn1Click(Sender: TObject);
begin
MessageDlg(Программа вычисляет детерминант(определитель) матрицы методом Гаусса с выбором главного элемента. Внимание!!! Матрица должна быть квадратной!',mtInformation,[mbOK],0);
end;
procedureTForm1.StringGrid1KeyPress(Sender: TObject; var Key: Char);
begin
case Key of
#8,'0'..'9', '-': ;
'.',',':
begin
if Key DecimalSeparatorthen
Key := DecimalSeparator;
end;
else
key := Chr(0)
end;
end;
end.
4. ТЕСТОВАЯЗАДАЧА
4.1 Математическоерешение задачи
В матрице вида
/>
Определить детерминант.
Решение:
Вычисление определителя данной матрицывручную целесообразно производить с помощью разложения элементов по 1-й строкепо формуле (1). В итоге получится:
/>(7)
Воспользовавшись правилом Саррюса(правилом треугольников), вычисляются определители третьего порядка входящие всостав выражения (7):
detA = 4(10∙7∙2+(-20) ∙3∙5+5∙7∙10-5∙7∙10-10∙7∙3-5∙(-20)∙2)-7∙(7,5∙7∙2+(-20) ∙3∙2+7∙3∙10-10∙7∙2-(-20)∙3∙2-7,5∙7∙3)+5∙(7,5∙5∙2+10∙3∙2+3∙5∙10-10∙5∙2-10∙3∙2-3∙5∙7,5)-6∙(7,5∙5∙7+3∙5∙(-20)+10∙7∙2-(-20)∙5∙2-10∙3∙7-7,5∙7∙5)
detA = 4∙(140-300+350-350-210+200)-7∙(105-120+210-140+120-157,5)+5∙(75+60+150-100-60-112,5)-6∙(262,5-300+140+200-210-262,5)
detA = 4∙(-170)-7∙17,5+5∙12,5-6∙(-170)
detA = 280
Ответ: определитель матрицы равен 280
4.2 Решение,полученное с использованием разработанного программного обеспечения
Введя исходные данные в программу получимследующий результат: «Определитель матрицы равен: 280». Результат, полученный сиспользованием разработанной программы соответствует результату, вычисленномуматематически.
Вывод: разработанное программноеобеспечение верно вычисляет определитель произвольной матрицы.
5. ИНСТРУКЦИЯПОЛЬЗОВАТЕЛЮ
Для запуска программы необходимо запуститьфайл Determinant.exe, дваждыщелкнув по нему мышью. В появившемся окне при необходимости изменить порядокматрицы, введя значение в поле напротив надписи «Порядок матрицы» и нажав накнопку «Изменить порядок матрицы». В ячейках таблицы ввести значения элементовматрицы. Вводимые данные должны являться действительными числами, содержатьтолько цифры, знак « — » и разделитель целой и дробной части. После заполненияВСЕХ элементов матрицы нажать кнопку «Расчет». Ответ будет написан под таблицейв формате: «Детерминант матрицы равен: -280,000»
Выход из программы осуществляется спомощью кнопки />.
Внешний вид окна программы представлен нарисунке 5.
/>
Рис. 5. Внешний вид окна программы
ЗАКЛЮЧЕНИЕ
В данной работе были изучены численные методы нахождения определителя матрицы и выбран наиболееоптимальный, с точки зрения реализации его на компьютере – метод исключения свыбором главного элемента. Написана программас использованием массивов. Данная программа позволяет определить детерминантматрицы размером N×N, размер матрицы задается пользователем, вводимые данные –действительные числа. Вычисление определителя матрицы является второй главнойзадачей линейной алгебры, и применяется при решении сложных систем линейныхуравнений с несколькими неизвестными./>
28
СПИСОК ИСПОЛЬЗОВАННЫХИСТОЧНИКОВ
1. Методические указания по выполнению курсовых работ подисциплине «программирование» для студентов дневной формы обучения, обучающихся попрограмме направлений подготовки бакалавров 550200, 553000, 552800. РазработалО.С. Середин, к.ф.-м.н., доцент каф. АТМ. Тула 2003 г.
2. Бахвалов Н.С.,Жидков Н.П. Кобельков Г.М. Численные методы. – М.: ЛабораторияБазовых Знаний, 2000, – 624с.
3. ВолосевичА.А. Язык Object Pascal и система программирования Delphi. Учебное пособие. Минск:Белорусский государственный университет информатики и радиоэлектроники, 2003, — 61с.
4.
29 Курс лекцийпо дисциплине «вычислительная математика
29 . Тула 2007,- 162с.