ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.10.2024
Просмотров: 92
Скачиваний: 1
- 124 - |
|
Приведен (4.45) к линейной схеме ( Л - |
схема) |
F*(С'*"((<Я°+с,1&0+®а1>г)+-"+С?т£тЗ • |
(4 4g) ! |
В (4.46) кавдая скобка реализуется линейной функцией. Колинеот- |
|
0 0 обращений к алгоритму линейной функции определится порядков m .
/
|
125 - |
|
Г Л А В А 7 |
|
СИНШ АЛГОРИТМОВ ВЫЧИСЛЕНИЯ НЕКОТОРЫХ ФУНКЦИЙ |
|
ПРИ ОГРАНИЧШОЙ ДОТЕ РАЗРЯДНОЙ СЕТКИ УВМ |
|
5 .1 . Некоторые Функции о повышенной точеоотью |
|
вычислений в клаосах степенных разложений |
j |
и итерационных поопессов |
В настоящее время известен ряд численных методов начис |
ления элементарных функций [61,623. Выбор того или иного ме тода среди известных зависит от специфики вычислительной ма шины и требований, предъявляемых к показателям алгоритма вы числения.
Повышенная точность вычислений значительно ухудшает ос новные показатели -t и d эффективности алгоритмов. Это Обуславливается, прежде всего, большими соответствующими пока зателями алгоритмов простых операций повышенной точности, кото рые являются составляющими алгоритмов вычисления элементарный
функций. |
|
|
|
При вычиояешш |
значения функции на машине широко исполь |
||
зуются различные численные методы; разложение в ряд Тейлора- |
|||
Маклорена, приближение разного рода многочленами, |
метод |
итера |
|
ций |б З ,6 4 | .Любой из |
этих вычислительных методов |
и ряд |
других - |
может быть разбит на отдельные повторяющиеся участки о однозначнымя операциями.
|
Еоли для достижения необходимой точности требуется обра |
|||
щаться к такому участку N * |
раз, |
который проводит вычисле |
||
ния с |
к -аначной точностью, |
то |
общее вреда реализации |
|
|
|
|
|
(5.1) |
где |
Й ч - время реализации отдельного участка о |
к -значной |
||
точностью. |
|
|
|
|
|
Каждый участок состоит из простых операций |
(сложение, |
||
вычитание, умножение), которые выполняются с повышенной точ
ностью. Как была показано |
в главе 1У, время - tw |
тем больше, |
|
чем выше степень точности |
к . |
Отсюда величина |
Т раотет |
о увеличением к ♦ Более того, |
с ростом степени точности рао- |
||
- 126 -
тех я число обращений N k к повторяющемуся участку» Например, с ростом точности в ряде Тейлора следует выбирать большее число
членов разложения. |
|
Очевидно, что значительный роот времени Т |
может при |
вести к нежелательным показателям эффективности |
алгорит |
мов управления. В связи о этим в настоящей главе рассматрива
ются некоторые возможности уменьшения N k и 4!Чч |
в различных |
||||||||||||||||
клаооах вычисления элементарных функций. |
|
|
|
|
|
||||||||||||
|
|
В классе отепенных разложений Тейлора-Маклорена функция |
|||||||||||||||
|
|
|
S |
C |
* |
|
Р |
xCiVfi |
X |
- |
|
|
i |
# |
|||
|
|
|
|
) |
“ |
о • |
|
|
|
||||||||
Согласно [ б 1 , |
для |
|
|
1=0 |
|
|
|
|
|
|
|
||||||
знакочередувдего ряда оотаточный член |
|||||||||||||||||
|
|
|
|
J |
R |
p l |
|
|
< |
! |
О р |
+ |
П |
|
,(5,2) |
||
где |
|
Q p*i— ({>*<) |
|
|
-й член ряда. |
|
|
|
|
|
|||||||
|
|
Боля вое члены ряда одного знака удовлетворяют условию |
|||||||||||||||
то |
конечный член ряда |
|
p> |
1 |
|
|
|
■ |
|
||||||||
|
|
|
|
|
G |
|
|
5 |
|
|
|
|
|||||
Отоада оотаточнай член |
R |
p |
l |
« l |
a |
p |
l |
- |
|
||||||||
|
|
|
|
|
| |
|
|
|
|||||||||
|
|
Для многих степенных разложений элементарных функций, |
|||||||||||||||
содержащих в знаменателе |
j |
! |
, |
в |
интервале изменения аргумен |
||||||||||||
та |
[о |
+ l ] |
при |
р > 4 |
|
условие |
(5.3) можно записать |
так: |
|||||||||
|
|
|
|
|
I RP I < |
1«р I • |
|
|
|
|
(5-4) ' |
||||||
|
& |
Конечный р |
-член |
ряда |
заданной абсолютной погрешности |
||||||||||||
|
при выполнении (5 .2) |
н (5,4) можно выбрать из условия |
|||||||||||||||
|
|
|
|
O p |
^ |
^ |
0(i+i |
> |
|
|
|
|
» |
||||
где |
|
Op |
и |
О р н |
- |
|
максимальные значения членов |
на всем ин- |
|||||||||
тчдвале изменения аргумента. |
|
|
|
|
|
|
|
|
|
||||||||
- 127 -
|
Реализуя |
Р +* |
член разложения по схеме Горнера, |
оо- | |
|||||||||||
глаоно (5 .1) |
и |
(4 .27), получиы^для |
N « = p |
|
|
|
j |
||||||||
|
Т = * р £ * ч — р ( ^ м |
+ - ^ уин) |
=а |
|
|
|
|
||||||||
|
|
' |
|
|
' |
|
|
|
|
|
|
|
(5.5) |
|
|
|
|
* р ( к И о + 1< ш ^ в ) - p k ( £ + k m ) i 0 . |
|
|
|
||||||||||
Пусть для |
|
И |
-разрядной сетки |
сГ= 2 н , |
а для повышенной |
||||||||||
точнооти абсолютная ошибка метода 8 я |
2 * |
. Обозначим через |
|||||||||||||
N i |
порядковые номера членов ряда, |
которые обеспечивают точ' |
|||||||||||||
нооть вычисления в |
( |
i n |
) -ы разряде |
t= |
1 , 2 , . . . , |
к |
, |
||||||||
тогда |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Out |
> |
2 ' ы > й н т . |
|
(5.6) |
|
|
|||||
Для достижения точности в |
( ia K )-м разряде из (5.6) |
|
следует |
||||||||||||
система |
|
|
|
|
|
|
|
|
|
|
■ . |
|
|
|
|
|
|
|
|
|
a Hi > Т * |
> |
|
|
|
|
|
|
|
||
|
|
|
|
|
С(щг У 2 |
> Q n*.+1 |
у |
|
|
|
|||||
|
|
|
|
|
atiK > 2 ~ kH> a N^ i |
, |
(5.7) |
|
|||||||
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
% |
|
|
|
|
где |
Ык=Р |
, |
a |
|
Nt(+I ■ |
р+ I. |
|
|
|
|
|
||||
Преобразуем |
(5 .7) к виду |
|
|
|
|
|
|
|
|
|
|||||
' |
Ос |
|
|
а , |
|
|
Q |
a |
|
Он, > 2 ~И |
|
(5.8) |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
2~* |
> |
|
Он, +1 |
Q^+z |
. . . |
Qfi/Z> 2 |
|
|
|
|
||||
< г * |
> |
|
&НС+1 |
0*1+2 |
• |
• • ■W««)^ 2 ^ |
|
|
|
||||||
|
2 ‘ (' 0"> |
а . , . , |
Ow-f+2 |
• |
• |
• Cli/K> 2~*w |
|
|
|
||||||
2 ~ к* > |
• |
|
|
|
|
|
|
|
|
- 128 - |
|
|
|
|
|
|
|
Из (5.8) видно, что члены |
|
|
, |
Qn k- , +z |
i . . . * 0 |
iv* не пре |
||||||||
вышают значения |
Ы к |
|
|
и при выполнении уоловия (5,2) и |
||||||||||
(5 .4) |
|
|
|
|
|
. |
|
, |
|
|
|
|
||
|
|
|
£ _ |
а * |
|
< |
|
|
|
|
|
(5.9) |
||
|
|
|
V-Nit+1 |
|
|
|
|
|
|
|
|
|
||
|
Таким образом, |
суммирование данных членов рада можно |
||||||||||||
проводить с одинарной точностью. |
|
|
|
|
|
|
||||||||
|
Для членов |
|
|
|
|
|
|
,.«».C Iiyh можно запи |
||||||
сать, |
что |
|
( |
|
|
|
|
. - (К-2) И |
|
|
|
|
||
|
|
|
X |
а * |
< |
|
|
|
|
|
||||
|
|
|
2 ' |
|
|
|
|
(5.Ю ) |
||||||
|
|
T=Nk-i +1 |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
||||
и суммирование этих членов рада следует проводить не ниже, |
||||||||||||||
чем о удвоенной точностью. |
|
|
|
|
|
|
|
|
||||||
|
Неравенство |
(5.10) |
совместно |
о (5.9) |
дает |
|
|
|
||||||
|
|
Nк |
|
|
|
|
|
|
|
|
|
|
|
|
В общем олучае для членов C?Wi4| |
М |
ы |
2с |
О бусловив |
|
|||||||||
|
|
W;-m |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X |
a * |
< |
2 |
гЫ |
|
|
|
|
|
|
|
|
|
|
<Р* NiH |
|
|
|
|
|
|
|
|
|
|
|
|
позволяет сумму этих членов вычислять о точностью |
E k - l 3 . |
|||||||||||||
С учетом последующих членов |
|
|
|
|
|
|
|
|||||||
|
|
1 |
> |
< |
2 |
Л |
|
|
|
|
|
|
|
|
Для |
i s |
I имеем первые члены Of., |
0< ,Cfa , . . . , Ofv( |
, |
суммиро |
|||||||||
вание которых вдет |
о |
К -значной точностью. |
|
|
|
|||||||||
|
Таким образом, вычисляя с |
|
к-значной точностью пер |
|||||||||||
вые члены рада, |
а остальные с |
точностью, меньшей |
к |
, |
значи |
|||||||||
тельно улучшим показатель |
Ь |
эффективности алгоритма. |
Как |
|||||||||||
правило, |
степенные разложения Тейлора-Маклорена на вычислитель |
|||||||||||||
ных машинах реализуются по схеме Горнера или с использованием рекурентных соотношений. Поэтому вычисление оуммы рада начи
нается о младших членов ( Q p , O |
p - i |
, . , . с, одинар0 ^ 0 |
ной точностью. Затем переходим к |
удвоенной точности и так да- |
|
)- |
|
|
89 - |
|
|
|
|
|
|
|
|
лее. Заканчиваем вычисления о |
к -значной точностью. |
||||
Повторяющийся участок вычисления но схеме Горнера со |
|||||
стоит из операций умножения и оложения. Поэтому |
|
||||
.CK-U-oJ |
iTK-CH)] |
гСк-t-OJ |
|
||
t v 4 |
— "Сел |
-I- |
х . smh |
= |
|
|
= [ k - ( £ . - 0 ] { f c + [ k - ( i - 0 ] m ] t o . |
|
|||
Общее время реализации всего ^яда |
|
|
|||
Т - |
+ (Nz- N i) -Ьуч + •■• + (N k- N*-4) ^ |
|
|||
: N i[6 +(2k -f)ftl]+*** + |
N/tf-i ( £ +5 гс)+№*н (£+Згп)+М ((£+м). |
||||
Отовда |
|
|
|
|
|
Т |
- X |
N i { 6 + [ 2 ( X - 0 + i ] w } . |
(5,11) |
||
При реализации ряда Маклорена по схеме Горнера для хранения постоянных коэффициентов % ^ \ о )
лс ‘ “ Т Г
членов ряда О |
j =С^ X |
требуетоя объем долговременной |
||
памяти |
D - ( N - H ) К « ( р + * ) К . |
|||
|
||||
|
|
|
|
(5.12) |
Однако |
этот |
объем значительно уменьшается, воли учесть, |
||
что для хранения констант Су*., +< |
, Су^+л... .. Су* достаточно |
|||
по одной ячейке (из |
системы (5.8) |
данные члены меньше 2 " 0 ^ и), |
||
для констант Сук-л+< |
.........достаточно по 2 ячейки, а для |
|||
констант Со , |
С» , .. . , С у , |
необходимо но к ячеек. |
||
Тогда объем долговременной памяти |
||||
D - ( N 4 M ) K |
+ ( N a- N i ) ( k - 0 + ( N . - N 0 ( K - 2 ) + ... + |
|||
+( N1 - Nl-i) [k - ( t- о] +• *•+(Nk-i+ IVif-i)2+(Nk-IYk-i)»
=k + Ni 4- Nz + --- +Nk,
или