Г.И. Архипов, В.А. Садовничий, В.Н. Чубариков - Лекции по математическому анализу (1108924), страница 26
Текст из файла (страница 26)
Для определения всех козффициентов интерполяционного многочлена Ньютона (и — 1)-й степени достаточно вычислить значения интерполируюших функций в -"-("-2='1 точках (с учетом кратности). Здесь существенно, что при добавлении новой точки интерполяции интерполируюшие функции, вычисленные ранее, сохраняются и надо только добавить к ним значения интерполируюших функций в атой точке. Т е о р е м а 2. Пусть функция Дх) имеет п-ю производную на отрезке [а,Ь), а < х1 < Х2 « х„< 6.
Тогда имеет место формула у(6) = Р„(Ь) + В(Ь), где у(-1(с) В(6) = , (Ь вЂ” х1) ...(Ь вЂ” х ), причем с — некоторая точка, принадлежа2цая (а,Ь). Д о х а з и га е л ь с га в о. Рассмотрим вспомогательную функцию В(х) = Дх) — Р„(х) — (х — х1)... (х — х„)Н, где Н вЂ” некоторое число, значение которого мы выберем ниже. Имеем В(х1) = = В(х„) = О. Величину Н найдем из соотношения В(6) = О. Отсюда по теореме Рояля, примененной п раз, получим, что существует числд с Е (а,6), для которого В1"1(с) = О, откуда у1" 1(с) — и! Н = О.
Следовательно, ~1"1(с) и! Теорема 2 доказана. Лекция 2Т Ь 17. МЕТОД ХОРД И МЕТОД КАСАТЕЛЬНЫХ (МЕТОД НЬЮТОНА). БЫСТРЫЕ ВЫЧИСЛЕНИЯ Пусть функция 1(х) дифференцируема на отрезке [а,6]. Тогда у(х) непрерывна на [а, Ь] и по теореме Коши о промежуточном значении для любого а б Ж, лежащего между числами з'(а) и у(6), внутри отрезка [а,6] найдется точка с такая, что Дс) = а. Естественной и важной задачей и в теоретическом, и в практическом смысле является задача вычисления приближенного значения числа с с наперед заданной точностью. Например, можно поставить вопрос о нахождении корня уравнения хт = 2 с точностью до десяти знаков после запятой, т.е.
для за найти приближенное значение са такое, чтобы имело место неравенство ]з/2 — со] ( 10 щ и т.п. Рассмотрим два естественных метода нахождения таких рриближенных значений, а именно: метод хорд и метод касательных, который еще называют методом Ньютона, поскольку Ньютон первым его применил. Эти методы важны не столько сами по себе, сколько тем, что они являются простейшей моделью многих вычислительных процессов, применяемых в гораздо более сложных ситуациях, Оба метода итерационные, т.е.
они состоят в последовательном вычислении некоторых чисел хь хт,, х„,.... При этом разность ]с — х„] -+ 0 при п -+ оо, и поэтому, начиная с некоторого номера пю она должна стать меньше наперед заданного значения, называемого заданной точностью или погрешностью вычисления. Метод хорд.
Число х~ определим как абсциссу точки пересечения горизонтальной прямой у = а с "хордой" графика функции у = 1(х), т.е. с отрезком, соединяющич точки (а,,1'(а)) и (Ь,~(Ь)). Обозначим отрезок [а,6] через 1ю Полагая А = Да) и В = ДЬ), исходя из подобия соответствующих треугольников для нахождения величины х~ имеем уравнения: а-А  — а а — В х~ — п 6 — х~ х~ — Ь Отсюда находим х~(а — А) — 6(а — А) = х~(а — В) — а(а — В), — а(а — В) + Ь(а — А)  — А 160 чэаем в качестве 1«берем один из отрезков [а,х«] или [х),Ь) так, чтобы число а вновь находилось между значеыиями 1(х) ыа его концах, т.е. на концах отрезка 1«функция 1(х) — а имеет значения разных зыаков.
По тому же правилу находим 1э и т.д. Получим систему вложенных отрезков: 1с Э 1«Э . Э 1„..« ... Как известно, онн содержат общую точку с, Если, например, 1"'(х) > О, то 1(х) не убывает, и тогда иэ непрерывности 1(х) следует, что 1(с) = о, поскольку на концах каждого из отрезков 1» функция д(х) = 1"(х) — о имеет значения разных знаков. Метод касательных. Этот метод состоят в следующем.
Пусть для простоты а = О. (Если зто не так, то вместо уравыеыия 1(х) = а рассмотрим уравнение д(х) = О, где д(х) = 1(х) — а.) Велычину х~ определим из соотношеныя 1(Ь), 1(Ь) = 1~(Ь) т.е. х~ = Ь вЂ” —, Ь -, ' 1«(Ь)' При и > 1 далее имеем У( .) х„+« — — х» — —, У (х») В обоих методах ыадо еще уметь определить момент, когда следует оборвать процесс вычислений. Чтобы упростить решение этого вопроса и сократить объем вычислений, применяют следующий комбинированный метод. Метод хорд и касательных. Сущность этого метода состоит в нахождении пар точек х»,у», подчиненных следующему условию х» < с < у», Схема вычисления величин х» и у» такова.
Пусть 1»(х) > О на 1с —— [а«Ь). Определим х«по методу хорд, а у~ по методу касательных. Тогда имеем х«< с < ум и далее за 1~ принимаем отрезок [хну«). Точыо так же, находя хэ по. методу хорд, а уэ по методу касательыых, получим отрезок 1э = [хэ,уэ) и т.д. Как только окажется, что [х» — у»[ < Ь, на этом процесс вычисления с с точностью до 6 обрывают. Пример. Пусть 1(х) = х« — а, о = О, а = 2.
Применим метод касательных. Для определенности положим хс — — 1. Величина х„+~ определяется по формуле 1(х„) хэ — а х» а 1 1' а »1 х»+1 — х» — х» — х» + = ( х» + [ ° «э «о««о ««««и«««»«««и ««о««« Для того чтобы выяснить, как быстро сходится этот вычислительный процесс, проведем оценку погрешности на (п+1)-м шаге. С этой целью обозначим через г» величияу г» = [т/а — х»(. Тогда г~ = (т/а — х»)~ = а — 2х»!/а + х~, откуда — = — ~ — + х» — !/а = г»ч!. 2х» 2 ~х» Из неравенства + ) !/а6 получаем, что при п > 1 1/ а'1 х»+! — ~х» + ( ~ ча 2!, х„/ Следовательно, г г» г» !'»+! « — —, так как а = 2. 2!/а 2 ' Отсюда можем заключить, что если *„приближает !/а с точностью до х десятичных знаков после запятой, т.е, г» < 10 ~, то х»е! пРнближает !/а Уже с точностью да 2й знаков, т.е.
!»е! < 10 ы. Если за хе возьмем, например, число 1,4, которое, как известно, прнближапт !/2 с точностью до одного знака, т.е. [!/2 — 1,4[ < 10 то получим г! < 10 з, гз < 10 ~, ..., г„< 1О з", ... Мы видим, что за п шагов точность составит величину, не меньшую чем х знаков, где х = 2». Так что для вычисления числа !/2 с заданной точностью в Й знаков достаточно выполнить п итераций, где Такого же типа оценки для метода Ньютона имеют место н в общем случае решения уравнения /(х) = О, если начальное приближение взято достаточно "корошим».
Доказательство этого утверждения основано на применения формулы Тейлора с разложением до второго члена. Обратим внимание на следующий факт: при оценке эффективности вычислительного алгоритма надо обращать внимание не только на количество итераций, но и на колячество арифметических операций в каждой итерации. Например, при вычисления,/е количество !62 арифметмческих операцмй в каждой итерацим равно 3: одно деление, одно сложение и одно умножение. Следовательно, для вычисления ~/а с точностью до А знаков надо выполнить 3[1ойт х]+3 армфметических операций.
Но и это еще не все, Во-первых, надо иметь в вмду, что нет' необходимости в начальных итерациях учитывать все х знаков, так как точность. приближения от этого не возрастает; во-вторых, проводить деление в столбик "гораздо труднее, чем умножать числа, а умножать труднее, чем складывать. Отметим, что метод Ньютона дает возможность заменмть деление умножением.
Действительно, имеем 1 У(х) = — — а, хэ = 1 х Тогда У(~ю) 1/хп а, з хп+~ = хп — —, = х1 — —— 2х„— ах„. ~ (х») ' 1/х» Как и раньше, имеем г„= — — х„, г„= — — — + х„, аг„= — — (2х„+ ах„) = г„+,. Теперь, например, прм а < 1 и ге < 1О ' для величины п количества итераций — при вычмслении с точностью до й десятичных знаков после запятой имеем и < (1ой~ Ц+ 1., Еще более строгий подход к вопросу об эффективности вычмслительного алгоритма состоит в учете операций над цифрами, с помощью которых записывается чксло. Тогда можно срезать, что, например, сложение двух и-значных натуральных чисел требует не более Зп операций, а пшкольмый" способ умножения чисел в столбик требует порядка пз поразрядных умножений и порядка пз сложенмй.
Поэтому кажется-естественным, что быстрее чем за 0(пз) операций умножить два и-значных числа нельзя, В 50-х гг, академмк А.Н, Колмогоров поставил задачу доказать это, на первый взгляд, правильное утверждение. Но оказалось, что это не так. В 1961 г. А.А. Карацуба доказал замечательную теорему, которая положила начало совершенно новому направлению в вычислмтельной математике — творим быстрых вычислений.
Он доказал, что два пзначных числа можно умножить не за 0(пз), а за 0(п"хпз) операцмй. Т е о р е ы а (теорема А.А. Карацубы). Существует апгорятм, позволяющий умножять два и-значитя чясла за О(п'~азз) операций. Д о к а з а ю е л ь с я2 е о. Представим числа в двоичной записи: а = а„. а2, Ь = Ьа . Ь2. ЗаМЕтнМ, Чта аЬ = 1((а+ Ь) — (а — Ь) ). 4 Для деления числа на 4 достаточно сдвинуть его на 2 разряда вправо, зто займет только 0(п) операций. Так что достаточно доказать, что возведение в квадрат и-значного числа потребует указанного числа операций.
Доказательство проведем по индукции. Пусть для простоты и = 2" и пусть а Зв/2 о+ «у где о и «У вЂ” и/2-значные числа. Тогда имеет место тождество а2 оз(2ч 2п/2) «(я «„ /1)22п/2 /12(2ч/2 ]) Если число операций для возведения в квадрат и-зяачного числа обозначим через К(п), то К(п) < ЗК(п/2) + сп, К(п/2) < ЗК(п/4) + сп/2, К(2) < ЗК(1) + с, К(п) < 3" +с(п+3 — +32 — + +3 ), 2 4 где Ь = 1ояз и.
Отсюда имеем К(п) < 3" (Зс+ 1). Теорема доказана. В заключение укажем на одно соображение общего характера, лежащее в основе многих итерационных вычислительных алгоритмов. Пусть требуется найти значение функции в точке *с, т.е. вычислить Уо = У(яс) Обозначим через /„ приближение к /с с точностью Ь„ (до и десятичных знаков): Допустим, нам известна функция С(х) со следующим свойством; С(У ) = У, С'( Н.=г. = О. Тогда имеем С(У ) С(Уо) + С (Уо)(У.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
