Метод Натаниеля Мейкона (N.Macon) поиска исходных приближений для случая почти равных корней
Материал из MachineLearning.
(Новая: == Введение == == Изложение метода == == Анализ метода == == Числовой пример == == Заключение == == Литература ==) |
|||
Строка 1: | Строка 1: | ||
== Введение == | == Введение == | ||
+ | |||
+ | === Метод Ньютона-Рафсона === | ||
+ | {{main|Метод касательных (Ньютона-Рафсона)}} | ||
+ | |||
+ | Пусть имеется некоторая функция <tex>F(x)</tex> и необходимо найти такие значения аргумента <tex>x</tex>, для которых | ||
+ | {{eqno|1}} | ||
+ | :<tex>F(x)=0</tex> | ||
+ | |||
+ | Перепишем {{eqref|1}} в виде | ||
+ | {{eqno|1.1}} | ||
+ | :<tex>x = f(x)</tex> | ||
+ | |||
+ | и запишем <tex>n+1</tex>-ое приближения корня {{eqref|1.1}}, при этом делая поправку <tex>\alpha</tex> к очередному значению <tex>x_n</tex> | ||
+ | {{eqno|2}} | ||
+ | :<tex>x_{n+1} = x_n + \alpha \Delta x_n,</tex> | ||
+ | где <tex>\Delta x_n = f(x_n) - x_n,</tex> и положим <tex>\alpha = \frac{1}{1-f'(x_n)}</tex>. | ||
+ | |||
+ | Тогда {{eqref|2}} перепишется в виде | ||
+ | {{eqno|3}} | ||
+ | :<tex>x_{n+1} = \frac{f(x_n) - x_n f'(x_n)}{1 - f'(x_n)}</tex> | ||
+ | |||
+ | Нетрудно видеть, что {{eqref|3}} эквивалентно простому [[Метод последовательных приближений|методу последовательных приближений]] | ||
+ | :<tex>x_{n+1} = g(x_n),</tex> | ||
+ | где <tex>g(x) = \frac{f(x) - x f'(x)}{1 - f'(x)}</tex>. | ||
+ | |||
+ | Вспомним также, что если <tex>|g'(x)| < 1</tex>, то метод сходится. Имеем | ||
+ | :<tex>g'(x) = \frac{f''(x)[f(x) - x]}{[1 - f'(x)]^2}.</tex> | ||
+ | |||
+ | Но так как справедливо соотношение {{eqref|1.1}}, то для <tex>x,</tex> достаточно близких к решению {{eqref|1.1}}, выражение в скобках в числителе дроби становится малым. Поэтому итерационный метод, описываемый формулой {{eqref|3}} сходится, если | ||
+ | :1. Начальное приближение <tex>x_0</tex> выбрано достаточно близко к решению <tex>x = f(x)</tex>. | ||
+ | :2. Производная <tex>f''(x)</tex> не становится слишком большой. | ||
+ | :3. Производная <tex>f'(x)</tex> не слишком близка к 1. | ||
+ | |||
+ | Это и есть метод Ньютона-Рафсона. Обычно его записывают в виде | ||
+ | {{eqno|4}} | ||
+ | :<tex>x_{n+1} = x_{n} - \frac{F(x_n)}{F'(x_n)}</tex>, | ||
+ | |||
+ | где <tex>F(x) = f(x) - x = 0</tex> | ||
+ | |||
+ | Таким образом, мы вернулись к уравнению в форме {{eqref|1}}, и условия сходимости принимают следующий вид | ||
+ | :1. Начальное приближение <tex>x_0</tex> выбрано достаточно близко к корню уравнения <tex>F(x) = 0</tex>. | ||
+ | :2. Производная <tex>F''(x)</tex> не становится очень большой. | ||
+ | :3. Производная <tex>F'(x)</tex> не слишком близка к 0. | ||
+ | |||
+ | === Случай почти равных корней === | ||
+ | [[Изображение:macon.png|thumb|200px|Рисунок 1]] | ||
+ | Условие 3 сходимости метода Ньютона-Рафсона означает, что никакие два корня не находятся слишком близко один к другому. Соответствующая ситуация представлена на рисунке 1 (масштаб сильно увеличен). Заметим, что производная <tex>f'(x)</tex> близка | ||
+ | к 1 при x, равном обоим значениям корней, <tex>a_1</tex> и <tex>a_2</tex>. Более того, на основании теоремы Лагранжа, можно утверждать, что <tex>f'(x) = 1</tex> где-то между <tex>a_1</tex> и <tex>a_2</tex>. | ||
+ | |||
+ | Рассмотрим, что случится, если принять <tex>x_0</tex> в качестве исходного значения для корня <tex>a_1</tex>. Касательная, | ||
+ | проведенная через точку <tex>C</tex>, пересечет прямую <tex>y=x</tex> в точке <tex>A</tex>, и следующее приближение будет равно | ||
+ | <tex>x_1</tex>. Касательная, проведенная через точку <tex>B</tex>, пересекает прямую в точке <tex>D</tex>, и в качестве следующего приближеня получается снова <tex>x_0</tex>. Итерационный процесс, таким образом, осциллирует между <tex>x_0</tex> и <tex>x_1</tex> | ||
+ | до бесконечности, не сходясь ни к одному значению корня. Иначе говоря, не удается <i>отделить</i> эти два корня, потому что они расположены слишком близко. | ||
+ | |||
+ | Поэтому необходимо начальное приближение, достаточно близкое к искомому значению корня. Трудности возникают потому, что | ||
+ | вычисление знаменателя в формуле {{eqref|3}} включает в себя вычитание двух почти равных чисел, что приводит к понижению точности. | ||
== Изложение метода == | == Изложение метода == | ||
- | == | + | |
- | == | + | === Поиск начального приближения === |
- | == | + | |
- | == | + | [[Изображение:macon2.PNG|thumb|200px|Рисунок 2]] |
+ | Сначала находится значение x, при котором <tex>f'(x)=1</tex>, то есть решается уравнение | ||
+ | :<tex>x=x+f'(x)-1</tex> | ||
+ | Пусть решением этого уравнения будет некоторое <tex>x = x_0</tex>. Эта точка расположена между двумя корнями, <tex>a_1</tex> и <tex>a_2</tex>. Чтобы получить начальное приближение для решения уравнения, предположим, что <tex>x_0</tex> лежит посредине между | ||
+ | <tex>a_1</tex> и <tex>a_2</tex> (рисунок 2). Другими словами, мы предполагаем, что <tex>x_0 + d</tex> и <tex>x_0 - d</tex> являются корнями уравнения {{eqref|1.1}}. Разлагая <tex>f(x)</tex> в ряд Тейлора в окрестности точки <tex>x_0</tex> и принимая во внимание, что <tex>f'(x)=1</tex>, получаем | ||
+ | :<tex>f(x) = f(x_0) + (x - x_0) + \frac{1}{2} f''(x_0) (x - x_0)^2 + \ldots</tex> | ||
+ | |||
+ | Ограничим ряд тремя членами. Подставляя <tex>x + d</tex> вместо <tex>x</tex>, имеем | ||
+ | :<tex>f(x_0+d) = f(x_0) + d + \frac{1}{2} f''(x_0)(d^2)</tex> | ||
+ | |||
+ | Но по условию | ||
+ | :<tex>f(x_0+d) = x_0+d,</tex> | ||
+ | |||
+ | поэтому, решая эти уравнения относительно <tex>d</tex>, получаем | ||
+ | :<tex>d=\sqrt{\frac{2(x_0 - f(x_0))}{f''(x_0)}}</tex> | ||
+ | |||
+ | Таким образом, процесс решения сводится к следующему. Если дано уравнение с почти равными корнями, то, определив приблизительное | ||
+ | местонахождение этих корней, необходиом решить уравнение | ||
+ | :<tex>x = x + f'(x) - 1</tex> | ||
+ | |||
+ | и определить значение <tex>x_0</tex>. Для решения этого уравнения можно применить, например, метод Ньютона-Рафсона. | ||
+ | Найдя значение <tex>x_0</tex>, можно определить значение <tex>d</tex>. И, наконец, значения <tex>x_0-d</tex> и <tex>x_0+d</tex> | ||
+ | используются в качестве начальных приближений для определения соответственно <tex>a_1</tex> и <tex>a_2</tex>. | ||
+ | |||
+ | == Список литературы == | ||
+ | * ''Мак-Кракен Д.'' ''Дорн У.'' Численные методы и программирование на ФОРТРАНе М.: Мир, 1977. | ||
+ | {{Stub|}} |
Текущая версия
Содержание |
Введение
Метод Ньютона-Рафсона
Пусть имеется некоторая функция и необходимо найти такие значения аргумента , для которых
Перепишем (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.