То же, что аппроксимация. Термин П. иногда употребляется в смысле приближающего объекта (напр., начальное П.) … Математическая энциклопедия

Метод Ньютона - Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном… … Википедия

Метод одной касательной

Метод Гаусса - Ньютона - Метод Ньютона (также известный как метод касательных) это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643 1727), под именем… … Википедия

Метод Ньютона-Рафсона - Метод Ньютона (также известный как метод касательных) это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643 1727), под именем… … Википедия

Метод Ньютона - Рафсона - Метод Ньютона (также известный как метод касательных) это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643 1727), под именем… … Википедия

Метод касательной - Метод Ньютона (также известный как метод касательных) это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643 1727), под именем… … Википедия

Метод касательной (Метод Ньютона) - Метод Ньютона (также известный как метод касательных) это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643 1727), под именем… … Википедия

Метод касательных - Метод Ньютона (также известный как метод касательных) это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643 1727), под именем… … Википедия

Численное решение уравнений - и их систем состоит в приближённом определении корня или корней уравнения или системы уравнений и применяется в случаях, когда точное значение вычислить невозможно или очень трудоёмко. Содержание 1 Постановка задачи 2 Численные ме … Википедия

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

Метод Ньютона (касательных) для поиска корней

Это итерационный метод, изобретённый Исааком Ньютоном (Isaak Newton) около 1664 г. Впрочем, иногда этот метод называют методом Ньютона-Рафсона (Raphson), поскольку Рафсон изобрёл тот же самый алгоритм на несколько лет позже Ньютона, однако его статья была опубликована намного раньше.

Задача заключается в следующем. Дано уравнение:

Требуется решить это уравнение, точнее, найти один из его корней (предполагается, что корень существует). Предполагается, что непрерывна и дифференцируема на отрезке .

Алгоритм

Входным параметром алгоритма, кроме функции , является также начальное приближение — некоторое , от которого алгоритм начинает идти.

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

Нетрудно получить следующую формулу:

Интуитивно ясно, что если функция достаточно "хорошая" (гладкая), а находится достаточно близко от корня, то будет находиться ещё ближе к искомому корню.

Скорость сходимости является квадратичной , что, условно говоря, означает, что число точных разрядов в приближенном значении удваивается с каждой итерацией.

Применение для вычисления квадратного корня

Рассмотрим метод Ньютона на примере вычисления квадратного корня.

Если подставить , то после упрощения выражения получаем:

Первый типичный вариант задачи — когда дано дробное число , и нужно подсчитать его корень с некоторой точностью :

double n; cin >> n; const double EPS = 1E-15 ; double x = 1 ; for (;; ) { double nx = (x + n / x) / 2 ; if (abs (x - nx) < EPS) break ; x = nx; } printf ("%.15lf" , x) ;

Другой распространённый вариант задачи — когда требуется посчитать целочисленный корень (для данного найти наибольшее такое, что ). Здесь приходится немного изменять условие останова алгоритма, поскольку может случиться, что начнёт "скакать" возле ответа. Поэтому мы добавляем условие, что если значение на предыдущем шаге уменьшилось, а на текущем шаге пытается увеличиться, то алгоритм надо остановить.

int n; cin >> n; int x = 1 ; bool decreased = false ; for (;; ) { int nx = (x + n / x) >> 1 ; if (x == nx || nx > x && decreased) break ; decreased = nx < x; x = nx; } cout << x;

Наконец, приведём ещё третий вариант — для случая длинной арифметики. Поскольку число может быть достаточно большим, то имеет смысл обратить внимание на начальное приближение. Очевидно, что чем оно ближе к корню, тем быстрее будет достигнут результат. Достаточно простым и эффективным будет брать в качестве начального приближения число , где — количество битов в числе . Вот код на языке Java, демонстрирующий этот вариант:

BigInteger n; // входные данные BigInteger a = BigInteger.ONE .shiftLeft (n.bitLength () / 2 ) ; boolean p_dec = false ; for (;; ) { BigInteger b = n.divide (a) .add (a) .shiftRight (1 ) ; if (a.compareTo (b) == 0 || a.compareTo (b) < 0 && p_dec) break ; p_dec = a.compareTo (b) > 0 ; a = b; }

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

Пусть корень уравнения f(x)=0 отделен на отрезке , причем первая и вторая производные f’(x) и f""(x) непрерывны и знакопостоянны при хÎ .

Пусть на некотором шаге уточнения корня получено (выбрано) очередное приближение к корню х n . Тогда предположим, что следующее приближение, полученное с помощью поправки h n , приводит к точному значению корня

x = х n + h n . (1.2.3-6)

Считаяh n малой величиной, представим f(х n + h n) в виде ряда Тейлора, ограничиваясь линейными слагаемыми

f(х n + h n) »f(х n) + h n f’(х n). (1.2.3-7)

Учитывая, что f(x) = f(х n + h n) = 0, получим f(х n) + h n f ’(х n) » 0.

Отсюда h n » - f(х n)/ f’(х n). Подставим значение h n в (1.2.3-6) и вместо точного значения корня x получим очередное приближение

Формула (1.2.3-8) позволяет получить последовательность приближенийх 1 ,х 2 , х 3 …, которая при определенных условиях сходится к точному значению корняx, то есть

Геометрическая интерпретация метода Ньютона состоит в следующем
(рис.1.2.3-6). Примем за начальное приближение x 0 правый конец отрезка b и в соответствующей точке В 0 на графике функции y = f(x) построим касательную. Точка пересечения касательной с осью абсцисс принимается за новое более точное приближение х 1 . Многократное повторение этой процедуры позволяет получить последовательность приближений х 0 , х 1 , х 2 , . . ., которая стремится к точному значению корня x.

Расчетная формула метода Ньютона (1.2.3-8) может быть получена из геометрического построения. Так в прямоугольном треугольнике х 0 В 0 х 1 катет
х 0 х 1 = х 0 В 0 /tga. Учитывая, что точка В 0 находится на графике функции f(x), а гипотенуза образована касательной к графику f(x) в точке В 0 , получим

(1.2.3-9)

(1.2.3-10)

Эта формула совпадает с (1.2.3-8) для n-го приближения.

Из рис.1.2.3-6 видно, что выбор в качестве начального приближения точки а может привести к тому, что следующее приближение х 1 окажется вне отрезка , на котором отделен корень x . В этом случае сходимость процесса не гарантирована. В общем случае выбор начального приближения производится в соответствии со следующим правилом: за начальное приближение следует принять такую точку х 0 Î,в которой f(х 0)×f’’(х 0)>0, то есть знаки функции и ее второй производной совпадают.

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

Если корень уравнения отделен на отрезке , причем f’(х 0)и f’’(х) отличны от нуля и сохраняют свои знаки при хÎ , то, если выбрать в качестве начального приближения такую точку х 0 Î, что f(х 0).f¢¢(х 0)>0, то корень уравнения f(x)=0может быть вычислен с любой степенью точности.

Оценка погрешности метода Ньютона определяется следующим выражением:

(1.2.3-11)

где -- наименьшее значение при

Наибольшее значение при

Процесс вычислений прекращается, если ,

где -- заданная точность.

Кроме того, условием достижения заданной точности при уточнении корня методом Ньютона могут служить следующие выражения:

Схема алгоритма метода Ньютона приведена на рис. 1.2.3-7.

Левая часть исходного уравнения f(x) и ее производная f’(x)в алгоритме оформлены в виде отдельных программных модулей.

Рис. 1.2.3-7. Схема алгоритма метода Ньютона

Пример 1.2.3-3.Уточнить методом Ньютона корни уравнения x-ln(x+2) = 0при условии, что корни этого уравнения отделены на отрезках x 1 Î[-1.9;-1.1] и x 2 Î [-0.9;2].

Первая производная f’(x) = 1 – 1/(x+2) сохраняет свой знак на каждом из отрезков:

f’(x)<0 при хÎ [-1.9; -1.1],

f’(x)>0 при хÎ [-0.9; 2].

Вторая производная f"(x) = 1/(x+2) 2 > 0 при любых х.

Таким образом, условия сходимости выполняются. Поскольку f""(x)>0на всей области допустимых значений, то для уточнения корня за начальное приближение x 1 выберем х 0 =-1,9(так какf(-1,9)×f”(-1.9)>0). Получим последовательность приближений:

Продолжая вычисления, получим следующую последовательность первых четырех приближений: -1.9; –1.8552, -1.8421; -1.8414. Значение функции f(x) в точке x=-1.8414 равно f(-1.8414)=-0.00003.

Для уточнения корня x 2 Î[-0.9;2] выберем в качестве начального приближениях 0 =2 (f(2)×f”(2)>0). Исходя из х 0 = 2, получим последовательность приближений: 2.0;1.1817; 1.1462; 1.1461. Значение функции f(x) в точке x=1.1461 равно f(1.1461)= -0.00006.

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

Метод хорд

Геометрическая интерпретация метода хорд состоит в следующем
(рис.1.2.3-8).

Проведем отрезок прямой через точки A и B. Очередное приближение x 1 является абсциссой точки пересечения хорды с осью 0х. Построим уравнение отрезка прямой:

Положим y=0и найдем значение х=х 1 (очередное приближение):

Повторим процесс вычислений для получения очередного приближения к корню - х 2 :

В нашем случае (рис.1.2.11) и расчетная формула метода хорд будет иметь вид

Эта формула справедлива, когда за неподвижную точку принимается точка b, а в качестве начального приближения выступает точка a.

Рассмотрим другой случай (рис. 1.2.3-9), когда .

Уравнение прямой для этого случая имеет вид

Очередное приближение х 1 при y = 0

Тогда рекуррентная формула метода хорд для этого случая имеет вид

Следует отметить, что за неподвижную точку в методе хорд выбирают тот конец отрезка , для которого выполняется условие f (x)∙f¢¢ (x)>0.

Таким образом, если за неподвижную точку приняли точку а, то в качестве начального приближения выступает х 0 = b, и наоборот.

Достаточные условия, которые обеспечивают вычисление корня уравнения f(x)=0 по формуле хорд, будут теми же, что и для метода касательных (метод Ньютона), только вместо начального приближения выбирается неподвижная точка. Метод хорд является модификацией метода Ньютона. Разница состоит в том, что в качестве очередного приближения в методе Ньютона выступает точка пересечения касательной с осью 0Х,а в методе хорд – точка пересечения хорды с осью 0Х – приближения сходятся к корню с разных сторон.

Оценка погрешности метода хорд определяется выражением

(1.2.3-15)

Условие окончания процесса итераций по методу хорд

(1.2.3-16)

В случае, если M 1 <2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£e.

Пример 1.2.3-4. Уточнить корень уравнения e x – 3x = 0, отделенный на отрезке с точностью 10 -4 .

Проверим условие сходимости:

Следовательно, за неподвижную точку следует выбрать а=0, а в качестве начального приближения принять х 0 =1, поскольку f(0)=1>0 и f(0)*f"(0)>0.

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

9.6.1. Поиск на сетке. Особенно эффективен этот метод при небольшом числе собственно нелинейных параметров. Часто функции устроены так, что при фиксации значений одних параметров (которые и называем собственно нелинейными) остальная часть параметров становится линейной.

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

В качестве примера рассмотрим функцию

Здесь собственно нелинейным параметром будет . Допустим, известно, что . Пусть h - шаг для параметра . Вычислим линейных регрессий

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

9.6.2. Преобразование модели.

Иногда некоторым преобразованием модель можно свести к линейной или же уменьшить число собственно нелинейных параметров (см. п. 6.2.3). Покажем, как этого можно добиться, на примере логистической кривой

Производя над соответствующими уравнениями регрессии обратное преобразование, получим

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

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

Пользуясь разложением в ряд Тейлора и обозначая преобразование через получим, пренебрегая слагаемыми порядка

Отсюда следует, что

Последнее равенство можно взять за основу для анализа задачи с преобразованной моделью.

9.6.3. Разбиение выборки на подвыборки.

Для нахождения начального приближения можно разбить всю выборку на подвыборок (с приблизительно равными объемамй), где - число неизвестных параметров. Для каждой подвыборки найдем средние по у и по X, которые обозначим соответственно т. Решим систему нелинейных уравнений относительно

Решение этой системы и будет являться начальным приближением параметров. Очевидно, для того чтобы данный метод «работал», необходимо, чтобы эта система нелинейных уравнений решалась довольно легко, например аналитически.

9.6.4. Разложение в ряд Тейлора по независимым переменным.

Основой итеративной минимизации суммы квадратов является разложение функции регрессии в ряд Тейлора до линейных членов по параметрам. Для нахождения грубого начального приближения иногда бывает полезна процедура аппроксимации регрессии путем разложения ее в ряд Тейлора по независимым переменным . Будем для простоты считать одномерным. Пусть - среднее значение, тогда приближенно

Обозначим , таким образом приходим к линейной модели

Пусть - мнк-оценки параметров этой линейной регрессии. В качестве начальных приближений примем решение нелинейной системы уравнений относительно