Метод секущих

[StaticZero]

Пусть есть функция $f(x)$, монотонная строго и непрерывная на $[a, b]$ — отрезке, где есть только один корень, причём $f(a) f(b) < 0$.

Описана следующая процедура:

Цитата:

Проведём секущую через точки $f(a)$ и $f(b)$. Пусть её уравнение $y = mx - n$; найдём эти коэффициенты из системы уравнений

$$ \begin{cases} f(b) = mb - n, \\ f(a) = ma - n, \end{cases} $$

откуда

$$ m = \dfrac{f(b) - f(a)}{b - a}, \qquad n = -\dfrac{f(a)(b - a) - a(f(b) - f(a))}{b - a} = \dfrac{a f(b) - b f(a)}{b - a}. $$

Корень этой секущей равен $a_1 = n/m$. Проведём секущую через точки $f(a)$ и $f(a_1)$. Она пересечёт ось абсцисс в точке $b_1$. Теперь применяем всю описанную процедуру на отрезке $[a_1, b_1]$.

Я пока не могу понять, как провести строгое обоснование сходимости процедуры к корню. Можно было бы на скорую руку "вякнуть" про последовательность вложенных отрезков $[a, b] \supset [a_1, b_1] \supset \ldots$, но мне не очевидно, что:
а) отрезки вложенные;
б) их длина строго сокращается.

В каком направлении здесь нужно подумать?

[Mikhail_K]

С этой процедурой что-то не то.
Возьмите $f(x)=1-x^2$, $a=-2$, $b=0$. Условия выполнены.
Тогда получим $a_1=-0.5$, $b_1\in(-1,-0.5)$. Искомый корень $x=-1$.
Видим, что, во-первых, $b_1<a_1$, во-вторых, уже отрезок $[b_1,a_1]$ не содержит искомого корня.

Наиболее разумно будет строить отрезки специально так, чтобы они были вложенными и убывающими, и притом содержащими искомый корень. Например, так. У нас есть точки $a_0$ и $b_0$ по разные стороны от корня, проводим секущую, там где она пересекает ось абсцисс - пусть будет точка $x$. Дальше смотрим на знак $f(x)$ - если он тот же, что у $f(a_0)$, полагаем $a_1=x$, $b_1=b_0$; если такой же, что у $f(b_0)$, полагаем $a_1=a_0$, $b_1=x$. Затем повторяем всё снова уже с точками $a_1$ и $b_1$. Тогда Ваши условия a) и б) будут выполняться автоматически, и на каждой итерации корень будет находиться внутри отрезка.

[DeBill]

Метод секущих быстрее классического и супернадежного метода половинного деления. Но за все по жизни приходится платить... Платой за скорость сходимости здесь будет - отсутствие гарантий сходимости...

StaticZero в сообщении #1126781 писал(а):

как провести строгое обоснование сходимости процедуры к корню.

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

[svv]

(Оффтоп)

DeBill в сообщении #1126800 писал(а):

Но за все по жизни приходится платить...

Неужели математики не могут с этим что-нибудь сделать, наконец?

[StaticZero]

Mikhail_K в сообщении #1126790 писал(а):

Наиболее разумно будет строить отрезки специально так, чтобы они были вложенными и убывающими, и притом содержащими искомый корень. Например, так. У нас есть точки $a_0$ и $b_0$ по разные стороны от корня, проводим секущую, там где она пересекает ось абсцисс - пусть будет точка $x$. Дальше смотрим на знак $f(x)$ - если он тот же, что у $f(a_0)$, полагаем $a_1=x$, $b_1=b_0$; если такой же, что у $f(b_0)$, полагаем $a_1=a_0$, $b_1=x$. Затем повторяем всё снова уже с точками $a_1$ и $b_1$. Тогда Ваши условия a) и б) будут выполняться автоматически, и на каждой итерации корень будет находиться внутри отрезка.

То есть это вариация метода деления пополам, только точка будет подходить к корню медленнее...

[amon]

StaticZero в сообщении #1126781 писал(а):

Проведём секущую через точки $f(a)$ и $f(a_1)$.

Здесь - ошибка. Секущую надо проводить, взяв второй конец так, что бы $f(a|b)f(a_1)<0$. Тогда, если функция непрерывна, и корень на исходном промежутке ровно один, то метод всегда сойдётся, заодно и сходимость можно доказывать.

[Mikhail_K]

amon в сообщении #1126833 писал(а):

Здесь - ошибка. Секущую надо проводить, взяв второй конец так, что бы $f(a|b)f(a_1)<0$. Тогда, если функция непрерывна, и корень на исходном промежутке ровно один, то метод всегда сойдётся, заодно и сходимость можно доказывать.

Другими словами, Вы предлагаете делать так, как я описал выше в своём сообщении?

DeBill в сообщении #1126800 писал(а):

Метод секущих быстрее классического и супернадежного метода половинного деления. Но за все по жизни приходится платить... Платой за скорость сходимости здесь будет - отсутствие гарантий сходимости...

StaticZero в сообщении #1126826 писал(а):

То есть это вариация метода деления пополам, только точка будет подходить к корню медленнее...

У меня ощущение, что я чего-то сильно не понимаю. Вы вправду имеете в виду, что 1) Метод секущих, такой как он описан в Википедии ( https://ru.wikipedia.org/wiki/Метод_хорд ), там где секущая проводится через две последние точки вне зависимости от знака функции, быстрее метода половинного деления (во всяком случае, в большинстве случаев); 2) в то же время гибрид этих методов, предлагаемый мной или amon, медленнее метода половинного деления?
Что за странность? Откуда метод 2) может быть медленнее метода 1)? Ведь в методе 1) всё равно приходится считать значения функций во всех точках, так что сравнение их с нулём в методе 2) не может метод сильно замедлить.

[Евгений Машеров]

В описании наврано, зачем-то на одном шаге строится две секущие. Строится одна, в точке пересечения её с осью Х вычисляется функция. Если она ноль - ура!, если не ноль, то для следующего шага берётся отрезок, на концах которого разные знаки. Отрезки вложенные по построению, поскольку знаки на концах разные и точка пересечения секущей внутри отрезка, и строго вложенные, поскольку на концах предыдущего не нули.

[Mikhail_K]

Вот, и Евгений Машеров тоже со мной согласен, что метод, по уму, должен выглядеть именно так.

[Евгений Машеров]

А, так это википедики, да простит меня Алан Тьюринг за упоминание всуе его хобби... Я уж испугался, что такое в учебнике написано.
А по скорости - в большинстве практических случаев хорды быстрее бисекций, но есть контрпримеры, когда хуже. Деление пополам гарантирует результат за известное число шагов, regula falsi не гарантирует, хотя обычно число шагов меньше.

[Mikhail_K]

Евгений Машеров в сообщении #1126864 писал(а):

А, так это википедики, да простит меня Алан Тьюринг за упоминание всуе его хобби... Я уж испугался, что такое в учебнике написано.

Нет, то что в посте ТС - это какая-то невнятица, и я не знаю откуда он это взял.
В Википедии, во всяком случае, написано более внятно - но тоже без сравнения с нулём значений функции в промежуточных точках.

[Евгений Машеров]

И про сходимость. Она для хорд будет всегда, но не всегда быстрая. Пример - функция, в нуле равная миллиону, в единице равная минус единице, и близкая к ломаной, круто спадающей к точке 0,001, в которой принимает значение -,999999, а после неё почти горизонтальная. Бисекция за десять шагов даст ответ, а хорды будут подбираться шажками по миллионной доле. Но на практике подобное редкость.

[DeBill]

Mikhail_K в сообщении #1126865 писал(а):

Нет, то что в посте ТС - это какая-то невнятица, и я не знаю откуда он это взял.

Да вроде как раз по Википидеии: первая точка - это $b$, вторая - $a$, третья - $a_1$, четвертая - $b_1$...

Евгений Машеров
Если для Вашего примера запустить метод секущих, то уже вторая итерация вылетит хрен знает куда.... Так что все честно: иногда будет быстрее, а иногда - никак; в среднем -....

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

О скорости сходимости. Имеем для метода секущих $x_{n+1} = x_n - y_n \cdot \frac{x_n - x_{n-1}}{y_n - y_{n-1}}$ . Для модельной функции $y=x^2 -a^2$, с корнем $x=a$ (это, видимо, не принципиально: в общем случае надо смотреть тейлоровские разложения, и будет примерно также), имеем, для погрешности $\delta _n = x_n - a$:
$\delta _{n+1} = \frac{\delta_n \cdot \delta _{n-1}}{2a +\delta _n + \delta _{n-1}} \approx \frac{\delta_n \cdot \delta _{n-1}}{2a } $.
Полагая $\varepsilon _n = \ln (\delta _n)$, получим рек. равенство
$\varepsilon _{n+1} = \varepsilon _n + \varepsilon _{n-1} + \operatorname{const}$ - почти Фиббоначчи. Отсюда $\varepsilon _n \sim -\gamma ^n \cdot \operatorname{const}$, где $\gamma$ - золотое сечение. Так что Вики здесь не врёт...
Для сравнения: в методе касательных будет $\varepsilon _n \sim -2^n \cdot \operatorname{const}$, а в методе половинного деления (и методе хорд) $\varepsilon _n \sim -n\cdot\operatorname{const}$.
Итого: метод секущих сочетает в себе худшие свойства двух других: сходится не всегда, и не шибко быстро... Единственно, чем хорош: не надо считать производную (и обращать ее)

[svv]

В Википедии написано:

Цитата:

Будем искать нуль функции $f(x)$. Выберем две начальные точки $C_{1}(x_{1};y_{1})$ и $C_{2}(x_{2};y_{2})$ и проведем через них прямую. Она пересечет ось абсцисс в точке $(x_{3};0)$. Теперь найдем значение функции с абсциссой $x_{3}$. Временно будем считать $x_{3}$ корнем на отрезке $[x_{1};x_{2}]$. Пусть точка $C_{3}$ имеет абсциссу $x_{3}$ и лежит на графике. Теперь вместо точек $C_{1}$ и $C_{2}$ мы возьмём точку $C_{3}$ и точку $C_{2}$. Теперь с этими двумя точками проделаем ту же операцию и так далее, то есть будем получать две точки $C_{n+1}$ и $C_{n}$ и повторять операцию с ними. Отрезок, соединяющий последние две точки, пересекает ось абсцисс в точке, значение абсциссы которой можно приближённо считать корнем. Эти действия нужно повторять до тех пор, пока не получим значение корня с нужным приближением.

Мы (возьму на себя такую смелость; нас уже четверо ) не понимаем, почему этот алгоритм не делает различия между двумя случаями:
$f(x_3)$ имеет тот же знак, что $f(x_1)$, и
$f(x_3)$ имеет тот же знак, что $f(x_2)$.
В последнем случае целесообразно вместо отрезка $[x_3; x_2]$ взять $[x_1;x_3]$.
Описание метода в Вики выглядит так, словно о функции известно, что она выпуклая. Я не могу поверить, что автор метода не ввёл в него простейшую развилку, которая сделала бы его гораздо более полезным.

[DeBill]

svv в сообщении #1126895 писал(а):

почему этот алгоритм не делает различия

Как я понимаю, фишка в том, что в формуле

DeBill в сообщении #1126882 писал(а):

секущих $x_{n+1} = x_n - y_n \cdot \frac{x_n - x_{n-1}}{y_n - y_{n-1}}$ .

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