метод ИТП

В численном анализе метод ITP , сокращение от Interpolate Truncate и Project , является первым алгоритмом поиска корня , который достигает суперлинейной сходимости метода секущего. сохраняя при этом оптимальную наихудшая производительность метода пополам . Это также первый метод с гарантированной средней производительностью, строго лучшей, чем метод деления пополам при любом непрерывном распределении. На практике он работает лучше, чем традиционные стратегии, основанные на интерполяции и гибридных методах ( метод Брента , Риддерс , Иллинойс ), поскольку он не только сходится суперлинейно по функциям с хорошим поведением, но также гарантирует высокую производительность при функциях с плохим поведением, где интерполяция терпит неудачу.

Метод ITP следует той же структуре стандартных стратегий брекетинга, которая отслеживает верхнюю и нижнюю границы местоположения корня; но он также отслеживает область, в которой производительность в худшем случае находится на верхнем уровне. В качестве стратегии брекетинга на каждой итерации ITP запрашивает значение функции в одной точке и отбрасывает часть интервала между двумя точками, где значение функции имеет один и тот же знак. Запрашиваемая точка вычисляется в три этапа: она интерполирует поиск оценки regula falsi , затем искажает/усекает оценку (аналогично Regula falsi § Улучшения в regula falsi ), а затем проецирует искаженную оценку на интервал в окрестности биссектрисы. середина. Окрестность точки биссектрисы вычисляется на каждой итерации, чтобы гарантировать минмакс-оптимальность (теорема 2.1 из ). Метод зависит от трех гиперпараметров $\kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)$ и $n_{0}\in [0,\infty )$ где $\phi$ это золотое сечение ${\tfrac {1}{2}}(1+{\sqrt {5}})$: первые два управляют размером усечения, а третья — это слабая переменная, которая управляет размером интервала для шага проецирования.

Проблема с поиском корня

Учитывая непрерывную функцию $f$ определено из $[a,b]$ к $\mathbb {R}$ такой, что $f(a)f(b)\leq 0$, где ценой одного запроса можно получить доступ к значениям $f(x)$ по любому заданному $x$. И, учитывая заранее заданную целевую точность $\epsilon >0$Алгоритм поиска корня предназначен для решения следующей задачи с наименьшим количеством запросов:

Постановка задачи: найти ${\hat {x}}$ такой, что $|{\hat {x}}-x^{*}|\leq \epsilon$, где $x^{*}$ удовлетворяет $f(x^{*})=0$.

Эта проблема очень распространена в численном анализе , информатике и технике ; и алгоритмы поиска корней являются стандартным подходом к ее решению. Часто процедура поиска корня вызывается более сложными родительскими алгоритмами в более широком контексте, и по этой причине эффективное решение корневых проблем имеет чрезвычайно важное значение, поскольку неэффективный подход может привести к высоким вычислительным затратам, когда во внимание принимается более широкий контекст. счет. Это то, что пытается сделать метод ITP, одновременно используя гарантии интерполяции, а также минимальные оптимальные гарантии метода деления пополам, который заканчивается не более чем через $n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil$ итерации при запуске на интервале $[a_{0},b_{0}]$.

Метод

Данный $\kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)$, $n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil$ и $n_{0}\in [0,\infty )$ где $\phi$ это золотое сечение ${\tfrac {1}{2}}(1+{\sqrt {5}})$, в каждой итерации $j=0,1,2\dots$ метод ITP вычисляет точку $x_{\text{ITP}}$ следующие три шага:

Шаг 1 метода ITP.

Шаг 2 метода ИТП.

Шаг 3 метода ITP.

Все три шага в совокупности образуют метод ITP. Толстая синяя линия представляет собой «проецируемую-усеченную интерполяцию» метода.

1. [Шаг интерполяции] Вычисление биссектрисы и ложных точек: $x_{1/2}\equiv {\frac {a+b}{2}}$ и $x_{f}\equiv {\frac {bf(a)-af(b)}{f(a)-f(b)}}$ ;
2. [Шаг усечения] Возмущаем оценщик по направлению к центру: $x_{t}\equiv x_{f}+\sigma \delta$ где $\sigma \equiv {\text{sign}}(x_{1/2}-x_{f})$ и $\delta \equiv \min\{\kappa _{1}|b-a|^{\kappa _{2}},|x_{1/2}-x_{f}|\}$ ;
3. [Шаг проецирования] Спроецируйте оценщик на минмаксный интервал: $x_{\text{ITP}}\equiv x_{1/2}-\sigma \rho _{k}$ где $\rho _{k}\equiv \min \left\{\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {b-a}{2}},|x_{t}-x_{1/2}|\right\}$.

Значение функции $f(x_{\text{ITP}})$ в этой точке запрашивается, а затем интервал сокращается до корня, сохраняя подинтервал со значениями функции противоположного знака на каждом конце.

Алгоритм

Следующий алгоритм (написанный на псевдокоде ) предполагает начальные значения $y_{a}$ и $y_{b}$ даны и удовлетворяют $y_{a}<0<y_{b}$ где $y_{a}\equiv f(a)$ и $y_{b}\equiv f(b)$; и он возвращает оценку ${\hat {x}}$ это удовлетворяет $|{\hat {x}}-x^{*}|\leq \epsilon$ максимум в $n_{1/2}+n_{0}$ функциональные оценки.

Input: $a,b,\epsilon ,\kappa _{1},\kappa _{2},n_{0},f$ 
    Preprocessing: $n_{1/2}=\lceil \log _{2}{\tfrac {b-a}{2\epsilon }}\rceil$, $n_{\max }=n_{1/2}+n_{0}$, and  $j=0$;
    While ( $b-a>2\epsilon$ )
  
        Calculating Parameters:
            $x_{1/2}={\tfrac {a+b}{2}}$, $r=\epsilon 2^{n_{\max }-j}-(b-a)/2$, $\delta =\kappa _{1}(b-a)^{\kappa _{2}}$;
        Interpolation:
            $x_{f}={\tfrac {y_{b}a-y_{a}b}{y_{b}-y_{a}}}$;
        Truncation:
            $\sigma ={\text{sign}}(x_{1/2}-x_{f})$;
            If $\delta \leq |x_{1/2}-x_{f}|$ then $x_{t}=x_{f}+\sigma \delta$,
            Else $x_{t}=x_{1/2}$;
        Projection:
            If $|x_{t}-x_{1/2}|\leq r$ then $x_{\text{ITP}}=x_{t}$,
            Else $x_{\text{ITP}}=x_{1/2}-\sigma r$;
        Updating Interval:
            $y_{\text{ITP}}=f(x_{\text{ITP}})$;
            If $y_{\text{ITP}}>0$ then $b=x_{ITP}$ and $y_{b}=y_{\text{ITP}}$,
            Elseif $y_{\text{ITP}}<0$ then $a=x_{\text{ITP}}$ and $y_{a}=y_{\text{ITP}}$,
            Else $a=x_{\text{ITP}}$ and $b=x_{\text{ITP}}$;
            $j=j+1$;
Output: ${\hat {x}}={\tfrac {a+b}{2}}$

Пример: поиск корня многочлена

Предположим, что метод ITP используется для нахождения корня многочлена $f(x)=x^{3}-x-2\,.$ С использованием $\epsilon =0.0005,\kappa _{1}=0.1,\kappa _{2}=2$ и $n_{0}=1$ мы находим это:

Итерация	$a_{n}$	$b_{n}$	$c_{n}$	$f(c_{n})$
1	1	2	1.43333333333333	-0.488629629629630
2	1.43333333333333	2	1.52713145056966	0.0343383329048983
3	1.43333333333333	1.52713145056966	1.52009281150978	-0.00764147709265051
4	1.52009281150978	1.52713145056966	1.52137899116052	-4.25363464540141e-06
5	1.52137899116052	1.52713145056966	1.52138301273268	1.96497878177659e-05
6	1.52137899116052	1.52138301273268	← Критерии остановки удовлетворены

Этот пример можно сравнить с методом деления пополам. § Пример: поиск корня многочлена . Метод ITP потребовал менее половины количества итераций, чем деление пополам, чтобы получить более точную оценку корня без затрат на гарантии minmax. Другие методы также могут достичь аналогичной скорости сходимости (например, Риддерса, Брента и т. д.), но без гарантий минимального максимума, предоставляемых методом ITP.

Анализ

Основное преимущество метода ITP заключается в том, что он гарантированно не требует больше итераций, чем метод деления пополам, когда $n_{0}=0$. Таким образом, его средняя производительность гарантированно будет лучше, чем у метода деления пополам, даже если интерполяция не удалась. Более того, если интерполяция не дает сбоя (гладкие функции), то гарантированно достигается высокий порядок сходимости, как и у методов, основанных на интерполяции.

Худший случай производительности

Поскольку метод ITP проецирует оценку на интервал minmax с $n_{0}$ слабина, это потребует максимум $n_{1/2}+n_{0}$ итераций (теорема 2.1 из ). Это minmax-оптимум, как и метод деления пополам, когда $n_{0}$ выбран быть $n_{0}=0$.

Средняя производительность

Потому что это занимает не более $n_{1/2}+n_{0}$ итераций, среднее число итераций всегда будет меньше, чем у метода деления пополам для любого рассматриваемого распределения, когда $n_{0}=0$ (Следствие 2.2 из ).

Асимптотическая производительность

Если функция $f(x)$ дважды дифференцируемо и корень $x^{*}$ просто, то интервалы, полученные методом ИТП, сходятся к 0 с порядком сходимости ${\sqrt {\kappa _{2}}}$ если $n_{0}\neq 0$ или если $n_{0}=0$ и $(b-a)/\epsilon$ не является степенью 2 с членом ${\tfrac {\epsilon 2^{n_{1/2}}}{b-a}}$ не слишком близко к нулю (теорема 2.3 из ).

Программное обеспечение

• ИТП в R. предоставленный пакет

См. также

• Метод бисекции
• Метод рыцарей
• Подделки правил
• метод Брента

Внешние ссылки

• Улучшенный метод деления пополам , автор: Kudos