2014 dxdy logo

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

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




 
 Сходимость итерационных процессов
Сообщение13.06.2014, 10:38 
Здравствуйте.
Вопрос в следующем- в ходе итерационного процесса получаю вектор невязки r. Элементы вектора- модуль разности значений в ячейке между предыдущим и текущим значением. Каким образом лучше вводить критерий для окончания расчета? Норма вектора меньше заданной величины |r|<eps или сравнивать каждое значение для вектора |r[i]|<epsi? Второй вариант кажется более надежным (не получится, что во всех точках погрешность нулевая, а в одной очень большая, для примера), но, вроде, и более медленным. Что посоветуете?

 
 
 
 Re: Сходимость итерационных процессов
Сообщение13.06.2014, 13:10 
А это зависит от задачи, которую Вы решаете. Второе ограничение более жесткое, но и более ресурсоемкое. Соответственно, надо думать, каким может быть вектор невязки на реально используемых данных, насколько часто надо будет производить такую проверку и т.д. и т.п., универсального ответа на все случаи жизни просто нет.

 
 
 
 Re: Сходимость итерационных процессов
Сообщение13.06.2014, 16:16 
AndrSlav в сообщении #874853 писал(а):
но, вроде, и более медленным.

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

 
 
 
 Re: Сходимость итерационных процессов
Сообщение13.06.2014, 16:31 
Имхо, эти варианты эквивалентны. Первый правда помедленнее будет в плане вычислений и поточнее в плане отклонения - то есть, мое имхо полностью противоположно ТС в этом плане.
А откуда брать вектор допустимых погрешностей - оттуда же, откуда и эпсилон в первом случае. Допустим, у нас все компоненты вектора имеют разные допустимые погрешности и при этом могут выражаться в разных единицах измерения. Как считать норму в первом случае? Например, вот так $$\sqrt{(\frac{r_1}{e_1})^2 + .... + (\frac{r_n}{e_n})^2}$$ и сравнивать ее с единицей. Будет условие - попадание в многомерную сферу вокруг нуля. Во втором случае - в многомерный куб.

 
 
 
 Re: Сходимость итерационных процессов
Сообщение13.06.2014, 16:37 
_Ivana в сообщении #874966 писал(а):
Допустим, у нас все компоненты вектора имеют разные допустимые погрешности и при этом могут выражаться в разных единицах измерения.

Проблема в том, что ограничения по точности обычно естественны для самого решения, но вовсе не для невязки. Т.е. контроль невязки -- малоинформативен.

 
 
 
 Re: Сходимость итерационных процессов
Сообщение13.06.2014, 16:55 
ТС, вот вам до кучи еще несколько вариантов мер отклонений в статье на хабре.
Цитата:
Выбор метрики полностью лежит на исследователе, поскольку результаты кластеризации могут существенно отличаться при использовании разных мер.
- то, о чем писал Pphantom.

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

 
 
 
 Re: Сходимость итерационных процессов
Сообщение13.06.2014, 18:56 
[/quote]Ну, замедление-то малосущественно: просто пробежаться по массиву со сравнением -- всяко гораздо быстрее, чем любая итерация. Другой вопрос -- а откуда Вы этот вектор допустимых погрешностей возьмёте?[/quote]
Здесь, наверно, соглашусь, замедление не критичное. А погрешность- исходя из того, что изменение решения не должно значительно повлиять на получаемые параметры. Т.е. , например, нахожу поле давления => изменение давления на последующих итерациях не должно изменить скорость в поле более, чем на заданную малую величину. Однако, как было сказано,
[/quote]Проблема в том, что ограничения по точности обычно естественны для самого решения, но вовсе не для невязки. Т.е. контроль невязки -- малоинформативен.[/quote]
Действительно, связь между невязкой и получаемыми из решения значениями неоднозначна (а точнее, я пока не осознал) :-) Но кроме невязки оценить точность, вроде бы, никак нельзя.

 
 
 
 Re: Сходимость итерационных процессов
Сообщение16.06.2014, 15:12 
AndrSlav в сообщении #875022 писал(а):
Но кроме невязки оценить точность, вроде бы, никак нельзя.

В итерационных процессах скорость сходимости обычно линейная (т.е. погрешность убывает в геометрической прогрессии). Тогда она довольно надёжно оценивается как $\frac{q}{1-q}\cdot\|\vec x_k-\vec x_{k-1}\|$.

 
 
 
 Re: Сходимость итерационных процессов
Сообщение16.06.2014, 23:35 

(Оффтоп)

Я готов к вопросу типа "а что такое $q$, собссно?..."

Это да, вопрос содержательный (ежели вдруг у кого возникнет). Но на него и ответы содержательные вполне возможны.

 
 
 
 Re: Сходимость итерационных процессов
Сообщение02.07.2014, 19:37 
ewert в сообщении #876240 писал(а):
Я готов к вопросу типа "а что такое $q$, собссно?..."

Это да, вопрос содержательный (ежели вдруг у кого возникнет). Но на него и ответы содержательные вполне возможны.


Да, интересно бы было узнать:) Но фраза про линейную сходимость несколько смущает- у меня разные методы за разное количество итераций сходятся. А если в методе подпространств Крылова задать пространство размерностью задачи- сойдется за 1 итерацию- это ведь не линейная сходимость? У меня с математикой не очень хорошие отношения, возможно, бред пишу:)

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group