Сходимость итерационных процессов

[AndrSlav]

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

[Pphantom]

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

[ewert]

AndrSlav в сообщении #874853 писал(а):

но, вроде, и более медленным.

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

[_Ivana]

Имхо, эти варианты эквивалентны. Первый правда помедленнее будет в плане вычислений и поточнее в плане отклонения - то есть, мое имхо полностью противоположно ТС в этом плане.
А откуда брать вектор допустимых погрешностей - оттуда же, откуда и эпсилон в первом случае. Допустим, у нас все компоненты вектора имеют разные допустимые погрешности и при этом могут выражаться в разных единицах измерения. Как считать норму в первом случае? Например, вот так

$$\sqrt{(\frac{r_1}{e_1})^2 + .... + (\frac{r_n}{e_n})^2}$$

и сравнивать ее с единицей. Будет условие - попадание в многомерную сферу вокруг нуля. Во втором случае - в многомерный куб.

[ewert]

_Ivana в сообщении #874966 писал(а):

Допустим, у нас все компоненты вектора имеют разные допустимые погрешности и при этом могут выражаться в разных единицах измерения.

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

[_Ivana]

ТС, вот вам до кучи еще несколько вариантов мер отклонений в статье на хабре.

Цитата:

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

- то, о чем писал Pphantom.

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

[AndrSlav]

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

[ewert]

AndrSlav в сообщении #875022 писал(а):

Но кроме невязки оценить точность, вроде бы, никак нельзя.

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

[ewert]

(Оффтоп)

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

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

[AndrSlav]

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

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

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

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