Cтраница 2
Использование рядов позволяет свести задачу вычисления значений функции к задаче вычисления значений полинома, и, таким образом, ограничиться выполнением арифметических операций. [16]
Во-вторых, вычисление значений функции в промежуточной точке состоит в вычислении значений полинома третьей степени. [17]
Известным методом преобразования к форме с меньшим числом медленных операций при вычислении значения полинома является схема Горнера. [18]
Для вычисления такого полинома достаточно составить программу для выражения ( Pj Рз) - Вычисление значения полинома производится в цикле, причем число циклов равно степени полинома. Если коэффициенты полинома в оперативной памяти располагаются, начиная с адреса Р, а первой вычисляется внутренняя скобка, то для первого цикла необходимы значения в первую очередь коэффициентов Рл и рз. [19]
Из всего сказанного следует, что даже такая, казалось бы, простая задача, как вычисление значений полинома, в общем случае не имеет пока удовлетворительного решения. [20]
Вычисление значений частотных характеристик для конкретного s 7 со ( а в общем случае s а уш) сводится к вычислению значений полиномов B ( s) и A ( s) с последующим делением полученных комплексных чисел. При этом получаются значения вещественной Р ( о) и мнимой б ( со) частотных характеристик. [21]
В рассмотренных же нами примерах алгоритмов имеются некоторые элементы неточности и произвола. Так, мы говорили об алгоритмах выполнения арифметических операций и в то же время использовали эти операции как достаточно простые в алгоритмах вычисления значения полинома и извлечения квадратного корня. Ясно, что здесь имелись в виду разные исполнители алгоритмов, но это не было оговорено. В примере же алгоритма определения первого вхождения заданной буквы в заданное слово мы предполагали, что исполнитель умеет выполнять операцию различения двух букв. Однако и здесь осталось неясным, будет ли он считать изображения какой-либо буквы в разных шрифтах как одинаковые буквы или разные. Тем не менее и такие не точные алгоритмы оказываются весьма полезными в тех случаях, когда они предназначены не для исполнения, а для информационных целей. [22]
К сожалению, выяснить подлинную вычислительную сложность данной задачи обычно очень трудно. Для большинства практических задач, чтобы судить о качестве алгоритма, приходится полагаться на опыт. Однако иногда можно довольно точно оценить снизу число арифметических операций, требуемых для выполнения вычислений. В этой главе мы изложим некоторые важные результаты этого рода. Например, покажем, что умножение ( пХр) - матрицы на р-вектор требует пр умножений, а вычисление значения полинома я-й степени требует п умножений. Много дополнительных результатов о нижних оценках содержится в упражнениях. [23]