Бахвалов, Лапин, Чижонков - Численные методы в задачах и упражнениях (1032349), страница 13
Текст из файла (страница 13)
Пусть матрица А„(а, Ь) определена как и в предыдущей задаче. Доказать, что она положительно определена тогда и только тогда, когда а-2~Ь| соз — > О. и+1 1Т.34. Предположим, что матрица А Е Ки" и — симметричная и положительно определенная. 1) Показать, что существует единственная симметричная и положительно определенная матрица Х такая, что А = Хз. 2) Показать, что если Хо = 1, Х»+1 — — (Х» + АХ» ~)/2, то Х» -» -+ чг'А, где 1ГА означает матрицу Х из 1). 1Т.ЗЗ. Предположим, что матрица А Е В.и"" — симметричная и положительно определенная. Рассмотрим следующие итерации: ~от Ь = 1,2,... А» 1 = ѻѻт (разложение Холецкого) А» = С»0» т 1) Показать, что зти итерации сходятся; 2) Показать, что если матрица А=, а>с, имеет собственные значения Л1 > Лз > О, то матрицы А» сходятся к матрице йа3(Л1, Лз).
Глава У' Решение нелинейных уравнений Итерационные методы вычисления езолароваяного (отделенного от других) корня л уравнения У(я) = О, как правило, требуют указания какой — либо области 11, содержащей этот единственный корень. Широко используемые способы отделения корней — граФический н табличный — базируются на свойствах гладкости функции; в случае, когда у (х) является алгебраическим полиномом степени и, имеются аналитические подходы.
Если Дх) — непрерывна„то вещественный корень з принадлежит людному отрезку, на концах которого, функция имеет значе- $ ния разных знаков. Деля отрезок пополам, получаем универсальный метод вычисления корня (метод бисекцни). Этот подход не требует знания хорошего начального приближения. Если оио имеется, то для гладких функций используются более эффективные методы. Пусть отыскивается единственный на отрезке [а,б] корень г уравнения у(я) = О в предположении непрерывности функции Дз) . Если в его окрестности функция представляется в виде у(х) ' э, = (х — г) од(х), где р — натуральное, а б(х) — ограниченная функция такал, что о(з) ф О, то р называют крашкос1лью корня.
Если р = 1, то корень называют просшььл. При нечетном р функция Дх) меняет знак на [а, Ь[, т.е. Да)у(6) < О, а при четном р — нет. Итерационный метод решення порождает последовательность приближений (х„), которая сходится к корню: Иш [х„— з[ = О. л +СО Величину е„= я„— з называют абсолюшяой ошибкой на и-й итерации. Итерационный метод имеет порядок пь (или скоросшь сходььлосшв пь), если пь есть наибольшее положительное число, для которого существует такая конечная постоянная о > О, что [ео.ы 1 Иш зир ~ — ~ < о < оо.
о-+со ~ е1'1 п Постоянную о называют конставшой асимпшошвческой ошибки, она обычно оценивается через производные функции у (я) в точке х = з. 82 В 18. Метод простой итерации При п1 = 1 (д Е (О, 1)) сходимость назьзвается лвиебкоб (иногдв говорят, что в этом случае метод сходится со скоростью геометрической прогрессии со знаменателем в), при 1 < ш < 2 — сверхеимейивб, при щ = 2 — квадрашичиоб и т.д.
2 18. Метод простой итерации и смежные вопросы Исходное уравнение у(х) = О часто заменяют эквивалентным ему уравнением х = >р(х). Эту замену можно сделать, положив, например, >р(х) = х+ ф(хЩх), где 4>(х) — произвольная непрерывная знакопостоянная функция. Метод простой итерации. Выберем некоторое начальное приближение хв Е [а, Ь) к корню я, а дальнейшие приближения будем вычислять по формулам ха+1 = у(х„)> н = О, 1> 2, Последовательность х„стремится к х, например, когда отображение у = у(х) является сжимающим, т.е. при некотором 0 < >у < 1 выполнено условие р(у(х1),>р(хз)) < вр(хмхз) при всех хмхг. Здесь р(хмхз) — расстояние между х> и хз.
Метод секущих. Пусть х„> и х„— два последовательных приближения к корню. Заменим кривую у = Дх) прямой, проходящей через точки (х„му(х„1)) и (х„,у(х„)). В квчестве следующего приближения к корню возьмем точку пересечения этой прямой с осью абсцисс. Расчетная формула принимает вид х» хи-1 *""=*" Л*)-Л* ) "х"' Метод хорд. Пусть у(аЩ6) < О. Идея метода (его еще называют методом ложного положения) состоит в замене кривой у = = у(х) хордами, проходящими через концы отрезков, в которых У(х) имеет противоположные знаки. Метод хорд требует, чтобы один конец отрезка, нз котором ищется корень, был неподвижен. В качестве неподвижного конца хе выбирают тот конец отрезка, для которого знак у(х) совпадает со знаком второй производной у" (х) .
Расчетная формула имеет вид 1(х») х„+1 = х„ — (х„ — хв). 83 Г л а в а У. Решение яаеняеввых ееяеявй Метод парабол. Пусть х„ых„1 и х„— три последователь.! ных приблнжения к корню. Заменим кривую у = Дх) параболой, проходящей через точки (хе 2~Дхе — э))~ (хе — 11Дхе е)) и (хд1Дхд)), В качестве следующего приближения к корню возьмем ближайшую к х„точку пересечения этой параболы с осью абсцисс. Этот подход исключительно эффективен для нахождения корней многочлена как с действительными, так и с комплексными коэффициентами.
18.1. Пусть уравнение Дх) = О ямеет на отрезке [а,Ь] единственный корень х и для его вычисления используется метод простой итерации. Показать, что если ~р(х) имеет непрерывную производную на [а, Ь] и [ф(х)[ < д < 1 на этом отрезке, то для любого начального приближения хе Е [а,Ь] последовательность (х„) сходится к корша л. 18.2.
Пусть уравнение у(х) = О имеет корень на отрезке [а, Ь], причем у(х) диффереяцируема, а Г'(х) знакопостоянна на этом отрезке. 'требуется построить равносильное уравнение вида х = <р(х), для которого на [а, Ь] выполнено достаточное условие сходимости метода простой итерации [ф(х) [ < а < 1. 18.3. Построить итерационный процесс вычисления всех корней уравнения ~(х) = хе+ Зхэ — 1 = О методом простой итерации.
18.4. Определить областьначальных приближений хе, для которых итерационный процесс хз +1 х„+1 =— сходится. 18.5. Оценить скорость сходимости метода хорд. 18.6. Пусть л — простой корень уравнения У(х) = О. Оценить скорость сходимости метода секущих. 18.7. Доказать, что все корни уравнения Дх) = аех" + а1х" 1+... + а ех+ а„= О расположены в кольце [а„[ с Ь+ [а„] <[л[<1+ —, 84 1 13. Метод простой итерация где Ь = шах(!ада,!а»1, .
!аоО, с= шахЦао~,!ад~,..., 1а„дО. 18.8. Доказать, что если при х = а имеют место неравенства у(а) > О, У'(а) > О,..., у" (а) > О, то уравнение у(х) = аох" + адх" д +... + а„дх + а„= 0 не имеет корней, больших а. 18.9. Найти границы деиствительных корней уравнения х~ — 35 хо + 380»» — 1350х+ 1000 = О. 18.10. Пусть х„ед — — д/х„+2. Доказать, что Иш х„= 2 для о-дао любого хо > 2 18.11. Доказать, что итерационный процесс х„+д — — со» х„схоДитсл Дла любого начального пРиближениЯ хо 5 В.д . 18.12.
Исследовать сходимость метода простой итерации хоед —— = х» — 2х„+ 2 в зависимости от выбора начального приближения хо. 18.13. Уравнение х = 2*, имеющее два корня»д = 1 и»з — — 2, решается методом простой итерации. Исследовать его сходимость в зависимости от выбора начального приближения хо. 18.14. Доказать, что метод простой итерации длл решения уравнения х = др(х) сходится при любом начальном приближении: 1)др(х) =аош х+фсоо +?, где ~а — Д < 1; 2)др(х) =ее ое +с, где Ь> О, 2а~Ь < е.
18.15. Уравнение х + 1п х = О, имеющее корень» ш 0.6, предлагается решать одни ю методов простой итерации: 1)х„+д = -1пх„; 2)х„+д =е '"; х„+е *" Зх„+ 5е '" З)х„+д = " , .4)х„+д —— 2 ' 8 Исследовать эти методы и сделать выводы о целесообразности использования каждого ю них. 18.16. Пусть др(х) Е Сддд[» — б,»+ б], где» вЂ” единственная неподвижная точка для др(х).
Может лн метод простой итерации сходиться к», если ~ф(»)~ = 1? Может ли он расходиться в этом случае? 18.1Т. Выяснить, существует ли для всякого а единственное решение», уравнения х+ е ошх+ а = 0 при ф < 1. 85 Г л з в з К Решение яеляяеянмх уравнений 18.18. Найти область сходимости метода простой итерации для следующих уравнений: 1 1)х = ее* — 1; 2)х+ 1пх = —; 3)х = сбх.
! 18.19. Выписать расчетные формулы метода парабол. 18.20. Методом парабол найти корни уравнения 2х + 18 х = -0.5 с точностью 10 з. 18.21. Оценить скорость сходимости метода парабол. 18.22. Оценить скорость сходимости метода секущих в случае гп-кратного корня. 18.23.
Пусть отображение ~р: К" -~ К" имеет единственную неподвижную точку г = у(г) и непрерывно дифференцируемо в некоторой ее окрестности. 1) Доказать, что если все собственные значения его лкобиана у'(х) в точке л по модулю больше 1, то метод простой итерации расходится. 2) Из1юстно, что хотя бы одно собственное значение якобиана у'(г) по модулю больше 1. Может ли метод простой итерации сходиться для всех приближений хе, достаточно близких к гу 19. Метод Ньютона. Итерации высшего порядка Метод Ньютона. В случае одного уравнения формула метода Ньютона имеет вид ~(х„) х„+1 = х„— —, Пхв) Метод состоит в замене дуги кривой у = У(х) на касательную к ней в процессе каждой итерации. Это видно из уравнения касательной, проведенной в точке (х„, ~(х„)): у — у(х„) = ~'(х„)(х — х„), из которого формула итерационного процесса следует, если положить у =0 и х =х„+1.
Рассмотрим более общий случай — системы т нелинейных уравнений У(х) = О, 86 1 19. Метод Ньютона где х = (хы,х, )т, р = (Л,...,у,„)т. Будем предполагать отображение Р: К ~ К'" непрерывно дифференцируемым в некоторой окрестности решения и, так что Р'(х) = В предположении обратимости этого оператора метод Ньютона можно записать в виде х„+» = х„— (Р'(х„)) 'Р(хн).
Обозначим Й, = (х: Ох — в~! < а). Пусть при некоторых а,аыаг 0 < а, 0 < аы аз < оо, выполнены условия: 1) ц(Г'(х)) ц < а» при х е Й„; 2) ~~й'(и») — Р(пг) — е(п»)(п» вЂ” пз)ц < азцп» вЂ” пзц~ при пыпз Е Й,. Обозначим также с = а»аз, 6 = ппп (а, с») Д ~~ — евклидова норма в Н.ю. Теорема ~о сходимос1пи меп»ода Ньютона). При услооилх 1), 2) и хо Е Йь ип»ерационныб процесс Ньютона сходится с оценкой погрешносп»и Ох„— в0 < с» (с8хе — в~~) Метод ньебышева построения итераций высплего порядка. Пусть г — корень уравнения У(х) = 0 и г (у) — обратная к У(х) функция.
Тогда х и тих)) и х = Е(0). Разложим Р(0) в ряд Тейлора в окрестности некоторой произвольной точки у: х = Е(0) = г (у) + ~~~ Ф ~(у) —, + .. (-у)' ййа Положим е = ~р„(х) = х+ ~ Ц(-1)"йЦ'~(У(х)) — ', Щх))» ййа Итерационный процесс ху+» = »о (х ) имеет порядок сходимости и»+1. 19.1. Построить итерационный процесс Ньютона для вычисления 4/а, а > О, где р — вещественное число. 87 Г л в в а Ч Решение нелинейных авневвй 19 л Пусть уравнение у(х) имеет на отрезке [а, Ь] простой корень~ причем у (х) — трижды дифференцируемая функция.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
