Том 2 (1160084), страница 13
Текст из файла (страница 13)
+т„')' у(»()) — у(») (1<Л, + тоаЛ.+ .. + твЛ„)(тЛ,-'+ „.,'Л,.— +... + таЛ- ). (20) Деля каждую из скобок в знаменателе на скобку, стоящую в числителе, и обозначая , =й,; йг>О;,'Рй<=1, (21) 1>+ (а+ ° ° + то получим: г' (х<а>) — г'(»<')) 1 1(х">) — у(»') (ьл,+зла+ ...+ь„л„)(ьл +ал, +...+ь„л„-') (22) ) (х<а>) ) (х*) = (х<о) х*, А(х<а> х*)) =(А-'г(о) г()) Разложим вектор г<а> по собственным векторам матрицы А: Аг<')=1<Л1а, +ТаЦ~а+ ...
+Тола»о А '7' =т,л, 'г,+Тала 'го+ ... +То)„,'а„ (Аг(а), г<о>) = ТаЛ,+Т,Ло+ ... +ТаЛ„, (А 'г(", г< >) = т",Л, ' + ТаЛ '+ ... + 1„аЛ„'. Следовательно, т' (х(о)) — у(х(')) (16) (17) $11! 71 метод скорейшего спускА Применяя доказанное неравенство к (22), найдем: г (ххис>) — э (х(О) 4 У(х>э>) — У(х") ~ / т+ уг"А( ' (31) причем О < о < 1.
Отсюда 7'(хы>) — 7'(х') < (1 — у) ( У (х>Я>) — 7 (х')] = (1 — Ч) с, (32) где через с обозначено выражение [> (х>е>) — 7'(х*)]. Таким образом, для любого й получаем: 7 (х(э>) — 7 (х ) < с (1 — и) . (33) Оценим теперь >>х(ь> — х*>>з. Имеем: !>х(л> — х"!!э =(х(л> — х', хро — х') < — (Ах>л> — Ь, х>л> — х'). (34) Легко проверить, что (Ахш> — Ь, х>л> — х*) = Дх(а>) — ((х'). (35) Таким образом. )/х>л> — х'!~з < — (У(х>л>) — У(х)) < — '(1 — су)" = — („~), (36) Можно усовершенствовать метод скорейшего спуска, осуществляя одновременно несколько шагов.
Благодаря этому удается увеличить скорость сходимости. Олновремениое осуществление р шагов по методу скорейшего спуска эквивалентно вычислению х(~+ > по формуле р-г х(~+~> = х(~> + ~)' а~~>А~с(~>, з О (37) где, как и ранее, г(~>=Ь вЂ” Ах(~>, а коэффициенты а(а> подбираются так, чтобы 7(х(л+>>) приняла наименьшее возможное значение. Это требование к а~~> приводит к системе уравнений р-т — Х>а>+ ут а(~>А>ГЫ> =О (>=О, 1, ..., р — !) (38) >-о нли р-т '~~ а)~>(А>г(~>, Ау+~с(а>) = (А>г(л>, г>а>) (> =О, 1, 2,..., р — 1). (39) э-о и мы доказали.
что метод скорейшего спуска сходится со ско- ростью геометрической прогрессии к точному решению. 72 рвшвиии еиствм лиивйных алгивраичиских уравнений [гл. 6 Исследуем сходимость этого метода, Подберем постоянные 1» так, чтобы многочлен р-1 Т(Л) =1 — чр ЧЛ'"' (40) »=о имел наименьшее возможное значение максимума модуля на отрезке [и, л([. При Л = О наш многочлеи будет равен 1. Такое построение мы уже осуществили в 8 8 и видели там, что р (Л) просто выражается через многочлеиы Чебышева, наименее уклоняющиеся от нуля. При этом аяр [р(Л)1= Ь,1.
ЛЕ 1я», л») Следовательно, собственные значения матрицы 1 В Х вЂ” ~~', т»А + »-о (41) которые равны э(Л ) (Лу — собственные значения матрицы А) также по модулю меньше едийицы. Поэтому мы можем решать систему у = у + ~~~~ е»А (Ь вЂ” Ау) Х (42) относительно у методом простой итерации: и-1 у("+ 1= у<"1+ ~~ »»А ГЬ вЂ” Ау(а)) (43) о Так как простая итерация сходится, то система (42) имеет единственное решение. Таким решением может быть только х"= А 'Ь.
Обозначим й(а1 = у«э) — х'. (44) В силу (43) имеем: й('+'1 = Вй<а) (43) Таким образом, (Аи»" +1), и»"+О) = (АВи(а1, Вй(э») = (АВл и»э), й(э)). (46) Разложим вектор ирб по собственным ортонормированным векторам матрицы А: й = «тат+ «эха+ . + «яйя. (ь) (47) Тогда (АВ' и»111 й(э1) = ( ~ ПЛ»»рэ (Л») х», ~~ .1»л, 1=1 = ~~~~ «Ял») л» < з'„'Р ря(л) Я «Эл,= йа(Аи»Л1, и<~)). (48) Итак, (Ай(э+". й»" +11) ( ьэ(Ан«э>, й»л)). (49) х(" — х = е'»1 В=о, 1, ~...Л (50) Возьмем теперь в качестве у»а» вектор х»Л', полученный по методу ско.
рейшего спуска„Обозначим 74 Решение систем линейных АлГЯБРАических УРАВнений [Гл. 6 5. Пусть для решения системы Ак = Ь используется итерационная формула к!""> = 4)+ !)А) х!М вЂ” 4)ь, где 0 — некоторая неособенная матрица. Локазат1ь что метод сходится для любого начального вектора х1~1, если все характеристические иории матрицы !3А расположены внутри круга с центром в точке А = †! и радиуса 1, 6. Локазать, что если ВА предыдущей задачи есть сА, где с — отри.
цательная постоянная, удовлетворяющая одному из условий [ с~( шах ~~ [ агл + ал! [+ Шах ~ъ [ а11 — ая, [ А 1 а-1 или [с [( то метод последовательных приближений сходится. Т. Локазать, что метод последовательных приближений, приведенный п упражнении 5, сходится для всех симметрических положительно или отрицательно определенных матриц А, если взять  — сй где [ [( шаХ ~[ать[ а-1 и с(0 для положительно определенных А н с) 0 для отрицательно определенных А. 8.
Пусть для решения системы Ах = Ь используется итерационная формула х<"+ 0 = В 1 [ Ь вЂ” А (х!а! + к<1> + ... + ЛРЛ)[, где  — некоторая неособенная матрица. Локазать, что этот способ сходится и дает решение исходной системы, если максимальное собственное значение матрицы С'С, где С= АВ меньше, чем минимальное собственное значение матрицы В'В. ЛИТЕРАТУРА 1. В, Н.
Ф а д д е е в а, Вычислительные методы линейной алгебры, Гостехиздат, !950. 2. Л. В. Канторович, Функциональный анализ и прикладная математика, УМН, т. 3, вып. 6, 1948. 3, Л. Фокс, Х. Л. Хаски, Дж. Х. Билкинсон, Заметки о решении систем совместных линейных уравнений, УМН, т. о. вып, 3, 1%0. 4. М. Ш. Б и р м а н, Некоторые оценки для метода наискорейшего спуска, УМН, т. 5, вып.
3 1950. 5. М. Р. Ш у ра-Б у р а, Ошснка ошибок при численном обращении матриц высокого порядка, УМН, т. 6, вып. 4, 1951. ЛИТЕРАТУРА 6. А. Тю ринг, Ошибки округления в матричных процессах, УМН, т. 6, вып. 1, 1951. 7. М. А. К ра си ос ел ь с к ий, С. Г. Крейн, Замечание о распределении ошибок при решении систем линейных уравнений при помощи итерационного процесса, УМН, т. 7, вып. 4, 1%2, 8. Л.
В. Канторович, Приближенное решение функциональных уравнений, УМН, т. 11, вып. 6, 1956. 9. К е рт и с с, Методы «Монте-Карлоь для итерации линейных операторов, УМН, т. 12, вып. 5, 1%7. 1О. О. р о г а уг Ь е, решение линейных алгебраических уравнений может быть интересным, Ва11 ашег. Майи Бес., т.
59, М 64, 1953. (Приведена обширная библиография различных методов решения систем линейных алгебраических уравнений.) 11, Х а у с хо л д ер, Основы численного анализа, ИЛ, 1956. 12. Мил н, Численный анализ, ИЛ, 1951. ГЛАВА 7 ЧИСЛЕННЫЕ МЕТОДЪ| РЕШЕНИЯ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ ВЫСШИХ СТЕПЕНЕЙ И ТРАНСЦЕНДЕНТНЪ|Х УРАВНЕНИЙ $1. Введение В этой главе мы рассмотрим некоторые методы численного решения уравнений вида )(г)=0, где ) (г) — заданная функция действительного или комплексного аргумента г; в частности, у'(г) может быть многочленом степени и от г. При отыскании приближенных значений корней этого уравнения приходится решать две .адачи: 1) отделение корней, т.
е. отыскание достаточно малых областей, в каждой из которых заключен один и только. один корень уравнения; 2) вычисление корней с заданной то~настаю. Так как для алгебраических уравнений разработано больше ме~одов о~деления корней и методов их вычисления, то мы в дальнейшем будем более подробно ос1анавливаться на алгебраических уравнениях. $ 2. Отделение корней 1. Обшие замечания. При решении уравнения у'(г) = О прежде всего важно предварительно изучить расположение корней в комплексной плоскости г и заключить каждый корень в достаточно малую область, внутри которой не было бы других корней.
Для этой цели иногда выгодно применять графические методы. Если требуется найти только действительные корни уравнения, то для отыскания грубых значений корней можно построить график функции у =у'(х) и найти абсциссы точек пересечения графика с осью х (рис. 2). Иногда удобней представить сначала уравнение в виле ~е(х) = ф(х) 77 отдвлю1ив когнвй и затем, построив графики функций у=о(х) и у=ф(х), найти абсциссы ик точек пересечения, которые и будут приближенными значениями корней. Например, если нужно найти корни уравнения Х51ПХ= 1, то удобно представить его в виде 1 5!их=в х и применить указанный способ (рис.
3). Корни уравнения симметричны относительно х = Рис. 2. = О. Поэтому мы можем рассматривать только положительные корни. Значения х,, х, и, возможно, еще нескольких корней можно довольно точно определить графически. Однако на графике не будет х„для больших значений л. Тем не менее по ходу графиков мы можсы сказать, что значения х„при больших л будут близки к ял.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
