Методы нахождения корней полиномов

Нахождение корней уравнений (Equation Section 1) методом: Ньютона, Риддера, Брента, Лобачевского и Лагерра. Вычисление корней многочленов по схеме Горнера. Функции произвольного вида (при использовании пакета Mathcad). Нахождение корней полиномов.
Краткое сожержание материала:

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

СУМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

КАФЕДРА ИНФОРМАТИКИ

Контрольная работа

ПО ЧИСЛЕННЫМ МЕТОДАМ

на тему:

“Методы нахождения корней полиномов”

Сумы - 2007 г.

План

1 Нахождение корней уравнений ()

2 Схема Горнера

3 Функции произвольного вида

4 Нахождение корней полиномов

Список используемых информационных источников

1 Нахождение корней уравнений ()

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

Поскольку x - корень уравнения, то . Следовательно,

Таким образом, если нам известно приближенное значение корня уравнения, то полученное уравнение позволяет его уточнить. Понятно, что процесс уточнения можно повторять многократно, до тех пор, пока значение функции не будут отличаться от нуля на величину меньшую, чем заданная точность поиска. Очередное k-е приближение находится по формуле

Ограничившись в разложении только первыми двумя членами, мы фактически заменили функцию f(x) на прямую линию, касательную в точке x0, поэтому метод Ньютона еще называют методом касательных. Далеко не всегда бывает удобно находить аналитическое выражение для производной функции. Однако, в этом и нет особой необходимости: поскольку на каждом шаге мы получаем приближенное значение корня, можно для его вычисления использовать приближенное значение производной.

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

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

В таком виде метод называется методом секущих (secant method). При этом, однако, возникает проблема с вычислением первого приближения. Обычно полагают, что , то есть первый шаг вычислений проводится с использованием формулы , а все последующие - с использованием формулы . Именно эта вычислительная схема реализована в пакете Mathcad. Используя метод секущих, мы не можем гарантировать, что корень находится между двумя последними приближениями. Можно, однако, для вычисления очередного приближения использовать границы интервала, на котором функция меняет знак. Такой метод называется методом хорд (false position method).

Идея метода секущих развивается в методе Мюллера. Однако в этом методе для нахождения очередного приближения используются три предыдущие точки. Иными словами, метод использует не линейную, а квадратичную интерполяцию функции. Расчетные формулы метода следующие Получите эти формулы самостоятельно по аналогии с методом Ньютона, оставив в разложении Тейлора первые три слагаемых.:

Знак перед корнем выбирается так, чтобы абсолютное значение знаменателя было максимальным.

Поскольку поиск корня заканчивается, когда выполнится условие, то возможно появление ложных корней. Например, для уравнения ложный корень появится в том случае, если точность поиска задана меньше, чем 0,0001. Увеличивая точность поиска, можно избавиться от ложных корней. Однако не для всех уравнений такой подход работает. Например, для уравнения , которое, очевидно, не имеет действительных корней, для любой, сколь угодно малой точности найдется значение x, удовлетворяющее критерию окончания поиска. Приведенные примеры показывают, что к результатам компьютерных вычислений всегда нужно относиться критически, анализировать их на правдоподобность. Чтобы избежать "подводных камней" при использовании любого стандартного пакета, реализующего численные методы, нужно иметь хотя бы минимальное представление о том, какой именно численный метод реализован для решения той или иной задачи.

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

В методе Риддера (Ridder's method) вычисляют значение функции в середине интервала . Затем ищут экспоненциальную функцию такую, что Затем применяют метод хорд, используя значения . Очередное значение вычисляют по формуле

Метод Брента (Brent method) соединяет быстроту метода Риддера и гарантированную сходимость метода деления отрезка пополам. Метод использует обратную квадратичную интерполяцию, то есть ищет x как квадратичную функцию y. На каждом шаге проверяется локализация корня. Формулы метода достаточно громоздки и мы не будем их приводить.

Особые методы применяют для поиска корней полинома. В этом случае могут быть найдены все корни. После того как один из корней полинома найден, степень полинома может быть понижена, после чего поиск корня повторяется.

Метод Лобачевского, метод приближённого (численного) решения алгебраических уравнений, найденный независимо друг от друга бельгийским математиком Ж. Данделеном, русским математиком Н. И. Лобачевским (в 1834 в наиболее совершенной форме) и швейцарским математиком К. Греффе. Суть Л. м. состоит в построении уравнения f1(x) = 0, корни которого являются квадратами корней исходного уравнения f(x) = 0. Затем строят уравнение f2(x) = 0, корнями которого являются квадраты корней уравнения f1(x) = 0. Повторяя этот процесс несколько раз, получают уравнение, корни которого сильно разделены. В случае если все корни исходного уравнения действительны и различны по абсолютной величине, имеются простые вычислительные схемы Л. м. для нахождения приближённых значений корней. В случае равных по абсолютной величине корней, а также комплексных корней вычислительные схемы Л. м. очень сложны.

Метод Лагерра (Laguerre's method) основывается на следующих соотношениях для полиномов

Предполагают, что корень x1 находится на расстоянии a от текущего приближения, в то время как все другие корни находятся на расстоянии b: . Тогда

,

откуда

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

Еще один метод, который применяют для поиска корней полиномов, - метод сопровождающей матрицы (companion matrix). Можно доказать, что матрица

,

• называемая сопровождающей матрицей для полинома , имеет собственные значения равные корням полинома. Напомним, что собственными значениями матрицы называются такие числа ?, для которых выполняется равенство или . Существуют весьма эффективные методы поиска собственных значений, о некоторых из них мы будем говорить далее. Таким образом, задачу поиска корней полинома можно свести к задаче поиска собственных значений сопровождающей матрицы.
• 2 Схема Горнера
• Вычисление по схеме Горнера оказывается более эффективным, причем оно не очень усложняется. Эта схема основывается на следующем представлении многочлена:
• p(x) = (( ... ((anx + an-1)x + an-2)x + ... + a2)x + a1)x + a0.
• Займемся общим многочленом вида:
• p(x) = anxn + an-1xn-1 + an-2xn-2 + ... + a2x2 + a1x + a0.
• Мы будем предполагать, что все коэффициенты an, ..., a0 известны, постоянны и записаны в массив. Это означает, что единственным входным данным для вычисления многочлена служит значение x, а результатом программы должно быть значение многочлена в точке x.
  Стандартный алгоритм вычисления прямолинеен:

Evaluate(x)

xточка, в которой вычисляется значение многочлена

result = a[0] + a[1]*x

xPower = x

for i = 2 to n do

xPower = xPower*x

result = result + a[i]*xPower

end for

return result

Этот алгоритм совершенно прозрачен и его анализ очевиден. В цикле for содержится два умножения, которые выполняются n - 1 раз. Кроме того, одно умножение выполняется перед циклом, поэтому общее число умножений равно 2n - 1. В цикле выполняется также одно сложение, и одно сложение выполняется перед циклом, поэтому общее число сложений равно n.

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

HornersMethod(x)

xточка, в которой вычисляется значение многочлена

for i = n - 1 down to 0 do

result = result*x

result = result + a[i]

end for

return result

Цикл выполняется n раз, причем внутри цикла есть одно умножение и одно сложение. Поэтому вычисление по схеме Горнера требует n умножениё и n сложений - двукратное уменьшение числа умножений по сравнению со стандартным алгоритмом.

Предварительная обработка коэффициентов

Результат можно д...