Диссертация (1150844), страница 8
Текст из файла (страница 8)
Эквивалентные формы итераций для метода MGNВведём следующие обозначения. Пусть F, = (JS, ) :,{1,...,} обозначает пер()()вые столбцов матрицы Якоби JS (( ) , ( ) ) = JS, , F, = (JS, ) :,{+1,...,2}обозначает последние столбцов матрицы Якоби JS, .Докажем теорему 3.1.1 об эквивалентном виде итераций метода MGN.Доказательство теоремы 3.1.1. Необходимо доказать эквивалентность (3.5) и(3.6). Следующее равенство верно для любой F полного ранга и положительноопределённой V: (F)†V ΠF,W = (FT VF)−1 FT VF(FT WF)−1 FT W = (F)†W . Согласно теореме 2.2.3, colspace J, = ((() )2 ), и, таким образом, ΠJ, ,W =Π((() )2 ),W .⎛⎞Q ( )̂︀ = Q̂︀ = ⎝⎠Выберем матрицу V нужным образом.
Определим QTF,̂︀ T Q.̂︀ Докажем,— матрицу полного ранга (см лемму 2.2.1), и положим V = Qчто(︀)︀(J, )†V Π((() )2 ),W (X − Π(() ),W (X)) :,{+1,...,2} == M† QT (() )Π((() )2 ),W (X − Π(() ),W (X)),T()52где M = QT (() )F, согласно лемме 2.2.2.Мы доказываем это равенство, используя технику блочных матриц. Заметим, что вычисление нижней половины строк матрицы (JS, )†V требует вычис−1ление только нижней половины строк матрицы (JT.S, VJS, ) ⎞⎛0M̂︀ S, = ⎝ −,⎠,Таким образом, мы имеем QJTTF, F, F, F,⎛JT, VJS, =(︀−1(JTS, VJS, )(FT F )T FT, F,⎝ , ,T T(FT, F, ) F, F,)︀:,{+1,...,2}T T(FT, F, ) F, F,MT M+T T(FT, F, ) F, F,⎞⎠,=)︁(︁)︀(︀ T−1TT −1T−1 ,= −(MT(M M ) M ) (F, F, ) (F, F, )⎛V = Q(() )QT (() ) + F, FT, ,⎝JT, V =⎞T T(FT, F, ) F,T()T T(FT, F, ) F,M Q ( ) +(︀ T)︀(︀ T)︀−1 T(JS, VJ, )−1 :,{+1,...,2} JTV=(JVJ)JV=S,S,S,S,:,{+1,...,2}⎠,† T−1T()()= (MT M ) M Q ( ) = M Q ( ).Для реализации метода MGN используется именно вид итерации (3.6).
Намтакже понадобится другой вид итерации (3.5) для сравнения с методом VPGN.ОпределимH = (I − Π(() ),W )F, ,(3.9)и рассмотрим следующую итерацию:(+1)( )()= ( ) + (H )†W (X − Π(() ),W (X)).Предложение 3.1.1. Итерации (3.5) и (3.10) эквивалентны.(3.10)53Доказательство. Покажем, что(︀)︀†((JS, )†W ) :,{+1,...,2} = (I − Π(() ),W )F, W .(3.11)Чтобы это сделать, нужно представить (JS, )†W в следующем виде:⎛(JS, )†W =FT WF,⎝ ,⎞−1 ⎛FT, WF, ⎠TFT, WF, F, WF,⎞FT W⎝ , ⎠FT, W.(3.12)Вычислим нижнюю половину (3.12):((JS, )†W ) :,{+1,...,2} =TT−1TTT= (FT, WF, − F, ΠF, ,W WF, ) (F, − F, ΠF, ,W )W =(︀)︀−1= ((I − ΠF, ,W )F, )T W((I − ΠF, ,W )F, )((I − ΠF, ,W )F, )T W,TTтак как ΠTF, ,W WΠF, ,W = ΠF, ,W W.
C учётом Π(() ),W = ΠF, ,W получаем правую часть (3.11).⎞QT (() )̃︀⎠. Эта матрица невырождена,⎝Также определим матрицу Q =TF, W̃︀ T = [Q(() ) : WF, ], где colspace WF, = (() ) из-за положитак как Q⎛тельной определённости W.Для сравнения итерации метода MGN с итерацией метода VPGN нам понадобится следующее свойство.Лемма 3.1.2.Для⎛⎞ H , заданной в (3.9), выполнено следующее равенство:−ST, : ⎠−1 ⎝̃︀H = Q , где = ( ).0,⎛⎞T−S̃︀ H = ⎝ , : ⎠, вычислив отдельно проДоказательство.
Покажем, что Q0,изведение верхних и нижних строк. Так как QT (() )Π(() ),W = 0 −, , для54верхних − строк имеем QT (() )(I − Π(() ),W )F, = QT (() )F, =−ST, : .TДля нижних строк получаем FT, W(I − Π(() ),W )F, = (F, W −FT, W)F, = 0, .3.1.6.
Сравнение вида итераций методов VPGN и MGN()Представим матрицу Якоби JS* (( ) ), заданную в (3.8), в виде суммы двух()̃︀ () ) + H(̂︀ () ) = H̃︀ + Ĥ︀ , гдечастей: JS* (( ) ) = H(( )( )()−1()−1()T̃︀(H(( ) ) :, = −W Q( )Γ ( )Q ( )Π(() ),W X,()−1−1()T()̂︀(H(( ) ) :, = −Π(() ),W W Q( )Γ ( )Q ( )X, = ( ) = — -й элемент множества .̃︀ .Лемма 3.1.3.
Выполняется следующее равенство: H = H⎞⎛T−S̃︀ H̃︀ = ⎝ , : ⎠, а затем используем реДоказательство. Докажем, что Q0,̃︀ ) :, = −QT ( )Π(() ),W X, слезультат леммы 3.1.2. Мы имеем (Q(() )T H̃︀ = −ST , а также FT WH̃︀ = 0, , что доказываетдовательно, Q(() )T H, :,утверждение.Применим лемму 3.1.3 к шагу (3.4).Предложение 3.1.2. Следующая итерация эквивалентна (3.4):(+1)( )=()( )+(︁()H(( ) ))︁†()()̂︀+ H(( ) )(X − S* (( ) )).(3.13)WЗамечание 3.1.1. Предложение 3.1.1 и следствие 3.1.2 показывают, чтоитерация метода VPGN в виде (3.13) отличается от итерации метода MGN̂︀ вместо H , при этомв виде (3.10) псевдообращением матрицы H + Hcolspace H ⊂ (() ).553.2.
Вычисление базисов пространств () и (2)3.2.1. Общая теорияДля реализации шага итерации (3.6) предложенного алгоритма оптимизации MGN, нам необходимы эффективные алгоритмы вычисления ортонормированных базисов () и (2 ), где () обозначает пространство рядов,управляемых ОЛРФ(). Заодно, мы можем использовать полученные алгоритмы для улучшения устойчивости шага (3.4) алгоритма VPGN. Как и ранее, подZ() мы имеем в виду матрицу, столбцы которой составляют некоторый базис().
Нас интересует построение ортонормированных базисов для использования их при численном вычислении проекции на (), чтобы получать болееточные значения проекций.Начнём с построения Z(). Несмотря на то, что рассматриваемые рядывещественнозначные, мы конструируем комплекснозначный базис, так как такая замена не влияет на проекцию Π(),W для любого вещественного вектора и вещественной матрицы W. Таким образом, мы хотим найти невырожденную матрицу Z() = Z ∈ C × , которая бы удовлетворяла равенствуQT ()Z = 0 − .Введём следующую матрицу-циркулянт C(), зависящую от ∈ R+1 :⎞⎛1 2 . .
. . . . +1 0 . . .0⎟⎜.. ⎟..⎜.⎜ 01 2 . . . . . . +1. ⎟⎟⎜⎜ .................... 0 ⎟⎟⎜ .⎟⎜⎟⎜....⎜ 0 .....012+1 ⎟⎟⎜,(3.14)C() = ⎜.. ⎟............⎟⎜......⎜+1. ⎟⎟⎜⎜ .... ⎟............⎜ ........ ⎟⎟⎜⎟⎜⎟⎜ 3 . . . +1 0...012 ⎠⎝2......+10...0156которую можно получить расширением матрицы QT (). Получим ∈ () тогда и только тогда, когда C() ∈ span( −+1 , . . . , ). Если C() невырождена, то мы можем найти базисные векторы путём решения систем линейныхуравнений C() = −+1 , = 1, . . .
, , с помощью дискретного преобразования Фурье [43], и затем применить ортонормализацию к V = [1 : . . . ].Обозначим ℱ и ℱ−1 прямое и обратное дискретное преобразование Фурьедлины . Для ℱ () = , , ∈ C , = (0 , . . . , −1 )T , = (0 , . . . , −1 )T∑︀ −1i2выполняется = √1 =0 exp(− ). При этом определим преобразованиеФурье от матрицы как ℱ (X) = [ℱ (1 ) : . . .
: ℱ ( )], где X = [1 : . . . : ],и ℱ−1 (Y) аналогично.Следующая лемма — прямое применение теоремы о решении системы линейных уравнений с матрицей-циркулянтом [43]. Обозначим — характеристический многочлен ОЛРФ(), см. определение 1.1.4.Лемма 3.2.1.
Обозначим V = ℱ−1 (A−1 R ), где R = ℱ ([ −+1 : . . . : ]),TA = diag(( (0 ), . . . , ( −1 ))T ), = exp( i2 ). Тогда Q ()V = 0 −, ,при этом диагональ матрицы A содержит собственные числа матрицыC().Замечание 3.2.1.1. В качестве матрицы, содержащей базис (), можно взять матрицу Z, столбцы которой построены с помощью ортонормализации столбцов матрицы V , заданной в лемме 3.2.1. Будем обозначать это преобразование как Z = othonorm(V ). Так как QT ()V =0 −, , то и QT ()Z = 0 −, .2. Так как ℱ−1 — преобразование, сохраняющее ортонормированность, матрица Z = ℱ−1 (othonorm(A−1 R )) состоит из ортонормированных столбцов.Тем не менее, C() может оказаться вырожденной, например в случае линейных временных рядов с = +, управляемых ОЛРФ(), = (1, −2, 1)T .57Лемма 3.2.1 показывает, что собственные числа C() — значения многочлена () в узлах равномерной решётки на комплексной единичной окружностиT = { ∈ C : || = 1}: = {exp( i2 ), = 0, .
. . , − 1}, ⊂ T. Следовательно, невырожденность C() эквивалентна отсутствию корней полиномов ()на . Следующая лемма помогает избежать проблем с нулевыми собственнымичислами. Определим унитарную матрицу T () = diag((1, i , . . . , i( −1) ))T ,где — вещественное число.Лемма 3.2.2. Пусть — вещественное. Если ряд X управляется ОЛРФ(),̃︀ = T ()X управляется (),̃︀̃︀то ряд Xгде ()= (T+1 (−)). Более того,2̃︀ = T ()Y управляется (())̃︀если ряд Y управляется ОЛРФ(2 ), то ряд Y.̃︀ равны ̃︀( ) = (˜К тому же, собственные значения C() ), где ˜ = −i .Доказательство.
Лемма доказывается с помощью вычисления столбцов мат2 T̃︀ = 0T по определению 1.1.3 и̃︀ = 0T и ((())̃︀T ()+1 (X)̃︀риц ) +1 (Y) − −замечания о том, что 2 () = ( ())2 .Замечание 3.2.2. Возьмём ∈ R, −/ < ≤ / (так как и + 2/̃︀ — невырождеведут к одному и тому же результату) такую, что C()̃︀ используя лемму 3.2.1, такой,на, и вычислим ортонормированный базис Z,̃︀ = 0 −, . Тогда Z = (T (−))Z̃︀ — ортонормированная мат̃︀ Zчто QT ()̃︀ 2 такой, чторица такая, что QT ()Z = 0 −, . Подобным образом, для Z̃︀ 2 = 0 −, , Z2 = (T (−))Z̃︀ 2 , мы получаем QT (2 )Z2 = 0 −, .̃︀ 2 )ZQT (()̃︀Равенство ˜( ) = (˜ ) означает, что собственные числа C(())можно вычислить как значения многочлена () в точках ∈ (), где)︂)︂(︂ (︂2()()() = { , = 0, . .
. , − 1}, = exp i.−(3.15)() — повёрнутая равномерная решётка на T. Следовательно, можно добить̃︀ся невырожденности C(())выбором подходящего .58Цель выбора состоит в том, чтоб уменьшить число обусловленности мат̃︀рицы C(())как можно сильнее. Приближённо, это можно свести к задачемаксимизации наименьшего собственного числа |min ()| = min∈() | ()|,так как модуль максимального собственного числа не превосходит max∈T | ()|.В точной арифметике любое ненулевое наименьшее собственное число соответствует невырожденности. Однако на практике нам требуется как можно меньшее число обусловленности для устойчивости и точности вычисления.Объединяя леммы 3.2.1, 3.2.2 с замечаниями 3.2.1, 3.2.2, мы получаем следующий алгоритм вычисления Z.Алгоритм 3.2.1 (Вычисление базиса ()). Вход: число , вектор коэффициентов ∈ R+11:Найти 0 = arg max−/ ≤</ min∈() | ()| с помощью одномерногочисленного метода оптимизации.2:Вычислить вектор = (,0 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
