Нахождение корней уравнения методом Ньютона

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

УЧРЕЖДЕНИЕ  ОБРАЗОВАНИЯ «ПОЛОЦКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ»

 

 

 

Спортивно-педагогический факультет

 

Кафедра технологии и методики преподавания

 

 

 

 

 

 

 

КУРСОВАЯ  РАБОТА

по дисциплине «Вычислительные методы и компьютерное  моделирование»

на тему «Нахождение корней уравнения методом Ньютона»   

 

 

 

 

 

 

 

 

 

 

 

Выполнил                 Масиёнок П.В.

                                                                                    гр. 08-ТИ

 

 

 

 

Проверил (а)       пр. Т. М. Федулова

 

 

 

 

 

Новополоцк  2012

 

Содержание

 

Введение 3

Глава 1. Метод Ньютона 5

1.1 Геометрическая интерпретация метода Ньютона 5

1.2 Алгоритм решения задач с помощью метода Ньютона 7

Глава 2. Нахождение корней алгебраических уравнений методом Ньютона 8

2.1 Метод итерации 8

2.2 Пример поиска корней системы уравнений с помощью метода итераций 9

2.3 Метод ньютона 12

2.4 Пример поиска корней  уравнений с помощью метода Ньютона 14

Заключение 20

Список использованной литературы 21

 

 

 

ВВЕДЕНИЕ

 

Метод Ньютона (также известный как метод  касательных)— это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность.

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

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

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

  В качестве объекта выступает метод Ньютона (метод касательных).

Предметом курсовой работы является решение корней уравнения методом Ньютона.

Целью курсовой работы является нахождение корней уравнения методом Ньютона.

В соответствии с целью мною были сформулированы следующие задачи:

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

 

 

 

ГЛАВА 1. МЕТОД НЬЮТОНА

 

1.1 Геометрическая интерпретация  метода Ньютона

 

Пусть корень ξ уравнения f(x)=0 отделен  на отрезке [a,b]. Предположим мы нашли (n-1)-ое приближение корня xn-1. Тогда n-ое приближение xn мы можем получить следующим образом. Положим

xn = xn-1 + hn-1 . (1.1)

Раскладывая в ряд f(x=ξ) в точке xn-1, получим

f(xn) = f(xn-1+hn-1) = f(xn-1) + f’(xn-1)hn-1=0

Отсюда следует

 h_n-1 (1.2)

Подставим (1.2) в формулу (1.1), получим

 X_n = x_n-1 -   n=1,2,… (1.3)

 

Рис.1. Геометрическая интерпретация метода Ньютона

 

Геометрически метод Ньютона эквивалентен замене дуги кривой y=f(x) касательной, проведенной  в некоторой точке кривой (см. рис.1).

В точке B имеем f(x0)f’’(x0)>0. Здесь x0=b. Проведем касательную в точке B, получим  на пересечении касательной осью OX точку x1. Далее проводим касательную  в точке B1, получим точку x2 и т.д.

Если положить x0=a, то в точке x0 будем  иметь f(x0)f’’(x0)<0. Тогда  касательная  в точке A пересекла бы ось OX в  точке x’1, лежащей вне отрезка [a,b], то есть при таком выборе начальной точки, метод Ньютона оказывается расходящимся. Достаточные условия сходимости метода Ньютона определяются следующей теоремой.

Теорема 5. Если f(a)f(b)<0, причем f’(x) и f’’(x) отличны от нуля и сохраняют  определенные знаки при a≤x≤b, то исходя из начального приближения x₀ ϵ[a,b], удовлетворяющего неравенству

f(x0)f’’(x0)>0 (1.4)

можно вычислить методом Ньютона (1.3) единственный корень ξ уравнения f(x)=0 с любой степенью точности.

Доказательство: Пусть . Согласно неравенству (1.4) в качестве точки x0 мы должны взять ту границу отрезка, для которой f(x0)>0, т.е. в данном случае т. b.

Итак, имеем x0>ξ. Докажем, что все  приближения xn> ξ и следовательно все f(xn)>0. Пусть теперь xn-1> ξ. Положим

 ξ = xn-1 + (ξ-xn-1).

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

,

где ξ <cn-1<xn-1.

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

 

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

  ч.т.д. (1.5)

Из (1.5) учитывая знаки и имеем xn<xn-1, то есть получаем ограниченную монотонную убывающую последовательность . Следовательно, существует .

Переходя к пределу в формуле (1.3) получим

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

Оценим скорость сходимости метода Ньютона. Из (1.4) следует

. (1.6)

Представим f(ξ) в виде

, откуда

. (1.7)

Подставим (1.7) в (1.6), получим

Отсюда 

. (1.8)

Здесь

Рис.2. Геометрическая интерпретация метода Ньютона

 

Таким образом, скорость сходимости метода Ньютона квадратичная.

Критерий завершения итерационного  процесса имеет вид

|xn – xn-1|<ε.

Замечание. В общем случае совпадение с точностью до ε двух последовательных приближений xn-1 и  не гарантирует, что  с той же точностью совпадет xn и ξ (см. рис. 2). Поэтому целесообразно проверять кроме разности |xn – xn-1|<ε также значение функции f(xn): |f(xn)|< ε1.

 

1.2 Алгоритм решения  задач с помощью метода Ньютона

 

- определяем интервал (если он не задан), которому будет принадлежать корень уравнения.  Сужение интервала можно производить методом половинного деления.

- находим f ¢(x) и f ²(x), причем f ¢(x) ¹ 0 при xÎ[a;b], f ¢(x) и f ²(x)  должны сохранять знак на отрезке [a;b] 

- выбираем один из концов  отрезка [a,b] за x₀, исходя из того, что должно выполняться следующее условие f(x₀)·f ²(x₀)>0.

- вычисляем  , пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e - до выполнения неравенства | x_i-x_i-1| < e.

ГЛАВА 2. НАХОЖДЕНИЕ КОРНЕЙ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ МЕТОДОМ НЬЮТОНА

 

1. Метод итерации

 

Как и в  случае одного уравнения, метод простых  итераций заключается в замене исходной системы уравнений эквивалентной  системой х=φ(х), где

 

 и построении итерационной последовательности х(k+1) = φ (х(k)), где k=1,2,3,… - номер итерации, которая при k→∞ сходится к точному решению.

Сущность  этого метода заключается в следующем. Пусть дано уравнение

f(x)=0. (1)

где f(x) –  непрерывная функция, и требуется  определить его вещественные корни. Заменим уравнение (1) равносильным уравнением

x=j (x). (2)

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

x1=j (x0). (3)

Подставляя  теперь в правую часть равенства (3) вместо x0 число x1 получим новое  число x2=j (x1). Повторяя этот процесс, будем  иметь последовательность чисел

xn=j (xn-1) (n=1, 2,...). (4)

Если эта  последовательность – сходящаяся, т.е. существует предел , то, переходя к пределу в равенстве (4) и предполагая функцию j (x) непрерывной, найдем:

 

или

x =j (x). (5)

 

Таким образом, предел x является корнем уравнения (2) и может быть вычислен по формуле (4) с любой степенью точности.

Доказано, что  достаточными условиями сходимости итерационного процесса является выполнение условия | j (x)<1 для xО [a, ,b].

При этом процесс  сходится к единственному корню x .

 

                                   Рис. 3.                                                             Рис. 4.

 

На рис. 3 приведен пример сходящегося итерационного процесса xn+1=j (xn) при 0<j ’(x)<1 и на рис.4 – расходящегося при j ’(x)<1.

 2.2 Пример поиска корней уравнений с помощью метода итераций

 

Рассматриваемый метод реализует третий подход из представленных в концепции. Предварительно исходное уравнение f(x) = 0 преобразуют к виду:

f(х) = х,

 что является  частным случаем более общей  структуры: g(x) = f(x).

Затем выбирают начальное значение х0 и подставляют его в левую часть уравнения, но f(х0) ¹ х0, поскольку х0 взято произвольно и не является корнем уравнения. Полученное уравнение f(х0) = х1 рассматривают как очередное приближение к корню. Его снова подставляют в левую часть уравнения f(х1) и получают следующее значение х2 (х2 = f(х1)) и т. д., в общем случае хi+1 = f(хi).

Получающаяся таким образом  последовательность: х0, х1, х2, х3 х4,... при определенных условиях может сходиться к корню х. Иллюстрация метода итерации для различных ситуаций приведена на рис. 5. 5

 

Таким условием является |f'(х)| £ 1 на [а, b], причем чем ближе модуль к нулю, тем выше окажется скорость сходимости к решению. В противном случае последовательность расходится от искомого решения ("метод не сходится").

6

 

На рис. 6 приведен один из возможных случаев, когда итерационный процесс не сходится. Видно, что последовательность: х0, х1, х2, х3 х4,... удаляется от корня х. Это всегда будет иметь место в том случае, если тангенс угла наклона f(х) в окрестности корня по модулю больше единицы.

Существуют различные способы преобразования уравнения f(x) = 0 к виду f(х) = х, где одни могут привести к выполнению условия сходимости всегда, другие – в отдельных случаях. Самый простой способ следующий: f(x)+x = 0+x,   f(x)+x = (p(x) => f(х)=х, но он не всегда приводит к успеху.

Существует другой способ, в соответствии с которым f(х) =х – f(x)Ik, причем k следует выбирать таким образом, чтобы |k| > Q/2, где Q = max|f '(x)| на отрезке [а, b] и знак k совпадал бы со знаком f'(х) на [а, b].

Погрешность решения можно оценить из соотношения

|х* – хi| £ q/(1-q) |xi – xi+1|,

где q = max (f'(x)) на отрезке [а, b].

Вследствие этого для окончания вычислений в методе итерации применяют соотношение q/(1–q) |xi – xi+1| £ e, где e – заданная погрешность решения.

Часто используют упрощенное условие окончания поиска |xi – xi+1| £ e, не вычисляя максимальное значение производной, но в этом случае погрешность решения может не соответствовать заданной (т.е. быть больше или меньше).

Пример: Имеем уравнение 2х + lg(2x + 3) = 1. Необходимо уточнить корень с погрешностью  e < 0,001.

 

Решение

Запишем f(х) = 2х + lg(2x +3) – 1. Проведя процедуру отделения корней, получим, что корень находится в промежутке [0;0,5], т. е. а = 0, b =0,5.

Приведем уравнение f(х)=0 к виду, удобному для итераций: f(х) = х. Для этого уравнение 2х + lg(2x +3) –1=0 выразим следующим образом:

f(х) = х= 0,5 – 0,5 lg(2x +3).

Найдем производную функции f'(x):

 

f'(x )= -0,5·lg(е)/(2х+3)·2 = – lg(е)/(2х+3); lg(е) = 0,4343;

 

f'(0 )= -lg(е)/(2·0+3) = – 0,1448; f'(0,5)= -lg(е)/(2·0,5+3)= – 0,1086.