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

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

Метод хорд и метод секущих это синонимы. И если некоторые авторы предпочитают один термин другому, это не значит, что они описывают разное. Разница в словах означает меньше, чем именование метода Лобачевского-Греффе-Данделена одним именем, так хотя бы национальность автора можно угадать. И если википедики (теперь мои извинения сэру Элтону Джону) приводят различие, то пусть хотя бы дают работающий алгоритм.
Да, ложное положение и regula falsi это то же самое.

[svv]

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

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

Так мы же когда отказываемся? — когда уже понятно, что функция выпуклой не является ($f(x_1)<0,f(x_3)>0,f(x_2)>0$), и тупой метод всё равно не обещает ни быстрой, ни вообще никакой сходимости. А так есть надежда, что функция вогнутая, и к ней будет применён адекватный вариант метода.

[ewert]

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

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

[ewert]

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

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

[DeBill]

ewert в сообщении #1126940 писал(а):

А, да, прошу прощения, не вчитался.

А, да, я тоже...Почему то решил, что алгоритм у ТС такой же, как в Вики: строятся последовательно точки $b,a,a_1, b_1,...$. Ан нет: по паре $(a,b)$ строится пара $(a_1, b_1)$, что не тоже самое...
Тогда: пересчет для алгоритма ТС на модельном примере (выпуклость - вниз, корень - в точке $c$) дает для логарифма погрешности $\delta _n = \ln (c-a_n)$ асимптотику $\delta _n \sim - \operatorname{const}\cdot \mu ^n$ с показателем сходимости $\mu = 1 + \sqrt{2} =2.4142...$. Это чуть хуже чем показатель для чистого метода секущих, расчитанного на две итерации: $\gamma ^2 = \frac{3+\sqrt{5}}{2} =2.618...$ . Зато, для выпуклой вниз функции, при условии, что мы не обломались на первом шаге ( $b_1 < b$), сходимость получается.

-- 30.05.2016, 12:48 --

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

Так мы же когда отказываемся? — когда уже понятно, что функция выпуклой не является

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

(Оффтоп)

"Не вынесет" здесь означает "новый вложен в старый"

[whitefox]

В справочнике Г.Корн Т.Корн пункт 20.2-2(c), помимо указанной выше формулы метода секущих, содержится следующий текст:

Г.Корн Т.Корн писал(а):

Для отыскания действительных корней действительных уравнений приближение $z^{[j+1]}$ обычно строят по $z^{[j]}$ и $z^{[k]},$ где $k=k(j)<j$ — наибольший индекс, такой, что $f(z^{[k]})$ и $f(z^{[j]})$ имеют разные знаки:

$$z^{[j+1]}=z^{[j]}-\frac{z^{[j]}-z^{[k]}}{f(z^{[j]})-f(z^{[k]})}f(z^{[j]})$$

[DeBill]

whitefox
И для примера Евгений Машеров, метод будет пилить по одной миллионной долго-долго.
Зато надежно, блин...

-- 30.05.2016, 17:49 --

А с другой стороны: а чё делать? Трясти

ewert в сообщении #1126940 писал(а):

сочетание чистого метода хорд (не секущих) с методом половинного деления

?

[whitefox]

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

А с другой стороны: а чё делать? Трясти

ewert в сообщении #1126940 писал(а):

сочетание чистого метода хорд (не секущих) с методом половинного деления

?

Имхо, чистая бисекция для данного примера сработает лучше.

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

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

[ewert]

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

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

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

-- Пн май 30, 2016 21:24:11 --

whitefox в сообщении #1127168 писал(а):

В справочнике Г.Корн Т.Корн пункт 20.2-2(c), помимо указанной выше формулы метода секущих, содержится следующий текст:

Г.Корн Т.Корн писал(а):

Для отыскания действительных корней действительных уравнений приближение $z^{[j+1]}$ обычно строят по $z^{[j]}$ и $z^{[k]},$ где $k=k(j)<j$ — наибольший индекс, такой, что $f(z^{[k]})$ и $f(z^{[j]})$ имеют разные знаки:

$$z^{[j+1]}=z^{[j]}-\frac{z^{[j]}-z^{[k]}}{f(z^{[j]})-f(z^{[k]})}f(z^{[j]})$$

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