2014 dxdy logo

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

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




 
 Оценка погрешности в итерационном процессе
Сообщение12.09.2012, 00:15 
Часто итерационный процесс останавливают тогда, когда разность между текущим и предыдущим значением становится меньше какого-то эпсилон.
Например, такой принцип используется при приближенном вычислении интегралов с помощью квадратурных формул используется. В этом случае правило имеет свое обоснование, так как доказывается, что погрешность не превосходит величины $M |I_n - I_{n-1}|$. Константа $M>0$ не известна, но хоть что-то.

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

Какими общими свойствами должен обладать алгоритм, чтобы это правило было применимо?

Сейчас разбираюсь с алгоритмом нахождения собственного вектора диагонализируемой матрицы (оператора).

Пусть $A$ оператор.

Пространство $V$, на котором действует оператор, разбивается в прямую сумму одномерных инвариантных подпространств $V=V_1+...+V_n$.

Пусть $w_1$ - собственное значение $A$ максимальное по модулю. И пусть ему соответствует подпространство $V_1$.

Пусть $x$ - произвольный вектор. $x = x_1+ x_2+...+x_n$, где $x_i \in V_i$.

Тогда, $\left(\frac{1}{w_1}A\right)^n x = x_1+ \left(\frac{w_2}{w}\right)^n x_2+...+\left(\frac{w_n}{w}\right)^n x_n$

$\left(\frac{1}{w_1}\right) A^n x \rightarrow x_1$ при $n \rightarrow \infty $, так как $\left| \frac{w_i}{w}\right| < 1$.

Ввиду линейности, если $\left(\frac{1}{w_1}\right)A^n x \rightarrow x_1$, то и $A^n x \rightarrow y_1 \in V_1$.

Наверное, можно каждый раз нормировать результат, чтоб не получались слишком большие или маленькие числа.

Можно ли здесь теоретически оценить относительную погрешность через разность текущей и предыдущих значений итерации?

 
 
 
 Re: Оценка погрешности в итерационном процессе
Сообщение12.09.2012, 20:25 
Аватара пользователя
ellipse в сообщении #617711 писал(а):
Часто итерационный процесс останавливают тогда, когда разность между текущим и предыдущим значением становится меньше какого-то эпсилон.

ellipse в сообщении #617711 писал(а):
Какими общими свойствами должен обладать алгоритм, чтобы это правило было применимо?

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

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


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