Сложность итерационного метода? - PullRequest
Новая
       6

Сложность итерационного метода?

1 голос
/ 11 июля 2011

Проблема:

Я хочу реализовать метод Якоби . Это похоже на метод с фиксированной точкой: 

Xn+1 = P Xn +Q

if X* verify X=PX +Q 

then if Xn converge then it converge to X*

скажем, мне удалось найти альфу <1, такую, что: </p>

||PX|| < alpha * ||X|| (обычно альфа - максимум собственных значений P, но здесь это не имеет значения)

Тогда мой метод будет сходиться.

Сложность

Я хотел бы рассчитать сложность такого алгоритма. скажем, я хочу || Xn-X * || быть меньше, чем эпсилон. для одной данной альфы я могу вычислить n так, чтобы вышеприведенное неравенство было проверено. Но в моем случае я могу доказать, что такая альфа существует, но у меня нет его значения.

Существуют ли методы для вычисления сложности для таких итерационных методов, не зная точно альфа?

Заранее спасибо

1 Ответ

2 голосов
/ 11 июля 2011

Без дополнительной информации: Нет.

Для того, чтобы была граница, необходимо доказать равномерное сходимость процесса по всем альфа-значениям.Но такой конвергенции не существует (если только у вас нет более строгого условия, например, alpha < 0.9

Не уверен, почему вы не можете сгенерировать конструктивный процесс, чтобы найти верхнюю границу <1 для альфы, если вы можете доказатьСуществование. Доказательством того, что метод сходится, является просто нахождение соответствующей нормы, в которой матричная норма <1 <em>, путем явного нахождения ее значения .

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

ДОКАЗАТЕЛЬСТВО

Пусть epsilon > 0.
Предположим, что мы можем ограничить число итераций некоторым f(x), где f: R+ --> N.
Т.е.Если e_n = ||Xn - X*||, мы предполагаем, что для всех n > f(epsilon). e_n < epsilon.

Мы покажем, что существует действительная альфа и N, такие что N > f(epsilon). e_N > epsilon.

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

Этот момент деликатный, так как наличие действительной границы f фактически зависит от альфы, поскольку предположениечто он ограничивает итерации, основанные на матрице, на которой альфа «определена».Хотя сама альфа неизвестна, мы должны доказать, что f действительно для всех значений альфа, и именно здесь мы переходим от нормальной сходимости к равномерной сходимости.

Мы выбрали наш эпсилони мы берем N = f(epsilon)+1.В соответствии с нашим предположением e_N < epsilon, давайте просто возьмем alpha = (2*epsilon/e_0) ^ 1/2N, предполагая 2*epsilon/e_0 < 1, в противном случае мы можем заменить эпсилон любым значением <1. </p> 

e_n+1 = || X(n+1) - X* ||
      = || PXn + Q - PX* - Q ||
      = || P(Xn - X*) ||
      <= ||P|| ||Xn-X*||
      = ||P|| e_n

Как я уже говорил, без дополнительной информации легкопостроить P так, чтобы вышеприведенное неравенство было фактическим равенством.Например, P = I*k дает равенство для всех вещественных k.Следовательно, существует P такое, что e_n+1 = ||P|| e_n = ... = ||P||^(n+1) * e_0

Наше последнее наблюдение состоит в том, что даже если ||PX|| < alpha * ||X|| может существовать X такое, что: ||PX|| > alpha^2 * ||X||.
Например, если P = I * alpha мыЗнайте, что alpha<1 и вышеупомянутое верно для всех X.(Опять же, поскольку никакой другой информации о P нет, достаточно того факта, что может существовать такой X.)

Если мы подключим наш alpha, мы заключаем, что возможно следующее: 

e_N = ||P||^N * e_0
    > (alpha^2)^N * e_0
    = alpha^2N * e_0
    = 2*epsilon  // since alpha = (2*epsilon/e_0) ^ 1/2N
    > epsilon
    > e_N // since we assumed we had a bound, and e_N < epsilon

Число не может быть больше самого себя.

QED.

...