МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
СУМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
КАФЕДРА ИНФОРМАТИКИ
Контрольная работа
ПО ЧИСЛЕННЫМ МЕТОДАМ
на тему:
“Методы нахождения корней полиномов”
Сумы - 2007 г.
План
1 Нахождение корней уравнений (Equation Section 1)
2 Схема Горнера
3 Функции произвольного вида
4 Нахождение корней полиномов
Список используемых информационных источников
1 Нахождение корней уравнений (Equation Section 1)
Одним из наиболее распространенных методов поиска корней уравнений является метод Ньютона и его модификации. Пусть требуется решить уравнение. Будем считать, что x является решением уравнения. Разложим функцию f(x) в ряд в точке x0 близкой к точке x и ограничимся только первыми двумя членами разложения.
Поскольку x – корень уравнения, то . Следовательно,
Таким образом, если нам известно приближенное значение корня уравнения, то полученное уравнение позволяет его уточнить. Понятно, что процесс уточнения можно повторять многократно, до тех пор, пока значение функции не будут отличаться от нуля на величину меньшую, чем заданная точность поиска. Очередное k-е приближение находится по формуле
Ограничившись в разложении только первыми двумя членами, мы фактически заменили функцию f(x) на прямую линию, касательную в точке x0, поэтому метод Ньютона еще называют методом касательных. Далеко не всегда бывает удобно находить аналитическое выражение для производной функции. Однако, в этом и нет особой необходимости: поскольку на каждом шаге мы получаем приближенное значение корня, можно для его вычисления использовать приближенное значение производной.
В качестве малой величины можно взять, например, заданную точность вычислений , тогда расчетная формула примет вид
(1.1)
С другой стороны, для вычисления производной можно воспользоваться значениями функции, полученными на двух предыдущих шагах,
(1.2)
В таком виде метод называется методом секущих (secant method). При этом, однако, возникает проблема с вычислением первого приближения. Обычно полагают, что , то есть первый шаг вычислений проводится с использованием формулы (1.1), а все последующие – с использованием формулы (1.2). Именно эта вычислительная схема реализована в пакете Mathcad. Используя метод секущих, мы не можем гарантировать, что корень находится между двумя последними приближениями. Можно, однако, для вычисления очередного приближения использовать границы интервала, на котором функция меняет знак. Такой метод называется методом хорд (false position method).
Идея метода секущих развивается в методе Мюллера. Однако в этом методе для нахождения очередного приближения используются три предыдущие точки. Иными словами, метод использует не линейную, а квадратичную интерполяцию функции. Расчетные формулы метода следующие[1]:
(1.3)
(1.4)
Знак перед корнем выбирается так, чтобы абсолютное значение знаменателя было максимальным.
Поскольку поиск корня заканчивается, когда выполнится условие, то возможно появление ложных корней. Например, для уравнения ложный корень появится в том случае, если точность поиска задана меньше, чем 0,0001. ............