Оценить скорость сходимости формулы Герона

[VoprosT]

Здравствуйте, помогите, пожалуйста с упражнением:

Вот у нас есть $a>0$ и последовательность, которая сходится к $\sqrt{a} \colon x_{n+1}= \frac{1}{2}(x_n + \frac{a}{x_n})$ при $x_1 > 0$.
Необходимо оценить величину $\left\lvert x_n - \sqrt{a}\right\rvert$ в зависимости от $n$. Перед этим упражнением было показано, как оценить погрешность при вычислении $e$. А тут что-то явного выражения, ограничивающего эту разность, не выходит, или его явно предъявлять и не надо?

[ИСН]

И не надо.

[mihaild]

Явно выписывать не надо. Просто выразите погрешность на $n+1$-м шаге через погрешность на $n$-м.

[pogulyat_vyshel]

про принцип сжатых отображений полезно почитать

[VoprosT]

ИСН в сообщении #1480981 писал(а):

И не надо.

mihaild в сообщении #1480983 писал(а):

Явно выписывать не надо. Просто выразите погрешность на $n+1$-м шаге через погрешность на $n$-м.

Выходит следующее: $\left\lvert x_{n+1} - \sqrt{a}\right\rvert = \frac{1}{2}(\frac{x_{n}^{2}-2x_{n}\sqrt{a}+a}{x_n}) = \frac{1}{2}(\frac{(x_{n}-\sqrt{a})^2}{2x_n}) \leqslant (\left\lvert x_n - \sqrt{a}\right\rvert)^2$. То есть погрешность на следующем шаге меньше квадрата погрешности на предыдущем. А так как последовательность сходится к $\sqrt{a}$, то на какой-то итерации погрешность станет меньше $1$, тогда потом последовательность очень быстро сойдётся к $\sqrt{a}$. В этом суть, верно?

-- 27.08.2020, 19:12 --

pogulyat_vyshel в сообщении #1480989 писал(а):

про принцип сжатых отображений полезно почитать

Вот оно что, интересно, спасибо! До сжимающих отображений мне ещё ещё целый том в Зориче.

[mihaild]

VoprosT в сообщении #1481001 писал(а):

$\frac{1}{2}(\frac{(x_{n}-\sqrt{a})^2}{2x_n}) \leqslant (\left\lvert x_n - \sqrt{a}\right\rvert)^2$

Это не обязано быть правдой. Представьте, что $x_n = 10^{-100}$, $a = \frac{1}{4}$.

[VoprosT]

mihaild в сообщении #1481002 писал(а):

VoprosT в сообщении #1481001 писал(а):

$\frac{1}{2}(\frac{(x_{n}-\sqrt{a})^2}{2x_n}) \leqslant (\left\lvert x_n - \sqrt{a}\right\rvert)^2$

Это не обязано быть правдой. Представьте, что $x_n = 10^{-100}$, $a = \frac{1}{4}$.

Да, что-то я погорячился, тогда можно просто оставить $\frac{1}{2}(\frac{(x_{n}-\sqrt{a})^2}{2x_n})$

[mihaild]

VoprosT в сообщении #1481003 писал(а):

тогда можно просто оставить $\frac{1}{2}(\frac{(x_{n}-\sqrt{a})^2}{2x_n})$

А это уже не та форма - хочется погрешность в зависимости от $n$, но не от $x_n$ (иначе можно просто написать $|x_n - \sqrt{a}|$).

[VoprosT]

mihaild в сообщении #1481004 писал(а):

VoprosT в сообщении #1481003 писал(а):

тогда можно просто оставить $\frac{1}{2}(\frac{(x_{n}-\sqrt{a})^2}{2x_n})$

А это уже не та форма - хочется погрешность в зависимости от $n$, но не от $x_n$ (иначе можно просто написать $|x_n - \sqrt{a}|$).

Хм. Тогда можно вспомнить, что $x_n \geqslant \sqrt{a}$ и написать $\frac{1}{2}(\frac{(x_{n}-\sqrt{a})^2}{2x_n}) \leqslant \frac{1}{2}(\frac{(\left\lvert x_{n}-\sqrt{a} \right\rvert)^2}{2\sqrt{a}})$? Хотя $x_n$ всё равно осталось..
Продолжая, можно оценить вплоть до $\left\lvert x_1 - \sqrt{a} \right\rvert$, а степени в выражении будут чем-то вроде $2^n$ у модуля и $1+2+4+8+16+...+2^{n-1} = 2^n - 1$ у других коэффициентов:
$\frac{1}{2}(\frac{(x_{n}-\sqrt{a})^2}{2x_n}) \leqslant (\frac{1}{4\sqrt{a}})^{2^{n}-1}(\left\lvert x_{1}-\sqrt{a} \right\rvert)^{2^n}$
Хм. А зачем нам этот факт, если значение $\sqrt{a}$ мы не знаем(как раз ищем его), поэтому и значения этой разности не знаем

[mihaild]

VoprosT в сообщении #1481005 писал(а):

$\frac{1}{2}(\frac{(x_{n}-\sqrt{a})^2}{2x_n}) \leqslant (\frac{1}{4\sqrt{a}})^{2^{n}-1}(\left\lvert x_{1}-\sqrt{a} \right\rvert)^{2^n}$

Это плохая оценка, так как начальное приближение может сильно отличаться от ответа.

VoprosT в сообщении #1481005 писал(а):

А зачем нам этот факт, если значение $\sqrt{a}$ мы не знаем(как раз ищем его), поэтому и значения этой разности не знаем

Мы хотим оценить асимптотику ошибки в зависимости от $n$ - т.е. найти такую функцию $g$, что $|x_n - a| \leqslant f(a, x_1) \cdot g(n)$.

[VoprosT]

mihaild в сообщении #1481012 писал(а):

VoprosT в сообщении #1481005 писал(а):

$\frac{1}{2}(\frac{(x_{n}-\sqrt{a})^2}{2x_n}) \leqslant (\frac{1}{4\sqrt{a}})^{2^{n}-1}(\left\lvert x_{1}-\sqrt{a} \right\rvert)^{2^n}$

Это плохая оценка, так как начальное приближение может сильно отличаться от ответа.

Как тогда её улучшить?Подумать о том, что $x_1$ может быть любым? Или надо получить совсем другую оценку?

[mihaild]

VoprosT в сообщении #1481013 писал(а):

Как тогда её улучшить?

Не доходите до $x_1$ - начните с точки, которая уже достаточно близка. А еще может быть удобнее считать изменение относительной, а не абсолютной, погрешности.

[novichok2018]

Это же метод Ньютона. Разве про оценки для него не всё уже известно?

[GAA]

VoprosT в сообщении #1481013 писал(а):

Как тогда её улучшить?

Введем обозначение для относительной погрешности $n$-ого приближения

$\varepsilon = \frac {x_n - \sqrt a} {\sqrt a }.$

1.Если $|\varepsilon_1| < 1/2$, то $ 0\le \varepsilon_n \le \varepsilon_1^{2^n}$.
Из определения относительной погрешности $n$-ого приближения вытекает

$x_n =\sqrt a (1+\varepsilon_n ).$

Тогда

$x_{n+1} =\frac 1 2 (x_n + a/x_n) = \sqrt a \left(1 + \frac {\varepsilon^2} {2(1+\varepsilon_n)} \right).$

Подставляя выражение для $x_{n+1}$ через его относительную погрешность, получаем

$\varepsilon_{n+1} = \frac {\varepsilon_n^2} {2(1+\varepsilon_n)}.$

Т.к. $|\varepsilon_1| < 1/2$, то $0 < \frac 1 {2(1+\varepsilon_1)}< 1$. Следовательно, $\varepsilon_n$ неотрицательны. Из неотрицательности вытекает $\varepsilon_{n+1} \le \varepsilon_n^2$. Из этого вытекает утверждение.

2.Таким образом задача сводится к выбору первого приближения.
При $a>1$ аргумент можно представить в виде

$a= 2^{2k+l}M,$

где $1 \le M <2$, $l$ — ноль или 1.
В качестве начального приближения можно взять

$x_1 = 2^k \left(\frac {2^l} {3} M + 17/24\right).$

При $a< 1$ задачу можно свести к извлечению корня из $b\equiv1/a >1$.

Возможно в этом упражнение.

[Eule_A]

Если я правильно помню (поправьте меня, если ошибаюсь), у Ильина и Позняка в "Основах математического анализа" этот вопрос обсуждается.