Метод Симпсона (Мюллера) - порядок сходимости

[Xavu Bunepe]

Здравствуйте, уважаемые господа!
У меня возник один вопрос по теории численных методов, и я не могу разрешить его из-за путаницы в определениях и понятиях, в различных источниках и лекциях
ВОПРОС: Какой порядок сходимости у метода Мюллера*, или метода парабол ?
Казалось бы, я знаю на этот вопрос весьма точный ответ - это число p=1.8 , которое выводится из формулы отношения погрешностей в последовательных итерациях
Но вот в чем загвоздка - необходимо ответить, какой метод имеет третий порядок сходимости? И по предварительным ответам указано, что именно метод Мюллера* имеет этот самый третий порядок сходимости
Конечно же перед тем как задавать вопрос, я занялся просмотром соответствующей литературы, однако кроме данного числа 1.8, другой информации в особенности не нашлось, разве что уточнение до 1.839
Я начинаю подозревать, что скорость сходимости и порядок сходимости - это не совсем одно и то же; Возможно кто-либо из них является реальной степень отношения погрешностей на последующих итерациях, а какое-то просто натуральной цифрой, на вскидку характеризующую соответствующую величину
Заранее благодарен за помощь

* - Подправил альтернативное название метода, в котором случайно ошибся

[Gortaur]

Порядок сходимости - это вот что. Допустим Вы делаете дискретизацию с интервалами $dx$. Тогда если порядок сходимости $\alpha$, то

$$ I - \bar{I} = \mathcal{O}(dx^\alpha), $$

где $I$ - реальное значение интеграла, $\bar{I}$ - численное. Обычно порядок сходимости - натуральное число если у Вас не какой-нибудь странный метод и необычный случай. Так что очевидно что $1.8$ это не порядок сходимости.

[Xavu Bunepe]

Gortaur в сообщении #403785 писал(а):

Порядок сходимости - это вот что

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

Цитата:

В качестве $x^{(k+1)}$ выбирается тот из корней квадратного уравнения, для которого величина $|x^{(k+1)}-x^{(k)}|$ наименьшая. Доказывается, что погрешность метода определяется соотношением $e^{(k+1)}=e^{(k)}*e^{(k-1)}*e^{(k-2)}={(e^k)}^p$
где p = 1,839.

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

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

PS Конечно же в предоставленной формуле, верхние индексы - это не арифметическое степени, а номер итерации

[ewert]

Что Вы понимаете под "методом Симпсона" -- и вообще, какая задача-то решается?...

[Xavu Bunepe]

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

Что Вы понимаете под "методом Симпсона" -- и вообще, какая задача-то решается?...

Возможно рассматриваемый метод именуется Мюллером, а не Симпсоном; однако за то время пока я изучал литературу по соответствующему вопросу, встречали разные обозначения, и я не уверен какое из них достоверно корректное

По крайней мере тот метод который нужен мне, описан в этом источнике: http://physics.herzen.spb.ru/library/01/01/nm_labs/nonlineareq.htm#_ftnref4 , после перехода по ссылке необходимо немного прокрутить страницу вверх, и там предоставлено описание этого метода Мюллера/парабол

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

[ewert]

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

[Circiter]

2ewert

Цитата:

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

Вертится в голове какой-то метод Чебышева, кубическая сходимость, да....

2Xavu Bunepe
Действительно, при работе с дискретными примочками порядок сходимости оценивают примерно так как писал Gortaur (только там погрешность в модуль заключают + учет неравномерности сетки). Видимо, в этом направлении надо копать.

Все-равно как-то не понятно, откуда там тройка может взяться. Может быть имелось ввиду что-нибудь другое, например, что через метод Симпсона (на параболах) можно точно приближать полиномы степени не более третьей? Не, это глупость я сказал...

[Gortaur]

Приведите задачу - что Вам нужно посчитать? Чебышев и правда хорошо приближает.

[ewert]

Circiter в сообщении #403833 писал(а):

Все-равно как-то не понятно, откуда там тройка может взяться.

Ну а что там ещё-то может получиться. Если $x_k$ и $x_{k+1}$ -- два соседних приближения к корню $x^*$, то погрешность $r_{k+1}\equiv x^*-x_{k+1}\sim\dfrac{1}{f'}\cdot f(x_{k+1})$. В свою очередь, $f(x_{k+1})\sim\dfrac{f'''}{6}\cdot(x_{k+1}-x_k)^3\sim\dfrac{f'''}{6}\cdot(x^*-x_k)^3\equiv\dfrac{f'''}{6}\cdot r_k^3$ (если использовать формулу Тейлора второго порядка). Т.е. $r_{k+1}\sim\dfrac{f'''}{f'}\cdot r_k^3$.

[Xavu Bunepe]

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

По идее, скорость сходимости именно кубической и должна оказаться

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

Circiter в сообщении #403833 писал(а):

Действительно, при работе с дискретными примочками порядок сходимости оценивают примерно так как писал Gortaur

Спасибо; при изучении различных материалов по данному вопросу, я пришел к выводу что в принципе существует огромное множество *конкретных* способов оценки скорости сходимости того или иного итерационного метода
Так например, в рассмотрение может вводиться как разница между последовательными приближениями $x^{(k+1)}$ и $x^{(k)}$, так и соответствующая разность с начальным прибложением в виде $x^{(k+1)}$ и $(x^0)$, после чего для указанных соотношений погрешность очередной итерации выражается через погрешность предыдущей итерации, в виде $e^{(k+1)}=k*{e^{(k)}}^p$, и в таком случае указанное число $p$ как раз и будет скоростью сходимости

Gortaur в сообщении #403839 писал(а):

Приведите задачу - что Вам нужно посчитать? Чебышев и правда хорошо приближает.

Спасибо; практическая реализация задачи уже успешно завершена, и в принципе фактический расчет уже производится; необходимо теперь теоретически обосновать, что имеется третий порядок сходимости, все-таки хочется сделать все по-честному

[ewert]

Xavu Bunepe в сообщении #403972 писал(а):

кроме того в одном из учебников, а именно Петров и Лобанов - Лекции по вычислительной математике, нашелся алгоритм выведение требуемой формулы для апроксимирующего многочлена произвольного порядка

самое главное -- что этот замечательный алгоритм никому не нужен

[Xavu Bunepe]

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

Самое главное -- что этот замечательный алгоритм никому не нужен

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

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

Т.е. $r_{k+1}\sim\dfrac{f'''}{f'}\cdot r_k^3$.

Видимо указанный вариант является оптимальным для решения задачи, насколько я понимаю условием сходимости является условие типа $|\dfrac{f'''}{f'}|<1$, чтобы получилось что-то вроде убывающей геометрической прогрессии
Конечно я понимаю, что данное условие является достаточным, а не необходимым, поскольку если $r_0$ было достаточно малым по абсолютной величине числом, таким что при умножении на отношение соответствующих производных, получается величина меньшая единицы; хотя в таком случае уже кубическую сходимость гарантировать нельзя, особенно если отношение производных в новой точке сильно меняется; хотя это уже плохо обусловленная задача, и рассматривать ее нецелесообразно

[ewert]

Xavu Bunepe в сообщении #404766 писал(а):

насколько я понимаю условием сходимости является условие типа $|\dfrac{f'''}{f'}|<1$, чтобы получилось что-то вроде убывающей геометрической прогрессии

Нет, конкретное значение этого выражения не имеет значения (кстати, я там потерял шестёрку внизу -- она случайно затёрлась производной при копипастении). Там пафос в другом: что каждая следующая погрешность оценивается через некоторую степень предыдущей, умноженную на некоторую константу (не важно какую, лишь бы фиксированную): $|r_{k+1}|\leqslant C\cdot|r_k|^m,\ m>1$. При этом уже сходимость гарантирована, если начальное приближение достаточно близко к решению. И скорость сходимости называется сверхлинейной, имея в виду, что под линейной понимается сходимость со скоростью геометрической прогрессии, т.е. $|r_{k+1}|\leqslant q\cdot|r_k|$, и вот тут-то действительно должно быть $q<1$. Слово "порядок" для $m$ в этой ситуации употреблять как-то не принято (как мне кажется), т.к. оно довольно жёстко закреплено за показателем степени в абсолютных оценках погрешности типа $O(h^m)$, где $h$ -- малый параметр метода (например, шаг численного интегрирования).