Метод Натаниеля Мейкона (N.Macon) поиска исходных приближений для случая почти равных корней

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

1 Введение
- 1.1 Метод Ньютона-Рафсона
- 1.2 Случай почти равных корней
2 Изложение метода
- 2.1 Поиск начального приближения
3 Список литературы

Введение

Метод Ньютона-Рафсона

Основная статья: Метод касательных (Ньютона-Рафсона)

Пусть имеется некоторая функция $F(x)$ и необходимо найти такие значения аргумента $x$ , для которых

(1)

$F(x)=0$

Перепишем (1) в виде

(1.1)

$x = f(x)$

и запишем $n+1$ -ое приближения корня (1.1), при этом делая поправку $\alpha$ к очередному значению $x_n$

(2)

$x_{n+1} = x_n + \alpha \Delta x_n,$

где $\Delta x_n = f(x_n) - x_n,$ и положим $\alpha = \frac{1}{1-f'(x_n)}$ .

Тогда (2) перепишется в виде

(3)

$x_{n+1} = \frac{f(x_n) - x_n f'(x_n)}{1 - f'(x_n)}$

Нетрудно видеть, что (3) эквивалентно простому методу последовательных приближений

$x_{n+1} = g(x_n),$

где $g(x) = \frac{f(x) - x f'(x)}{1 - f'(x)}$ .

Вспомним также, что если $|g'(x)| < 1$ , то метод сходится. Имеем

$g'(x) = \frac{f''(x)[f(x) - x]}{[1 - f'(x)]^2}.$

Но так как справедливо соотношение (1.1), то для $x,$ достаточно близких к решению (1.1), выражение в скобках в числителе дроби становится малым. Поэтому итерационный метод, описываемый формулой (3) сходится, если

1. Начальное приближение $x_0$ выбрано достаточно близко к решению $x = f(x)$ .

2. Производная $f''(x)$ не становится слишком большой.

3. Производная $f'(x)$ не слишком близка к 1.

Это и есть метод Ньютона-Рафсона. Обычно его записывают в виде

(4)

$x_{n+1} = x_{n} - \frac{F(x_n)}{F'(x_n)}$ ,

где $F(x) = f(x) - x = 0$

Таким образом, мы вернулись к уравнению в форме (1), и условия сходимости принимают следующий вид

1. Начальное приближение $x_0$ выбрано достаточно близко к корню уравнения $F(x) = 0$ .

2. Производная $F''(x)$ не становится очень большой.

3. Производная $F'(x)$ не слишком близка к 0.

Случай почти равных корней

Рисунок 1

Условие 3 сходимости метода Ньютона-Рафсона означает, что никакие два корня не находятся слишком близко один к другому. Соответствующая ситуация представлена на рисунке 1 (масштаб сильно увеличен). Заметим, что производная $f'(x)$ близка к 1 при x, равном обоим значениям корней, $a_1$ и $a_2$ . Более того, на основании теоремы Лагранжа, можно утверждать, что $f'(x) = 1$ где-то между $a_1$ и $a_2$ .

Рассмотрим, что случится, если принять $x_0$ в качестве исходного значения для корня $a_1$ . Касательная, проведенная через точку $C$ , пересечет прямую $y=x$ в точке $A$ , и следующее приближение будет равно $x_1$ . Касательная, проведенная через точку $B$ , пересекает прямую в точке $D$ , и в качестве следующего приближеня получается снова $x_0$ . Итерационный процесс, таким образом, осциллирует между $x_0$ и $x_1$ до бесконечности, не сходясь ни к одному значению корня. Иначе говоря, не удается отделить эти два корня, потому что они расположены слишком близко.

Поэтому необходимо начальное приближение, достаточно близкое к искомому значению корня. Трудности возникают потому, что вычисление знаменателя в формуле (3) включает в себя вычитание двух почти равных чисел, что приводит к понижению точности.

Изложение метода

Поиск начального приближения

Рисунок 2

Сначала находится значение x, при котором $f'(x)=1$ , то есть решается уравнение

$x=x+f'(x)-1$

Пусть решением этого уравнения будет некоторое $x = x_0$ . Эта точка расположена между двумя корнями, $a_1$ и $a_2$ . Чтобы получить начальное приближение для решения уравнения, предположим, что $x_0$ лежит посредине между $a_1$ и $a_2$ (рисунок 2). Другими словами, мы предполагаем, что $x_0 + d$ и $x_0 - d$ являются корнями уравнения (1.1). Разлагая $f(x)$ в ряд Тейлора в окрестности точки $x_0$ и принимая во внимание, что $f'(x)=1$ , получаем

$f(x) = f(x_0) + (x - x_0) + \frac{1}{2} f''(x_0) (x - x_0)^2 + \ldots$

Ограничим ряд тремя членами. Подставляя $x + d$ вместо $x$ , имеем

$f(x_0+d) = f(x_0) + d + \frac{1}{2} f''(x_0)(d^2)$

Но по условию

$f(x_0+d) = x_0+d,$

поэтому, решая эти уравнения относительно $d$ , получаем

$d=\sqrt{\frac{2(x_0 - f(x_0))}{f''(x_0)}}$

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

$x = x + f'(x) - 1$

и определить значение $x_0$ . Для решения этого уравнения можно применить, например, метод Ньютона-Рафсона. Найдя значение $x_0$ , можно определить значение $d$ . И, наконец, значения $x_0-d$ и $x_0+d$ используются в качестве начальных приближений для определения соответственно $a_1$ и $a_2$ .