Ввести с клавиатуры вещественные коэффициенты многочлена и значение x вывести значение многочлена

Обновлено: 08.07.2024

Коэффициенты многочлена хранятся в массиве a: array [0..n] of integer n – натуральное число, степень многочлена). Вычислить значение этого многочлена в точке x (т. е. Y:= a[n]*(x в степени n)+. +a[1]*x+a[0]). (Используйте схему Горнера) Обьясните пожалуйста что это за схема горнера и с чем ее едят, ибо я вообще не понимаю сути задачи.

Вычислить значение многочлена - Turbo Pascal

Помогите пожалуйста Вычислить значение многочлена для заданного вещественно- го x двумя способами: суммируя элементы по возрастанию степе- ни x и по схеме Горнера. Сравнить количество арифметических операций в том и другом случае. 12) 5x^8+3,4x^7-3x^6+1,2x^5+14x^3+x^2+x+1.

Вычислить значение многочлена для заданного вещественного x - Turbo Pascal

Вычислить значение многочлена для заданного вещественно- го x двумя способами: суммируя элементы по возрастанию степе- ни x и по схеме Горнера. Сравнить количество арифметических операций в том и другом случае. y=(5*(x^8))+(3.4*(x^7))-(3*(x^6))+(1.2*( x^5))+(14*(x^3))+(x^2)+x+1.

Интерполяция и аппроксимация функций - MathCAD

Здравствуйте! Помогите решить задачу в MathCAD. По заданным экспериментальным точкам построить: 1) канонический интерполяционный многочлен и вычислить его значение в точке z; 2) интерполяционный многочлен Лагранжа и вычислить его значение в точке z; 3) методом наименьших квадратов (МНК) определить коэффициенты приближающей функции и вычис.

Вычислить значение функции - Turbo Pascal

Вычислить значение функции при помощи суммы ряда с точностью (E) . Сравнить полученное значение суммы с результатом вычисления стандартной функции. Миниатюры.

Вычислить значение выражения, записанного строкой. - Turbo Pascal

Задана строка S, содержащая цифры и знаки «+» и «-». Вычислить значение данного выражения. За ранее спасибо.

Вычислить корень уравнения на заданном отрезке [a, b] - Turbo Pascal

Вычислить корень уравнения на заданном отрезке [a, b] с точностью 10^-6, используя следующий метод: М = 1 – метод поло- винного деления, М = 2 – метод касательных, М = 3 – метод хорд. Вычисление значения функции в точке и вычисление корня уравнения оформить в виде отдельных функций. Значения параметра s: si [s1; s2], si = s1 + ids, i = 0.

Процедуры и функции: Используя процедуру, вычислить значение - Turbo Pascal

Используя процедуру, вычислить значение выражения. Дано выражение: y=a[SUB]1[/SUB]x[SUP]4[/SUP]+a[SUB]2[/SU B]x[SUP]3[/SUP]+a[SUB]3[/SUB]x[SUP]2[/SU P]+a[SUB]4[/SUB]x+a[SUB]5[/SUB] Подскажите пожалуйста,срочно нужно.

Вычислить приближенное значение интеграла - Turbo Pascal

Cоставить функцию для вычисления приближенного значение интеграла Вложение 260379 Миниатюры.

Вычислить значение функции при заданном значении аргумента - Turbo Pascal

Написать программы для решения предложенных ниже задач. Пользователь вводит допустимое значение х, программа выдает результат. у=1+x[SUP]2[/SUP].

Вычислить корень уравнения на заданном отрезке [a, b] - Pascal ABC

Вычислить значения 1й и 2й производной в точке х=0.1 методом Лагранжа - MathCAD

Дана функция y(x)=exp((-x^2)/2), x:=[0..1] 1. Получить таблицу значений с шагом h=0.2 (в принципе, сделал, но не программно, а тупо, прибавляя h "вручную"). 2.С помощью полинома Лагранжа вычислить значения 1й и 2й производных в точке х=0.1. Оценить погрешность. Приближенное значение ф-ций в заданной точке Лагранжем я находил, но.

Динамические переменные - Free Pascal

Вычислить значение многочлена P(x) = a0 + a1 x + a2 x^2 + . + an x^n для заданного целого x (значения коэффициентов a0, a1. an вводятся с клавиатуры и динамически размещаются в памяти). P.S. "x" указывается в степени, а у "а" номер его;.

четные\нечетные числа и задачка - Turbo Pascal

Здравствуйте, буду благодарна. 1) Дано натуральное семизначное чило N. Вычислить количество четный и нечетных цифр числа. Вывести на экран последовательность из четных цифр. 2) для заданного числа а вычислить значение суммы: 1-(а/2!)+(3а/4!)-(5а/6!)+. +(17а/18!).. .

Разработать алгоритм табулирования функции. Вычислить значение функции - Turbo Pascal

Прошу помочь с паскалем. Задание: разработать алгоритм табулирования функции. Вычислить значение функции при изменении аргумента в ука- занном диапазоне и с заданным шагом. Организовать вывод значения аргумента и вычисленного значения функции в виде таблицы: Миниатюры.

вычислить значение логического выражения - Turbo Pascal

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

Вычислить и вывести на экран в виде таблицы значения функции - Turbo Pascal

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

Дано вещественное число X и целое число N (N> 0). Найти значение указанного выражения - Turbo Pascal

Дано вещественное число X и целое число N (N > 0). Найдите значение выражения X-^/3!+^/5!-. +^* ^/(2*N+1) !. Полученное число является приближённым значением функции sin в точке X. нужно написать программу.

Вычислить значение функции - Pascal (Паскаль)

Вычислить значение функции Z = x1+e[SUP]x2[/SUP], где x1, x2 - корни уравнения A[SUB]i[/SUB]x[SUP]2[/SUP]+B[SUB]i[/SUB] x+C[SUB]i[/SUB] = 0, i = 1,2. N. Коэффициенты уравнения заданы в массивах A [1..N], B [1..n], C [1..N]. Для вычисления корней использовать процедуру.

Обьекты - Pascal ABC

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

Необходимо вычислить значения в точке X - С++ для начинающих

Люди помоги пожалуйста, срочно надо решение, а сам я не знаю как. :cry: Необходимо вычислить значения в точке X. Вычислять с помощью операторов повторения. Изображения.

Значение суммы бесконечного ряда - Turbo Pascal

Есть задание вычислить значение суммы бесконечного ряда [LATEX]S = 2*square bracket*\frac + \frac<3^> + \frac<5^> + \frac<7^> + . *square bracket*[/LATEX] с точностью [LATEX]\varepsilon[/LATEX]. Что означает двойка с квадратными скобками? Сама формула программы, за исключением скобок с двойкой, методом ре.

Вычислить значение функции (программа и блок-схема) - Turbo Pascal

составить алгоритм и программу вычисления функции f(x) при произвольном x; Миниатюры.

Вычислить значение выражения при n равном от 1 до 10 - Pascal (Паскаль)

Здравствуйте! Пожалуйста, помогите решить задачу, сама не справлюсь: Вычислить значение выражения при n равном от 1 до 10. Само выражение во вложении. Благодарю! Изображения.

Рекурсия. Вычислить значение выражения - Pascal ABC

Помогите пожалуйста решить, а то я что то не понимаю. 2. Используя рекурсивную функцию, для заданного натурального N и вещественного x (x > 0) вычислить значение выражения: [LATEX]\sqrt>>[/L ATEX].

Вычислить значение функции Аккермана, используя стек - Pascal (Паскаль)

Задана функция Аккермана: [LATEX]A(n,x,y)= egin & \ n+1 \; < if >\; n=0 \\ & \ x \; < if >\; n=1,\;y=0 \\ & \ 0 \; < if >\; n=2,\;y=0 \\ & \ 1\; < if >\; n=3 \;y=0 \\ & \ 2\; < if >\; n\geq 4, \;y=0 \\ & \ A(n - 1, A(n,x,y - 1), x) \; < if >\; n\neq 1, \;y\neq 0 \end[/LATEX] где n,x,y - целые положительные числа. Вычисли.

Процедуры и функции: Описать функцию Polynom(A,N,X) вещественного типа, находящую значение полинома P в вещественной точке X. - Pascal ABC

Описать функцию Polynom(A,N,X) вещественного типа, находящую значение полинома P в вещественной точке X. Полином P задается параметрами N (степень полинома, 0 N 8) и A (коэффициенты полинома, вещественный массив размера N+1): P(X) = A[1]·XN + A[2]·XN–1 + . + A[N]·X + A[N+1]. Используя эту функцию, найти значения заданного полинома в.

Ввести 3 числа вычислить ||a-b|-c|, не используя стандартные функции. - Turbo Pascal

Ввести 3 числа вычислить ||a-b|-c|, не используя стандартные функции. Вывести полученное значение. Помогите, пожалуйста.

Контрольная работа по Turbo Pascal - Turbo Pascal

Помогите решить контрольную: 1. Дан массив X из 25 элементов. Вычислить: y=25(x[SUB]25[/SUB]*(x[SUB]25[/SUB]-x[SU B]24[/SUB])*(x[SUB]25[/SUB]-x[SUB]24[/SU B]+x[SUB]23[/SUB])*. *(x[SUB]25[/SUB]-x [SUB]24[/SUB]+x[SUB]23[/SUB]-. +x[SUB]1 [/SUB])) 2. Дан массив X (25 элементов). Вычислить: y[SUB]i[/SUB]=(x[SUP]2[/SUP][SUB]i[/SUB] +3*x[SUB]i[/SUB.

Использование комбинированного и множественного типа - Pascal ABC

Помогите с программой и блок схемой а. Вычислить значение квадратного трехчлена az2+bz+c с комплексными коэффициентами а, Ь, с в комплексной точке z. Действия с комплексными числами оформить подпрограммами. б. С клавиатуры вводятся неотрицательные целые числа, не превышающие 255. Признак конца ввода - ноль. Получить множество общих делите.

задача паскаль.вычислить значение функции на заданном интервале - Pascal ABC

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

Составить описание классов многочленов от одной переменной, задаваемых степенью многочлена и массивом коэффициентов. Предусмотреть методы для вычислен - Pascal (Паскаль)

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

Найти значение многочлена по схеме Горнера - C для начинающих

Найти значение многочлена y=11*x^10+10*x^9+. +2*x+1 по схеме Горнера.На языке Си.

Вычислить сумму - Turbo Pascal

Помогите, пожалуйста, вычислить сумму: 1-x^2/2!+x^4/4!+. +((-1)^n)*(x^2n)/(2n) !+.

Дан вещественный вектор А [1.n] - Turbo Pascal

Дан вещественный вектор А [1..n]. Заменить все отрицательные элементы вектора на их квадраты и отсортировать в порядке возрастания. Вычислить среднее арифметическое максимального и минимального элементов. Вывести на экран отсортированный массив и вычисленное значение.

динамические массивы - Turbo Pascal

1. Создать вещественный массив из 20000 чисел. a. Заполнить его случайными числами в диапазоне от 0 до 1. b. Вычислить среднее значение элементов массива с номерами, кратными 13. Очистить динамическую память. c. Создать целочисленный массив из 100х100 чисел. Заполнить его случайными числами в диапазоне от 10 до 30. d. Записать полученный.

Вычислить произведение членов ряда - Turbo Pascal

Вычислить произведение (1-1/2)*(1-1/3)*(1-1/4)*. *(1-1/n).

составить блок-схему и программу для задачи: - Turbo Pascal

Выбрать алгоритм, составить его блок-схему и программу, в которой: 1) вычислить в точках xi=a+(i-1)h, i=1,2, … n+1, h=(b-a)/(n+1) промежутка [a;b] значения элементов массива yi=f(xi), где f(x) – указанная функция: y=(〖sin〗^2 |x|/2+3^(1/(x-1)))/√(6&x^4-16)*√(1-lnx) где x∈[2.2;2.6],n=4 2) среди элементов массива yi найти первые два y1min, y.

Вычислить интеграл - Pascal ABC

Вычислить интеграл dxxf )( заданным методом, воспользовавшись критерием двойного пересчета с точностью 10–6: M = 1 – метод левых прямоугольников, М = 2 – метод правых прямо- угольников, М = 3 – метод средних прямоугольников, М = 4 – ме- тод трапеции, М = 5 – метод Симпсона. Вычисление значения функции в точке оформить в виде функции, вычи.

Нахождение элементов многочлена - Pascal ABC

сост-ть программу, кот-я запрашивает у пользователя целочисленные корни многочлена 4й степени и, исп-я т. Виетта, находит его коэф-ты. Вывести результат в виде таблицы: 1я сторона-степени, 2я-коэф при степ х.

Включение вашего ID publisher AdSense Это просто и быстро, используя соответствующую форму.

Найти коэффициенты многочлена
Вот условие задачи: Даны действительные числа а0 . а6 . Получить для х=1,3,4 значения.

Найти коэффициенты k-ого многочлена Чебышева
Посмотрела по форуму - не нашла такой темы. Помогите, пожалуйста, с программой на С. Что-то никак.

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

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

Собственно решение выделено горизонтальными отбивками. Остальное - подготовка входных данных, вывод на консоль и проверка результата.

Решение

Без сдвигов, битовых операций, модных алгоритмов и магии. Но тоже вроде работает.

valen10, красивое решение.

Есть один маленький недостаток: время выполнения. Оно увеличивается примерно в два раза при увеличении степени полинома на 1. Ваш алгоритм на моём железе вычисляет коэффициенты полинома 14-й степени примерно за 1 миллисекунду, 30-й степени - за 51 секунду, 31-й - 103 секунды и т.д.

Моё решение вычисляет полином 30-й степени за 5 микросекунд, а 50-й - за 11 микросекунд.

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

Интереса ради проверил у себя 30 степень - 2,9 сек. Но быстрый рост функции будет безжалостен к любому процессору, достаточно увеличить степень полинома на 3-4 единицы.

мне решение regio1961 показалось более наглядным
за одно только

Kuzia domovenok, что в этой строке такого особенного? Да, интересный способ посчитать количество установленных битов. Но количество повторов равно количеству единиц. А можно и за фиксированное количество шагов это сделать. Например, для 32-битного целого - за 5 шагов.

Добавлено через 1 минуту
Причем еще более наглядно

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

Что такое массив, определяющий коэффициенты многочлена степени N?
Помогите решить , не могу понять что такое массив ,определяющий коэффициенты многочлена степени N .

Многочлен степени n задан массивом своих коэффициентов. Подсчитать коэффициенты производной многочлена.
7.2.1. Помогите, пожалуйста, решить задачу в С++. Многочлен степени n задан массивом своих.

Как создать многочлен n-ой степени, где коэффициенты многочлена выводятся через массив?
как создать многочлен н-ой степени где коэффициенты многочлена выводятся через массив

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

Как и обещал, выкладываю решение задач для школьников по C++. На этот раз будут рассмотрены задачи с действительными числами.

Задача №1

Дано положительное действительное число X. Выведите его дробную часть.
Формат входных данных
Вводятся положительное действительное число.
Формат выходных данных
Выведите ответ на задачу.

Решение

Задача №2

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

Решение

Задача №3

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

Решение

Задача №4

Процентная ставка по вкладу составляет P процентов годовых, которые прибавляются к сумме вклада в конце года. Вклад составляет X рублей Y копеек. Определите размер вклада через год.
При решении этой задачи нельзя пользоваться условными инструкциями и циклами.
Формат входных данных
Программа получает на вход целые числа P, X, Y.
Формат выходных данных
Программа должна вывести два числа: величину вклада через год в рублях и копейках. Дробная часть копеек отбрасывается.

Решение

Задача №5

Процентная ставка по вкладу составляет P процентов годовых, которые прибавляются к сумме вклада через год. Вклад составляет X рублей Y копеек. Определите размер вклада через K лет.
Формат входных данных
Программа получает на вход целые числа P, X, Y, K.
Формат выходных данных
Программа должна вывести два числа: величину вклада через K лет в рублях и копейках. Дробное число копеек по истечение года отбрасывается. Перерасчет суммы вклада (с отбрасыванием дробных частей копеек) происходит ежегодно.
Примечание
В этой задаче часто возникают проблемы с точностью. Если они возникли у вас - попробуйте решить задачу в целых числах.

Решение

Задача №6

Определите среднее значение всех элементов последовательности, завершающейся числом 0.
Формат входных данных
Вводится последовательность целых чисел, оканчивающаяся числом 0 (само число 0 в последовательность не входит, а служит как признак ее окончания).
Формат выходных данных
Выведите ответ на задачу.

Решение

Задача №7

Дана последовательность натуральных чисел $%x_1, x_2, . x_n$%. Стандартным отклонением называется величина $$sigma = sqrt>$$
где $$s = frac$$ - среднее значение последовательности.
Определите стандартное отклонение для данной последовательности натуральных чисел, завершающейся числом 0.
Формат входных данных
Вводится последовательность целых чисел, оканчивающаяся числом 0 (само число 0 в последовательность не входит, а служит как признак ее окончания). В последовательности не менее двух чисел до 0.
Формат выходных данных
Выведите ответ на задачу.

Решение

Задача №8

Дан многочлен $%P(x)=a_nx_n + a_x_+ . + a_1x + a_0$% и число $%x$%. Вычислите значение этого многочлена, воспользовавшись схемой Горнера:
$$P(x)=(. (((a_nx + a_)x + a_)x + a_). )x + a_0$$
Формат входных данных
Сначала программе подается на вход целое неотрицательное число n ≤ 20, затем действительное число x, затем следует $%n+1$% вещественное число — коэффициенты многочлена от старшего к младшему.
Формат выходных данных
Программа должна вывести значение многочлена.

Решение

Задача №9

Даны действительные коэффициенты $%a, b, c$%, при этом $%a ≠ 0$% . Решите квадратное уравнение $%ax^2 + bx + c = 0$% и выведите все его корни.
Формат входных данных
Вводятся три действительных числа.
Формат выходных данных
Если уравнение имеет два корня, выведите два корня в порядке возрастания, если один корень — выведите одно число, если нет корней — не выводите ничего.

Решение

Задача №10

Даны действительные коэффициенты a, b, c. Решите уравнение $%ax^2 + bx + c = 0$% и выведите все его корни.
Формат входных данных
Вводятся три действительных числа.
Формат выходных данных
Если данное уравнение не имеет корней, выведите число 0.
Если уравнение имеет один корень, выведите число 1, а затем этот корень.
Если уравнение имеет два корня, выведите число 2, а затем два корня в порядке возрастания.
Если уравнение имеет бесконечно много корней, выведите число 3.

Решение

Задача №11

Даны вещественные числа a, b, c, d, e, f. Известно, что система линейных уравнений $$eginax+by = e\cx+dy=fend$$ имеет ровно одно решение. Выведите два числа x и y, являющиеся решением этой системы.
Формат входных данных
Вводятся шесть чисел - коэффициенты уравнений системы.
Формат выходных данных
Выведите ответ на задачу.

Решение

Задача №12

Даны вещественные числа a, b, c, d, e, f. Решите систему линейных уравнений $$eginax+by = e\cx+dy=fend$$
Формат входных данных
Вводятся шесть чисел - коэффициенты уравнений системы.
Формат выходных данных
Вывод программы зависит от вида решения этой системы.
Если система не имеет решений, то программа должна вывести единственное число 0.
Если система имеет бесконечно много решений, каждое из которых имеет вид $%y=kx+b$%, то программа должна вывести число 1, а затем значения $%k$% и $%b$%.
Если система имеет единственное решение $%(x_0, y_0)$%, то программа должна вывести число 2, а затем значения $%x_0$% и $%y_0$%.
Если система имеет бесконечно много решений вида $%x=x_0$%, $%y$% — любое, то программа должна вывести число 3, а затем значение $%x_0$%.
Если система имеет бесконечно много решений вида $%y=y_0$%, $%x$% — любое, то программа должна вывести число 4, а затем значение $%y_0$%.
Если любая пара чисел $%(x, y)$% является решением, то программа должна вывести число 5.

Не занимаясь реализацией этого алгоритма, давайте оптимизируем его. Например, пусть нам дан многочлен третьей степени a₃x 3 + a₂x 2 + a₁x + a₀. Вынесем за скобки общий множитель x при слагаемых, в которых это возможно. Получим: (a₃x 2 + a₂x + a₁)x + a₀. Вынесем за скобки x также и в полученном выражении со скобками, в итоге получим: ((a₃x + a₂)x +a₁)x + a₀.

Полученную форму записи называют схемой Горнера. Очевидно, что она существует для многочлена любой степени.

Итак, имея n = 3 и коэффициенты a₃, a₂, a₁ и a₀, мы можем посчитать его значение с помощью n операций умножения и nопераций сложения, а это значит, что для вычисления требуется порядка 2n операций и алгоритм имеет линейную асимптотическую сложность O(n), что демонстрирует очевидное преимущество перед предыдущим решением.

Посмотрим, как может выглядеть цикл, в котором вычисляется значение многочлена в точке. Для этого немного изменим представление в виде схемы Горнера, не меняя при этом значения многочлена: (((0x + a₃)x + a₂)x + a₁)x + a₀.

Теперь нам требуется n + 1 операций, однако заведя переменную res для накопления результата, которая перед входом в цикл будет равна 0, мы можем, вводя коэффициенты a₃, a₂, a₁ и a₀, посчитать значение многочлена в одном цикле:

for i := 1 to n + 1 do begin

Примечание: оператор read нужен нам для того, чтобы можно было вводить коэффициенты через пробел, а не черезEnter.

Теперь разберем сам цикл. На первом шаге мы получаем в res значение выражения 0x + a₃ = a₃, на втором – a₃x + a₂, на третьем – (a₃x + a₂)x + a₁, на четвертом – ((a₃x + a₂)x + a₁)x + a₀. Как видно, формула полностью восстановилась, причем вычисление идет от наиболее вложенных скобок к верхним уровням.

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

При вычислении значений многочленов очень широкое применение получило правило Горнера. Метод назван в честь британского математика Уильяма Джорджа Горнера.
В соответствии с этим правилом многочлен n-й степени:

Вычисление значения многочлена производится в порядке, определяемом скобками. Что имеем? Чтобы вычислить многочлен по схеме Горнера, надо выполнить n умножений и n-k сложений (здесь k – число коэффициентов многочлена, равных 0). Если , то умножений будет n-1.
Можно показать, что для вычисления многочленов, общего вида нельзя построить схему более экономичную по числу операций, чем схема Горнера.
Самая большая привлекательность схемы Горнера состоит в простоте алгоритма для вычисления значения многочлена.

При вычислении многочленов специального вида может потребоваться меньшее число операций, чем при применении универсальной схемы Горнера. Например, вычисление степени по схеме Горнера означает последовательное перемножение n множителей и требует n-1 умножение. Однако каждый первый читатель скажет, что для вычисления, например, нужно последовательно вычислить , , , т.е. выполнить всего 3 умножения вместо 7.

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

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

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

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

Имеем следующий многочлен:

Для вычислений используем следующие вспомогательные многочлены:

Коэффициенты определяются методом неопределенных коэффициентов исходя из условия . Из последнего условия составляем систему уравнений, приравнивая коэффициенты при равных степенях многочленов.

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

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

Наконец-то, добрался и до наших математиков.

Ю.Л. Кетков дал общее представление многочлена n-й степени для n>5, всегда приводящее к действительным выражениям и требующее для вычисления многочлене n-й степени выполнения [(n+1)/2]+[n/4] умножений и n+1 сложений.

Например, при n=2k схема Кеткова сводится к нахождению многочленов:

где , при k –четном, и , , если k нечетное (k>2).

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

Э. Белага в своих работах дал строгое доказательство невозможности построения схемы вычисления произвольных многочленов n-й степени, использующей на втором этапе меньше, чем [(n+1)/2]+1 умножений и n сложений.

В.Я. Пан занимался вопросами оптимального вычисления многочленов. В частности, им предложено несколько схем для вычисления действительных многочленов, которые весьма близко подобрались к оценкам Э. Белаги. Приведу некоторые схемы Пана для действительных многочленов.
1. Схема для вычисления многочленов четвертой степени.
Рассматривается многочлен .

Представим в виде:

2. Схема для вычисления , .
Строим вспомогательные многочлены , , :

Для вычисления значения многочлена используем выражения:

Эта схема на втором этапе требует умножения и сложения.

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

У В.Я. Пана существуют и другие схемы для вычисления многочленов, в том числе и для комплексных.

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

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

Читайте также: