Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 24
Текст из файла (страница 24)
Рис. 4.13 Рис. ~.12 Метод (4.48) обладает только линейной сходимостью. Его можно рассматривать как метод простой итерации с итерационной функцией с — х 1()(х) = х —, 1(х). Так как скорость сходимости определя- ется вблизи корня величиной д и ~ р'(х) ~ = ~ 1 — ' ', то она — (с — х) ) (х) ,) (с) — 1 (х) тем выше, чем ближе окажется выбранная точка с к х. 3. Метод секущих. Замена в формуле метода Ньютона производной ~(х(п-1) ) У (х(п)) ~'(х(")) приближением,„...„, приводит к расчетной формуле л(стода секущих: х( " 1' — х' "' Х(а+1) — Х(п) 1 (х( "' ), п ~ 1.
(4.49) Хх(" ") — У(х'"') Заметим, что этот метод двухшаговый, так как для нахождения очередного приближения х' "' ' требуется знание двух предыдущих приближений х("' и х("1). В частности, для того чтобы начать вычисления, необходимо задать два начальных приближения х'()) и х'" . Все рассмотренные ранее методы требовали для вычисления х' "') только знание х'"', т.
е. были одношаговыми. 114 На рис. 4.13 приведена геометрическая иллюстрация метода. Очередное приближение х~""~ получается здесь как абсцисса точек пересечения с осью Ох секущей, соединяющей точки М' "" и М' "' графика функции ~(х) с координатами (х~" '~, ~(х'" ы)) и (х'"~, 1" (х~ ">)). Примечательно то, что эта модификация метода Ньютона сохраняет свойство сверхлинейной сходимости, если вычисляется простой корень х. Точнее, верно следующее утверждение. Т е о р е и а 4.9.
Пусть х — простой корень уравнения 1'(х) = О, в некоторой окрестности которого функция ~ дважды непрерывно диф- ференцируела, причел ~'(х) ~ О. Тогда существует о-окрестность корня х такая, что при произвольнол выборе приближений х'в> и х<Ы из этой и-окрестности летод секущих сходится с порядкол р ~ 1.618, т. е. для и ~ 1 справедлива оценка ф + 1 2 — ~/5 + 1 ~х'и'г> — х! ~ ~с~х<т — х)р, р = 2 Так как одна итерация метода секущих требует только одного нового вычисления значения функции 1, а метод Ньютона — двух вычислений значений функций (~ и 1 ), то трудоемкость двух итераций метода секущих приблизительно эквивалентна трудоемкости одной итерации по Ньютону. Две итерации метода секущих дают порядок р~ м 2.618 > 2, поэтому его можно расценивать как более быстрый по сравнению с методом Ньютона. К сожалению, метод обладает, вообще говоря, только локальной сходимостью.
Он требует выбора двух близких к х 1в общем случае— очень близких) начальных приближений х<о' и х'". Если эти приближения выбраны неудачно, то метод расходится (рис. 4.14). Рис. Л.14 115 4. Метод Стеффенсена. Итерационная формула метода Сшеффеясеяа имеет вид х(п+»» х(»»» ( х~"' »» ~ О. = х х' „~(х ), »» 1 О. (4.50) Можно считать, что она получена в результате замены производной ~'(х» "»), входящей в расчетную формулу метода Ньютона, приближением (4.47), где г' "' = х<"' + ~(х' "'). Метод Стеффенсена интересен тем, что он является одношаговым, не требует вычисления производной ~' и в то же время, как и метод Ньютона, сходится квадратично, если корень х — простой, функция 1' дважды непрерывно дифференцируема в окрестности корня, а началь- ное приближение х»»»» выбрано близко к х. Геометрическая иллюстрация метода Стеффенсена приведена на рис. 4.15.
Приближение х~"'»» получается как абсцисса точки пересечения с осью Ох секущей, проходящей через точки » М< "» и У» "» с координатами (х~ ю 1 (х~ а» )) и (х( а» ~ (г» "» )). Значение г' "» отвечает абсциссе точки а'" пересечения с осью Ох прял" ! мой у ~(х~ "» ) — (х 1 — х» "» ), проходящей через 1 точку М'"' и параллельной 0 «» «~У» я"! « прямой у = -х. Несмотря на свойство квадРис. ф.1~ ратичной сходимости, метод Стеффенсена уступает методу секущих, поскольку требует большей вычислительной работы для достижения той же точности в.
Это связано с тем, что на каждой итерации рассматриваемого метода вычисление функции производится дважды, а в методе секущих лишь один раз. 5. Уточнение метода Ньютона для случая кратного корня. В принципе для вычисления корня уравнения ~(х) = 0 кратности и» ) 1 можно использовать и стандартный метод Ньютона. Однако в этом случае скорость его сходимости является только линейной. Можно показать, что знаменатель»» соответствующей геометрической прогрес- 1 сии приближенно равен 1 — —. 116 Для того чтобы сохранить квадратичную скорость сходимости, метод Ньютона нужно модифицировать следующим образом: (4.51) Можно показать (это достигается раскрытием неопределенностей с помощью формулы Тейлора), что при таком выборе итерационной функции р(х) = х — »> —, получим у'(х) = 0, и сходимость снова У (х) У'( ) окажется квадратичной.
На рис. 4.16, а, 6 проиллюстрировано поведение последовательных приближений стандартного метода Ньютона и его модификации (4.51) для случая отыскания корня кратности т = 2. Рис. 4.16 Для метода (4.51) значение х<""' получается следующим образом. Б точке М< "> с координатами (х'">, у(х< ">)) к графику функции проводится касательная. Пересечение ее с осью Ох дает вспомогатель- м ную точку х<"". Для получения точки х<""> нужно воспользоваться равенством х' "+" — х' "' = т (х < "+" — х' "> ). Пример 4.10.
Применим методы, рассмотренные в данной главе, для вычисления положительного корня уравнения 4(1 — х~) — ех = О, считая известным, что х б (О, 1] (см, пример 4.2). Результаты вычислений приведены в табл. 4.5 — 4.8. В них для каждого приближения дается число верных знаков и требуемое число вычислений 117 значений функции г"(х) = 4(1 — ~з) — ет (для упрощенного метода Ньютона учтено вычисление Х'(т~® )). Вычисления выполнены с 10 знаками мантиссы. Отметим, что выбор начальных приближений был довольно случайным (хотя и разумным). Тем не менее лучший результат показал метод секущих.
Решение с 10 верными знаками мантиссы было получено после 5 итераций и для этого потребовалось лишь 6 вычислений функции. Хотя метод Ньютона (см. пример 4.8) при том же начальном приближении г'о~ дает такое же значение х всего после 4 итераций, для этого требуется 8 вычислений функции (4 вычисления ~и 4 вычисления ~'). Пример 4.11.
Применим метод Ньютона и его модификацию (4.51) для вычисления корня т = 0 кратности пт = 2 для уравнения стем = О. Возьмем ,г' о> = 1. Результаты вычислений даны в табл. 4.9 и 4.10. Как видно из табл. 4.9, погрешность метода Ньютона убывает довольно медленно и соответствует примерно геометрической прогрессии со знаменателем д = 1/2. В то же время 5 итераций по формуле (4.51) при т = 2 дают значе— ние решения с погрешностью, меньшей 6 = 10 1о.
Таблица 45 Таблица 46 Упрощенный метод Ньютона; х4ш = 0.5 Метод ложного положения; с = 1 т( о) = 0.5 Число Число верных вычис- Число Число п т( п) . верных вычисзнаков лений функций знаков лений функций 118 0 .0.5000000000 1 0.7392185177 2 0.6896366262 3 0.7081565866 4 0.7017501401 5 0.7040350503 6 0.7032284740 7 0.7035142540 8 0.7034131306 9 0.7034489297 10 0.7034362584 0 О 1 2 1 3 2 4 5 3 6 3 7 4 8 4 9 4 10 5 11 О 1 2 3 4 5 6 7 8 9 10 0.5000000000 0.6660226835 0.6971284254 0.7023912700 0.7032658920 0.7034108088 0.7034348083 0.7034387825 0.7034394406 0.7034395495 0.7034395676 0 0 1 2 2 3 2 4 3 5 4 6 5 7 6 8 6 9 7 10 8 11 Таблица 47 Таблица 48 Метод секущих; х< е> = 1, х< ~> = 0.5 Метод Стеффенсена; х' о' = 0.5 Таблица 4Я Т а б л и ц а 4.10 Уточнение метода Ньютона для случая т= 2 Метод Ньютона 6.
Чувствительность к погрешностям. Рассмотренные в этом параграфе одношаговые методы можно интерпретировать как различные варианты метода простой итерации. Поэтому исследование их чувствительности к погрешностям сводится 1аналогично тому, как это было сделано в предыдущем параграфе для метода Ньютона) к использованию соответствующих результатов 8 4.5. Так, например, можно убе- диться в хорошей обусловленности модифицированного метода Ньютона и метода ложного положения. Высокая скорость сходимости метода секущих делает его привлекательным для применения.
Однако вызывает беспокойство тот факт, У ( .1 и-11 ) У ( .1 и) ) что в формулу (4.49) входит величина , аппрок- х1И-1) х1 И1 симирующая производную. Вблизи корня, когда х1 "1 м х1и-11 и 1(х1 "1) м 1(х'" ") и О, погрешность вычисления функции начинает существенно сказываться на точности этой величины, и метод секущих теряет устойчивость. Этим он существенно отличается от методов простой итерации и Ньютона, для которых приближения х'"' равномерно устойчивы к погрешности независимо от числа итераций и. Тем не менее при грамотном использовании метод секуш;их дает возможность получить почти столько же верных значащих цифр корня х, сколько вообще позволяет обусловленность задачи (см. З 4.2). Возможная (но не обязательная) потеря точности составляет 1 — 2 верные цифры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
