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

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

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

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

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

/>Введение

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

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

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

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

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

Y0,Y1=A*Y0, Y2=A2*Y0, …, Yk=Ak*Y0,… (1)

Y0,Y’1=A’*Y0, Y’2=A’2*Y0, …,Y’k=A’k*Y0, … (2)

Пусть b1,…, bn координаты вектора Y0в базисе X’1,…, X’n, a1, …, an координаты Y0в базисе X1,…, Xn. При этом предположим, что базисы выбраны так, что система векторовX1, X2, …, Xn и X’1, …, X’nудовлетворяет условиям ортогональности и нормированности.

Образуемскалярное произведение (Y’k, Yk):

(Y’k,Yk)=(A’k*Y0, Ak*Y0)=(Y0,A2k*Y0)=(b1*X’1+ … +bn*X’n,a1*l2k1*X1+… + + an*l2kn*Xn)

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

(Y’k,Yk)=a1*b1*l2k1+ … + an*bn*l2kn (3).

Аналогично:

(Y’k-1,Yk)=a1*b1*l2k-11+ … + an*bn*l2k-1n (4).

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

(Y’k, Yk)/(Y’k-1, Yk) = l1 + O(l2/l1)2k.

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

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

/>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.

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

functiona=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.6280.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 00.516;

-1.316 0 -1.7434.628;

0 0.516 4.6280.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 00.516;

-1.316 0 -1.7434.628;

0 0.516 4.6280.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 00.516;

-1.316 0 -1.7434.628;

0 0.516 4.6280.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 00.516;

-1.316 0 -1.7434.628;

0 0.516 4.6280.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 00.516;

-1.316 0 -1.7434.628;

0 0.516 4.6280.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

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

/>

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

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

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

/>Заключение

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

/>Списоклитературы

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

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

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