Лекции по математическому анализу - Архипов Г.И.
ISBN 5-06-003596-4
Скачать (прямая ссылка):
6*
163 Теорема (теорема A.A. Карацубы). Существует алгоритм, позволяющий умножить два п-значнцх числа за O(nlog3 3) операций.
Доказательство. Представим числа в двоичной записи: а = an ... ai, b = bn ... 61. Заметим, что
a6 = i((a + 6)2-(a-6)2).
Для деления числа на 4 достаточно сдвинуть его на 2 разряда вправо, это займет только 0(п) операций. Так что достаточно доказать, что возведение в квадрат n-значного числа потребует указанного числа операций. Доказательство проведем по индукции. Пусть для простоты п~ 2\ и пусть
а = 2n/2ot + ?,
где а и ? — n/2-значные числа. Тогда имеет место тождество а2 = а2(2п - 2"/2) + (а + /?)22п'2 - ?2(Tf2 - 1).
Если число операций для возведения в квадрат n-значного числа обозначим через К(п)у то
K(n) <ZK(n/2) + cn, . К(п/2) < ZK(n/A) + сп/2,
К(2) < ZK(I)+ с,
K(n) < Zk + c(n + Z^ + 32^ + . H- 3*),
где k = Iog2 п. Отсюда имеем .
tf(n)<3fc(3c+l).
Теорема доказана.
В заключение укажем на одно соображение общего характера, лежащее в основе многих итерационных вычислительных алгоритмов. Пусть требуется найти' значение функции в точке Xq , т.е. вычислить /о = f(xо). Обозначим через /п приближение к /о с точностью An (до п десятичных знаков):
Д« = |/п-/о|.
164- Допустим, нам известна функция G(x) со следующим свойством:
G(fo) = fo, = 0.
Тогда имеем
G(/n) = G(/o) + GU)(/n-/o) + ^(/n-/o)2,
откуда |/о - G(/„)| < с А2, где с = max .
Теперь, полагая /„+i = G(fn), получим приближение к /0 с точностью порядка 2п десятичных знаков после запятой. Тем самым мы имеем быстросходящийся алгоритм для приближенного вычисления значения /о. Заметим, что рассмотренный выше алгоритм вычисления корня квадратного из числа «о является частным случаем данного при f(x0) = y/xt и G(/n) = i(/„ + ^). Глава VI
НЕОПРЕДЕЛЕННЫЙ ИНТЕГРАЛ
Лекция 28
,11. ТОЧНАЯ ПЕРВООБРАЗНАЯ. ИНТЕГРИРУЕМЫЕ ФУНКЦИИ
Определение 1. Функция F(x) называется точной первообразной для функции f(x) на (а, 6), если при любом х Є (а, 6) имеем F'(x) = f(x), т.е. в каждой" точке х интервала (а, 6) значение функции f(x) является производной для функции F(x).
Теоремаї, Пусть f(x) определена на (а, 6) и F%(x), F2(x) — две ее точные первообразные. Тогда существует число с 6'К такое, что при любом X Є (а, Ь)
F1(X)-F2(X) = C.
Доказательство. Пусть функция
G(x) = F1(X) -F2(X).
Тогда G(x) — дифференцируемая функция, причем всюду на (а, 6)
Gf(x) = F{(x) - Ft2(X) = /(х) - /(х) - 0.
Положим x0 = Тогда по формуле Лагранжа конечных приращений имеем
G(X)-G(X0) = G^(X-X0)=O,
т.е.
G(x) = G(x0) V x Є (а, 6).
Но, полагая с = G(x0), получим, что G(x) = с для всех точек х интервала (а, 6). Теорема 1 доказана.
Замечание. Из теоремы 1 следует такое утверждение: любые две первообразные F{x) и G(x) функций /(х) и д(х) отличаются на константу тогда и только тогда, когда их производные совпадают, т.е.
166- когда F' = / = д = G'. Ранее мы видели, что далеко не все функции, заданные на каком-либо интервале (а, 6), имеют производную.
Аналогично обстоит дело и с первообразной, т.е. не все функции имею? производную. Но если функция /(ж), определенная на (а, 6), имеет первообразную, то она называется интегрируемой. Прежде чем перейти к йзучению класса интегрируемых функций, несколько обобщим понятие точной первообразной.'
Определение 2. Непрерывная функция F(x) называется первообразной функции f(x) на интервале (a,b), если в каждой его точке X за исключением, быть может, конечного их числа выполняется равенство F'(x) = /(ж).
Теорема 2. Пусть Fi (х) и F2(X) — первообразные для функции f(x) на (a,b). Тогда найдется число с такое, что всюду на этом интервале
Доказательство. Пусть х\,..., хп — конечное множество точек, на котором не существует F1'(ж) или F^(ж). Тогда множество (а, 6) состоит из конечного числа интервалов /?, на которых производные обеих функций существуют. Следовательно, по теореме 1 их разность постоянна на каждом таком интервале. Кроме того, эта разность является непрерывной функцией на всей области определения. Отсюда следует, что в общей граничной точке любых двух смежных интервалов ее значение равно одновременно пределу справа и слева. Эти значения, в свою очередь, совпадают с ее значениями на смежных интервалах. А это значит, что функция на смежных интервалах, включая точку их общей границы, постоянна. Следовательно, она постоянна на всем интервале (а, 6), что и требовалось доказать.
Определение 3. Совокупность всех первообразных функций для какой-либо одной функции /(ж) яа интервале называется неопределенным интегралом от функции /(ж). Эта совокупность обозначается символом J f(x)dx (читается: интеграл от f(x)dx).
Из теоремы 2 следует, что все функции этой совокупности отличаются друг от друга на постоянную. Поэтому, если F^) — какая-нибудь одна первообразная, то можно записать равенство
F1(X)-F2(X) = C.
(1)
где с — произвольное число.
167 Это равенство надо понимать как равенство двух множеств, состоящих из функций, определенных на (а, 6), причем слева стоит совокупность, образующая неопределенный интеграл от /(х), а справа — совокупность функций, отличающаяся от функции ^(ж) на функцию, значение которой равно числу с для всех точек х этого интервала.
