Отправляет email-рассылки с помощью сервиса Sendsay

Всё о работе в Интернет

Подписаться Бесплатная «Серебряная» новостная рассылка Подписчиков 7.350 RSS
←   Ноябрь 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней 1 выпусков (1 раз в 2 месяца)


Сайт рассылки: http://bestinvestblog.com
Открыта: 10-02-2009

Автор
bestinvestblog

Статистика

7.350 подписчиков
0 за неделю
←   Все выпуски   →

Занятие 52. Искусственные рекуррентные соотношения для повышения эффективности обработки числовых последовательностей.


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

Третий день сидит за монитором программист и не может запустить программу!

Рекомендуем ему сесть перед монитором!

ИСКУССТВЕННЫЕ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ

На практике достаточно часто возникает необходимость суммирования (или какой-либо иной обработки) числовой последовательности, каждый член которой содержит циклически вычисляемые элементы.

Например, общий член числовой последовательности , используемой для вычисления числа π, содержит знакочередование. Общий член числовой последовательности , используемой для вычисления экспоненты ex, содержит возведение в степень и факториал.  

Упомянутые примеры относятся к области численных методов математики, в которой проблемы повышения быстродействия вычислительных алгоритмов продолжают оставаться актуальными.

Учитывая важность задачи, рассмотрим процесс суммирования членов числовой последовательность с общим членом , в котором собраны четыре типичных случая циклически вычисляемых элементов, зависящих от порядкового номера члена последовательности, а именно: знакочередование, возведение в степень, вычисление факториала и суммирование натурального ряда чисел.

Предварительные “беглые” раздумья над поставленной задачей приводят к неутешительному выводу о необходимости использования “циклов в цикле”. Действительно, в процессе суммирования (внешний цикл) нужно будет вычислять каждый i-ый член последовательности. Для этого, в свою очередь, потребуются внутренние циклы для для определения знака i-го члена, для возведения в i-ю степень, для вычисления факториала числа i, а также для суммирования натурального ряда чисел вплоть до i. Иначе говоря, для решения задачи необходима организация циклических процессов не только для суммирования в целом, но и для вычисления каждого из членов последовательности.

Таким образом, я намерен предложить вашему вниманию способ объединения всех этих циклических процессов в единый цикл суммирования на базе использовании искусственно построенных рекуррентных соотношений. Благодаря им на каждом шаге внешнего цикла суммирования очередной член последовательности вычисляется и тут же включается в состав суммы без применения каких-либо иных дополнительных внутренних циклов.

Будем использовать следующие очевидные искусственные рекуррентные соотношения:

1) для организации знакочередования ; 

2) для возведения в степень ;

3) для вычисления факториала ;

4) для вычисления суммы натурального ряда чисел .

Задача C.1.10. “Искусственные рекуррентные соотношения”. Бесконечная числовая последовательность, содержащая циклически вычисляемые элементы, задана формулой общего члена . Построить подпрограмму вычисления суммы первых N членов этой последовательности (N >= 0).

   Function Sum_Artificial_Recurrent ( x: Real; N: Integer ): Real;
      Var i: Integer; B,C,D,F,S: Real;
   Begin
      S:=0; B:=-1; C:=x; D:=1; F:=1;
      For i:=2 To N+1 Do
         Begin S := S + B*C/(D*F);
               B:=-B; C:=C*x; D:=D*i; F:=F+i End;
      Sum_Artificial_Recurrent := S
   End;

Подпрограмма C.1.10 (функция Sum_Artificial_Recurrent) подсчитывает сумму последовательности, каждый член которой содержит циклически вычисляемые элементы. При этом используются искусственные рекуррентные соотношения.

В подпрограмме обработка каждого из циклически вычисляемых элементов выполняется отдельно и для их обозначения использованы промежуточные переменные B, C, D, F. Разумеется, в составе формулы общего члена последовательности могут быть и иные элементы, для которых рекуррентные соотношения не нужны и которые нет необходимости вычислять отдельно.

Перед циклом суммирования установлено начальное нулевое значение для суммы членов последовательности S. Также перед циклом установлены те значения промежуточных переменных B, C, D, F, которые соответствуют первому члену последовательности ( i = 1 ), и которые определены первыми ветвями соответствующих рекуррентных соотношений. Таким образом, всё подготовлено для вычисления первого члена последовательности. Именно поэтому первый оператор, выполняемый в цикле – это оператор суммирования: к предыдущему значению суммы добавляется значение очередного члена последовательности, вычисленное в соответствии с формулой общего члена. Только после этого можно вычислять элементы следущего члена последовательности ( i = 2, 3, ... ). Для этого используются выражения, представленные вторыми ветвями соответствующих рекуррентных соотношений.

Следует обратить внимание на то, что вычисление элементов членов последовательности в цикле начинается со второго. Поэтому и значения параметра цикла i, выполняющего роль порядкового номера члена последовательности, элементы которого вычисляются, начинаются с 2. А для того, чтобы обеспечить нужное для получения суммы число повторений цикла, конечное значение параметра должно быть взято равным N + 1. 

Таким образом, в подпрограмме C.1.10 процесс суммирования построен на основе всего лишь одного цикла. Благодаря использованию искусственных рекуррентных соотношений удалось избавиться от дополнительных циклических процессов вычисления каждого члена последовательности.

Побочным полезным эффектом использования искусственных рекуррентных соотношения является то, что удаётся избавиться от весьма неприятного возведения в степень отрицательной единицы, а также и переменной x, значение которой может быть любого знака. Действительно, использование для возведения в степень отрицательного числа экспоненциальной и логарифмической функций невозможно. А если идти путём возведения в степень соответствующего положительного числа, то понадобится дополнительное определение знака результата в зависимости от чётности либо нечётности показателя степеня.

Уважаемые подписчики! При необходимости задать вопрос, проконсультироваться, уточнить или обсудить что-либо обращайтесь через Гостевую книгу моего персонального сайта http://a-morgun.narod.ru. При этом настоятельно рекомендую пользоваться браузером Internet Explorer.

С уважением, Александр.

 
В избранное