Диссертация (1150736), страница 21
Текст из файла (страница 21)
Многочлены в обратныхстепенях имеют дополнительный множитель , так как̃︀(,) () = − ( −1 ),̃︀(,) () = − ( −1 ).Лемма 15 Для любых < < (,) = (,) (,) .Доказательство. Пусть < < и функции , , являются остаточными членами функции соответствующих порядков. Многочлены Шура131полностью определяются соответствующими параметрами Шура и связываютостаточные члены следующим образом: =(,) + ̃︀(,) ,̃︀(,) + (,) =(,) + ̃︀(,) ,(,) + ̃︀(,) =(,) + ̃︀(,) .(,) + ̃︀(,) Исключая из первого уравнения при помощи подстановки второго уравнения, получаем представление в виде дробно–линейной функции от ,как и в третьем уравнении.
Многочлены Шура не зависят от , так как определяются параметрами с ≤ . Следовательно, пропорциональны соответствующие коэффициенты дробно–линейного представления. По определению, (0) = 1 при всех . Следовательно, соответствующие коэффициенты равны,что равносильно уравнению в заключении леммы.4.3.2Преобразование коэффициентов функций ШураПусть функция Шура рациональная:() =0 ()0,0 + 0,1 + 0,2 2 + . .
.=.0 () 0,0 + 0,1 + 0,2 2 + . . .Из преобразования Мёбиуса следует, что все остаточные члены в алгоритмеШура также рациональные: () = (),0 + ,1 + ,2 2 + . . .=, () ,0 + ,1 + ,2 2 + . . . = 0, 1, 2, . . .Коэффициенты числителя и знаменателя заданы с точностью до общего множителя.
Выберем этот множитель из условия ,0 = 1 при всех .Лемма 16 Пусть > ≥ 0. Тогда(︃)︃(︃)︃ (︃)︃ (), (), ̃︀, () ()=. (), () ̃︀, () ()132Доказательство. Из определения многочленов Шура следует, что (), () + ̃︀, () () , () + ̃︀, () () ()= () =.= (), () + ̃︀, () () , () + ̃︀, () ()()После умножения числителя и знаменателя на () получаем утверждениелеммы.
Нормировка многочлена () сохраняется, так как ̃︀, (0) = 0, ипоэтому (0) = (0) = 1.4.3.3Структура бинарного дерева при расчёте параметровШураПусть = 2 . Выполним операцию дихотомии целочисленного промежутка [0, − 1]. Для этого сначала разделим его на две части [0, 2−1 − 1]и [2−1 , 2 − 1] и отметим их индексами = 0 и = 1, соответственно. Затем каждую из этих частей снова разделим пополам и отметим индексом −1 , например, вторую часть на отрезки [2−1 , 2−1 + 2−2 − 1] и[2−1 + 2−2 − 1, 2 − 1].
Продолжая таким образом, получим для каждого уровня бинарного дерева = , − 1, . . . , 0 разбиение целочисленного промежутка[0, − 1] на 2− частей, причем каждая из этих частей отмечена мультииндексом = (− , . . . , 1 ) из нулей или единиц ( ∈ {0, 1}).Пусть 0 ≤ < . Длина каждого промежутка с мультииндексом =(− , −−1 , . . . , 1 ) равна 2 . Обозначим его границы [ , ].
Тогда =−∑︁2−1 , = + 2 − 1.=1Каждому промежутку [ , ] поставим в соответствие матрицу = ( , +1) .Тогда по лемме 15 эти матрицы удовлетворяют рекуррентному уравнению = (,0) (,1) .Мультииндексы образуют естественную структуру бинарного дерева. Корень соответствует пустому мультииндексу при = и, соответственно, паре133многочленов Шура ( , ), которые и требуется рассчитать. Вершины бинарного дерева при = 0 соответствуют преобразованию Шура, которое полностью определяется соответствующим параметром Шура .Для вычисления пары многочленов Шура, стоящей в корне бинарного дерева, достаточно начать с вершин и, применяя рекуррентное уравнение, последовательно вычислять пару многочленов Шура от –го уровня к + 1–мууровню при = 0, 1, . . .
, − 1. Общее количество преобразований равно=−1∑︁2−−1 = 2 − 1 = − 1.=0Сложность данного алгоритма складывается из сложности определения всехпараметров Шура и сложности умножения многочленов при рекуррентномрасчёте элементов матриц .4.3.4Расчёт многочленов Шура по параметрам ШураПусть заданы параметры Шура ( )=1 . Требуется вычислить многочленыШура ( , ). Будем считать, что = 2 . При непосредственном умножениимногочленов на каждом шаге требуется выполнить умножения в количестве,пропорциональном номеру этого шага. Поэтому общее количество умножений пропорционально 2 .
При помощи преобразований Фурье эту сложностьможно значительно уменьшить.Подставим параметры Шура в вершины бинарного дерева и будем выполнять умножения, двигаясь к вершине. На –ом уровне будет выполнено 2−−1однотипных операций.Рассмотрим вершину на уровне > 0. Ей соответствует мультииндекс длины < . Пусть вычислены многочлены, входящие в матрицы (,0)и (,1) , приписанные к вершинам уровня − 1, соединённых с выбранной вершиной. Обозначим соответствующие многочлены Шура ( (,0) , (,0) ) и( (,1) , (,1) ).
Степени этих многочленов не выше 2 − 1. Требуется вычислитьмногочлены ( , ) степеней не выше 2+1 − 1 по формуле = (,0) (,1) + ̃︀(,0) (,1) , = (,0) (,1) + ̃︀(,0) (,1) .134Для реализации умножения применяется БПФ. Исходные многочлены имеют = 2 коэффициентов и степень −1, а результат умножения пары такихмногочленов имеет степень 2 − 2 и, соответственно, 2 − 1 коэффициентов.Поэтому значение результата требуется вычислить в 2 точках на единичнойокружности.Для произвольного многочлена степени не выше ℓ − 1 набор его значений в ℓ равноотстоящих точках единичной окружности обозначим ℓ . Эторезультат БПФ от набора коэффициентов многочлена на ℓ точек. Если степень меньше, чем ℓ − 1, то набор коэффициентов ¯ дополняется нулями доразмерности ℓ, после чего применяется БПФ.Будем считать, что в памяти хранятся не коэффициенты многочленов (,0) , (,1) , (,0) , (,1) , а значения преобразований Фурье (,0) , (,1) , (,0) , (,1) , каждое длины .
Поскольку результат умножения многочленов имеет длину 2, то сначала эти преобразования Фурье надо интерполировать на2 отсчетов.Лемма 17 Пусть — мультииндекс, соответствующий некоторой вершинеуровня > 0. С ней соединены вершины уровня − 1, имеющие мультииндексы (, 0) и (, 1). Многочлены Шура в этих вершинах обозначим ( , ),( (,0) , (,0) ) и ( (,1) , (,1) ), соответственно.Пусть = 2 .
Результаты ДПФ на точек обозначим−1( )=0= ,( )−1=0 = ,−1((,0) )=0= (,0) ,(,0)((,0) )−1,=0 = (,1)((,1) )−1,=0 = (,1)((,1) )−1.=0 = Тогда при 0 ≤ ≤ − 1 = (,0) (,1) + (−1) ((,0) )* (,1) , = (,0) (,1) + (−1) ((,0) )* (,1) .Доказательство. По лемме 15(︃)︃ (︃)︃ (︃)︃(,0)(,0)(,1)(,1)̃︀̃︀̃︀ () ()() ()() ()=. () ̃︀ () (,0) () ̃︀(,0) () (,1) () ̃︀(,1) ()Значение ДПФ на отсчётов от набора коэффициентов произвольного много2−. Выберемчлена () степени меньше есть вектор (( )−1=0 , где = 135первый столбец в последнем уравнении и подставим = : = (,0) (,1) + ̃︀(,0) ( )(,1) , = (,0) (,1) + ̃︀(,0) ( )(,1) .Вершины с мультииндексами (, 0) и (, 1) находятся на уровне −1, поэтому̃︀(,0) () = −1 (,0) ( −1 ) и ̃︀(,0) () = −1 (,0) ( −1 ). Подстановка−1 = − = (−1) ,−1 = *приводит к заключению леммы.4.3.5Расчёт остаточных членовПараметры Шура заранее неизвестны. При последовательном расчётеэтих параметров по остаточным членам 1 , 2 , .
. . требуется вычислять всекоэффициенты числителей и знаменателей этих функций вплоть до степени. Количество коэффициентов на каждом шаге пропорционально , а количество шагов равно . Поэтому сложность пропорциональна 2 . При использовании бинарного дерева преобразований Шура длина каждого остаточногочлена уменьшается, что значительно снижает объем вычислений.Пусть — мультииндекс длины − , определяющий вершину в бинарномдереве на уровне . С этой вершиной связан целочисленный отрезок [1 , 2 ]длины 2 на отрезке [0, −1]. Будем вычислять первые 2 −1 коэффициентовфункции Шура 1 , являющейся остаточным членом порядка 1 исходнойфункции .Дуги бинарного дерева, выходящие из одной вершины, помечены цифрами 0 или 1. Их будем называть, соответственно, левой и правой ветвями. Придвижении только по левым ветвям по направлению к концевым вершинам начальный индекс интервала 1 не меняется, поэтому номер остаточного членатакже не меняется, а длина набора коэффициентов числителя и знаменателяуменьшается.
Следовательно, при таком движении не требуется заново вычислять эти коэффициенты. При сдвиге по правой ветви необходимо выполнитьпересчет параметров остаточного члена.В начальный момент известным является набор коэффициентов в корневойвершине и, следовательно, во всех вершинах, достижимых из нее по левым136ветвям.
Обход бинарного дерева выполним в лексикографическом порядке.При этом в каждый момент времени во всех вершинах, расположенных выше анализируемой, будут храниться вычисленные коэффициенты остаточныхчленов. Одновременно в каждой вершине уже пройденного поддерева, т.е. вкаждой вершине, лежащей левее пути из текущей вершины в корневую вершину, будет храниться вычисленная пара многочленов Шура.При движении по дуге, помеченной нулём остаточные члены Шура неменяются, а многочлены Шура меняются, так как меняется порядок многочленов. При движении по дуге, помеченной единицей, меняются также остаточные члены Шура. Способ расчёта числителей и знаменателей остаточныхчленов Шура основан на следующем утверждении.Лемма 18 Пусть — мультииндекс некоторой вершины уровня + 1 > 0.
Сней соединены вершины уровня с мультииндексами (, 0) и (, 1). В вершине(, 0) многочлены Шура обозначим ( (,0) , (,0) ), а остаточную дисперсию — (,0) . В вершинах (, 0) и (, 1) остаточные члены Шура обозначим () = ()/ () и (,1) () = (,1) ()/(,1) (), соответственно. Тогда)︃ (︃ )︃(︃)︃(︃̃︀(,0) , −̃︀(,0)(,1)1,= (,0) − (,0) , (,0)(,1)где = 2 .Доказательство. Пусть — натуральное число, двоичное представлениекоторого есть мультииндекс . Тогда вершинам с мультииндексами и (, 0)соответствуют остаточный член Шура = 2 , а вершине с мультииндексом (, 1) — остаточный член 2 + . Обозначим = 2 , = 2 + .Тогда из определения многочленов (, (), , ()) следует, что (,0) = ,и (,0) = , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
