Главная > Математика > Численные методы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

8. Метод парабол.

Метод секущих можно рассматривать как замену функции интерполяционным многочленом первой степени, проведенным по узлам

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

Приравнивая его нулю, получим квадратное уравнение

где

Тот из двух корней квадратного уравнения (36), который меньше по модулю, определяет новое приближение

Очевидно, для начала расчета надо задать три первых приближения (обычно наугад выбирают три числа), т. е. процесс является трехшаговым.

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

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

В методе парабол «разболтка» счета вблизи корня сказывается еще сильней, чем в методе секущих, ибо в расчете участвуют вторые разности. Тем не менее корни можно найти, с хорошей точностью; для определения оптимального числа итераций удобно пользоваться приемом Гарвика, описанном в п. 7.

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

Корни многочлена. Метод парабол оказался исключительно эффективным для нахождения всех корней многочлена высокой степени. Если — алгебраический многочлен, то, хотя сходимость метода при произвольном начальном приближении и не доказана, на практике итерации всегда сходятся к какому-нибудь корню, причем быстро.

Для многочлена частное есть тоже многочлен; поэтому последовательно удаляя найденные корни, можно найти все корни исходного многочлена.

Замечание 1. Если — многочлен высокой степени, то возникают дополнительные трудности. Многочлен быстро возрастает при увеличении аргумента, поэтому в программе для ЭВМ должна быть страховка от переполнения. Обычно вводят масштабные множители, величина которых связана с диапазоном изменения аргумента.

Замечание 2. Наибольшие по модулю корни многочлена высокой степени могут быть очень чувствительны к погрешности коэффициентов при старших степенях. Например, корнями многочлена

являются последовательные целые числа слегка измененный многочлен имеет такие корни:

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

Замечание 3. Для удаления вычисленных корней надо... делить многочлен. Это вносит погрешность округления в коэффициенты и влияет на точность нахождения следующих корней. На практике отмечено, что если сначала удалять меньшие по модулю корни, точность падает мало, но если надать удаление с больших корней, точность может упасть катастрофически. Поэтому за начальное приближение берут тогда итерации обычно сходятся к наименьшему по модулю корню. Его удаляют и по такому же начальному приближению ищут следующий корень и т. д. При такой организации вычислений потеря точности будет небольшой.

<< Предыдущий параграф Следующий параграф >>
Оглавление