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

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

「水曜日」シーズン1の中心には大きなミステリーがあります

「水曜日」シーズン1の中心には大きなミステリーがあります

Netflixの「水曜日」は、典型的な10代のドラマ以上のものであり、実際、シーズン1にはその中心に大きなミステリーがあります.

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ケイト・ミドルトンは、州の夕食会と州の訪問中にカミラ・パーカー・ボウルズからスポットライトを奪いたくなかった、と専門家は言う.

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンが、オリビア・ワイルドが彼女とハリー・スタイルズとの間の「難しい」が「非常に友好的」な分割を恒久的にすることを望んでいる理由を見つけてください.

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする 

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする&nbsp;

エリザベス女王の死後、ケイト・ミドルトンが舞台裏で「非常に困難な時期」を過ごしていたと伝えられている理由を調べてください.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

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

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

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

HMSプリンスオブウェールズの橋はスターウォーズからまっすぐです

HMSプリンスオブウェールズの橋はスターウォーズからまっすぐです

BAE Systems Maritimeは昨日、英国海軍の2番目のクイーンエリザベスクラスの空母であるHMSプリンスオブウェールズのブリッジモジュールを展開しました。公海を航海するよりも、アウターリムの惑星を周回してタイファイターを発射する必要があるようです。70,000の排水量のトン運搬船は、2020年に就役し、姉のエリザベス女王と同様に、約40機の航空機を運ぶ予定です。

ルイビルはサヨナラゲームでウェイクフォレストを倒すために家を盗んだ

ルイビルはサヨナラゲームでウェイクフォレストを倒すために家を盗んだ

ルイビルは、通常の大学野球の強みであるピッチング、ディフェンス、スマートベースランニングを通じて、全国ランキングのトップ5と19-2の会議記録への道を歩みました。昨夜、彼らは野球の最もエキサイティングなプレーの1つである盗塁を使用して、ウェイクフォレストのスイープを完了しました。

おいしいツイストのためにコーンブレッドであなたの次のサンドイッチを作りましょう

おいしいツイストのためにコーンブレッドであなたの次のサンドイッチを作りましょう

粗いパン粉とふわふわの食感のコーンブレッドは、唐辛子を吸い上げるのに理想的な乗り物です。しかし、それだけではありません。

別の驚くべきマーベルヒーローがキャプテンアメリカに参加します:シビルウォー!

別の驚くべきマーベルヒーローがキャプテンアメリカに参加します:シビルウォー!

ニール・ブロムカンプが、チャッピーが第10地区をどのように遅らせたのかについて話します。フォースの覚醒の噂は、次の予告編に何を期待するかについてのいじめを提供します。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

ホームオフィスのセットアップ術を極めよう!AppExert の開発者は、家族全員が一緒にいる場合でも、在宅勤務の技術を習得しています。祖父や曽祖父が共同家族で暮らしていた頃の記憶がよみがえりました。

2022 年、私たちのデジタル ライフはどこで終わり、「リアル ライフ」はどこから始まるのでしょうか?

20 年前のタイムトラベラーでさえ、日常生活におけるデジタルおよびインターネットベースのサービスの重要性に驚くことでしょう。MySpace、eBay、Napster などのプラットフォームは、高速化に焦点を合わせた世界がどのようなものになるかを示してくれました。

ニューロマーケティングの秘密科学

ニューロマーケティングの秘密科学

マーケティング担当者が人間の欲望を操作するために使用する、最先端の (気味が悪いと言う人もいます) メソッドを探ります。カートをいっぱいにして 3 桁の領収書を持って店を出る前に、ほんの数点の商品を買いに行ったことはありませんか? あなたは一人じゃない。

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

私たちが住んでいる世界を確実に理解するには、データが必要です。ただし、空間参照がない場合、このデータは地理的コンテキストがないと役に立たなくなる可能性があります。

Language