Диссертация (1150844), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

. . , , −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) требует много вычислений, поэтому приме­ним эвристику, основывающуюся на том, что можно не перебирать все точкимножества ().

Характеристики

Список файлов диссертации