Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 30
Текст из файла (страница 30)
В частности, чтобы заставить ХЕЙО[)ч найти наименьший возможный интервал, нужно задать ТОЕ равным нулю. На каждом шаге 2ЕЙ01Р1 выбирает очередное приближение из двух кандидатов — один получен алгоритмом бисекции, а другой — алгоритмом интерполяции. Если А, В и С различны, используется обратная квадратичная интерполяция; в противном случае — линейная интерполяция (метод секущих).
Если точка, полученная интерполяцией, «разумна», то выбирается она; иначе выбирается точка бнсекции. Определение «разумности« довольно техническое, но по существу оно означает, что точка находится внутри текущего интервала и не слишком близка к его концам. Следовательно, длина интервала гарантированно убывает на каждом шаге и убывает быстро, если функция хорошо ведет себя.
Более подробно см. в книге Брент (1973). Нужно упомянуть некоторые программистские детали ХЕЯ01М, поскольку они могут быть важны и в других ситуациях. Точка бисекции вычисляется как ХМ= В+0.5я(С вЂ” В), пк пОдпРОГРАммА заяо7н 179 а не по обычной формуле ХМ=0.5«(С+ В). Чтобы это понять, возьмем С=0.982 и В=0.987. Предположим, что вычисления выполняются на машине с трехзначной десятичной плавающей арифметикой с усечением. Тогда для С+В будет получено значение 1.95 и обычная формула даст в качестве средней точки 0.980, что находится вне интервала. Общий принцип таков: лучше преобразовать формулы, чтобы онн выражали желаемую величину как малую поправку к хорошему приближению. Большое внимание уделено проблеме машинных нулей и переполнений.
Например, проверка, что Р(В) и Р(С) имеют разные знаки, отличается от обычного условия Р (В) Р (С) ( 0.0. Если Е(В)=10-" и Р(С)= — 10-", то они имеют разные знаки; однако на многих машинах произведение будет машинным нулем и тест не будет выполнен. Точка, получаемая интерполяционными алгоритмами, записывается в виде В+РЯ, но деление не производится, пока это не будет необходимо и безопасно. Если берется точка бнсекции, то эта величина не нужна вовсе. Дадим теперь краткое резюме того, что утверждает Брент относительно своей версии алгоритма 2ЕКО15!. Во-первых, опа всегда сходится, даже для плавающей арифметики.
Во-вторых, количество вычислений функции не может превысить числа, равного примерно ~!О82 ( гб! ! ) 1 где ТОЫ =0.5" ТО).+2.0*ЕРБ*АВЯ(В). В-третьих, нуль К, получаемый алгоритмом, таков, что Р гарантированно меняет знак в определенном интервале, приблизительно совпадающем с !К вЂ” 2"ТО1.1, К+2'ТОЫ!. В-четвертых, Брент очень широко проверял свой алгоритм на весьма разнообразных функциях и установил, что в типическом случае для гладкой функции требуется порядка 1О вычислений значений.
В-пятых, он ни разу не обнаружил функции, для которой потребовалось бы более трехкратного числа вычислений по сравнению с методом бисекцин, т, е, больше 170 иа !ВМ 360 для корня, не находящегося вблизи нуля. В-шестых, если функция Е достаточно гладкая, например имеет непрерывную вторую производную вблизи простого нуля К, то алгоритм УЕЛО!!1 (начатый достаточно близко к К) постепенно перестанет делать бисекцин и будет сходиться к В посред- т РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ 180 КЕАЬ РОНСТЮН 2ЕКО!М(АХ, ВХ, Р, ТОЬ) КЕАЬ АХ, ВХ, Р, ТОЬ С С С С С НУЛЬ ФУНКЦИИ Р(Х) ВЫЧИСЛЯЕТСЯ В ИНТЕРВАЛЕ АХ, ВХ ВХОДНАЯ ИНФОРМАЦИЯ..
') Де Морган имеет в виду книгу Рихпш'а Ргохгем английского религиоаиого писателя Джона Баннана (!628 — !688). — Прим. нерее. ством процесса, очень схожего с методом секущих и имеющего скорость сходимостн не меньше ! .618. Локазательства этих утверждений см. в книге Бреит (1973). Приводимая ниже программа иллюстрирует использование ХЕК0114 для простого примера г(х)=ха — 2х — 5. Из приблизительного графика((х) легко видеть, что имеется только один действительный нуль и что он'лежит между 2 и 3.
Результат: Х=2.0945514815. В этом примере мы имеем дело с полиномом, к которому можно было бы применить методы 2 7.4, однако здесь он использован по причинам исторического интереса. В книге Уиттекера и Робинсона «Анализ наблюдений» (%)!1!!а)сег, Ко8(пзоп, Т)!е Са1си!Нз о1 ОЬзегча!)опз, 1924) приводится следующий отрывок из.
письма, написанного де Морганом Вивеллу (91Г)!еъеП) в 1861 гх «Я потому называю х' — 2х — 5=0 прославленным уравнением, что именно на нем Валлис рискнул применить метод Ньютона, когда тот впервые опубликовал его, вследствие чего каждый численный метод должен проявить себя в том числе н на этом примере. Изобрести численный метод и пренебречь показать, как он работает для этого уравнения, означает оказаться в положении паломника, не желающего войти в маленькую дверцу.
(см. Л. Вппуап)» ". С ИЛЛЮСТРИРУЮЩАЯ ПРОГРАММА ДЛЯ 2ЕКО1М С КЕАЬ Р!)НСТ!ОН Р(Х) КЕАЬ Х Р = Х'[Х'Х вЂ” 2.) — 6. КЕТОКН ЕНО С ЕХТЕКНАЬ Р КЕАЬ А, В, 2, ТОЬ, 2ЕК01(Ч А=2. В=8. Т01. = 1.ОŠ— !О 2=2ЕК01Н(А, В, Р, Т01.) »УК!те(6, 1)2 1 РОКМАТ(ЗН 2=, Р!6.10) ЗТОР Е(ЧО ?.2. ПОДПРОГРАММА 2ДДО!М !в! АХ ВХ Р Т01. ВЫХОДНАЯ ИНФОРМАЦИЯ с С с С с С НАЧАТЬ ШАГ 20 30 С С С С С С с с С С С С С С С С С С С С С С С С С С С ЛЕВЫЙ КОНЕЦ ИСХОДНОГО ИНТЕРВАЛА ПРАВЫЙ КОНЕЦ ИСХОДНОГО ИНТЕРВАЛА ПОДПРОГРАММА-ФУНКЦИЯ, КОТОРАЯ ВЫЧИСЛЯЕТ Р(Х)ДЛЯ ЛЮБОГО Х В ИНТЕРВАЛЕ АХ, ВХ ЖЕЛАЕМАЯ ДЛИНА ИНТЕРВАЛА НЕОПРЕДЕЛЕННОСТИ КОНЕЧНОГО РЕЗУЛЬТАТА ХЕ)10!Н АБСЦИССА, АППРОКСИМИРУЮЩАЯ НУЛЬ ФУНКЦИИ Р В ИНТЕРВАЛЕ АХ, ВХ БЕЗ ПРОВЕРКИ ПРЕДПОЛАГАЕТСЯ, ЧТО Р(АХ) И Р(ВХ) ИМЕЮТ ПРОТИВОПОЛОЖНЫЕ ЗНАКИ.
2ЕЯО!Н ВЫЧИСЛЯЕТ НУЛЬ Х В ЗАДАННОМ ИНТЕРВАЛЕ АХ, ВХ В ПРЕДЕЛАХ ДОПУСКА НА ОШИБКУ 4*МАСНЕР5'АВ5(Х)+ ТОЬ, ГДЕ МАСНЕР5 — ОТНОСИТЕЛЬНАЯ МАШИННАЯ ТОЧНОСТЬ. ЭТА ПОДПРОГРАММА-ФУНКЦИЯ ПРЕДСТАВЛЯЕТ СОБОЙ СЛЕГКА МОДИФИЦИРОВАННУЮ ТРАНСЛЯЦИЮ АЛГОЛ 60 — ПРОЦЕДУРЫ ХЕЯО, ПРИВЕДЕННОЙ В КНИГЕ )1!СНА)10 ВЯЕНТ, АЬОО)( !ТНМ5 РОЯ М! Н )М12АТ !ОН )Ч )ТНООТ ПЕЯ1ЧАТ!ЧЕ5, РЯЕНТ1СЕ-НА1Л., 1НС. (!973).
ЯЕАЬ А,В,С,Р,Е,ЕРБ,РА,РВ,РС,ТОЬ(,ХМ,Р,О,Я,5 ВЫЧИСЛИТЬ ЕР5, ОТНОСИТЕЛЬНУЮ МАШИННУЮ ТОЧНОСТЬ ЕР5= !.0 !О ЕРБ=ЕРББЬО Т01.! =1.О+ЕР5 !Г(ТО1.! .ОТ. !.О) 60 ТО !О ПРИСВОЕНИЕ НАЧАЛЬНЫХ ЗНАЧЕНИЙ А=АХ В=ВХ РА = Р(А) РВ=Р(В) С=А РС=ГА О= †е =г) 1Р(АВ5(РС) .ОЕ. АВ5(ГВ)) 00 ТО 40 А=В В=С С=А РА4 РВ КЗ. КОМПЛЕКСНЫЕ КОРНИ (вз )Г(АВЗ(0) .ОТ. ТО!.!)В=В+О )Г(АВЗ(0) Л Е. ТО!.!)В =В+В(ОХ(ТО(.(,ХМ) ГВ = Р(В) )Е(((7В*(ЕС)АВЗ(ГС))) .СТ. О.О)ОО то ЗО ОО ТО 30 С С КОНЧЕНО С 90 ЕЕ((О!Х = В НЕТ()ЙХ ЕГ(0 7.3.
Трансцендентные ураанения— комплексные корни Обычно аналитические функции имеют не только действительные, но и комплексные корни. Могут ли методы, обсуждавшиеся в 5 7.! и 7.2, использоваться для нахождения комплексных нулей? Метод бисекции опирается на то, что непрерывная функция, меняющая знак в интервале, имеет нуль внутри этого интервала. Зту идею нелегко обобщить для локализации комплексных нулей аналитических функций. Одна родственная идея — это прин!(ип аргдмекп70: предположим, что ) аналитична в области )? комплексной плоскости, и пусть С вЂ” простая замкнутая кривая в )с, Предположим, что когда г описывает контур С, 7"(г) ровно один раз обходит начало координат.
Тогда !" имеет ровно один нуль внутри С. Было сделано множество попыток непосредственно применить этот принцйп к локализации нулей ! внутри области, но ни одна не оказалась особенно успешной. Основная трудность состоит в необходимости большого количества вычислений 7'(г), чтобы увидеть, заключает ли кривая ()(г): г~ С) внутри себя начало координат. Лемер (Э.
Н. ( е)7гпег) использовал усложненный вариант этой идеи для локализации нулей полиномов, Но для функций 7' общего вида, по-видимому, иет какого-либо хотя и медленного, но гарантированного аналога метода бисекции. Поэтому на практике пользуются другими методами. Методы Ньютона и секущих можно использовать в комплексной плоскости без каких-либо изменений в теоремах. Как и для действительных корней, необходимо близко подойти к нулю, прежде чем может начаться быстрая сходимость.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
