2. РЕШЕНИЕ ПОЛНОЙ ЗАДАЧИ О СОБСТВЕННЫХ ЗНАЧЕНИЯХ

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

В этом случае столбцы матрицы будут собственными векторами, а собственными значениями матрицы

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

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

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

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

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

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

Метод вращений имеет несколько вычислительно-ориентированных модификаций, сокращающих непроизводительные затраты машинного времени на поиск наибольшего по модулю внедиагонального элемента (циклический метод вращений, метод вращений с барьерами [22]) или уменьшающих влияние ошибок округления [106]. Метод гарантирует точность, сравнительную с точностью вычислительной машины, на которой реализован алгоритм. Для этого требуется от 6 до 10 циклов или от до вращений. Метод прост и компактен. Этот метод неэффективен при использовании двухступенчатой памяти. По затратам машинного времени он уступает методам, основанным на предварительном приведении к трехдиагональной форме, поскольку не использует преимуществ симметричных ленточных матриц.

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

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

Этот алгоритм реализован в подпрограмме Оператор обращения к подпрограмме в случае задачи (3) с матрицей имеет вид Здесь число степеней свободы; матрицы инерционнмх и квазиупругих коэффициентов соответственно; X — вектор, содержащий вычисленные частоты — матрица, столбцы которой являются собственными формами

Обобщение метода вращений. В основе обобщений лежит следующее соотношение:

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

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

В качестве матрицы можно взять

Если представить матрицу в виде суммы где и -соответственно симметричная и кососимметричная матрицы, то справедливо соотношение

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

соответствуют комплексным собственным значениям матрицы

Может оказаться, что один из блоков имеет где кососимметричная матрица. Тогда действительные части собственных значений этого блока равны а мнимые части равны собственным значениям матрицы

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

Методы, основанные на приведении симметричной матрицы к трехдиагональной форме. Эти методы позволяют использовать свойства симметричных трехдиагональ-ных матриц

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

Последовательность полиномов является последовательностью Штурма. Пусть величины вычислены для некоторого

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

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

В методе Гивечса исходная симметричная матрица приводится к симметричной трехдиагональной форме путем элементарных преобразований подобия с матрицами вращения (8). С учетом симметрии для этого требуется выполнить около умножений и извлечений квадратных корней. В классической схеме метода Якобн на одном цикле выполняется около умножений и извлечений квадратных корней.

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

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

Для вычисления отдельных собственных векторов трехдиагональной матрицы эффективен метод обратной итерации [106]. Если требуется вычислить все собственные векторы, то наиболее эффективным окажется применение методов LR- и -алгоритмов к трехдиагональной матрице.

Задачи о собственных колебаниях в форме (2) или (3) необходимо предварительно привести к задачам с симметричной матрицей по методу квадратного корня. В противном случае несимметричные матрицы преобразуют к верхней или нижней почти треугольной форме (форме Хессенберга). Этот процесс может быть осуществлен теми же устойчивыми преобразованиями и требует того же числа действий, что и для симметричных матриц.

LR- и QR-алгоритмы. Они относятся к универсальным алгоритмам. Алгоритм Рутисхаузера [22, 106] основан на разложении матрицы на произведение двух треугольных где нижняя треугольная матрица с единичными элементами на главной диагонали, верхняя треугольная матрица. Такая факторизация всегда существует, если главные диагональные миноры матрицы не обращаются в нуль. Из соотношения следует, что произведение сомножителей в обратном порядке является матрицей, подобной В LR-алгоритме этот процесс повторяется многократно: В пределе стремится к к верхней треугольной матрице с собственными значениями на главной диагонали в порядке убывания. Объем вычислений на одном шаге составляет около умножений, причем половина из них необходима для разложения на сомножители; поддиагональные элементы стремятся к нулю, как Поэтому для сокращения объема вычислений исходную матрицу следует сначала привести к верхней почти треугольной форме. Эта форма является инвариантной относительно -алгоритма (этим же свойством обладает и ленточная форма). Если вместо использовать матрицу то элемент стремится к нулю, как , и если у — достаточно хорошее приближение к то будет быстро убывать. Один из способов ускорения сходимости состоит в том, что сдвиг осуществляется на каждом шаге: причем в качестве принимают последний диагональный элемент матрицы

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