На очередном шаге имеем хп:

x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=\frac{(1/3)x_n^{4/3}}{(1+(4/3)x_n^{1/3})}.\!

Скорость сходимости полученной последовательности составляет приблизительно 4/3. Это существенно меньше, нежели 2, необходимое для квадратичной сходимости, поэтому в данном случае можно говорить лишь о линейной сходимости, хотя функция всюду непрерывно дифференцируема, производная в корне не равна нулю, и f бесконечно дифференцируема везде, кроме как в корне.

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

Пусть

f(x)=x^2.\!

Тогда f'(x)=2x\! и следовательно x-f(x)/f'(x)=x/2\!. Таким образом сходимость метода не квадратичная, а линейная, хотя функция всюду бесконечно дифференцируема.

Ограничения

Пусть задано уравнение f(x)=0\!, где f(x)\colon\mathbb{X}\to\R\! и надо найти его решение.

Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя Канторовича.

Теорема Канторовича.

Если существуют такие константы A,B,C, , что:

\frac{1}{|f'(x)|}<A\!на [a, b], то есть f′(x)существует и не равна нулю; \left|\frac{f(x)}{f'(x)}\right|<B\!на [a, b], то есть f(x) ограничена; на [a, b], и |f''(x)|\leqslant C\leqslant\frac{1}{2AB}\!;

Причём длина рассматриваемого отрезка |a-b|<\frac{1}{AB}\left(1-\sqrt{1-2ABC}\right)\!. Тогда справедливы следующие утверждения:

на [a, b] существует корень x* уравнения f(x)=0\colon\exist x^*\in[a,\;b]\colon f(x^*)=0\!; если x_0=\frac{a+b}{2}\!, то итерационная последовательность сходится к этому корню: \left\{ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\right\}\to x^*\!; погрешность может быть оценена по формуле |x^*-x_n|\leqslant\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}\!.

Из последнего из утверждений теоремы в частности следует квадратичная сходимость метода:

|x^*-x_n|\leqslant\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}=\frac{1}{2}\frac{B}{2^{n-2}}\left((2ABC)^{2^{n-2}}\right)^2=\alpha |x^*-x_{n-1}|^2.\!

Тогда ограничения на исходную функцию f(x) будут выглядеть так:

функция должна быть ограничена; функция должна быть гладкой, дважды дифференцируемой; её первая производная f′(x) равномерно отделена от нуля; её вторая производная f′′(x) должна быть равномерно ограничена.

Обобщения и модификации

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

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

НЕ нашли? Не то? Что вы ищете?

Формула итераций этого метода имеет вид:

x_{n+1}=x_n-\frac{1}{f'(x_0)}f(x_n).\!

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

\alpha(x)=\alpha_0=-\dfrac{1}{f'(x_0)}.\!

При таком выборе α0 в точке х0 выполнено равенство:

\varphi'(x_0)=1+\alpha_0f'(x_0)=0,\!

и если отрезок, на котором предполагается наличие корня х* и выбрано начальное приближение х0, достаточно мал, а производная \varphi'(x)\!непрерывна, то значение \varphi'(x^*)\! будет не сильно отличаться от \varphi'(x_0)=0\!\! и, следовательно, график y=\varphi(x)\! пройдёт почти горизонтально, пересекая прямую у=х, что в свою очередь обеспечит быструю сходимость последовательности точек приближений к корню.

Этот метод можно также рассматривать, как модернизацию метода хорд (секущих), где число γ следует выбрать равным

\max\limits_x|\varphi'(x)|.\!

Рис.6. Иллюстрация последовательных приближений метода одной касательной, применённого к функции \scriptstyle{f(x)=e^x-2} с начальным приближением в точке x0=1,8..

Многомерный случай

Обобщим полученный результат на многомерный случай.

Пускай необходимо найти решение системы:

\left\{\begin{array}{lcr} f_1(x_1,\;x_2,\;\ldots,\;x_n)

Выбирая некоторое начальное значение \vec{x}^{[0]}\!, последовательные приближения \vec{x}^{[j+1]}\!находят путём решения систем уравнений:

f_i+\sum_{k=1}^n\frac{\partial f_i}{\partial x_k}(x^{[j+1]}_k-x_k^{[j]})=0,\qquad i=1,\;2,\;\ldots,\;n,\!

где

\vec{x}^{[j]}=(x_1^{[j]},\;x_2^{[j]},\;\ldots,\;x_n^{[j]}),\quad j=0,\;1,\;2,\;\ldots\!

Применительно к задачам оптимизации

Пусть необходимо найти минимум функции многих переменных f(\vec{x})\colon\R^n\to\R\!. Эта задача равносильна задаче нахождения нуля градиента \nabla f(\vec{x})\!. Применим изложенный выше метод Ньютона:

\nabla f(\vec{x}^{[j]})+H(\vec{x}^{[j]})(\vec{x}^{[j+1]}-\vec{x}^{[j]})=0,\quad j=1,\;2,\;\ldots,\;n,\!

где H(\vec{x})\! — гессиан функции f(\vec{x})\!.

В более удобном итеративном виде это выражение выглядит так:

\vec{x}^{[j+1]}=\vec{x}^{[j]}-H^{-1}(\vec{x}^{[j]})\nabla

Следует отметить, что в случае квадратичной функции метод Ньютона находит экстремум за одну итерацию.

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

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

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

\vec{x}^{[j+1]}=\vec{x}^{[j]}-\lambda_j

где \lambda_j=\arg\min_\lambda f(\vec{x}^{[j]}-\lambda H^{-1}(\vec{x}^{[j]})\nabla f(\vec{x}^{[j]})).\! Для оптимизации вычислений применяют следующее улучшение: вместо того, чтобы на каждой итерации заново вычислять гессиан целевой функции, ограничиваются начальным приближением H(f(\vec{x}^{[0]}))\! и обновляют его лишь раз в т шагов, либо не обновляют вовсе.

Применительно к задачам о наименьших квадратах

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

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97