Проектирование алгоритма вычисления элементарной функции с использованием таблично-алгоритмического метода

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

http: ///

Техническое задание

1. Выполнить проектирование алгоритма вычисления элементарной функции с использованием таблично-алгоритмического метода в соответствии с заданным вариантом. Алгоритм предназначен для целочисленных вычислений в дополнительном коде в формате «байт со знаком».

Функция

Интервал аппроксимации

Разрядность n

Метод вычисления поправки

vx

0,5?x?1

8

Линейная интерполяция

2. Выполнить расчет параметров алгоритма.

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

4. Разработать MatLab-программу для экспериментального анализа полной, вычислительной и методической погрешностей целочисленного алгоритма.

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

6. Разработать блок-схему подпрограммы вычисления элементарной функции по разработанному алгоритму в целочисленном формате данных.

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

8. Сопоставить экспериментальные значения погрешностей с их теоретическими оценками и сделать выводы.

Содержание

Введение

1. Теоретические основы таблично-алгоритмического метода

2. Постановка задачи проектирования алгоритма вычисления функции

3. Расчет параметров алгоритма

4. Масштабирование алгоритма

5. Блок-схема модели для экспериментального анализа погрешностей алгоритма

6. Описание и листинг программы

7. Результаты моделирования

8. Подпрограмма вычисления функции на языке Ассемблер IBM PC

Заключение

Список использованных источников

Введение

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

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

значения аргумента приводятся к интервалу аппроксимации;

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

выполняется постобработка полученного значения функции.

Существующие методы вычисления элементарных функций можно разделить на три вида:

алгоритмический метод;

табличный метод;

таблично-алгоритмический метод.

В случае алгоритмического метода элементарная функция вычисляется, как правило, с помощью степенного многочлена. Данный метод требует минимального объема памяти, но занимает значительное время вычислений. В случае табличного метода значения функции вообще не вычисляются, поскольку для всех возможных значений аргумента в памяти компьютера хранятся готовые значения функции в виде таблицы. Это самый быстрый метод, но при увеличении разрядности аргумента объем таблицы становится чрезмерно большим. В основу таблично-алгоритмического метода также положена таблица значений функции, но она строится не для всех значений аргумента, а для ограниченного ряда табличных значений. Если текущее значение аргумента отличается от табличного, то из таблицы извлекается ближайшее грубое значение функции, а затем вычисляется поправка по одному из численных методов. Таблично-алгоритмический метод сочетает в себе достоинства первых двух методов и получил наибольшее распространение в микропроцессорах и микроконтроллерах. Вычисление значений элементарных функций один из наиболее часто встречающихся типов математических операций, выполняемых в микроконтроллерах при решении задач управления движением роботов-манипуляторов, навигации, стабилизации, цифровой фильтрации и т. д. Общая доля этих операций может составлять 3−5%, а время, которое требуется для их программной реализации, 50% времени решения всей задачи.

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

1. Теоретические основы таблично-алгоритмического метода

В основе таблично-алгоритмического метода лежит разбиение интервала аппроксимации функции f (x) на равные промежутки величиной h (рис. 1):

Рис. 1. Разбиение интервала аппроксимации

В результате разбиения образуются значения аргумента xs, которые в дальнейшем называются табличными. Для каждого xs вычисляется значение функции f (xs), которое также называется табличным. Полученные значения xs и f (xs) сводятся в таблицу, которая размещается в памяти компьютера (рис. 2). Если таблично-алгоритмический метод использует и производные вычисляемой функции, то аналогичным образом формируется таблица значений производных. Табличные значения функции и производных получают один раз на этапе разработки алгоритма.

Индекс

Табличные значения

0

xmin

f (xmin)

1

xmin+h

f (xmin+h)

i

xs

f (xs)

N

xmax

f (xmax)

Рис. 2. Таблица значений аргумента и функции

В дальнейшем вычисление функции f (x) для произвольного значения x на интервале аппроксимации от xmin до xmax выполняется следующим образом. Сначала определяется интервал разбиения xsx xs+h, в котором находится значение x. С этой целью вычисляется индекс таблицы i, который является адресом табличных значений xs и f (xs):

i=[(xxmin)/h]ц, (1)

где []ц оператор округления до целого значения с недостатком. После этого искомое значение функции вычисляется по алгоритму

f (x)= f (xs) + ц (xs, x), (2)

где ц (xs, x) это поправка, которая уточняет табличное значение функции f (xs); x=x xs разность между текущим и табличным значением аргумента, причем xmax = h.

В частности, поправку ц (xs, x) можно вычислить, используя метод линейной интерполяции. Тогда алгоритм (2) принимает следующий вид:

f (x)=f (xs)+ (x xs)•[ f (xs+h) f (xs)]/h= f (xs)+ x •[ f (xs+h) f (xs)]/h, (3)

где f (xs+h) соседнее табличное значение функции.

Вычисление функции по алгоритму (3) можно представить графически (рис. 3):

вычислительный погрешность алгоритмический ассемблер

Рис. 3. Вычисление значения функции

Из рис. 3 видно, что поправка ц (xs, x) определяется как неизвестный катет прямоугольного треугольника по известному катету

x=xxs и tg ()=[ f (xs+h) f (xs)]/h.

Алгоритм (3) обладает методической погрешностью

ем? x (x h) • |f (2)|max / 2, (4)

где |f (2)|max максимальный модуль второй производной на интервале аппроксимации.

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

2. Постановка задачи проектирования алгоритма вычисления функции

Одной из задач проектирования алгоритмов таблично-алгоритмического метода является удовлетворение требований по времени и точности вычисления элементарной функции.

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

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

Проектируемый алгоритм обладает полной погрешностью, значение которой можно представить в виде суммы

е=емв,

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

ем? ев. (5)

Погрешность ев можно оценить аналитически. Однако такая оценка получается громоздкой и слишком грубой. Задачу можно упростить, если вместо исходного баланса (5) потребовать более жесткий баланс погрешностей:

ем0, (6)

где е0 погрешность представления переменных в целочисленном формате данных, причем

е0? ½Мf = |f|max / 2(2n11), (7)

где Мf — масштаб функции f (x); n — разрядность. Заметим, что оценка ев0 близка к реальной, поскольку количество арифметических операций в алгоритме (3) исчисляется единицами.

Для большинства элементарных функций на интервале аппроксимации выполняется равенство |f|max ?1, тогда получаем:

е0? 2-n. (8)

Подставив в (6) оценку (4) для ем и оценку (8) для е0, получаем баланс погрешностей в виде

x (x h) • |f (2)|max / 2? 2n. (9)

Левая часть данного соотношения достигает максимального значения при x =h/2. Поэтому в окончательном виде баланс погрешностей принимает вид

h2 • |f (2)| max / 8? 2-n. (10)

Баланс (10) позволяет найти шаг таблицы h, исходя из заданной разрядности формата данных n.

3. Расчет параметров алгоритма

Для нахождения шага таблицы представим его в виде h=2-s. Тогда из баланса (10) получаем

s? [n + log2|f (2)| max 3]/2. (11)

Параметр s, найденный из (11), округляется до целого значения с избытком.

Данный параметр обеспечивает баланс методической и вычислительной погрешностей алгоритма. Кроме того, он определяет не только шаг таблицы h=2-s, но и количество табличных значений функции f (x), равное 2s.

Так как разрядность n известна, то для нахождения параметра s по формуле (10) необходимо определить максимальный модуль второй производной |f (2)| max на интервале аппроксимации. Для этого достаточно построить график второй производной (например, с помощью программы MatLab (рис. 4).

Рис. 4. Графики второй производной

Из полученного графика второй производной находим |f(2)|max= 0. 707. Тогда, учитывая, что n=8, из (11) находим s ?2,75. При округлении с избытком s=3. Тогда можно рассчитать шаг таблицы h=2-s=2-3=0. 125.

x = sym (`x');

diff (sin (x), x, 2)

fplot (`-sin (x)', [0.5 1])

4. Масштабирование алгоритма

Для выполнения вычислений в целочисленном формате данных любую вещественную величину (целые числа, правильные и неправильные дроби) необходимо представить в виде целого числа, которое можно разместить в заданном n-разрядном формате. Последнее можно достигнуть, выполнив масштабирование алгоритма. Найдем масштабы для величин x, f (x), f (xs), f (xs+h), xs, x и h, входящих в алгоритм (3). При этом будем исходить из форматов целочисленных аналогов этих величин X, F (X), F (Xs), F (Xs+H), Xs, X и H, приведенных на рис. 5.

Величины f (x), f (xs) и f (xs+h), имеют общий масштаб

Mf? (2п-11)/|f|max, (12)

где |f|max определяется из графика функции на интервале аппроксимации.

Величины x, xs, x и h также имеют общий масштаб

Мx? (2n-1 1)/ xmax. (13)

Масштабирование алгоритма (3) сводится к замене исходных вещественных величин эквивалентными отношениями соответствующих целочисленных значений к масштабам и приведению подобных. Учитывая, что H =2(n-s-1), алгоритм (3) после масштабирования можно представить в виде

F (X) = F (X s) +2(n-s-1)•X •(F (X s+H) F (X s)). (14)

Тогда из (14) вытекает следующий целочисленный алгоритм:

F (X) = F (X s) +[2-4(X •(F (X s+H) F (X s))]ц½, (15)

где []ц½ — оператор округления до целого значения по ½.

На рис. 5 приведены форматы целочисленных величин, входящих в алгоритм (15).

n-1

n-2

n-s-1

n-s-2

n-s-3

0

Зн

X, F (X), F (Xs), F (Xs+H)

n-1

n-2

n-s-1

n-s-2

n-s-3

0

Зн

0

0

0

Xs

n-1

n-2

n-s-1

n-s-2

n-s-3

0

Зн

0

0

X

n-1

n-2

n-s-1

n-s-2

n-s-2

0

Зн

0

1

0

0

0

H=2n-s-1

Рис. 5. Форматы целочисленных величин

5. Блок-схема модели для экспериментального анализа погрешностей алгоритма

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

7. Описание и листинг программы

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

Листинг программы выглядит следующим образом:

clear

clc

%Вычисление табличных значений аргумента и функции с шагом h

h=2^-3; %шаг таблицы

xs = 0. 5: h:1; %таблица значений аргумента

fs = sqrt (xs); %таблица значений функции

Mx = 27;

Mf = 27;

XS = round (xs*Mx); %таблица целочисленных значений аргумента

FS = round (fs*Mf); %таблица целочисленных значений функции

%Вычисление текущих значений функции с шагом h/4

x= 0. 5: h/4:1;

fx=sqrt (x);

subplot (5,1,1); plot (x, fx,'g') %график функции

grid on;

title 'Graphic sqrt (x)';

X=round (x*Mx);

i = floor ((x-0. 5)/h) +1; %значение индекса

%Вычисление не масштабированных значений функции

%по методу линейной интерполяции

for j=1: 1:17

if (i (j)< 5)

f (j) = fs (i (j))+(x (j)-xs (i (j)))*((fs (i (j)+1)-fs (i (j)))/h);

else

f (j) = fs (i (j));

end;

%Вычисление значений функции по целочисленному алгоритму

if (i (j)< 5)

F (j) = FS (i (j))+ round (2^-4*(X (j)-XS (i (j)))*(FS (i (j)+1)-FS (i (j))));

else

F (j) = FS (i (j));

end;

end

%Демаcштабирование значений функции

fdem = F/Mf;

subplot (5,1,2); plot (x, fdem,'g');

grid on;

title 'Graph f demash';

%Полная погрешность

eps = sqrt (x) — fdem;

subplot (5,1,3); plot (x, eps,'b');

grid on;

title 'Graph polnoi pogreshnosti';

%Методическая погрешность

e_m = sqrt (x) — f;

subplot (5,1,4); plot (x, e_m,'r');

grid on;

title 'Graphic methodich pogreshnosti';

%Инструментальная погрешность

e_instr = f-F/Mf;

subplot (5,1,5); plot (x, e_instr,'-k');

grid on;

title 'Graphic instrum pogreshnosti';

8. Результаты моделирования

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

http: ///

Заключение

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

2. Разработана MatLab-программа для экспериментального анализа полной, вычислительной и методической погрешностей алгоритма.

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

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

Список использованных источников

1. Попов Б. А., Теслер Г. С. Вычисление функций на ЭВМ. Справочник Киев: Наукова думка, 1984. 599 с.

2. Ледовской М. И., Пьявченко О. Н. Методическое руководство к курсовой работе «Проектирование алгоритмов математических операций для микроЭВМ» по курсу «Основы обработки данных и моделирования» Таганрог: Изд-во ТРТУ, 1999. 30 с.

3. Ледовской М. И. Методическое руководство к выполнению лабораторных работ на модульной основе с диагностико-квалиметрическим обеспечением по дисциплине «Алгоритмические основы математических операций» Таганрог: Изд-во ТТИ ЮФУ 2009. 20 с.

4. Конспект лекций по курсу «Алгоритмические основы математических операций ч. 2».

ПоказатьСвернуть
Заполнить форму текущей работой