Определение ранга матрицы методом окаймляющих миноров
Определение понятий матрицы и ранга матрицы, а также описание алгоритма Гаусса. Анализ сути метода окаймляющих миноров. Характеристика алгоритма и пример вычисления ранга матрицы методом окаймляющих миноров. Анализ вычислительной сложности алгоритма.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 17.03.2017 |
| Размер файла | 364,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
Аннотация
Введение
1. Теоретический раздел
1.1 Основные определения
1.2 Суть метода окаймляющих миноров
1.3 Пример нахождения ранга матрицы методом окаймления миноров
2. Практический раздел
2.1 Формальная постановка задачи
2.2 Алгоритм вычисления ранга матрицы методом окаймляющих миноров
2.3 Анализ вычислительной сложности алгоритма
Заключение
Список использованной литературы
Аннотация
В данной курсовой работе будет рассматриваться способ определения ранга матрицы под названием «Метод окаймляющих миноров». Этот метод работает с матрицами любого размера на основе понятий «минор» и «окаймляющий минор». Задание на работу - разработка и анализ алгоритма данного метода, определяет приемы, которые будут использоваться в работе. Особенность метода состоит в том, что в лучшем случае время работы алгоритма будет значительно меньше, чем при использовании других алгоритмов, задающихся той же целью. Формально целью работы является алгоритмизация задач выделения окаймляющего минора на основе данного и нахождения детерминанта квадратной матрицы методом алгебраических дополнений. При разработке алгоритма использованы приемы рекурсивного использования алгоритмов, в результате чего возрастает временная сложность алгоритма, однако алгоритм в таком виде более понятен читателю.
Курсовая работа выполнена на листах формата А4, содержит страниц машинописного текста.
Алгоритм представлен в виде блок-схемы.
Введение
Целью курсовой работы является разработка алгоритма, позволяющего осуществить нахождение ранга заданной матрицы методом окаймляющих миноров. Ход работы включил в себя несколько этапов:
- изучение теоретического материала по теме;
- создание алгоритма вычисления ранга матрицы методом окаймляющих миноров;
- создание блок-схемы;
- решение контрольной задачи по нахождению ранга произвольно заданной матрицы размера nЧm.
Результат может быть использован в процессе выполнения интуитивных расчетов по оценке характеристик систем управления технологическими процессами.
1. Теоретический раздел
1.1 Основные определения
Матрицей A размера mЧn называется прямоугольная таблица чисел, функций или алгебраических выражений, содержащая m строк и n столбцов:
A =.
Числа m и n определяют размер матрицы [1, с. 4].
Матрица называется квадратной n-го порядка, если число ее строк равно числу столбцов и равно n [1, с. 4].
Матрица любого размера называется нулевой, или нуль-матрицей, если все ее элементы равны нулю [1, с. 5].
Последовательность a11, a22, ..., ann диагональных матричных элементов образует главную диагональ квадратной матрицы, идущую из ее левого верхнего угла в правый нижний угол. Последовательность an1, a(n-1)2, ..., a1n матричных элементов образует побочную диагональ квадратной матрицы, идущую из ее левого нижнего угла в правый верхний угол [1, с. 5].
Минором Mij элемента aij квадратной матрицы n-го порядка A называется определитель(n?1)-го порядка, получающийся из определителя матрицы A вычеркиванием i-й строки и j-го столбца (той строки и того столбца, на пересечении которых располагается элемент aij) [1, с. 46].
Определителем |A| матрицы первого порядка A= (a11), или определителем первого порядка, называется число ?1, равное матричному элементу a11: ?1=|A|=a11 [1, с. 29].
Определителем |A| матрицы второго порядка A = (aij), или определителем второго порядка, называется число ?2, определяемое формулой:
?2 = |A| = = a11·a22?a12·a21 [1, с. 29].
Определителем |A| матрицы третьего порядка A = (aij), или определителем третьего порядка, называется число ?3, определяемое формулой:
?3=|A|= =
=a11*a22*a33 + a12*a23*a31 + a13*a21*a32 - a13*a22*a31 - a12*a21*a33 ? a11*a23*a32 [1, с. 29].
Рангом матрицы называют максимальный порядок её миноров, среди которых есть хотя бы один, не равный 0 [2].
Метод решения СЛАУ Гаусса заключается в последовательном исключении переменных из каждого уравнения до тех пор, пока в каждом уравнении не останется только по одной переменной. Если n=m, то можно говорить, что алгоритм Гаусса стремится привести матрицу A системы к единичной матрице -- ведь после того как матрица стала единичной, решение системы очевидно -- решение единственно и задаётся получившимися коэффициентами bi. При этом алгоритм основывается на двух простых эквивалентных преобразованиях системы: во-первых, можно обменивать два уравнения, а во-вторых, любое уравнение можно заменить линейной комбинацией этой строки (с ненулевым коэффициентом) и других строк (с произвольными коэффициентами). На первом шаге алгоритм Гаусса делит первую строку на коэффициент a11. Затем алгоритм прибавляет первую строку к остальным строкам с такими коэффициентами, чтобы их коэффициенты в первом столбце обращались в нули -- для этого, очевидно, при прибавлении первой строки к i-ой надо домножать её на - ai1. При каждой операции с матрицей A (деление на число, прибавление к одной строке другой) соответствующие операции производятся и с вектором b; в некотором смысле, он ведёт себя, как если бы он был m+1-ым столбцом матрицы A. В итоге, по окончании первого шага первый столбец матрицы A станет единичным (т.е. будет содержать единицу в первой строке и нули в остальных). Аналогично производится второй шаг алгоритма, только теперь рассматривается второй столбец и вторая строка: сначала вторая строка делится на a22, а затем отнимается от всех остальных строк с такими коэффициентами, чтобы обнулять второй столбец матрицы A. И так далее, пока мы не обработаем все строки или все столбцы матрицы A. Если n=m, то по построению алгоритма очевидно, что матрица A получится единичной, что нам и требовалось [3].
1.2 Суть метода окаймляющих миноров
Метод окаймляющих миноров объясняется двумя пунктами:
1. Пусть минор M k -го порядка не равен нулю, то переходим ко 2 пункту.
2. Если окаймляющие миноры для минора M (k+1) -го порядка, составить невозможно (т.е. матрица содержит k строк или k столбцов), то ранг равен k. Если окаймляющие миноры существуют и все равны нулю, то ранг равен k. Если среди окаймляющих миноров есть хотя бы один, не равный нулю, то повторяем для него пункт №1, приняв k+1 вместо k.
1.3 Пример нахождения ранга матрицы методом окаймления миноров
Найти ранг матрицы
A=
методом окаймляющих миноров.
Решение:
Т.к. данная матрица не нулевая то соответственно существует минор 1-го порядка, следовательно, ранг матрицы A ? 1.
Найдём минор второго порядка начнём с левого верхнего угла и вычислим минор второго порядка:
M2(1)=0
Рассмотрим следующий минор 2 порядка:
M2( 2 )=
Найдём минор 3 порядка начнём с левого верхнего угла и вычислим минор 3 порядка:
M3(1)= = 1·0·1+3·1·2+3·0·6-3·0·2-1·1·6-3·0·1=0+6+0-0-6-0=0
M3(2) = = 3·1·(-2) + 3·2·6 + 4·0·1 - 4·1·6 - 3·2·1 - 3·0·(-2)=
= -6 + 36 + 0 - 24 - 6 + 0 = 0
Таким образом ранг матрицы A = 2 т.к. все миноры третьего порядка равны нулю.
2. Практический раздел
2.1 Формальная постановка задачи
В ходе алгоритмизации метода необходимо выполнить несколько следующих этапов:
1) вычисление определителя минора;
2) проверка минора на существование около него окаймляющих миноров;
Реализация этапов осуществлена алгоритмическими методами и доступна в пункте 2.2.
2.2 Алгоритм вычисления ранга матрицы методом окаймляющих миноров
Алгоритм реализован в виде блок-схемы.
Опишем решение задачи:
Дана матрица размера nЧm, заполненная числами, требуется найти ранг этой матрицы, используя метод окаймляющих миноров.
Для каждого элемента матрицы, если элемент не равен 0, следовательно, ранг матрицы больше либо равен 1.
Для каждого ненулевого элемента матрицы для порядка минора от 2 до минимума из n и m нужно выполнить проверку на существование окаймляющего минора. Если сумма расстояний от позиции элемента до границ матрицы меньше порядка минора, следовательно, окаймляющий минор существует. Если окаймляющий минор существует и его определитель не равен 0, переходим на следующий порядок минора, ранг матрицы больше либо равен текущему порядку минора. При этом алгоритм продолжит вычисления, кроме случая, когда ранг достигнет своего максимума - минимального значения из m и n.
Для нахождения определителя минора воспользуемся идеями метода Гаусса решения систем линейных уравнений.
Будем выполнять те же самые действия, что и при решении системы линейных уравнений, исключив только деление текущей строки на a[i][i] (точнее, само деление можно выполнять, но подразумевая, что число выносится за знак определителя). Тогда все операции, которые мы будем производить с матрицей, не будут изменять величину определителя матрицы, за исключением, быть может, знака (мы только обмениваем местами две строки, что меняет знак на противоположный, или прибавляем одну строку к другой, что не меняет величину определителя).
Но матрица, к которой мы приходим после выполнения алгоритма Гаусса, является диагональной, и определитель её равен произведению элементов, стоящих на диагонали. Знак, как уже говорилось, будет определяться количеством обменов строк (если их нечётное, то знак определителя следует изменить на противоположный). Таким образом, мы можем с помощью алгоритма Гаусса вычислять определитель матрицы за O(N3) [3].
Блок-схема алгоритма представлена на рисунках 1-2.
Рисунок 1 - Блок- схема
Рисунок 2 - Блок-схема
2.3 Анализ вычислительной сложности алгоритма
Вычислительная сложность алгоритма - это количество элементарных операций, затрачиваемых алгоритмом для решения конкретной задачи. Сложность зависит от размерности входных данных и от самих данных. Чем сложнее алгоритм в вычислительном плане, тем больше времени и вычислительных ресурсов потребует его выполнение.
Каждый вычислительный алгоритм может быть отнесен к одному из двух классов сложности. В данном случае это множество задач, для решения которых известны алгоритмы, схожие по трудоемкости. В классе P вычислительные затраты линейно растут с увеличением размерности. Например, время, требуемое на очистку дороги, прямо пропорционально площади этой дороги. Если ее увеличить вдвое, то и временные затраты также возрастут в два раза. Класс NP включает задачи, для решения которых известны только алгоритмы, сложность которых экспоненциально зависит от размерности данных. Поэтому они, как правило, неэффективны при работе с большими множествами. Примером является задача поиска выхода из лабиринта, временные затраты на который экспоненциально растут с увеличением числа разветвлений. матрица ранг окаймляющий минор
Данный метод прогонки, примыкает к классу P, так как затраты линейно растут с увеличением размерности матрицы.
Таблица 1 - Количество выполняемых операций алгоритма «Метод прогонки»
|
№ |
Действие |
Повторы |
|
|
1 |
rang=1; |
1 |
|
|
2 |
pr=0 |
min(n,m) |
|
|
3 |
Создание окаймляющего минора B |
rang2Ч(m-rang-1) Ч(n-rang-1) |
|
|
4 |
Вычисление определителя минора |
O (N3) Ч(m-rang-1) Ч(n-rang-1) |
|
|
5 |
pr=1 |
(m-rang-1) Ч(n-rang-1) |
|
|
6 |
rang=rang+1 |
min(n,m) |
|
|
7 |
rang=rang-1 |
1 |
|
|
8 |
x[n] = B[n]; |
1 |
|
|
Количество операций |
O(N3) Ч(m-rang-1) Ч(n-rang-1) |
Таким образом, на таблице 1 показаны процессы и количество их повторений, при подсчете повторений, количество операций равно O(N3) Ч (m-rang-1) Ч (n-rang-1), где N - это размер окаймляющего минора, m и n размер матрицы.
Таблица 2 - Временная стоимость алгоритма «Метод прогонки»
|
№ |
Действие |
Стоимость |
Повторы |
|
|
1 |
rang=1; |
C1 |
1 |
|
|
2 |
pr=0 |
C2 |
min(n,m) |
|
|
3 |
Создание окаймляющего минора B |
C3 |
rang2Ч(m-rang-1) Ч(n-rang-1) |
|
|
4 |
Вычисление определителя минора |
C4 |
O (N3) Ч(m-rang-1) Ч(n-rang-1) |
|
|
5 |
pr=1 |
C5 |
(m-rang-1) Ч(n-rang-1) |
|
|
6 |
rang=rang+1 |
C6 |
min(n,m) |
|
|
7 |
rang=rang-1 |
C7 |
1 |
|
|
8 |
x[n] = B[n]; |
C8 |
1 |
В результате получим
; (1)
. (2)
После сокращения формулы, и время работы алгоритма в самом благоприятном случае вычисляется так (2).
В данном алгоритме используется цикл с неизвестным количеством итераций, что затрудняет вычисление времени работы алгоритма.
Заключение
В ходе изучения материала был хорошо изучена теоретическая часть нахождения ранга матрицы методом: окаймляющих миноров, а также практические части путем рассмотрения наглядных примеров применения этого метода на практике.
Данный метод прост и легок в освоении что, несомненно, является огромным плюсом в копилку данному методу.
В ходе выполнения курсовой работы был произведен ручной расчет.
Список использованной литературы
1. Белоусов И.В. Матрицы и определители. Учебное пособие. - Кишинев, 2006. - 101 с.
2. Определение ранга матрицы. Вычисление ранга матрицы по определению [Электронный ресурс]. - URL: http://math1.ru/education/matrix/rang.html
3. Вычисление определителя матрицы методом Гаусса [Электронный ресурс]. - URL: http://e-maxx.ru/algo/determinant_gauss#1
Размещено на Allbest.ru
Подобные документы
Изучение понятий, действий (сумма, разность, произведение), свойств квадратной матрицы. Определение и признаки ранга матрицы. Анализ методов окаймляющих миноров и преобразований. Расчет системы линейных уравнений согласно методам Крамера и матричному.
реферат [178,9 K], добавлен 01.02.2010Линейные операции над матрицами. Умножение и вычисление произведения матриц. Приведение матрицы к ступенчатому виду и вычисление ранга матрицы. Вычисление обратной матрицы и определителя матрицы, а также решение систем линейных уравнений методом Гаусса.
учебное пособие [658,4 K], добавлен 26.01.2009Понятие матрицы и ее основные элементы. Пример нахождения ее ранга путем приведения к ступенчатому виду. Описание действий над матрицами. Разбор умножения их на примере. Особенности алгебраического дополнения. Алгоритм определения обратной матрицы.
презентация [617,0 K], добавлен 15.09.2014Понятие обратной матрицы. Пошаговое определение обратной матрицы: проверка существования квадратной и обратной матрицы, расчет определителя и алгебраического дополнения, получение единичной матрицы. Пример расчета обратной матрицы согласно алгоритма.
презентация [54,8 K], добавлен 21.09.2013Расчет произведения заданных матриц. Решение системы линейных алгебраических уравнений по формулам Крамера, матричным методом и методом Гаусса. Координаты вектора в базисе. Определение ранга заданной матрицы. Система с базисом методом Жордана-Гаусса.
контрольная работа [88,2 K], добавлен 19.01.2014Понятие матрицы, ее ранга, минора, использование при действиях с векторами и изучении систем линейных уравнений. Квадратная и прямоугольная матрица. Элементарные преобразования матрицы. Умножение матрицы на число. Класс диагональных матриц, определители.
реферат [102,8 K], добавлен 05.08.2009Классификация способов нахождения обратной матрицы, полученной в системе MathCAD с помощью миноров и алгебраических дополнений: разбиения ее на клетки и на произведение 2-х треугольных матриц; с помощью модели Гаусса. Вычисление погрешности методов.
лабораторная работа [380,9 K], добавлен 31.10.2012Задачи и методы линейной алгебры. Свойства определителей и порядок их вычисления. Нахождение обратной матрицы методом Гаусса. Разработка вычислительного алгоритма в программе Pascal ABC для вычисления определителей и нахождения обратной матрицы.
курсовая работа [1,1 M], добавлен 01.02.2013Решение системы линейных уравнений по правилу Крамера и с помощью обратной матрицы. Нахождение ранга матрицы. Вычисление определителя с помощью теоремы Лапласа. Исследование на совместимость системы уравнений, нахождение общего решения методом Гауса.
контрольная работа [97,3 K], добавлен 24.05.2009Вычисление и построение матрицы алгебраических дополнений. Решение системы линейных уравнений по формулам Крамера, с помощью обратной матрицы и методом Гаусса. Определение главной и проверка обратной матрицы. Аналитическая геометрия на плоскости.
контрольная работа [126,9 K], добавлен 20.04.2016
