Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 46
Текст из файла (страница 46)
Это можно сделать несколькими способами, и в следующем разделе мы изложим метод, основанный на ЯЯ-алгоритме. В этом разделе мы опишем классический метод последова- тельностей Штурма. Мы теперь будем предполагать, что все внедиагональные элементы Ь,, Ь„, отличны от нуля.
Это не приводит к какой-либо потере общно- сти, так как если некоторое Ь~, О, то характеристический полипом три- виально разлагается в произведение двух полиномов, каждый из которых можно рассматривать отдельно. Определим следующие полиномьк Ро(Л) = 1, р,(Х) = а1 — Х, (6.2.6) Рю(Х) — (ар — Х)Р; 1(Х) — Ь|,р~ э(Л)1 !=2,...,п, Ь, О а,— Х Г а1-Л Ь~ = (аэ — Х)апет ~ Ь| аэ — Л Ь, а2 Ь3 Ь2 аз —" дет О Га1 — Х 01 Ь2 де~ (аз — Х) рэ( Л ) — Ьэ р1 ( Л ). ~ ь, ь, ~ Верно и более общее утверждение: рг является характеристическим ~олиномом подматрицы, состоящей из первых ~ строк и столбцов матрицы А „1.
Поскольку каждая из этих подматриц симметрична, все полиномы рг имеют только вещественные нули. Мы теперь покажем, что полиномы рг обладают следующим свойством: если р~(Хо) =О, то рю~~(Ло)рг,(Хо)<О. (6.2,7) Это свойство говорит о том, что если Хи — нуль некоторого полинома Рк то 192 где а ~ — диагональные элементы, а Ьг — внедиагональные элементы матри- цы А „1. Ясно, что р~ — полипом степени г, причем р„есть характеристи- ческий полипом матрицы А„1. Действительно, например, при и = 3. используя разложение по минорам, имеем о значение не является нулем ни полинома рт 1, ни полинома рт+,, причем рт 1 и рт+1 имеют в точке Ло разные знаки.
Если, например, ,,(Л ) =О,то р,(Л,)Ро(Ло)=-ЬгРо(Ло) = -Ьг1 < О. В обшем случае утверждение (6.2.7) доказывается по индукции. Пусть р„+, (Ло) = О. Тогда по предположению индукции рь (Ло) Ф О, и так как рь+г(Ло) = — 6~~~Р (Ло) мы получаем рь(Ло)рь+г(Ло) = — Ьь+1рь(Ло) < О. Полиномы (6,2,6) образуют так называемую последовательность Штурма, а свойство (6.2,7) известно как свойство последовательности Штурма.
Из (6.2.7) следует важное свойство перемежаемости нулей полиномов р,, которое мы проиллюстрируем на примере п = 3, Пусть Л, < Лг < Лз, д, < дг и и, — нули полиномов рз, рг и р1 соответственно. Во-первых, заметим, что непосредственно из определения (6.2.6) имеем р~(Л) > О при Л -э —, .г=1, ...,п. (6.2.8) Отсюда, так как рг(Л) — квадратичный полипом, следует, что рг(Л) > О при 1Л 1-+ + . Кроме того, в силу (6,2,7) имеем рг (и,) < О, так что д, < р, < дг, Проведем аналогичные рассуждения относительно полинома рз, Так как р, (д1) > О, а р1 (дг) < О, то снова в силу (6,2,7) имеем Рис.
б.2. Свойство неремежае- мости нулей Рт<Р1 <Рг, Л1<Р1 <Лг<дг<Лз. (6.2.9) Полиномы рт, рг и рз изображены на рис, 6.2. Из свойства перемежаемости нулей следует, что все нули полинома р„(т,е. собственные значения А и 1) различны. Этот факт есть следствие предположения о неравенстве нулю внедиагональных элементов Ь~, Мы теперь можем использовать свойство перемежаемости нулей как основу численного алгоритма аппроксимации собственных значений, Для произвольного Л определим функцию с(Л) как число совпадений знаков 1З дж. Ортега 1оз рз(р.1) < О и рз(дг) > О. Отсюда, так как рз — кубический полипом и Рз ( Л ) > О при Л -~ —, заключаем, что полипом рз должен иметь нуль на каждом из интервалов ( —, д,), (д,, дг) и (дг, + ).Таким образом, мы приходим к свойству перемежаемостн нулей у следующих друг за другом членов последовательности 1, р1(Л), рг(Л), ..., р (Л), причем, если некоторое р1 (Л) = О, то в качестве знака этого члена будем брать знак р~ 1 (Л) .
Предположим, например, что п = 3, р, ( Л ) = 2 — Л, рз ( Л ) = (2 — Л) ' — 1, рэ ( Л ) = (2 — Л ) р э ( Л ) — р, ( Л ), Вычисляя последовательность Штурма при Л = О, получаем значения (+1, +2, +2, +3), т.е. мы имеем три совпадения знаков последовательных членов, так что с(О) = 3. Аналогично, с(2) = 2, а с(5) = О, Оказывается, по функция с ( Л ) обладает замечательным свойством, которое непосредственно спедует иэ свойства перемежаемости нулей.
Т е о р е м а 6.2.1. Значение функции е(Л) равно числу нулей полинома р„, больших или равных Л. Этот результат можно использовать как основу для построения численного метода нахождения приближенных значений нулей полинома р„. Будем считать, что нули упорядочены в порядке убывания: Л1 > Лз »... Л„. Пусть [1, и] — отрезок, в котором содержатся все собственные значения.
Такой отрезок легко определить следующим образом. Как указывается в приложении 3, любая норма матрицы дает оценку сверху абсолютных величин всех собственных значений. В частности, ! Л~ ! < !! А„, !! (1 = 1,..., н), и мы можем положить 1 = — !!А„1!! и и = !!А„-~ !! Вычислим с(Л) в средней точке 71 отрезка [1, и]. Значение с(7,) дает нам число нулей Л~ на отрезке ['у1, и].
Предположим, что мы хотим найти значение третьего по величине нуля Л,. Если с(7,) > 3, то мы знаем, что Л, Е Е [у,, и]; в противном случае Лэ Е [1, 7, ]. Предположим, что Лэ Е [7,, и], возьмем в качестве 7а среднюю точку отрезка [7,, и] и вычислим значение с(7э). И снова, если с(7~) > 3, то мы знаем, что Лэ Е [уэ, и]; в противном случае Лэ Е [71, 71]. Мы можем продолжать эту процедуру, запоминая отрезок, в котором должен лежать корень Л„и вычисляя следующее значение функции с (Л) в средней точке этого отрезка.
После 1с делений мы получаем отрезок длиной 2 ~ (и — 1), содержащий нужный нам нуль. Продолжая процесс деления, мы можем сделать этот отрезок сколь угодно малым. Обратите внимание, что только что изложенный метод очень близок к методу половинного деления, рассмотренному в разделе 4.2. Однако функция с(Л) дает информацию о всех нулях, которую можно использовать для значительного сокращения затрат машинного времени.
Предположим, например, что в предыдущем абзаце с(у1) = 7. Тогда мы знаем, что все нули Л,, Л~ лежат на отрезке ['у1, и], и можем использовать вычисляемые затем значения с(7~) для локализации расположения сразу нескольких нулей, а не какого-то одного конкретного нуля. Теперь перейдем к вопросу о вычислении собственных векторов матл рицы А. Предположим, что мы уже нашли приближение Л~ к собственному значению Ль и хотим определить соответствующий собственный вектор х. Первым шагом является вычисление соответствующего собственного векл тора трехдиагональной матрицы А„з, Если бы Л„совпадало с точным собственным значением Л„, то собственный вектор был бы нетривиальным ре- 194 шепнем однородной системы уравнений л (А„т — Х»1) х = О.
(6.2.10) л Если же Х» отлично от Х», то система (6.2.10), вообще говоря, не имеет нетривиального решения. Мы, однако, не будем пытаться найти нетривиальное решение (6.2.10), а возьмем в качестве приближенного собственного вектора решение системы (А„1 — Х»1) х = И, (6.2.11) где вектор правой части Ы будет выбираться определенным образом. Чтобы выяснить, при каких условиях это решение будет хорошо аппроксимировать собственный вектор, сначала напомним, что при нашем предположении о том, что все Ь; Ф 0 в (6.2.5), все собственные значения матрицы А„, различны, и в силу теорем 6.1.1 и 6,1.2 она имеет п линейно независимых собственных векторов ').
Обозначим эти соответствующие собственным значениям Л~,..., Х„векторы как у~,..., у„. Тогда мы можем разложиты1 по собственным векторам: 4 = 7~ У~ + + 7л Ул. л Заметим теперь, что матрица А„1 — Х»1 имеет собственные значения л Х; — Л» (1 = 1... л) и соответствующие собственные векторы у„..., у„, л л а матрица (А„1 — Х»1) ' имеет собственные значения (Х; — Х„) ' и те же собственные векторы ч,,..., у„. (Эти утверждения в более общем виде сформулированы в упражнении 6.2.1.) Следовательно, мы можем написать л П л х=(А„1 — Х»1) ' д= Х 7;(А„1 — Х»1) 'у;= 1=1 (6.2.12) л 71 7» л — Х вЂ” '„у,= — лу»+ 2: Л; — Մ˄— Л (= Л; — Л тФ» л л Предположим теперь, что Л» достаточно близко к Л», скажем, 1Л» — Х» ! = = 10 е, и что Х» не слишком близко ни к какому другому собственному значению Л1, Тогда при условии, что коэффициент 7» не слишком мал, в выражении (6,2,12) будет доминировать член 7»(Л» — Х»)-' у».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
