Беклемишев - Дополнительные главы линейной алгебры (947281), страница 39
Текст из файла (страница 39)
При 1 = 1 для У ( з! имеем также т»»т-1- О, но Уже за счет того, что в числителе дроби степень й меньше, чем »1 — 1. Коэффициент ~О»„имеет конечный ненулевой предел, который мы обозначим через )1. Итак, при и-О- СО и О! !'Оцй/ХО +' )!21О,ХО 1=11=! Мы видим, что для любого е ) О при всех й) й, (е) 17».с» — и21„.с»1(е.
Отсюда нетрудно получить (рай!.,.с,( — е(17,х (((Иго,.с,1+е и, так как!!7»х»О»!! = 7» Ц х»+1 ~! = 7», 7» О (Р"!15!ЛО). В общем случае Е»„)СО Ф О, а значит, не равен нупю предел 7 последовательности 7». Отсюда )! т .КО+»- — 21! ХО. 7 ! К рассмотрению случая Е»мх» = О мы вернемся несколько позже. $ а Вычисление сОБстВенных вектОРОВ 173 Для сходящейся последовательности у„отношение уь/у» т стремится к 1. Поэтому нз ие Р~ — ~) 7„1 )., ь следует а„— ~ 7, Равенства (1) можно записать в виде Ахь = аьых~,.
Переходя к пределу, мы видим, что х„стремится к собственному вектору, принадлежащему собственному значению ),ь Впрочем, вспомнив определение компонентных матриц, нетрудно заметить н непосредстненно, что в том случае, когда Я„,х, отличен от нуля, он является сооствениым вектором, принадлежащим 7ч, Посмотрим на проведенное рассуждение несколько подробнее. Каждый член суммы (3) стремится к О или к сз при й-+- со, и это определяется его «порядком» 7м. 17.ь..й(ы накладывали ограничение 11, ~ ) ( Ц ( (1) 1). В общем слу~ае могут оказаться несколько иле~он суммы (3) с раиными ~ор~дка~и. Тогда хь сходится к некоторой линейной комбинации собственных векторов, соответствующих этим членам. Для вещественных матриц предположение о вещественности максимального по модулю характеристического числа является существенным. Есть возможность находить степенным методом комплексные характериствческие числа и соответствующие инварнантные подпространства для вещественных матриц, но мы не будем останавливаться на этом вопросе.
Теперь обсудим, что будет, если начальный вектор х, выбран так, что У„,х„= О. В этом случае член сумзы (3) с максимальным порядком обращается в нуль. Изменяя рассуждение, мы должны будем разделить обе части равенства (3) на самый большой из порядков не обратившихся в нуль членов. В остальном доказательство пе изменится, и мы увидим, что последовательность хь стремится к сооственному вектору, соответствующему старшему из членов.
В частности, может оказаться, что этот собственный вектор принадлежит другому собственному значению, Однако в действительности равенство Л, х, =- О вполне точно выполняться ие может, и даже если бы оно выполнялось, ошибки округления на первых >ке итерациях вызовут эффект, равносильный его нарушению. Значит, в рассматриваемом случае последовательность х, вполне может сходиться к собственному вектору, принадлежащему максимальному по модулю характеристическому числу. Этого может не произойти, если ошибки округления малы, а последовательность сходится быстро.
3. Обратный степенной метод. В других вариантах степенного метода тот же процесс применяется не к исходной матрице А, а к некоторой функции от нее. Рассмотрим широко применяемый ва- 174 гл. пи вввдвнив в числвниыв матоды рнант, называемый обратным степенным методом со сдвигом. В этом случае вместо матрицы А используется матрица (А — рЕ) '. Конечно, обратную матрицу можно не вычислять, а строить последовательность по формулам хл — — а.„, (А — рЕ) хмы (5) решая систему линейных уравнений относительно х„„,.
При этом пользуются вычисляемым один раз П/-разложением или 9Л-разложением матрицы А — рЕ. Характеристические числа гч матрицы А — оЕ связаны с характеристическими числами Л равенствами р, = (Х, — р) '. Таким образом, обратный степенной метод со сдвигом дает последовательность, сходящуюся к собственному вектору Л, принадлежащему тому из характеристических чисел Л„для которого ! Х, — р ~ " максимален. Это характеристическое число является ближайшим к числу р. Обычно обратный степенной метод со сдвигом применяется в том случае, когда надо найти собственный вектор по известному приближенному значению характеристического числа.
При этом сдвиг полагают равным этому значению, н последовательность сходится очень быстро, возможно, за одну птерацшо. Трудность здесь состоит в том, что при р, близком к характеристическому числу Ц, приходится решать систему с плохо обусловленной матрицей. Пока>кем, что, несмотря на эту трудность, собственный вектор может быть получен достаточно точно, если он пе является плохо обусловленным, и собственное значение )ч хорошо отделено от соседних. Точность вычисленного вектора х может быть оценена по не- вязке т>=(А — рЕ)х.
Норму !!х ~~ = (хгх)ьа вектора х будем считать равной Е Тогда предыдущее равенство можно переписать в виде (А т>, г)х Отсюда видно, что х является точным собственным вектором, принадле>кащим собственному значению р для возмущенной матрицы А — ч>хг. Если норма невязки мала, то мала и норма возмущения Н = — т>хг. Действительно, для любого вектора у при ~(у ~| = 1 имеем !!(охг)у~~=!~о(хгу)(~» ~~е>!й причем равенство достигается при х = у. Поэтому для возмущения Н находим 3Н)= зпр 3~Ну(=(4>(, !э~ 1 Формулу (5) можно записать в виде (А -рЕ) ха>т=— аьм ' 175 $6. ВЫЧИСЛЕНИЕ СОБСТВЕННЫХ ВЕКТОРОВ Напомним, что п~.1 выбирается так, чтобы вектор хь+, имел норму, равную 1, т. е.
аь+1 — — 'З (А — рЕ) 1ХВ1, Вектор Х*/аз+1 можно трактовать как невязку, которую дает х„+„и, следовательно, чем больше ал+„тем меньше невязка и тем меньше эквивалентное возмущение О. Для того чтобы оценить величину аь, вспомним, что в общем случае (т. е. для начального вектора х„не удовлетиоряющего некоторому точному равенству) величина а~ стретп1тся к наибольшему по модулю характеристическому числу матрицы, определяющей процесс. Если сдвиг О близок к Ц и удален от остальных характеристических чисел А, то наибольшим по модулю характеристиче. ским числом матрицы (А — рЕ) ' будет (Х1 — р) '.
Таким образом, а1,=()ч — р) '0(1), и можно ожидать больших значений а„и, следовательно, малой нормы иевязкп. Однако на первых итерациях это пределы1ое соотношение не играет такой роли, как выбор начального вектора. Покажем, что прн удачном Выборе э1ого вектора можно получить малую невязку уже на первой итераш1и. Действительно, мы можем предполагать, что норма матрицы А — рЕ невелика п число обусловленности 1~ А — рЕ 1 ° ~~ (А — рЕ) ' ~~ велико потому, что ~~ (А — рЕ) 11~ е ', где з — некоторое малое число. В случае спектральной нормы это означает, что существует единичный вектор х„для которого ~ (А — рЕ) 'х, ~ ) е '.
Это — первый вектор сингулярного базиса матрицы (А — рЕ) '. Если в качестве начального вектора взять х„ то уже после первого шага невязка окажется по норме меньше чем з. Приведенное соображение не слишком утешительно, так как хороший начальный вектор нам неизвестен. Впрочем, оно не так бесполезно, как может показаться. В самом деле, при решении плохо обусловленной системы линейных уравнений оказывается большой как раз компонента ошпоки по первому вектору сингулярного базиса обратной матрицы (предложение 5 ь 2). Поэтому, если на первой итерации решение содержало большую ошибку, эта ошибка вызовет сокрашсние невязки на следующей итерации. Обсудим скорость сходимости обратного степенного метода, Она зависит от коэффициентов в разложении (3), написанном для матрицы (А — рЕ) '.
й,х,=~ ~ (Р.,— р)-)п- йг„х.. 1/=1 Производная ((Х, — р)- )У-11 равна ()11 — р)-В при 1' = 1, а при 1) 1 ( 1)» В (В+1).„СУг+) 2) (л,— р) т-з 176 Гл.не ВВедение В численные методы Если р близко к Л~ и Умгкч~ О, то старшим будет член, содержащий этот вектор, и порядок коэффициента в старшем члене равен ь 5~ 1 „+,, Скорость сходнмости определяется скоростью стрем(л,— р)"' лення к нулю отношений Вт- (л| — р) + с (л; — р)"г-' Мы видим, что наименее благоприятен случай, в котором существует характеристическое число Лю также близкое к р и имеющее большую кратность в минимальном многочлене.
Иногда положение может быть исправлено при помощи изменения сдвига, но если Л~ и Лр действительно близки между собой, это свидетельствует о плохой обусловленности задачи. СкоРость сходимости УменьшаетсЯ также, если вектоР йГьпх, мал или равен нулю. Как объяснялось выше, его обращение в нуль, вообще говоря, не влияет на вычисленный собственный вектор.
Вектор, к которому сходится последовательность, может зависеть от начального приближения в двух случаях. Во-первых, если существуют несколько различных характеристических чисел, модули которых равны и превосходят модули остальных. Во-вторых, если максимальному по модулю характеристическому числу соответствует собственное подпространство размерности т ) 1. Кзк в этом случае найти базис этого подпространства, мы опишем несколько ниже. Ошибки округления, возникающие на каждой итерации, как и при итерационном решении систем линейных уравнений, влияют на сходнмость процесса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
