Метод риддера нахождения корней уравнения

Численные методы решения нелинейных уравнений. Метод Риддера.

Численные методы решения нелинейных уравнений. Метод Риддера.

Метод Риддера ( Ridder’s method ) является итерационным численным методом решения нелинейного уравнения непрерывной функции. Данный метод относится к методам интервалов локализации корня.

В соответствии с методом задача поиска корня в уравнении сводится к задаче:

— создание уникальной экспоненциальной функции вида ;

— поиска корня уравнения экспоненциальной функции , который будет являться приближением корня функции .

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

Значение функции в трех точках определяется в следующем виде:

› В точке значение функции определяется ;

› В точке значение функции определяется ;

› В точке значение функции определяется .

В представленных формулах используется параметр h, который определяется по формуле .

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

Задача поиска корня уравнения f(x) сводится к поиску корней квадратного уравнения относительно переменной . Корень квадратного уравнения определяется по формуле:

Используя математические преобразования данное уравнение можно привести к виду:

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

В результате подстановки переменной в данное уравнение получим формулу для определения точки пересечения функции с осью абсцисс.

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

,

где функция определена следующим образом:

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

или .

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

.

Данный метод решения нелинейного уравнения характеризуется определёнными свойствами:

— приближенное значение корня на любой итерации всегда оказывается внутри интервала локализации корня [ a,b ];

— метод обладает сверхлинейной сходимостью с порядком сходимости √2. Вычисленная на основании него последовательность приближений сходится довольно быстро. Каждое последующее приближение будет в среднем на две значимые цифры более точным по сравнению с предыдущем значением.

Алгоритм нахождения корня нелинейного уравнения по методу Риддера

1. Найти начальный интервал неопределенности одним из методов отделения корней. З адать погрешность расчета (малое положительное число ) и начальный шаг итерации ( ) .

2. Определить среднюю точку в рассматриваемом интервале и найти значения функции в трех точках: по краям рассматриваемого интервала , и в середине интервала .

3. Выполнить расчет приближенного значения корня функции в соответствии с формулой:

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

1 интервал: если , то новый интервал

2 интервал: если , то новый интервал

5. Проверяем значение корня на предмет заданной точности, в случае:

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

— если разность двух последовательных приближений не достигает необходимой точности , то необходимо продолжить итерационный процесс и перейти к п.2 рассматриваемого алгоритма.

Пример решения уравнений методом Риддера

В качестве примера, рассмотрим решение нелинейного уравнения методом Риддера . Корень необходимо найти в рассматриваемом диапазоне с точностью .

Вариант решения нелинейного уравнения в программном комплексе MathCAD .

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

Рис.2 . Результаты расчета по методу Риддера

Для обеспечения заданной точности при поиске уравнения в диапазоне необходимо выполнить 5 итерации. На последнем шаге итерации приближенное значение корня нелинейного уравнения будет определяться значением: .

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

Комментарии

В статье рассмотрен численный метод решения нелинейного уравнения, который используется в функции root () программного комплекса MathCad. По умолчанию функция root () использует несколько методов для расчета корней уравнений: метод Риддера (Ridder) и метод Брента (Brent).

root(f(x),x,a,b)
где f(x) — функция, определяющая уравнение;
х—переменная;
а и b—границы интервала локализации.
Обязательным условием является то, что значения функции на концах интервала должны быть противоположных знаков.

Последние материалы

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

Категория: Общая информация
Дата последнего изменения: 01.05.2019

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

Категория: Общие данные
Дата последнего изменения: 01.05.2019

В любой момент времени в электроэнергетической системе может возникнуть резкое нарушение квазиустановившегося режима работы, из-за короткого замыкания,…

Установившийся режим работы энергосистемы является квазиустановившемся, так как характеризуется малыми изменениями перетоков активной и реактивной мощности,…

В процессе моделировании переходных процессов в Matlab/Simulink (с библиотекой SimPowerSystems) возникает необходимость в определении взаимного угла между двумя…

Категория: Общие данные
Дата последнего изменения: 02.08.2018

Численные методы в Matchcad (стр. 1 )

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3

ЧИСЛЕННЫЕ МЕТОДЫ В MATHCAD

расчеты на Mathcad.

7.Анализ и синтез сигналов с помощью

В данной работе рассматриваются на многочисленных примерах, каким образом решаются на Mathcad’e разнообразные задачи численного анализа (решение систем линейных и нелинейных уравнений, решение дифференциальных уравнений, аппроксимация функций и т. д.). Необходимые ссылки как на учебники по численным методам, так и на руководства по пакету Mathcad можно найти в списке литературы. К сожалению, существует настоящая пропасть между теми численными методами, которые описаны в общедоступных учебниках, и теми, которые применяются на практике. В замечательной, хотя и недоступной для большинства студентов книге «Numerical Recipes in C», авторы замечают: «Увы, времена меняются; классические формулы почти абсолютно бесполезны. Они являются музейными экспонатами, хотя и прекрасными».

На момент написания данного пособия последней версией Mathcad¢а является версия Mathcad 2000 (предыдущая версия – Mathcad 8). Поскольку данная версия еще не получила повсеместного распространения, возможности, реализованные только в этой версии, оговариваются в пособии особо

Глава 1. Нахождение корней уравнений

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

,

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

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

Найдем нули функции на интервале x=[–2,7], используя Mathcad

Изобразим сначала функцию на графике.

На заданном интервале функция три раза обращается в ноль. Определим нули функции, используя встроенную функцию root(f(x),x). Первый аргумент – функция, нуль которой необходимо найти, второй – переменная, которую необходимо варьировать. (Вообще говоря, функция f может быть функцией многих переменных и необходимо указывать, по какой именно переменной мы ищем нуль функции.) Кроме того, необходимо задать начальное приближение поиска. Точность вычислений задается встроенной переменной TOL. По умолчанию ее значение равно 0,001. Это значение можно изменить либо через меню Math/Built–In Variables или непосредственно в тексте документа:

Задаем начальное приближение:

И вычисляем корень:

Если требуется найти несколько корней, как в нашей задаче, то имеет смысл определить новую функцию:

Функция r(x) возвращает значение корня ближайшее к x[2], то есть начальное приближение мы задаем через аргумент функции. Задаем вектор начальных приближений x и находим соответствующие им корни X:

Для данного примера корни легко могут быть найдены аналитически. Они равны на заданном интервале — p/2, p/2 и 3p/2. Полученный численный результат с заданной точностью совпадает с точным решением.

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

Первый аргумент функции z задает значение параметра, второй – начальное приближение. Найдем корни уравнения при значениях параметра 1 и 2.

Если мы хотим получить комплексный корень, то начальное приближение следует задавать комплексным:

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

Для нахождения корней полиномов имеется встроенная функция polyroots(a). Аргументом функции является вектор коэффициентов полинома , то есть для уравнения вектор а имеет вид

Если в полиноме отсутствуют некоторые степени, то на соответствующих местах следует писать 0. Пусть требуется найти корни полинома

Коэффициенты полинома могут быть и комплексными.

1.3. Нахождение корней уравнений путем символических преобразований.

Во многих случаях, Mathcad позволяет найти аналитическое решение уравнения. Для этого необходимо воспользоваться пунктом Solve for Variable из пункта меню Symbolic. Для того чтобы найти решение уравнения необходимо записать выражение и выделить в нем переменную (поставить указатель курсора возле переменной). Это необходимо для того, чтобы показать, какая именно величина является переменной, а какая – фиксированным параметром. После этого выбираем из пункта меню Symbolic подпункт Solve for Variable

решение готово ––>

Обратите внимание! В данном случае был найден только один корень, хотя, очевидно, их бесконечно много.

В случае полинома Mathcad, а точнее – встроенный символический процессор Maple – находит все корни.

–> Для этого примера найдено 2 корня, хотя они и вырождены. Пример с комплексными корнями: ––>

1.4 Поиск корней уравнений в Mathcad 2000.

Mathcad 2000 представляет ряд дополнительных возможностей для поиска корней уравнений. Функция root(f(var1, var2, . ),var1, [a, b]) имеет теперь два необязательных аргумента a и b, которые определяют границы интервала, на котором следует искать корень. На концах интервала [a, b] функция f должна менять знак (f(a)f(b) (Ctrl+.).

Решение записано в виде матрицы. Каждый столбец соответствует паре (x, y), то есть найдены решения (1,3) и (3,1).

2.4. Нахождение экстремумов функций

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

Первая заключается в использовании блока given и функции minerr.

Определим функцию двух переменных

Зададимся целью найти ее экстремум в области x=[–5,5] y=[–5,5]. Оценим по графику положение экстремума.

Заносим в матрицу М значения функции в узловых точках

На заданном интервале функция не превосходит 25. Зададим начальные приближения для поиска экстремума

Записываем блок уравнений или неравенств. Число уравнений и неравенств в блоке given – Find должно быть больше и равно числа искомых величин. Если уравнений и неравенств не хватает, то можно просто продублировать одно и то же уравнение или вписать какое–либо тождество, например, 2=2 .

Функция Minerr ищет приближенной решение для системы уравнений и неравенств, записанных в блоке. В данном случае мы получили, что системе уравнений наилучшим образом соответствует точка [0,0]. (Поскольку по умолчанию точность вычислений составляет 0.001, мы округлили результат до 0).

Из графика видно, что значение 26 больше самого большого значения функции в окрестностях точки [1,1], то есть точное решение найти нельзя и функция Minerr подбирает такое значение x, при котором функция ближе всего к значению 26.

Вторая возможность – поиск нулей первой производной, то есть стандартный математический подход. Для этого можно использовать блок given – Find. Функция Find ищет точное решение системы уравнений и неравенств, записанных после слова given.

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

В старших версиях Mathcad’а появилась дополнительная возможность поиска экстремумов с помощью функций Minimize и Maximize, которые могут быть использованы как сами по себе, так и совместно с блоком given. Аргументы функций: имя функции, экстремум которой ищется, и список ее аргументов.

Определяем функцию двух переменных и задаем начальные приближения .

Задаем область поиска максимума внутри блока given

Находим максимум функции в заданной области

В случае функции одной переменной задаем функцию и начальное приближение

Находим максимум

Если мы хотим найти максимальное или минимальное значение функции на некотором интервале, то необходимо определить этот интервал в блоке given

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

Глава 3. Аппроксимация функций

Введение

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

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

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

Наиболее часто встречающим видом точечной аппроксимации является интерполяция (в широком смысле).

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

В качестве функции обычно выбирается полином, который называют интерполяционным полиномом.

В том случае, когда полином един для всей области интерполяции, говорят, что интерполяция глобальная.

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

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

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

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

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

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

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)

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

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

(1.3)

(1.4)

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

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

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

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

(1.5)

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

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

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

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

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

,

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

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

,

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

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]*xxPower = xfor i = 2 to n doxPower = xPower*xresult = result + a[i]*xPowerend forreturn result

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

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

HornersMethod(x)xточка, в которой вычисляется значение многочленаfor i = n — 1 down to 0 doresult = result*xresult = result + a[i]end forreturn result

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

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

Результат можно даже улучшить, если обработать коэффициенты многочлена до начала работы алгоритма. Основная идея состоит в том, чтобы выразить многочлен через многочлены меньшей степени. Например, для вычисления значения x256 можно воспользоваться таким же циклом, как и в функции Evaluate в начале этой статьи; в результате будет выполнено 255 умножений. Альтернативный подход состоит в том, чтобы положить result = x*x, а затем семь раз выполнить операцию result = result*result. После первого выполнения переменная result будет содержать x4, после второго x8, после третьего x16, после четвертого x32, после пятого x64, после шестого x128, и после седьмого x256.

Для того, чтобы метод предварительной обработки коэффициентов работал, нужно, чтобы многочлен был унимодальным (то есть старший коэффициент an должен равняться 1) , а степень многочлена должна быть на единицу меньше некоторой степени двойки (n = 2k — 1 для некоторого k > 1). В таком случае многочлен можно представить в виде:

p(x) = (xj + b)q(x) + r(x), где j = 2k-1. (1)

В обоих многочленах q и r будет вдвое меньше членов, чем в p. Для получения нужного результата мы вычислим по отдельности q(x) и r(x), а затем сделаем одно дополнительное умножение и два сложения. Если при этом правильно выбрать значение b, то оба многочлена q и r оказываются унимодальными, причем степень каждого из них позволяет применить к каждому из них ту же самую процедуру. Мы увидим, что ее последовательное применение позволяет сэкономить вычисления.

Вместо того, чтобы вести речь о многочленах общего вида, обратимся к примеру. Рассмотрим многочлен:

p(x) = x7 + 4×6 — 8×4 + 6×3 + 9×2 + 2x — 3.

Определим сначала множитель xj + b в уравнении (1). Степень многочлена p равна 7, то есть 23 — 1, поэтому k = 3. Отсюда вытекает, что j = 22 = 4. Выберем значение b таким образом, чтобы оба многочлена q и r были унимодальными. Для этого нужно посмотреть на коэффициенты aj-1 в p и положить b = aj-1 — 1. В нашем случае это означает, что b = a3 — 1 = 5. Теперь мы хотим найти значения q и r, удовлетворяющие уравнению:

x7 + 4×6 — 8×4 + 6×3 + 9×2 + 2x — 3 = (x4 + 5)q(x) + r(x).

Многочлены q и r совпадают соответственно с частным и остатком от деления p на x4 + 5. Деление с остатком дает:

p(x) = (x4 + 5)(x3 + 4×2 + 0x + 8) + (x3 — 11×2 + 2x — 37).

На следующем шаге мы можем применить ту же самую процедуру к каждому из многочленов q и r:

q(x) = (x2 — 1)(x + 4) + (x + 12), r(x) = (x2 + 1)(x — 11) + (x — 26).

В результате получаем:

p(x) = (x4 + 5)((x2 — 1)(x + 4) + (x + 12)) + ((x2 + 1)(x — 11) + (x — 26)).

Посмотрев на этот многочлен, мы видим, что для вычисления x2 требуется одно умножение; еще одно умножение необходимо для подсчета x4 = x2*x2. Помимо этих двух умножений в вычислении правой части равенства участвуют еще три умножения. Кроме того, выполняется 10 операций сложения. В таблице 1 приведены сравнительные результаты анализа этого метода и других методов вычисления. Экономия не выглядит значительной, однако это объясняется тем, что мы рассматриваем лишь частный случай. Общую формулу для сложности можно вывести, внимательно изучив процедуру. Заметим прежде всего, что в равенстве (1) участвуют одно умножение и два сложения. Поэтому для числа умножений M = M(k) и числа сложений A = A(k) мы получаем следующий набор рекуррентных соотношений:

Таблица 1. Число операций при вычислении значения многочлена степени 7

Решая эти соотношения, мы заключаем, что число умножений приблизительно равно N/2, а число сложений приблизительно равно (3N — 1)/2. Неучтенными, однако, остались умножения, необходимые для подсчета последовательности значений x2, x4, x8, . x2k-1; на это требуется дополнительно k — 1 умножение. Поэтому общее число умножений приблизительно равно N/2 + log2N.

Таблица 2. Число операций при вычислении значения многочлена степени N

В таблице 2 приведены результаты сравнительного анализа стандартного алгоритма, схемы Горнера и алгоритма с предварительной обработкой коэффициентов. При сравнении последних двух алгоритмов видно, что нам удалось сэкономить N/2 — log2N умножений, но за счет дополнительных (N — 1)/2 сложений. Во всех существующих вычислительных системах обмен умножений на сложения считается выгодным, поэтому предварительная обработка коэффициентов повышает эффективность.

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

Найдем нули функции на интервале x=[–2,7], используя Mathcad

Изобразим сначала функцию на графике.

На заданном интервале функция три раза обращается в ноль. Определим нули функции, используя встроенную функцию root(f(x),x). Первый аргумент – функция, нуль которой необходимо найти, второй – переменная, которую необходимо варьировать. (Вообще говоря, функция f может быть функцией многих переменных и необходимо указывать, по какой именно переменной мы ищем нуль функции.) Кроме того, необходимо задать начальное приближение поиска. Точность вычислений задается встроенной переменной TOL. По умолчанию ее значение равно 0,001. Это значение можно изменить либо через меню Math/Built–In Variables или непосредственно в тексте документа:

Задаем начальное приближение:

И вычисляем корень:

Если требуется найти несколько корней, как в нашей задаче, то имеет смысл определить новую функцию:

Функция r(x) возвращает значение корня ближайшее к x[2] , то есть начальное приближение мы задаем через аргумент функции. Задаем вектор начальных приближений x и находим соответствующие им корни X:

Для данного примера корни легко могут быть найдены аналитически. Они равны на заданном интервале /2/2 и Полученный численный результат с заданной точностью совпадает с точным решением.

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

Первый аргумент функции z задает значение параметра, второй – начальное приближение. Найдем корни уравнения при значениях параметра 1 и 2.

Если мы хотим получить комплексный корень, то начальное приближение следует задавать комплексным:

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

Для нахождения корней полиномов имеется встроенная функция polyroots(a). Аргументом функции является вектор коэффициентов полинома , то есть для уравнения вектор а имеет вид

Если в полиноме отсутствуют некоторые степени, то на соответствующих местах следует писать 0. Пусть требуется найти корни полинома

Коэффициенты полинома могут быть и комплексными.

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

1. Coppersmith D., Odlyzko A. M., Schroeppel R. Descrete logarithms in GF(p) // Algorithmica. V. 1,1986. P. 1-15.

2. Lenstra A. K, Lenstra H. W. (jr.) The Development of the Number Field Siev. Lect. Notes in Math. V. 1554. Springer, 1993.

3. McCarthy D. P. “The optimal algorithm to evaluate xn using elementary multiplication methods”, Math. Comp., vol. 31, no 137, 1977, pp. 251 – 256.

[1] Получите эти формулы самостоятельно по аналогии с методом Ньютона, оставив в разложении Тейлора первые три слагаемых.

[2] К сожалению, это не всегда так. Если начальное приближение выбрано неудачно и значение производной в этой точке близко к нулю, то, вообще говоря, найденный корень может быть не ближайшим к начальному приближению. В качестве примера решите самостоятельно задачу поиска корня уравнения , выбрав в качестве начального приближения число близкое к . Чем ближе к будет выбранное значение, тем более далекий от 0 корень мы будем получать.