一次元におけるニュートン法のグローバル収束:オーバーシュートの数

2
Daniel S. 2020-04-16 17:26.

のルーツを見つける問題を考えてみましょう $f(x)$。単一のルートがあると仮定します$x_*$ の間に $a$ そして $b$$a < x_* < b$

また、の兆候を仮定します $f''(x)$ のために変更されません $x \in [a,b]$

よく知られている $f(a) f''(a) > 0$次に、ニュートン法はオーバーシュートなしで解に収束します。たとえば、を参照してください。https://en.wikipedia.org/wiki/Newton%27s_method#Analysis そして ニュートン反復は単調に収束します[閉じた]

さて、もしも $f(a) f''(a) < 0$

ニュートン近似法が最初の反復で正確に発生する単一のオーバーシュートの後に収束することをどのような条件下で確立できますか?

聞かせ 始める\ {式} X_ {N + 1} = x_nに関する- \ FRAC {F(x_nに関する)} {F '(x_nに関する)} \端{式}$x_0=a$\ begin {equation} x_ {1} = a- \ frac {f(a)} {f '(a)} \ end {equation}

どのような条件下で $x_1 > x_*$ そして $f(x_1) f''(x_1) > 0$

この質問はフォローアップです ニュートン法の収束に関するダルブーの定理

定理や洞察を参照すると非常に役立ちます。特に、次の論文から上記の質問に対する答えを抽出することができませんでした

「Surlaméthoded'approximationdeNewton」、Nouvelles annalesdemathématiques:journal descandidatsauxécolespolytechniqueetnormale、serie 2、vol 8(1869)、pp.17-27

具体例

しましょう $0 < p < 1$ そして $0.5 < q < 1$。仮定 {ALIGN}開始\&F(X)=(8(Q-0.5)^ 2 {P} ^ 3 +( - 34(Q-0.5)^ 2から1.5){P} ^ 2 + \ NONUMBER \\& \ quad \ quad \ quad +(40(q-0.5)^ 2 + 6)p-16(q-0.5)^ 2-4)/(p-2)^ 2。\ label {eq:cubic2} \ end {align} 検索します$x_*$ そのような $f(x_*)=0$

次に、 $x_* \approx x_1$\ begin {align} x_ *&\ approx x_1 \\&= x_0- \ frac {f(x_0)} {f '(x_0)} \\&= 0.845 + \ frac {1.23688 q ^ 2-1.23688 q + 0.31} {-2.38422 q ^ 2 + 2.38422 q + 2} \ label {eq:pstarf} \ end {align} ここで、$x_0=0.845$

それを示すのは簡単です $x_0 < x_* \leq 1$

どうすればそれを示すことができますか $x_1 > x_*$ ニュートン近似法のグローバル収束の一般的な特性を使用していますか?

追記

明らかに、のルート $f(x)$ のルートと同じです $g(x)$\ begin {align}&g(x)=(8(q-0.5)^ 2 {p} ^ 3 +(-34(q-0.5)^ 2-1.5){p} ^ 2 + \ nonumber \\& \ quad \ quad \ quad +(40(q-0.5)^ 2 + 6)p-16(q-0.5)^ 2-4)。\ end {align} 次に、 \ begin {align} x _ *&\ approx x_0- \ frac {g(x_0)} {g '(x_0)} \\&= 0.845- \ frac {1.650041(q --0.5)^ 2 + 0.0010375} {0.3234(q --0.5)^ 2 --3.465} \ end {align} ここで、$x_0=0.845$。ただし、ニュートン近似の収束は、$g(x)$ より $f(x)$。それでも、$g(x)$ NAMがオーバーシュートすることは決してないことを私たちは知っていました。 $g(x_0) g''(x_0) > 0$。理由/場合を事前に確認する方法はありますか$f(x)$ ニュートン近似の最良の入力は $g(x)$ 収束時間に関しては、しかしそれは $g(x)$ オーバーシュートの数に関しては最高ですか?

1 answers

2
Claude Leibovici 2020-04-18 18:39.

これはコメントするには長すぎます。

問題を簡単にするために、定義しましょう $k=\left(q-\frac{1}{2}\right)^2$ これは $$g(p)=8 k p^3-\frac{68 k+3}{2} p^2+2(20 k+3) p-4 (4 k+1)$$ どこ $0 \leq k \leq \frac 14$

あなたが示したように、 $g(p)\,g''(p) \geq 0$ のために $ p_0 \geq 2-\frac{2}{\sqrt{3}}$ (あなたの論文のタイプミス-どの方程式を見てください $(32)$与える)。したがって、ダルブーの定理により、ニュートンの反復を$p_0$ソリューションへのパス中にオーバーシュートすることなく収束を保証します。しかし、これはそれを意味するものではありません$p_0$ 最良の出発点です。

とにかく、それを使って、 $$p_1=2-\frac{2}{\sqrt{3}}-\frac{\left(48-32 \sqrt{3}\right) k}{\left(144-84 \sqrt{3}\right) k+9 \sqrt{3}}\,\, > p_0\qquad \forall \, 0 \leq k \leq \frac 14$$

で始まります $p_0=2-\frac{2}{\sqrt{3}}$、これは、オーバーシュートに気付かない最初の反復の結果です。 $$\left( \begin{array}{cccccc} k & p_1 & p_2 & p_3 & p_4 & \text{solution} \\ 0.00 & 0.845299 & 0.845299 & 0.845299 & 0.845299 & 0.845299 \\ 0.01 & 0.850068 & 0.850078 & 0.850078 & 0.850078 & 0.850078 \\ 0.02 & 0.854845 & 0.854892 & 0.854892 & 0.854892 & 0.854892 \\ 0.03 & 0.859631 & 0.859747 & 0.859747 & 0.859747 & 0.859747 \\ 0.04 & 0.864427 & 0.864648 & 0.864648 & 0.864648 & 0.864648 \\ 0.05 & 0.869232 & 0.869604 & 0.869605 & 0.869605 & 0.869605 \\ 0.06 & 0.874046 & 0.874622 & 0.874622 & 0.874622 & 0.874622 \\ 0.07 & 0.878869 & 0.879709 & 0.879709 & 0.879709 & 0.879709 \\ 0.08 & 0.883702 & 0.884872 & 0.884874 & 0.884874 & 0.884874 \\ 0.09 & 0.888544 & 0.890123 & 0.890125 & 0.890125 & 0.890125 \\ 0.10 & 0.893395 & 0.895469 & 0.895473 & 0.895473 & 0.895473 \\ 0.11 & 0.898256 & 0.900921 & 0.900928 & 0.900928 & 0.900928 \\ 0.12 & 0.903126 & 0.906492 & 0.906503 & 0.906503 & 0.906503 \\ 0.13 & 0.908006 & 0.912193 & 0.912211 & 0.912211 & 0.912211 \\ 0.14 & 0.912895 & 0.918038 & 0.918067 & 0.918067 & 0.918067 \\ 0.15 & 0.917794 & 0.924044 & 0.924089 & 0.924089 & 0.924089 \\ 0.16 & 0.922702 & 0.930227 & 0.930295 & 0.930295 & 0.930295 \\ 0.17 & 0.927619 & 0.936606 & 0.936708 & 0.936708 & 0.936708 \\ 0.18 & 0.932547 & 0.943203 & 0.943355 & 0.943355 & 0.943355 \\ 0.19 & 0.937483 & 0.950043 & 0.950266 & 0.950266 & 0.950266 \\ 0.20 & 0.942430 & 0.957153 & 0.957478 & 0.957478 & 0.957478 \\ 0.21 & 0.947386 & 0.964566 & 0.965034 & 0.965034 & 0.965034 \\ 0.22 & 0.952352 & 0.972317 & 0.972987 & 0.972988 & 0.972988 \\ 0.23 & 0.957328 & 0.980448 & 0.981405 & 0.981407 & 0.981407 \\ 0.24 & 0.962313 & 0.989008 & 0.990371 & 0.990374 & 0.990374 \\ 0.25 & 0.967308 & 0.998053 & 0.999992 & 1.000000 & 1.000000 \end{array} \right)$$

いずれにせよ、開始点の非常に優れた(理論に基づいた)推定値を生成することが可能です。書く $$\color{blue}{p_0=\frac{\sum_{n=0}^4 a_n\,k^n } {\sum_{n=0}^4 b_n\,k^n }}$$ どこ $$\left( \begin{array}{ccc} n & a_n & b_n \\ 0 & 1458 \left(-3+\sqrt{3}\right) & -2187 \\ 1 & -1944 \left(-113+65 \sqrt{3}\right) & 2916 \left(25-14 \sqrt{3}\right) \\ 2 & 1728 \left(-2817+1630 \sqrt{3}\right) & 2592 \left(-638+371 \sqrt{3}\right) \\ 3 & 1152 \left(38303-22115 \sqrt{3}\right) & 576 \left(27345-15794 \sqrt{3}\right) \\ 4 & 512 \left(-262761+151697 \sqrt{3}\right) & 768 \left(-66129+38174 \sqrt{3}\right) \end{array} \right)$$ これを使う $p_0$、以下の表は最初の反復を再現しています $p_1$ ニュートン法と解法の $$\left( \begin{array}{cccc} k & p_0 & p_1 & \text{solution} \\ 0.00 & 0.845299 & 0.845299 & 0.845299 \\ 0.01 & 0.850078 & 0.850078 & 0.850078 \\ 0.02 & 0.854892 & 0.854892 & 0.854892 \\ 0.03 & 0.859747 & 0.859747 & 0.859747 \\ 0.04 & 0.864648 & 0.864648 & 0.864648 \\ 0.05 & 0.869605 & 0.869605 & 0.869605 \\ 0.06 & 0.874622 & 0.874622 & 0.874622 \\ 0.07 & 0.879709 & 0.879709 & 0.879709 \\ 0.08 & 0.884874 & 0.884874 & 0.884874 \\ 0.09 & 0.890125 & 0.890125 & 0.890125 \\ 0.10 & 0.895473 & 0.895473 & 0.895473 \\ 0.11 & 0.900928 & 0.900928 & 0.900928 \\ 0.12 & 0.906503 & 0.906503 & 0.906503 \\ 0.13 & 0.912211 & 0.912211 & 0.912211 \\ 0.14 & 0.918067 & 0.918067 & 0.918067 \\ 0.15 & 0.924088 & 0.924089 & 0.924089 \\ 0.16 & 0.930294 & 0.930295 & 0.930295 \\ 0.17 & 0.936706 & 0.936708 & 0.936708 \\ 0.18 & 0.943351 & 0.943355 & 0.943355 \\ 0.19 & 0.950259 & 0.950266 & 0.950266 \\ 0.20 & 0.957465 & 0.957478 & 0.957478 \\ 0.21 & 0.965012 & 0.965034 & 0.965034 \\ 0.22 & 0.972951 & 0.972988 & 0.972988 \\ 0.23 & 0.981343 & 0.981407 & 0.981407 \\ 0.24 & 0.990265 & 0.990374 & 0.990374 \\ 0.25 & 0.999813 & 1.000000 & 1.000000 \end{array} \right)$$

つまり、1回の反復が必要です。新しいものの拡張の程度をさらに増やすことができます$p_0$

Related questions

MORE COOL STUFF

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは、夫に会ったとき、典型的な交際のアドバイスに逆らいました。

マイケルシーンが非営利の俳優である理由

マイケルシーンが非営利の俳優である理由

マイケルシーンは非営利の俳優ですが、それは正確にはどういう意味ですか?

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

特徴的なスターのコリン・エッグレスフィールドは、RomaDrama Liveでのスリル満点のファンとの出会いについて料理しました!加えて、大会での彼のINSPIREプログラム。

「たどりつけば」をオンラインでストリーミングできない理由

「たどりつけば」をオンラインでストリーミングできない理由

ノーザンエクスポージャーが90年代の最も人気のある番組の1つになった理由を確認するには、Blu-rayまたはDVDプレーヤーをほこりで払う必要があります。

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖は、世界で2番目に大きいボイリング湖です。そこにたどり着くまでのトレッキングは大変で長いですが、努力する価値は十分にあります。

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

サロンからのヘアトリミングや個人的な寄付は、油流出を吸収して環境を保護するのに役立つマットとして再利用できます。

ホワイトハウスの最も記憶に残る結婚式を見てください

ホワイトハウスの最も記憶に残る結婚式を見てください

過去200年以上の間にホワイトハウスで結婚したのはほんの数人です。彼らは誰でしたか、そしてそこで結婚式を獲得するために何が必要ですか?

Netflixのジョエルマクヘイルとのジョエルマクヘイルショーは、ジョエルマクヘイルにぴったりの車を復活させます

Netflixのジョエルマクヘイルとのジョエルマクヘイルショーは、ジョエルマクヘイルにぴったりの車を復活させます

ジョエル・マクヘイル、マイク・コルター(スクリーンショット:Netflix)「私の神よ、これは1つのことを変えます。」これは、ジョエル・マクヘイルとのジョエル・マクヘイルショーの最後のジョークです。リアリティ番組の嘲笑と寛大なスナキネスの時間は、なじみのある顔を見つけます。

チームロケットは20年ぶりにポケモンシリーズでアッシュを破った

チームロケットは20年ぶりにポケモンシリーズでアッシュを破った

画像経由:@pancakeparadox(Twitter)。1997年にポケモンシリーズが初公開されて以来、チームロケット(またはラテンアメリカではチームロケット)として知られる悪役のグループは、何度もアッシュに直面してきました。

今週の科学技術でトランプがめちゃくちゃになったことすべて

今週の科学技術でトランプがめちゃくちゃになったことすべて

画像:ゲッティ私たち全員が千年もの間生きていて、私たちの体が燃える風によってほこりと長引く悲鳴だけに押し流されたと考えるのは驚くべきことです。私たちがそうしていないことを除いて、それはトランプ政権の最初の週の終わりであり、驚くほど多くの恐ろしいことがすでに起こっています。

あなたの「マイクロピッグ」が代わりに通常のピッグになってしまったとしても驚かないでください

あなたの「マイクロピッグ」が代わりに通常のピッグになってしまったとしても驚かないでください

そして今、あることを手に入れていると思っていたが、まったく別のことをしてしまった男の話。CBSニュースは、彼女が「ミニブタ」であるという誤ったふりをしてエスターを養子にしたカナダ人のスティーブジェンキンスの心温まる物語をもたらします。これは、特にせいぜいゴールデンレトリバーまたはセントバーナードをストラップします。

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya shared a sweet photo in honor of boyfriend Tom Holland's 26th birthday Wednesday

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

シーレン「Ms.JuicyBaby」ピアソンは、先月脳卒中で入院した後、「もう一度たくさんのことをする方法を学ばなければならない」ため、言語療法を受けていることを明らかにしました。

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

オスカー受賞者の世紀半ばの家には、3つのベッドルーム、2つのバス、オーシャンフロントの景色があります。

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、生後4か月の娘、モナコに母乳育児をしていると語った。

投資ノート:Bioscout AU$300万シード

投資ノート:Bioscout AU$300万シード

Bioscoutは、農家を運転席に置くという使命を負っています。Artesian(GrainInnovate)やUniseedと並んで、最新のシードラウンドでチームを支援できることをうれしく思います。問題真菌症による重大な作物の損失は、農民にとって試練であることが証明されています。

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

遠隔医療は、パンデミック後の時代では新しいものではなく、時代遅れの分野でもありません。しかし、業界を詳しく見ると、需要と供給の強力な持続可能性と、米国で絶え間ない革命となる強力な潜在的成長曲線を示しています。

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

2021年は、世界的なベンチャーキャピタル(VC)の資金調達にとって記録的な年でした。DealStreetAsiaによると、東南アジアも例外ではなく、この地域では年間で記録的な25の新しいユニコーンが採掘されました。

ムーアの法則を超えて

ムーアの法則を超えて

計算に対する私たちの欲求とムーアの法則が提供できるものとの間には、指数関数的に増大するギャップがあります。私たちの文明は計算に基づいています—建築と想像力の現在の限界を超える技術を見つけなければなりません。

Language