Вычисление характеристических многочленов, собственных значений и собственных векторов (86017)

Посмотреть архив целиком

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

СУМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

КАФЕДРА ИНФОРМАТИКИ










Курсовая работа

по дисциплине «Численные методы»

на тему:

«Вычисление характеристических многочленов, собственных значений и собственных векторов»












Сумы, 2005


Содержание


СОДЕРЖАНИЕ

ТЕОРЕТИЧЕСКИЕ ДАННЫЕ

ВВЕДЕНИЕ

МЕТОД ДАНИЛЕВСКОГО

УКАЗАНИЯ ПО ПРИМЕНЕНИЮ ПРОГРАММЫ

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

АНАЛИЗ ПРОГРАММЫ

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ


Теоретические данные


Введение


Большое количество задач с механики, физики и техники требует нахождение собственных значений и собственных векторов матриц, т.е. таких значений λ, для которых существует нетривиальное решение однородной системы линейных алгебраических уравнений . Тут А-действительная квадратичная матрица порядка n с элементами ajk, а --вектор с компонентами x1, x2,…, xn Каждому собственному значению λi соответствует хотя бы одно нетривиальное решение. Если даже матрица А действительная, ей собственные числа (все или некоторые) и собственные векторы могут быть недействительными. Собственные числа являются корнями уравнения , где Е - единичная матрица порядка n


или


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


Метод Данилевского


Простой и изысканный метод нахождения характеристического многочлена предложил А.М.Данилевский. Рассмотрим идею метода. Рассмотрим матрицу A



Для которой находится характеристический многочлен, при помощи подобных преобразований преобразуется к матрице


,


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


, то и .


Поэтому для обоснования метода достаточно показать, каким образом из матрицы A строится матрица P.

Подобные преобразования матрицы A к матрице P происходят последовательно. На первом шаге матрица А преобразовывается к подобной до неё матрице А(1), в которой предпоследний столбец имеет необходимый вид. На втором шаге матрица А(1) преобразовывается на подобную к ней матрицу А(2), в которой уже два предпоследних столбца имеют необходимый вид, и т.д.

На первом шаге матрица А умножается справа на матрицу



и слева на матрицу ей обратную



Первый шаг даёт


,


где

На втором шаге матрица А(1) умножается справа на матрицу


и слева на обратную к ней матрицу



Очевидно, что элементы матрицы


.


Это означает, что два предпоследних столбца матрицы А(2) имеют необходимый вид. Продолжая этот процесс, после n-1 шагов придем к матрице


,


которая имеет форму Фробениуса и подобная к входной матрице А. При этом на каждом шаге элементы матрицы А(j) находятся по элементам матрицы А(j-1) также, как мы находили элементы матрицы А(2) по элементам А(1). При этом предпологается, что все элементы отличные от нуля. Если на j-ом шаге окажется, что , то продолжать процесс в таком виде не будет возможно. При этом могут возникнуть два случая:

  1. Среди элементов есть хотя бы один, отличный от нуля, например . Для продолжения процесса поменяем в А(j) местами первый и -й строчки и одновременно 1-й и -й столбцы. Такое преобразование матрицы А(j) будет подобным. После того, как получим матрицу , процесс можно продолжать, т.к. столбцы матрицы А(j),приведённые к необходимому виду не будут испорчены.

  2. Все элементы равны нулю. Тогда матрица А(j) имеет вид , где F- квадратичная матрица порядка j, которая имеет нормальный вид Фробениуса; В—квадратная матрица порядка n-j, но , то есть характеристический многочлен матрицы F является делителем характеристического многочлена матрицы А. Для нахождения характеристического многочлена матрицы А необходимо еще найти характеристический многочлен матрицы В, для которой используем этот же метод.

Подсчитано, что количество операций умножения и деления, необходимых для получения характеристического многочлена матрицы порядка n составляет n(n-1)(2n+3)/2.

На данном этапе работы мы получили характеристический полином, корнями которого будут собственные числа матрицы А. Процедура нахождения корней полинома n-ой степени не проста. Поэтому воспользуемся пакетом MathCAD Professional для реализации данной задачи. Для поиска корней обычного полинома р(х) степени n в Mathcad включена очень удобная функция polyroots(V). Она возвращает вектор всех корней многочлена степени n, коэффициенты которого находятся в векторе V, имеющим длину равную n+1. Заметим, что корни полинома могут быть как вещественными, так и комплексными числами. Таким образом мы имеем собственные числа, при помощи которых мы найдём собственные векторы нашей матрицы А. Для нахождения собственных векторов воспользуемся функцией eigenvec(A,vi), где А-исходная матрица, vi-собственное число, для которого мы ищем собственный вектор. Данная функция возвращает собственный вектор дня vi.


Указания по применению программы


Данная курсовая работа выполнена на языке программирования Pascal. В курсовую работу входит файл danil.exe. Danil.exe предназначен для нахождения характеристического полинома методом Данилевского. Входными параметрами является размерность матрицы и сама матрица, а выходным — характеристический полином.


Программная реализация


Программный код программы danil.exe

uses wincrt;

label 1;

type mas=array[1..10,1..10]of real;

var A,M,M1,S:mas;

z,max:real;

f,jj,tt,ww,v,h,b,y,i,j,w,k,e,l,q,x,u:byte;

p,o:array[1..10]of real;

t:array [1..10]of boolean;


procedure Umnogenie(b,c:mas; n:byte; var v:mas);

var i,j,k:byte;

begin

for i:=1 to n do

for j:=1 to n do

begin

v[i,j]:=0;

for k:=1 to n do

v[i,j]:=b[i,k]*c[k,j]+v[i,j];

end;

end;


procedure dan(n:byte; var a:mas);

label 1,2;

var y:byte;

begin

For y:=1 to n-1 do

begin

if a[1,n]=0 then

begin

if y>1 then begin

max:=abs(a[1,n]);

w:=1;

for i:=1 to n-y do

if abs(a[i,n])>max then begin max:=abs(a[i,j]); w:=i; end;


if max=0 then

begin

for l:=n downto n-y+1 do

begin

p[f]:=a[l,n];

t[f]:=false;

f:=f-1;

end;

t[f+1]:=true;

x:=x+1;

u:=n-y;

if y=n-1 then begin o[q]:=a[1,1]; q:=q+1; end else dan(u,a);

goto 2;

end;


for j:=1 to n do

begin

z:=a[1,j];

a[1,j]:=a[w,j];

a[w,j]:=z;

end;


for k:=1 to n do

begin

z:=a[k,1];

a[k,1]:=a[k,w];

a[k,w]:=z;

end;

goto 1;

end

else

begin

max:=abs(a[1,2]);

w:=1;e:=2;

for i:=1 to n-1 do

if abs(a[i,n])>max then begin max:=abs(a[i,j]); w:=i; e:=n; end;

for j:=2 to n do

if abs(a[1,j])>max then begin max:=abs(a[i,j]); w:=1; e:=j; end;

if abs(a[n,1])>max then begin max:=abs(a[n,1]); w:=n; e:=1; end;

if max=0 then

begin

o[q]:=a[n,n];


q:=q+1;

u:=n-1;

if n=2 then begin o[q]:=a[1,1]; q:=q+1; o[q]:=a[n,n]; q:=q+1; end else dan(u,a);

goto 2;

end;



if (w>1) and (e=n) then

begin

for j:=1 to n do

begin

z:=a[1,j];

a[1,j]:=a[w,j];

a[w,j]:=z;

end;


for k:=1 to n do

begin

z:=a[k,1];

a[k,1]:=a[k,w];

a[k,w]:=z;

end;

goto 1;

end;


if (w=n) and (e=1) then

begin

for j:=1 to n do

begin

z:=a[1,j];

a[1,j]:=a[n,j];

a[n,j]:=z;

end;


for k:=1 to n do

begin

z:=a[k,1];

a[k,1]:=a[k,n];

a[k,n]:=z;

end;

goto 1;

end;


if w=1 then

begin

for j:=1 to n do

begin

z:=a[n,j];

a[n,j]:=a[e,j];

a[e,j]:=z;

end;

for k:=1 to n do

begin

z:=a[k,n];

a[k,n]:=a[k,e];

a[k,e]:=z;

end;

goto 1;

end;


end;


end;

1:

for i:=1 to n do

for j:=1 to n do

if i<>(j+1) then M[i,j]:=0

else M[i,j]:=1;


for i:=1 to n do

for j:=1 to n do

if (i+1)<>j then M1[i,j]:=0

else M1[i,j]:=1;



for i:=1 to n do

if i<>n then begin M[i,n]:=a[i,n]; M1[i,1]:=-a[i+1,n]/a[1,n]; end

else begin M[i,n]:=a[i,n]; M1[i,1]:=1/a[1,n]; end;

Umnogenie(M1,A,n,S);

Umnogenie(S,M,n,A);

if y=n-1 then

begin

for l:=n downto 1 do

begin

p[f]:=a[l,n];

t[f]:=false;

f:=f-1;

end;

t[f+1]:=true;

x:=x+1;

end;

end;

2:

end;


begin

writeln('Vvedite razmernost` matrici A');

readln(ww);

f:=ww;

for i:=1 to ww do

begin

for j:=1 to ww do

begin

write('a[',i,j,']=');

Readln(A[i,j]);

end;

end;


q:=1;

x:=0;

dan(ww,a);

for i:=1 to q-1 do


Случайные файлы

Файл
48874.rtf
14061.rtf
140955.doc
162081.rtf
71463.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.