Кратко и по делу.
Существование и единственность
- Рассмотрим $f(x)=\cos x-x$. $f$ непрерывна, $f(0)=1>0$, $f(1)=\cos 1-1\approx -0.4597<0$, следовательно по теореме о промежуточном значении существует корень в $(0,1)$.
- Любой корень должен лежать в $[-1,1]$, поскольку при $x>1$ имеет место $\cos x\le 1<x$, а при $x<-1$ — $\cos x\ge -1>x$. На отрезке $[-1,1]$ производная
$$f^{\prime }(x)=-\sin x-1<-\sin 1-1<0,$$ поэтому $f$ строго убывает на $[-1,1]$ и корень единственен. Обозначим его $\alpha$. Численно $\alpha \approx 0.73908513321516$.
Методы приближённого нахождения и скорость сходимости
1) Метод дихотомии (bisection)
- Требует начального интервала $[a,b]$ с $f(a)f(b)<0$ (например $[0,1]$).
- Итерация: делить интервал пополам, выбирать подпериод, где смена знака.
- Сходимость линейная: погрешность после $n$ шагов $\le (b-a)2^{-n}$. Для точности $\epsilon$ нужно примерно $n\ge \lceil {\log }_2((b-a)/\epsilon )\rceil$.
2) Простая итерация (метод неподвижной точки) $x_{n+1}=g(x_n)$ с $g(x)=\cos x$ - Поскольку $|g^{\prime }(x)|=|\sin x|\le \sin 1\approx 0.84147<1$ на $[-1,1]$, оператор является сжатием на этом отрезке. Так как $\cos$ переводит любую точку в $[-1,1]$, для любого начального $x_0\in \mathbb{R}$ последовательность сходится к $\alpha$.
- Сходимость линейная. Асимпт. множитель сходимости вблизи корня равен $|g^{\prime }(\alpha )|=|\sin \alpha |\approx 0.673612$. Ошибка приблизительно убывает как $e_{n+1}\approx |\sin \alpha |e_n$.
- Прост в реализации, но медленнее Ньтона.
3) Метод Ньютона для $h(x)=\cos x-x$ - Итерация
$$x_{n+1}=x_n-\frac{\cos x_n-x_n}{-\sin x_n-1}=x_n+\frac{\cos x_n-x_n}{1+\sin x_n}.$$ - При достаточном приближении к $\alpha$ сходимость квадратичная: $e_{n+1}\approx C{e}_n^2$, где
$$C=\frac{h^{\prime \prime }(\alpha )}{2h^{\prime }(\alpha )}=\frac{\cos \alpha }{2(1+\sin \alpha )}.$$ Используя $\cos \alpha =\alpha$ получаем численно $C\approx 0.2208$. Значит при малой ошибке число верных цифр примерно удваивается за шаг.
- Требует вычисления $\sin x_n$ и $\cos x_n$ и хорошего начального приближения; возможны проблемы при делении на малое $1+\sin x_n$ (в нашем случае $1+\sin \alpha$ не мал).
4) Секущая и другие методы
- Секущая: не требует производной, порядок сходимости $\approx 1.618$ (суперлинейный).
- Aitken/экстраполяция могут ускорить линейную итерацию.
Практические замечания и оценки
- Для быстрой и надёжной процедуры: можно начать с нескольких шагов дихотомии, затем переключиться на Ньютон. Альтернатива — прямо итерация $x_{n+1}=\cos x_n$, она гарантированно сходится и простая, но медленнее.
- Оценки числа итераций: для простой итерации с коэффициентом сходимости $r$ требуемое число шагов для достижения погрешности $\epsilon$ примерно
$$n\gtrsim \frac{\ln (\epsilon /|e_0|)}{\ln r}.$$ Для Нютона при квадратичной сходимости число итераций растёт как ${\log }_2{\log }_{1/C}(1/\epsilon )$ (ошибки квадратно уменьшаются).
Кратко: единственный корень $\alpha \in (0,1)$, итерация $x_{n+1}=\cos x_n$ даёт простую гарантию с линейной сходимостью (коэффициент около $0.67$ вблизи корня), Ньютон даёт квадратичную сходимость (константа ~$0.221$), дихотомия — надёжна с линейной скоростью $1/2$ на шаг.