§ 4.8. Дополнительные замечания

1. Метод обратной квадратичной интерполяции.

Пусть приближения уже найдены, а соответствующие значения функции различны (последнее предположение заведомо будет выполнено, если функция строго монотонна). Тогда строят такой квадратичный многочлен от переменной у, что Для За очередное приближение к решению принимается

Этот трехшаговый метод обладает локальной сходимостью с порядком для начала его работы требуется задание трех хороших начальных приближений.

2. Методы с порядком сходимости выше второго.

Приведем пример одношагового метода, обладающего кубической сходимостью:

Существуют и другие методы с порядком сходимости выше второго, теоретически очень быстро сходящиеся вблизи корня. Однако они редко используются

на практике, так как их преимущество в скорости сходимости начинает проявляться лишь тогда, когда итерации уже почти сошлись и в действительности осталось сделать 1—2 итерации либо вообще пора прекратить вычисления. Чтобы ощутить преимущество таких методов над методами Ньютона и секущих, нужна ЭВМ с очень высокой разрядностью и желание получить решение с чрезвычайно высокой точностью.

3. Вычисление корней многочленов.

Вычисление корней многочленов степени специальная задача, для решения которой разработано большое число эффективных алгоритмов. Укажем на один из них — метод Мюллера. В нем по трем ранее найденным приближениям строят интерполяционный многочлен второй степени т. е. такой многочлен для которого при За очередное приближение принимают тот из двух корней многочлена (в общем случае являющихся комплексными), который расположен ближе к

Вплоть до начала 60-х годов задача вычисления корней многочленов была весьма распространенной. Одна из основных причин состояла в том, что к отысканию корней характеристического многочлена сводилась одна из важнейших задач алгебры — задача вычисления собственных чисел матриц. В настоящее время существуют другие, гораздо более эффективные численные методы вычисления собственных значений (см. гл. 8), и, по-видимому, задача вычисления корней многочлена во многом потеряла свою актуальность.

Как было отмечено ранее, к задаче отыскания корней многочлена высокой степени с приближенно заданными коэффициентами следует отнестись очень внимательно: она может оказаться плохо обусловленной (см. в гл. 3 пример Уилкинсона). Вообще, можно посоветовать избегать применения методов решения вычислительных задач, в которых используются многочлены высокой степени.

4. Гибридные алгоритмы.

В последние годы получили признание алгоритмы, которые называют гибридными (или регуляризированными). Они представляют собой комбинации надежных, но медленно сходящихся методов типа бисекции с недостаточно надежными, но быстро сходящимися методами типа секущих и Ньютона. Результирующие алгоритмы обладают высокой надежностью и гарантированной сходимостью. В тех же случаях, когда в окрестности простого корня функции гладкая, сходимость становится сверхлинейной.

Алгоритм ZEROIN, изложенный в [86], является примером эффективного гибридного алгоритма, на каждом шаге которого принимается решение о том, какой из трех методов: бисекции, секущих или обратной квадратичной интерполяции — следует использовать для вычисления очередного приближения.

5. Критерии окончания.

Проблема выбора правильного критерия окончания итерационного процесса часто оказывается достаточно сложной. Следует иметь в виду, что наряду с обсуждавшимся в предыдущих параграфах условием нередко используется следующее условие: