C LANGUAGE TECHNOLOGY

【C言語】二分法とニュートン法の違い

悩んでいる人

二分法とニュートン法の違いと,C言語によるコードを教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

二分法とニュートン法の違い

数値微分の手法としてよく知られている二分法ニュートン法の違いを説明します.

二分法は,解を含む区間の中間点を求める操作を繰り返すことで方程式を解く反復法による求根アルゴリズムです.

二分法は1次収束なので収束(Convergent)までが遅いですが,方程式が連続かつ関数値の符号が異なる初期値を設定すれば必ず収束します.

ニュートン法は,方程式系を数値計算によって解くための反復法による求根アルゴリズムです.

ニュートン法は2次収束なので収束までが二分法より速いです.

また,ニュートン法の収束の必要条件は方程式が連続かつ微分可能なことですが,初期値の設定により収束しない場合があります.

C言語による二分法のコード

C言語による二分法とニュートン法のコードは以下になります.

\(f(x) = x^2 - 2\)なので\(\sqrt{2}\)に収束します.

関数値の符号が異なる初期値の設定のために,30~34行目でdo-while文を利用しています.

もし関数値の符号が同じ初期値に設定された場合,再度初期値を入力します.

実行結果は以下になります.

\(\sqrt{2} \simeq 1.414...\)に収束する様子がわかります.

C言語によるニュートン法のコード

C言語によるニュートン法のコードは以下になります.

二分法のコードと同様に\(f(x) = x^2 - 2\)なので\(\sqrt{2}\)に収束します.

実行結果は以下になります.

二分法と比較して少ない反復数(ループの回数)で\(\sqrt{2}\)に収束していることがわかります.

初期値を-2に設定した場合は\(\sqrt{2}\)に収束せず,\(-\sqrt{2}\)に収束してしまいます.

二分法とは異なり,ニュートン法は初期値の設定により収束しない場合がありますので注意しましょう.

ニュートン法で間違って収束した例は以下になります.

まとめ

二分法とニュートン法の違いと,C言語によるコードを紹介しました.

どちらも有用ですので,うまく使い分けましょう!

二分法とニュートン法の比較は下表になります.

項目二分法ニュートン法
収束(求根)の速さ遅い(1次収束)速い(2次収束)
収束条件方程式が連続かつ
関数値の符号が異なる初期値の設定
方程式が連続かつ微分可能(必要条件)
※初期値の設定により収束しない場合あり

数値微分の一般論を知りたいあなたはこちらからどうぞ.

C言語 数値微分
【C言語】数値微分とは【前進差分,後退差分,中心差分,常微分方程式,オイラー法,3次テイラー展開,4次ルンゲクッタ法】

こういった悩みにお答えします. こういった私から学べます. 目次1 数値微分2 C言語で数値微分:前進差分,後退差分,中心差分3 常微分方程式4 C言語で常微分方程式:オイラー法,3次テイラー展開,4 ...

続きを見る

数値解析した結果をグラフで表示する時は,gnuplotがおすすめです.

C言語 gnuplot
【C言語】gnuplotでグラフ作成

こういった悩みにお答えします. こういった私から学べます. 目次1 gnuplot2 C言語からgnuplotでグラフ作成3 gnuplotでsin関数のグラフ作成3.1 gnuplotの標準関数にあ ...

続きを見る

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

友だち追加

独学が難しいあなたは,C言語を学べるおすすめのオンラインプログラミングスクール4社で自分に合うスクールを見つけましょう.

-C LANGUAGE, TECHNOLOGY
-, , , ,