Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 29
Текст из файла (страница 29)
Если математическая функция 1 достаточно гладкая (имеет одну или две непрерывные производные), то часто есть возможность значительно сократить число вычислений функции по сравнению с методом бисекции. Было изучено большое число различных итерационных методов, из которых мы обсудим здесь только метод Ньютона и метод секущих. Дальнейшие сведения об этих н прочих методах можно найти в статье Траубэ: «Решение трансцендентных уравнений» (Рэлстон, Уилф (1967)). 1) Или иоловиииого делении.— Прим. верее. 174 7. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ В методе Ньютона (иногда называемом также методом Нью- тона — Рафсона) нуль г функции / находится как предел после- довательности действительных чисел (хд).
(Мы предполагаем сейчас точную арифметику действительных чисел.) Каждое новое приближение хд„вычисляется как единственный нуль каса- тельной прямой к функции у=/(х) в точке хд, т. е. путем локаль- ной линеаризации / около хд. Как показывается в анализе, /(»д) х»„= х» —, прн условии, что /' (хд)~=0. Теорема Если/(г)=О, а/' (г)~0 и(" непрерывна, то существует открытый интервал /)/(г), содержащий г и такой, что если х, принадлежит й1(г), то для метода Ньютона хд-ег при я +ос. Более того, если обозначить через ед ошибку приближения хд . ед —— =хд — г, то е»+ д р (е) (пп —, е» 2/' (е) Вместо того чтобы доказывать теорему, мы обсудим ее. Условие означает, что г — простой нуль /.
Утверждение устанавливает, что ошибка еде, примерно равна Се», где С=/" (г)/2/'(г). Итак, говоря приблизительно, каждая итерация возводит ошибку ед в квадрат. При ед- 0 число правильных десятичных (или двоичных) цифр примерно удваивается на каждой итерации. 1 Если С порядка 1, то при хд столь близком к г, что )ед) ( —, 2 ' имеем 1 ! 1 )е„е,) < 2,, )е»„,) < —,, ..., )ед+е! < — „. Таким образом, грубо говоря, нужно примерно шесть итераций, чтобы сократить ошибку от — до наименьшего значения, возмож-, 2 ного для плавающей арифметики 1ВМ 360 с удвоенной точностью.
Это нужно сопоставить с приблизительно 55 итерациями, необ- ходимыми для достижения той же точности методом бисекции. Об итерационном процессе, для которого ошибка е„удовлет- воряет соотношению еде, 1(гп — „=С Ф О, ее» говорят, что он имеет сходимость порядной, В условиях теоремы, если /" (г)~0, метод Ньютона имеет сходнмость порядка 2, иногда называемую также квадратичной сходимостью. гл, деиствительные козни 175 По мере того как ошибка в методе Ньютона уменьшается до значений, сравнимых с расстоянием между соседними числами с плавающей точкой, зернистая структура числовой системы делает продолжение алгоритма невозможным. Подлинная трудность в методе Ньютона заключается в выборе начального приближения х„которое бы находилось внутри интервала У(г) искомого нуля г.
Если график 7 имеет вид, показанный на рис. 7.1, то йг(г) приблизительно совпадает с интервалом (г — е, г+з). Если х, взято вне йг(г), то последовательные ите- Рис. 7.1. рации метода Ньютона все больше удаляются от г и нуль не будет найден. Вследствие этого методу Ньютона часто предшествует какой. нибудь глобально сходящийся алгоритм типа бисекции, прежде чем можно будет переключиться на быстро сходящиеся ньютоновы итерации.
Таким образом, метод Ньютона зачастую является лишь завершающей процедурой более медленного, но зато гарантированного начального алгоритма. При таком комбинировании, к примеру, последние 26 или около того итераций бисекцин могут быть заменены 6 ньютоновыми шагами. Если г — не простой нуль, так что Г' (г)=0, то условия теоремы нарушаются. Сходимость метода Ньютона к двойному корню имеет порядок ! (называется также линейной сходииостью), а не 2. Например, для г'(х) — — х' в ньютоновом процессе хх+,—— =хь/2, следовательно, еь„,/е„== — при всех й. Заметим, что каждая итерация метода Ньютона требует вычисления не только 7" (х), но и Г'(х).
Есть функции, для которых вычисление 7'(х) после того, как найдено Г(х), очень дешево. Для других функций стоимость вычисления Г'(х) эквивалентна второму вычислению г(х). Наконец, для третьих функций вычисление )'(х) почти невозможно. Главное достоинство метода Ньютона состоит в том, что с его помощью можно находить комплексные нули аналитических функций 7", а также в том, что его можно распространить на решение систем нелинейных уравнений с многими переменными. 7.
РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ )76 При нахождении нулей функции /, для которой вычисление 7' (х) затруднено, метод секуи(их является часто лучшим выбором, чем метод Ньютона. В этом алгоритме начинают с двумя исходными числами х, и х,. На каждом шаге х»„получают из х„и х», как единственный куль линейной функции, принимающей значения 7(х») в х» и 7(х»,) в х»,. Эта линейная функция представляет секущую к кривой у=) (х), проходящую через ее точки Рис. 7хь с абсциссами х» и х» т — отсюда название метод секущих (рис. 7.2).
Легко показать, что !» »+~ » (1»,— г»)/(к»» — х») ' где 7» — — 7(х»). (Правую часть лучше не приводить к общему знаменателю. Почему)) Теорема сходимости для метода секущих формулируется так: Теорема Если 7(г)=0, но 7' (г)~0 и 7'"(г)~0, а 7" непрерывна, то суи(е- ствует открытый интервал М(г), содержащий г и такой, что если х, и х, — различные точки из йг(г), то последовательность х» сходится к г при 7» оо. Более оюго, Е»~1 )ип — = С ~= О, е» де р= —,' Д/'б+Ц=).Е)й. Доказательство значительно более сложно, чем простое доказательство, возможное для метода Ньютона. Утверждение теоремы означает, что для достаточно хороших начальных приближений метод секущих сходится к простому нулю функции, тл. подпгогялммл хвяогя имеющей непрерывную вторую производную, и при этом сходимость имеет порядок 1.6!8.
Если учесть, что на каждом шаге метода Ньютона требуется два вычисления функции (одно вычисление г и одно 1'), то можно считать, что порядок сходимости метода в пересчете на одно вычисление функции равен $' 2ж!.4!4. Поскольку шаг метода секущих требует лишь одного вычисления функции, этот метод может расцениваться как более быстрый по сравнению с методом Ньютона. Как н метод Ньютона, метод секущих очень хорошо работает для аналитических функций комплексного переменного. Однако обобщение метода на системы уравнений по-видимому довольно трудно, хотя и возможно, Подобно методу Ньютона, наибольшая трудность в методе секущих заключается в нахождении х, и х„достаточно близких к г для того, чтобы могла начаться сходимость. Если 1(х) была вычислена более чем в двух точках, то, видимо, разумно использовать эту информацию для улучшения последующих оценок нуля.
Одним из подобных методов является обратная квадратичная интерполяция, где берутся трн точки: хя „х„, и хю Пусть д(у) — квадратичный многочлен от переменного у, для которого х;=д(Л), !=я — 2, я — 1, я. Тогда в качестве следующего приближения к нулю берется хь,—— д(0). Это можно записать непосредственно в терминах трех значений х и трех значений 7, однако точная формула не важна здесь. Необходимо, чтобы три значения 1 были различны. Если это не так, в формуле произойдет деление на нуль.
Скорость сходимости обратной квадратичной интерполяции равна 1.839, что несколько быстрее, чем в методе секущих. Однако нужны три начальных значения, и если онн выбраны недостаточно близко к нулю, то поведение алгоритма может быть весьма странным. 7.2. Подпрограмма УЕВО11ч Один из лучших имеющихся машинных алгоритмов для нахождения действительного нуля функции сочетает безотказность бисекции с асимптотической скоростью метода секущих в случае гладких функций. Он называется ЕЕк01)ч и был изобретен в 1960-х годах в Математическом центре Амстердама (Ван Вейнгарден, Деккер и др.). Описание н анализ даны в публикации Уилкинсон (! 967), именно с.
8 — 12. Впервые алгоритм был опубликован Деккером (!969) и затем улучшен Брентом (!973). Мы используем фортранную реализацию алгоритма Деккера в версии Брента. В конце этого параграфа помещен текст подпро- ь Решение нелинейных уРАВнений граммы-функции ЕЕК01)А). Типичное обращение к ХЕ(10151 имеет вид 2_#_=ХЕК01Р((А, В, Р, ТОЕ).
Здесь А,  — концевые точки интервала, на котором ищется нуль. Параметр Р обозначает вещественную подпрограмму-функцию, имеющую аргументом одну вещественную переменную. Т01. — это граница погрешности, допустимой в результате, Программа предполагает без проверки, что Р(А) и Р(В) имеют разные знаки.
ЕЕЙ01(А( выполняет итерационный процесс, в котором на каждом шаге присутствуют три абсциссы А, В и С. Обычно 1.  — последнее и наилучшее приближение к нулю. 2. А — предыдущее приближение. 3. С вЂ” предыдущее или еще более раннее приближение, такое, что Р(В) и Р(С) имеют противоположные знаки. Во всех случаях В и С ограничивают нуль.
Кроме того, 1Р(В)! (1Р(С)Е Если длина интервала! — С! уменьшилась настолько, что выполняется условие ) — С)«Т01.+4.»ЕР5 АВБ(В), то значение В выдается как значение функции ХЕК011ч. Кроме Т01., в проверке сходимости участвует параметр машинной точности ЕР5, чтобы подстраховать возможный случай, когда заданное значение ТОЕ слишком мало.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
