2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

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

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Метод Симпсона (Мюллера) - порядок сходимости
Сообщение24.01.2011, 15:24 


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

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

 Профиль  
                  
 
 Re: Метод Симпсона (Короткий вопрос, просьба посмотреть)
Сообщение24.01.2011, 15:49 


26/12/08
1813
Лейден
Порядок сходимости - это вот что. Допустим Вы делаете дискретизацию с интервалами $dx$. Тогда если порядок сходимости $\alpha$, то
$$
I - \bar{I} = \mathcal{O}(dx^\alpha),
$$
где $I$ - реальное значение интеграла, $\bar{I}$ - численное. Обычно порядок сходимости - натуральное число если у Вас не какой-нибудь странный метод и необычный случай. Так что очевидно что $1.8$ это не порядок сходимости.

 Профиль  
                  
 
 Re: Метод Симпсона (Короткий вопрос, просьба посмотреть)
Сообщение24.01.2011, 16:08 


24/01/11
7
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 Конечно же в предоставленной формуле, верхние индексы - это не арифметическое степени, а номер итерации

 Профиль  
                  
 
 Re: Метод Симпсона (Короткий вопрос, просьба посмотреть)
Сообщение24.01.2011, 16:17 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Метод Симпсона (Короткий вопрос, просьба посмотреть)
Сообщение24.01.2011, 16:31 


24/01/11
7
ewert в сообщении #403798 писал(а):
Что Вы понимаете под "методом Симпсона" -- и вообще, какая задача-то решается?...
Возможно рассматриваемый метод именуется Мюллером, а не Симпсоном; однако за то время пока я изучал литературу по соответствующему вопросу, встречали разные обозначения, и я не уверен какое из них достоверно корректное

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

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

 Профиль  
                  
 
 Re: Метод Симпсона (Короткий вопрос, просьба посмотреть)
Сообщение24.01.2011, 17:01 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Метод Симпсона (Короткий вопрос, просьба посмотреть)
Сообщение24.01.2011, 17:31 
Заслуженный участник


26/07/09
1559
Алматы
2ewert
Цитата:
по идее, скорость сходимости именно кубической и должна оказаться. Только я такого метода, кажется, не встречал

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

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

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

 Профиль  
                  
 
 Re: Метод Симпсона (Короткий вопрос, просьба посмотреть)
Сообщение24.01.2011, 17:40 


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

 Профиль  
                  
 
 Re: Метод Симпсона (Короткий вопрос, просьба посмотреть)
Сообщение24.01.2011, 18:06 
Заслуженный участник


11/05/08
32166
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$.

 Профиль  
                  
 
 Re: Метод Симпсона (Короткий вопрос, просьба посмотреть)
Сообщение24.01.2011, 21:17 


24/01/11
7
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 писал(а):
Приведите задачу - что Вам нужно посчитать? Чебышев и правда хорошо приближает.
Спасибо; практическая реализация задачи уже успешно завершена, и в принципе фактический расчет уже производится; необходимо теперь теоретически обосновать, что имеется третий порядок сходимости, все-таки хочется сделать все по-честному

 Профиль  
                  
 
 Re: Метод Симпсона (Короткий вопрос, просьба посмотреть)
Сообщение24.01.2011, 21:54 
Заслуженный участник


11/05/08
32166
Xavu Bunepe в сообщении #403972 писал(а):
кроме того в одном из учебников, а именно Петров и Лобанов - Лекции по вычислительной математике, нашелся алгоритм выведение требуемой формулы для апроксимирующего многочлена произвольного порядка

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

 Профиль  
                  
 
 Re: Метод Симпсона (Короткий вопрос, просьба посмотреть)
Сообщение26.01.2011, 13:11 


24/01/11
7
ewert в сообщении #403994 писал(а):
Самое главное -- что этот замечательный алгоритм никому не нужен
В случае если бы целью решаемой задачи было получение самого быстрого и эффективного варианта решения, то видимо мне пришлось бы с Вами согласиться; но цель работы другая, и я не могу ее поменять вне зависимости от моего желания
ewert в сообщении #403859 писал(а):
Т.е. $r_{k+1}\sim\dfrac{f'''}{f'}\cdot r_k^3$.
Видимо указанный вариант является оптимальным для решения задачи, насколько я понимаю условием сходимости является условие типа $|\dfrac{f'''}{f'}|<1$, чтобы получилось что-то вроде убывающей геометрической прогрессии
Конечно я понимаю, что данное условие является достаточным, а не необходимым, поскольку если $r_0$ было достаточно малым по абсолютной величине числом, таким что при умножении на отношение соответствующих производных, получается величина меньшая единицы; хотя в таком случае уже кубическую сходимость гарантировать нельзя, особенно если отношение производных в новой точке сильно меняется; хотя это уже плохо обусловленная задача, и рассматривать ее нецелесообразно

 Профиль  
                  
 
 Re: Метод Симпсона (Короткий вопрос, просьба посмотреть)
Сообщение26.01.2011, 14:07 
Заслуженный участник


11/05/08
32166
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$ -- малый параметр метода (например, шаг численного интегрирования).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group