Курсовая работа разработка алгоритма вычисления обратной матрицы с помощью теоремы гамильтона кэли - shikardos.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Курсовая работа разработка алгоритма вычисления обратной матрицы с помощью теоремы - страница №1/1

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГАОУ ВПО БАЛТИЙСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ИМ. И.КАНТА

Кафедра компьютерной безопасности

Специальность «Компьютерная безопасность»


«УТВЕРЖДАЮ»

Зав. кафедрой КБ

___________С.И. Алешников

«__»_____________2013 г.



КУРСОВАЯ РАБОТА




РАЗРАБОТКА АЛГОРИТМА ВЫЧИСЛЕНИЯ ОБРАТНОЙ МАТРИЦЫ

С ПОМОЩЬЮ ТЕОРЕМЫ ГАМИЛЬТОНАКЭЛИ

Курсовую работу выполнила:

студентка 2 курса Института ПМ и ИТ

спец: «Компьютерная безопасность»

___________ Ротнова Н.С.
Научный руководитель:

к. ф.-м. н., доцент кафедры КБ

______________ Белова О.О.

Калининград


2013

СОДЕРЖАНИЕ



  1. Введение.

  2. Теорема Гамильтона — Кэли.

  3. Доказательство 1.

  4. Доказательство 2.

  5. Доказательство 3.

  6. Примеры.

  7. Алгоритм нахождения обратной матрицы в программе Maple.

  8. Глоссарий.

  9. Литература.

ВВЕДЕНИЕ

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


Первый способ. Нахождение с помощью алгебраических дополнений.

1. Вычислить определитель \det{a} данной матрицы. Если \det{a}=0, то обратной матрицы не существует (матрица a вырожденная).

2. Составить матрицу \begin{pmatrix}a_{ij}\end{pmatrix} из алгебраических дополнений a_{ij}=(-1)^{i+j}m_{ij} элементов матрицы a.

3. Транспонируя матрицу \begin{pmatrix}a_{ij}\end{pmatrix}, получить присоединенную матрицу a^{+}=(a_{ij})^{t}.

4. Найти обратную матрицу (4.1), разделив все элементы присоединенной матрицы на определитель \det{a}:

a^{-1}=\frac{1}{\det{a}}\cdot a^{+}.
Второй способ. Для нахождения обратной матрицы можно использовать элементарные преобразования.

1. Составить блочную матрицу (a\mid e), приписав к данной матрице a единичную матрицу того же порядка.

2. При помощи элементарных преобразований, выполняемых над строками матрицы (a\mid e), привести ее левый блок a к простейшему виду \lambda. При этом блочная матрица приводится к виду (\lambda\mid s), где s — квадратная матрица, полученная в результате преобразований из единичной матрицы e.

3. Если gif" alt="\lambda=e" align=bottom width="51px" height="13px" border=0>, то блок s равен обратной матрице, т.е. s=a^{-1}. Если \lambda\ne e, то матрица a не имеет обратной.
В самом деле, при помощи элементарных преобразований строк матрицы (a\mid e) можно привести ее левый блок a к упрощенному виду \lambda. При этом блочная матрица (a\mid e) преобразуется к виду (\lambda\mid s), где s — элементарная матрица, удовлетворяющая равенству \lambda=sa. Если матрица a невырожденная, то ее упрощенный вид совпадает с единичной матрицей \lambda=e. Тогда из равенства e=\lambda=sa следует, что s=a^{-1}. Если же матрица a вырожденная, то ее упрощенный вид \lambda отличается от единичной матрицы, а матрица a не имеет обратной.

Есть и другой способ, основанный на теореме Гамильтона — Кэли.

Теорема Гамильтона — Кэли — известная теорема из теории матриц, названная в их честь.

Уильям Роун Гамильтон и Артур Кэли
Гамильтон Уильям Роуан (4.8.1805, Дублин, — 2.9.1865, Дансинк, близ Дублина), ирландский математик. Член Ирландской Академии Наук, с 1827 — профессор астрономии в Дублинском университете и директор университетской астрономической обсерватории. В 1833—35 в «Трудах» Ирландской АН опубликовал работу, в которой почти одновременно с Г. Грассманом дал точное формальное изложение теории комплексных чисел, построил своеобразную, систему чисел, т. н. кватернионов. Это учение было одним из источников развития векторного исчисления. В механике Гамильтон применил вариационный метод (т. н. принцип наименьшего действия).

Кэли, Артур (16.8.1821, Ричмонд, — 26.1.1895, Кембридж), английский математик. С 1863 профессор Кембриджского университета. Основные работы по теории алгебр, квадратичных форм. Установил связь между теорией инвариантов и проективной геометрией. Исследования К. в этой области легли в основу истолкования геометрии Лобачевского («интерпретация Кэли — Клейна»). Автор работ по теории определителей, дифференциальных уравнений, эллиптических функций. Занимался также сферической астрономией и астрофизикой.


Предположим, что A это n×n матрица. Теорема Гамильтона — Кэли говорит, что при подстановке матрицы в ее характеристический полином получается нулевая матрица.

Другими словами, если f характеристический полином A, тогда f(A) = 0.

Этот результат заявил и доказал Кэли для n = 2 и n = 3 в 1858.

Гамильтон, доказал это для n = 4 в 1862. Общий случай был доказан Фробениусом в 1878.



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

Теорема Гамильтона — Кэли широко применяется в математике. Например, это используется для вычисления инверсии A; показательной функции etA, которая необходима для того, чтобы решить системы дифференциальных уравнений; степени Ak, как в алгоритме Пуцера; и многие другие.


Есть много доказательств теоремы Гамильтона-Кэли.

Например, в книге Ланга (S.Lange, Linear Algebra, second edition, Addison-Wesly, 1971), доказательство связано с довольно сложной индукцией, которая показывает, что линейное отображение комплексных чисел триангулируемо (триангуляция разбиение поверхности на треугольники).

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

ТЕОРЕМА ГАМИЛЬТОНА — КЭЛИ
Многочлен p(\lambda) переменной \lambda называется аннулирующим для квадратной матрицы a, если при подстановке в многочлен матрицы a вместо переменной \lambda получаем нулевую матрицу, т.е. p(a)=o.

Рассмотрим три доказательства этой теоремы.



ДОКАЗАТЕЛЬСТВО 1

Доказательство индукцией по размерности пространства.

Пусть A-линейный оператор конечномерного пространства V.

База индукции:

Пусть V=1> и Ae1= αe1.

Тогда характеристический многочлен оператора А имеет вид f(t)= α-t и, значит, f(A)= α-α=0.

Шаг индукции: Пусть dim V=n>1 и для пространств меньшей размерности теорема справедлива. Пусть также A-линейный оператор пространств V и f(t) его характеристический многочлен. Наша цель показать, что f(A)=0, т.е. f(A)x=0 для любого xV.

Возьмем произвольный вектор xV и рассмотрим последовательность векторов:



x1=x и xi+1=Axi, iN.

Так как пространство V конечномерно, то найдется такое k, что x1,…,xk линейно независимы и xk+1 есть линейная комбинация векторов x1,…,xk:

xk+11x1+…+αkxk.

Пусть W=<x1,…,xk>. Согласно выбору векторов, AxiW для любого i=1,…,k и значит подпространство W A-инвариантно.

Возможны два случая: WV и W=V.

Рассмотрим первый случай. Согласно индуктивному предположению, в этом случае характеристический многочлен ограничения оператора A на W являются аннулятором оператора A/W и значит f1(A)x=0, где f1(t)-характеристический многочлен оператора A/W. Напомним, что многочлен f1 является делителем многочлена f, то есть f(t)=g(t) f1(t).

Следовательно, f(A)x=g(A) ∙ f1(A)x=g(A)( f1(A)x)=g(A) ∙0=0.

Рассмотрим второй случай: W=V. В этом случае n=k и множество векторов ε={x1,…,xn} образует базис V. Матрица оператора A в этом базисе имеет вид



Следовательно


и det(A-t)=(-1)n(tn- αntn-1-…- α2t- α1).

Напомним, что xn+1= α1x1+...+ α1xn

или

Anx1= α1x1+ α2Ax1+…+ αnAn-1x1.

Значит (An- αnAn-1-…- α1A- α1)x1=0

и поэтому f(A)x=0 для любого xV.

ДОКАЗАТЕЛЬСТВО 2

Обозначим через B матрицу, союзную с tE-A. Ее элементы принадлежат кольцу K[t] и являются полиномами от t не выше (n-1)-й степени, и6о они равны, с точностью до знаков, минорам (n-1)-го порядка матрицы tE-A, элементы которого содержат t не выше чем в первой степени.

Можно записать

B=B1tn-1+ B2tn-2+…+ Bn-1t+ Bn,

где B1, B2, Bn-1, Bn— матрицы над k.

По свойству взаимной матрицы имеет место равенство В(tE-А)=det(tE-А)Е, котoрое можно записать подробно (B1tn-1+ B2tn-2+…+ Bn-1t+ Bn)(tE-A)=( tn- b1tn-1+…+ (-1)n-1bn-1t+(-1)n bn)E.

По определениям равенства матриц и равенства полиномов, мы вправе приравнять коэффициенты при одинаковых степенях на всех позициях, что равносильно приравниванию матричных коэффициентов при степенях t.

Получаем цепочку равенств:

B1=E,

B2- B1A=-b1E,

B3-B2A=b2E,

. . . . . . . . . . . . . . . . . .

Bn-Bn-1A=(-1)n-1bn-1E,

-BnA=(-1)nbnE.

Умножим справа первое равенство на Аn, второе на Аn-1, третье на Аn-2,…, (n— 1)-е на А и сложим с последним. Слева все слагаемые взаимно уничтожатся и останется нулевая матрица. Справа получим An-b1An-1+b2An-2+…+(-1)n-1bn-1A+(-1)n-1bn-1A+(-1)nbnE.

Итак,


f(A)= An-b1An-1+b2An-2+…+(-1)n-1bn-1A+(-1)nbnE=0,

что и требовалось доказать.



ДОКАЗАТЕЛЬСТВО 3

Для третьего доказательства нам потребуется следующая информация.


Определение. Пусть a — комплексное число и n — неотрицательное целое число. Следующие последовательности φn,a являются фундаментальными для всего, что мы делаем.

где δn(k) является последовательностью, которая равна 0 для всех k n

и δn(n)=1.
Следствие. Пусть A n×n матрица с элементами из комплексных чисел, тогда


Предложение 1. Пусть a and n∈ ℕ. С φn,a которая приведена в определении мы имеем


Лемма 1. Пусть D это простая производная оператора. А n целое неотрицательное число и а ℂ. Тогда мы имеем

где следует понимать как предел, то есть , как и в


.

Доказательство.


Оценка x=a в случае, когда a 0 дает . Если a=0, значит, как описано выше, получаем



Предложение 2. Пусть A n×n — матрица с комплексными элементами. Пусть cA(z) = det(zI -A)-характеристический многочлен. Предположим, a1, …, aR являются различными корнями соответствующей кратности M1, …, MR. Тогда для каждого r, 1 r R, и m, 0 m Mr -1, существует такая матрица Br,m, такая что
.

Доказательство.

Наше предложение означает, что мы можем учитывать cA следующим образом:

Запись (i,j) из (zI -A)-1 имеет вид , где pi,j(z) некоторый многочлен степени меньше n. Используя простые дроби, мы можем написать



где br,m(i, j) ∈ ℂ. Отсюда следует, что

где Br,m матрица n×n чья (i,j) запись является br,m(i, j) для каждой пары (r, m).
Лемма 2.

Пусть p(z)-многочлен и а является корнем кратности М. Пусть m это неотрицательное целое с m

Доказательство теоремы.

По лемме 1 и предложению 2



Пусть теперь p(z) любой многочлен. Тогда в силу линейности оператора производной мы имеем

Тем не менее, для каждого корня ar с кратностью Mr, лемма 2 подразумевает

для 0 m < Mr. Если положить p = cA , то из этого следует, что cA(A) = 0.
ПРИМЕРЫ

1. Для 1 × 1 матрицы А = (а), характеристический многочлен имеет вид p(λ) = λ-a, и таким образом р(А)=(а)-а(1) = 0 очевидно.
2. Для 2 × 2 матрицы A
a=\begin{pmatrix}a&b\\c&d\\\end{pmatrix} ,
характеристическим многочленом будет p(λ) = λ2 − (a + d)λ + (ad − bc), и по теореме Гамильтона-Кэли
p(a)=a^2-(a+d)a+(ad-bc)i_2=\begin{pmatrix}0&0\\0&0\\\end{pmatrix};

что действительно всегда так очевидно путем разработки записи A2.

3. Покажем, что характеристический многочлен матрицы
c:\users\natasha\desktop\mathtex.jpg

является для нее аннулирующим.


Находим характеристический многочлен матрицы
c:\users\natasha\desktop\mathtex (1).jpg

Подставляя вместо переменной λ матрицу A, получаем


c:\users\natasha\desktop\(3).jpg
Что и требовалось доказать.

4.
Ее характеристический многочлен задается

Теорема Гамильтона-Кэли утверждает, что если мы определим

то

В чем можно легко убедиться.

5. Предположим,

Тогда

И теорема Гамильтона-Кэли говорит, что
.
6. Покажем метод доказательства 3 теоремы на примере

По лемме 1 мы имеем



Характеристический многочлен A будет cA(z) = (z-2)2. Поэтому у нас есть


Так и



АЛГОРИТМ НАХОЖДЕНИЯ ОБРАТНОЙ МАТРИЦЫ

В ПРОГРАММЕ Maple

Запустим программу с пакетом linalg.

Введем размерность матрицы и ее элементы.
>

>

>




С помощью встроенных функций введем единичную матрицу.
>


Найдем характеристический многочлен. Для удобства с помощью функции expand раскроем скобки, если они имеются.
>



>


Воспользуемся циклом, чтобы записать коэффициенты при λ.

Свободный член многочлена P запишем отдельно.



>







>

Найдем обратную матрицу.


>


Проверим это с помощью функции inverse.

>

>

>




>


Ответы совпали.
С помощью этого алгоритма рассмотрим нахождение обратной матрицы для других матриц.
1. Рассмотрим матрицу, состоящую из одного элемента.
>

>

>




>



>



>



>



>



>


2. Матрица второго порядка.
>

>

>




>



>



>



>





>



>





3. Для матрицы порядка 4 можно найти обратную матрицу.
>

>

>




>



>



>



>









>



>


4. Если же вводимая матрица вырожденная, то при вычислении обратной матрицы появится ошибка.
>

>

>




>



>



>



>





>



>

Error, numeric exception: division by zero
5. Возьмем матрицу с дробными элементами.
>

>

>




>



>



>



>







>



>



6. Проверим программу для матрицы 20-ого порядка.
>

>

>




Так как программа создавалась в worksheet mode, матрица, содержащая больше 10 строк или столбцов, выводится следующим образом.

>


Двойной щелчок по выводу открывает окно, где можно увидеть нашу единичную матрицу.


>



>



>









































>



>

Проверяем.


>


7. Рассмотрим подобную матрицу
>

>

>





>



>

>



>









































>



>
Таким образом, мы уменьшили количество нулей и разнообразили элементы. В результате получили матрицу, элементы которой многозначные и дробные. При проверке с помощью inverse(A) результат совпадает.

ГЛОССАРИЙ

Аннуляторы операторов. Ненулевой многочлен f F[x] называется аннулятором линейного оператора A F-пространства V; если f(A)=0.

Заметим, что согласно теореме о действиях в координатах, равенство f(A)=0 равносильно равенству f(A)=0б где A-матрица А в произвольном базисе.

Пользуясь новым понятием, мы можем переформулировать критерий диагонализируемости следующим образом:

Теорема (критерий диагонализируемости).

Оператор А диагонализируем ⇔ найдется аннулятор f оператора А, удовлетворяющий двум условиям:

  1. f разложен на линейные множители,

  2. f не имеет кратных корней.

Справедлива следующая теорема о существовании аннулятора.

Любой линейный оператор конечномерного пространства имеет хотя бы один аннулятор.

Доказательство.

Пусть V-n-мерное векторное пространство над полем F. Так как размерность пространства операторов V имеет размерность n2, то для любого линейного оператора A пространства V операторы линейно зависимы.

Это значит, что некоторая нетривиальная линейная комбинация этих операторов есть нулевой оператор

Полагая f(x)=, мы получаем требуемый многочлен.



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

Нулевая матрица это матрица, размера m x n, все элементы которой равны нулю.

Поле множество F с двумя бинарными операциями аддитивная операция (сложение) и мультипликативная операция (умножение), если оно (вместе с этими операциями) образует коммутативное ассоциативное кольцо c единицей 1≠0, все ненулевые элементы которого обратимы.

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

Функция f (отображение, операция, оператор) это закон или правило, согласно которому каждому элементу x из множества x ставится в соответствие определенный элемент y из множества y.

Характеристический полином матрицы. Многочлен, определяющий собственные значения матрицы называется характерестическим, т.е. сопоставляя квадратной матрице с элементами из поля К матрицу tE-A, элементы которой принадлежат кольцу полиномов K[t]. Матрица tE-A называется характеристической матрицей для А, а ее определитель f(t)=det(tE-A) называется характеристическим полиномом матрицы А.

Если

c:\users\natasha\desktop\матрица.jpg
То f(t)=tn-b1tn-1+b2tn-2+…+(-1)nbn с коэффициентами из K. Вычислим b1 и bn. Заметим, что b1 есть коэффициент при tn-1 в определителе
c:\users\natasha\desktop\матрица - копия.jpg

Буква t входит, причем в первой степени, только в диагональные элементы матрицы tE-A. Следовательно, каждое слагаемое определителя, содержащее tn-1, имеет в числе сомножителей по крайней мере n-1 диагональных элементов, но тогда и последний сомножитель тоже диагональный. Таким образом, коэффициент при tn-1 равен коэффициенту при tn-1 в полиноме (t-a11)* (t-a22)…( t-ann) т. e. равен —( a11+ a22 +…+ ann).

Таким образом, b1=a11+ a22 +…+ ann .Это выражение имеет специальное название —след матрицы A и обозначается Sp А или Tr А (от Spur-нем., Тгасе—англ.).

Для подсчета свободного члена положим t = 0. Получим

(-1)nbn=det(-A)=(-1)n det A, откyда bn=det A.

Остальные коэффициенты тоже можно подсчитать, но это несколько сложнее.



ЛИТЕРАТУРА

1. Акивис М. А., Гольдберг В. В. Т Тензорное исчисление, М.: Наука, 1969.

2. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1966.

3. Ланкастер П. Теория матриц. — М.: Наука, 1973.

4. Фаддеев Д.К. Лекции по алгебре – М.: Наука. 1984.

5. Панов Т.Е. Линейная алгебра и геометрия. Курс лекций, мех-мат МГУ.

6. W.A. Adkins and M. G. Davidson, The Cayley-Hamilton and Frobenius theorems via the Laplace Transform, Linear Algebra and its Applications, 371 (2003).

7. A. Cayley, A memoir on the theory of matrices, Philosophical Transactions of the Royal Society of London, 148, (1858), 17-37.



8. G. Frobenius, Ueber lineare Substitutionen und blineare Formen J. Reine Angew. Math. 84, (1878), 1-63.