Реферат: Метод Ньютона и его модификации
В связи с развитием новой вычислительной техники инженерная практика наших дней все чаще и чаще встречается с математическими задачами, точное решение которых получить весьма сложно или невозможно.
Дата добавления на сайт: 23 февраля 2025
Автономная Некоммерческая Организация
Высшего Профессионального Образования
СМОЛЬНЫЙ ИНСТИТУТ РОССИЙСКОЙ АКАДЕМИИ ОБРАЗОВАНИЯ
Факультет ИТ
Реферат
по учебной дисциплине: Дополнительные главы высшей математики
на тему: Метод Ньютона и его модификации
Студента: Астаховой К.В.
САНКТ-ПЕТЕРБУРГ 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, (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 такое, что ||ψ(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 с.