Метод Натаниеля Мейкона (N.Macon) поиска исходных приближений для случая почти равных корней
Материал из MachineLearning.
Содержание |
Введение
Метод Ньютона-Рафсона
Пусть имеется некоторая функция и необходимо найти такие значения аргумента
, для которых
Перепишем (1) в виде
и запишем -ое приближения корня (1.1), при этом делая поправку
к очередному значению
где и положим
.
Тогда (2) перепишется в виде
Нетрудно видеть, что (3) эквивалентно простому методу последовательных приближений
где .
Вспомним также, что если , то метод сходится. Имеем
Но так как справедливо соотношение (1.1), то для достаточно близких к решению (1.1), выражение в скобках в числителе дроби становится малым. Поэтому итерационный метод, описываемый формулой (3) сходится, если
- 1. Начальное приближение
выбрано достаточно близко к решению
.
- 2. Производная
не становится слишком большой.
- 3. Производная
не слишком близка к 1.
Это и есть метод Ньютона-Рафсона. Обычно его записывают в виде
,
где
Таким образом, мы вернулись к уравнению в форме (1), и условия сходимости принимают следующий вид
- 1. Начальное приближение
выбрано достаточно близко к корню уравнения
.
- 2. Производная
не становится очень большой.
- 3. Производная
не слишком близка к 0.
Случай почти равных корней
Условие 3 сходимости метода Ньютона-Рафсона означает, что никакие два корня не находятся слишком близко один к другому. Соответствующая ситуация представлена на рисунке 1 (масштаб сильно увеличен). Заметим, что производная близка
к 1 при x, равном обоим значениям корней,
и
. Более того, на основании теоремы Лагранжа, можно утверждать, что
где-то между
и
.
Рассмотрим, что случится, если принять в качестве исходного значения для корня
. Касательная,
проведенная через точку
, пересечет прямую
в точке
, и следующее приближение будет равно
. Касательная, проведенная через точку
, пересекает прямую в точке
, и в качестве следующего приближеня получается снова
. Итерационный процесс, таким образом, осциллирует между
и
до бесконечности, не сходясь ни к одному значению корня. Иначе говоря, не удается отделить эти два корня, потому что они расположены слишком близко.
Поэтому необходимо начальное приближение, достаточно близкое к искомому значению корня. Трудности возникают потому, что вычисление знаменателя в формуле (3) включает в себя вычитание двух почти равных чисел, что приводит к понижению точности.
Изложение метода
Поиск начального приближения
Сначала находится значение x, при котором , то есть решается уравнение
Пусть решением этого уравнения будет некоторое . Эта точка расположена между двумя корнями,
и
. Чтобы получить начальное приближение для решения уравнения, предположим, что
лежит посредине между
и
(рисунок 2). Другими словами, мы предполагаем, что
и
являются корнями уравнения (1.1). Разлагая
в ряд Тейлора в окрестности точки
и принимая во внимание, что
, получаем
Ограничим ряд тремя членами. Подставляя вместо
, имеем
Но по условию
поэтому, решая эти уравнения относительно , получаем
Таким образом, процесс решения сводится к следующему. Если дано уравнение с почти равными корнями, то, определив приблизительное местонахождение этих корней, необходиом решить уравнение
и определить значение . Для решения этого уравнения можно применить, например, метод Ньютона-Рафсона.
Найдя значение
, можно определить значение
. И, наконец, значения
и
используются в качестве начальных приближений для определения соответственно
и
.
Список литературы
- Мак-Кракен Д. Дорн У. Численные методы и программирование на ФОРТРАНе М.: Мир, 1977.