Проблема собственных значений

     РЕФЕРАТ 

     Курсовая  работа 28 страниц, 7 таблиц,7 источников. 

     Ключевые  слова: собственные значения, метод Якоби, преобразование Хаусхолдера, симметричные матрицы,  трехдиагональная форма, QL-алгоритм.  

     Объект  исследования: проблема собственных значений. 

     Предмет исследования: методы и алгоритмы, решения проблемы собственных значений. 

     Методы  исследования: анализ, численное исследование .  

     Цель  курсовой работы: Ознакомиться и изучить проблему собственных значений исследование эффективных методов ее решения проблемы собственных значений. 

     Задачами  курсовой работы являются: Определение эффективности работы  алгоритмов решения проблемы собственных значений. 

     Выводы: Ознакомился с понятием собственные значения. Провели исследование эффективных  методов ее решения, а так же провели численные эксперименты и анализировали их результат. 
 
 
 

     СОДЕРЖАНИЕ

 
 
 

 

      Введение.

      

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

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

     В данной работе будут рассмотрены  наиболее эффективные методы  решения задач на собственные значения.  
 
 
 
 
 
 
 
 
 
 
 
 

1. Классификация методов решения проблем собственных значений 

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

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

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

     4.Для   очень больших матриц первостепенное  значение при выборе алгоритма  может иметь  экономия памяти.

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

2. Эффективные методы решения проблем собственных значений. 

1.Метод  Якоби для действительных  симметрических матриц. 

     Предлагаемый  алгоритм реализует построчный поиск  максимального по модулю  элемента правом верхнем углу исходной симметричной матрицы. Алгоритм пригоден для любых действительных симметричных матриц. Он построен таким образом, что обеспечивает точность, сравнимую с точностью той вычислительной машины, на которой реализован алгоритм. Обычно для этого требуется примерно 6-10 циклов, или приблизительно 3n²/5n²  вращений Якоби.

     Однако  необходимо признать. Что хотя метод  Якоби достаточно компактен и  изящен он требует большего времени  для вычислений, чем сочетание  метода Хаусхолдера  и  QL -алгоритма с неявными сдвигами. Поэтому при  больших порядках исходных матриц  предпочтительнее использовать эти процедуры вместо процедуры Якоби. Более того, метод Якоби не использует преимуществ симметрических ленточных матриц. Ширина

     которых мала по сравнению с их порядком n.

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

       

     A->D=V^TAV 

     где D – диагональная, а V – ортогональная матрица. Матрица D является пределом, к которому стремится последовательность матриц A_k при k->∞, а V – произведение всех промежуточных матриц плоских вращений, используемых для диагонализации исходной матрицы, т.е. 

     V=U₀U₁U₂… 

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

      

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

     Преобразование Хаусхолдера позволяет привести действительную  симметрическую матрицу A₁ к симметрической трехдиагональной форме A_n-1.  Если  преобразование Хаусхолдера используется в сочетании с QL - алгоритмом то собственные векторы исходной матрицы A будут вычислены автоматически. Алгоритм Хаусхолдера приводит симметричную матрицу A размером (n x n) к трехдиагональной форме за (n - 2) ортогональных преобразований. Каждое преобразование уничтожает требуемую часть целой строки и целого соответствующего столбца. Базовой матрицей является матрица Хаусхолдера P, имеющая форму  

     P = 1 - 2ww^T 

     ,где  w - действительный вектор такой что |w|² = 1. (матричное, произведение векторов a и b записывается как ab^T, в то время как скалярное произведение этих векторов a^Tb). Матрица P является ортогональной, поскольку 

     P² = (1 – 2ww^T)(1 – 2ww^T) = 1 – 4ww^T + 4w(w^Tw)w^T = 1 

     Таким образом, P = P^-1. Но P^T = P, следовательно P^T = P^-1, что и доказывает ортогональность. Перепишем P как  

     P = 1 - (uu^T)/H 

     где  H = |u|²/2 и теперь u может быть любым вектором. Пусть x - вектор, составленный из первого столбца матрицы A. Выберем u = x – s|x|e₁, где e₁ - единичный вектор [1, 0,...,0]^T, s - либо 1, либо -1, а выбор знака s будет сделан позже. Тогда  

     Px = x - (u(x - s|x|e₁)^Tx)/H = x - (2u(|x|² - s|x|x₁))/(2|x|² - 2s|x|x₁) = x - u = s|x|e₁ 

     Это показывает, что матрица Хаусхолдера  P действует на заданный вектор x, уничтожая все его элементы, кроме первого. Для приведения симметричной матрицы A к трехдиагональной форме, вектор x, который будет образовывать первую матрицу Хаусхолдера, составим из нижних n - 1 элементов первого столбца. Тогда будут обнулены нижние n - 2 элемента.

3. QL-алгоритм с неявными сдвигами.

     QL-алгоритм со сдвигом, определен следующими соотношениями:

                        U_s(A_s – k_sI)=L_s ;   A_s+1=L_sU_s^T+k_sI;  A_s+1=U_sA_sU_s^T          (1)

     где  U_s-ортогональная; L_s- нижняя  треугольная матрица; k_s –сдвиг, соответствующий наименьшему по модулю собственному значению ведущего минора размера 2 на 2  матрицы A_s.  Алгоритм с неявным сдвигом основан на следующей лемме: если A – невырожденная симметричная матрица и выполняется условие

                                                     BU=UA                                              (2)

     где U –ортогональная; B – трехдиагональная матрица с положительными вне диагональными элементами, то матрицы U и B полностью определены последней строкой матрицы U. Это  легко проверить последовательным сравнением строк  n, n-1,…1,  обеих частях уравнения (2). Поэтому, если  каким – либо методом определить трехдиагональную матрицу A_s+1 такую, что

                                                    Ā_s+1=Ū_sA_sŪ_s^T                                                               (3)

     Где Ū_s - ортогональная матрица, то при совпадении последних строк матриц Ū_s и U_s из уравнений (1) выполняется соотношение U_s= Ū_s и Ā_s+1=A_s+1. В первоначальном алгоритме матрица Q_s определяется как произведение n-1 матриц плоских вращений

     U_s = E₁^(s)E₂^(s)…E_n-1^(s)

     где E_i^(S) –матрица вращения в плоскости (i, i+1). Заметим, что последняя строка матрицы U_s  является последней строкой матрицы E_n-1^(s). В алгоритме с неявным сдвигом матрица Ū_s, удовлетворяющая уравнению (3), вычисляется как произведение матриц плоских вращений Ē₁^(s), Ē₂^(s) ,…, Ē_n-2^(s), Ē_n-1^(s) . QL-алгоритм  предназначен для определения всех собственных значений симметрической трехдиагональной матрицы.

 
 
 
 
 
 
 
 

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

1.Метод  Якоби для действительных  симметрических матриц.

     Параметры:

     N - порядок исходной матрицы (тип:  целый);

     A - вещественный двумерный массив размерности N на 3, содержащий в последних N - 1 компонентах первого столбца элементы нижней диагонали, во втором столбце - элементы главной диагонали, в первых N - 1 компонентах третьего столбца - элементы верхней диагонали;

     EV -вещественный одномерный массив  размерности N, содержащий вычисленные  собственные значения в возрастающем  порядке; 

     RAB - вещественный одномерный массив  размерности 2*N, используемый как  рабочий;

     IERR - целая переменная, служащая для  сообщения об ошибках, обнаруженных в ходе работы подпрограммы, при этом:

     а) значение IЕRR больше N, если не все попарные произведения соответствующих элементов  побочных диагоналей неотрицательны

     б) значение IЕRR полагается равным номеру собственного значения, для вычисления которого потребовалось более 30 итераций, при этом собственные значения с индексами 1, 2, ..., IЕRR - 1 вычислены правильно и расположены в возрастающем порядке, но они не обязательно являются самыми меньшими из всех N собственных значений.