の根を見つけるための反復回数 $x^3+2x-54$ ニュートン法を使用する
ルートを見つけるために必要な（理論上の）最小反復回数を計算するように求められます $\alpha$ の $x^3+2x-54$ ニュートン法を使用して、より少ない絶対誤差を保証します $10^{-8}$、および間隔から開始 $I$ そして $x_0$ 私の選挙の。
ルートを検索しました $I=[3,4]$、と $x_0=3.5$（実際にはルートに非常に近いです）。私は2つの方法で反復回数を見つけようとしました：
最初のオプション。ここでは、の値を知る必要があります$\alpha$。要求された分析は理論的であるため、これは罪ではないと思います。Wolframを使って、$\alpha\approx3.60$。ウィキペディアで検索すると、$|e_{n+1}|\leq M|e_n|^2$、 どこ $M=\sup_{x\in I}\frac{1}{2}|\frac{f''(x)}{f'(x)}|$ そして $|e_k|=|x_k-\alpha|$。
この場合、 $M=\frac{1}{2}|\frac{6\cdot3}{3\cdot3^2+2}|=0.310$
$$|e_n|\leq M^{\sum_{i=0}^{n-1}2^i}|e_o|^{2^n}=0.31^{2^n-1}|3.5-\alpha|^{2^n}\approx0.31^{2^n-1}\cdot0.1^{2^n}$$
必要に応じて $|e_n|<10^{-8}$、その後 $$(0.31\cdot0.1)^{2^n}<10^{-8}\cdot0.31\to2^n>\frac{\log(10^{-8}\cdot0.31)}{\log(0.031)}\to n>\frac{\log(\frac{\log(10^{-8}\cdot0.31)}{\log(0.031)})}{\log(2)}\approx2.5$$
したがって、最低でも必要です $3$ 反復。
2番目のオプション。ここに示す方法を使用します。$N(x)=x-\frac{f(x)}{f'(x)}\implies f(N(x))=\frac12f''(\tilde x)\frac{f(x)^2}{f'(x)^2}$
なので $\max_{x\in I}|f''(x)|=24$、 $\min_{x\in I}|f'(x)|=29$、その後 $$|f(N(x))|\leq\frac{12}{29^2}|f(x)|^2\to|f(x_n)|\leq(\frac{12}{29^2})^{\sum_{i=0}^{n-1}2^i}|f(x_0)|^{2^n}$$
$|f(x_0)|=|f(3.5)|\approx3.70$、およびとして $|x-\alpha|\leq0.31|f(x)|$、そして私たちは欲しい $|x_n-\alpha|<10^{-8}$：
$$0.31(\frac{12}{29^2})^{2^n-1}\cdot3.7^{2^n}<10^{-8}\to(\frac{12\cdot3.7}{29^2})^{2^n}<\frac{10^{-8}\cdot12}{0.31\cdot29^2}\to0.0528^{2^n}<0.046\cdot10^{-8}\to$$ $$\to n>\frac{\log(\frac{\log(0.046\cdot10^{-8})}{\log(0.0528)})}{\log(2)}\approx2.87$$
したがって、最低でも必要です $3$ 反復。
私の手順が間違っていない場合、両方の方法で同じ回数の反復が行われます（丸められた後）。最初のものは、おそらく私たちがの値を使用するという事実のために、よりタイトです$\alpha$。私は正しいですか？理論的な観点から、最初のアプローチと2番目のアプローチのどちらを使用する方がよいでしょうか。
回答
ニュートン-カントロビッチの定理を証明するためのラインボルト-オルテガ戦略は、ニュートン法の収束が $f(x)=0$ 二次多項式のニュートン法の収束によって主になります $$0=p(t)=\frac{L}2t^2-|f'(x_0)|t+|f(x_0)|=\frac{L}2(t-t^*)(t-t^{**}),$$ から $t_0=0$ その小さな根に向かって $t^*$。 $L$ 周囲の十分な大きさの近傍の2階微分の限界 $x_0$、 $|f'(x_0)|$ に置き換えられます $\|f'(x_0)^{-1}\|^{-1}$システムとそのヤコビ行列用。これは、何よりも、反復に対して関係を取得することを意味します$$ |x_{k+1}-x_k|\le t_{k+1}-t_k $$
ここであなたは得る $L=24$、 $f(x_0)=-4.125$、 $f'(3.5)=38.75$、そのため、根は $t^{**}=3.11895341$、 $t^{*}=0.11021325$。の収束のために$t_k$ シーケンス1は良い関係を得る $$ \theta_{k+1}=\frac{t_{k+1}-t^*}{t_{k+1}-t^{**}} =\frac{p'(t_k)(t_k-t^*)-p(t_k)}{p'(t_k)(t_k-t^{**})-p(t_k)} =\frac{t_k-t^*}{t_k-t^{**}}\frac{2t_k-(t^*+t^{**})-(t_k-t^{**})}{2t_k-(t^*+t^{**})-(t_k-t^{*})}=\theta_k^2 $$ そのため $$ t_k=\frac{t^*-θ_0^{2^k}t^{**}}{1-θ_0^{2^k}},~~θ_0=\frac{t^*}{t^{**}}, ~~t^*-t_k=\frac{θ_0^{2^k}(t^{**}-t^*)}{1-θ_0^{2^k}} $$ 取得するため $|x_k-x^*|\le t^*-t_k\le 10^{-8}$ およそ必要になるでしょう $$ 2^k\ge \frac{\ln(10^{-8})-\ln(t^{**}-t^*)}{\ln(θ_0)}=5.840012=2^{2.55} $$ これもまた $k=3$ 答えとして。