§5. Метод Ньютона и одношаговые оценки: шагай по касательной

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

Метод касательных

Для численного решения нелинейного уравнения $\varphi(x) = 0$ можно использовать метод Ньютона (метод касательных). Задаётся начальное приближение $x_0$, затем вычисляются

Откуда формула. Проведём касательную к графику $y = \varphi(x)$ в точке $(x_k, \varphi(x_k))$: $y = \varphi(x_k) + \varphi'(x_k)(x - x_k)$. Положим $y = 0$ — найдём, где касательная пересекает ось абсцисс. Координата $x_{k+1}$ этой точки удовлетворяет

откуда (при $\varphi'(x_k) \ne 0$) и получается (5).

Смысл по-пацански: заблудился в овраге в темноте и ищешь, где ровное место. Щупаешь склон под ногами (производная), прикидываешь по нему, где склон выйдет в ноль, и шагаешь туда. Потом снова щупаешь.

Замечание. Для нелинейной системы уравнений $\boldsymbol\varphi(\mathbf x) = \mathbf 0$ аналогом (6) будет линейная система $\boldsymbol\varphi'(\mathbf x_k)(\mathbf x_{k+1} - \mathbf x_k) = -\boldsymbol\varphi(\mathbf x_k)$, где $\boldsymbol\varphi'$ — матрица Якоби из частных производных. Решив её методом Гаусса, находим очередной шаг.

Как быстро сходится

Теорема 3. Пусть в $\delta$-окрестности корня $x^*$ уравнения $\varphi(x) = 0$ функция $\varphi$ дважды непрерывно дифференцируема, $0 < \alpha \le |\varphi'(x)|$, $|\varphi''(x)| \le \beta$. Положим $\varepsilon = \min\{\delta/2, \alpha/\beta\}$. Тогда если $|x_0 - x^*| \le \varepsilon$, то при всех $k \ge 0$

$$|x_{k+1} - x^*| \le |x_{k+1} - x_k| \quad \text{и} \quad |x_{k+1} - x^*| \le \delta^{-1}|x_k - x^*|^2.$$

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

Второе показывает, что при старте из достаточно малой окрестности простого корня ($\varphi'(x^*) \ne 0$) метод сходится квадратично — существенно быстрее геометрической прогрессии. На каждой итерации число верных знаков примерно удваивается.

Если же $x_0$ взят далеко от корня, процесс может разойтись — в частности, возникают «осцилляции»: касательная перекидывает приближение через корень всё дальше.

Пример 10. Квадратный корень. Извлечь $\sqrt a$ — значит решить $\varphi(x) = x^2 - a = 0$. Здесь $\varphi'(x) = 2x$, и

— известный «вавилонский» алгоритм усреднения $x_k$ и $a/x_k$.

Смотри на порядок ошибки: $10^{-3}$, $10^{-6}$, $10^{-12}$, $10^{-24}$ — каждый шаг удваивает число верных знаков.

Уравнение правдоподобия для Коши

Пример 11. Для модели сдвига закона Коши с плотностью $f(x, \theta) = \dfrac{1}{\pi[1 + (x - \theta)^2]}$ уравнение правдоподобия (3) имеет вид

Информация Фишера одного наблюдения

По теореме 1 §4 асимптотическая дисперсия ОМП $\tilde\theta$ равна $1/I_1 = 2$. Сравним с медианой (глава 7): $\sigma^2_{MED} = \pi^2/4$. Относительная эффективность

В этой модели ОМП асимптотически точнее медианы примерно на 23 %.

Но уравнение (7) коварно. Левая часть — сумма непрерывных функций, положительная при $\theta < X_{(1)}$ и отрицательная при $\theta > X_{(n)}$. Значит, хотя бы один корень всегда есть. А если привести слагаемые к общему знаменателю, в числителе окажется многочлен степени $2n - 1$ — корней может быть до $2n - 1$ (вопрос 3). Плохой старт Ньютона легко уводит к «не тому» корню или вообще в бесконечность.

Одношаговые оценки

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

Теорема 4. Пусть выполнены условия R1–R8 из §3 и §4, а оценка $\hat\theta_0$ такова, что $\sqrt n\,(\hat\theta_0 - \theta) \xrightarrow{d} \xi \sim N(0, \sigma^2(\theta))$. Тогда одношаговая оценка

$$\hat\theta_1 = \hat\theta_0 - \frac{\varphi(\hat\theta_0)}{\varphi'(\hat\theta_0)}, \qquad \varphi(\theta) = \frac{\partial}{\partial\theta}\ln L(\theta) = \sum_{i=1}^n \frac{\partial}{\partial\theta}\ln f(x_i, \theta),$$

имеет асимптотическую дисперсию $1/I_1(\theta)$.

Почему так. Стартовая оценка уже лежит на расстоянии порядка $1/\sqrt n$ от корня. Шаг Ньютона квадратично уменьшает ошибку: было $\sim 1/\sqrt n$, стало $\sim 1/n$ — пренебрежимо мало на фоне статистического разброса $1/\sqrt n$ самого корня. Значит, после одного шага мы уже «сидим» на ОМП с точностью, которая не влияет на асимптотику.

Пример 12. Возьмём для сдвига Коши в качестве начальной оценки $\hat\theta_0$ выборочную медиану $MED$. По теореме 4 и теореме 1 главы 7 одношаговая оценка $\hat\theta_1$ с

является асимптотически эффективной оценкой параметра сдвига $\theta$. (У Лагутина $\varphi$ записана с противоположным знаком — на шаг Ньютона это не влияет.)

Пример 13. Пусть $X_i$ имеют плотность-смесь $f(x, \theta) = (1 - \theta)p_1(x) + \theta\,p_2(x)$, где плотности $p_1$ и $p_2$ известны, а вес $\theta \in [0, 1]$ — нет. Пусть у $p_1$ и $p_2$ средние $\mu_1 \ne \mu_2$, а дисперсии конечны. Поиск ОМП приводит к уравнению степени $n - 1$ относительно $\theta$:

решить которое при больших $n$ довольно сложно. Применение теоремы 4 позволяет, не решая его, асимптотически эффективно оценить $\theta$. Для этого достаточно взять в качестве $\hat\theta_0$ оценку метода моментов из уравнения $(1 - \theta)\mu_1 + \theta\mu_2 = \bar X$:

По ЦПТ она асимптотически нормальна — и один шаг Ньютона от неё даёт эффективную оценку.

Смысл по-пацански: черновик (медиана, метод моментов) кладёт тебя в нужный район. Один точный шаг по касательной — и ты у нужного подъезда. Дальше шагать смысла нет: статистический шум всё равно больше.

Пощупай руками

Режим «Касательные Ньютона»: синяя кривая — левая часть уравнения правдоподобия для пяти точек Коши. Двигай стартовую точку и число шагов:

• старт около корня (или кнопка «Старт = медиана») — в таблице число верных знаков удваивается;
• старт подальше (попробуй $\theta_0 = 2$ или $1$) — касательные разбрасывает, Ньютон улетает в бесконечность;
• при $\theta_0 = 0{,}5$ — хаотичные осцилляции.

Режим «Одношаговая оценка»: $n\,\mathbf{D}$ медианы, одного шага от неё и ОМП. Один шаг почти не уступает полному решению, и оба держатся около 2 против 2,47 у медианы.

Проверь себя