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

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

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

Тема: «Итерационный метод решения проблемы собственных значений»

 

 

 

 

Новосибирск, 2010

Введение

 

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

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

математический итерационный метод программный

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

 

Этот метод особенно удобен в применении к симметричной матрице, однако попробуем изложить его без этого предположения. В основе метода лежат последовательности итераций вектора 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₁*l^2k₁*X₁+ … + + a_n*l^2k_n*X_n)

 

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

 

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

 

Аналогично:

 

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

 

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

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

 

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

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

 

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

 

Программа, реализующая рассматриваемый метод, разработана в среде Ма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];

 

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

 

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

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

Получим

 

L1= -5.5251

0.2841

3.4399

4.3911