Метод Ньютона и его модификации

Автономная Некоммерческая Организация

Высшего Профессионального Образования

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

Факультет ИТ

Реферат

по учебной дисциплине: Дополнительные главы высшей математики

на тему: Метод Ньютона и его модификации

Студента: Астаховой К.В.

САНКТ-ПЕТЕРБУРГ 2014г.

Оглавление

Введение

. Метод Ньютона

. Модификации метода Ньютона

. Метод секущих для нелинейного уравнения

. Метод хорд для нелинейного уравнения

. Упрощенный метод Ньютона

. Модификация метода Ньютона для системы двух уравнений

. Метод локального положения

. Метод секущих

. Метод Стефенсена

. Уточнение метода Ньютона для случая кратного корня

Заключение

Список использованных источников

Введение

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

В данном реферате рассматривается знаменитый метод Ньютона и его модификации: методы ложного положения, метод секущих, метод Стеффенсена, метод секущих или метод ложного положения.

1. Метод Ньютона

Одним из наиболее простых и быстрых методов решения нелинейных уравнений вида

f(x) = 0 (1)

является метод Ньютона или метод касательных, основанный на формуле Тейлора или формуле Лагранжа. Пусть функция f(x) дважды дифференцируема на отрезке [a, b], содержащем корень x уравнения (1). Пусть xk Î [a, b] известный член последовательности приближений к Î, полученный данным методом, начиная с x0. По формуле Тейлора для любой точки x Î [a, b] имеем

(2)

где точка q k лежит между точками x и xk. Для корня x = x Î [a, b] уравнения (1) по этой формуле получаем:

. (3)

Так как xk близко к x, то разность x - xk по модулю достаточно мала, но тогда величина (x - xk)2 будет еще меньше и ее можно отбросить. Далее полагая q k = xk получим формулу,

, (4)

по которой будем находить следующее приближение xk+1 к корню x

. (5)

Рисунок 1

Заметим, что xk+1 абсцисса точки пересечения касательной

проведенной к графику функции y = f(x) в точке (xk, f(xk)).

Геометрический смысл метода Ньютона: приближение к корню x уравнения (1) совершается по абсциссам точек пересечения касательных к графику функции y = f(x), проводимых в точках соответствующим предыдущим приближениям.

Скорость приближений последовательности (xk) к x следует из следующей теоремы.

Теорема 1. Пусть функция f(x) удовлетворяет условиям

. (6)

Тогда если члены последовательности (xk), определяемой методом Ньютона принадлежат отрезку [a, b] и эта последовательность сходится на [a, b] к корню x уравнения (1), то для любого k Î N справедливы неравенства:

. (7)

Доказательство. Подставляя в правую часть формулы (3) вместо нуля формулу (4) получим равенство:

,

,

.

Переходя к модулям, получаем первую формулу (7).

По формуле Тейлора имеем

.

Тогда из формулы (4) получим . Переходя к модулям, имеем

. (8)

По формуле Лагранжа , где q лежит между точками x и xk. Так как f(x) = 0, то имеем. Отсюда получаем вторую формулу (7).

Начальную точку x0 в методе Ньютона необходимо выбирать исходя из следующей теоремы.

Теорема 2. Пусть на отрезке [a, b] функция f(x) имеет первую и вторую производные постоянного знака и пусть f(a) f(b) <0. Тогда если точка x0 выбрана на [a, b] так, что

f(x0) f (x0) > 0, (9)

то начиная с нее последовательность (xk), определяемая методом Ньютона, монотонно сходится к корню x Î [a, b] уравнения (1).

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

2. Модификации метода Ньютона

Теоремы 1 и 2 и формула (5) предполагают, что производная функции f(x) внутри отрезка [a, b] не обращается в нуль. Если число x - кратный корень уравнения (1) то f ' (x) =0. Но итерационный процесс Ньютона сходится, когда x кратный корень уравнения (4), но сходимость линейная. Если известен m - показатель кратности корня x, то рекомендуется вести вычисление по формуле:

. (10)

Такую модификацию называют методом Ньютона-Шредера.

Для уменьшения затрат, связанных с вычислением производной вычисление можно вести по формуле:

. (11)

Такую модификацию называют упрощенным методом Ньютона. Этот метод утрачивает высокую сходимость.

Вместо производной в формуле (5) берут ее приближенное значение по формуле

.

Это приводит к так называемому разностному методу Ньютона:

Рисунок 2

. (12)

Параметр hk связывается с номером итерации.

Если взять параметр hk = xk -1 - xk , то получим формулу

, (12)

где числа x0 и x1 должны задаваться. Такую модификацию называют двух шаговым методом Ньютона или методом секущих.

Метод секущих обеспечивает за два шага квадратичную сходимость, но худшую сходимость, чем метод Ньютона. Число x1 выбирается близким к числу x0. Окончание счета контролируют малостью модулей невязок |f(xk)|, или поправок | xk -1 - xk |.

Алгоритм нахождения корня методом Ньютона.

Ввод: Функция f(х), производная f'(х), точность вычисления e корня, допуск d - малое число, связанное с реальной точностью вычисления f(х), f'(х). Промежуток [a, b] существования корня.

Вывод: корень с уравнения.

c:=a; если f(c)*f ''(c) < 0, то c:=b;

. d:= c -f(c)/f '(c));

если |c - d| <e, то конец

в противном случае вычислить f(c);

если |f(c)| <d, то конец

идти к шагу 1.

Пример. Методом Ньютона найти корень уравнение x2 - sin x - 1 = 0 (точность 0,01) в интервале (1, p). Имеем f(х) = x2 - sin x - 1, a = 1, b = p » 3,1416, e = 0,01, d = 0,001. Находим f ' (х) = 2x - cos x, f '' (х) = 2 - sin x, c = b.

Таблица 1

Шаг12345c3,14161,92381,50341,41411,4096f(c)8,87001,76260,26260,0121-f ' (c)7,28324,19322,93962,6722-

Корень уравнения: x = 1,41 ±0,01 .

3. Метод секущих для нелинейного уравнения

В формуле

x(k+1) = x(k) - f(x(k))/f '(x(k)) , k = 0, 1, 2, ...

метода Ньютона требуется вычислять производную функции f(x), что не всегда удобно, а иногда практически невозможно. В методе секущих производная f '(x(k)) заменяется на дробь (так называемую разделенную разность) (f(x(k)) - f(x(k-1))) / (x(k) - x(k-1)).

В результате формула метода принимает вид:

x(k+1) = x(k) - f(x(k))(x(k) - x(k-1)) / (f(x(k)) - f(x(k-1))), k = 1, 2, (13)

где x(0),x(1) - некоторые начальные приближения к корню.

Геометрический смысл метода секущих заключается в замене на итерации с номером k графика функции y=f(х) на секущую, проходящую через точки (x(k),f(x(k))) и (x(k-1),f(x(k-1))) и, следовательно, задаваемую уравнением

y = (f(x(k)) - f(x(k-1)))(x - x(k))/ (x(k) - x(k-1)) + f(x(k))

Далее находим точку ее пересечения с осью OX, что соответствует решению линейного уравнения:

(f(x(k)) - f(x(k-1)))(x - x(k))/ (x(k) - x(k-1)) + f(x(k)) = 0

Отсюда получаем:

x = x(k) - f(x(k))(x(k) - x(k-1)) / (f(x(k)) - f(x(k-1))) ?x(k+1)

) В общем случае сходимость по методу Ньютона происходит быстрее, чем по методу секущих, и кроме того не требуется нахождения сразу двух начальных приближений к искомому корню. Но при использовании метода секущих не требуется вычисления производной.

) Условие окончания итераций в методе секущих остается тем же, что и в классическом методе Ньютона: | x(k+1) - x(k) | ? ?.

4. Метод хорд для нелинейного уравнения

В методе хорд производная f '(x(k)) метода Ньютона заменяется на еще более простую (по сравнению с методом секущих) разделенную разность (f(x(k)) - f(x(0))) / (x(k) - x(0))

В результате формула метода хорд принимает вид:

x(k+1) = x(k) - f(x(k))(x(k) - x(0)) / (f(x(k)) - f(x(0))), k = 1, 2, ...(14)

причем x(0), x(1) - некоторые начальные приближения к корню. Геометрически рассматриваемый метод означает замену на каждой итерации графика функции y=f(х) на хорду, то есть через точки (x(0),f(x(0))) и (x(k),f(x(k))) проводим хорду

y = (f(x(k)) - f(x(0)))(x - x(k))/ (x(k) - x(0)) + f(x(k))

и находим точку ее пересечения с осью OX, что соответствует решению линейного уравнения:

(f(x(k)) - f(x(0)))(x - x(k))/ (x(k) - x(0)) + f(x(k)) = 0

Выражая отсюда x, получаем:

x = x(k) - f(x(k))(x(k) - x(0)) / (f(x(k)) - f(x(0))) ? x(k+1)

Замечание Критерий окончания итераций в методе хорд имеет вид:

| x(k+1) - x(k) | ? ?

. Упрощенный метод Ньютона

Этот метод имеет вид

x(k+1) = x(k) - f(x(k))/f '(x(0)) , k = 0, 1, 2, ... (15 )

где x(0) - некоторое начальное приближение к корню.

Критерий окончания данного итерационного процесса имеет вид:

| x(k+1) - x(k) | ? ?

К достоинствам этого метода следует отнести простоту его реализации и возможность обобщения на системы уравнений , а к недостаткам - более медленную по сравнению с методом Ньютона сходимость.

6. Модификация метода Ньютона для системы двух уравнений

Для решения системы из двух уравнений

используется следующая модификация метода Ньютона:

(16)

где (x1(0), x2(0)) - некоторое начальное приближение к искомому корню.

Замечание 2.7 1) В данном методе в отличие от классического метода Ньютона обратную матрицу требуется подсчитывать только один раз.

) Условие окончания итерационного процесса имеет вид: || x(k+1) - x(k) || ? ?

. Метод локального положения

Пусть f дважды непрерывно дифференцируема, а x* - невырожденная стационарная точка. Тогда найдется окрестность Vx* точки x* такая, что приближения xn+1 = xn - [f ??(xn)]-1f ?(xn), начатые из произвольной начальной точки x0 ? Vx*, сверхлинейно сходятся к x*.

Доказательство. Очевидно, F = f ? х C1 и поэтому

lim x?x*||F ?(x) - F ?(x*)|| = 0.(17)

Поскольку F ?(x*) невырожден, в силу (17) при x достаточно близких к x* невырожден и оператор F ?(x) и более того,

x?x* ||[F ?(x)]-1 - [F ?(x*)]-1|| = 0.

Поэтому, в частности, при x достаточно близких к x*

||[F ?(x)]-1|| ? C.(18)

Далее, в силу того, что F дифференцируема, а x* - стационарная точка,

F(x) = F(x*) + F ?(x*)(x - x*) + o(x - x*) = F ?(x*)(x - x*) + o(x - x*),

Но тогда в силу (18)

x - x* - [F ?(x)]-1F(x) = [F ?(x)]-1F ?(x)(x - x*) - [F ?(x)]-1F(x) = = [F ?(x)]-1[F ?(x)(x - x*) - F(x)] = o(x - x*).

Или

- [F ?(x)]-1F(x) - x* = o(x - x*).

В частности, при x = xn

xn+1 - x* = xn - [F ?(xn)]-1F(xn) - x* ?(xn - x*) = o(xn - x*).(19)

Возьмем теперь в качестве Vx*, например, окрестность {x ? Rm: ||?(x - x*)|| ? ||x - x*||/2}. В силу (19), очевидно, если x0 ? Vx*, то

||xn+1 - x*|| ?1/2

||xn - x*|| ? ... ?1/ (2n+1)

||x0 - x*||

и, следовательно, xn ? x* при n? ?. Более того, для произвольного q ? (0, 1) найдется ? > 0 такое, что ||?(x - x*)|| ? q||x - x*|| при ||x - x*|| ? ?. Но тогда, если ||xn - x*|| ??, то||xn+1 - x*|| ? q||xn - x*||. Из последнего утверждения очевидным образом вытекает нужное соотношение ||xn - x*|| ? Cqn.

. Метод секущих

Можно связать задание последовательности с какой-либо сходящейся к нулю векторной последовательностью, например, с последовательность невязок или поправок . Так, полагая , где j=1,…n, a k=1,2,…, приходим к простейшему методу секущих - обобщению скалярного метода секущих:

, (20)

где

,

=1,2,3,… .

Этот метод является двухшаговым и требует задания двух начальных точек и . При п = 1 сходимость метода (20) имеет порядок . Можно рассчитывать на такую же скорость и в многомерном случае.

К методу секущих так же, как и к методу Ньютона, можно применить пошаговую аппроксимацию обратных матриц на основе метода Шульца. Расчетные формулы этой модификации легко выписать, заменив в совокупности формул ААМН (аппроксимаиионный аналог метода Ньютона)

матрицу на матрицу из (20).

9. Метод Стефенсена

Вычисления по методу Стеффенсена производят по формулам

,

,

где .

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

По-видимому, для решения нелинейных систем вида метод Стеффенсена чаще кажется лучшим выбором, чем метод секущих или метод ложного положения.

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

10. Уточнение метода Ньютона для случая кратного корня

Метод Ньютона для случая кратного корня обладает лишь линейной скоростью сходимости. Чтобы сохранить квадратичную сходимость его модифицируют следующим образом:

,

где m - кратность корня.

Как правило, значение m v неизвестно. Используя метод Ньютона, можно узнать кратность корня. Для этого будем задавать значения m= 1,2,3 и вычислять значение корня с заданной точностью, одновременно подсчитывая количество итераций для каждого значения m. При некотором значении m число итераций будет минимальным. Это значение m и есть кратность корня.

ньютон хорда корень уравнение

Заключение

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

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

Список использованных источников

1.Интернет источник Radyx

2.Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении: Учеб. пособие. - М.: Дело, 2000. - 440 с.

.Амосов А.А., Дубинский Ю.А., Копчёнова Н.В. Вычислительные методы для инженеров: Учеб. пособие. - М.: Высш. Школа, 1994. - 544 с.

.Интернет источник - Copyright © 1993-2015. Компания Softline.

.Демидович Б.П., Марон И.А., Шувалова Э.З. Численные методы анализа. 2-е изд., испр. и доп. - М.: Гос. изд-во физ.-мат. Лит., 1963. - 400 с.