2

Пензенский государственный университет

Кафедра "Высшая и прикладная математика"

РЕФЕРАТ

По курсу «Математический анализ»

на тему «Приближенное решение алгебраических и трансцендентных уравнений. Метод Ньютона»

Выполнил: студент группы 08ВВ1

Чубарь Алексей

Проверил: доцент кафедры высшей и прикладной математики

Руденко Алевтина Кирилловна

Пенза, 2009

Содержание

• Биография Исаака Ньютона 3
• История метода 7
• Отделение корней 8
• Описание метода Ньютона (метода касательных) 10
• Оценка погрешности 15
• Метод хорд (линейной аппроксимации) 18
• Суть метода 18
• Погрешность 20
• Условие сходимости 21
• Метод половинного деления 22
• Суть метода 22
• Погрешность 23
• Пример решения уравнения методом Ньютона 25
• Список литературы 27
• Биография Исаака Ньютона
• Исаак Ньютон, сын мелкого, но зажиточного фермера, родился в деревне Вулсторп (графство Линкольншир), в год смерти Галилея и в канун гражданской войны. Отец Ньютона не дожил до рождения сына. Мальчик родился болезненным, до срока, но всё же выжил и прожил 84 года. Факт рождения под Рождество Ньютон считал особым знаком судьбы.
• Покровителем мальчика стал его дядя по матери, Вильям Эйскоу. В детстве Ньютон, по отзывам современников, был замкнут и обособлен, любил читать и мастерить технические игрушки: часы, мельницу и т. п. По окончании школы (1661) он поступил в Тринити-колледж (Колледж святой Троицы) Кембриджского университета. Уже тогда сложился его могучий характер -- научная дотошность, стремление дойти до сути, нетерпимость к обману и угнетению, равнодушие к публичной славе.
• Научной опорой и вдохновителями творчества Ньютона в наибольшей степени были физики: Галилей, Декарт и Кеплер. Ньютон завершил их труды, объединив в универсальную систему мира. Меньшее, но существенное влияние оказали другие математики и физики: Евклид, Ферма, Гюйгенс, Валлис и его непосредственный учитель Барроу.
• Похоже на то, что значительную часть своих математических открытий Ньютон сделал ещё студентом, в «чумные годы» 1664--1666. В 23 года он уже свободно владел методами дифференциального и интегрального исчислений, включая разложение функций в ряды и то, что впоследствии было названо формулой Ньютона-Лейбница. Тогда же, по его утверждению [2], он открыл закон всемирного тяготения, точнее, убедился, что этот закон следует из третьего закона Кеплера. Кроме того, Ньютон в эти годы доказал, что белый цвет есть смесь цветов, вывел формулу «бинома Ньютона» для произвольного рационального показателя (включая отрицательные), и др.
• Все эти эпохальные открытия были опубликованы на 20-40 лет позже, чем были сделаны. Ньютон не гнался за славой. Стремление открыть истину было у него главной целью.
• 1667: эпидемия чумы отступает, и Ньютон возвращается в Кембридж. Избран членом Тринити-колледжа, а в 1668 году становится магистром.
• В 1669 году Ньютон избирается профессором математики, преемником Барроу. Барроу пересылает в Лондон сочинение Ньютона «Анализ с помощью уравнений с бесконечным числом членов», содержавшее сжатое изложение некоторых наиболее важных его открытий в анализе. «Анализ» получил некоторую известность в Англии и за её пределами. Ньютон готовит полный вариант этой работы, но найти издателя так и не удаётся. Она была опубликована лишь в 1711 году.
• Продолжаются эксперименты по оптике и теории цвета. Ньютон исследует сферическую и хроматическую аберрации. Чтобы свести их к минимуму, он строит смешанный телескоп-рефлектор (линза и вогнутое сферическое зеркало, которое полирует сам). Всерьёз увлекается алхимией, проводит массу химических опытов.
• 1672: демонстрация рефлектора в Лондоне вызывает всеобщие восторженные отзывы. Ньютон становится знаменит и избирается членом Королевского общества (британской Академии наук). Позже усовершенствованные рефлекторы такой конструкции стали основными инструментами астрономов, с их помощью были открыты иные галактики, красное смещение и др.
• Разгорается полемика по поводу природы света с Гуком, Гюйгенсом и другими. Ньютон даёт зарок на будущее: не ввязываться в научные споры. В письмах он жалуется, что поставлен перед выбором: либо не публиковать свои открытия, либо тратить всё время и все силы на отражение недружелюбной дилетантской критики. Судя по всему, он выбрал первый вариант.
• 1680: Ньютон получает письмо Гука с формулировкой закона всемирного тяготения, послужившее, по признанию первого, поводом его работ по определению планетных движений (правда, потом отложенных на некоторое время), составивших предмет «Начал». Впоследствии Ньютон по каким-то причинам, быть может, подозревая Гука в незаконном заимствовании каких-то более ранних результатов самого Ньютона, не желает признавать здесь никаких заслуг Гука, но потом соглашается это сделать, хотя и довольно неохотно и не полностью [3].
• 1684--1686: после долгих уговоров Ньютон соглашается опубликовать свои главные достижения. Работа над «Математическими началами натуральной философии» (весь трёхтомник издан в 1687 году). Приходят всемирная слава и ожесточённая критика картезианцев: закон всемирного тяготения вводит дальнодействие, несовместимое с принципами Декарта.
• В 1689 году Ньютон был в первый раз избран в парламент от Кембриджского университета и заседал там немногим более года. Второе избрание состоялось в 1701--1702 годах.
• 1696: Королевским указом Ньютон назначен смотрителем Монетного двора (с 1699 года -- директор). Он энергично проводит денежную реформу, восстанавливая доверие к основательно запущенной его предшественниками монетной системе Великобритании.
• 1699: начало открытого приоритетного спора с Лейбницем, в который были вовлечены даже царствующие особы. Эта нелепая распря двух гениев дорого обошлась науке -- английская математическая школа вскоре увяла на целый век, а европейская -- проигнорировала многие выдающиеся идеи Ньютона, переоткрыв их много позднее. На континенте Ньютона обвиняли в краже результатов Гука, Лейбница и астронома Флемстида, а также в ереси. Конфликт не погасила даже смерть Лейбница (1716).
• В 1703 году Ньютон был избран президентом Королевского общества и управлял им до конца жизни -- более двадцати лет.
• 1705: королева Анна возводит Ньютона в рыцарское достоинство. Отныне он сэр Исаак Ньютон. Впервые в английской истории звание рыцаря присвоено за научные заслуги.
• Последние годы жизни Ньютон посвятил написанию «Хронологии древних царств», которой занимался около 40 лет, и подготовкой третьего издания «Начал».
• В 1725 году здоровье Ньютона начало заметно ухудшаться (каменная болезнь), и он переселился в Кенсингтон неподалёку от Лондона, где и скончался ночью, во сне, 20 (31) марта 1727 года. Похоронен в Вестминстерском аббатстве.
• Надпись на могиле Ньютона гласит:
• «Здесь покоится сэр Исаак Ньютон, дворянин, который почти божественным разумом первый доказал с факелом математики движение планет, пути комет и приливы океанов.
• Он исследовал различие световых лучей и появляющиеся при этом различные свойства цветов, чего ранее никто не подозревал. Прилежный, мудрый и верный истолкователь природы, древности и Св. писания, он утверждал своей философией величие Всемогущего Бога, а нравом выражал евангельскую простоту.
• Пусть смертные радуются, что существовало такое украшение рода человеческого»
• На статуе, воздвигнутой Ньютону в 1755 г. в Тринити-колледже, высечены стихи из Лукреция:
• «Qui genus humanum ingenio superavit (Разумом он превосходил род человеческий)»
• Сам Ньютон оценивал свои достижения более скромно:
• Не знаю, как меня воспринимает мир, но сам себе я кажусь только мальчиком, играющим на морском берегу, который развлекается тем, что время от времени отыскивает камешек более пёстрый, чем другие, или красивую ракушку, в то время как великий океан истины расстилается передо мной неисследованным.
• По словам А. Эйнштейна, «Ньютон был первым, кто попытался сформулировать элементарные законы, которые определяют временной ход широкого класса процессов в природе с высокой степенью полноты и точности» и «… оказал своими трудами глубокое и сильное влияние на всё мировоззрение в целом».

История метода

Метод был описан Исааком Ньютоном в рукописи «De analysi per aequationes numero terminorum infinitas» (лат. Об анализе уравнениями бесконечных рядов), адресованной в 1669 году Барроу, и в работе «De metodis fluxionum et serierum infinitarum» (лат. Метод флюксий и бесконечные ряды) или «Geometria analytica» (лат. Аналитическая геометрия) в собраниях трудов Ньютона, которая была написана в 1671 году. В своих работах Ньютон вводит такие понятия, как разложение функции в ряд, бесконечно малые и флюксии (производные в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в 1711 году благодаря Уильяму Джонсону, вторая была издана Джоном Кользоном в 1736 году уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения xn, а последовательность полиномов и в результате получал приближённое решение x.

Впервые метод был опубликован в трактате «Алгебра» Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе Analysis aequationum universalis (лат. Общий анализ уравнений). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений xn вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.

В 1879 году Артур Кэли в работе The Newton-Fourier imaginary problem (англ. Проблема комплексных чисел Ньютона-Фурье) был первым, кто отметил трудности в обобщении метода Ньютона на случай мнимых корней полиномов степени выше второй и комплексных начальных приближений. Эта работа открыла путь к изучению теории фракталов.

Отделение корней

Во многих приближённых методах нахождения корня уравнения заранее требуется знать какой-либо отрезок, на котором лежит искомый корень, и притом только один этот корень (то есть предъявляемый отрезок не должен содержать других корней уравнения). В этом случае говорят, что корень отделён на отрезке. Отделить корень - значит указать такой отрезок, на котором корень отделён. Заметим, что отделить корень можно не единственным образом: если корень отделён на каком-либо отрезке, то годится и любой меньший отрезок, содержащий этот корень. Вообще говоря, чем меньше отрезок, тем лучше, но при этом не следует забывать о том, что на отделение корня на меньших отрезках также тратятся вычислительные усилия, и, быть может, весьма значительные. Таким образом, часто для начала довольствуются весьма широким отрезком, на котором корень отделён.

Кроме того, часто нужно знать начальное приближение x0 к корню (который, заметим, неизвестен). В качестве этого начального приближения берут, как правило, любую точку отрезка, на котором отделён корень, например, его середину, если описание метода не предписывает поступить как-нибудь иначе.

Приведём некоторые утверждения, которые могут помочь при отделении корня.

Теорема 1 Если функция непрерывна на отрезке, причём значения её в концах отрезка и - это числа разных знаков, то на отрезке лежит по крайней мере один корень уравнения.

Практический смысл теоремы в том, что если мы, вычисляя значения функции в некоторых точках, видим, что вычисление в двух соседних точках даёт значения разных знаков, то на отрезке между этими точками лежит отыскиваемый корень. Если же известно заранее, что корень один, то получаем, что корень отделён на найденном отрезке. Этот же способ, когда мы наугад вычисляем значения функции в каких-то точках, может привести к отделению корней и в случае, когда корней несколько, но заранее известно их число или хотя бы оценка сверху для их количества. Рассмотрим иллюстрирующий сказанное пример.

Теорема 2 Если функция строго монотонна на отрезке, то есть возрастает или убывает на, то на этом отрезке уравнение не может иметь более одного корня.

Доказательство сразу следует из того, что строго монотонная функция принимает каждое своё значение ровно один раз. Если 0 является значением функции, то и значение 0 принимается один раз, то есть уравнение имеет один корень.

Тем самым, если отрезок, на котором заведомо имеется хотя бы один корень (например, если и - разного знака), - это отрезок строгой монотонности функции, то на отделён ровно один корень.

Заметим, что интервалы монотонности функции можно отыскивать, решая неравенства (что соответствует возрастанию функции) и (что соответствует убыванию).

Описание метода Ньютона (метода касательных)

Пусть корень уравнения f(x) = 0 отделён на отрезке, причем f'(x) и f''(x) непрерывны и сохраняют определённые знаки при . Найдя какое-нибудь n-e приближение корня n (), мы можем уточнить его по Методу Ньютона следующим образом. Пусть , где hn малая величина. Отсюда, применяя формулу Тейлора, получим:

Следовательно,

Внеся эту поправку в формулу (2), получим следующее по порядку приближение корня:

(n=0,1,2…).

Геометрически метод Ньютона эквивалентен замене небольшой дуги кривой y=f(x) касательной, проведенной в некоторой точке кривой. в самом деле, положим для определённости, что f''(x)>0 при и f(b)>0 (рис. 1).

Выберем, например, х0=b, для которого f(x)f''(x)>0. Проведем касательную к кривой y=f(x) в точке B0 (x0, f(x0)).

В качестве 1-го приближения x1 корня возьмем абсциссу точки пересечения этой касательной с осью Ox. Через точку B1(x1, f(x1)) снова проведем касательную, абсцисса точки пересечения которой с Ox даст нам 2-е приближение x2 корня и т.д. (рис. 1). Очевидно, что уравнение касательной в точке Bn (xn, f(xn)) (где n=0,1,2…) есть

Полагая, что у=0, x=xn+1,получим формулу (3):

.

Заметим, что если в нашем случае положить х0=a и, следовательно, f(x)f''(x)<0, то, проведя касательную к кривой y=f(x)в точке A(a, f(a)) , мы получили бы точку x1' (рис. 1), лежащую вне отрезка [а, b], т. е. при этом выборе начального значения метод Ньютона оказывается непрактичным. Таким образом, в данном случае «хорошим» начальным приближением х0 является то, для которого выполнено неравенство

(4)

Докажем, что это правило является общим.

Теорема. Если f(a)f(b)<0, причем f'(x) и f" (х) отличны от нуля и сохраняют определенные знаки при , то, исходя из начального приближения удовлетворяющего неравенству (4), можно вычислить методом Ньютона (формула (3)) единственный корень уравнения (1) с любой степенью точности.

Доказательство. Пусть, например, f(a)< 0, f(b)>0, f'(x) >0, f''(x)>0 при (остальные случаи рассматриваются аналогично). Согласно неравенству (4) имеем f(x0) >0 (например, можно принять х0 = b).

Методом математической индукции докажем, что все приближения xn>(n = 0, 1, 2,...) и, следовательно, f(xn)>0. В самом деле, прежде всего, x0 >.

Пусть теперь xn>. Положим

Применяя формулу Тейлора, получим:

где <cn<xn.

Так как f''(x)>0, то имеем:

и, следовательно,

что и требовалось доказать.

Из формулы (3), учитывая знаки f(xn) и f'(хn), имеем хn+1 < хn (n = 0, 1, ...), т. е. последовательные приближения x0, x1,…, хn, ... образуют ограниченную монотонно убывающую последовательность. Следовательно, существует .

Переходя к пределу в равенстве (3), будем иметь:

т.е. f()=0. Следовательно, =, что и требовалось доказать.

Поэтому, применяя метод Ньютона, следует руководствоваться следующим правилом: в качестве исходной точки х0 выбирается тот конец интервала (а, b), которому отвечает ордината того же знака, что и знак f"(x).

Замечание 1. Если:

1. функция f(x) определена и непрерывна при ;

2. f(a)f(b)<0;

3. f'(x)при ;

4. f"(x) существует всюду и сохраняет постоянный знак, то при применении метода Ньютона для нахождения корня уравнения f(x) = 0, лежащего в интервале (а, b), за начальное приближение x0 можно принять любое значение . В частности, можно взять x0=a или x0=b.

Действительно, пусть, например, f'(x) > 0 при , f"(x )>0 и х0 = с, где .

Если f(с) = 0, то корень = с и задача, таким образом, решена.

Если f(c) > 0, то справедливо приведенное выше рассуждение и процесс Ньютона с начальным значением с сходится к корню .

Наконец, если f(с) <0, то находим значение

Применяя формулу Тейлора, будем иметь:

где --некоторое промежуточное значение между с и х1. Таким образом, f(x1)f''(x1)>0.

Кроме того, из условия f"(x) >0 вытекает, что f' (х) -- возрастающая функция и, значит, f'(x) > f' (а) > 0 при х>а. Следовательно, х1 можно принять за начальное значение для процесса Ньютона, сходящегося к некоторому корню функции f(x) такому, что > с а. Так как в силу положительности производной f' (х) при х > а функция f(x) имеет единственный корень на интервале (а, +), то =.

Аналогичное рассмотрение можно провести для других комбинаций знаков производных f'(x)и f"(x).

Замечание 2. Из формулы (3) видно, что чем больше численное значение производной f'(x) в окрестности данного корня, тем меньше поправка, которую нужно прибавить к n-му приближению, чтобы получить (n+l)-e приближение. Поэтому метод Ньютона особенно удобно применять тогда, когда в окрестности данного корня график функции имеет большую крутизну. Но если численное значение производной f'(x) близ корня мало, то поправки будут велики, и вычисление корня по этому методу может оказаться очень долгим, а иногда и вовсе невозможным. Следовательно, если кривая y=f(x) вблизи точки пересечения с осью Ох почти горизонтальна, то применять метод Ньютона для решения уравнения f(x) = 0 не рекомендуется.

Оценка погрешности

Для оценки погрешности n-го приближения хn можно воспользоваться общей формулой.

(6)

где m1 -- наименьшее значение | f'(x)|на отрезке [а, b].

Выведем еще одну формулу для оценки точности приближения xn. Применяя формулу Тейлора, имеем:

(7)

где . Так как в силу определения приближения хп имеем

то из (7) находим:

где М2 -- наибольшее значение |f" (х)| на отрезке [а, b]. Следовательно, на основании формулы (6) окончательно получаем:

Если процесс Ньютона сходится, то хп- хп-1 0 при п-->. Поэтому при п имеем:

т.е. «установившиеся» начальные десятичные знаки приближений xn-1 и xn начиная с некоторого приближения, являются верными.

Заметим, что в общем случае совпадение с точностью до е двух последовательных приближений хп-1 и хп вовсе не гарантирует, что с той же точностью совпадает значение хп и точный корень | (рис. 19).

Установим также формулу, связывающую абсолютные погрешности двух последовательных приближений хп и xn+1. Из формулы (5) получаем:

где . Отсюда, учитывая формулу (3), будем иметь:

и, следовательно,

(9)

Формула (9) обеспечивает быструю сходимость процесса Ньютона, если начальное приближение х0 таково, что

В частности, если

то из формулы (9) получаем:

т.е. в этом случае, если приближение хп имело m верных десятичных знаков после запятой, то следующее приближение хп+1 будет иметь по меньшей мере 2т верных знаков; иными словами, если , то с помощью метода Ньютона число верных знаков после запятой искомого корня удваивается на каждом шаге.

Метод хорд (линейной аппроксимации)

Информация о предыдущих приближениях корня используется для нахождения последующих приближений не только в методе касательных. В качестве примера другого такого метода мы приведём метод, основанный на нахождении xi + 1 по двум предыдущим приближениям xi и xi ? 1 с помощью линейной интерполяции, называемый методом хорд.

Идея метода состоит в том, что по двум точкам Mi ? 1(xi ? 1;f(xi ? 1)) и Mi(xi;f(xi)) построить прямую Mi ? 1Mi (то есть хорду, соединяющую две точки графика y = f(x)) и взять в качестве следующего приближения xi + 1 абсциссу точки пересечения этой прямой с осью Ox. Иными словами, приближённо заменить на этом шаге функцию f(x) её линейной интерполяцией, найденной по двум значениям : x и xi ? 1. (Линейной интерполяцией функции f(x) назовём такую линейную функцию , значения которой совпадают со значениями f(x) в двух фиксированных точках, в данном случае -- в точках xi ? 1 и xi.)

Уравнение хорды - это уравнение прямой, проходящей через две точки (a, f(a)) и (b, f(b)).

В зависимости от того, лежат ли точки xi ? 1 и xi по разные стороны от корня x * или же по одну и ту же сторону, получаем такие чертежи:

Рис 3. Построение последовательного приближения по методу хорд: два случая.

Итак, очередное последовательное приближение будет зависеть от двух предыдущих: . Найдём выражение для функции .

Интерполяционную линейную функцию будем искать как функцию с угловым коэффициентом, равным разностному отношению

построенному для отрезка между xi ? 1 и xi, график которой проходит через точку Mi:

Решая уравнение , находим

то есть

(1)

Заметим, что величина ki может рассматриваться как разностное приближение для производной f'(x) в точке xi. Тем самым полученная формула (1) -- это разностный аналог итерационной формулы метода Ньютона. Вычисление по формуле (1) гораздо предпочтительнее вычисления по другой полученной нами формуле

хотя эти две формулы математически тождественны, поскольку при использовании формулы (1) в случае вычислений с округлениями (например, на компьютере) достигается меньшая потеря значащих цифр.

Погрешность

Имеются две разновидности применения формулы (1). Первая разновидность: вычисления ведутся непосредственно по формуле (1) при , начиная с двух приближений x0 и x1, взятых, по возможности, поближе к корню x * . При этом не предполагается, что x * лежит между x0 и x1 (и что значения функции f в точках x0 и x1 имеют разные знаки). При этом не гарантируется, что корень попадёт на отрезок между xi ? 1 и xi на каком-либо следующем шаге (хотя это и исключено). В таком случае затруднительно дать оценку погрешности, с которой xi + 1 приближает истинное значение корня x * , и поэтому довольствуются таким эмпирическим правилом: вычисления прекращают, когда будет выполнено неравенство , где - желаемая точность нахождения корня. При этом полагают приближённое значение корня равным .

Условие сходимости

Достаточное условие сходимости, таково: Это неравенство может быть переписано в виде откуда получаем, что сходимость гарантируется, когда, во-первых, так как (тем самым проясняется смысл выбора знака числа ), а во-вторых, когда при всех X на всём рассматриваемом отрезке, окружающем корень. Это второе неравенство заведомо выполнено, если

где . Таким образом, угловой коэффициент K не должен быть слишком мал по абсолютной величине: при малом угловом коэффициенте уже на первом шаге точка X[1] может выскочить из рассматриваемой окрестности корня X[*] , и сходимость итераций к корню может быть нарушена.

Метод половинного деления

Пусть  - заданная точность, с которой требуется отыскать корень. Процесс деления отрезков следует остановить, как только станет верным неравенство . Очевидно, что если при этом положить

то расстояние от корня , лежащего где-то в интервале , до середины этого интервала будет не больше , то есть приближённое равенство будет выполнено с нужной точностью. C увеличением точности заметно возрастает объем вычислительной работы, поэтому метод удобно применять для нахождения грубого корня уравнения.

Метод легко реализуется на ЭВМ.

Пример решения уравнения методом Ньютона

Уравнение:

, .

f(0)=1

f''(0)=1

Следовательно, при x=1 f(x)f''(x)>0. Начальное приближение x0=0.

f'(x)=

f'(x)0 при

Вывод: в третьем приближении получен результат с 4-мя точными знаками после запятой: .

Ответ:

Список литературы

· «Основы вычислительной математики», Б. П. Демидович, И.А. Марон, 1966г.

· Материалы электронной библиотеки http://elib.ispu.ru/