Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 21
Текст из файла (страница 21)
Если х<"' Е (х — о, х + о), то ~ <г< "+)) ~ < д в силу условия (4.18). Тогда на основании равенства (4.20) получаем ~ х< и+1) х ~ < у ~ х< и) ние х, входящее в правую часть оценки, неизвестно, Кроме того, 96 Это означает, что метод простой итерации обладает линейной скоростью сходимости и поэтому доказательство теоремы завершается применением леммы 4.1. ° Оценка погрешности (4.19) является априорной. Она показывает, что метод простой итерации сходится со скоростью геометрической прогрессии, знаменатель которой равен д.
Чем меньше у, тем выше сокрость сходимости. Видна и роль правильного выбора начального приближения: чем меньше погрешность начального приближения, тем меньше итераций потребуется сделать для достижения заданной точности я. Неравенство (4.19), как правило, не используется для практической оценки погрешности. Одна из причин этого состоит в том, что значе- использование неравенства (4.19) приводит к существенно завышенной оценке погрешности. 4. Критерий окончания.
Выведем апостериорную оценку погрешности, пригодную для практического применения. Т е о р е и а 4.3. Пуспгь выполнены условия теорелхы 4.2 и х(в) б Е (х — в, х + о). Тогда верна следуюгцая апостериорная оценка похреиг- ности: )х(п) — х[ ~ ~— ~х("' — х'" ') ~, и 1 1. 1 — 9 (4.21) а В силу равенства (4.20) имеем х( п) х — (г( и) (х( и-1) х) — сх( п) (х( п-1) х( п) ),» (х( п) (х( п) х) Отсюда хг( и) х( п) о( п) Взяв модуль от левой (Х("1) - Х(п) ).
. (4.22) и правой частей этого равенства и воспользовав(г( и) , получим требуемое соотно(г( п) 1 — д' шись неравенством шение (4.21). ° Если величина д известна, то неравенство (4.21) дает эффективный метод контроля погрешности и можно сформулировать следующий критерий окончания итерационного процесса. Вычисления следует вести до выполнения неравенства Ч ~ х' "' — х( п " ~ ( е или 1- д равносильного ему неравенства )х(и) -х("" ~ < — е. (4.23) Ч Если это условие выполнено, то можно считать, что х'п) является приближением к х с точностью е.
Пример 4.5. Используем метод простой итерации для вычисления положи— Преобразуем уравнение к виду (4.15), где (р(х) = )('1 — ех/4. Заметим, что Р ( ) = ~ ((8Д вЂ” И/4), у'( ) = -е*(1 — (8)((8!)! — е /4)!. Т Р < 0 на [а, Ь], то производная !р' монотонно убывает и д = птах ~хр'(х)) = [а, Ь] = (о'(Ь) )!) 0.37.
Следовательно, условие сходимости (4.18) выполнено. Возьмем = 0.7 и будем вести итерации до выполнения критерия (4.23). В табл. 4.3 соответствующие приближения приведены с 10 знаками мантиссы. 4-28 97 тельного корня х уравнения 4(1 — хг) — ех = 0 с точностью е = 10 4. Резуль— тат примера 4.4 дает для корня отрезок локализации [а, 6] = [0.70, 0.72].
Таблица 43 ~х(и) х(и-)) ~ 1-д х( и) 0.7000000000 0.7046714292 0.7029968319 0.7035984939 0.7033824994 0.7034600632 3. 10-3 1. 10-з 4 104 2-10 4 5.10 ~ Критерий окончания выполняется при а = 5. После округления значе- ния х'5' до четырех значащих цифр получим х = 0.7035 + 0.0001. 3 а м е ч а н и е. Часто в практике вычислений вместо критерия (4.23) используется привлекательный своей простотой критерий (4.24) ~х(и) х<и-<) ~ < Е В случае 0 ( 9 ч 1/2 использование критерия (4.24) оправдано. Действительно, здесь (1 — 9)/9 ~ 1 и поэтому выполнение неравенства (4.24) влечет за собой выполнение неравенства (4.23).
В то же время в случае 1/2<9<1 использование критерия (4.24) может привести к преждевременному прекращению итераций. Дело в том, что когда величина 4 близка к единице, итерационный процесс сходится медленно и расстояние между двумя последовательными приближениями х(и) и х<" () не характеризует рассто- яния от х<") до решения х (рис. 4.8). Рис.
~.8 Пример 4.6. Пусть метод простой итерации используется для решения 10-4 уравнения х = 0.9999х + 10 '/т<2. Здесь у(х) = 0.9999х + †, у '(() = 0.9999 ~~2 и, следовательно, условие (4.18) сходимости метода выполнено. Для вычислений по формуле (4.16) используем 6-разрядную десятичную ЭВМ. Возьмем х<о) = 0.715010. Тогда х')) = 0.715009 и, если доверять критерию (4.24), то следовало бы считать, что решение получено с точностью е = 10 е. Продолжая 98 вычисления, получим х(2' = 0.715008, х" з' = 0.715007, х'в) = 0.715006, х(ь) = 0.715005, х'е) = 0.715005.
Дальнейшие итерации теряют смысл. Сколько же верных знаков найдено? Сравнение с точным значением решения 1 х — — — = 0.707106... показывает, что верными в приближении х(е) являются ~/2 только две значащие цифры. Ислользование критерия (4.24) в данном случае категорически недопустимо. Б дальнейшем мы еще вернемся к обсуждению этого примера. Использование критерия (4.23) предполагает знание величины входящей в условие (4.18). Однако далеко не всегда эта величина известна, либо может быть легко вычислена. В тех же случаях, когда удается оценить в, эта оценка оказывается довольно грубой. Исключим из критерия окончания итераций величину в. Заметим, что в малой окрестности корня величина производной (в практически постоянна: ц)'(х) )( (р'(х). Поэтому в равенстве (4.22) величину а(и) = (р'Я(и ") можно приближенно заменить на (о'(х).
Далее в силу равенства х( и) х( и-1) — (р(х( и-1) ) (р(х( и-2) ). — (р (~[ и) )(х( и-1) х( и-2) ) н Ю где С(и) — пРомежуточная междУ х("1) и х'и 2) тОчка, имЕЕМ С)(и) = (х'и) — х(и 1))/(х(и(' — х(и 2) ) = гр'(~(и) ) н гр'(х). Таким образом, в равенстве (4.22) можно положить а(и' и а(и) и поэтому при определенных условиях можно использовать следующий практический критерий окончания итерационного процесса: м (1( и) ) Х( и) Х( и-1) ) ~Ч с,( и) 5.
Дополн.нтельные сведения о характере сходимости В случае, когда производная р знакопостоянна на отрезке локализации, итерационная последовательность обладает некоторыми полезными допол- нительными свойствами. Заметим, что при (() (х) Ф О в достаточно малой окрестности корня знак производной (р'(х) действительно постоянен. Т е о р е и а 4.4. Пусть ))а, о1 — отрезок локализации корня уравнения (4.15). Предположим, что на этом отрезке функция (в непрерывно дифференцируема, а ее производная (р'(х) знакопостоянна и удовлетворяет неравенству (4.18) при 0 < в ( 1.
Пусть х(о) Е [а, 5] — произ- 99 вольное начальное приближение и в случае ~р' < 0 выполнено дополнительное условие х<ы = <о(х<о>) ч (а, 6~ (первое приближение не выходит за пределы отрезка локализации). То<да итерационная последовательность не выходит эа пределы отрезка (а, 6], л<етод простой итерации сходится и верны оценки по<решности (4.19), (4.21). Кроле то<о, справедливы следующие свойства: 1о.
Если у' ) 0 на <а, 6~, то х'"' сходится к х, л<онотонно воэрас— тая в случае а ( х<о> < х, и л<онотонно убывая в случае х < х<о< ч 6. 2в. Если <р' < 0 на [а, 6~, то сходил<ость х<п> к х носит колебательный харакитер, т. е. при всех и ~ 0 значения х< и> и х<п+ы расположены по разные стороны от х, причел< последовательности приближений с четныл<и и нечетнь<л<и нол<ерал<и сходятся к х л<онотонно.
В этол случае верна апостериорная оценка по<решности <х<п< х< ( <х<п< х< -1) ~ и) 1 (4.25) и справедлив критерий (4.24) окончания итерационно<о процесса. Мы не будем приводить здесь полное доказательство теоремы. Оно основано на использовании равенства (4.20), установленного при доказательстве теоремы 4.2. Докажем только справедливость свойств 1о и 2о. и Если О «р' ( о, то знаки величин х< "' — х и х' " <> — х совпадают, в то время как ~х< "< — х~ ( д~х<п '~ — х~. Следовательно, последо- вательность монотонно приближается к х с той стороны, где лежит х<о', Если же — о «<э' < О, то из равенства (4.20) следует, что знаки величин х'"' — х и х'" <> — х различны.
Это подтверждает колеба- тельный характер сходимости. И Э а м е ч а н и е. Монотонный и колебательный характер сходимости итерационной последовательности, указанные в теореме 4.4, иллюстрируют соответственно рис. 4.7, и и 4.7, б. 6. Приведение уравнения к виду, удобному для итераций. Ключевой момент в применении метода простой итерации — эквивалентное преобразование уравнения (4.1) к виду (4.15). Конечно, такое преобразование имеет смысл только тогда, когда оказывается выполненным условие (4.18) при 0 < д < 1. Укажем один из простых способов такого преобразования.
100 Предположим, что производная / на отрезке [а, 6] непрерывна и положительна. Тогда существуют положительные постоянные тп и М такие, что О < т ( /'(х) < М, х Е [а, Ь]. Приведем уравнение (4.1) к виду х = х- а7'(х), (4.26) где а > О. В этом случае итерационная функция у имеет вид фх) = = х — а/(х).
Как выбрать а, чтобы выполнялось условие (4.18), причем у было бы по возможности минимальным7 Заметим, что 1 — иМ ~~ р'(х) = 1 — аф'(х) < 1 — агп и поэтому )~р'(х) [ ~ д (а) = гпах (]1 — аМ], ]1 — ат]1. Для того чтобы было выполнено неравенство о(а) < 1, достаточно взять любое а е (О, 2/М). Конкретный выбор параметра а зависит от наличия информации о числах т и М. Если известны обе эти величины, то лучшим является выбор а = ао — — 2/(М+ тп).
В этом случае 4(ао) = (М вЂ” тп)/(М+ т). 1 Если же известно только М, то можно положить а = а~ = — В этом случае о (а~) = 1 — — Кроме того, при а = а~ производная ~р'(х) неот- рицательна, и в силу теоремы 4.3 сходимость является монотонной. 3 а м е ч а н и е. Случай, когда производная /' отрицательна, сводится к рассмотренному выше умножением уравнения /(х) = О на — 1. х с [0.70, 0.72];, пы оценки 0 < и = /'(0.70) ~ (~'(х) ~ </;(0.72) = М Выберем 2 в уравнении (4.26) а = , возьмем х'о~ = 0.7 и будем вести итерации т + М х(п) по формуле х' "+ы = х' "' — о[е — 4(1 — х' ~~)т]. Выбранному а соответ- М вЂ” т ствует д— 0.013 и поэтому сходимость должна быть более быстрой, М + т чем в примере 4.6. Действительно, уже первая итерация дает х' ~ > Д = 0.7034025118, и так как ]х~ "~ — х'о~ ) я 5 10 5, то итерации следует 1 — д прекратить и считать х = 0.7034 х 0.0001.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
