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

- 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)