Метод золотого сечения решение нелинейного уравнения

Elgam

Есть множество методов численного решения одномерных нелинейных уравнений
Возьмем к примеру метод половинного деления. Там на каждом шаге отрезок делится на две равных частей. Прога на паскале:
i:=0;
alp:=abs(B-A);
repeat
c:=(A+B)/2;
if(F(A)*F(C)<=0) then B:=C else A:=C;
i:=i+1;
newalp:=abs(B-A)/alp;
alp:=abs(B-A);
until (B-A<=E);
X:=(A+B)/2;
Fx:=F(X);
Iter:=i; {kolichestvo iteracii}
alpha:=newalp; {Sxodimost' metoda polovinnogo deleniya lineinaya s koeff.=0.5} - параметр сходимости
Есть еще метод золотого сечения. Там отрезок делится на две части специальным образом. Точку деления отрезка можно выбрать двумя способами: Когда длина левого подотрезка меньше чем длина правого и наоборот. Вот возникает вопрос: А как на каждом шаге определить, каким образом следует делить, так, чтобы первая часть была длиннее второй части или наоборот, так чтобы вторая часть была длиннее первой части? Ведь для быстрой сходимости итерационного процесса важно чтобы на каждом шаге решение оказывалось на том подотрезке, которая имеет меньшую длину чем длина другого подотрезка.
Приводится следующий код. Из данного фрагмента получается, что метод золотого сечения сходится примерно с такой же скоростью как у метода половинного деления.
i:=0;
alp:=abs(B-A);
repeat
c:=B-(B-A)/1.618034; { или же A+(B-A)/1.618034 ?}
if(F(A)*F(C)<=0) then B:=C else A:=C;
i:=i+1;
newalp:=abs(B-A)/alp;
alp:=abs(B-A);
until (B-A<=E);
X:=(A+B)/2;
Fx:=F(X);
Iter:=i;
alpha:=newalp; {параметр сходимости}

choconasty

Нет разницы: c:=B-(B-A)/1.618034, или c:=A+(B-A)/1.618034.
Скорость сходимости, по-моему, ещё меньше (в общей ситуации чем при делении пополам, а "параметр сходимости" — вообще бесполезный коэффициент, в данном случае.

kachokslava

преимущество метода золотого сечения состоит в том, что не надо выполнять деление при вычислении очередной точки.
если a,b,c,d - - точки: конец, G1, G2, конец, то если отбрасываем "a" и надо пересчитать новую точку, то просто: G3=d-(c-b)

Sanych

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

choconasty

Не понял твой метод — как задаются точки a, b, c и d?
По формулам в корневом посте, однократное деление на каждом шаге метода "зол. сечения" есть, причём не на 2., а на 1,67.., хотя для современных процессоров разницы уже нет.

choconasty

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

spiritmc

Первые четыре --- это два конца и два золотых сечения.
Дело не в делении, а в вычислении функции.
Там может быть очень небезразлично, сколько раз вычислять.
См. метод деления последовательностью Фибоначчи.
---
...Я работаю...

spiritmc

> Так при делении отрезка пополам тоже самое:
Не то же самое.
> на каждом шаге функция вычисляется ровно один раз.
Какой из отрезков ты делишь пополам?
Дрёмов прав: метод предназначен для задачи оптимизации, а не для поиска корней.
---
...Я работаю...

choconasty

> Какой из отрезков ты делишь пополам?
Есть [a, b], f(a f(b).
Делим пополам: c=(a+b)/2. Вычисляем f(c).
Выбираем из [a, c] и [c, b] новый "[a, b]".
> Дрёмов прав: метод предназначен для задачи
> оптимизации, а не для поиска корней.
Почему подобным методами задачи оптимизации не решаются в принципе (без дополнительной информации о функции я уже объяснил.
Кстати, давно хотел спросить — ты называешь свой метод цитирования единственно правильным, но для его применения к длинным текстам нужно знать, сколько строк займёт цитата на экране пользователя, следовательно, нужно разбивать текст на строки вручную, причём брать строки не больше некоторой разумной минимальной ширины (учитывая, что некоторые уже сидят на форуме с телефонов но тогда для десктопщиков такая цитата будет выглядеть слишком неряшливо (как стишок, с короткими строками).
Теговый метод таких проблем не создаёт.

spiritmc

>> Дрёмов прав: метод предназначен для задачи
>> оптимизации, а не для поиска корней.
> Почему подобным методами задачи оптимизации не решаются
> в принципе (без дополнительной информации о функции я уже объяснил.
А x^2=0, как это ни странно, имеет корень на отрезке [-1; 1].
Да и почти всюду нулевые функции тоже существуют.
> нужно знать, сколько строк займёт цитата на экране пользователя,
Ограничение на длину строки известно.
> следовательно, нужно разбивать текст на строки вручную,
Текстовый редактор делает это за человека.
> Теговый метод таких проблем не создаёт.
Он создаёт другие и куда большие проблемы.
---
...Я работаю...

yurimedvedev

Ограничение на длину строки известно.
К сожалению, только одному. О великий гуру! О великолепный кохтпа!

choconasty

> Почему подобным методами задачи оптимизации не решаются
> в принципе (без дополнительной информации о функции я уже объяснил.
А x^2=0, как это ни странно, имеет корень на отрезке [-1; 1].
Да и почти всюду нулевые функции тоже существуют.
Да, корень существует.
Но задача оптимизации — это не нахождения корней уравнения. И для класса C([a, b]) она не решается численно!
Никакое конечное число значений функции на [a, b] не позволит даже локализовать экстремум!
Разница между этими задачам принципиальная — быть корнем - локальное свойство точки. Быть точкой экстремума — глобальное свойство точки, по всему отрезку.
Текстовый редактор делает это за человека.
Ты все посты набираешь сначала в текстовом редакторе, то есть? И считаешь, что это удобней?
> Теговый метод таких проблем не создаёт.
Он создаёт другие и куда большие проблемы.
Какие, например? Есть тэги — [q], [quote] созданные специально для цитирования.
Существует подобная практика давно, придумано не на форум.локал, проверено, и поэтому вполне естественно, что эти тэги предоставляют больше преимуществ, и меньше проблем, чем любой искусственный способ.

spiritmc

> Никакое конечное число значений функции на [a, b] не позволит даже локализовать экстремум!
Бесконечное число локальных экстремумов --- это свойство постоянной либо нездоровой функций.
> Ты все посты набираешь сначала в текстовом редакторе, то есть?
А ты никогда не правишь то, что потом отсылаешь?
> И считаешь, что это удобней?
Да, значительно удобнее пользоваться полноценным редактором, а не огрызками мозилл.
Даже если это сообщение на одну строку.
> Какие, например? Есть тэги — [q], [quote] созданные специально для цитирования.
> Существует подобная практика давно, придумано не на форум.локал,
> проверено, и поэтому вполне естественно, что эти тэги предоставляют
> больше преимуществ, и меньше проблем, чем любой искусственный способ.
Это вообще смешно.
Начиная от того, что отрисованные цитаты сильно разрывают текст,
оставляя неоправданно большие зрительные пространства и отрисовывая кучу лишних линеек,
заканчивая отсылом к практике.
Подобная теговая практика существует вообще нисколько по сравнению с цитированием через ">" (или "ИИ>")
и представляет собой как раз искусственный способ, связанный с особенностями теговой разметки гипертекста.
---
...Я работаю антинаучным аферистом...

yurimedvedev

Подобная теговая практика существует вообще нисколько по сравнению с цитированием через ">" (или "ИИ>")
токактыпишешьотстойнашипредкинапротяжениисотенлетписалибезпробеловточекизаглавныхбукв
Оставить комментарий
Имя или ник:
Комментарий: