Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 84
Текст из файла (страница 84)
Остается доказать, что последовательности а([й) стремятся к нулю. Имеем 518 атеглционные методы для вешания полной пгозлемы [гл. чщ Из доказанной теоремы следует, в частности, что если взять ~а=се= ... =О (схема <Ю), то при (Л,)' )), () ... >(Л„(, получим 1нп р<«) = Л, < <ет «~~о Точнее р< )=Л„,+О( — ""-)'+О~ — '*"') . (26) ~ ˄— р<а) — ~«! ч,. е.
га,=р<„'),+(„, ! ˄— р<а+,') — с«( ~ ре', Тогда, взяв получим где р — некоп)оран константа. доказапсельспгво. Можно доказать. что в зсимптотической формуле (25) порядок остаточного члена, в условиях теоремы 77.2, оказывается точным. Именно. где )И вЂ некотор константа, аа -ь О. Позтому а — —" +та.
<ач 1) та+) ( ) Ча- т и-) (1 '„' (1+ «) = 1+ «). та( и-<)та("и) п-г — 'а © л+с Таким образом, результат теоремы 77.1 распрос~раняется на любые матрицы с вещественными собственными значениями, удовлетворяющими неравенствам <Л, () <)т~ ) ... ) <Л„~, если только предположить, что все Ь««) не равны нулю. В работе Рутисхаузера 121 рассматривается и случай комплексных собственных значений, а также возможные вырождения процесса. Задача вычисления собственных векторов рассмотрена в работе 141.
Сходимость алгорифма деления и вычитания, особенно при наличии близких собственных значений, довольно медленна. Так как зтот процесс к тому же не самоисправляющийся, при длительном его проведении возникает опасность некоторого накопления ошибок округления. Тем более интересна возможность использования сдвигов для ускорения сходимости процесса.
Именно, при некотором определенном выборе сдвигов получается процесс с квадратичной сходимостью поочередно для каждого собственного значения. Теорема 77.3. Пусть на некотором <лаге проиесса <',)О (со сдвигом или без сдвига) в условиях предыдущей теоремы уже получено. что й 771 алгоеивм двлкния и вычитания где а,' -ь'О. При С„„=р<„">,+1в имеем Л Шз'П вЂ” Г, Л вЂ” 1Ы ч ~в — г ьь! ч Ра-1 в~1+ откуда (27) Л.— Р'„"~н — Гь,г ! ( Р". при 2 ' ~ )) -~ — 'с! Опишем теперь упомянутый процесс с ускорением. допустим для простоты, что все собственные значения положительны и Л, ) Л,) ) ) Лги Пусть сделано несколько шагов алгорифма ЯЕ) без сдвига, так что в грубом приближении последний столбец начал стабилизироваться. Пусть это произошло на й, шаге.
Тогда берем ~„„, =р1„"»,, я=Р1Ь 'Н+Г„,, ... В НОВОМ ПРОЦЕССЕ МЫ ПОЛУЧИМ КзаДРатнЧ- ную сходимость последовательности Гв к Л„; последовательности же а~и~„и Р~"~ сходятся с той же быстротой к нулю. Пусть при н=й, числа ч~'4„и р1Ы, практически станут равными нулю. Тогда можно принять, с той же степенью точности, ˄—.~а, и перейти к процессу с ускорением для определения Л„ ,. Именно, полагаем Г =-ры>, 1 =Р<"*",Н+г ... При этом мы выь„.г! и-2' йя+2 и-3 г,ьг черкиваем из схемы столбец, состоящий из значений Р<")н так как последние более не нужны ни для определения Л„, ни для продолжения схемы, ибо о1„"~, стало и остается равным нулю.
После определения Л„ , переходим, поочередно, к определению Л„ а, Л„ ,, ..., Л,. То, что в этом процессе для каждого собственно~о аначения будет иметь место квадратичная сходимость. следует из того, что по ходу процесса векторы р<"Л р<а>, ..., р~~~, будут попадать в инвариантные подпространства убывающих размерностей и Л„ ,, Л„ ,, ...
..., Л, будут играть поочередно роль наименьших собственных значений. Укаэанный процесс можно применять уже при переходе ко второй строне, полагая 1а=Р(П и à — 1,=Р1з1, ... При этом, однако, несколько первых сдвигов будут иметь случайный характер..и процесс начнет быстро сходиться, лишь как только один из сдвигов .окажется близким к какому-либо собственному значению. Именно 520 итиялционныи митоды лля иишиния полной пеоьлимы !пл.'ип !' и и' о о о оо о а Ио ИбнвВВ6аИйп оаоооооооооо $йлеБ83 ооооооао $35 ЯЯ И а и но н а Е Но о С о о 1 и Ю и и о о !'и и и $С оооо оо о $ц$о оы 'Ыо ооо ооо ооо 1 $~ ~ййБд$ аф оооооын 'оноа 1!11!1!111 ЙЙЙ оооооооо о ! ! ! 1 Раааи ооооооаооо аа ~а воо й 771' Алгоуиэм деления и ВычитАния 521 это собственное значение будет определено первым.
Следующим, вообще говоря, определится собственное значение, ближайшее к полученному. Применение сдвига возможно,и на первом шагу процесса, т. е. можно взять весовой полипом р„(!) равным (à — Г()(! — !в) ... (1 — 1А) при Г,+ О. Это влечет за собой изменение начальной строки процесса.
Легко видеть, что она в этом случае должна быть построена по формулам ((=1, 2..., и — 1) (1=!. 2, ..., и — 1). В этой форме ()О процесс полезен для уточнения полученного каким-либо другим способом грубого приближения к одному из собственных значений. За !( следует взять это известное грубое приближение и далее применять процесс ЯО со сдвигами так, как он описан выше. В табл.
Ч1И. 1 — Ч!И. 6 приводится числовой материал, и.члюстрирующий ход Я0 процесса. В табл. ЧИ!. 1 дается ход (',)В процесса без ускорения для положительно-определенной матрицы (4) й 51. Первая строка таблицы заполняется по данным табл. Ч1.!6. В табл. Ч!И.2 приведен для той же матрицы ()!) процесс со сдвигами Г = О гь+ = гь+ Ф. В этом случае все четыре собственных значения определяются после двенадцати шагов процесса. В табл. Ч!П. 3 дается ход (;)с) процесса для не положительно-определенной (н даже несимметричной) матрицы Леверье. !1ервая строка схемы взята из табл. Ч!. 17. В табл. ЧП!. 4 приводится для матрицы Леверье ь)О процесс со сдвигами 1г = ~з =за = ~о = !о = !в = () 1А(.( — — 1ь+рз при й)~6. (ь) Наибольшие корни получились с невысокой точностью из-за некоторой потери точности на 7-м и 8-м шагах.
В табл. ЧШ. 5 дается уточнение наибольших корней матрицы Леверье прн помощи схемы ЯЕ) с постоянными сдвигами. Наконец, в табл. ЧП1.6 дается уточнение первого собственного значения с изменением начальной строки процесса на г(= — 17.863248 и с последующими постоянными сдвигами. БЙВ оод о о оа о:о ьа ««о оо о ' оы ' ' ' ' о ' ' тимы о 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 'йй 111 оооо ~Е фоа о а М- оф 1 ! а ) Я,„ оа ао ! о О оао $ оо ' 'Ыо 'ао оооо 1имооо ' 11 11! 1 и И 3 й$ а О ен и ы С,7 ЙВиа Ы о в~о о ои оа .Др 'ооооао 1~1 О «Д Оооо о о .Оо Ы 1 ' оаы оти '0 о 'оооо ' 1а 'йы ' 'ааааа 11 аоо 3 а о а оа о О ~й ., В' ойоЗо ооой Ыоо О ооооим оооо 111111111 О О 7 а О 11111111 о оаа ° Р оа )о э'~ 522 итеелционные методы для еешения ионной ннонлемы 1гл.
чн и 77! сч 1 О м О О Ф Со 01 СЧ Сч 40 О СО СО СО 1-' 1 о о 1' 1' 4' 1 о 00 ОЪ ! 40 СЪ О О 00 СО 1-' о о 1' 'ъ СР о 00 о о о СЪ Я о о о о о о о о С'\ ооо о о о ОЪ О ф 8 о о о о С'1 С'4 о о ОЪ О о о о о о о О О О О Ф о О О Ф О Ф и О 'О ОЪ о о оо о т о о о ! о сч ОЪ Я 'тъоо С СО Сп о сч о сч о со О ССЪ ОЪ СЪ о о 10 Ф Ф х 1-:.1 М -'1 СО .О О 1 со Сс сп оо ОЪ ! О Сь О Со 1 О :Ч СО СО О 6- СО СО О 4'Ъ 00 Ъ ОЪ СО С'Ъ О О ° ъ о ! 8 СЪ Сь ОЪ С'Ъ СО 00 СЧ $ Я 383 00 О СЪ О 'Ъ ОЪ 'Ъ Сс Сп сч о СЪ СЧ ь Ф О О Ф т О яяВЗ СО ОЪ 1 Я О: со я о о о о СО \О 1 О 4' О СЧ о О 1 Со Со о о о 10 о С'Ъ С'4 С'1 о л со Я Ц о СО о о 1' ОЪ СО С'4 0 ь Оъ ОЪ Сп' С1 .Ъ о о Ч О О ь о о О О м и И О О О О О Ф а 4НС и Ф х Ф Р О х н м Ф Ф С1 О О лнгививм виляния и вычнтлння Ф Х м Ф О 10 О С О О О Ф 01 1 4О О 524 итивлционныв методы для вешания полной пговлвмы !гл, юп 5 78.
Треугольный степенной метод А — - С»О В». (а) .. Предполагается, что такое разло>кение возможно при всех а. Тогда, при некоторых дополнительных ограничениях, матрицы Ой=([([> ), ..., дя таковы, что ,~(а) 1!ш», — Ло аэ. а1» " а матрицы Са и Ва стремятся к предельным матрицам. Докажем зто. Прежде всего отметим Я 1, п.12), что д[а) !(») (2) -> где Л; верхний главный минор 1-го порядка матрицы А . Оце(а) (а) ним Ь(> ). Пусть А=Р >ЛР, где Л=[Л„..., Л„[. Тогда А( ) = КА М=КР >Л РМ.
Положим Чц Чгв КР " Фа ° ° Ч Рц ° ° Р>в РМ= Рщ Рин Тогда — а а а Л,Рц Л>Ри ° .. Л,Р>н а й а й Л РМ ~ ЛзРм Лзрзз ° ° Л»Рзи Треугольный степенной метод (Бауэр [7[) является обобщением ступенчатого степенного метода, приспособленным для нахождения всех собственных значений матрицы А. Мы будем предполагать, что все собственные значения матрицы А вещественны и различны по абсолютной величине. Обозначим их ), ..., Л„, занумеровав в порядке убывания абсолютных величин.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
