Обратная итерация

Cтраница 1

Обратная итерация была предложена как способ улучшения приближенного собственного вектора. Применение автоматических вычислений на ЭВМ привело к естественному вопросу, может ли этот метод находить собственные векторы, если используется как самостоятельный. Наш анализ обратной итерации с фиксированным сдвигом показывает, что сходимость имеет место для всех начальных векторов, которые не ортогональны к искомому собственному вектору. Необходима, однако, некоторая оговорка: если у А-о есть пара наименьших собственных значений, то ХА не знает, к какому из соперничающих собственных векторов ей следует сходиться, хотя она без всякого колебания приближается к натянутому на них подпространству. [2]

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

Обратные итерации особенно эффективны, когда матрица А симметричная. [4]

Обратную итерацию часто ( хоть и не всегда) используют со сдвигом о, очень близким к некоторому собственному значению Kj. Программы INVIT и TINVIT из EISPACK берут в качестве о вычисленное собственное значение, а оно часто является верным во всех своих разрядах. Одним из основных фактов матричных вычислений является то, что ошибки округлений могут приводить к совершенно ошибочным решениям очень плохо обусловленных систем уравнений. Поэтому ситуация на первый взгляд такова: выигранное благодаря удачному сдвигу в теоретической скорости сходимости теряется на практике из-за нескольких ошибок округлений. И в самом деле, некоторые учебники предостерегают пользователей, чтобы они не брали значение о, очень близкое к какому-либо собственному значению. [5]

Процедура обратной итерации эффективна при решении частной проблемы собственных значений, т.е. при выделении одного собственного значения. В процессе вычислений приходится иметь дело с плохо обусловленной матрицей, однако процедура быстро сходится, если удачно выбрано начальное приближение. Оператор ( А - Е) увеличивает проекцию вектора, на который он действует, в направлении собственного вектора и подавляет все остальные проекции. В качестве начального приближения целесообразно выбирать равновесную функцию распределения. Вычислительная практика показывает, что такое начальное приближение обеспечивает сходимость процедуры обратных итераций к искомому минимальному по модулю собственному значению, т.е. к константе скорости. [6]

Метод обратных итераций сходится очень быстро; чаще всего требуется сделать 1 - 3 итерации. [7]

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

Метод обратной итерации реализован посредством решения соответствующих уравнений методом исключения Гаусса с частичным выбором главного элемента. Когда AJ, комплексное, вычисления выполняют с использованием комплексной арифметики и вспомогательного массива Ь размерности ( п 2) Х п; воспользовавшись тем, что исходная матрица задана в форме Хессенберга, нижний левый треугольник массива Ь с основанием и высотой из п элементов используют для записи мнимых частей элементов матрицы приведения к треугольной форме. [9]

Естественное обобщение обратной итерации состоит в том, чтобы менять сдвиг от шага к шагу. [10]

В контексте обратной итерации единственный вектор, которым мы располагаем на fe - м шаге, - - это текущее приближение uk к собственному вектору; естественно поэтому брать в качестве сдвига отношение Релея. Однако в случае QL-алгоритма имеется матрица Ал, и потому можно вычислить более точное приближение к A.J. Более того, если А1 трехдиагональная, то это уточненное значение можно получить очень малой ценой. Прежде чем подробно обсудить такие сдвиги, посмотрим на результат одного QL-преобразования с произвольным сдвигом а для трехдиагональной матрицы А. [11]

При выполнении обратной итерации или вычислении определителя матрицы А появление нулевого главного элемента не нарушает работу программы. При этом нулевое значение det ( A - XI) не приводит к ошибкам. Однако появление нулевого главного элемента при решении систем уравнении означает, что матрица А - XI стала вырожденной из-за ошибок округления, и в этом случае необходимо прекращать выполнение процедуры. [12]

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

Более целесообразно выполнять обратные итерации несколько иначе. [14]

Наиболее важным вариантом обратной итерации является итерация с отношением Релея. Мы увидим, что этот метод сходится для почти всех начальных приближений, как бы они ни были плохи, и что впоследствии, обычно после двух или трех шагов, число верных знаков утраивается на каждой итерации. [15]

Страницы: 1 2 3 4