Краткий курс вычислительной математики. Денисова Э.В - 16 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

Составители: 

Рубрика: 

Глава 2
ВЫЧИСЛЕНИЕ ЗНАЧЕНИЙ ФУНКЦИИ
При вычислении с помощью счётных машин значений функций, заданных формулами, далеко не безразлично,
в каком виде записана соответствующая формула. Математически эквивалентные выражения часто
оказываются неравноценными с точки зрения практики вычислений. Дело в том, что основными операциями
большинства вычислительных машин являются сложение, вычитание, умножение и деление. Поэтому
возникает необходимость представить рассматриваемую математическую задачу в виде последовательности
этих элементарных операций. Учитывая ограниченность объёма памяти машины и необходимость экономии
машинного времени, желательно эти операции разбить на повторяющиеся циклы и выбрать соответствующий
алгоритм. Ниже мы рассмотрим приёмы, сводящие вычисление некоторых функций к таким циклам из
элементарных операций.
§ 1. Вычисление значений многочлена. Схема Горнера
Пусть дан многочлен
n
-й степени
( )
1
01
nn
n
x ax ax aP
−
= + ++
с действительными коэффициентами
k
a
( )
0,1, ,kn=
, и пусть требуется найти значение этого
многочлена при
x
ξ
=
(
)
1
01
nn
n
aa a
P
ξξξ
−
= + ++
(2.1)
Вычисление значения
(
)
P
ξ
удобнее всего производить следующим образом. Представим
выражение
( )
1
01
nn
n
aa a
P
ξξξ
−
= + ++
(2.1) в виде
( )
( )
( )
( )
( )
01 2 3
.
n
aa a a a
P
ξ ξξξξ
= + + + ++
Если ввести числа
(2.2)
то
( )
.
n
bP
ξ
=
Таким образом, вычисление значения многочлена
( )
Px
при
x
ξ
=
сводится к повторению следующей
совокупности элементарных операций:
( )
1
1, 2, , .
kk k kk
cb bac k n
ξ
−
= =+=
Нетрудно показать, что числа
0 01 1
,, ,
n
b ab b
−
=
являются коэффициентами многочлена
( )
Qx
, полученного в
качестве частного при делении данного многочлена
( )
Px
на двучлен
x
ξ
−
, а
( )
n
bP
ξ
= −
остаток от
деления.
Таким образом, можно, не производя деления, определять коэффициенты частного
( )
Qx
, а также остаток
( )
P
ξ
. Числа
0, 1,
,
n
bb b
обычно находят, пользуясь известной схемой Горнера
( )
0 12
01 1
00 1 2
n
n
n
a aa a
bb b
ba b b bP
ξ
ξξ ξ
ξ
−
+
= =
Вычисление значений многочлена
( )
n
Px
по схеме Горнера требует выполнения
n
умножений и
nk−
сложений, где
k −
число коэффициентов
i
a
, равных нулю. Если
0
1a =
, то требуется выполнить
1n −
умножений. Показано, что для многочленов общего вида нельзя построить схему более экономную в смысле
числа операций, чем схема Горнера.
15

Страницы