Диссертация (Структурные аппроксимации временных рядов), страница 9
Описание файла
Файл "Диссертация" внутри архива находится в папке "Структурные аппроксимации временных рядов". PDF-файл из архива "Структурные аппроксимации временных рядов", который расположен в категории "". Всё это находится в предмете "физико-математические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве СПбГУ. Не смотря на прямую связь этого архива с СПбГУ, его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата физико-математических наук.
Просмотр PDF-файла онлайн
Текст 9 страницы из PDF
. . , , −1 )T как , = (exp(i( 2 − 0 )), = 0, . . . , − 1.3:Вычислить матрицы R = ℱ ([ −+1 : . . . : ]), L = A−1 R , гдеA = diag .4:Найти матрицу U ∈ C × , состоящую из ортонормированных столбцовматрицы L (например, U может состоять из левых сингулярныхвекторов L ).5:̃︀ = ℱ −1 (U ).Вычислить Z6:̃︀ столбцы которой образуют ортонорreturn Матрица Z = (T (−0 ))Z,мированный базис ().̃︀Заметим, что вектор состоит из собственных чисел матрицы C().Обсудим вычислительные свойства построенного алгоритма. Следующаятеорема показывает порядок |min ()| (и, следовательно, порядок числа обусловленности матрицы, которую надо обратить) в зависимости от длины ряда59 и зависящего от неё .Теорема 3.2.1. Пусть обозначает максимальную кратность корня многочлена (), лежащего на комплексной единичной окружности T, min () —̃︀наименьшие по модулю собственные числа матриц C(()).1.
Для любой вещественной последовательности ( ) выполняется|min (( ))| = ( − ) при → +∞.2. Существуют такая вещественная последовательность ( ), что|min (( ))| = Θ( − ), то есть порядок − достигается.Доказательство. Обозначим ∠(, ) угол между двумя точками на T, 0 ≤∠(, ) ≤ . Докажем первый пункт. Рассмотрим корень 1 ∈ T кратности , тогда для любого : min∈() ∠(, 1 ) ≤по принципу Дирихле. Зафиксируемлюбое 0 ≤ 0 < 2, и выберем 0 = arg min∈(0 ) ∠(, 1 ). Вычисление () вточке 0 завершает доказательство первого пункта, так как |1 −0 | = (1/ ).Чтобы доказать второй пункт, построим кусочную оценку () для ∈T. Рассмотрим разложение () = () (), где корни многочлена ()лежат на T, в то же время как корни () не лежат на T.
По построению,inf ∈T | ()| > 0.Обозначим 1 , . . . , корни () с кратностями 1 , . . . , . Мы разбиваем окружность T на полуоткрытых непересекающихся дуг 1 , . . . , , T =⋃︀/ для любого ̸= (1≤≤ таких, что ∈ для любого , и ⃒ ∈⃒⃒ () ⃒обозначает замыкание ), из чего следует inf ∈ ⃒ (− ) ⃒ > 0.Чтобы закончить доказательство, мы покажем, что существует такое 0 ≤ = ( ) < 2 чтоmin∈(( )), 1≤≤∠(, ) = Θ(1/ ). Введём следующее множество, зависящее от 0 ≤ < / , ∈ T:ℬ, = {0 ≤ < 2 : min ∠(, ) ≤ }.∈()60Это множество ℬ, имеет следующий явный вид:(︂(︂ (︂)︂)︂ )︂ ⃒}︁⋃︁ {︁2⃒Arg exp iℬ, =+/ ⃒.−≤≤0≤≤ −1()Давайте объясним это выражение.
Рассмотрим ( )такие , что ∠(( )из (3.15), и выберем все, ) ≤ . Это означает, что полярный угол их отношения( )/ лежит в промежутке [−, ], то есть / ∈ {exp (i) |−≤≤ }. Сдела(︀ (︀)︀)︀ем эквивалентные преобразования: exp i 2−∈ { exp (i) |−≤≤ },)︂)︂(︂ (︂2∈ {exp (i) /|−≤≤ },exp i −где = −, и в итоге(︂)︂2 ∈ {Arg(exp i(+ ) /)|−≤≤ }.(3.16)Чтобы было выполнено min∈() ∠(, ) ≤ , нужно, чтобы равнялось одному из 0 , .
. . , −1 . Объединение всех множеств вида (3.16) по = 0, . . . , − 1даёт ℬ, .Мера Лебега множества ℬ, на окружности T равна mes ℬ, = 2 для⋃︀ < / . Возьмём = 2 и рассмотрим ℬ = 1≤≤ ℬ, . Так как mes ℬ ≤ ,мы получаем, что mes ℬ̂︀ ≥ , где ℬ̂︀ = [0; 2) ∖ ℬ, что означает, что ℬ̂︀ не пустоемножество. Таким образом, мы доказали, что для любой ∈ ℬ̂︀min∈(), 1≤≤∠(, ) >.2 Зафиксируем произвольное 0 ∈ ℬ̂︀ и рассмотрим любое ∈ (0 ).
Пусть — такое, что ∈ . Для любого , |− | = Θ(1/ ). Следовательно | ()| =⃒⃒⃒ () ⃒| ()| ⃒ (− ) ⃒ |( − ) | ≥ Θ( − ), где > 0 — некоторая константа.Теперь рассмотрим алгоритм вычисления Z(2 ). Заметим, что 2 () =( ())2 , благодаря чему можно получить выигрыш по точности при вычислении (2 ) по сравнению с прямым вычислением 2 и применением алгоритма613.2.1. Более того, для увеличения точности можно использовать следующее соображение.Замечание 3.2.3.
Рассмотрим лемму 3.2.1 для ОЛРФ(2 ): введём R2 =−1ℱ ([ −2+1 : . . . : ]) ∈ R ×2 , L2 = A−2 R2 , V2 = ℱ L2 . Применим принцип замечания 3.2.1, но уже к ОЛРФ(2 ). Из () ⊂ (2 ) следует, что colspace V ⊂ colspace V2 , а из этого следует, что colspace L ⊂colspace L2 . Поэтому ортонормализацию столбцов плохо обусловленной матрицы L2 можно заменить на поиск ортонормированного базиса пространства столбцов матрицы (I − ΠU ,I )L2 ранга , что за счёт знания U ,полученной ортонормализацией L , позволяет сделать процесс ортонормализации L2 менее обусловленным.Используя приведённые выше соображения, получим алгоритм 3.2.2.Алгоритм 3.2.2 (Вычисление базиса (2 )). Вход: число , вектор коэффициентов ∈ R+1 .1:Вычислить 0 , A , U таким же способом, как в алгоритме 3.2.1 .2:Вычислить R2 = ℱ ([ −2+1 : .
. . : ]), L2 = A−2 R2 .3:̂︀ 2 = (I − ΠU ,I )L2 .Вычислить L 4:̂︀ ∈ C × , столбцы которой составляют ортонормиНайти матрицу Û︀ 2 (например, Û︀ может состоять из первых рованный базис colspace L̂︀ 2 ).левых сингулярных векторов матрицы L5:̃︀ 2 = ℱ −1 [U : Û︀ ].Вычислить Z6:̃︀ 2 , столбцы которой образуют ортонорreturn Матрица Z = (T (−0 ))Zмированный базис (2 ).Замечание 3.2.4.
Несмотря на то, что в алгоритме 3.2.2 используетсяматрица A2 , благодаря её диагональному виду сохраняется порядок относительной ошибки элементов решения СЛАУ. Относительная ошибка вычис1ления величины 1/min может быть приближённо оценена как: |min || min−621min + |≈ | min|, где — ошибочный член, || значительно меньше |min |, имеетпорядок ( ), а определено в теореме 3.2.1. Более того, относительнаяошибка величины 1/2min , рассчитанная как |2min || 21 −min1(min +)2 |,имеет приближенное значение того же порядка.3.2.2.
Использование компенсированной схемы Горнера привычислении базиса в алгоритмах 3.2.1 и 3.2.2Вычисление базисов () и (2 ) — плохо обусловленная задача при наличии корней у полинома () на окружности T, что видно из теоремы 3.2.1.Неустойчивость может проявляться и в пограничной ситуации, когда корнилежат возле окружности T, так как min () непрерывно зависит от коэффициентов ОЛРФ(). Поэтому применение алгоритмов 3.2.1 и 3.2.2 напрямую может привести к неустойчивости на практике. Мы предлагаем использовать такназываемую «error-free» арифметику и компенсированную схему Горнера [44](алгоритм CompHorner).Объясним, как компенсированная схема Горнера может использоватьсяпри вычислении базисов Z() и Z(2 ) с повышенной точностью. Схема Горнера может напрямую применяться в алгоритмах 3.2.1 и 3.2.2 для вычисленияполиномов .Более того, с помощью схемы можно повысить точность вычисления Uна шаге 4 алгоритма 3.2.1, что важно, если L плохо обусловлена. Заметим, что̂︀ на шаге 4 алгориттакой же подход может быть применён при вычислении Uма 3.2.2.
Рассмотрим матрицу R , вычисляемую на шаге 3 алгоритма 3.2.1. Такi2(−1)как (R ), : = (exp( i2), . . . , exp( i2 ), exp( )), можно свести умножениеR на вектор к вычислению полинома в точке exp( i2 ). Следовательно, мыможем точнее посчитать умножение R на вектор с помощью схемы Горнера.Чтобы использовать это свойство, рассмотрим новый способ вычисления63U . Пусть O — такая, что L O состоит из ортонормированных столбцов. Матрицу O можно найти с помощью SVD или QR разложения.
Тогда выполненоU = A−1 (R O ). Такое представление U позволяет применить компенсированную схему Горнера к вычислению R O .Алгоритм 3.2.3 (Вычисление базиса () с использованием компенсированной схемы Горнера). Вход: число , вектор коэффициентов ∈ R+1 .1:Провести шаги 1 и 2 так же, как в алгоритме 3.2.3, но используя алгоритм CompHorner при вычислении полиномов.2:Провести пункт 3 так же, как в алгоритме 3.2.3.3:Вместо пункта 4: найти матрицу O такую, что L O — ортонормированная, после чего вычислить B = R O , используя алгоритм CompHorner,и U = A−1 (B ), используя обычное матричное умножение.4:Проделать пункты 5, 6 так же, как в алгоритме 3.2.1.Алгоритм 3.2.4 (Вычисление базиса (2 ) с использованием компенсированной схемы Горнера). Вход: число , вектор коэффициентов ∈ R+1 .1:Вычислить 0 , A , U таким же способом, как в алгоритме 3.2.3.2:Провести пункты 2 и 3 так же, как в алгоритме 3.2.2.3:̂︀ иным способом: найти матрицу Ô︀ такую, что L̂︀ 2 Ô︀ ∈Вычислить Û︀ = R2 Ô︀ , используяR × — ортонормированная, после чего вычислить B̂︀ = (I −ΠU ,I )A−2 (B̂︀ ), используя матричноеалгоритм CompHorner, и U умножение.4:Проделать пункты 5, 6 так же, как в алгоритме 3.2.2.3.2.3.
Быстрое вычисление оптимального поворотаВ пункте 1 алгоритма 3.2.1 требуется найти численное решение задачи0 = arg maxmin | ()|.−/ ≤</ ∈()(3.17)64Для решения этой задачи можно использовать любой метод поиска максимума на отрезке, например, метод Brent [45] или метод золотого сечения сразбиением на промежутки [46].Проблема состоит в том, что вычисление значения min∈() | ()| требует ( ) времени, при том, что число точек в (), лежащих ближе к корням (), чем их соседние точки, не так и много — порядка числа корней полинома (). Прямая оптимизация (3.17) требует много вычислений, поэтому применим эвристику, основывающуюся на том, что можно не перебирать все точкимножества ().