V Международная студенческая научная конференция Студенческий научный форум - 2013
«ОЦЕНКА ВРЕМЕННОЙ СЛОЖНОСТИ ПАРАЛЛЕЛЬНОГО КУСОЧНО-ПОЛИНОМИАЛЬНОГО ВЫЧИСЛЕНИЯ ФУНКЦИЙ»
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
В данной статье рассматривается кусочно-полиномиальное вычисления функции на основе интерполяционного полинома Ньютона.
Схемы кусочно-полиномиальной аппроксимации часто рассматривали в качестве оптимальных машинных алгоритмов вычисления функций [3, 4]. Такое представление об оптимальности обусловлено следующими качествами данных схем. Аппроксимирующий полином строится на каждом подынтервале, объединение подынтервалов покрывает основной интервал. Длину подынтервала можно выбрать такой малой, чтобы приближение на нем не превышало априори заданной границы погрешности. На этой основе возможно достигать высокой точности приближения полиномом малой степени. Именно это качество определяет преимущество таких схем и сравнительную оптимальность их временной сложности.
Выбор кусочно-полиномиальной аппроксимации на основе полинома Ньютона позволит сохранить общность схемы интерполяции, одновременно с этим именно данный подход отличается сравнительно высокой точностью вычисления функций. Сочетание общности и точности аппроксимации функций с минимальной временной сложностью является отличительным качеством кусочно-полиномиальной аппроксимации функций на основе полинома Ньютона.
Для ускоренного вычисления функций применяются параллельные алгоритмы вычисления аппроксимирующих полиномов.
Ускорение в этом случае достигается не за счет сокращения общего количества операций, а за счет параллельного выполнения взаимно независимых частей аппроксимирующего функцию алгоритма при условии готовности значений данных. Многочисленные примеры параллельных алгоритмов вычисления полиномов представлены в [5 – 10].
Все параллельные алгоритмы здесь и в дальнейшем описываются на модели неветвящейся параллельной программы. Понятие неветвящейся параллельной программы как последовательности параллельных арифметических команд заимствуется из [11]. При этом арифметические команды отождествляются с конкретными арифметическими операциями. Временная сложность алгоритма понимается как длительность выполнения представляющей его неветвящейся параллельной программы.
Более точно в дальнейшем временная сложность алгоритма (кратко, иногда, – время) измеряется количеством последовательных шагов его выполнения, при этом будет учитываться вид операции на каждом последовательном шаге. Временная сложность будет обозначаться , где – количество процессоров.
Конкретная программная реализация неветвящихся параллельных программ в данной модели не учитывается, не учитывается отображение на архитектуру параллельной вычислительной системы. Модель абстрагируется от способов обмена: предполагается [11], что параллельная вычислительная система работает как идеальный параллельный процессор [12].
Для излагаемой ниже кусочно-полиномиальной схемы вычисления функций на основе интерполяционного полинома Ньютона в условиях вариации степени полинома и количества подынтервалов ставится задача представить эту схему в максимально параллельной форме, а также дать оценки ее временной сложности на модели неветвящихся параллельных программ.
Описание метода. Рассматривается функция одной действительной переменной вида
, (1)
где промежуток произвольно фиксирован. Выбирается система непересекающихся подынтервалов равной длины, объединение которых совпадает с :
(2)
где .
Таким образом,
(3)
Для каждого отдельно взятого подынтервала с номером из (2), (3) строится интерполяционный полином Ньютона с равноотстоящими узлами степени , где выбирается минимальным для достижения заданной точности приближения одновременно на всех подынтервалах. При этом полином Ньютона в общем случае преобразуется по дистрибутивности с приведением подобных так, что в результате преобразования на -м подынтервале принимает канонический вид полинома с заданными значениями числовых коэффициентов от одной переменной:
, (4)
где ,
В (3) индекс коэффициента совпадает с номером подынтервала, индекс соответствует аппроксимируемой функции.
Построение (4) выполняется для всех подынтервалов, причем так, чтобы на каждом из них не превышалась заданная граница погрешности
, . (5)
Практическую проверку выполнения неравенства (5) можно выполнить по системе проверочных точек. Будем считать, что число проверочных точек одинаково на каждом подынтервале и задается в виде числового параметра равного . В приводимой ниже программе число проверочных точек задается в виде , где – длина подынтервала, – расстояние между проверочными точками. Таким образом, в программе . В целом этот параметр зависит от априори заданной точности, языка программирования, формата данных, и технических целей.
Полином Ньютона с равноотстоящими узлами степени на -м подынтервале для функции (1) записывается в виде
где – конечная разность -го порядка в точке , – расстояние между узлами интерполяции.
, (6)
где – границы -го подынтервала.
Равностоящие узлы интерполяции на текущем шаге можно записать в виде
. (7)
Приняв обозначения
, (8)
интерполяционную формулу Ньютона можно записать в виде
(9)
Чтобы привести (9) к виду, аналогичному (4), можно предварительно вычислить конечные разности первого порядка и конечные разности -го порядка , а затем –
. (10)
С использованием (10) из (9) принимает вид
. (11)
При этом всюду в дальнейшем полагаем ,
Ниже приведена блок-схема построения кусочно-полиномиального приближения функции общего вида на основе интерполяционного полинома Ньютона.
Рис. 1. Блок-схема построения кусочно-полиномиального приближения
функций
Программа кусочно-полиномиального вычисления функции на основе интерполяционного полинома Ньютона (здесь и в дальнейшем используется язык программирования Object Pascal системы Delphi) заимствуется из [13]:
program Nuton;
{$APPTYPE CONSOLE}
Uses SysUtils;
const eps=1.0e-12; nn=20;
type mass1=array[0..nn] of extended;
mass2=array[0..nn,0..nn] of extended;
var j,k,n,l,r,kk,k1,p1,c:integer;
a00,b00,a0,b0,x1,t,h,h1,s,p,hh:extended;
x,b,y,a: mass1;
e,d,dy: mass2;
condition: boolean;
function fnf(x:extended):extended;
begin fnf:=1/(x) end;
procedure Konech_Raznoct(var dy:mass2);
begin
for j:=0 to n do x[j]:=a00+j*hh;
for j:=0 to n-1 do dy[1,j]:=fnf(x[j+1])-fnf(x[j]);
for k1:=2 to n do
for j:=0 to n-k1 do dy[k1,j]:=dy[k1-1,j+1]-dy[k1-1,j] end;
procedure Vieta(var d:mass2);
begin
e[1,1]:=1; e[1,0]:=-y[0];
for kk:=2 to n do begin
e[kk,0]:=-e[kk-1,0]*y[kk-1];
for l:=1 to kk-1 do e[kk,kk-l]:=e[kk-1,kk-l-1]-e[kk-1,kk-l]*y[kk-1];
e[kk,kk]:=e[kk-1,kk-1] end;
for l:=0 to j do d[l,j]:=e[j,l] end;
begin
writeln (eps:10);
writeln ('n':5,'k':5,'2^k':15,'prib pol':25);
a0:=1/2; b0:=1;
k:=0; repeat
n:=1; repeat
condition:=true;
h:=(b0-a0)/exp(k*ln(2));
a00:=a0; b00:=a00+h;
while a0015;
k:=k+1
until k>17;
readln
end.
приближенное значение функции
в проверочных точках
8 0 1.000000E+0000 8.41470984807897E-0001
7 1 2.000000E+0000 8.41470984807897E-0001
6 2 4.000000E+0000 8.41470984807897E-0001
5 3 8.000000E+0000 8.41470984807897E-0001
4 4 1.600000E+0001 8.40061095850306E-0001
4 5 3.200000E+0001 8.41470984807897E-0001
4 6 6.400000E+0001 8.41119047188088E-0001
3 7 1.280000E+0002 8.41470984807897E-0001
3 8 2.560000E+0002 8.41470984807897E-0001
3 9 5.120000E+0002 8.41470984807897E-0001
2 10 1.024000E+0003 8.41470984807897E-0001
2 11 2.048000E+0003 8.41448999154129E-0001
2 12 4.096000E+0003 8.41470984807897E-0001
2 13 8.192000E+0003 8.41465488525081E-0001
2 14 1.638400E+0004 8.41470984807897E-0001
2 15 3.276800E+0004 8.41469610745356E-0001
2 16 6.553600E+0004 8.41470984807897E-0001
2 17 1.3107200E+0005 8.41470641292772E-0001
Примеры вычисления функции на основе интерполяционного полинома Ньютона. Результаты программной реализации метода аппроксимации функции на основе полинома Ньютона сведены в таблицы.
Таблица 1
Степени интерполяционного полинома Ньютона,
аппроксимирующего функцию ,
по кусочно-полиномиальной схеме
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
||
|
10-4 |
7 |
5 |
4 |
3 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
10-5 |
8 |
6 |
4 |
4 |
3 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
10-6 |
10 |
7 |
5 |
4 |
3 |
3 |
2 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
10-7 |
12 |
8 |
6 |
5 |
4 |
3 |
3 |
2 |
2 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
10-8 |
10 |
7 |
6 |
4 |
4 |
3 |
3 |
3 |
2 |
2 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
||
|
10-9 |
11 |
8 |
6 |
5 |
4 |
4 |
3 |
3 |
2 |
2 |
2 |
2 |
2 |
2 |
1 |
1 |
1 |
||
|
10-10 |
12 |
9 |
7 |
6 |
5 |
4 |
4 |
3 |
3 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
1 |
||
|
10-11 |
9 |
8 |
6 |
5 |
4 |
4 |
4 |
3 |
3 |
3 |
2 |
2 |
2 |
2 |
2 |
2 |
|||
|
10-12 |
11 |
8 |
7 |
6 |
5 |
4 |
4 |
4 |
3 |
3 |
3 |
2 |
2 |
2 |
2 |
2 |
|||
|
10-13 |
12 |
9 |
7 |
6 |
6 |
5 |
4 |
4 |
3 |
3 |
3 |
3 |
2 |
2 |
2 |
2 |
|||
|
10-14 |
12 |
10 |
8 |
7 |
6 |
5 |
4 |
4 |
4 |
3 |
3 |
3 |
3 |
2 |
2 |
2 |
|||
|
10-15 |
10 |
9 |
7 |
6 |
6 |
5 |
4 |
4 |
4 |
3 |
3 |
3 |
3 |
2 |
2 |
||||
|
10-16 |
12 |
10 |
8 |
7 |
6 |
5 |
5 |
4 |
4 |
3 |
3 |
3 |
3 |
3 |
2 |
||||
|
10-17 |
12 |
10 |
8 |
7 |
6 |
5 |
5 |
4 |
4 |
4 |
4 |
3 |
3 |
3 |
3 |
||||
|
10-18 |
12 |
9 |
8 |
6 |
5 |
5 |
4 |
4 |
4 |
4 |
3 |
3 |
3 |
||||||
Во входном столбце таблицы обозначает априори задаваемую границу погрешности. Во входной строке задает показатель степени в количестве подынтервалов из (2), (3). На пересечении строки, содержащей , и столбца, содержащего , указывается минимальное значение степени интерполяционного полинома Ньютона, при которой функция в заголовке таблицы аппроксимируется полиномом данной степени с точностью до на каждом из подынтервалов.
Пустующая клетка означает, что в используемой версии языка программирования граница погрешности оказалась недостижимой для данного числа подынтервалов ни при одном значении .
Как видно из таблицы, для границы погрешности достигается третья степень интерполяционного полинома. Это означает, что функцию можно приближенно вычислить с точностью .
Ниже приводятся результаты работы программы для суперпозиции элементарных функций.
Таблица 2
Степени интерполяционного полинома Ньютона,
аппроксимирующего функцию ,
по кусочно-полиномиальной схеме
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
||
|
10-4 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
10-5 |
4 |
3 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
10-6 |
6 |
5 |
3 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
10-7 |
8 |
6 |
4 |
3 |
3 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
10-8 |
10 |
7 |
5 |
4 |
3 |
2 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
10-9 |
11 |
8 |
6 |
5 |
4 |
3 |
3 |
2 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
10-10 |
9 |
7 |
6 |
4 |
4 |
3 |
3 |
2 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
||
|
10-11 |
11 |
8 |
6 |
5 |
4 |
3 |
3 |
3 |
2 |
2 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
||
|
10-12 |
12 |
9 |
7 |
5 |
5 |
4 |
4 |
3 |
3 |
2 |
2 |
2 |
2 |
2 |
2 |
1 |
1 |
||
|
10-13 |
9 |
8 |
6 |
5 |
4 |
4 |
4 |
3 |
3 |
2 |
2 |
2 |
2 |
2 |
2 |
1 |
|||
|
10-14 |
11 |
8 |
7 |
6 |
5 |
4 |
4 |
3 |
3 |
3 |
3 |
2 |
2 |
2 |
2 |
2 |
|||
|
10-15 |
12 |
9 |
7 |
6 |
5 |
5 |
4 |
4 |
3 |
3 |
3 |
2 |
2 |
2 |
2 |
2 |
|||
|
10-16 |
12 |
10 |
8 |
7 |
6 |
5 |
4 |
4 |
3 |
3 |
3 |
3 |
3 |
2 |
2 |
2 |
|||
|
10-17 |
10 |
9 |
7 |
6 |
6 |
5 |
4 |
4 |
3 |
3 |
3 |
3 |
2 |
2 |
2 |
||||
|
10-18 |
8 |
7 |
6 |
5 |
5 |
4 |
4 |
3 |
3 |
3 |
3 |
3 |
2 |
||||||
Из таблицы видно, что аппроксимация функции интерполяционным полиномом Ньютона, например, второй степени обеспечивает точность порядка
Временная сложность кусочно-полиномиального вычисления функции. Используется модель неветвящихся параллельных программ без учета обмена, согласно которой, как отмечалось, временная сложность (время) выполнения алгоритма измеряется числом последовательных шагов и обозначается где – количество процессоров. Основные вариационные особенности рассматриваемых алгоритмов заимствуются из [14].
Прежде всего, целесообразно принять во внимание случай аппроксимации часто встречающейся функции. Например, в случае если это стандартная или элементарная функция. Или же, если эта функция повторяется в процессе численного моделирования. В этих случаях коэффициенты аппроксимирующего полинома вычисляются априори для всех подынтервалов, хранятся в виде массива в памяти компьютера, при вычислении функции по значению аргумента дешифрируется номер подынтервала, который является математическим адресом соответственного набора коэффициентов полинома, аппроксмирующего на этом подынтервале функцию.
При аппроксимации полиномом из (9) функции , , выполняется следующая дешифрация номера подынтервала: , – целая часть числа, , . Значение служит адресом выборки соответственных подынтервалу коэффициентов полинома (4). Листинг программы кусочно-полиномиальной аппроксимации функции на основе интерполяционного полинома Ньютона приводится также в [13].
В рассматриваемом случае при вычислении полинома по схеме Горнера временная сложность вычисления функции составит
,
где – время бинарного умножения и сложения. Отсюда
,
поскольку степень полинома постоянна и фактически минимальна.
При вычислении функции общего вида минимизация временной сложности может быть достигнута за счет преобразования набора алгоритмов к параллельной форме.
Для оценки временной сложности вычисления полинома (9) оценим сложность каждого из слагаемых.
Вычислим конечные разности по максимально параллельной форме и затем приведем подобные на основе дистрибутивности. Требуемое вычисление можно осуществить с помощью известного выражения конечных разностей через значения функции [15]:
,
или
(12)
где – биноминальные коэффициенты.
Во-первых, можно считать априори вычисленными и хранимыми в памяти компьютера для всех и , поскольку значения биноминальных коэффициентов не зависят от вида полинома и аппроксимируемой им функции.
В таком случае можно представить в виде
где имеют известные значения
Более того, таким путем можно вычислить сразу из (10), априори выполнив по дистрибутивности деление биномиальных коэффициентов на факториал:
(13)
где .
Тогда правая часть (13) вычисляется путем одновременного умножения коэффициентов на значения функции , за время бинарного арифметического умножения обозначенного Для вычислений потребуется количество процессоров равное .
После этого количество слагаемых (13) будет равно . Их сумма параллельно вычисляется по схеме сдваивания (рис. 2).
Рис. 2. Схема сдваивания
Очевидно, схема на рис. 2 включает не более последовательных шагов, соответственно её временная сложность
где – время бинарного сложения.
Число процессоров не превышает количества на первом шаге и равно . Это число меньше требуемого для парных умножений в (13), поэтому окончательная оценка времени вычисления из (13) примет вид
, (14)
что с точностью до эквивалентных величин по порядку роста можно записать в виде
. (15)
Значения в (9) требуется получать одновременно для
Способ заключается в том, чтобы повторить схему сдваивания для каждого в отдельности, но реализовать все такие схемы параллельно по всем рассматриваемым .
Максимального значения правая часть (9) достигает при , что влечёт
(16)
где соответственно левым частям (14) число процессоров возрастёт до
(17)
отсюда
Таким образом, имеет место
Лемма 1. В рассматриваемых условиях все конечные разности для полинома (9) на каждом отдельном подынтервале можно вычислить параллельно с временной сложностью
, (18)
что влечет
Замечание 1. Оценка (18) не учитывает время вычисления функции в узлах интерполяции из правой части (12). Если это время учесть, то получится
(19)
где – время вычисления значения функции в одном узле, при этом во всех узлах такие значения вычисляются синхронно в качестве входных для конечных разностей (12) из (9) и для соответственных схем сдваивания. Оценка числа процессоров определяется количеством вычисляемых значений, согласно (12) число этих значений в точности равно . Поскольку , то в (19) значение при данном уточнении не меняется.
Далее оценим сложность вычисления коэффициентов полинома.
Каждое произведение вида
, (20)
представляет собой разложение полинома по корням, имеющим последовательные натуральные значения, не зависящие от вида интерполяционного полинома Ньютона: . Поэтому коэффициенты полинома
, (21)
можно вычислить априори и хранить в памяти компьютера для всех требуемых значений . В частности, это можно сделать по формулам, отличным от формул Виета [16]:
,
где – корни полинома (21) в общем случае. В данном случае . На этой основе в дальнейшем коэффициенты каждого полинома (20) предполагаются уже известными, так что такой полином имеет вид (21) с заданными числовыми значениями коэффициентов.
Возрастание степени интерполяционного полинома приведет к увеличению количества соответствующих коэффициентов, которые также можно сделать хранимыми в памяти компьютера.
Если вернутся к поиску коэффициентов всего полинома Ньютона, то путем приведения подобных и приравнивания одинаковых коэффициентов в левых и правых частях (11) получится:
.
Отсюда
(27)
где
, . (28)
В (27), (28), при этом коэффициенты зависят от вида аппроксимируемой функции и номера подынтервала.
Для оценки параллелизма достаточно учесть вторую формулу из (28). Согласно этой формуле требуется одновременно умножить значения под знаком суммы (за время на процессорах), это требуется сделать одновременно по всем номерам коэффициентов из (27), на что потребуется
,
процессоров, или,
.
Очевидно, данное количество не больше количества из (19).
Для вычисления коэффициентов из (28) еще требуется сложить полученные значения. По схеме сдваивания для одного коэффициента потребуется процессоров, время вычисления составит. На все коэффициенты для одного рассматриваемого полинома потребуется процессоров, которые одновременно их рассчитывают по схемам сдваивания. Наиболее длительная среди них займет время .
В результате, на основании изложенного имеет место
Лемма 2. В рассматриваемых условиях коэффициенты отдельно взятого на -м подынтервале полинома вида (27) можно вычислить параллельно с временной сложностью
(29)
что влечет
Временная сложность параллельного построения кусочно-полиномиального вычисления функции с учетом проверочных условий. Предположим, что данное построение интерполяционных полиномов вида (27) выполнено одновременно для всех номеровподынтервалов. Тогда правая часть оценки (29) не изменится, а число процессоров согласно (2) возрастет в раз. Отсюда вытекает
Теорема 1. В данном предположении и условиях леммы 2 коэффициенты полиномов вида (27) на всех подынтервалах можно вычислить параллельно с временной сложностью
(30)
что влечет Число процессоров в (30) составляет .
Выполним теперь учет числа проверочных точек, а также выполнение проверки неравенства (5) в каждой из них.
Будем предполагать, во-первых, что проверки выполняются одновременно на всех подынтервалах, во вторых, что вычисление в каждой проверочной точке построенного полинома выполняется по параллельной схеме, точнее, с использованием схемы Стоуна [10, 11] для вычисления всех степеней независимой переменной, затем с использованием схемы сдваивания для сложения их произведений на коэффициенты,– за время , или,
. (31)
Правые части (31) сложатся по времени с правыми частями (30), в то время как число процессоров в процессе проверки составит, где – число проверочных точек на подынтервале, – число подынтервалов. Отсюда вытекает
Теорема 2. В рассматриваемых предположениях коэффициенты полиномов вида (27) на всех подынтервалах можно вычислить и затем выполнить проверки неравенств (5) по всем данным подынтервалам параллельно с временной сложностью
что влечет
(32)
Число процессоров в (32) составляет.
Замечание 2. Условия теоремы 2 не предполагают выполнение всех проверочных неравенств так, чтобы они одновременно все были верными. Эти условия лишь указывают на возможность одновременной проверки неравенств вида (5) независимо от их истинности на множестве из подынтервалов.
Пусть в дополнение к условиям теоремы 2 требуется с необходимостью определить условия истинности всех проверочных неравенств в пределах , где граница изменения предполагается априори заданной и постоянной, . Тогда нетрудно видеть, что требуемую проверку можно выполнить одновременно для всех допустимых значений , т. е. для . Имеется ввиду, что каждый из синхронно работающих процессоров выдает сигнал истинности или ложности проверяемого неравенства, поэтому результат проверки будет положительным для первого (и последующих значений), при котором неравенства (5) удовлетворяются одновременно на всех подынтервалах.
В рассматриваемых условиях оценки теоремы 2 должны воспроизводиться одновременно для , так что число подынтервалов из теоремы 2 меняется как . Следовательно, количество процессоров, приведенное в теореме 2 возрастает в раз, или, в . На этой основе с учетом вида оценки имеет место
Следствие 1. В рассматриваемых условиях и при выполнении условий теоремы 2 имеет место оценка (32), где количество процессоров возрастает до значения .
Временная сложность параллельного построения кусочно-полиномиального вычисления функции с учетом одновременно всех допустимых степеней полиномов. Предположим, что изложенное построение интерполяционных полиномов вида (27) выполнено одновременно для всех , , подынтервалов, при этом степень полинома принимает одновременно все возможные значения , граница изменения степени полинома по-прежнему предполагается априори заданной и постоянной:.
Такое предположение целесообразно, если требуется максимально параллельная форма проверки условия (5) одновременно для всех допустимых значений . В свою очередь, проверка неравенства (5) для каждого обусловлена тем, что априори неизвестно, для какого именно значения это неравенство верно одновременно во всех проверочных точках на всех подынтервалах.
Итак, если искомую проверку выполнять максимально параллельно по всем рассматриваемым , то правая часть оценки временной сложности примет вид:
(33)
соответственно, оценка (32) перейдет в соотношение:
(34)
Число процессоров в (33), (34), в условиях следствия 1, возрастет до величины , или
. (35)
При сохранении главного порядка роста по соотношение (35) примет вид:
. (36)
Теорема 3. В рассматриваемых предположениях коэффициенты полиномов вида (27) одновременно для всех и одновременно на всех подынтервалах при всех можно вычислить и затем выполнить проверки неравенств (5) по всем данным подынтервалам параллельно с временной сложностью (33), что эквивалентно по величине порядка роста (34). При этом требуемое число процессоров оценивается из (35), или, с точностью до порядка роста, из (36).
Временная сложность параллельного построения кусочно-полиномиального вычисления функции, производной и определенного интеграла. Полином вида (27) влечет табличный вид производной: , . (37) Таким образом, вместе с коэффициентами аппроксимирующих полиномов автоматически получаются коэффициенты полиномов, аппроксимирующих производные тех же функций. Отсюда вытекает Следствие 2. В условиях теоремы 3 без изменения утверждения теоремы и оценок (33) – (36) имеет место дополнительное утверждение о том, что наряду со всеми рассматриваемыми полиномиальными приближениями функции одновременно выполнимо параллельное вычисление приближений ее производных вида (37).В [13] на основании аналогичного формирования коэффициентов первообразных выводится формула: , где – число подынтервалов разбиения промежутка интегрирования, или, окончательно,
. (38)
Чтобы параллельно вычислить правую часть (38), достаточно применить схему сдваивания к готовым коэффициентам, что повлечет время порядка , или, с учетом границ числа подынтервалов и степеней .
Таким образом, наряду с функцией и производными одновременно могут быть вычислены интегралы (38) за время с дополнительным к (35) количеством процессоров порядка .
Дополнительные оценки. Если в условиях теоремы 3 построение полинома Ньютона вида (4) выполняется одновременно для всех заданных границ погрешности , , как это сделано, например, в табл. 1, 2, то правые части оценок (33), (34) сохранятся, а число процессоров в (35), (36) возрастет в раз.
Если в тех же условиях расчет коэффициентов выполняется одновременно для набора из функций, аналогично, правые части оценок (33), (34) сохранятся, число процессоров в (35), (36) возрастет в раз.
Замечание 3. Существенно, что и в случаях простых функций (табл. 1), и в случаях их конечных, но произвольных суперпозиций (табл. 2) вид аппроксимирующих полиномов не меняется, он инвариантен относительно вида функции, с точностью до числовых значений коэффициентов. Поэтому для часто встречающихся функций при хранении коэффициентов скорость вычисления фактически не меняется.
Свойство, отмеченное в замечании 3, целесообразно использовать для синхронизации параллельных процессов вычисления наборов функций с одновременно готовыми значениями аргументов. В самом деле, выбрав и зафиксировав одну и ту же степень полинома в форме (3) для приближенного вычисления конечного набора функций в параллельной вычислительной системе, можно все функции набора при готовом значении аргумента вычислять одновременно. При этом синхронизируется не только время вычисления каждой функции, но и шаги схемы Горнера, по которой выполняется вычисление аппроксимирующих функции полиномов.
Замечание 4. Целесообразно отметить, что изложенный метод построения аппроксимирующих функцию полиномов распространяется не только на случай явного задания функции. По существу в способе построения аппроксимирующих полиномов ничего не изменится, если функция задано неявно. Более того, ее значения в узлах интерполяции могут быть результатом решения сложных уравнений различной природы. Однако, поскольку есть значения в узлах интерполяции, этого достаточно для построения интерполяционных полиномов. Равно этого достаточно для вычисления значений полиномов и их сравнения со значениями функции в проверочных точках. Сохраняется также весь параллелизм построения полиномиальной аппроксимации. Единственно, что при этом меняется, помимо способа вычисления самой функции, – это время вычисления самой функции в оценках (32) – (34).
Заключение. В работе представлены максимально параллельные формы алгоритмов приближенного вычисления функций одной действительной переменной на основе варьируемого кусочно-полиномиального метода, использующего интерполяционные полиномы Ньютона. Показано, что вычисление функции осуществимо за время , где – заданная граница вариации степени полинома, – количество процессоров, которое эквивалентно . Оценки выполнены на модели неветвящихся параллельных программ.
В случае часто встречающихся функций аппроксимация реализуется за время для отдельно взятой функции. В многопроцессорной системе метод может использоваться для синхронизации процессов вычисления функций при заданных значениях аргументов.
Наряду со всеми рассматриваемыми полиномиальными приближениями функции одновременно выполнимо параллельное вычисление приближений ее производных и определенных интегралов.
В работе не рассматривается случай произвольно фиксированного количества процессоров.
Список литературы
1. Люстерник Л.А., Червоненкис О.А., Янпольский А.Р. Математический анализ: Вычисление элементарных функций. – М.: Физматгиз, 1963. – 248 с.
2. Попов Б.А., Теслер Г.С. Вычисление функций на ЭВМ: Справочник. – Киев: Наукова думка, 1985. – 600 с.
3. Голубков Ю.А. К правильному выбору алгоритмов аппроксимации функций для ЭВМ, работающих в реальном масштабе времени // Электронные вычислительные машины. – М.: ИТМ и ВТ АН СССР, 1965. – Вып. 3. – С. 115-154.
4. Лебедев В.Н. Введение в системы программирования. – М.: Статистика, 1975. – 312 с.
5. Winograd S. On the Parallel Evaluation of Certain Arithmetic Expressions. “Journal ACM”, 1975. – v. 22, № 4. – Р. 477-492.
6. Winograd S. On the Speed Gained in parallel methods. “New Concepts and Technologies in Parallel Information Processing, Ed. Coianielle, Leiden, Nordhoft, 1975”, 1975. – Р. 155-165.
7. Ромм Я.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки / Диссертация на соискание ученой степени доктора технических наук. – Таганрог: ТРТУ, 1998. – 546 с.; ВНТИ Центр. – № 05.990.001006.
8. Maruyama K. On the Parallel Evaluation of Polynomials // IEEE Trans. on Computers, 1973. – v. c, 22, № 1. – Р. 2-5.
9. Miranker W.L. A Survey of Parallelism in Numerical Analysys // SIAM Review, 1971. – v. № 7. – Р. 524-547.
10. Stone H.S. Problems of parallel computation. – In: Complexity of Sequent. Paral Numer. Algor. // Ed. T.F. Traub. N.Y.: Acad. Press, 1973. – Р. 1-16.
11. Солодовников В. И. Верхние оценки сложности, решения систем линейных уравнений. – В кн.: Теория сложности вычислений. I: Записки научных семинаров ЛОМИ АН СССР. – Л. – 1982. Т. 118. – С. 159-187.
12. Котов В.Е. О связи алгебраических и архитектурных аспектов параллельных вычислений. – В кн.: Вычислительные процессы и системы. Под ред. Г.И. Марчука. – М.: Наука, 1983. – С. 54-80.
13. Аксайская Л.Н. Разработка и исследование параллельных схем цифровой обработки сигналов на основе минимизации временной сложности вычисления функций. – Таганрог: ЮФУ, 2008, автореферат диссертации на соискание ученой степени кандидата технических наук, 18 с.
14. Джанунц Г.А. Компьютерный метод кусочно-полиномиального приближения решений обыкновенных дифференциальных уравнений в применении к моделированию автоколебательных реакций. – Таганрог: ЮФУ, 2012, автореферат диссертации на соискание ученой степени кандидата технических наук, 22 с.
15. Пулькин С.П., Никольская Л.Н., Дъячков А.С. Вычислительная математика. – М.: Просвещение, 1980. – 176 с.
16. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. II // Кибернетика и системный анализ. – 2007. – № 2. – С. 161 – 174.