II Иванова Е.Е Дифференциальное исчисление функций одного переменного (1081372), страница 46
Текст из файла (страница 46)
РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИИ отпрезнов [1, 1.3] [ао, 6о] Э [а1, 61] ) ... ) [а„, 6„] 3 ..., п Е г1, ~х„— х'~ ( С~х„1 — х'~", (11.12) то говорят, что метод имеет в 11(х ) сходимость порядка р (число р называют пор.адком сходимосши метпода). При р= 1 и 0(С( 1 метод в 0(х') обладает линейной скоростпьто сходимостпи, а при р > 1 — сверхлинейной на которых удерживают локализованный корень, а методы второй — итерационной последоватпельностпи (х„) приближений к значению х . В первой группе отличие одного метода от другого состоит в том, каким образом выбирают на п-й итерации точку х„б (а„, 6„), которая станет одним из концов отрезка [а +1, 6 +1] С [а, 6„].
К таким методам принадлежат способ деления отрезка пополам (его иногда называют методом бисекции) и метод хорд (метпод пропорциональных частией или линебного интперполированил) [1, 9.6]. Если точку х„рассматривать как приближенное значение корня х', то исследование методов из обеих групп можно свести к анализу итерационной последовательности (х„~. Условием работоспособности любого из методов является его сходимостпь к искомому значению х', т.е. последовательность (х„) должна быть сходящейся, причем аппп(х„) = х .
Метвод называют одношаговым, если х„вычисляют лишь по значению х„1, и многошаговым — в противном случае (в частности, Й-шаговым, если при вычислении х„используют й значений х„т„х„т,+1, ..., х„1). Ясно, что при наличии одного приближенного значения хо корня х можно начать его уточнять лишь при помощи одношагового метода. Если в некоторой окрестности У(х') корня х при постоянных С > 0 и р > 1 для одношагового метода справедлива оценка 371 11.5.
Численные методы уточнения значения корня скоростпью сходимостпи (в частности, при р=2 и 3— квадратиичной и кубическоЯ. Теорема 11.3. Если одношаговый метод обладает в некоторой окрестности У(х ) корня х' линейной сходимостью, то ~х„— х'~ < д"~хо — х'~ Ухо Е 0(х'), О < д < 1. (11.13) ~х~, 1 — х ~~<ф ~хо — х Тогда с учетом (11.12) ~хауз Х ~ ~(Я~хт 1 Х ~ ~<Я ~ХО Х ~) т.е. (11.13) справедливо и при п = т.
~ Таким образом, линейная скорость сходимости метода приводит к уменьшению начальной погрешности ~хо — х'~ по итерациям в геометрической прогрессии со знаменателем д < 1. Если в методе бисекции (методе деления отрезка пополам) принять хо=(ао+Ьо)/2 и х„=(а„+Ь„)/2, то Ь~ — а Ьо — ао 1 Ьо — ао 1 т.е. метод имеет скорость сходимости геометрической прогрессии со знаменателем д = 1/2 (например, для сокращения начального отрезка локализации в 10~ раз нужно 19 итераций). Если для Й-шагового метода верно (11.12), то справедлива следующая теорема. 24' < При и =0 неравенство (11.13) очевидно, а при а=1 оно верно в силу (11.12), если обозначить д =С и учесть, что р = 1.
Применим метод математической индукции. Пусть (11.13) верно при а = т — 1: 11. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ 372 Теорема 11.4. Пусть в некоторой б-окрестности 0(х', 6) корня х' Й-шаговый метод имеет порядок сходимости р. Тогда при Сб~ 1 < 1 (С вЂ” постоянная иэ (11.12)) ~х„— х'~ < С Р-' ~хо — х"~Р Ухо ~ 0(х', Ю) (11.14) и итерационная последовательность (х„) не выходит за пре- делы У(х, о). ~ При а = О неравенство (П.14) очевидно, а при а = 1 оно верно в силу (11.12).
Применим метод математической индукции. Пусть (11.14) верно при п,=т — 1: т-1 ~х„, 1 — х'~ <С 1-1 ~хо — х'~" Тогда с учетом (11.12) получим ~х„, — х'~ < С~х,„1 — х'~~ < т;1 < С С Р-1 хо — х' Р тв =СР 1 хо — х т.е.
(11.14) справедливо и при я = т. Поскольку ~хо — х'~ < Б и С11Ь 11<1/о, иэ (11.14) имеем ~х„-х'~<(1/о)Ь 1)У =о. ~ Примем, что при численном решении (11 ° 1) входными данными являются значения функции Дх), вычисляемые с некоторой абсолютной погрешностью, не превышающей Ьу.
Эта погрешность может быть вызвана как ошибками округления, так и использованием для вычисления ~(х) приближенных способов. На рис. 11.2 вычисляемые значения Дх) расположены в некотором ограниченном штриховыми линиями „коридоре" шириной 2Ьу в направлении оси ординат. Ясно, что в малой окрестности искомого корня х' иэ-за малости Щх)~ предельная относительная погрешность 8у = Ьу/~~(х)~ возрастает по мере приближения х к х'. 373 П.Б. Чисаенные методы уточнениа знечениа кориа Рис. 11.2 Для непрерывной функции Дх) найдется такая е-окрестность 0(х', е) корня х' (см. рис.
11.2), что Чх Е 0(х', е) Щх) ! < Ьу. В этой окрестности знак Дх) недостоверен и невозможно указать определенное значение х, при котором вычисленное значение ~(х) обращается в нуль. Такую окрестность называют интпервалом неопредеяенностпи корэив х'. Пусть х' — корень кратности яг (для простого корня т = 1). Тогда, согласно формуле Тейлора, откуда у(тв)( «~ Чх Е 0(х~, я) ' !х — х'! Щх)! < Ьу, т.е. радиус интервала неопределенности корня х' д 1/ш '!У( )(х )! Для простого корня (11.15) 374 П. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ ~х~ — х 1~ — Чи ~х„1 — х„~~ от итерации к итерации и д„> 1 говорит обычно о попадании х в интервал неопределенности (при х ~ У(х', е) для сходящегося метода д„< 1).
Правило, использующее условие д„> 1 для контроля попадания в интервал неопределенности, называют иравилом Гарвияа. 11.6. Метод простой итерации Есии (11.1) эквивалентным преобразованием привести к виду (11.16) х = у(х), 4 то, начиная с нулевого приближения хо к корню х', можно построить итперационную последовательностпь (х„) с элемен- тами х1 — у(хо) х2 — (р(х1) ° ° ° х — (р(х -1) ° ° ° и б х.
где 1Я'(х') ~ характеризует чувствительность решения задачи к погрешностям исходных данных, называемую о6условлеккоствью задачи или метода ее решения. Если эта чувствительность мала, то задачу или метод ее решения считают хорошо обусловленными, а если велика, то — плохо обусловленными. Значение 1Я'(х )~ в (11.15) называют а6солютвкым числом обусловленностии.
При численном решении (11.1) оценить значение е не всегда возможно, но ясно, что е не меньше абсолютной погрешности Ь вычисления значений х и представления корня х' в ЭВМ. Не имеет смысла задавать точность решения (11.1) меньше е. Более того, нельзя требовать от численного метода достоверных результатов при х Е 0(х', е). Немонотонное изменение отношения 375 11,6. Метод простой ытерацмы При существовании конечного предела х' этой последовательности и непрерывности функции ~р(х) х' = у(х'), т.е.
х'— корень (11.16), а значит, и корень (11.1). Итак, существо методе простпой ипзераа~ии состоит в построении сходящейся последовательности (х„~ и выборе некоторого ее элемента в качестве приближенного значения искомого корня х'. Ясно, что этот метод является одношаговым. Рис. 11.3 Геометрически корень х' является абсциссой точки пересечения графикафункции ~р(х) и биссектрисы у=х (рис. 11.3). 377 11.6.
Метод дростом итерации Но значение д не всегда легко оценить достоверно. Вместо (11,17) запишем хя х =(Р (4и-1)(хв-1-х ) — Ф ®в-1)(хп-1 — хт~+хя х ) (11.19) Отсюда (11.20) Кроме того, х„ — х„ ~ = ~р(х„ ~) — фх„ ~) = ~р'(~;)(х„ ~ — х„ р), где ~ лежит между х„~ и х„г. Для простого корня в его малой окрестности значение ф(х) изменяется мало и можно принять Тогда вместо (11.20) получим ю'(О ( — — )' х„— х' ~, (х„~ — х„) = 1 — ф(~) х„— 2х„-1+ х~-г и условие окончания итераций будет иметь вид или !х„— х„-д < !хе — 2х„~ + х„з!8.
Если задана точность 8 вычисления значения х', то из (11.18) и неравенства !х„— х'! ( е следует, что в качестве х можно взять значение х„при условии П. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИИ 378 Если при выполнении условий теоремы 11.5 Чх б 0(х') у'(х) > О, то из (11.19) следует О« 1, хть-1 х' — х„ -1«, "О, х хи-1 т.е. знак разности х' — х„при итерациях чередуется, так что !х„— х"! < !х„— х„1!/2 (см. рис.
11.3, б). Это означает, что все совпадающие у значений х„и х„1 десятичные знаки верны для значения х'. Тот же вывод справедлив и при О «р'(х) < 1/2 Чх Е 0(х'), что следует из (11.18) при д < 1/2. Если на какой-либо итерации допущена ошибка, которая не вывела итерационную последовательность за пределы отрезка !а, 6], то последующие итерации будут по-прежнему сходиться к искомому корню х', а влияние допущенной ошибки будет постепенно затухать. Однако погрешности вычисления функции у(х) и ошибки округления могут возникать на каждой итерации.
Оценку их влияния проведем на основе (11.15), приняв в (11.1) Дх) = х — у(х). Тогда для простого корня радиус интервала неопределенности так как абсолютные погрешности вычисления функций Дх) и ~р(х) в данном случае одинаковы, т.е. Ьу = Ь, . Если ~р'(х') ж 1, то метод простой итерации плохо обусловлен, количество верных цифр корня х' будет на ~-1~(1 — ф(х'))] (~г] означает целую часть — „антье" от х 11, 3.2]) меньше количества верных цифр в вычисляемых значениях ~р(х), а касательная к графику т.е. последовательность (х„) строго монотонна (возрастающая при хо < х' и убывающая при хо > х') (см.
рис. 11.3,а), а если Чх Е %3(х') ср'(х) < О, то 379 11.6. Метод просхой итерацми у(х) =х — —, ЛфО. Дх) (11.21) При подборе необходимо учитывать условия теоремы 11.5, т.е. в некоторой е-окрестности У(х ) искомого корня х' потребовать, чтобы (11.22) Если на этапе отделения корня х' установлен отрезок локализации [а, 6] этого корня, то за нулевое приближение можно взять хо — — (а+ 6)/2. Поскольку расположение х' на [а, 6] не известно, замена в (11.22) 0(х') на [а, 6] может привести при — 1 «р'(х) < О к тому, что х1 — — <р(хо) ф [а, 6], а итерационная последовательность выйдет за пределы отрезка локализации.
Чтобы этого не произошло, достаточно монотонности итерационной последовательности (х„) на [а, 6], т.е. замены (11.22) на условие 0«р'(х) =1 — < д< 1 Чх б [а, 6]. ~'(х) (11.23) Пусть на отрезке [а, 6] производная ~'(х) непрерывна и положительна. В силу теоремы 9.5 [1] она принимает на [а, 6] наибольшее М и наименьшее т значения. Тогда из (11.23) следует условие О < 1 — — < 1 — — < 1. М т Л Л Отсюдапри Л=М у=1 — т/М.
Однакопри т/М«1 такой выбор Л не выгоден из-за возможной близости <р'(х ) к 1 и функции <р(х) в точке х' почти совпадет с биссектрисой у = = х (см. рис. 11.3, а). В случае — 1 < ф(х') < О (см. рис. 11.3, б) обусловленность метода улучшается и потери верных цифр не происходит. Один из несложных способов эквивалентного преобразования (11.1) к виду (11.16) состоит в подборе параметра Л в выражении 380 11. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИИ связанной сэтим медленной сходимости (х„) и плохойобусловленности метода. Ситуацию можно несколько улучшить, если в (11.22) вместо 1.) (х') взять отрезок [а, ~3], где а = (За — Ь) /2 и Р = (Зо — а)/2, при условии, что он локализует тот же единственный корень х'. Тогда х1 — — 4р(хо) е [а, Я и итерационная последовательность не выйдет за пределы [а, )3], а из (11.22) следует условие -1< 1 — — < 4р(х) < 1 — — < 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
