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

Реферат

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

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

Объем пояснительной записки - !!!!!!! листов.

Количество приложений - !!!!!!.

При написании пояснительной записки было использовано 9 литературных источников.

Перечень ключевых слов: метод Данилевского, собственные значения, собственные вектора, каноническая форма Фробениуса.

Содержание

Введение

1. Теоретическая часть

1.1 Точные методы решения систем линейных алгебраических уравнений

1.2 Погрешности при численном решении задач

1.3 Классификация погрешностей, возникающих при решении системы линейных алгебраических уравнений. Оценка погрешности решения системы линейных алгебраических уравнений

1.4 Мера обусловленности системы линейных алгебраических уравнений и матрицы

1.5 Собственные значения и собственные вектора матрицы

1.6 Метод А.М. Данилевского нахождения канонической формы Фробениуса матрицы

1.7 Исключительные случаи в методе А.М. Данилевского

1.8 Вычисление собственных векторов в методе А.М. Данилевского

1.9 Итерационный метод вращений Якоби решения симметричной полной проблемы собственных значений

1.10 Методы решения обобщенной проблемы собственных значений

Введение

данилевский уравнение алгебраический погрешность

Целый ряд инженерных задач сводится к рассмотрению систем уравнений, имеющих единственное решение лишь в том случае, если известно значение некоторого входящего в них параметра. Этот особый параметр называется характеристическим, или собственным значением системы. С задачами на собственные значения инженер сталкивается в различных ситуациях. Так, для тензоров напряжений собственные значения определяют главные нормальные напряжения, а собственными векторами задаются направления, связанные с этими значениями. При динамическом анализе механических систем собственные значения соответствуют собственным частотам колебаний, а собственные вектора характеризуют моды этих колебаний. При расчете конструкций собственные значения позволяют определять критические нагрузки, превышение которых приводит к потере устойчивости. Выбор наиболее эффективного метода определения собственных значений или собственных векторов для данной инженерной задачи зависит от ряда факторов, таких, как тип уравнений, число искомых собственных значений и их характер. Алгоритмы решения задач на собственные значения делятся на две группы. Итерационные методы очень удобны и хорошо приспособлены для определения наименьшего и наибольшего собственных значений.

1. Теоретическая часть

1.1 Точные методы решения систем линейных алгебраических уравнений

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

Пусть дана система n уравнений с n неизвестными и с определителем, отличным от нуля. Тогда по теореме Крамера система имеет единственное решение, и значения неизвестных выражаются в виде отношения двух определителей порядка n. При этом число различных определителей в отношении равно . Для решения необходимо выполнить умножений и делений. Здесь не учтены простые операции сложения и вычитания. Уже при n=20 число операций равно приблизительно и является настолько большим, что становится невозможным решать указанным путем на современных ЭВМ систему даже двадцати уравнений.

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

1.2 Погрешности при численном решении задач

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

Неточность информации о решаемой задаче

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

Погрешность аппроксимации

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

1.3 Классификация погрешностей, возникающих при решении системы линейных алгебраических уравнений. Оценка погрешности решения системы линейных алгебраических уравнений

Оценка погрешности решения системы

Пусть рассматривается система

, (1)

где - точное решение.

В действительности решается система с изменёнными матрицей и свободным вектором:

, (2)

где - изменённая матрица; - изменённый свободный вектор.

Представим решение системы (2) в виде

,

где - погрешности решения.

Подставляя в (2), получим с учётом обозначений сначала

,

затем после преобразований

.

Вычтем из этого выражения выражение (1) и получим

.

С учётом равенства , получим систему уравнений

,

из которой следует:

. (3)

Из этого выражения для погрешности решения сразу получается нужная оценка

1.4 Мера обусловленности системы линейных алгебраических уравнений и матрицы

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

Под мерой обусловленности системы понимают следующую величину

, (4)

где .

Здесь подразумеваются нормы матрицы, подчиненные норме вектора.

По этому определению верна следующая оценка для погрешности решения

(5)

Вычислим значение . Так как , если матрица задана точно (см. выражение (3)), то

. (6)

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

С учётом этого выражение для (см. (4)) запишется в виде:

. (7)

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

,

где - мера обусловленности матрицы .

Тогда неравенство (5) может быть заменено неравенством:

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

Так как

то для с учётом (7) получаем следующее значение

.

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

.

Тогда

.

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

«Говорят, что система линейных уравнений является плохо обусловленной, если, грубо говоря, уравнения почти линейно зависимы».

1.5 Собственные значения и собственные вектора матрицы

Рассмотрим квадратную матрицу n-ого порядка:

Собственные значения _i квадратной матрицы A есть действительные или комплексные числа, удовлетворяющие условию:

,

где E - единичная матрица,

- собственный вектор матрицы A, соответствующий некоторому собственному значению .

Матрица называется характеристической матрицей матрицы A. Т.к. в матрице по главной диагонали стоят , а все остальные элементы равны нулю, то характеристическая матрица имеет вид:

Определитель этой матрицы называется характеристическим или вековым определителем и равен:

В развернутом виде он является многочленом n-ой степени относительно , т.к. при вычислении этого определителя произведение элементов главной диагонали дает многочлен со старшим членом , т.е.

и называется характеристическим многочленом. Корни этого многочлена - собственные значения или характеристические числа матрицы A. Числа называются коэффициентами характеристического многочлена.

Ненулевой вектор называется собственным вектором матрицы A, если эта матрица переводит вектор X в вектор

,

т.е. произведение матрицы A на вектор X и произведение характеристического числа на вектор X есть один и тот же вектор. Каждому собственному значению матрицы соответствует свой собственный вектор .

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

Определитель этой системы равен нулю, т.к. из этого условия были определены собственные значения матрицы A. Следовательно, система имеет бесконечное множество решений. Ее можно решить с точностью до постоянного множителя (как систему однородных уравнений). Решив эту систему, мы найдем все координаты собственного вектора X. Подставляя в систему однородных уравнений поочередно , получаем n собственных векторов.

1.6 Метод А.М. Данилевского нахождения канонической формы Фробениуса матрицы

Метод основан на подобном преобразовании матрицы. Он относится к числу наиболее быстрых методов. Известно, что подобное преобразование матрицы не изменяет её собственного многочлена.

Действительно,

если , то .

В качестве матрицы в методе А.М. Данилевского принимается каноническая форма Фробениуса:

.

Коэффициенты первой строки этой матрицы совпадают с коэффициентами собственного многочлена. В этом можно убедиться при помощи разложения определителя по элементам столбцов матрицы :

=

.

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

Начнем преобразование с элементов последней строки. Предположим, что элемент последней строки матрицы отличен от нуля. Разделим на него -й столбец матрицы . Тогда последняя строка матрицы примет вид:

.

Затем будем умножать полученный -й столбец на и вычитать из -го столбца. Проделав это преобразование для , приведем последнюю строку к виду Фробениуса . Можно проверить, что такое преобразование матрицы равносильно умножению её справа на матрицу

.

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

В результате первого шага преобразований получим:

.

Второй шаг преобразований аналогичен первому и состоит в приведении предпоследней строки матрицы к виду Фробениуса при условии неизменности последней её строки.

Предположим, что элемент матрицы отличен от нуля. Тогда

,

.

В результате второго шага преобразований получим

Таким образом, в регулярном случае, когда коэффициенты , , …, , после выполнения шагов изложенных преобразований матрица будет приведена к каноническому виду Фробениуса

, (4)

где , .

Затем по первой строке полученной матрицы составляется искомый собственный многочлен матрицы .

1.7 Исключительные случаи в методе А.М. Данилевского

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

Пусть , , т.е. имеется ненулевой элемент слева от нулевого элемента. Тогда этот ненулевой элемент выдвигаем на место нулевого элемента , т.е. переставляем -й и -й столбцы и строки. Такое преобразование матрицы может быть записано в виде:

,

Где

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

Пусть , . Тогда матрица имеет вид

=.

Применяя теорему Лапласа о разложении определителя, получаем

,

где , - единичные матрицы порядков , соответственно.

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

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

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

Для контроля вычислений полезно сравнивать полученное значение коэффициента собственного многочлена со следом матрицы, т.е. проверять выполнение равенства , где . Отметим, что для следа матрицы применяется также обозначение .

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

.

1.8 Вычисление собственных векторов в методе А.М. Данилевского

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

, .

Однако, если построена матрица , с помощью которой приведена к форме Фробениуса , то нахождение собственных векторов упрощается.

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

; (5)

;

.

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

При этом первое уравнение системы (5) приводится к равенству:

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

.

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

. (6)

Для собственного вектора (см. формулу (6)) имеем равенство

.

Так как , то

.

Умножим обе части последнего равенства слева на матрицу , получим равенство:

, (7)

из которого следует:

.

Так как (см. формулу (4)), то для вычисления собственных векторов матрицы получается формула:

.

1.9 Итерационный метод вращений Якоби решения симметричной полной проблемы собственных значений

Метод вращений применим к эрмитовым матрицам с комплексными элементами. Для простоты рассмотрим частный случай эрмитовых матриц - действительных симметричных.

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

, (1)

где - некоторая ортогональная матрица;

- диагональная матрица, элементами которой являются собственные числа матрицы .

Так как для ортогональной матрицы обратная матрица совпадает с транспонированной матрицей: , то равенство (1) равносильно следующему

. (2)

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

, (3)

где - некоторая ортогональная матрица, которая несложно вычисляется;

- квадратная матрица с близкими к нулю недиагональными элементами, так как найти в общем случае трудоемко:

. (4)

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

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

. (5)

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

. (6)

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

Таких процессов может быть построено большое число. Рассмотрим метод вращений. Он достаточно прост по вычислительной схеме и обладает быстрой сходимостью.

Метод вращений Якоби

В методе вращений последовательность матриц строится с помощью ортогональной матрицы вращения:

(7)

Матрица вращений получается из единичной матрицы заменой ее элементов на пересечениях - х и - х строк и столбцов записанными элементами.

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

. (8)

Введем обозначения:

.

Ввиду особой структуры матрицы (7) все столбцы матрицы , кроме - го и - го, будут такими же, как и в матрице . Элементы столбцов номеров и будут вычисляться по формулам:

;

. (9)

Аналогично строки матрицы , кроме - й и - й, будут такими же, как в матрице , а элементы ее строк - й и - й вычисляется по формулам:

;

. (10)

Равенства (9) и (10) позволяют несложно вычислить коэффициенты

,

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

. (11)

Сейчас назначим в выражении (11) такое значение угла , чтобы рассматриваемый элемент обратился в нуль. Из этого условия получаем выражение:

,

из которого находим значение угла

(12)

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

, (13)

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

Тогда на основании выражения (13) верно неравенство:

.

Следовательно, мера уменьшиться при преобразовании (8).

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

По выбору элемента как наибольшего по модулю справедливо неравенство

и, следовательно,

. (14)

С помощью этого неравенства из выражения (13) получается

, (15)

где .

Пусть значение . Тогда величина и из неравенства (15) вытекает цепочка неравенств

.

Так как , то для меры близости матрицы к диагональному виду будем иметь оценку

. (16)

Отсюда следует, что со скоростью не меньшей, чем скорость сходимости геометрической прогрессии со знаменателем .

Рассмотренный метод преобразования подобия с ортогональной матрицей требует выбора среди недиагональных элементов преобразуемой матрицы наибольшего по модулю. Для этого необходимо выполнить приблизительно операций.

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

1.10 Методы решения обобщенной проблемы собственных значений

Решение обобщенной проблемы собственных значений

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

Определение 2. Матрица называется матричным пучком и обозначается .

Если матрица невырожденная, то обобщенная проблема собственных значений эквивалентна стандартной проблеме собственных значений с матрицей .

Решение ряда задач сводится к обобщенной проблеме собственных значений с симметричными действительными положительно определенными матрицами , :

. (1)

Тогда все собственные числа обобщенной проблемы положительны (неотрицательны).

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

Отметим, что обобщенная проблема собственных значений с симметричными действительными положительно определенными матрицами возникает, например, при определении собственных частот линейных колебательных систем с распределенными параметрами вариационными методами математической физики, в том числе методом конечных элементов. При анализе частот собственных колебаний конструкции необходимо решать уравнение (1), в котором искомая величина явно выражена через частоту собственных колебаний конструкции; - общая матрица жесткости конструкции; - матрица масс; - форма собственных колебаний.

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

Рассмотрим первый метод. С помощью преобразования подобия представим в уравнении (1) матрицу в виде разложения на множители:

, (3)

где - ортогональная матрица;

- диагональная матрица, ненулевые элементы которой равны: , ; , - собственные числа матрицы , при этом , ; ; - диагональная матрица, ненулевые элементы которой равны: , .

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

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

Согласно формуле (3) подставим матрицу в уравнение (1), получим

Умножая полученное равенство слева на матрицу , получим:

. (4)

Представим

(5)

и, подставляя это выражение в уравнение (4), приведем его сначала к виду

,

а затем запишем так

. (6)

Уравнение (6) можно представить в стандартном виде

, (7)

где - симметричная матрица.

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

(8)

где - ортогональная матрица;

- диагональная матрица.

На основании выражений (7), (8) запишем равенство

,

из которого следует

, (9)

где - ортогональная матрица, равная произведению обратимых матриц.

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

Собственные векторы проблемы (7) связаны с векторами исходной проблемы (1) соотношением (5).

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

, (10)

где - правая треугольная матрица разложения по схеме метода квадратных корней (разложение Холецкого, см. формулы (11) подраздела).

Подставляя выражение (10) для матрицы в уравнение (1) и умножая его слева на матрицу , получим

.

Затем, подставляя в это уравнение , получим

, (11)

где - симметричная матрица.

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

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

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

3. Разработаны методики ускорения сходимости при решении проблем собственных значений как частичных, так и полной.

Заключение

Во время освоения данного метода я не могла пропустить некоторые минусы метода Данилевского:

- Погрешность накапливается со скоростью геометрической прогрессии.

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

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

Но также нельзя не остановиться на очевидных плюсах метода:

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

- Данный метод очень удобен в программировании (на этапе разработки ПО проблем практически не возникало).

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

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

1. Бахвалов Н.С. Численные методы. М.: Наука, 1987. 600 с.

2. Бусленко H.П., Голенко Д.И., Соболь И.М., Срагович В.Г., Шрейдер Ю.А. Метод статистических испытаний (метод Монте-Карло). М.: Физматгиз, 1962. 332 с.

3. Бусленко Н.П., Шрейдер Ю.А. Метод статистических испытаний (Монте-Карло) и его реализация на цифровых вычислительных машинах. М.: Государственное издательство физико-математической литературы, 1961. 226 с.

4. Демидович Б.П., Марон И.А. Основы вычислительной математики. М.: Наука, 1966. 664 с.

5. Ермаков С.М. Метод Монте-Карло и смежные вопросы. М.: Наука, 1975. 294 с.

6. Калиткин Н.Н. Численные методы. М.: Наука, 1978. 512 с.

7. Копчёнова Н.В., Марон И.А. Вычислительная математика в примерах и задачах. М.: Наука, 1972. 368 с.

8. Соболь И.М. Метод Монте-Карло. М.: Наука, 1985. 80 с.

9. Соболь И.М. Численные методы Монте-Карло. М.: Наука, 1973. 312 с.

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