Диссертация (1150736), страница 22
Текст из файла (страница 22)
Применим лемму 16:(︃ )︃ (︃)︃ (︃)︃(,0)(,0)(,1)̃︀, =. (,0) , ̃︀(,0)(,1)Из рекуррентных уравнений для многочленов Шура следует, что(︃)︃ (,0) , ̃︀(,0)̃︀, = , − = (,0) .det (,0)=̃︀−,,,, ̃︀(,0)137Умножение предыдущего уравнения на обратную матрицу приводит к утверждению леммы.Предположим, что в вершине известны результаты БПФ на 2 отсчетов 2 и 2 . Значения 2 (,0) и 2 (,0) также вычисляются заранеепри интерполяции многочленов Шура, как описано в разделе 4.3.4. В результате умножения получаются многочлены степени 2 − 1. Остается выбратьих часть, вплоть до степени − 1, что сформулировано в следующем утверждении.
В нём обозначает вектор коэффициентов многочлена () пристепенях от 0 до − 1.−1−1Следствие 6 Пусть в условиях леммы 18 ( )2и ( )2есть ДПФ=0=0−1−1на 2 точек от 2 и 2 . Пусть ( )2и ( )2есть ДПФ на=0=02 точек от наборов коэффициентов (,0) () и (,0) (), соответственно.Определим(︃̂︀̂︀)︃=1 (,0)(︃* −*−)︃ (︃)︃,0 ≤ ≤ 2 − 1.−1−1 ̂︀ 2 −1 )2Пусть (̂︀ )2=0 есть результат ОДПФ от векторов ((−1) )=0=0 и (̂︀̂︀ )2 −1 , соответственно.и (=0−1−1(,1)) = (̂︀ )Тогда ((,1) ) = (̂︀ )=0 .=0 и (Доказательство. Если степени многочленов и больше, чем 2 −1, тов силу леммы 18 их усечение до степени 2 − 1 влияет только коэффициентымногочленов (,1) , (,1) при степенях, больших − 1.
Произведение(︃)︃ (︃)︃(,0)(,0)̃︀̃︀ , −2 () =− (,0) , (,0)2 имеет степень не выше 3 − 1, так как многочлены (,0) , (,0) , ̃︀(,0) , ̃︀(,0)имеют степени не выше . В то же время первые коэффициентов многочлена () равны нулю, так как после деления на получается многочленпо лемме 18. Следовательно, многочлен () может иметь ненулевые коэффициенты только при степенях от до 3 − 1 и() = (),deg ≤ 2 − 1.138Первые коэффициентов многочлена () по лемме 18 совпадают с век(,1)торами (,0) col((,1), ) при 0 ≤ ≤ − 1. Вектор ДПФ от () на 22−1− 2 точек совпадает по определению с вектором (( ))2.
По=0 , где = −1 (,0)этому первые коэффициентов в ОДПФ от вектора (( ))2совпа=0 /(,1) (,1)̂︀ )̂︀ , (−1) дают с ( , ). Остаётся доказать, что ( )/ (,0) = col(или что1( ) =(︃*−*)︃ (︃−(−1) (−1) )︃,0 ≤ ≤ 2 − 1.Очевидно, что ( ) = (−1) . Далее, вершина с мультииндексом (, 0)находится на уровне , поэтому ̃︀(,0) () = (,0) ( −1 ) и ̃︀(,0) () = (,0) ( −1 ). Следовательно, при 0 ≤ ≤ 2 − 1̃︀(,0) ( ) = (,0) (* ) = (−1) * ,̃︀(,0) ( ) = (,0) (* ) = (−1) * ,что доказывает утверждение следствия.4.3.6Формулировка быстрого алгоритма ШураВ этом разделе формулируется быстрый алгоритм Шура, основанный насвойствах, установленных в предыдущих разделах.Пусть = 2 и задан первый столбец ( )=0 самосопряжённой тёплицевойматрицы порядка + 1 и 0 = 1.
Требуется найти многочлен Сегё ()степени не выше , порождённый тёплицевой матрицей . Предположим, чтоматрица положительно определена.Построим бинарное дерево высоты , листья которого нумеруются числами = 0, 1, . . . , − 1. Листья образуют нулевой уровень. Пусть 1 ≤ ≤ .Уровень с номером состоит из 2− вершин.
Вершина –го уровня с номером помечаются мультииндексом из нулей и единиц, являющимся двоичнымпредставлением числа . Эта вершина соединяется ровно с двумя вершинами( − 1)–го уровня, двоичное представление которых есть (, 0) и (, 1).Определим функцию Шура∑︀ −10 () = − ∑︀=1.−1=0 139Остаточный член функции 0 порядка обозначим ().Каждая вершина бинарного графа нагружена следующими данными: параметрами многочленов числителя и знаменателя остаточного члена Шура ипараметрами многочленов Шура. Рассмотрим вершину уровня ≥ 0 с номером . Введём обозначение = 2 . С этой вершиной связаны следующиеданные:∙ первые 2 коэффициентов нормированного числителя () и нормированного знаменателя () остаточного члена ();∙ результаты ДПФ 2 ,+2 и 2 ,+2 на 2 точек от многочленовШура порядка 2 , рассчитанных от начальной функции Шура ;−1∙ величина ,+2шагов от на , обратная к остаточной дисперсии за 2чальной функции Шура ().Перед началом работы алгоритма обхода данного дерева все многочленыШура неизвестны, а среди многочленов числителей и знаменателей остаточных членов известными являются только (0, , 0, ).
Это начальные многочлены числителя и знаменателя 0 (). В памяти хранятся ДПФ от коэффициентовмногочленов0, =2∑︁ −1,0, =2∑︁−1=1 ,0 ≤ ≤ .=0Целью алгоритма является вычисление многочленов Шура в корне дерева:(0, (), 0. ()), для чего потребуется вычислить все данные во всех вершинах.Вершины обходятся в лексикографическом порядке. В пройденных вершинах рассчитаны все нагруженные данные. Пройденные вершины определяются следующим образом.С каждой вершиной связывается единственный путь к корневой вершине.Пусть текущая вершина находится на -м уровне и имеет номер < 2− .Существует единственный путь от ней до корневой вершины дерева. Науровне ℓ > этот путь проходит через вершину с номером ℓ = [/2ℓ− ],где [·] — целая часть числа.
Тогда пройденными являются все вершины уровня ℓ ≤ с номером < 2−ℓ ( + 1), а также все вершины уровня ℓ > с140номером > ℓ . При ℓ > в вершине ℓ уже вычислены значения числителя изнаменателя (ℓ ,ℓ , ℓ ,ℓ ), но не значения многочленов Шура (ℓ ,ℓ , ℓ ,ℓ ).Алгоритм обхода дерева.Начальной вершиной является первый лист с мультииндексом =(0, . . .
, 0). В этой вершине заданы значения = 1, = −1 и ( )−1 =1/(1 − |1 |2 ).Бинарное дерево обходится в лексикографическом порядке. Пусть текущая вершина имеет номер на уровне < . Двоичное представление числа образует мультииндекс . Введём также обозначения для порядка = 2многочленов Шура в данной вершине и для номера остаточного члена Шура обозначим ℓ = 2 . В этой вершине уже рассчитаны векторы ℓ,ℓ+ , ℓ,ℓ+ размерности , а также обратная величина к остаточной дисперсии.Обработка текущей вершины состоит из следующих операций. Сначалазначения ДПФ на отсчётов ℓ,ℓ+ и ℓ,ℓ+ интерполируются на 22−1отсчётов 2 ℓ,ℓ+ = ( )2−1=0 и 2 ℓ,ℓ+ = ( )=0 . Дальнейшая обработказависит от чётности номера .1. Пусть текущая вершина чётная, = 20 . Тогда её мультииндекс можнопредставить в виде (, 0), где — мультииндекс вершины уровня + 1, соединённой с текущей вершиной и к которой приписан остаточный член Шураℓ .
Выполняются следующие операции.1. Расчёт ДПФ 2 = ( )2−1= ( )2−1на 2 точек от=0=0 , 2 первых 2 коэффициентов числителя и знаменателя остаточного члена ℓ ().2. Расчёт параметров нового остаточного члена Шура ℓ+ , приписанногок соседней вершине уровня и номером + 1, имеющей мультииндекс(, 1). Для этого по следствию 6 вычисляются величины(︃ )︃ (︃)︃ (︃ )︃**̂︀ −=,0 ≤ ≤ 2 − 1.̂︀− Затем вычисляются ОДПФ2−1−1̂︀ )2−1 ,(̂︀ )=0= 2((−1) =0141−1 ̂︀ 2−1(̂︀ )2−1=0 = 2 ( )=0на 2 отсчётов. По следствию 6 первые коэффициентов числителя и знаменателя функции ℓ+ () образуют векторы ( −1̂︀ )−1 и=0(−1−1̂︀ )=0,соответственно.
Эти данные приписываются вершине (, 1)уровня и от неё вдоль нулевых ветвей по всем вершинам уровней,меньших .3. В вершине нулевого уровня с мультииндексом = (, 1, 0, . . . , 0) определяются величины: = 1, = ̂︀0 и ( )−1 = 1/(1−|̂︀0 |2 ). Эта вершинастановится текущей на следующем шаге алгоритма.2. Пусть текущая вершина нечётная, = 20 + 1. Тогда её мультииндексможно представить в виде (, 1), где — мультииндекс вершины уровня +1,соединённой с текущей вершиной.
При этом вершина с мультииндексом (, 0)уже обработана ранее, и в ней вычислены результаты ДПФ на 2 отсчётов(,0) 2−1)=0(,0)((,0) 2−1)=0от (,0) и (от (,0) , а также остаточная дисперсия.По лемме 17 значения ДПФ от коэффициентов многочленов Шура 2−1( )2−1=0 = 2 , ( )=0 = 2 в вершине с мультииндексом опреде-ляются по формулам = (,0) + (−1) ((,0) )* , = (,0) + (−1) ((,0) )* ,0 ≤ ≤ 2 − 1.Кроме того, обратная остаточная дисперсия вычисляется по правилу( )−1 = ( (,0) )−1 −1 .На следующем шаге алгоритма текущей вершиной становится вершина смультииндексом .На этом заканчивается тело цикла в алгоритме расчёта данных в нагруженном бинарном дереве.
Начинается обработка новой текущей вершины. Алгоритм заканчивает работу, когда текущая вершина находится на уровне .Теорема 15 Пусть тёплицева матрица положительно определена. Тогдасформулированный алгоритм обхода дерева заканчивает работу и в вершинеуровня находятся многочены Шура для функции 0 ().142Доказательство. Из положительной определённости следует, что | | <1 для всех 0 ≤ < = 2 , где — коэффициенты отражения. По лемме 14коэффициенты отражения совпадают с параметрами Шура для функции 0 .
Ввершинах нулевого уровня величины были определены как 1 − | |2 , где — номер вершины уровня 0. Следовательно, при всех и обращение ( )−1выполняется корректно.Способ расчёта многочленов Шура основан на лемме 17 и следствии 6.4.4Сложность расчёта многочленов ШураРассмотрим общую сложность быстрого алгоритма Шура на абстрактноймашине. Для этого нам потребуются сведения о специальных реализацияхБПФ, приведенные в приложении D.4.4.1Общая оценка количества операцийАммар и Грегг[78] приводят оценку сложности алгоритма Шурадля многочленов с вещественными коэффициентами при программной реализации и использовании БПФ с разделенным основанием, которая составляет (8/3) log22 + ( log2 ) вещественных операций умножения и(16/3) log22 + ( log2 ) операций сложения.Сложность алгоритма обхода бинарного дерева полностью определяетсяего размером: высотой или размерностью = 2 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
