Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 22
Текст из файла (страница 22)
101 Пример 4.7. Для решения задачи, поставленной в примере 4.5, можно воспользоваться преобразованием уравнения (4.4) к виду (4.26). Будем считать известным, что х е [0.70, 0.72]. Так как на отрезке локализации выполнено условие (4(1 — ~~) — ех) = -8х — ех < О, то перепишем уравнение в виде л(х) = О, г.; /;~х) = ех — 4(1 — хз), Тогда ~'(х) = ех + 8х и для $4.5.
Обусловленность метода простой итерации В ~ 4.4 метод простой итерации был рассмотрен при идеальном предположении о возможности точного вычисления значений функции 1о(х). В действительности же вычисления на ЭВМ дают приближенные значания у'(х). 'Поэтому вместо последовательности х)"), удовлетворяющей равенству х' "') ' = у(х' а) ), получается последовательность х) "', для которой н Ч х( и+1) —,о «(х( а) ) (4.27) диться к решению х, а внесенная ошибка — затухать. Поэтому о таких итерационных методах говорят, что они обладают свойспгвол салоиса- 1)авляел)ости. Однако погрешности допускаются не на одной, а на всех итерациях и совокупное их влияние несколько иное. 1.
Обусловленность задачи. Прежде чем сформулировать результат о поведении метода простой итерации при наличии погрешности в вычислении функции у, отметим, что преобразование уравнения )" (х) = О к виду х = 1о(х) изменяет обусловленность задачи. Запишем это уравнение в виде ~ (х) = О, где )' (х) = х — фх), и воспользуемся результатами З 4.2. Заметим, что Ь(~*) = Ь(у*), поскольку в действи— тельности приближенно вычисляется только, функция 1о. Поэтому оценка (4.11) в данном случае выглядит так: Ь(х*) < иЬ(р*). (4.28) Здесь и = 1/~1 — у'(х) ) — абсолютное число обусловленности корня х.
Грубо оценивая при выполнении условия ~ р'~ < в < 1 величину и — 1 числом и = , приходим к оценке 1 — д' (4.29) Известно, что метод простой итерации и многие другие итерационные методы устойчивы к ошибке, допущенной на одной из итераций. Такая ошибка эквивалентна некоторому ухудшению очередного приближения; если она не вывела приближение за пределы области сходи- мости, то итерационная последовательность по-прежнему будет схо- В случае, когда р ~ ~О или р ~в О, ее можно уточнить. Действительно, как нетрудно установить, и ( 1, если 1о ' ( О; следовательно, ~ (х*) < ~ (р*). (4.30) Заметим, что в оценках (4.28) — (4.30) величины Ь (х*) и Ь (р*) можно заменить на о(х*) и о(у*).
Чтобы убедиться в этом, достаточно разделить левую и правую части оценок на величины )х) и ~р(х)~, которые равны между собой. Например, оценка (4.28) преобразуется к виду о( х ') < и6(~р ') (4.31) и, следовательно, абсолютное и относительное числа обусловленности здесь совпадают. Сделаем некоторые выводы. Задача вычисления корня х уравнения х = р(х) плохо обусловлена, если 1о '(х) м 1.
В этом случае сле- дует ожидать, что количество верных цифр корня х по сравнению с количеством верных цифр в вычисляемых значения у*(х) должно быть меньше примерно на У = 18 и цифр. Для радиуса интервала неопреде- ленности е м иЛ(р*) корня х в случае ~ 1о'~ ~ 9 < 1 справедлива оцен- — — ~(р ) ка е ( е* = — —, В случае, когда — 1 ( р' < О, уточненная оценка 1 — д' таксва: е < е * = Ь(р*); здесь потери верных цифр быть не должно. 2.
Чувствительность метода простых итераций к погрешности вы— числений. Сформулируем основной результат данного параграфа. Т е о р е и а 4.5. Пусть выполнены условия теоремы 4.2 и для всех х Е (х — о, х + о) имеет место неравенство ~ р(х) — р(х*) ~ ( Л(р'). 109 Пример 4.9.
Для уравнения х = фх) при фх) = 0.9999х + 10 4/~/2 имеем ~р'(х) = 0.9999 и, следовательно, и = 10~. Поэтому при решении этого уравнения методом простой итерации на ЭВМ будет потеряно примерно четыре значащих цифры. Вычисления на 6-разрядной десятичной ЭВМ (или на близкой ей по точности ЭВМ типа 1ВМ РС) могут дать в таком случае всего лишь две верные значащие цифры.
Это вполне согласуется с результатом, полученным в примере 4.6. ж(р*) Предположил) также, что е = «т (т. е. величина Ь(1о*) 1 — о достаточно лала). Если вычисления по форл)улал) (4.1б) и (4.27) начинаются с одного начального приближения х' а) = х) о) Е (х — о), х + о)) ()де о") о — е = ппп 1о, ), то последооап)ельность х<п) не оыходит за преде- Я лы о-окрестности корня х и для всех п ~ ~1 справедливы следующие оценки по)реи)ности: Здесь С = —. Я 1 — о 3 а м е ч а н и е 1. В случае р' < О в неравенствах (4.32) — (4.34) можно положить е* и) Ь(р*), С п 1. 3 а м е ч а н и е 2. При достаточно больших и в оценках (4.32)— (4.34) величину е* можно считать приближенно равной радиусу и Докажем по индукции, что для всех п > О справедливы неравенства (4.32), (4.33) и х< и) Е (х — о, х + о).
Очевидно, что при п = О это верно. Предположим, что доказываемое утверждение справедливо при некотором п ~ О. Вычитая из равенства (4.27) равенство (4.16), получа- ем х< и+)) х) и+1) — )р'(~) и) )(х(п) х(п) ) + ~(и) ~(п) Е (х о х + о) и М где Ь) п) = р*(х) п)) — )р(х'п) ) ~Ь'п) ~ ч Ь(~р*). Как следствие полученного равенства и сделанных предположений, имеем (х<п+)) — х(п+1) ~ ~~ д~х)п) — х)п) ~ + ~Д)и) ~ ~ ~)1е + ~()р ) = я 104 )х)и) х<п) ~ <~» ~х)и) х~ ~ цп~х<о) — х~ + Е* /х)п) х~ ~ ~С!х)п) х~и-)) ~ +6» ~(р*) интервала неопределенности ~ = 1 — р '(х) (4.32) (4.33) (4.34) Объединяя эту оценку с оценкой (4.19), получаем ~ х < "'ы — х ~ ~ д"' ) х~ е> — х ~ + е *.
Поэтому ~г'"'ы — т~ ( да~ + е* ~~ + е* = о. Д Нужное утверждение доказано для номера, равного п + 1, а следовательно, и для всех п Ъ О. Вычитая. из равенства (4.27) равенство (4.17), получаем ~( ~+1) ~ — о( Ы (г( ~~) г) 1 ~ ( ~~) о( ~) — <р (~( ~) ) ~с ~) Е (х — о г+ ст). Таким образом, и о(п) н Л < п> х< "+ы — ~ = (х< "> — х~ "+'~) + 1 — а~"' 1 — а< "> Из полученного равенства вытекает оценка (4.34).9 Итак, итерационный процесс не ухудшает обусловленность корня х. Как оказывается, гарантированная точность метода простой итерации ограничена снизу величиной, примерно совпадающей с радиусом е интервала неопределенности. Критерий (4.23) окончания итераций применим, если е * < е.
Входящую в соотношения (4.29), (4.30) величину Ь(~о*) в общем случае оценить сверху достаточно сложно. Оценка снизу очевидна: Ь(у*) ) ~х~е . В благоприятной ситуации, когда вычисления ведутся по простым формулам, можно надеяться на то, что Ь(р*) окажется величиной порядка ~ х~ е~. 3 4.6. Метод Ньютона Знаменитый метод Ньютона является одним из наиболее эффектив— ных методов решения самых разных нелинейных задач. Расчетную формулу метода можно получить, используя различные подходы.
Рассмотрим два из них. 105 1. Метод касательных. Выведем расчетную формулу метода для решения нелинейного уравнения (4.1) из простых геометрических соображений. Соответствующая иллюстрация приведена на рис. 4.9. Пусть х~о' — заданное начальное приближение к корню х. В точке М' ® с координатами (х< о', ~ (х~ о~ )) проведем касательную к графику функции у = ~(х) и за новое приближение х ~ 1' примем абсциссу точки пересечения этой Рис. 4.9 касательной с осью Ох. Аналогично, за приближение х'2~ примем абсциссу точки пересечения с осью Ох касательной, проведенной к графику в точке М'~' с координатами (х~", ~(х".~)).
Продолжая этот процесс далее, получим последователь- ность х'®, х'Ы, х<2>, ..., х~ а', ... приближений к корню х, Напомним, что уравнение касательной, проведенной к графику функции у = ~(х) в точке (х'"', ~(х<"')), имеет вид у ~ ( х ( а ) ) + ~ ( х ( ~ ~ ) ( х х ~ а ) ) (4.35) Полагая в равенстве (4.35) у = О, замечаем, что при выполнении усло- вия ~'(х'"') 1 О абсцисса х< "+ы точки пересечения касательной с осью Ох удовлетворяет равенству О = У(х<и>)+ У'(х(т)(х<п~~> х~т) (4.36) Выражая из него х' "", получаем расчетную формулу метода Ньюто- на: (4.37) Благодаря такой геометрической интерпретации этот метод часто называют нетодом касательных.
2. Метод линеаризации. С более общих позиций метод Ньютона можно рассматривать как итерационный метод, использующий специальную линеаризацию задачи и позволяющий свести решение исход— ного нелинейного уравнения к решению последовательности линейных уравнений. 106 Пусть приближение х) ") уже получено. Представим функцию в окрестности точки х)и) по формуле Тейлора: ~(х) — ~(х(и) ) + ~'(хг и) )(х х( и) ) + (х х! и) )2 Г(0 2 (4.38) (4.39) г'(хг и) ) + г'(х( и) )(х х) и) ) — О Принимая решение уравнения (4.39) за новое приближение х<и')), приходим к формуле (4.37). 3. Основная теорема о сходимости метода Ньютона. Т е о р е и а 4.6. Пусть х — простой корень уравнения ~(х) = О, в некоторой окрестности которого функция ~ дважды непрерывно дифференцируема. Тогда найдется такая малая и-окрестность корня х, что при произвольном выборе начального приближения хго) иэ этой окрестности итерационная последовательность метода Ньютона не выходит эа пределы окрестности и справедлива оценка х) и'» — х) ~ С~ х) и) — х~ г, п 1 О (4,4О) где С = о ', оэначаюгцая, что метод сходится с квадратичной скоростью.
Следствием оценки (4.40) является априорная оценка ~ х~ ") - х~ ~ ~одг, и ~ ~О, (4.41) в которой )) = о) ~х'о) — х~. а Так как ~'(х) х О (по определению простого корня), то в силу непрерывности функций ~' и )"' найдется оо-окрестность корня, в которой при некоторых постоянных а и ф выполнены неравенства О < а 1 ~ ~У'(х) ~, ~Г'(х) ~ < Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
