книги из ГПНТБ / Основы теории алгоритмов учеб. пособие

-

130

-

Х >

-

к

+

2 1

N i .

(5.13)

Например), для разрядной оетки

П

=

8

следует вычислить

*

С

-

с точностью

§

4

2 '3

.

Для достяхволя такой точности

до

л

отаточ!

но выбрать четырнадцать членов разложения (

р =

13)

<z

=

i + х +

-£7 +••• +]^7

4 5 '

в вычисления проводить с учетверенной точностью (

к =

4 ).

Еоли рассматривается интервал

0 ^ 36 < i

, то сум/ш-

рование членов

О »

,

Q

i

z

,

О можноа

вычислять о

одинарной

точностью, т .к .

2

" * >

а

»

,

Q

i

z>

,2а" 32,»

С

« )

;

членов

Q

g

,

Clio

-

о удвоенной точностью,

т .к .

2 " “ > 0 » . С » > 2

~

2 \

( N . - ( 0 ) ;

членов

( Х

б

О, /

,

Cfe -

о утроенной точностью, т .к .

2 ' ‘ > c k , c i ' , a l > 2 ' *

>'

( М г - 8 ) ;

шенов do

,

Q

l , .

.

.

,

-0 сs учетверенной точностью,

т .к .

они больше

2 “*

(

N* =

5).

Объем долговременной памяти без

економии ячеек

(5.12)

составит

„

Время реализация оценим по (5.5)

и (5 . I I ) .

Пусть

t = 3 (гла­

ва

1У,

пример для дополнительного кода), a

mto = io i + -ivwH +

+

i

зам

. Примем, чтб

= 5 t«

, тогда

it! -to «

1to + 5Ь>+ ft* -

7Ь> t согласно

(5.5),

Т

=

= н е т 0 •

Т *

с-1

=954io.

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

$ (& )представляется полиномом'степени р .

р

( # )

*

Со + С, ЗС- + • • • + Ср.,

+ Ср ЗСР.

Если для коэффициентов

C^j ( ^ =

0 , 1 , . .. ,

р

)

можно составить

систему

Ык

п

2 ~ (1 -ф

>

£ - С * > ' - 2

,

(5.14)

то все вычисления данного полинома цри 0 ^

ЗС

^

I

нецеле­

сообразно

проводить с

к -значной точностью, иначе это

приведет

к большому времени реализации. Система (5,14)

позволит устано­

Очевидно,

что члены, удовлетворяющие (5.14),

вычисляются о

( к-1)

- степенью точности.

,

Объем долговремшной памяти может быть определен из

(4 .1 3 ), а в р е м

реализации из (4 .I I ) .

В классе

итерационных приближений

V

УУН -

погрешность каждой итерации

’

Если для достижения заданной точности В ^ 2

требуется р

итераций,

то мокко составить многонтерадионную систему пова-

шечпой точности

•

-

132 -

&

S

i

St,

>

•

•

2

• - "

2~п >

б

*

/ (

+

St. > г 2”

4

*

Я

•

2

&Ni+iй

S

'

>N

i

a

>

•

•

•

StiM

2

'

“

«' 0

„"

St> .>«

• 2

-•

w

•

*-

>

< W l,

где Nt -

число

итераций.

Для

§Ni

я $ы,+1 выполняется условие

&Ni

> 2 W > $Ni.H .

рации j=NiM+‘f

.Мк-г + 2

Nк , N kh необхо­

димо выполнять с

к -значной точностью.

Уменьшение степени

-

133 -

6o t S i , § г , • , Siii

> 2~ч

•

t •

• • •

(5.16)

S

i

, . <zmv <

Особенностью оиотемы (4.16) являетоя то, что она содержит по

одной итерации с высшей степенью точности.

4

Например,

вычислим обратную величину

У =

дГ

о погреш­

ностью § * 2 '* 2

на машине о разрядностью

н

=

8 . Для

Й +<

= ^ ^

'

(5 .17|

На интервале [ о, 5

* i ]

максимальные относительные и аооолют-

ные ошибки по своему

значению совпадают,

т .к .

- 134

-

Приведен (5.18)

к системе (5 .1 6 ), тогда

So,

Si, S t ,

S i > 2 ~ g 1

5/,

- 2

' “

>

S s

= 2 " и

J

Отсюда следует, что для достижения заданной точности

достаточно провести

три итерации с одинарной точностью, одну -

с удвоенной и одну -

о учетверенной.

Если выбрать в качестве начального приближения линейное

ч . -

н

32 зС-

п

1 7

то можно записать систему

&> = 0 ,059

>

2 ~ g

6< =0, О0348

> 2 ЧС

I

$ 1 = 0,12 -10 -*'>

2-~2*

[

S i = 0.15-10'*

>

2-~*г

Преобразуем данную оиотему к виду

S c , S t = 2'*

*

Sc. = 2 Н«

6 ,

-

2 ' зг

одну - о удвоенной я одну -

о учетверенной.

Оценим время реализация метода итераций.

Бели все р -

итерации вычислять с

к

-значной точностью,

то

Т

- ptum ,

(5.19)

4*

к -значной

где Ъитц - время выполнения одной итерации с

точностью.

Для систеш

(5.15)

■

Т

-

£ т Л

’

(5.20)

где

W - число итераций в

t -й строчке оиотемн

(5 .15).

Для быотрооходящихоя итераций ( х >

-\[~

) из

(S .I6)

к

Т

“

ш Д м т ч

+

2 - tu r n

,

(5.21)

Определим показатель

Т

ва примере обратной величины.

Одна итерация о

к

-значной точностью,

согласно форму­

ле итерации

имеет

У i+< ~

а^ 2

1*ищ -

i w

+

2

i *«« -

к 1Ьо + 2 £ т

ь •

Для

I * 3 и

да = 7

Из (5.18) следует, что Wt = 2, •% = i , (tls = 0,

2.

T - S - 2 3 6 - t o - Ш < Н * .

Для системы (5.15) имеем из (5.20)

T

= 2 i7 i . + 6 2 io 4 2 - 236to - 5 6 8 ^ .

Согласно (5 ,1 6 ),

из (5.21) для w<= з ,

т г = I, ж **

0,

i

Т

-

3 * < 7 Ь + 62io + 2Ъ6*~

« 3 4 9 -to .

_______ J

5ВМ.

\

Один из методов уменьшения времени реализации алгорит­

бить

интервал [ а , в ] , на котором отыскивается значение функ­

ции,

на систему непересекающихся подинтервалов. На каждом

степенью,

чем полином на интервале [а ,

в ] , при сохранении

той же точности. Для отыскания необходимого подинтервала по­

требуется

loq^K операций сравнения

(

К - число подинтервалов).

Однако в логическую схему отыскания подинтервала будет вхо­

дить (

К - I) операций сравнения.

Объем памяти, отводимый для хранения вычислительных

конотант,

определяется как

3 ) “

**)*(*-*)>

где

P j

- порядок полинома

^ -го

подынтервала.

Из

[6 5 ,ббЗследует,

что непосредственно вычислению поли­

кой схемы (число сравнений)

прямо пропорционально зависит

от

числа подинтервалов ( К ),

а время реализации "t ~

К

.

обходимого подинтервала

было бы также независимо от

К

,

Такие алгоритмы,

у которых осуществляется последователь­

138

А а р ; = А а ^ + 2 а

A<V**- А cip + 2A,

где

А

-

относительный адрес ;

j

-

номер подинтервала;

2 А -

две адресные единицы (0010).

X . t

Если оценивать номер подинтервала по 2-м первым разрядам

после запятой,

то можно весь интервал [0 + I]разбить на 4

под­

интервала. При атом 00 - первый подинтервал,

01 - второй подинтервал,

10 - третий подинтервал,

I I -

четвёртый подинтервал.

В общем олучае,

если номер подинтервала оценивать по

к разрядам, то получим

к

- 2

К

*

л

(5.22)

- 139 -

А а ^ - Д а к н + К А ,

где

L- порядковый номер коэффициента полинома

( i - 2 , 5 , . * . ,

К Л

- количество адресных единиц.

Объем долговременной памяти, отводимый под константа,

алипри

р,-р**...

,

= Р

D

-

К (р+ 0

(5,23)

Для удобства размещения сиотемы констант полиномов в

любом месте памяти машина к относительному адресу

Д

при-

бавим адресную колстаяту ( N A ) j

,

определяющую начало зоны

(в дальнейшем -

это

номер зоны,

равный абсолютному адресу ко­

эффициента

С|«

)

размещения системы констант для заданной

функция

£

.

Тогда для некоторой функции

£

абсолютные 'адреса коэф­

фициентов:

к,

,

А а 4.

+

( « %

.

(5.24)

А а я : - А < у и и к а

I

ЛГ

(5.25)

а

2, 5,..-,

Р+0 >

где

-

оиотема счисления.

Зона систдаы констант разбита на подзоны, число которых

равно

р +1.

В каждой подзоне хранятся коэффициенты о одинако­