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

 

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

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

ФункцияИнтервал аппроксимацииРазрядность nМетод вычисления поправки?x0,5?x?18Линейная интерполяция

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

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

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

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

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

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

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

Содержание

Введение

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

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

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

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

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

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

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

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

Заключение

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ИндексТабличные значения0xminf(xmin)1xmin+hf(xmin+h)………ixsf(xs)………Nxmaxf(xmax)Рис.2. Таблица значений аргумента и функции

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

=[(x-xmin)/h]-ц , (1)

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

(x)= f(xs) + ?(xs,Ñx), (2)

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

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

(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=x-xs и tg(a)=[ 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 ? 1/2Мf = |f|max / 2(2n-1-1), (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 ? 2-n. (9)

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

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

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

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

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

? [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);(sin(x), x, 2)(-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), имеют общий масштаб

f ? (2п-1-1)/|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))]ц1/2, (15)

где [·]ц1/2 - оператор округления до целого значения по 1/2.

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

n-1n-2n-s-1n-s-2n-s-30Зн…X, F(X), F(Xs), F (Xs+H)n-1n-2n-s-1n-s-2n-s-30Зн…00…0Xsn-1n-2n-s-1n-s-2n-s-30Зн0…0…ÑXn-1n-2n-s-1n-s-2n-s-20Зн0…100…0H=2n-s-1Рис.5. Форматы целочисленных величин

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

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

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

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

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

clear

%Вычисление табличных значений аргумента и функции с шагом h=2^-3; %шаг таблицы= 0.5:h:1; %таблица значений аргумента= sqrt(xs); %таблица значений функции= 2^7;= 2^7;= round(xs*Mx); %таблица целочисленных значений аргумента= round(fs*Mf); %таблица целочисленных значений функции

%Вычисление текущих значений функции с шагом h/4= 0.5:h/4:1;=sqrt(x);(5,1,1); plot(x,fx,'g') %график функцииon;'Graphic sqrt(x)';=round(x*Mx);= floor((x-0.5)/h) +1; %значение индекса

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

%по методу линейной интерполяцииj=1:1:17(i(j)<5)(j) = fs(i(j))+(x(j)-xs(i(j)))*((fs(i(j)+1)-fs(i(j)))/h);(j) = fs(i(j));;

%Вычисление значений функции по целочисленному алгоритму(i(j)<5)(j) = FS(i(j))+ round(2^-4*(X(j)-XS(i(j)))*(FS(i(j)+1)-FS(i(j))));(j) = FS(i(j));;

%Демаcштабирование значений функции= F/Mf;(5,1,2); plot(x,fdem,'g');on;'Graph f demash';

%Полная погрешность= sqrt(x) - fdem;(5,1,3); plot(x,eps,'b');on;'Graph polnoi pogreshnosti';

%Методическая погрешность_m = sqrt(x)- f;(5,1,4); plot(x,e_m,'r');on;'Graphic methodich pogreshnosti';

%Инструментальная погрешность_instr = f-F/Mf;(5,1,5); plot(x,e_instr,'-k');on;'Graphic instrum pogreshnosti';

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

Больше работ по теме: