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

UptoLike

ВУЗ: 

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

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

Рубрика: 

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

Страницы