50398 (Вычисление определителя матрицы прямым методом)

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

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

Государственное образовательное учреждение высшего профессионального образования

Тульский государственный университет

Кафедра “Автоматика и телемеханика”

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА К КУРСОВОЙ РАБОТЕ

по дисциплине: «Программирование на языке высокого уровня»

на тему: «Вычисление определителя матрицы прямым методом»

Выполнил: студент группы 260661

Ю.В. Красов

Проверил: ассистент кафедры АТМ

А.С. Карцева

Тула 2008

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ВЫБОР И ОБОСНОВАНИЕ ЧИСЛЕННОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ

1. Определение матрицы

2. Определение детерминанта

3. Метод исключения Гаусса. Вычисление определителя методом исключения

1. АЛГОРИТМ РАБОТЫ ПРОГРАММЫ

1. Структура алгоритма и данных

2. Схема алгоритма

1. ТЕКСТ ПРОГРАММЫ

   1. Описание переменных и структур данных

   2. Текст программы на языке Pascal

2. ТЕСТОВАЯ ЗАДАЧА

   1. Математическое решение задачи

   2. Решение, полученное с использованием разработанного программного обеспечения

3. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

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

Основополагающими средствами изучения математических моделей являются аналитические методы: получение точных решений в частных случаях (например, табличные интегралы), разложения в ряды. Определенную роль издавна играли приближенные вычисления. Например, для вычисления определенного интеграла использовались квадратурные формулы.

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

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

С использованием компьютера стал возможен вычислительный эксперимент, т. e. расчет в целях проверки гипотез, а также в целях наблюдения за поведением модели, когда заранее не известно, что именно заинтересует исследователя. В процессе численного эксперимента происходит по существу уточнение исходной математической постановки задачи. В процессе расчетов на компьютере происходит накопление информации, что дает возможность в конечном счете произвести отбор наиболее интересных ситуаций. На этом пути сделано много наблюдений и открытий, стимулирующих развитие теории и имеющих важные практические применения.

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

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

Разнообразие задач, где могут быть использованы компьютеры, очень велико. Для решения каждой задачи нужно знать многое, связанное именно с этой задачей.

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

1. ВЫБОР И ОБОСНОВАНИЕ ЧИСЛЕННОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ

1. Определение матрицы

Матрицей называют совокупность чисел, расположенных в прямоугольной таблице

,

состоящей из m строк и n столбцов.

Числа называют элементами матрицы. Первый индекс в обозначении элемента ( i ) указывает на номер строки, а второй индекс ( j )- на номер столбца, в которых расположен этот элемент.

В нашем случае ( ) матрица называется прямоугольной размера . Если число строк в матрице равно числу столбцов (m=n), то матрицу называют квадратной порядка m.

1. Определение детерминанта

Для квадратной матрицы может быть введено понятие детерминанта (определителя). Детерминант матрицы [A] обозначают

6

или .

Детерминантом матрицы порядка n>1 называют число

, (1)

где - детерминант матрицы порядка n-1, полученной из матрицы [A] вычеркиванием первой строки и k -ого столбца.

Матрица порядка 1 состоит из одного числа, и ее детерминант по определению считают равным этому числу:

(2)

Детерминант матрицы второго порядка в соответствии с (1) и (2) можно вычислить по следующей формуле:

.

Для матрицы третьего порядка

В соответствии с определением детерминант матрицы четвертого порядка может быть выражен через определитель третьего порядка, тот в свою очередь через определители второго порядка и т.д.

Число называют дополнительным минором элемента . Для произвольного элемента матрицы также можно ввести понятия дополнительного минора: - это определитель матрицы, получаемой из исходной вычеркиванием i -ой строки и j-ого столбца. Например, для матрицы [A] третьего порядка дополнительным минором элемента будет определитель

Одним из важных свойств определителей является то, что при перестановке местами двух строк или двух столбцов определителя, он должен быть умножен на -1:

.

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

1. Метод исключения Гаусса. Вычисление определителя методом исключения

Пусть дана матрица

Метод Гаусса можно интерпретировать как метод, в котором матрица приводится к верхней треугольной форме (прямой ход).

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

Запишем общие формулы метода Гаусса. Пусть проведено исключение к элементов из (k-1)-го столбца. Тогда останутся строки с ненулевыми элементами ниже главной диагонали.

Умножим k-ю строку на число

m > k (3)

и вычтем из m-й строки. Первый ненулевой элемент этой строки обратится в нуль, а остальные изменятся по формулам

( 4)

k < m(5)

Проведя вычисления по этим формулам при всех указанных индексах, обратим в нуль элементы k-го столбца, лежащие ниже главной диагонали. Аналогичная процедура приводит матрицу системы к верхней треугольной форме, при этом весь процесс приведения называется прямым ходом метода Гаусса.

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

(6)

где k- количество перестановок строк при использовании метода исключения с выбором главного элемента.

На некотором шаге прямого хода может оказаться, что коэффициент но мал по сравнению с остальными элементами матрицы системы и, в частности, мал по сравнению с элементами первого столбца. Деление коэффициентов системы на малую величину может привести к значительным ошибкам округления.

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

Важным достоинством данного метода, является то, что вычисление определителя требует примерно (2/3)n³ операций, что несравнимо меньше с операциями, при вычислении определителя по правилу Крамера, поэтому метод Гаусса с выбором главного элемента наиболее применим при обработке данных на компьютере.