Архипов, Садовничий - Лекции по математическому анализу (940510), страница 27

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 27)

Пример. Пусть 1(х) = хт — а, а = О, а = 2. Применим метод касательных. Для определенности положим хс — — 1. Величина х»+~ определяется по формуле 1(х„) хт — о х„ а 1 / а '1 х»+! = х» — —," — — х» — —" = х» — — + — = — х» +— 1'(х„) 2х„ " 2 2х„ 2 1 " х„ ~ ~ з'мнп иа м»»»тн»»»ч е»е» Для того чтобы выяснить, как быстро сходится этот вычислительный процесс, проведем оценку погрешности на (в+1)-м шаге.

С этой целью обозначим через г„величину г„= (тД вЂ” х„(. Тогда гэ = (~Га — х„)т = а — 2х„~Га+ х~, откуда — = — ( — + х„— ~/а = г„+ь 2х„2 (,х„ Из неравенства Яхта > ~/аэ получаем, что при в > 1 1/ а1 х«+1 = — ~х«+ — ) > ~/аш 2~ х«) Следовательно, х 2 г„г„ г«+1 « — —, так как а = 2.

2~/а 2 ' Отсюда можем заключить, что если х„приближает ~/а с точностью до к десятичных знаков после запятой, т.е. г„< !О ~, то х„+1 приближает с/а уже с точностью дэ 2х знаков, т.е. г„э1 < 10 т". Если за хэ возьмем, например, число 1,4, которое, как известно, приближает ~/2 с точностью до одного знака, т.е. (ъГ2 — 1,4( < 10 ', и уч <Ыт, ~<10~, ..., „<10т, ...Мы д что за в шагов точность составит величину, не меньшую чем х знаков, где и = 2", Тах что для вычисления числа ~/2 с заданной точностью в х знаков достаточно выполнить и итераций, где в = ((ойэ х) + 1. Такого же типа оценки для метода Ньютона имеют место и в общем случае решения уравнения у(х) = О, если начальное приближение взято достаточно "хорошим".

Доказательство этого утверждения основано на применении формулы Тейлора с разложением до второго члена. Обратим внимание на следуюшяй факт; при оценке эффективности вычислительного алгоритма надо обращать внимание не тоЛько на количество итераций, но и на количество арифметических операций в каждой итерации. Например, при вычислении ~/а количество арифметических операций в каждой итерации равно 3: одно деление, одно сложение и одно умножение. Следовательно, для вычисления ~/а с точностью ло и знаков надо выполниъь 3(1ойз х) +3 арифметических операпий. Но и это еше ие все.

Во-первых, надо иметь в виду, что нет' необходимости в начальных итерациях учитывать все й знаков, так как точность приближения от этого не возрастает; во-вторых, проводить деление в столбик 'гораздо труднее, чем умножать числа, а умножать труднее, чем складывать. Отметим, что метод Ньютона дает возможность заменить деление умножением. Действительно, имеем ! /(х) = - - -, ха = 1.

х Тогда /(») 1/х х»+1 = х» — —, — — х» — —— 2х» — ах». /'(х») — 1/х~ Как и раньше, имеем )! 1 з 1 2х» з з 1 г» = — — х„1, г = — — — +х, аг = — — (2х»+ах ) = г»+ь )а 1» аР а»»=а»» Теперь, например, при а < 1 и го < 1О ' для величины ив количества итераций — при вычислении с точностью до й десятячных знаков после запятой имеем и < (1ойт Ц+ 1., Еще более строгий подход к вопросу об эффективности вычислительного алгоритма состоит в учете операций над цифрами, с помощью которых записывается число.

Тогда можно с)газать, что, например, сложение двух и-значных натуральных чисел требует не более Зп операций, а "школьный" способ умножения чисел в столбик требует порядка п~ поразрядных умножений и порядка пз сложений. Поэтому кажется-естественным, что быстрее чем за О(п~) операций умножить два и-значных числа нельзя.

В 50-х гг. академик А.Н. Колмогоров поставил задачу доказать это, на первый взгляд, правильное утверждение. Но оказалось, что это.не так. В 1961 г. А.А. Карацуба доказал замечательную теорему, которая положила начало совершенно новому направлению в вычислительной математике — теории быстрых вычислений. Он доказал, что два пзначных числа можно умножить не за 0(пз), а за 0(и'а з) операций. Т е о р е ае а (теорема А.А. Карацубы). Существует алгоритм, позволяющий умножить два и-значнгяк числа за 0(п"'к*з) операциЯ. Д о к о з а гп е л ь с ю е о.

Представим числа в двоичной записи: а = а„... ам 6 = 6„... 61. Заметим, что а6 = -((а+6) — (а — 6) ). 1 4 Для деления числа на 4 достаточно сдвинуть его на 2 разряда вправо, зто займет только 0(п) операций. Так что достаточно доказать, что возведение в квадрат и-значного числа потребует указанного числа операций.

Доказательство проведем по индукции. Пусть для простоты и = 2" н пусть а = 2"~г . а+ я, где а и Я вЂ” п/2-зпачные числа. Тогда имеет место тождество г, г(2к 2Мг) + (а + )у)г2е/г 1гг(2~/г ц Если число операций для возведения в квадрат и-значного числа обозначим через К(п), то К(п) < ЗК(п/2) + сп, К(п/2) < ЗК(п/4) + сп/2, К(2) < ЗК(1) + с, К(п) < 3» + с(п + 3- + Зг — + ° + 3~), где 6 = 1окг и. Отсюда имеем К(п) < 3~(Зс+ 1).

Теорема доказана. В заключение укажем на одно соображение общего характера, лежащее в основе многих итерационных вычислительных алгоритмов. Пусть требуется найти значение функции в точке хе, т.е. вычислить Уо = У(хс) Обозначим через Х„приближение к /е с точностью Ь„ (до и десятичных знаков): Допустим, нам известна функция С(х) со следующим свойством: С(Уо) = Уо, С'(хи, = О. Тогда имеем С(У») — С(Уо)+ С (УОПУ» — Уо) + — (У» — Уо), С" Ы) откуда !Уо — С(У»)) < сЬ„„где с = )пах( — ~.

Теперь, полагая У„+1 = С(У»), получим приближение к Уо с точностью порядка 2п десятичных знаков после запятой. Тем самым мы имеем быстросходящийся алгоритм для приближенного вычисления значении Уо. Заметим, что рассмотренный выше алгоритм вычисления корня квадратного из числа хо является частным случаем данного при У(ха) = ~Ухо ои С(У») = ~~(У + та). Глава т'1 НЕОПРЕДЕЛЕННЫЙ ИНТЕГРАЛ Лекция 28 б 1. ТОЧНАЯ ПЕРВООБРАЗНАЯ. ИНТЕГРИРУЕМЫЕ ФУНКЦИИ Определение 1. Функция Р(х) называется точной первообразной для функции у(х) на (а,б), если аря любом х Е (а,б) имеем Р'(х) = у(х), т.е, в каждоМ точке х интервала (а, 6) значение функции ((х) является производной для функцяв г'(х). Т е о р е м а 1.

Пусть у(х) определена на (а, 6) я Р2(х), Р2(х)— две ее точные первообразные. Тогда су2цествует число с б'1к такое, что при любом х б (а, 6) Р2(х) — Рт(х) = с. Д о к а з а ц! е л ь с та в о. Пусть функция С(Х) — Р! (Х) Р2(Х). Тогда С(х) — днфференцнруемая функция, причем всюду на (а,б) С (х) = Р2(х) — Р2(х) — 1(х) — У(х) = б. Положим хо — — ~+. Тогда по формуле Лагранжа конечных прира2цений имеем С(х) — С(хо) = С'(0(» — хо) = О, т.е.

С(х) = С(хо) т х б (а, 6), Но, полагая с = С(хо), получим, что С(х) = с для всех точек х интервала (а,б). Теорема 1 доказана, Замечание. Из теоремы 1 следует такое утверждение: любые две первообразные Р(х) и С(х) функций у(х) и о(х) отличаются на константу тогда и только тогда, когда их производные совпадают, т.е. когда г' = у = а = С'. Ранее мы видели, что далеко ие все функции, заданные на каком-либо интервале (а,6), имеют производную.

Аналогично обстоит дело и с первообразной, т.е. не все функции имеют производную. Но если функция у(х), определенная на (а,Ь), имеет первообразную, то она называется интегрируемой. Прежде чем перейти к йзучению класса интегрируемых функций, несколько обобщим понятие точной первообразной.' Определение 2. Непрерывная фупкцяя Г(х) называется перво- образной функции у(х) па интервале (а, 6), если в каждой его точке х за исключением, быть может, конечного их числа выполпяется равенство г'(х) = у(х).

Т е о р е м н 2. Пусть 6'г(х) и Рг(х) — первообразпыв для функции у(х) па (а,Ь). Тогда найдется число с такое, что всюду па этом интервале рг(х) — Рг(х) = с. Д о к а з а вг е л ь с ю в в. Пусть хы, .., х„— конечное множество точек, на котором не существует Р((х) илн Рг(х). Тогда множество (а,6) состоит из конечного числа интервалов 4, на которых производные обеих функций существуют. Следовательно, по теореме 1 их разность постоянна на каждом таком интервале. Кроме того, эта разность является непрерывной функцией на всей области определения.

Отсюда следует, что в общей граничной точке любых двух смежных интервалов ее значение равно одновременно пределу справа и слева. Этн значения, в свою очередь, совпадают с ее значениями на смежных интервалах. А это значит, что функция на смежных интервалах, включая точку их обшей границы, постоянна. Следовательно, она постоянна на всем интервале (а,6), что н требовалось доказать. Определение 3. Совокупность всех первообразпых функций для какой-либо одной функции у(х) ла интервале называется неопределенным интегралом от функции Дх).

Эта совокупность обозначается символом ) Дх)ах (читается: интеграл от у(х)ах). Из теоремы 2 следует, что все функции этой совокупности отличаются друг от друга на постоянную. Поэтому, если г'(х) какая-нибудь одна первообразная, то можно записать равенство ~(х)Ых = Р(х) + с, где с — произвольное число. \БТ Это равенство надо понимать как равенство двух множеств, состоящих из функций, определенных на (а,6), причем слева стоит совокупность, образующая неопределенный интеграл от у(х), а справа — совокупность функций, отличающаяся от функции Р(х) на функцию, значение которой равно числу с для всех точек х этого интервала. Примеры. 1. ) 1 Их = х + с, так как х' = 1.

Характеристики

Список файлов лекций