Лекции по математическому анализу - Архипов Г.И.
ISBN 5-06-003596-4
Скачать (прямая ссылка):
160 Зал ем в качестве 1\ берем один из отрезков [а, агі] или [ж'і,6] так, чтобщ число о; вновь находилось между значениями f(x) на его концах, т.е. на концах отрезка 1\ функция f(x) — а имеет значения разных знаков. По тому же правилу находим I2 и т.д. Получим систему вложенных отрезков: Iq D і і D ¦¦ D In D ¦ Как известно, они содержат общую точку с.
Если, например, f'(x) > 0, то f(x) не убывает, и тогда из непрерывности f(x) следует, что /(с) = а, поскольку на концах каждого из отрезков In функция ^f(x) = f(x) — а имеет значения разных знаков.
Метод касательных. Этот метод состоит в следующем. Пусть для простоты а = 0. (Если это не так, то вместо уравнения /(я) ~ а рассмотрим уравнение д(х) = 0, где д(х) = f(x) — а.) Величину х\ определим из соотношения
Ь-Х! 'W ' /'(6)'
При п> 1 далее имеем
/ы
Хп+1 = Xn-
В обоих методах надо еще уметь определить момент, когда следует оборвать процесс вычислений. Чтобы упростить решение этого вопроса и сократить объем вычислений, применяют следующий комбинированный метод.
Метод хорд и касательных; Сущность этого метода состоит в нахождении пар точек хп,уп, подчиненных следующему условию хп < с < уп. Схема вычисления величин хп и уп такова. Пусть f"{x) > 0 на I0 = [а, 6]. Определим х\ по методу хорд, a yi — по методу касательных. Тогда имеем х\ < с < у\, и далее за 1\ принимаем отрезок [агьз/ij. Точно так же, находя X2 по. методу хорд, а у2 по метрду касательных, получим отрезок I2 = [х2,у2] и т.д. Как только окажется, что jx„ — yn| < $, на этом процесс—вычисления с с точностью до S обрывают.
Пример. Пусть f(x) = X2 — а, а = 0, а = 2.
Применим метод касательных. Для определенности положим хо = 1 ¦ Величина хп+і определяется по формуле
fM _ _ х2п~ а хп а
Лп+1 — хп 777 г — хп - — хп — г
f'(xn) Ixn 2 eIxn
Секции по математическому аналізу
161 Для того чтобы выяснить, как быстро сходится этот вычислительный процесс, проведем оценку погрешности на (n-f 1)-м шаге. С этой целью обозначим через г„ величину r„ = Iv^ — хп|. Тогда
г2 = {у/а-хп)2 = а-2жпЧ/а+Жп>
откуда
Из неравенства > Vab получаем, что при n > 1
хл+і=Kxn+1) -
Следовательно,
г2 г2
гп+1 < TTT= < Hr» так как « = 2.
Iya і
Отсюда можем заключить, что если хп приближает у/а с точностью до к десятичных знаков после запятой, т.е. гп < 10"*, то xn+i приближает у/а уже с точностью д® 2к знаков, т.е. rn+i < 10-2Л. Если за хо возьмем, например, число 1,4, которое, как известно, приближаем
V2 с точностью до одного знака, т.е. \у/2 — 1,4| < IO-1, то получим гі < IO"2, г2 < IO-4, ..., тп < Ю-2"1, ... Мы видим, что за п шагов точность составит величину, не меньшую чем к знаков, где к = 2n. Так что для вычисления числа у/і с заданной точностью в к знаков достаточно выполнить п итераций, где
n = (log2A]+l.
Такого же типа оценки для метода Ньютона имеют место и в общем случае решения уравнения /(х) = 0, если начальное приближение взято достаточно "хорошим". Доказательство этого утверждения основано на применении формулы Тейлора с разложением до второго члена.
Обратим внимание на следующий факт: при оценке эффективности вычислительного алгоритма надо обращать внимание не только на количество итераций, но и на количество арифметических операций в каждой итерации. Например, при вычислении у/а количество
162- арифметических операций в каждой итерации равно 3: одно деление, одно сложение и одно умножение. Следовательно, для вычисления у/а с точностью до к знаков надо выполнить 3[log2 к] + 3 арифметических операций. Но и это еще не все. Во-первых, надо иметь в виду, что нет необходимости в начальных итерациях учитывать все к знаков, так как точность • приближения от этого не возрастает; во-вторых, проводить деление в столбик 'гораздо труднее, чем умножать числа, а умножать труднее, чем складывать.
Отметим, что метод Ньютона дает возможность заменить деление умножением. Действительно, имеем
• f(x) - - - a, Xo = 1.
X
Тогда
„ /(*«) __ і/*п - о _ 2
*п+1 — хп — —г г — Xn 5 — ?хп ах .
/'(xn) -Xfxl
Как и раньше, имеем
Гп
I
--Xn
Qf
2 1 2хп о о 1 , ч.
r^ = + *п> агп = - - (2xn + а<) = гп+1
а* а а
Теперь, например, при а < 1 и г0 < IO-1 для величины п — количества итераций — при вычислении с точностью до к десятичных знаков после запятой имеем п < [Iog2 к] + 1..
Еще более строгий подход к вопросу об эффективности вычислительного алгоритма состоит в учете операций над цифрами, с помощью которых записывается число. Тогда можно сказать, что, например, сложение двух n-значных натуральных чисел требует не более Зп операций, а "школьный" способ умножения чисел в столбик требует порядка п2 поразрядных умножений и порядка п2 сложений. Поэтому кажется естественным, что быстрее чем за 0{п2) операций умножить два n-значных числа нельзя. В 50-х гг. академик А.Н. Колмогоров поставил задачу доказать это, на первый взгляд, правильное утверждение. Но оказалось, что это не так,.
В 1961 г. A.A. Карацуба доказал замечательную теорему, которая положила начало совершенно новому направлению в вычислительной математике — теории быстрых вычислений. Он доказал, что два п-значных числа можно умножить не за 0(п2), а за Ofnlog33) операций.
