Vosstanovlenie_funktsionalnoy_zavisimosti

2. Восстановление функциональных зависимостей

Частным случаем функций, которые можно вычислить с помощью 4-х арифметических действий, является алгебраический многочлен.

2.1 Вычисление значений многочлена.

Схема Горнера

Рассмотрим алгебраический многочлен

, (2.1.1)

или

, (2.1.2)

где ,…, - числовые коэффициенты, n – степень многочлена. Чтобы вычислить значение многочлена (2.1.1) при заданном x, можно применить разные способы.

Первый способ:

p:=a[0]; for i:=1 to n do p:=p+a[i]*power(x,i);

p=a(0) do i=1,n p=p+a(i)*x**i enddo

Здесь на каждом цикле выполняется операция возведения в степень: x², x³ ,…, xⁿ , требующая 1,2,…, n-1 умножений. Общее число умножений равно сумме арифметической прогрессии . К этому добавляется n умножений на коэффициент a_i, и n сложений. Всего действий.

Второй способ

p:=a[0]; z:=x; for i:=1 to n do begin p:=p+a[i]*z; z:=z*x; end;

p=a(0) z=x do i:=1,n p=p+a(i)*z z=z*x enddo

Здесь выполняется 2n умножений и n сложений, всего 3n действий.

Третий способ (схема Горнера)

Горнер (1819 год) предложил минимизировать количество операций следующим образом

P_n(x)=a₀+x(a₁+x(a₂+…+x(a_n-1+xa_n)…)

p:=a[n]; for i:=n-1 downto 0 do p:=p*x+a[i];

p=a(n) do i=n-1,0,-1 p=p*x+a(i) enddo

Здесь выполняется n умножений и n сложений, всего 2n действий.

Таким образом, разная организация вычислительного алгоритма приводит к существенно различным потребностям в ресурсах (в данном случае - затратам времени).

2.2. Вычисление значений трансцендентных функций.

Любая функция может быть приближенно представлена в виде алгебраического многочлена. Для этого нужно решить три задачи:

-  найти коэффициенты многочлена,

-  найти оценку погрешности (разницы между точным значением искомой функции и полученным значением многочлена),

-  найти способ управления параметрами алгоритма для получения решения с заданной точностью.

Для функций типа sinx и cosx все три задачи одновременно решаются с помощью формулы Тейлора

, (2.2.1)

где  - некоторая точка, лежащая между x и x₀ при xx₀.

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

Для sinx и cosx любая производная по модулю не превосходит единицы. Поэтому при для sinx и cosx остаточный член стремится к нулю при любых x и x₀. Поэтому за счет выбора n можно достичь любой заданной точности.

Таким образом, чтобы определить искомую функцию, нужно найти значение самой этой функции и ее производных в некоторой точке x₀. Кажется, что эта задача сложнее, чем исходная. Но решается она просто. Нужно выбрать x₀ так, чтобы значение функции и всех ее производных в этой точке были известны. Например, для функции sinx в точке x₀=0 f(x₀)=0, f(x₀)=1, f(x₀)=0, f(x₀)=-1, и т.д. Разложение функции sinx по формуле Тейлора имеет вид

Алгоритм вычисления sinx

sin:=0; u:=x; k:=1; while abs(u)> do begin sin:=sin+u; u:=-u*x*x/(2*k*(2*k+1)); k:=k+1; end;

sin=0 u:=x k=1 do while (abs(u).gt.) sin=sin+u u=-u*x*x/(2*k*(2*k+1)) k:=k+1 enddo

Однако, вычисления по этому алгоритму не всегда приводят к хорошему результату. Например, при использовании одинарной точности получаем sin2525. Результат абсурдный, так как погрешность во много раз превосходит сам результат.

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

Рассмотрим порядок вычислений по этой формуле:

Т.е. модуль слагаемого в начале очень быстро растет, достигает максимума примерно 10¹⁰ при k=12, затем начинает убывать и стремится к нулю. Но при одинарной точности длина мантиссы в условном десятичном представлении не превышает восьми разрядов. Двух десятичных разрядов не хватает даже для представления целой части суммы. Поэтому погрешность и представляется двузначным десятичным числом.

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

sin25=sin(25-8)sin(-0.132741)

Разница (25-8) по модулю меньше 1. Поэтому с возрастанием номера слагаемого происходит его быстрое убывание, т.к. числитель уменьшается, а знаменатель растет. Достаточно точный результат получается при малом числе слагаемых, и погрешность округления мала, поскольку малы сами слагаемые.

Для уменьшения значения аргумента в других случаях можно использовать известные тригонометрические формулы:

,

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

Однако разность (25-8) имеет погрешность на два порядка превышающую единицу последнего разряда. Поясним это на схеме:

+

2

5

0

0

0

0

0

0

+

0

2



+

2

5

1

3

2

7

4

1

+

0

2

=

-

0

0

1

3

2

7

4

1

+

0

2

В нормализованном виде



1

3

2

7

4

1

0

0

+

0

0

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

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

,

где [x] и {x} – целая и дробная части числа (x=[x]+{x}).