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

-

140

-

аргумента и абсолютным адреооы первого коэффициента

представляет собой логическую схему,

предшествующую вычисле­

нию полинома. Как видно,

логическая схода содержит операции

"одвнг" и "сложение". Объем и враля реализации (5.24) не за­

висит

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

Выражение (5.25) используется непосредственно

при вычис­

лении полинома для получения абсолютных адресных коэффициен­

тов

.

Разбиение интервала изменения аргумента на число подин­

тервалов

К

=

не воегда является удобным, т .к , может .

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

отводимой

под конотанты. Покажем это.

Для одного и того же порядка аппроксимирующего, полинома

и заданной допустимой погрешности ( 6§<>и

/можно найти такие

K |

a

K t

и,

следовательно,

их погрешности § 1

и

6 г

,

что при

K i " ^ * 4

имеем 8* >6%о»

а при Ка=о,к

Здесь

1 'г

удовлетворяет требованию по погрешности и

может

быть выбрано

для разбиения

функций на

К г подинтервалов.

Для

и

К г

выполняется условие

j ) i

< Эг.

,

где

D t

=

К д ( Р +0

,

a

~Dz =■ К г ( р + 0

.

Но так как

К г =

. то I ) г = ^ D i .

Однако если найти такое целое

К

( Ki <

К <

К г )

,

при

котором ошибка

8

находится в

пределах

ffC K O

> $ Г Н

> ^ С К г ) ,

то

объем памяти

7) ( K J

под константы

уменьшится,

при этом

D i < i ) < 3 ) д .

р

Если

K - K i

« К г ~ К

,

то. для q= 2

Da.a 0-5

выигрыш в

числе ячеек ДЗУ по

сравнению с

D sl

будет близок

к

50$.

^Преобразуем

X

так,

чтобы при

оценке его

по первым

К —разрядам число возможных номеров подинтервалов соот­

ветствовало

бы

К

, для этого разбиваем интервал

[0

* l]

на

К

подинтервала. Находим новый интервал

[dt- 6 ],

на кото-

-

и г -

ром помещается

К

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

Тогда

_

К

К

'

"

К г “

’

где

^

4<

<1* .

Преобразуем интервал

[о

*■i]

в

[о

1 1]

по формуле

ос'=

Тогда для любого

X

в интервале

[О

*■l]

будет

получено

ОС'

, не превышающее величины

Ь

,

Число возможных но­

меров

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

будет равно

К

,

Коэффициенты полиномов раопределенн в памяти так,

что

их абсолютные адреса

А а р •• -

к\

( N A ) j . ,

A o i j t s = А а ^ С И )

+ К А }

(

L * i , з

,

.

.

р

+ о

•

Очевидно, что для

в логическую охему дополнительно

необходимо ввести операцию умножения. Параметра логической

охеш

оотаютоя независимыми от

К

,

Рассмотрим интервал

j-^l < С

, Для получения ад­

реса I-го коэффициента преобразуем |х |

в [ £ * С ]

и 0С"4 Го~Д

При этом

Ш~г

*

—---

тогда

с . - г

A

O ljt

!

=«wс &-- гg

q -(n x ) + ( « %

,

(5.26)

где

п

К

К

хш ----.

0

< р

(N A )J - ( N A ) j

Зона размещения системы констант имеет номер ( NA

, Конс­

В выражении

(5.27)

операцию формирования модуля можно

иоключить, если X

>0

,

Логическая схема,

реализующая (5 .2 7 ), применима для ап­

проксимирования функции в

положительной или отрицательной об­

В этом олучаe

логическая схема (5.28) предпочтительнее: (5 .27),

г .к .

здесь отсутствует операция формирования модуля.

Выше рассматривался вопрос построения логической схемы

для

аргумента

X

, представленного в прямом коде.

Еоли для

изображения чисел в машине применяется обрат­

мер подштервал.

Пусть

-

аргумент,

представленный в одном из кодов»

Тогда,в (5,28) выделив

t +

I разряд,

получим

A a , i ! - { В

М

Л

[ f м м 1 < ^ Ц < 5 . з о >

где

И

(«-<)

с - г

-(и-Ю

-О -Ю

(WA =

г а -[н~(е*<)]

f, + I

( 7

“ т

J -

константа

выделения

разряда.

Определим размещение системы констак г в

памяти машины.

Обозначим

6

[ Л ]

=*

Г Х ]

. Тогда можно записать, что

[X] -

S x + CX3a

»

где [ Х ] ц - цифровые р.зряды tX J .

Отокда

A

+

(5.31)

- ( rx j,

Л c

+

*j+ ( m ) \ -

+ s ,

+ с т \

■

Для

* > 0

в н е *

S .-О, М ч * х - & | * | > DoM, ooquTM

деления получим

A c i j i - - Ы « | ^ &" , + ( N A ) i ,

что соответствует

(5.27). Отсюда номер зоны

Мзоны ( * > 0 >

=

( WA ) j . .

Для

ЗС<0 имеем S * =

I .

Номер подинтервала, оцененный

по

разрядам, будет цредотавлен в

обратном коде.

ратном направлении. Из (5.21)

видно, что N зоны ( 16 < 0)

омещен на величину

в сторону увеличения адресов ва

счет сдвига знака чиола, т .е .

-

148 -

идти машины,

а

I -в коэффициенты разместим согласно логичес­

кой охам (5,32)

а последовательности (5 .33). Тогда номера

вон

f

-X

олов будут;

для

ЗС > 0

NaOHbi(»P) =

+ ( ^ _1>

>

ЕЛЯ

ОС <0

и м

т о о - с м

) , + < f': , -<e*l>3+ o f-rti:(K < » « )A ]'>

(

*f

=

1,2 .........

&

) .

Логическая охема, согласно (5.32), реализует выражение

A a j M ‘ - f вЯЯ' -1* 4 ^

-

}

л

4 ( NA) i .

Старшие олова

L -х коэффициентов найдутоя из

А о ^ и »

A c i j < H i + <А.

Для младших слов

L -го

коэффициента имеем

/

A Oj ц , ; =

A

jUva -D + ( К о ,1) А .

5 .3 .

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

степени аппроксимирующего полинома

Для выбора оптимального числа подынтервалов оледует уста­

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

К , отепенью

аппроксимирующего полинома

Р

и абсолютной ошибкой аппрок­

симации

S

. Для этого данную функцию на каждом подинтер­

вале будем аппроксимировать интерполяционным полиномом Лаг­

ранжа. Выбор узлов интерполирования для получения наименьшей

ошибки произведем по методу Чебышева. Согласно

[б2] , ошибка

такой аппроксимации, не превышает значения

Sг

( 6 - о ) Р4<

(р+о

'(p+0!2aptl

Иl-Jntax D U ]

(5.34)

-

максимальная по модулю (

р + I) производ­

ная функции на

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

[a, 6] .

Бели интервал

[ А в ] , где

А

- верхняя граница

ин­

тервала, а

&

-

нижняя граница

интервала,

разбить на

К

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

то

Ь - а

к

(5.35)

Подотавив (5,35)

в

(5 .34), получим

8*оп »

■ i i S ~A ) (>_______ Г д .эд

'

(б*36)

3

(p+Oi г*** К * 4 Н^так1,

Отовда

_____________

&-Д

ы Гм\тях СА»6)

^

ЯВ

4

V 2 “*5|ол (р+1)!

Так как

число подинтерваяов не может бить не целим,

то екругля~

ем до большего целого. Тогда

f & B . B l

1

2'’5^*(p*i)'

J .

(5 .3 6 -а )

Значения

Г А, В]

для некоторых функций при-

ведены в

таблице 5.1.