루트를 찾을 반복 횟수 $x^3+2x-54$ 뉴턴의 방법 사용
루트를 찾는 데 필요한 (이론적) 최소 반복 횟수를 계산하라는 요청을 받았습니다. $\alpha$ 의 $x^3+2x-54$ Newton의 방법을 사용하여 다음보다 작은 절대 오차를 보장합니다. $10^{-8}$, 간격에서 시작 $I$ 과 $x_0$ 내 선거의.
나는 뿌리를 찾았다 $I=[3,4]$,와 함께 $x_0=3.5$(사실 루트에 매우 가깝습니다 ). 두 가지 방법으로 반복 횟수를 찾으려고했습니다.
첫 번째 옵션. 여기서 우리는$\alpha$. 요청 된 분석은 이론적이므로 이것이 죄가 아니라고 생각합니다. Wolfram을 사용하여$\alpha\approx3.60$. Wikipedia 에서 검색 한 결과$|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$ 반복.
두 번째 옵션. 여기에 표시된 방법을 사용합니다 .$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$. 내가 맞아? 이론적 관점에서 첫 번째 또는 두 번째 접근 방식을 사용하는 것이 더 낫습니까?
답변
Newton-Kantorovich 정리의 증명을위한 Rheinboldt-Ortega 전략은 Newton 방법의 수렴이 $f(x)=0$ 2 차 다항식에 대한 Newton 방법의 수렴에 의해 전공됩니다. $$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$ 주위에 충분히 큰 이웃에 대한 이차 미분의 경계입니다. $x_0$, $|f'(x_0)|$ 대체된다 $\|f'(x_0)^{-1}\|^{-1}$시스템 및 Jacobi 매트릭스 이것은 무엇보다도 반복을 위해 관계를 얻는다는 것을 의미합니다.$$ |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$ 대답으로.