Буслов, Яковлев - Введение в численный анализ (947494), страница 14
Текст из файла (страница 14)
Пусть х и у произвольные начальные векторы. Определим итерации уы = Ау ' ' = А™у = ~ Л Р,у, х = Ах ' = ~ Л Р,х . Аналогично методу итераций убеждаемся, что 71 (у,х ) (у х — ') 6.2.3 Обратные итерации Поиск минимального по модулю собственного значения Пусть у некоторый стартовый вектор. Определим обратные итерации как убо = Ау1в+Е или (ушло = А 'убй), то есть зто прямая задача для нахождения максимального собственного значения д „„матрицы В = А ' обратной к исходной матрице.
Очевидно, что минимальное по модулю собственное значение матрицы А равно максимальному по модулю собственному числу обратной матрицы. В = А ' 1 ,(д= — ) Метод обратных итераций со сдвигом Пусть А невырожденнея зрмитова, матрица и Л вЂ” некоторое пробное число. Рассмотрим матрицу (А — Л 1), ее собственными значениями являются числа (Л, — Л.), где Л, — собственные значения исходной матрицы А . У обратной матрицы (А — Л.Х) ' собственные значения — это величины ' . Процедура метода обратных итераций со сдвигом у'"' = (А — ЛУ)у'+о приводит к нахождению шах ~ „х ~ . Иными словами мы находим то собственное значение Л„, которое является 1 ближайшим к пробному чиспу Л .
Варьируя пробное Л н вновь применяя метод обратных нтершщй со сдвигом можно найти все собственные значения матрицы А 6.3 Неэрмитовы матрицы 6.3.1 Дополнительные сведения В случае если алгебраическая и геометрическая кратности собственных чисел оператора А совпадают. то унитарным преобразованием (то есть преобразованием сохраняющим скалярное произведение: (Ух,ну) = (х,у) ) (в Рь~ ортогональным преобразованием) оператор приводится к диагональному виду н на диагонали стоят собственные числа А с учетом кратности. Однако нередка ситуации> когда юпебраическая кратность собственного значения превышает геометрическую (обратное, кстати, невозможно). В С при определенном выборе базиса (называемым жордановым или каноническим базисом оператора А ) матрица оператора становится блочио-диагональной.
В каждом из блоков (жордановых клеток) матрица оператора является верхнетреугольной и имеет вид Л 1 О ... О О О Л 1 ... О О О О Л ... О О О О О ... Л 1 О О О ... О Л Размеры жордановых клеток, их количество, также как и числа Л (корни характеристического уравнения) являются инвариантами оператора А (то есть не зависят от выбора жорданова базиса). В В.'ч жорданов базис приводит к клеткам вида (1) если Л вещественный корень характеристического уравнения матрнць| оператора А в каком либо базисе.
Поскольку коэффипненты характеристического полинома матрипы оператора в В.'ч вещественны, то вместе с каждым комплексным корнем Л = д+)и он обдадает и комплексно сопряженным Л = д — ги . ?Корданова клетка в этом случае имеет вид д и 1 0 0 0 ... 0 0 — и д 0 1 0 0 ... 0 0 О 0 и и 1 О ... ΠΠΠΠ— д О 1 ... О О О О О О д и ... О О 0 0 0 Π— и д ...
0 0 0 0 0 0 0 0 ... 0 1 0 0 0 0 0 0 ... д и 0 0 0 0 0 0 ... — и д 6.3.2 Метод итераций для максимального ио модулю собственного числа крат- ности 2 в случае жордановой аномалии Отановимся подробно на случае, когда максимальному по модулю собственному значению Л оператора А соответствует жорданова клетка размера 2 х 2 . В каноническом базисе и', и",..., ин матрица оператора А имеет вид Л 1 ) 0 ... 0 0 Л ) 0 ...
0 0 О в 0 О Здесь  — матрица, отвечающая оставшимся собственным значениям, конкретный вид которой нас не интересует. Обозначим дуальный базис через ч', ч~,..., ч~ . Тогда Аи' = Ли' А" ч' = Лч' Аи" = Ли~ +и1 А"те = Лч~ +ч1 Вектор и' является собственным дляоператора А соответствующим собственному значению Л. Вектор й называется присоединенным. Для сопряженного оператора А* собственным и присоединенным векторами, соответствующими собственному значению Л (в Рьл — просто Л ) являются векторы дуэльного базиса ч' и чз соответственно. Заметим, что и = ч, и и" = ч, то есть собственный вектор для оператора является присоединенным для сопряженного и 2 э наоборот.
Непригодность обычного метода итераций Будем считать, что собственнь|е значения пронуметрованы в порядке убывания мооуля и что Лс = Л . Пусть х произвольный вектор. Разложим его по векторам жорданова базиса н дуального к нему х = 2,(х,ч')и', х = 2,(и',х)ч' Подействуем иа х оператором А и сопряженным: Ах = ~(х,ч')Ап* «А" х = ~(п'«х)А ч' Ах=(Л<х«ч' >-е<к«ч >)и'+Л<х ч >п +~ <к«ч*>Апз '=з А"х = (Л < и', х > -~- < пз, х >)ч'+ Л < пз, х > ч" -е ~ < п*, х > А" ч' .
ыз Аналогично, поскольку Л" пЛ~ ' ] О,. 0 0 Л ] 0 ... 0 0 в" 0 то А х (Л <хч«>+пЛ вЂ” «<хчз>)п«+Л <хч >п (2) Квадратичная форма и-ой степени оператора А с использованием (2) может быть записана как (А х,х) = (А х,~ (и',х)ч') = 1 = Л ( (а + Ь вЂ” ) + О (]Л /Л] ) ), где а =< х,ч' >< и',х > + < х,ч >< пз,х > (= 2 < х,ч' >< п',х > — в Рьч), Ь =< х,чз >< и',х > и Л' следующее по модулю за Л собственное значение. В нашей ситуации Л вещественно.
По аналогии с методом скалярных произведений, применяемым для эрмитовых матриц, рассмотрим отношение Релея .« Итак, р„= Л(1 + О(1/и)), то есть сходимость прв и -э оо настольно неудовлетворительная, что теряет практический смысл. Таким образом обычными итерационными методами собственное число в случае жордановой аномалии удовлетворительно сосчитать не представляется возможным. Необходим какой-то другой подход. Модифицированный метод итераций Составим квадратное уравнение, для которого Л является корнем кратности 2 (1 — Л) ' = зз + рз Е о = О р= — 2Л, о=Л Коэффициенты р и д заранее неизвестны, поскольку неизвестно само Л .
Попытаел«ся их определить. Обозначим х = А" х и рассмотрим выражение 74 х ~' +рх + дх" ' =< х,ч' > (Л!~' +рЛ", + дЛ", ') и'+ =о + < хт' > ((и+цЛ",+рпЛ! '+7(п — 1)Л" ,э)п+ < х т' > (Л!+'+рл! +дл! ')и'+... = =о =< х,ч > (пЛ" (Л +рЛ+о)+Л вЂ” ел~ э)п'+... =< х, г > Л~ (Л вЂ” д) и'+ .. поскольку (Л вЂ” д) = — д = 0 . Таким образом х"т'+ рх + дхь ' = о(х~~') . При этом координаты п-ой итерации х" ведут себя как соответствующая степень Л: т, = (А" х), Л" х,, поэтому естественно ввести три вектора -!-2,, - ! у ' ' = „„„, Для координат этих векторов, как следует из предыдущего выполнено д„" '+рд„"+ дд,.-' = о([л'|л["") Выпишем соответствующие равенства для пары координат, скажем и и й др д,"+рд„"+дд'„'-' = о[[л'7л["") -о д,-' др д," + рд~ + ддь-' = о [[л'7л["") - б д~-' Домножая первое равенство на д, ', а второе на д„" ' и вычитая из первого равенства второе, получаем -!-! — ! .!-! — ! — + о (~л'|л]"'") = э! -! э! — + о ([л'7Л]") Аналогично.
домножая первое равенство на д,, а второе на дь и вычитая их первого равенства второе, получаем -!-1 в -!-! д = — ',",,"' "„',*" + о [ [л'7л]") Заметим, что необходимое количество итераций в предложенном методе, можно контролировать исходя из того, что должно выполнятся равенство р /4 = д .
2 75 Глава 7 Поиск минимума 7.1 Случай одной переменной 7.1.1 Метод золотого сечения Пусть Ф[х): [а, Ь] -э В. и известно, что на промежутке [а, Ь] функция Ф имеет хотя бы один локальный минимум. Для применения излагаемого ниже метода золотого сечения, от функции Ф[х) не требуется даже непрерывность, достаточно лишь кусочной непрерывности. Будем пока считать, что Ф имеет иа промежутке лишь один локальный минимум [он же и глобальный). Метод основан на сравнении значений функзщи в разлшзных точках, с последующим отбрасыванием промежутков, на которых минимум уж точно не может находиться. Ясно, что чтобы осуществлять подобную процедуру, необходимо знать значения функции, вообше говоря, в 4-х точках.
Действительно, пусть а = хо < хз < х < хз = Ь, и пусть, скажем, в точке хз значение функции наименьшее из этих четырех величин. Тогда минимум Ф заведомо не может нэзсодиться на промежутке [хо, хз] и поэтому этот промежуток можно отбросить. Теперь на оставшемся промежутке [хз,хз] нам известны крайние значения функции и значение в одной внутренней точке. Добавляя новую точку хз мы можем повторить сравнение значений Ф и вновь сузить допустимый промежуток.
Как наиболее разумно размещать добавляемые гочки? Представляется естественным, чтобы деление отрезков происходило подобно предыдущему делению. хз хз хз хз хо Это означает, в частности, что внутренние точки должны располагаться симметрично, то есть [х~ — хо[ = [хз — хз[ = Ь . Боли длина исходного промежутва равна 1, то должно выполняться соотношение ( Ь хз — хо х„ — хз 1 — 2Ь 1 хз — хо хз — хз 1 — Ь откуда Ь 1 — 2Ь 1 — 2( 4= — = Ь Х Разрешая квадратное уравнение относительно 8, получаем Е = з,"з О, 38, то есть на каждом шаге (за исключением вычисления стартовых внутренних точек х1 и хг ) отрезок сокращается в 1/[1 — () - 1,61 раза и сходимость метода линейная.
77 Таким образом, для того, чтобы начать процесс золотого сечения, к граничным точкам хе = а н хз = Ь добавляются две точки х1 = хе+б(хз — хе) х = хз — б(хз — хо). Затем после озбрасывания точек н добавления новых, на последующих шагах номера точек перемешаны беспорядочно. Дадим им номера у,И,гп, и пусть Ф(х ) < Ф(хюб ) . При делении по золотому сечению отбрасывается отрезок одним, из концов которого является точка наиболее удаленная от т, .
Пусть этой точкой является хз (очевидно, что зто одна из крайних точек). Затем надо добавить новую точку х Пусть для определенности хь < х < х, . Тогда в силу симметрии расположения внутренних точек она определяется соотно1нением х„= хе ф хз — х, (т.е, сумма крайних точек минус внутренняя). Если функция Ф имеет на исходном промежутке несколько локальных минимумов, то метод золотого сечения все равно сойдется к одному из ннх, не обязательно к глобальному.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
