Файл: Основы теории алгоритмов учеб. пособие.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 24.10.2024

Просмотров: 108

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

-80 -

Ипг можно получить из выражений

 

 

 

Д?И1 =

ОСи- i S « ,

 

 

 

(3.20)

 

 

 

 

 

 

 

 

к

 

 

 

 

 

 

 

 

 

 

}?И2. =“ Хп-4-

G i - U n - l S i -

(3.21)

 

 

 

 

 

 

 

 

i ’ O

 

 

 

 

 

 

 

Были проведены многочисленные вычислительные экспери­

менты. На рис.

3.1 и 3.2

приведены значения истинные

?СиТ)

 

|и

рассчитанные по формуле (3.21) для

X

с i ( t )

(рис,

3.1)

и

i

$

= Si.fi(F t

с шагом квантования

 

л Ь

= 0,1

(рис. 3 .2).

 

 

|

 

Как видно из графиков, оценка

максимальной промежуточ­

 

ной суммы,

рассчитанная по формуле

(3 .21), только при

больших

: значениях

2 p a c v (n T ) >

Z ( п т)

 

•

, а в области

малых

 

 

значений

Z pacvC *1) ^

 

 

. Для того, чтобы этого

 

избежать, необходимо в области малых значений

У а ограничить

:

2расv ( п Т )

снизу на некотором заранее выбранном уровне,

кото­

 

рый больше или равен

2 ( и Т ) т ,-и.

Также и формулы (3,18)

и

 

(3.19) дают оценки,

которые всегда

больше истинного г?(иТ)

,

-Но процедура выборки максимального из ряда чисел весьма длитель­ на и занимает много меота в программе. Но для медленно изменяю­

щихся сигналов

в

 

качестве максимального

зна чения

X may ц Ijwar

I можно брать

максимальную из'двух крайних

точек, т .е .

 

Xmax =

т а о б ( З С п , ЗЙм-к),

y Mdx = W ao'(yfi-i>^fi-K).

 

Как показали опыты, рассчитанное значение

£ ( н Т )

боль­

ше истинного максимального значения вычислений

2 ( » Т )

,

Для увеличения точности необходимо минимизировать зна­

чение 20» Т )

,

но сделать

его меньше максимальной величины

из ряда

(

a

e

, a i , . . . ,

О к ,

6 i , 6 а . , . . . ,

 

 

!

<f

X

и-к, Цн - i , ...,

у и г 3

 

 

 

:не представляется возможным.

Минимизировать Z (n T j можно, определенным образом из­ менив передок суммирования попарных произведений при вычисле­ нии выражения (3 .7 ). Если № - постоянная или медленно, изме-

-82 -

iяяадаяея функция, то порядок суммирования можно задать, иохо-| дя из минимума промежуточной сумма при суммировании козффици-» рнтйв. Для получения So mLn необходимо первым брать макои-.

мальный по модуля коэффициент Q max ,

затем - максимальный

из коэффициентов, противоположных по знаку

О max , далее брать

коэффициенты так,

чтобы промежуточная их суша

не превышала

i

! значение CLmax. Бели это удается осуществить,

то Samx^Qmax-

 

Разумеется,

можно при минимизации получить S& = 6 max

 

; н Samtn < Cl max ,

но при вычислениях все же необходимо под4

|етавлять

,

S& » 6 max .

 

 

 

Задача получения наименьшей промежуточной суммы ряда

,

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

|

Зависимость %(нт)=*£(Х,Ц)

можно получить и другим

|0пособом. Рассмотрим несколько

первых значений

у1X1 ,

за­

 

менив в них величины y f n - j 3

значениям! y O - j - l j

.

 

у 1>-2 'Л

>уоз , у га.

 

 

 

I

Обозначив

V* f n l = Фн

t

имеем

 

 

 

У® я Qo ОСо

 

 

 

 

 

у = do Xi. + ( O t - O o g i) # 0 ,

 

 

 

у а “*£7оОСл,+

X i

+

 

 

tj, - a. +(a,-a.k)x.+fa.- (a*-a. k)k-

-a*k]» .+ {a,~[a,-(at-a,6,)61_

-а„Ц k-(a,-a,bt)k-a.b] X, ,

- 83 -

~ ( a i ~ a o & i ) & i ~ a o & z ] x z + { J X i +

 

 

+

L -

С

П

з -

—Ofo j Ло,

|где

Со * Go

 

1

C i = (

) = a i - c 0 6 i ;

 

c * - f

l - C l i - C t U - C . t x i

 

С з - f

S ' a s - Ы х - с Л х - с Л з ;

 

C4 « [

] * t y ~ C s6 i - C * S * - C i S 3-CoS4.

1 Найдем следующие значения функции с учетом введенян* обозначений:

у 5 *=Co3Cs + Ci^4 +Ca0^j+C3^4 + C 4 ^ f -

~ ( Q 6 t +Сз6а + G tБз + С* 6*)

у 6 « C a tf e + C i t f s M - C a ^ + C s a V f Q ^ z - C s X t ^

- ( С ^ б г + С 3 6 з з -С а6 ^ С з Б О ^ <, ,

Ц ? - С . х 7 +с 1 # 6 + с а г + м < , + с * х ^ с * # ъ -

- Сб%1-(е4$5+Cs$4-c$ 64.-Cef3&)эС0,

- 84

y e - СоХг + С 1 & 1 +СгХе + Ci Xs + Cg #<, i Се X з -

~ C a X i, ~ C r X i - (C i^ - C s - ^ i - C e S z - C r i n ) ЭС0 }

где

С 5 = C-4 6 i + Cj Ьг + Czj)3 * C l &4 у

 

 

Се = C4 S2, 4 Сз Ьз + C z B g —C s i n *

 

 

С г

« C , g 3 + C3 g« +C Ggj. - C y g a , . .

 

 

''С в ~ Ct,f)4 - C s& i - C e& z'- C rfin .

!1родоляая, получим

 

 

 

|

 

= C o X ,g + C i X s + С г Х ? + C s3 C e + C4 Х - т -

|

 

~ C s X < , - C c X i - C i X i - C g M i + С я Х 0 ,

 

LJtO ~ Со X i o ^ - Ci Xg + C z X g +СздС,? 4- C g X 6 -

 

 

- C

r X 5 ~

C s X z

+ C 3 X i

+ Cto # 0 ,

 

^f11 ^

C o X n - f

C L Xu>

t - C z X g

-f Сз X s +

 

 

+ C g X ? - C s X 6 - C e X s - C j Щ -

 

 

 

Cg & j + Cg X-z + C io X t + C 1 1 X 0 ■

и так далее.

 

 

 

 

ции

Отсвда можно записать выражение в общем виде для функ-

^

Lн]

- F ( C „ , X l^ J )

 

 

a

w

-

 

 

+

 

 

 

*>

 

c *

 

 

 

+ 2 - C n tf{> m l

- £

CfJ 3COf j (-... ,

fn=5V+i

)

p-3i)+i

- 85 -

где

C i - < п -

;

 

Я"°

м

М~iO

Cm = 2 Cjbw>ti-j — 2 Ст-^ Bm-tv-y -

 

<^*1

30

?~Зу>

 

 

Ср e ^

Cm

 

 

4rl

 

 

 

 

 

m»\Hi

 

 

 

 

 

 

 

I

Исследуем поведение

при действии на

интегрирующие

контуры постоянного напряжения с амплитудой,

равной единице

,

(для аналогии исследуем переходной процесс в контуре). При

1

втом

ОС[К] = I

и

 

 

 

 

 

 

 

 

 

1

0

 

 

2$

 

5v>

4«>

 

 

 

 

UW = 2

C t '

S

c i

^

Сгп~ Л

ср + -

 

а

(.=>0

 

j=0+i

 

М . Ш

<>*5^+1

 

,

(3.23)

 

 

 

 

J - V + 1 .

 

Р—

 

 

 

i

Как известно, в интегрирующем и дифференцирующих конту­

рах в

этом случав

при

t l - * 00

 

 

, т ,е .^ (Д ]л *

 

' Уmax при малых значениях

П . .

 

 

!

 

 

Рассмотрим

случай

Qi

^ I )

h i ~ i

,

При этом из

 

(3,22)

оледует,

что

 

 

 

 

 

 

 

 

откуда из (3.23) видно, что tffHJ -

среди первых $+i

 

нений. Действительно,

 

 

 

 

 

 

 

 

 

Р

 

О

 

 

 

 

 

 

 

Ц [ Ш ] ~ J E C i ~ £ C

i

< У

 

 

 

 

d

t*0

L -t

.

,

 

 

 

 

 

 

 

 

 

\?

 

i)

 

 

 

 

 

У [ Й 2 ] <

 

 

 

 

- iJ 'C i& V * M + C # u L < y [V+i3

 

и так далее.

Смотрите также файлы