WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 ||

В разделах 2.4 и 2.5 рассматриваются вещественные функции одного аргумента, представимые степенными рядами двух видов, и показывается вычислимость таких функций в пределах F LINSP ACE [9,12] при условии линейной сходимости соответствующих рядов на отрезке [-, ] из области сходимости, т. е. если для остаточного члена выполняется |rµ(n)(x)| 2-n для любого x [-, ], где 0 µ(n) C1n + C2 (при этом предполагается, что µ вычисляется алгоритмом класса F LINSP ACE).

Предположим, что имеется степенной ряд S(x) = aixi = a0 + a1x + a2x2 +... + akxk +... (1) i=для x из [-, ], > 0,, где радиус сходимости. Пусть ai F LINSP ACE конструктивные числа, x F LINSP ACE конструктивное число из отрезка [-, ], i F LINSP ACE вычислимые функции из CF, i F LINSP ACE вычислимая функция из CFx. Пусть также m некоторое натуральное число, i(m) двоично-рациональные приближения коэффициентов ai с точностью 2-m, (m) двоично-рациональные приближения аргумента x с точностью 2-m.

k Рассматриваются частичные суммы Sk(x) = aixi ряда (1) с подi=становкой i(m) вместо коэффициентов ai и (m) вместо аргумента x:

k Sk(m) = i(m)(m)i.

i= Для расчета приближенных значений Sk(m) таких выражений используется схема Горнера с округлением промежуточных результатов:

h0(m) = k(m), hr(m) = k-r(m) + hr-1(m)(m), (2) hr(m) = hr(m) + r, где r = 1, 2,..., k; при r = k полагается Sk(m) = hk(m). Величины hr(m) получаются отбрасыванием битов qm+1qm+2... qm+p чисел hr(m) после двоичной точки, начиная с (m + 1)-го, т. е.

|r| = |hr(m) - hr(m)| = 0.0... 0qm+1qm+2... qm+p, а знак совпадает со знаком hr(m). Оценивается погрешность вычислений r (k, m) = |Sk(m) - Sk(x)| при следующих ограничениях на модуль ai и :

|ai| 1 для всех i, + 2-5.

Утверждение 1. Если m 5, то погрешность вычислений по схеме (2) оценивается как (k, m) < 2-m25(k + 1). (3) Пусть требуется вычислить приближенное значение частичной суммы Sµ(k)(x) ряда (1) с точностью 2-k для некоторого натурального k. Положим m = m(k) = m(k1, k2) = 5 + log2(k1 + 1) + k2, (4) где k1 = µ(k), k2 = k. Тогда m 5, и, следовательно, погрешность вычисления Sµ(k)(x) оценивается как (µ(k), m(k)) < 2-k. Так как для остаточного члена выполняется |r(x)| = |S(x) - S(x)| 2-(n+1) для любого x [-, ], где = µ(n+1), то |S (m)-S(x)| (, m)+2-(n+1). Возьмем m = m(k1, k2) по формуле (4) для k1 = µ(n + 1), k2 = n + 1. Тогда |S (m) - S(x)| < 2-(n+1) + 2-(n+1) = 2-n.

Так как µ(n) ограничена сверху линейной функцией, то линейной зависимости m от n достаточно для вычисления суммы степенного ряда (1) на отрезке [-, ] с требуемой точностью.

Предположим, что коэффициенты ai ряда (1) получаются последовательным умножением на некоторые величины с ростом номера коэффициента, т. е. ai = ai-1bi, с начальным значением a0 = b0:

S(x) = aixi = b0 + b0b1x + b0b1b2x2 +... + b0... bk-1bkxk +... (5) i=При вычислении Sk(m) удобно не пересчитывать коэффициенты ai, а накапливать их значение вместе с вычислением промежуточных величин. По этому для расчета приближений Sk(m) величин Sk(m) используется следующая схема с округлением промежуточных результатов, отличная от (2):

h0(m) = k(m), (6) hr(m) = k-r(m)[1 + hr-1(m)(m)], hr(m) = hr(m) + r, где r = 1, 2,..., k; при r = k полагается Sk(m) = hk(m). Проводится оценка погрешности (k, m) для такой схемы, аналогичная (3).

На основании вычислительных процессов (2) и (6) строятся алгоритмы SeriesSum1 и SeriesSum2 расчета приближений рядов (1) и (5).

Теорема 1. Если степенной ряд вида (1) аналитической функции f(x) линейно сходится на отрезке [-, ], + 2-5, и коэффициенты ai являются F LINSP ACE вычислимыми, то f(x) F LINSP ACEC[-, ].

Аналогичная теорема формулируется для функций, представимых рядами вида (5). Если коэффициенты ряда аналитической функции f являются также полиномиально вычислимыми по времени, то f будет принадлежать F P//LINSP ACEC[-, ].

В третьей главе рассматриваются конструктивные объекты математического анализа, наиболее часто используемые на практике, и доказывается F P//LINSP ACE вычислимость таких объектов, при этом для построения алгоритмов вычисления приближений используются только разложения в ряды и эквивалентные преобразования.

В разделе 3.1 устанавливается F P//LINSP ACE конструктивность алгебраических и некоторых трансцендентных чисел. Из известных результатов приводится ссылка на статью [2] и ссылки на ряд других работ.

Для построения конструктивных аналогов алгебраических чисел [8, 11] используется стандартное представление вещественных корней полинома P Z[x] списком отделяющих интервалов, при этом такой список вычисляется с помощью алгоритма Штурма. Предполагается, что полином задается списком всех своих коэффициентов, включая нулевые.

m Теорема 2. Пусть P (x) = pixi примитивный полином с целыми i=коэффициентами, свободный от квадратов. Тогда емкостная сложность алгоритма Штурма ограничена сверху функцией C(m3l(m) + m2w(P )).

Здесь l(m) длина двоичной записи m, w(P ) = (m + 1)(l(h(P )) + 1), h(P ) = maxm |pi| полунорма полинома P. Алгоритм Штурма позволяет i=по полиному P Z[x] построить набор CF конструктивных вещественных чисел, являющихся конструктивными аналогами корней полинома P.

Для вычисления рациональных приближений к корню используется итеративный алгоритм, на каждом шаге которого интервал, содержащий, делится на два подинтервала. Если 2-n заданная точность вычисления двоично-рационального приближения, то для концевых точек получающихся подинтервалов и значений P () в этих точках выполняются неравенства l() C1n, l(P ()) C2n.

Теорема 3. Пусть P Z[x] примитивный полином, свободный от квадратов, {i} набор вещественных корней P. Тогда каждое число из набора {i} принадлежит F P//LINSP ACECF.

Для построения конструктивных аналогов трансцендентных чисел и e используется формула Мэшина (J. Machin) для числа :

= 16 - 4, = arctg(5-1), = arctg(239-1), n и ряд для числа e.

i=i! В разделе 3.2 рассматривается вычислительная сложность основных элементарных функций. Для небольших по абсолютному значений аргументов элементарные функции вычисляются напрямую с помощью подходящего алгоритма для степенного ряда. Расчет таких функций на всей области определения выполняется с использованием аддитивной или мультипликативной редукции интервала.

Покажем схему расчета в пределах F P//LINSP ACE элементарных функций на примере логарифмической функции [10, 12].

Ряд Тейлора логарифмической функции ln(1 + x) = (-1)(i-1) xi i=i сходится для значений x в интервале (-1, 1]. С помощью мультипликативной редукции интервала вычисление логарифма для аргумента u = 1 + x u сводится к расчету логарифма для аргумента :

2r u u u ln(u) = ln 2r = ln + r · ln(2) = ln -r · ln ;

2r 2r 2r u здесь r некоторое целое число. Введем следующие обозначения: u =, 2r x приближение x, (u ) приближение u. Приближенные значения аргумента конструктивной функции являются двоично-рациональными числами, а такие числа, как уже говорилось, имеют конечное двоичное представление. Поэтому для вычисления (u ) достаточно сдвигать битовое представление u так, чтобы старший значащий бит оказался сразу после двоичной точки (т. е. (u ) = 0.1... ). Если u 1, то r > 0, иначе r 0. При этом (u ) будет принадлежать интервалу, 1, а величина (x ), равная (u ) - 1, будет находиться в интервале -1, 0. Так как (x ) -1, 0, 2 то x -1 - 2-5, 2-5 при условии, что x вычисляется с точностью 2-m, m 5. Обозначим интервал -1 - 2-5, 2-5 через (5).

Для модуля остаточного члена логарифмического ряда на интервале -1 - 2-5, 0 имеет место оценка |rn(x )| < 2-0.9(n+1)+2. Для x 0, 2-заведомо будет |rn(x )| < 2-n. То есть логарифмический ряд линейно сходится на интервале (5). Так как коэффициенты данного ряда ограничены по модулю сверху 1 и (5) [-, ], где = + 2-5, то используется схема (2) для расчета логарифмического ряда в пределах F P//LINSP ACE для x на интервале (5), в частности для расчета ln(2-1) = ln(1 - 2-1). При этом в качестве µ(n + 1) берется выражение 1.2n + 3, так как в этом случае будет |rµ(n+1)(x )| < 2-0.9(1.2n+3+1)+2 < 2-(n+1).

Учитывая, что k1 = 1.2n+3, k2 = n+1, получаем точность аргумента, достаточную для определения значения ln(1 + x ) с точностью 2-n:

2-m(k,k2), где m(k1, k2) = 5 + log2(k1 + 1) + k2.

Теорема 4. Функция ln(1+x) является F P//LINSP ACE конструктивной на любом отрезке [2-p - 1, 2p - 2], где p натуральное, p 1.

Аналогичные теоремы доказываются для функций (1 + x)h (h рациональное число, |h| < 1), sin(x), arcsin(x), exp(x).

Четвертая глава содержит описание библиотеки классов [12] для работы с F LINSP ACE конструктивными вещественными числами и функциями, реализованной на языке программированияC# 1.1. Приводятся результаты пробных вычислений некоторых констант и функций. Например, для вычисления приближенного значения ln(5) с 3320 двоичными знаками на компьютере с процессором AMD Athlon 64 X2 Dual Core 3800+ после точки понадобилось 27 с. При этом для умножения двоично-рациональных чисел использовался простой алгоритм с временной сложностью Cn2.

В заключении сформулированы основные результаты работы:

• Предложены алгоритмы для расчета в пределах F P//LINSP ACE полиномов и степенных рядов двух видов, в частности рядов Тейлора.

Приведены условия на степенные ряды аналитических функций, при которых такие функции являются F LINSP ACE конструктивными.

• Доказана F P//LINSP ACE вычислимость наиболее часто используемых на практике классов вещественных чисел и функций: алгебраических чисел, некоторых трансцендентных чисел, основных элементарных функций (получены соответствующие оценки погрешностей вычислений двоично-рациональных приближений и на основе этих оценок построены алгоритмы класса F P//LINSP ACE).

• Реализована библиотека классов на языке программированияC#в среде программирования Microsoft Visual Studio 7.1 для работы с F P//LINSP ACE конструктивными числами и функциями и на примерах некоторых чисел и функций математического анализа продемонстрирована практическая пригодность данной библиотеки.

Предложенные алгоритмы не всегда оптимальны по времени выполнения, но для построения F LINSP ACE вычислимого математического анализа важна принципиальная возможность построения линейных по памяти алгоритмов.

Список литературы [1] Косовская Т. М., Косовский Н. К. Различия между классом LINSP ACE и рядом других классов сложности. Тезисы докладов XIV Международной конференции Проблемы теоретической кибернетики (Пенза, 23 28 мая 2005 г.). М.: Изд-во мех.-матем. факультета Моск. ун-та, 2005. С. 72.

[2] Оревков В. П. О сложности разложения алгебраических иррациональностей в непрерывные дроби. Труды Матем. ин-та им В. А. Стеклова, CXXIX. Л.: Наука, 1973. С. 24 29.

[3] Шанин Н. А. Конструктивные вещественные числа и конструктивные функциональные пространства. Труды Матем. ин-та АН СССР им. В. А. Стеклова, Т. 67, изд. АН СССР, 1962. С. 15 294.

[4] Du D., Ko K. Theory of Computational Complexity. New York: John Wiley & Sons, 2000. 491 p.

[5] Ko K. Complexity Theory of Real Functions. Boston: Birkhauser, 1991. 309 p.

[6] Ko K. Polynomial-time computability in analysis. in Handbook of Recursive Mathematics, Vol. 2, Recursive Algebra, Analysis and Combinatorics, 1998. P. 1271 1317.

[7] Weihrauch K. Computable analysis. New York: Springer, 2000. 285 p.

Работы автора по теме диссертации [8] Яхонтов С. В. LINSP ACE-конструктивность алгебраических чисел. Труды V Международной конференции Дискретные модели в теории управляющих систем (Ратмино, 26 29 мая 2003 г.). М.: Изд-во факультета ВМиК Моск. ун-та, 2003. С. 96 97.

[9] Яхонтов С. В. Вычисление степенных рядов в пределах LINSP ACE. Материалы VIII Международного семинара Дискретная математика и ее приложения (Москва, 2 6 февраля 2004 г.).

М.: Изд-во мех.- матем. факультета Моск. ун-та, 2004. С. 118 122.

[10] Яхонтов С. В. Вычисление логарифмической функции в пределах LINSP ACE для конструктивных вещественных чисел. Материалы IX Международного семинара Дискретная математика и ее приложения (Москва, 18 23 июня 2007 г.). М.: Изд-во мех.- матем. факультета Моск. ун-та, 2007. С. 149 151.

[11] Яхонтов С. В. Вычисление алгебраических чисел и операции над ними с линейной памятью. Системы управления и информационные технологии. №1 (31), 2008 (март). С. 97 102. ISSN 1729-5068.

[12] Яхонтов С. В. LINSP ACE конструктивный аналог логарифмической функции. Вестник С.-Петерб. ун-та, Сер. 10. Прикладная математика. Информатика. Процессы управления. Вып. 2, 2008 (июнь).

С. 97 110. ISSN 1811-9905.

Pages:     | 1 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»