Курсовая работа " разработка алгоритма вычисления обратной матрицы с помощью теоремы гамильтона-кэли" - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Решение Для вычисления обратной матрицы воспользуемся методом присоединенной... 1 165.29kb.
Экзаменационные вопросы по курсу "Линейная алгебра " 1 44.79kb.
Лабораторная работа по дисциплине «Защита информации»: Современные... 1 91.15kb.
Контрольная работа по курсу «Теория Электросвязи» 1 31.59kb.
Лабораторная работа №1 2 Варианты заданий 2 Пример решения задачи... 9 489.4kb.
Курсовая работа по электронике «lc -генератор с обратной связью» 1 106.76kb.
Альтернативных колец 1 46.29kb.
Межличностные уменья, командообразование, ведение переговоров Эффективная... 1 45.02kb.
Дипломная работа Белова Анастасия Александровна 6 437kb.
Пример: Алгоритм метода пжи (полные жардановые исключения) 1 19.1kb.
Решение производим в matlab. Зададим матрицу S=[l 3 1 0]. Функция... 1 21.39kb.
Учебная программа для высших учебных заведений по специальности i-40... 12 1844.62kb.
Направления изучения представлений о справедливости 1 202.17kb.

Курсовая работа " разработка алгоритма вычисления обратной матрицы с помощью теоремы - страница №1/1

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

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

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

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


“УТВЕРЖДАЮ”

Зав. Кафедрой КБ и ПА

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

“__”_____________2013 г.



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


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



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

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

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

Спец: “Компьютерная безопасность”

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

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

______________ Белова О.О.

Калининград


2013

СОДЕРЖАНИЕ



  1. Введение.

  2. Уильям Роун Гамильтон и Артур Кэли.

  3. Когда появилась эта теорема.

  4. Некоторые определения.

  5. Аннуляторы операторов.

  6. Характеристический полином матрицы.

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

  8. Примеры.


ВВЕДЕНИЕ

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

Предположим, что 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), доказательство связано с довольно сложной индукцией, которая показывает, что линейное отображение комплексных чисел триангулируемо (триангуляция - разбиение поверхности на треугольники).

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

произвольного поля и требуют более сложные действия.

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

Уильям Роун Гамильтон и Артур Кэли.

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


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

Некоторые определения

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



Матрица - математический объект, записываемый в виде прямоугольной таблицы элементов кольца или поля (например, целых, действительных или комплексных чисел), которая представляет собой совокупность строк и столбцов, на пересечении которых находятся её элементы. Количество строк и столбцов матрицы задают размер матрицы.
Нулевая матрица - это матрица, размера m x n все элементы которой равны нулю.
 Союзная (взаимная) матрицаматрица, составленная из алгебраических дополнений для соответствующих элементов транспонированной матрицы.
Функция 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.

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



Аннуляторы операторов

Ненулевой многочлен 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)=, мы получаем требуемый многочлен.




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

Существует более эффективный способ нахождения аннуляторов:

Характеристический многочлен линейного оператора является аннулятором этого оператора.

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

Пусть 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.

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

При подстановке матрицы в ее характеристический полином получается нулевая матрица.

Иными словами, матрица является корнем своего характеристического полинома.
Доказательство.

Обозначим через 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,

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



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


Определение. Пусть 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

Теорема.

Пусть A это n×n комплексная матрица и cA(z)=det(zI-A) характеристический многочлен. Тогда при подстановке матрицы в ее характеристический полином получается нулевая матрица. Другими словами cA(A)=0.

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

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



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

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

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

Пример.
Покажем метод доказательства теоремы на примере

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



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


Так и



Примеры

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.
Предположим,


Тогда

И теорема Гамильтона-Кэли говорит, что
.




Бог — писатель, а мы все — герои и читатели одновременно. Айзек Зингер
ещё >>