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

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

Министерство образования РФ

Новосибирский государственный технический университет

Кафедра экономической информатики

Курсовая работа по дисциплине:

«Численные методы в экономике»

Тема: «Вычисление максимального по модулю собственного значения и соответствующего ему собственного вектора симметричной матрицы методом скалярных произведений»

Новосибирск - 2008

СОДЕРЖАНИЕ

Введение

1 Математическая постановка задачи

2 Описание программного обеспечения

3 Описание тестовых задач

Выводы

Список использованной литературы

ВВЕДЕНИЕ

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

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

1 МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

Этот метод особенно удобен в применении к симметричной матрице, однако попробуем изложить его без этого предположения. В основе метода лежат последовательности итераций вектора Y₀ матрицами A и A', транспонированной с А. Эти последовательности имеют следующий вид:

Y₀, Y₁=A*Y₀, Y₂=A²*Y₀, … , Y_k=A^k*Y₀, … (1)

Y₀, Y'₁=A'*Y₀, Y'₂=A'²*Y₀, … , Y'_k=A'^k*Y₀, … (2)

Пусть b₁, … , b_n координаты вектора Y₀ в базисе X'₁, … , X'_n, a₁, … , a_n координаты Y₀ в базисе X₁, … , X_n. При этом предположим, что базисы выбраны так, что система векторов X₁, X₂, … , X_n и X'₁, … , X'_n удовлетворяет условиям ортогональности и нормированности.

Образуем скалярное произведение (Y'_k,Y_k):

(Y'_k,Y_k)=(A'^k*Y₀,A^k*Y₀)=(Y₀,A^2k*Y₀)=(b₁*X'₁+ … +b_n*X'_n , a₁*^2k₁*X₁+ … + + a_n*^2k_n*X_n)

Далее в силу свойств ортогональности и нормированности системы векторов имеем:

(Y'_k,Y_k)=a₁*b₁*^2k₁+ … + a_n*b_n*^2k_n (3).

(Y'_k-1,Y_k)=a₁*b₁*^2k-1₁+ … + a_n*b_n*^2k-1_n (4).

Можно видеть, что из равенств (3) и (4) получаем:

(Y'_k , Y_k)/(Y'_k-1 , Y_k) = ₁ + O(₂/₁)^2k.

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

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

2 ОПИСАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

Программа, реализующая рассматриваемый метод, разработана в среде МаtLab, предназначенной для выполнения математических операций. Она состоит из головной программы и 2х подпрограмм, вызываемых из основной программы.

Головная программа (main.m). В основной программе задается начальное приближение yn, начальное значение собственного вектора L1 и значение допустимой ошибки ed. Текст программы:

clc %очистка экрана

yn=[1;1;1;1]; %задание начального приближения собственного вектора

L1= -5.5251; %начальное значение собственного числа матрицы

ed=0.00001; %значение допустимой ошибки

trace=1; %установка режима вывода на экран

[mout,Lout,yout]= sobstv('fun',yn,L1,ed,trace); %вызов функции, реализующей метод скалярных произведений

plot(mout,Lout) %вывод графика значений собственного числа заданной матрицы за время итерационного процесса

pause;

plot(mout,yout) %вывод графика значений собственного вектора, соответствующего собственному числу

Подпрограмма sobstv.m. В данной подпрограмме происходит вычисление максимального собственного числа и соответствующего ему собственного вектора. Значение собственного числа на каждом шаге заносится в L, результат умножения матрицы а на заданный вектор заносится в yn. Время выполнения итераций равно t, количество итераций - m. Текст программы:

function [mout,Lout,yout]=sobstv(fun,yn,L1,ed,trace);

a=feval(fun); %вызов матрицы, описанной в файле с именем matrsp

m=0; %обнуление счетчика итераций

Lout=L1;mout=m;yout=yn';

L=0; %присваивание начального значения решения

if trace

clc,yn,m,L1 %вывод значения решений на данном этапе

end

t0=fix(clock); %задание начальной точки отсчета времени выполнения итераций

while (abs(L1-L)>ed) %задание цикла

yn1=yn;

yn=a*yn;

L=L1;

L1=(yn'*yn)/(yn1'*yn); %вычисление собственного числа

y=yn/sqrt(yn'*yn); %вычисление собственного вектора

if trace

home,y,m,L1 %вывод текущих значений на экран

end %на данном этапе итераций

m=m+1; %увеличение счетчика итераций

Lout=[Lout;L1]; %формирование выходных параметров

mout=[mout;m];

yout=[yout;y'];

end

t1=fix(clock); %значение конечного момента времени

t=t1-t0 %время выполнения итераций

pause;

Подпрограмма fun.m. В этой подпрограмме задается матрица a.

Текст программы:

function a=fun

%Изменяемая пользователем часть

a=[1.255 1.340 -1.316 0;

1.340 2.526 0 0.516;

-1.316 0 -1.743 4.628;

0 0.516 4.628 0.552];

3 ОПИСАНИЕ ТЕСТОВЫХ ЗАДАЧ

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

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

L1= -5.5251

0.2841

3.4399

4.3911

Решение исходной задачи. Исходные данные:

yn=[1,1,1,1];

ed=0.00001;

a=[1.255 1.340 -1.316 0;

1.340 2.526 0 0.516;

-1.316 0 -1.743 4.628;

0 0.516 4.628 0.552];

Данные, полученные при выполнении программы:

y = -0.1501 m = 34 L1 = -5.5251 t = 0

-0.0135

-0.7853

0.6005

Изменение максимальной допустимой ошибки. Увеличим значение допустимой ошибки. Исходные данные:

yn=[1,1,1,1];

ed=0.0001;

a=[1.255 1.340 -1.316 0;

1.340 2.526 0 0.516;

-1.316 0 -1.743 4.628;

0 0.516 4.628 0.552];



Рисунок - График значений собственного числа заданной матрицы за время итерационного процесса

Рисунок - График значений собственного вектора, соответствующего собственному числу

Данные, полученные при выполнении программы:

y = 0.1491 m = 29 L1 = -5.5253 t = 0

0.0136

0.7880

-0.5972

Рисунок - График значений собственного числа заданной матрицы за время итерационного процесса

Уменьшим значение допустимой ошибки. Исходные данные:

yn=[1,1,1,1];

ed=0.000001;

a=[1.255 1.340 -1.316 0;

1.340 2.526 0 0.516;

-1.316 0 -1.743 4.628;

0 0.516 4.628 0.552];



Рисунок - График значений собственного вектора, соответствующего собственному числу

Данные, полученные при выполнении программы:

y = 0.1498 m = 39 L1 = -5.5251 t = 0

0.0135

0.7862

-0.5994

Изменение начального приближения собственного вектора. Увеличим значение начального приближения, т.е. отдалим от конечного решения. Исходные данные:

yn=[2,3,3,2];

ed=0.00001;

a=[1.255 1.340 -1.316 0;



Рисунок - График значений собственного числа заданной матрицы за время итерационного процесса

1.340 2.526 0 0.516;

-1.316 0 -1.743 4.628;

0 0.516 4.628 0.552];

Данные, полученные при выполнении программы:

y = -0.1501 m = 32 L1 = -5.5251 t = 1

-0.0135

-0.7853

0.6004

Уменьшим значение начального приближения, т.е. приблизим от конечного решения.



Рисунок - График значений собственного вектора, соответствующего собственному числу

Рисунок - График значений собственного числа заданной матрицы за время итерационного процесса



Рисунок - График значений собственного вектора, соответствующего собственному числу

Исходные данные:

yn=[1,0,1,0];

ed=0.00001;

a=[1.255 1.340 -1.316 0;

1.340 2.526 0 0.516;

-1.316 0 -1.743 4.628;

0 0.516 4.628 0.552];

Данные, полученные при выполнении программы:

y = 0.1496 m = 25 L1 = -5.5251 t = 0

0.0135

0.7866

-0.5989

Рисунок - График значений собственного числа заданной матрицы за время итерационного процесса

Рисунок - График значений собственного вектора, соответствующего собственному числу

Рассмотрим другие примеры. Исходные данные:

yn=[1,1,1];

L1= 0.01

edop=0.00001;

a=[1 1 1;

2 3 4;

0 4 0];

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

L1= 6.2085

0.4794

-2.6879

Полученный результат:

y = 0.2565 m =13 L1 =6.2085 t =0

0.8125

0.5235

Для рассмотрения работы с плохо обусловленной матрицей возьмем матрицу Гильберта размерностью 10.

Исходные данные:

yn=[1,1,1,1,1,1,1,1,1,1];

edop=0.00001;

a= hilb(10)



Рисунок - График значений собственного числа заданной матрицы за время итерационного процесса

Рисунок - График значений собственного вектора, соответствующего собственному числу

Найдем собственные значения исходной матрицы, используя функцию eig. Получим, что максимальное L1= 1.7519. Полученный результат:

y = 0.6994 m =4 L1=1.7519 t =0

0.4260

0.3170

0.2556

0.2153

0.1866

0.1650

0.1480

0.1344

0.1231

Рисунок - График значений собственного числа заданной матрицы за время итерационного процесса



Рисунок - График значений собственного вектора, соответствующего собственному числу

Для рассмотрения работы с разреженной матрицей. Исходные данные:

yn=[1,1,1,1,1];

edop=0.00001;

a=[1 0 0 1 0

0 0.5 0 0 0

1 0 2 0 0

0 0 0 1 0

0 0 0 0 0.5];

Ожидаемый результат, вычисленный с помощью eig 2. Полученный результат:

y = 0.0000 m =20 L1 =2.0000 t =0

0.0000

1.0000

0.0000

0.0000

Рисунок - График значений собственного числа заданной матрицы за время итерационного процесса

вектор матрица скалярный произведение

Рисунок - График значений собственного вектора, соответствующего собственному числу

ВЫВОДЫ

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

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

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

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Сарычева О.М. Численные методы в экономике: Конспект лекций / НГТУ - Новосибирск, 1995. - 65 с.

2. Уилкинс Дж.Х. Алгебраическая проблема собственных значений. - Наука, М. 1970.

3. Фаддеев Д.К., Фаддеев В.И. Вычислительные методы линейной алгебры М. Физматиздат, 1963.

Размещено на Allbest.ru