Методы поиска собственных значений
Методы поиска собственных значенийСкачать файл - Методы поиска собственных значений
Проблема собственных значений Анатолий Файфель 0. Эти задачи решены разными математиками в разное время и много раз. Но прежде, чем рассказывать о методах решения точнее, здесь пойдет речь об одном методе — методе вращений , предложенным Якоби нужно рассказать о самой задаче. Потом я напишу две версии программы. Одну не оптимизированную, другую оптимизированную. А в качестве программного средства буду использовать MS Excel и VBA. Готов дать необходимые разъяснения по этому поводу. MS Excel хорош тем, что позволяет скромными средствами добиться приятного внешнего вида. Я приведу обе программы полностью и в коде выделю курсивом, части относящиеся к красивизму, а не к алгоритму. Вы убедитесь, что это совсем немного. Выражение в скобках определяет матрицу: Оно имеет решение, если главный определитель равен нулю: Это и будут собственные значения. В конце концов, получим n собственных векторов. Вот здесь и возникли проблемы, о которых идет речь в названии статьи. Ведь для решения нужно составить уравнение 1. То есть нужно решить n матричных уравнений. Задача получается достаточно объемной. В литературе можно еще встретить обозначение tr. А почему бы нам просто не сметить базис, таким образом, чтобы в новой матрице все элементы, кроме стоящих на главной диагонали, обнулились? Если нам это удастся сделать, то вектора задающие новый базис будут собственными векторами, а элементы стоящие на главных диагоналях — собственными значениями. Потому, что с несимметричными матрицами дело обстоит гораздо сложнее. К тому же, симметричные матрицы встречаются в приложениях гораздо чаще. Для перехода к новому базису, Якоби предложил следующее преобразование. Сохраняются собственные значения и собственные векторы. Суть метода Якоби заключается в алгоритме построения последовательности матриц вращения: Во-первых, каково значение угла? Ответ на второй вопрос дает свойство 2. Для ответа на первый вопрос, придется проделать несколько преобразований рекомендую это проделать самостоятельно. В итоге, получим следующие формулы: Самое главное, что при таком преобразовании сохранились собственные значения и вектора см. А что делать дальше? Совершенно верно, произвести те же операции с новой матрицей. Более вдумчивый читатель, может задать справедливый вопрос: Так что же, метод не работает? Спешу вас успокоить, не всё впустую… Элемент, убитый на предыдущем шаге может возникнуть, но уже меньший по модулю! В книге \\\\\\\\\\\\\\\[1\\\\\\\\\\\\\\\] авторами доказывается сходимость данного метода. Преобразования мы будем выполнять, до тех пор, пока максимальный недиагональный элемент по модулю не будет превышать указанной точности. Настало время, когда можно перейти к программе. Нет смысла приводить здесь весь код программы, его можно скачать здесь. Я дам лишь небольшой комментарий. В модуле mdlMain находится несколько процедур и функция. Clear - Процедура отчистки рабочей области. Вызывается из меню и из главной процедуры. Row параметр, номер строки откуда выводить. FirstMatr — первый массив, SecondMatr — второй массив, ResMatrix — результирующий массив. Sp As Double - Функция вычисления следа матрицы. Напомню, след должен сохраняться см. Сейчас перечислю константы и локальные переменные, описанные в модуле mdlMain. Для экономии места и слов приведу листинг. Полностью ее можно найти в файле Matrix Посчитали собственные значения и собственные вектора. Но как проверить правильность результата? Для тестирования предлагаю следующее: Создаем диагональную матрицу, случайным образом вращаем ее, а потом запускаем алгоритм диагонализации. Для этих целей написана процедура MyGenerate. Ниже привожу результат работы этой программе в отладочном режиме. Диагональная матрица, сформированная процедурой MyGenerate. Та же матрица после вращения. Матрица, представленная в Таблице 4. На главной диагонали собственные значения. Таблица собственных векторов матрицы предстваленой в Таблице 4. К сожалению, я никак не могу прокомментировать это факт. Переставлены и переставлены, никакого противоречия тут нет. Никто и не обещал, что матрицы будут совпадать один в один. Главное, что они удовлетворяют определению. Нет, еще не всё. В самом начале я обещал дать две программы. Он будет работать быстрее и требовать меньше памяти. У меня четвертый пень, памяти пол гига! Что тут твои матрицы??? Подумаешь, будут они считаться 10 секунд или 5 секунд!!! Но приведу три возражения. Согласитесь, один месяц и две недели — есть разница! Во-вторых, при работе со специальным оборудованием пример: И, наконец, в-третьих, хороший алгоритм это же красиво! Достаточно хранить только верхний или нижний треугольник часть, матрицы лежащая выше или ниже главной диагонали, соответственно. Реализуем это следующим образом: Во всех местах, где мы обращаемся к элементам матрицы, будем вызывать специальную функцию GetIndex , которая по двум индексам квадратной матрицы будет давать нам индекс в одномерном массиве. Такая оптимизация даст нам, например, для матрицы размер 20 на 20, следующие преимущества: Теперь подумаем, нужно ли выполнять полное умножение матриц при вращении? Так, как матрица 2. Все равно получится 0. Для вращения авторы \\\\\\\\\\\\\\\[1\\\\\\\\\\\\\\\] предлагают воспользоваться следующими преобразованиями: Я предлагаю использовать вот эти соотношения: В итоге получаем операторов выполняются за одну итерацию. Получаем оператор за одну итерацию. Почти в 40 раз меньше! Нужен ли еще какой-нибудь комментарий? А откуда будет вызывать главная процедура Main? Процедура создания меню AddMenu вызывается когда пользователь открывает нашу рабочую книгу или в том случае, когда пользователь переключается от одной открытой рабочей книги к нашей. В нашем меню оно называется Matrix будет два элемента: При нажатии выполняется процедура Main. Вызывается процедура Clear — очистка рабочей области. Присылайте мне ваши замечания и рекомендации сюда. Сайт создан в системе uCoz. На самом деле никакой проблемы уже нет. Оно имеет решение, если главный определитель равен нулю:. Когда мы решим это уравнение, получим n значений. Это выражение называется следом и обозначается Sp. Якоби математик XIX века рассматривал вещественную симметричную матрицу. Изменяются только элементы, стоящие в i- ой и j- ой строке и в j- м и i- м столбце;. В итоге, получим следующие формулы:. Несмотря, на то, что формулы страшные, преобразования действительно не сложные и под силу хорошему девятикласснику, если ему объяснить, как умножаются матрицы. Переходим к реализации алгоритма. К алгоритму никакого отношения не имеет;. Show Row As Long - Процедура вывода матрицы на рабочий лист. MultMatrix FirstMatr As Double , SecondMatr As Double , ResMatrix As Double - Процедура умножения матриц. Все массивы размерности N на N;. Transp InputMatrix As Double - Процедура транспонирования матрицы. Входной параметр InputMatrix — массив опять же размерности N на N;. Swap A As Double , B As Double - Процедура , меняющая значения две переменных A и B. MyGenerate - Процедура формирующая диагональную матрицу и вращающая ее произвольным образом. Результатом работы этой процедуры будет симметричная матрица;. Main - Из названия видно, что это главная процедура. Private Declare Sub Sleep Lib 'kernel32' ByVal dwMilliseconds As Long - Это API-шная функция, используется для задержки выполнения. Private Row As Long. И вот, мы запустили программу, сгенерировали симметричную матрицу. Для тестирования предлагаю следующее:. При внимательном сравнении Таблицы 4. Этот алгоритм можно оптимизировать. Так как матрица симметричная, то нет необходимости хранить ее полностью. Такая оптимизация даст нам, например, для матрицы размер 20 на 20, следующие преимущества:. Для вращения авторы \\\\\\\\\\\\\\\[1\\\\\\\\\\\\\\\] предлагают воспользоваться следующими преобразованиями:. Точно по тем же причинам, нет необходимости при вычислении собственных векторов полностью умножать друг на друга матрицы. Я предлагаю использовать вот эти соотношения:. Теперь оценим, сколько операторов мы будем выполнять за одну итерацию для матрицы размером 20 на В нашем меню оно называется Matrix будет два элемента:.
Object not found!
Алгоритм вычисления собственных значений
Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
Как отрегулировать карбюратор иж
Магазин азбука мебели каталог южно сахалинск
Общие правила взрывобезопасности 2016