QL алгоритм для вычисления симметричных трехдиагональных матриц

Министерство  образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное  учреждение высшего профессионального  образования

«Новосибирский  Государственный Технический Университет»

 

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

 

 

 

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

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

Вариант-8

 

 

 

 

 

 

 

Факультет Бизнеса

Группа: ФБИ- 01

Студентка: Гаврилова О.П.

Преподаватель: д.ф-м.н., профессор

                            Соболева О.Н.

                           

 

 

 

 

 

 

 

Новосибирск 2012

Оглавление:

1. Введение………………………………………………………………………………….3
2. Задание 1...….………………………………………………………….…………………4
3. Задание 2………………………...……………………………………….……………….5
4. Задание 3………………...………………………………………………………………..6

5.   Заключение……………………………………………………………………………...13

6.   Список использованных источников …………………………………………………14

 

 

Введение:

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

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

     Абсолютные  и относительные погрешности для приближенных вещественных чисел тесно связаны с очень важным понятием верных цифр.  Верными могут быть только значащие цифры - все цифры числа, начиная с первой отличной от нуля слева. Говорят, что число х имеет m верных значащих цифр, если для абсолютной погрешности числа  справедливо неравенство  

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

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

     Если число λ и  вектор x≠0 удовлетворяют уравнению Ax= λx, то λ называется собственным значением матрицы A, а x – собственным вектором, соответствующим λ.

     Собственные значения  матрицы определяются из уравнения  для определителя: det(A- λE)=0, где E – единичная матрица. Если собственные значения матрицы A различны (λ_i ≠ λ_j), то собственные векторы, соответствующие этим собственным значениям, линейно независимы, т.е. если αx_i + βx_j =0, то α=β=0.

 

 

Задание 1.

Находим значение функции 

при a=0.2456

        b=0.20078

        c=0.008

 

Далее найдем абсолютную погрешность по формуле

 

Подставив в нее =0.0005

                             =0.00003

                             =0.0002

 

 

 

 

 

 

 

Теперь найдем относительную погрешность  по формуле

 

 

 

 

 

 

 

Рассчитаем число верных знаков

 

n=-5

m=2

Таким образом, число верных знаков равно двум:

f = 0,0000050587

 

 

 

Задание 2.

Значение функции было рассчитано в прошлом задании, и оно равно

 

Нам дано, что m=3

И из прошлой задачи мы нашли, что n=-5

Подставим данные в уравнение

 

откуда получим 

 

Абсолютная погрешность функции  равна 0,00000005

Рассчитаем относительную погрешность

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 3.

Описание метода

Основная идея алгоритма QL заключается в том, что любая действительная матрица может быть представлена в форме A = QL, где Q ортогональная, а L - верхняя треугольная матрицы.

Это разложение строится применением алгоритма преобразования Хаусхолдера с целью уничтожения элементов столбцов матрицы A выше диагонали.

Преобразование Хаусхолдера осуществляется с использованием матрицы Хаусхолдера, имеющей следующий вид:

где E - единичная матрица, vv^T- квадратная матрица того же размера.

Элементы вектора v на k-ой итерации определяется следующим образом:

(v₁,..v_k-1,v_k,..v_n), где элементы v₁..v_k-1 равны соответственно элементам k-ого столбца матрицы А, v_k=a_kk+sign(a_kk)|| a_jk ||, v_k+1.. v_n=0

 

Алгоритм QL состоит из цепочки ортогональных преобразований.

Выбираем изначально

A⁽⁰⁾=A

И представляем в форме 

A⁽⁰⁾=Q⁽⁰⁾L⁽⁰⁾

Переходим к новой матрице посредством  перемножения:

A⁽¹⁾=L⁽⁰⁾Q⁽⁰⁾  

       …

A^(k)=Q^(k)L^(k) 

A^(k+1)=L^(k)Q^(k)  

 

Таким образом, на (k+1)-ой итерации на диагонали матрицы A в порядке возрастания располагаются ее собственные значения.

 

Если в ходе итераций прослеживаются комплексно-сопряженная пара собственных  значений, соответствующая блоку (2х2), образуемому элементами j-ого и (j+1)-го столбцов,

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

 

 

 

 

Решение задачи с помощью  программы

Матрица задается в виде функции, что  обеспечивает универсальность программы:

function[A]=matr

A=[1 2 0;2 1 3;0 3 4];

 

Реализация алгоритма на MATLAB:

function[A,R,e]=SobZn(matr)  % фунция, вычисляющая собственные значения, вектора,

                        % расчетную погрешность симметричной трехдиагональной матрицы

[R,D]=eig(matr);        % вычисляем точные собственные значения матрицы

n=size(matr,1);         % размерность матрицы

A=matr;                 % присваеваем рабочей переменной исходную матрицу

An=matr;               

for i=1:10              % цикл, в котором вычисляются собственные значения

k=n;                    % присваиваем размер матрицы рабочей переменной

 while k>1              % находим нижнюю треугольную матрицу

  ak=A(1:k,k);         

  vk=ak; vk(k)=vk(k)+sign(ak(k))*norm(ak);

  vk=vk/norm(vk);

  A(1:k,1:k)=A(1:k,1:k)-2*vk*(vk'*A(1:k,1:k));

  k=k-1;

  end

L=A;                    % присваиваем полученное значение переменной L

Q=An/L; %A*inv(L);      % находим Q - ортогональную

A=L*Q;                  % переходи к последующей итерации

An=A;                   % присваиваем рабочей переменной значение А

end

  for I=1:(n-1)         % если есть комплексно-сопряженные значения

    for J=1:n           % избавляемся от них

     if J-I==1       

      if A(I,J) ~= 0

       C=A(I:J,I:J);   

       K=eig(C);

       K=sort(K);

       A(I:J,I:J)=diag(K); % присваиваем А матрицу, на главной дагонали

                           %которой находятся собственные значения

      end

     end

    end

  end

e=norm(A-D);             % выводим погрешность

 

Вызываем матрицу в головной программе как одну из стандартных функций MATLAB:

>> [A,R,e]=SobZn(matr)

 

Где A – матрица, на главной диагонали которой находятся собственные значения. R – матрица, столбцы которой содержат собственные вектора. e – погрешность, с которой рассчитаны собственные значения.

 

 

 

 

 

Протестируем программу для  различных матриц:

1. Симметричная трехдиагональная хорошо обусловленная матрица размерности 3х3:

function[A]=matr

A=[1 2 0;2 1 3;0 3 4];

 

Известны ее собственные значения:

   -1.9027

    1.8121

    6.0906

 

Получаем результат:

>> [A,R,e]=SobZn(matr)

 

A =

 

   -1.9027         0    0.0000

         0    1.8121         0

    0.0000         0    6.0906

 

 

R =

 

    0.5234   -0.8234    0.2192

   -0.7596   -0.3343    0.5578

    0.3861    0.4584    0.8005

 

 

e =

 

  2.7231e-010

 

2. Симметричная трехдиагональная хорошо обусловленная  матрица размерности 5х5:

function[A]=matr

A=[1 2 0 0 0 ;2 4 8 0  0; 0 8 3 4 0; 0 0 4 1 6; 0 0 0 6 8];

 

Известны ее собственные значения:

   -6.5456

   -1.4764

    1.3406

   10.4669

   13.2144

 

Получаем результат:

>> [A,R,e]=SobZn(matr)

 

A =

 

   -6.5456         0         0         0         0

         0   -1.4764         0         0         0

         0         0    1.3406         0         0

         0         0         0   10.4669         0

         0         0         0         0   13.2144

 

 

R =

 

   -0.1363    0.3659    0.9108   -0.1054    0.0830

    0.5144   -0.4531    0.1551   -0.4988    0.5072

   -0.6440    0.2187   -0.2793   -0.3769    0.5634

    0.5080    0.6615   -0.1944    0.2941    0.4244

   -0.2096   -0.4188    0.1751    0.7153    0.4883

 

 

e =

 

  6.6613e-015

 

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

 

3. Симметричная трехдиагональная матрица размерности 3х3:

function[A]=matr

A=[0.1 0.1 0; 0.1 0.11 0.12; 0 0.12 0.111];

 

Известны ее собственные значения:

   -0.0481

    0.1045

    0.2646

 

Получаем результат:

>> [A,R,e]=SobZn(matr)

 

A =

 

   -0.0481         0         0

         0    0.1045         0

         0         0    0.2646

 

 

R =

 

    0.4746   -0.7670    0.4319

   -0.7027   -0.0346    0.7107

    0.5301    0.6407    0.5554

 

 

e =

 

  1.6653e-016

 

4. Симметричная трехдиагональная разреженная матрица размерности 6х6:

function[A]=matr

A=[0 1 0 0 0 0;1 2 0 0 0 0;0 0 0 1 0 0;0 0 1 1 0 0;0 0 0 0 2 0;0 0 0 0 0 1];

 

Известны ее собственные значения:

   -0.6180

   -0.4142

    1.0000

    1.6180

    2.0000

    2.4142

 

Получаем результат:

>> [A,R,e]=SobZn(matr)

 

A =

 

   -0.6180         0         0         0         0         0

         0   -0.4142         0         0         0         0

         0         0    1.0000         0         0         0

         0         0         0    1.6180         0         0

         0         0         0         0    2.0000         0

         0         0         0         0         0    2.4142

 

 

R =

 

         0   -0.9239         0         0         0    0.3827

         0    0.3827         0         0         0    0.9239

   -0.8507         0         0    0.5257         0         0

    0.5257         0         0    0.8507         0         0

         0         0         0         0    1.0000         0

         0         0    1.0000         0         0         0

 

 

e =

 

  8.8818e-016

 

5. Симметричная трехдиагональная матрица размерности 6х6:

function[A]=matr

A=[1 100 0 0 0 0 0;

   100 23 15 0 0 0 0;

   0 15 43 10 0 0 0;

   0 0 10 11 93 0 0;

   0 0 0 93 32 14 0;

   0 0 0 0 14 28 33;

   0 0 0 0 0 33 18];

       

Известны ее собственные значения:

  -89.3848

  -73.5182

  -10.1722

   41.8099

   55.8294

  114.0294

  117.4064

 

Получаем результат:

>> [A,R,e]=SobZn(matr)

 

A =

 

  Columns 1 through 6

 

  -89.3817         0         0         0         0         0

         0  -73.5216         0         0         0         0

         0         0  -10.1722         0         0         0

         0         0         0   41.8099         0         0

         0         0         0         0   55.8298         0

         0         0         0         0         0  114.0294

         0         0         0         0         0         0

 

  Column 7

 

         0

         0

         0

         0

         0

         0

  117.4064

 

 

R =

 

  Columns 1 through 6

 

    0.7392    0.0321   -0.0031    0.1584   -0.0160   -0.6233

   -0.6681   -0.0239    0.0003    0.0647   -0.0087   -0.7045

    0.0778   -0.0602    0.0201   -0.9752    0.0872   -0.1201

   -0.0277    0.7368   -0.1072    0.0191    0.1250    0.2038

    0.0216   -0.6631    0.0223    0.1112    0.0509    0.2387

   -0.0028    0.1036    0.6452   -0.0488   -0.7437    0.0447

    0.0009   -0.0374   -0.7558   -0.0676   -0.6487    0.0154

 

  Column 7

 

   -0.1968

   -0.2291

   -0.1298

   -0.6224

   -0.6981

   -0.1246

   -0.0414

 

 

e =

 

    0.0035

 

 

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

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

Числом обусловленности матрицы А называется число

 

 

Возьмем матрицу А

function[A]=matr

A=[1/100001 1/100001 0; 1/100001 1/100002 0;0 0 1/100001];

 

Найдем ее число обусловленности:

>> cond(А)    //функция MatLab для нахождения числа обусловленности

 

ans =

 

  4.0001e+005             //число обусловленности матрицы порядка 10⁵

Матрица А является плохо обусловленной.

Проверим функцию, реализующую  QL алгоритм на данной матрице:

Известны собственные значения матрицы:

1.0e-004 *

   -0.0000

    0.1000

    0.2000

 

Результат, полученный с помощью функции:

>> [A,R,e]=SobZn(matr)

A =

 

  1.0e-004 *

 

   -0.0000         0         0

         0    0.1000         0

         0         0    0.2000

 

R =

 

    0.7071         0   -0.7071

   -0.7071         0   -0.7071

         0    1.0000         0

 

e =

 

  6.7763e-006

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