二分法とニュートン法の違いと，C言語によるコードを教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
目次
二分法とニュートン法の違い
数値微分の手法としてよく知られている二分法とニュートン法の違いを説明します．
二分法は，解を含む区間の中間点を求める操作を繰り返すことで方程式を解く反復法による求根アルゴリズムです．
二分法は1次収束なので収束（Convergent）までが遅いですが，方程式が連続かつ関数値の符号が異なる初期値を設定すれば必ず収束します．
ニュートン法は，方程式系を数値計算によって解くための反復法による求根アルゴリズムです．
ニュートン法は2次収束なので収束までが二分法より速いです．
また，ニュートン法の収束の必要条件は方程式が連続かつ微分可能なことですが，初期値の設定により収束しない場合があります．
C言語による二分法のコード
C言語による二分法とニュートン法のコードは以下になります．
\(f(x) = x^2 - 2\)なので\(\sqrt{2}\)に収束します．
関数値の符号が異なる初期値の設定のために，30～34行目でdo-while文を利用しています．
もし関数値の符号が同じ初期値に設定された場合，再度初期値を入力します．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <math.h> #define NR_ITERATIONS 100 #define TOLERANCE 0.0000000001 #define issamesign(x, y) (((x) > 0) == ((y) > 0)) /* * Please set your f(x). * This example is f(x) = x^2 - 2 */ double fx(double x) { return x * x - 2; } int main(void) { double x1; double x2; double xm; double xmprev; int i; do { printf("Please input two initial values: "); scanf("%lf%lf", &x1, &x2); } while (issamesign(fx(x1), fx(x2))); /* check if fx(x1) and fx(x2) are the same sign. */ for (i = 0; i < NR_ITERATIONS; i++) { xm = (x1 + x2) / 2; if (issamesign(fx(xm), fx(x1))) { x1 = xm; } else { x2 = xm; } printf("%.15lf\n", xm); /* Is f(x) convergent? */ if (fabs(xm - xmprev) < TOLERANCE) { break; } xmprev = xm; } if (i < NR_ITERATIONS) { printf("Convergent\n"); } else { printf("Divergent\n"); } return 0; } |
実行結果は以下になります．
\(\sqrt{2} \simeq 1.414...\)に収束する様子がわかります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
$ gcc bisection_method.c $ a.out Please input two initial values: 0 2 1.000000000000000 1.500000000000000 1.250000000000000 1.375000000000000 1.437500000000000 1.406250000000000 1.421875000000000 1.414062500000000 1.417968750000000 1.416015625000000 1.415039062500000 1.414550781250000 1.414306640625000 1.414184570312500 1.414245605468750 1.414215087890625 1.414199829101562 1.414207458496094 1.414211273193359 1.414213180541992 1.414214134216309 1.414213657379150 1.414213418960571 1.414213538169861 1.414213597774506 1.414213567972183 1.414213553071022 1.414213560521603 1.414213564246893 1.414213562384248 1.414213561452925 1.414213561918586 1.414213562151417 1.414213562267832 1.414213562326040 Convergent |
C言語によるニュートン法のコード
C言語によるニュートン法のコードは以下になります．
二分法のコードと同様に\(f(x) = x^2 - 2\)なので\(\sqrt{2}\)に収束します．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <math.h> #define NR_ITERATIONS 100 #define TOLERANCE 0.0000000001 /* * Please set your f(x). * This example is f(x) = x^2 - 2 */ double fx(double x) { return x * x - 2; } int main(void) { double x; double f; double df; double dx = 0.00001; int i; printf("Please input an initial value: "); scanf("%lf", &x); /* Newton's Method. */ for (i = 0; i < NR_ITERATIONS; i++) { f = fx(x); df = (fx(x + dx) - fx(x - dx)) / (2 * dx); x -= f / df; printf("%.15lf\n", x); /* Is f(x) convergent? */ if (fabs(f / df) < TOLERANCE) { break; } } if (i < NR_ITERATIONS) { printf("Convergent\n"); } else { printf("Divergent\n"); } return 0; } |
実行結果は以下になります．
二分法と比較して少ない反復数（ループの回数）で\(\sqrt{2}\)に収束していることがわかります．
|
1 2 3 4 5 6 7 8 9 |
$ gcc newton_method.c $ a.out Please input an initial value: 2 1.500000000003276 1.416666666667213 1.414215686274526 1.414213562374690 1.414213562373095 Convergent |
初期値を-2に設定した場合は\(\sqrt{2}\)に収束せず，\(-\sqrt{2}\)に収束してしまいます．
二分法とは異なり，ニュートン法は初期値の設定により収束しない場合がありますので注意しましょう．
ニュートン法で間違って収束した例は以下になります．
|
1 2 3 4 5 6 7 8 9 |
$ gcc newton_method.c $ a.out Please input an initial value: -2 -1.500000000003276 -1.416666666667213 -1.414215686274526 -1.414213562374690 -1.414213562373095 Convergent |
まとめ
二分法とニュートン法の違いと，C言語によるコードを紹介しました．
どちらも有用ですので，うまく使い分けましょう！
二分法とニュートン法の比較は下表になります．
| 項目 | 二分法 | ニュートン法 |
|---|---|---|
| 収束（求根）の速さ | 遅い（1次収束） | 速い（2次収束） |
| 収束条件 | 方程式が連続かつ 関数値の符号が異なる初期値の設定 | 方程式が連続かつ微分可能（必要条件） ※初期値の設定により収束しない場合あり |
数値微分の一般論を知りたいあなたはこちらからどうぞ．
数値解析した結果をグラフで表示する時は，gnuplotがおすすめです．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
