русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Полиномы


Дата добавления: 2013-12-23; просмотров: 1386; Нарушение авторских прав


Массивы и классические алгоритмы математики

Полиномом n-й степени называют функцию:

(6.1)

Если рассматривать график этой функции на плоскости, то и - это декартовы координаты точек графика функции. Значения (k из интервала [0,n]) называются коэффициентами полинома. Все они принадлежат одному типу и при программной работе с полиномами представляются одномерным массивом с n+1 элементами.

Если задан массив коэффициентов полинома , то вычислить значение полинома в точке не представляет особой сложности. Но ни один уважающий себя программист не позволит себе вычислять значение полинома, буквально пользуясь схемой 6.1, требующей n-1 операций возведения в степень, n операций умножения и n операций сложения. Прекрасный пример того, как можно упростить алгоритм, дает схема Горнера, вообще не требующая возведения в степень. В этой схеме полином представляют в виде:

(6.2)

Удобнее представлять схему Горнера в рекуррентной форме:

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

Если - полином n-й степени с коэффициентами , - полином n-й степени с коэффициентами и , то из этого следует равенство соответствующих коэффициентов:

(6.3)

Многие задачи над полиномами связаны с определением их корней. Напомню, является корнем полинома, если . У полинома n-й степени не более чем действительных корней. Если - нечетно, то полином имеет хотя бы один действительный корень. Все корни полинома принадлежат некоторому конечному интервалу [c, d]. Вне этого интервала поведение полинома определяется его старшим членом - . Для полинома четной степени обе ветви уходят в , если и в , если . Для полинома нечетной степени ветви полинома вне интервала [c, d] разнонаправлены. Если , то правая ветвь уходит в , а левая ветвь - в . Если , то левая ветвь уходит в , а правая ветвь - в .



Когда по каким-либо физическим соображениям интервал [c, d] известен хотя бы приблизительно, задача нахождения корней полинома облегчается, в противном случае она может быть довольно трудной, особенно для случая близко расположенных корней.



<== предыдущая лекция | следующая лекция ==>
Задачи (ввод, вывод и другие простые задачи с массивами) | Алгоритмы нахождения корня полинома


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.002 сек.