2008年6月5日 非線形方程式の近似解 2分法,はさみうち法,Newton-Raphson法)

Slides:



Advertisements
Similar presentations
Absolute Orientation. Absolute Orientation の問題 二つの座標系の間における剛体 (rigid body) 変換を復元す る問題である。 例えば: 2 台のステレオカメラから得られた3次元情報の間の関 係を推定する問題。 2 台のステレオカメラから得られた3次元情報の間の関.
Advertisements

計測工学 10 データの補間 スプライン補間 1. . 復習 階差 近似多項式の次数 の決定法 等間隔階差 – 関数 y=f(x) で、 x の値 が等間隔の場合 等間隔: x 0, x 0 +h, x 0 +2h ・・・ y の値: y 0, y 1, y 2 ・・・ これらの階差は – 第1階差:
『わかりやすいパターン認 識』 第 5 章 特徴の評価とベイズ誤り確率 5.4 ベイズ誤り確率と最近傍決定則 発表日: 5 月 23 日(金) 発表者:時田 陽一.
3 一次関数 1章 一次関数とグラフ § 5 一次関数の利用 (4時間) §5 §5 一次関数の利用 サイクリングで京都から神戸まで行くことにした。 朝出発して、 9 時にはあと 90km の地点を通過した。 さらに進んでいくと、 13 時にはあと 30km の地点を 通過した。 このペースで進み続けると、神戸には何.
中学数学2年 3 章 一次関数 3 一次関数の利用 § 1 一次関数の利用 (4時間) §1 §1 一次関数の利用 サイクリングで京都から神戸まで行くことにした。 朝出発して、 9 時にはあと 90km の地点を通過した。 さらに進んでいくと、 13 時にはあと 30km の地点を 通過した。 このペースで進み続けると、神戸には何.
Problem C: Grated Radish ~大根おろし~. 成績 Submit 数: 0 Accept 数: 0 問題セットの中で最難問題なので解けな くても仕方が無いかなと思いつつ, 1 チー ム位 submit して欲しかった.
数値解析シラバス C言語環境と数値解析の概要(1 回) C言語環境と数値解析の概要(1 回) 方程式の根(1回) 方程式の根(1回) 連立一次方程式(2回) 連立一次方程式(2回) 補間と近似(2回) 補間と近似(2回) 数値積分(1回) 数値積分(1回) 中間試験(1回) 中間試験(1回) 常微分方程式(1回)
プログラムのパタン演習 解説.
有限差分法による 時間発展問題の解法の基礎
Fortran と有限差分法の 入門の入門の…
電子情報工学科5年(前期) 7回目(21/5/2015) 担当:古山彰一
プログラミング論 数値積分
プログラミング論 I 補間
数個、数十個のデータ点から その特徴をつかむ
演習00-0 “Hello,world![改行]”を表示するプログラムを作成せよ. 1 1.
解析的には解が得られない 方程式を数値的に求める。 例:3次方程式
一次関数のグラフ(式を求めること) 本時の流れ ねらい「グラフや座標など与えられた条件をもとに一次 関数の式を求める。」 ↓
一次関数のグラフ(式を求めること) 本時の流れ ねらい「グラフや座標など与えられた条件をもとに一次 関数の式を求める。」 ↓
プログラミング論 I 講義,テスト C言語復習
プログラミング演習I
3 一次関数 1章 一次関数とグラフ §3 一次関数の式を求めること          (3時間).
スペクトル法による数値計算の原理 -一次元線形・非線形移流問題の場合-
1 次方程式 直線   と 軸が交わる点 解ける! 解析的に解ける(解析解)   または 厳密に解ける (厳密解)
Scilab で学ぶ  わかりやすい数値計算法 舞鶴高専 電子制御工学科 川田 昌克.
シミュレーション論Ⅰ 第4回 基礎的なシミュレーション手法.
IT入門B2 ー 連立一次方程式 ー.
4.2 連立非線形方程式 (1)繰返し法による方法
プログラミング論 II 電卓,逆ポーランド記法電卓
数値解析シラバス C言語環境と数値解析の概要(1回) 方程式の根(1回) 連立一次方程式(2回) 補間と近似(2回) 数値積分(1回)
非線形方程式の近似解 (2分法,はさみうち法,Newton-Raphson法)
2008年6月12日 非線形方程式の近似解 Newton-Raphson法
最短路問題のための LMS(Levelwise Mesh Sparsification)
(ラプラス変換の復習) 教科書には相当する章はない
電気回路Ⅱ 演習 特別編(数学) 三角関数 オイラーの公式 微分積分 微分方程式 付録 三角関数関連の公式
第7回 条件による繰り返し.
スペクトル法の一部の基礎の初歩への はじめの一歩
数値積分.
プログラミング論 II 2008年吉日 主成分分析 数値積分
第10回関数 Ⅱ (ローカル変数とスコープ).
プログラミング演習I 行列計算と線形方程式の求解
LU分解を用いた連立一次方程式.
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
第7回 条件による繰り返し.
6. ラプラス変換.
12.数値微分と数値積分.
ルンゲクッタ法 となる微分方程式の解を数値的に解く方法.
電気回路学Ⅱ コミュニケーションネットワークコース 5セメ 山田 博仁.
原子動力工学特論 レポート1 交通電子機械工学専攻 齋藤 泰治.
高度プログラミング演習 (05).
高度プログラミング演習 (05).
プログラミング 4 探索と計算量.
復習 一定回数を繰り返す反復処理の考え方 「ループ」と呼ぶ false i < 3 true i をループ変数あるいはカウンタと呼ぶ
知識科学研究科 知識システム構築論講座 林研究室 佛明 智
計算機プログラミングI 第6回 2002年11月14日(木) アルゴリズムと計算量 第1回課題の説明 平方根を計算するアルゴリズム 計算量
わかりやすいパターン認識 第7章:部分空間法  7.1 部分空間法の基本  7.2 CLAFIC法                  6月13日(金)                  大城 亜里沙.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
22・3 積分形速度式 ◎ 速度式: 微分方程式 ⇒ 濃度を時間の関数として得るためには積分が必要
回帰分析(Regression Analysis)
22・3 積分形速度式 ◎ 速度式: 微分方程式 ⇒ 濃度を時間の関数として得るためには積分が必要
C言語復習 来週もこの資料を持参してください.
1.基本概念 2.母集団比率の区間推定 3.小標本の区間推定 4.標本の大きさの決定
13.ニュートン法.
ニュートン法による 非線型方程式の解.
 3 方程式 1章 方程式 §4 方程式の利用         (4時間).
Cプログラミング演習 ニュートン法による方程式の求解.
3 一次関数 1章 一次関数とグラフ §4 方程式とグラフ         (3時間).
PADのテンプレート 処理、連接 x0 ← x x ← x0+ u(x0) err ← |x - x0| 判断(選択) x2 ← x3
コンピュータの高速化により, 即座に計算できるようになってきたが, 手法的にはコンピュータ出現以前に考え出された 方法が数多く使われている。
プログラミング演習I 補講用課題
プログラミング論 バイナリーサーチ 1.
Presentation transcript:

2008年6月5日 非線形方程式の近似解 2分法,はさみうち法,Newton-Raphson法) プログラミング論 I 2008年6月5日 非線形方程式の近似解 2分法,はさみうち法,Newton-Raphson法) http://www.ns.kogakuin.ac.jp/~ct13140/Prog.2008

for文復習 for(i=0; i<3; i++){ printf("Hello\n"); printf("World\n"); }

for文復習 for(i=0; i<3; i++){ printf("%d\n", i); } i=0;

練習 0 下のプログラムの出力は? int i, j; for(i=0; i<3; i++){ for(j=0; j<2; j++){ printf("i=%d, j=%d\n", i, j); }

解答 0 i=0, j=0 i=0, j=1 i=1, j=0 i=1, j=1 i=2, j=0 i=2, j=1

練習 1 左のプログラムの出力は? a = 12; b = 7; if( a < 10 ){ printf("A\n"); if( b < 10 ){ printf("B\n"); } else { printf("C\n"); } printf("D\n"); printf("E\n"); printf("F\n"); 左のプログラムの出力は?

解答 1 D E F

概要 非線形方程式の近似解の求め方 2分法 はさみうち法 Newton-Raphson法)

非線形方程式の近似解 解析的に解けない非線形方程式の近似解を求める方法. 非線形方程式の多くは解析的に解けない. 解の候補を方程式に代入すれば解か否かは判断可能 計算機により「解の候補を代入する」ことを繰り返し,解を探していく.

非線形方程式の近似解 非線形方程式 f (x) = 0 の解を求める y = f (x) とし,x から y を求めるのは容易. 例 : f (x) = x4+ax3+bx2+cx+d y = f (x) とし,x から y を求めるのは容易. y から x を求めることができない. x に具体的な数値を代入し,yを求めるのは容易 例 : f (x) = x4+2x3+3x2+4x+5 に x = 2を代入, f (2) = 41

非線形方程式の近似解の計算 ー 反復法 ー “反復法”は反復により方程式などの近似解を求める手法の総称. 具体例 : 2分法,はさみうち法, Newton-Raphson法など 基本的に,連続である関数の解を求める

非線形方程式の近似解の計算 ー 反復法 ー f (x) = 0 の近似解を求める例 解の候補の初期値を定める. 上記(2)を元に,より解に近い候補を求める 候補が解に十分近ければ終了. 近くない場合は,(2)に戻り繰り返す.

2分法 Bisection Method

2分法 反復法の一種. 初期値の区間内に解が存在すれば必ず収束し,必ず近似解が求まる. 収束速度は遅い. 連続な関数なら一般に使える

2分法 概要 方程式を f (x) = 0 とする (1) 解が存在する区間[a,b]を定める. (2) m = (a+b)/2 とし,f (m)を求め, (3) 解がmより小さいか大きいか調べる.  ・ mより小さい→解は区間[a,m]に存在.  ・ mより大きい→解は区間[m,b]に存在. (解の存在区間が半分になり,解に近づいた)

2分法 概要 (4) 新しい区間を[a,b]とし, これが十分に狭いか調べる. 十分に狭ければ終了.   これが十分に狭いか調べる.   十分に狭ければ終了.   狭くなければ新区間を用いて(2)に戻る. ・初期区間[a,b]が定められないと,2分法は使えない.

2分法の例 f (x) = 0.1x3+x-16 とし f (x) = 0 の解を探す

2分法の例 f (x) = 0.1x3+x-16 (1) 初期の区間を[0,8]に定める. 解は[0,8]に存在する. ただし,以下は既知であると仮定する. f (x)は単調増加であり実数解は1個 解は0~8の間に存在する (1) 初期の区間を[0,8]に定める. 解は[0,8]に存在する.

(8, f (8)) 解はこの区間に存在する (0, f (0)) 50 40 30 20 f (x) 10 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 -10 -20 x (0, f (0))

2分法の例 (2) 現在の区間 [0,8] の中心 4 に着目する. 解が 4 より小さいか,大きいかを調べる.   解が 4 より小さいか,大きいかを調べる.   f (4) = -5.6 < 0   なので,4 は解としては小さすぎた.   解は4より大きく,[4,8]に存在する.   (区間は半分に狭まった)

f (x) は単調増加 なので, 解はこの区間に 存在しない. f (x) は単調増加 なので, 解はこの区間に 存在する 50 40 30 20 f (x) 10 1 2 3 4 5 6 7 8 -10 -20 x

2分法の例 (3) 現在の区間 [4,8] の中心 6 に着目する. 解が 6 より小さいか,大きいかを調べる.   解が 6 より小さいか,大きいかを調べる.   f (6) = 11.6 > 0   なので,6 は解としては大きすぎた.   解は6より大きく,[4,6]に存在する.   (区間はさらに半分に狭まった)

50 40 解はこの区間に 存在する 30 20 f (x) 10 1 2 3 4 5 6 7 8 -10 -20 x

2分法の例 [4,6]の中間値 5 を 試す. f (5) = 1.5 > 0 で, 解は [4,5]に 存在する. 50 40 30 20 f (x) 10 1 2 3 4 5 6 7 8 -10 -20 x

2分法の例 [4,5]の中間値 4.5 を 試す. f (4.5) = -2.3875 < 0 で, 解は [4.5,5]に存在する. 50 [4,5]の中間値 4.5 を 試す. f (4.5) = -2.3875 < 0 で, 解は [4.5,5]に存在する. 40 30 20 f (x) 10 1 2 3 4 5 6 7 8 -10 -20 x

2分法の例 以下同様に繰り返し, 解が存在する区間を狭めていく. 区間が十分に小さくなったら終了する.

2分法の手順 方程式を f (x) = 0 とする (1)初期値(初期区間) xmin0 と xmax0定める. すなわち,f (xmin0) f (xmax0)<0 である. ここでは f (x)が単調増加関数であり, f (xmin0)<0, f (xmax0)>0 である例を扱う.

2分法の手順 (2) xmin0 と xmax0の中間値である xmid0 = (xmin0+xmax0)/2 を求める.

2分法の手順 (3) f (xmid0) を求め, f (xmid0)<0 か f (xmid0)>0 かを調べる. ・ f (xmid0)<0 なら,解は xmid0 より大きい.  解は区間は[xmid0 , xmax0]に存在する.  xmin1=xmid0,xmax1=xmax0, ・ f (xmid0)>0 なら,解は xmid0 より小さい. 新しい区間を[xmin1, xmax1]とする.

2分法の手順 (4) 解は区間 [xmin1 , xmax1]に存在している. 新しい区間が十分に狭ければ終了する. 以下同様に, xmid1 = (xmin1+xmax1)/2 を求め, 解がf (xmid1)より小さいか,大きいかを調べ,さらに狭い新しい区間を求めていく. 区間が十分に狭くなったら終了.

2分法の特徴 1回繰り返すたびに解の存在する区間が半分に減っていく. 初期値が指定できれば必ず収束する. 収束の速度を予想できる. これは他の手法と比べて収束が速いとは言えない. 初期値が指定できれば必ず収束する. 収束の速度を予想できる.

例 f (x) = x3-10 とする. f (x) = 0 の解を探す. 解は[0, 4]にあるのは既知であるとする. [0,4]の中間2に着目. f (0)<0, f (2)>0, f (4)>0 なので解は[0,2] [0,2]の中間1に着目. f (0)<0, f (1)<0, f (2)>0 なので解は[1,2]

練習 2 f (x) = -x2+10 とする. f (x) = 0 の解を探す. 解は[-2,6]にあるのは既知であるとする. 2分法で解の範囲を狭めていく場合の,解の範囲の推移を記せ. 解の範囲の長さが1以下になったら終了. おまけ:ロンドン(London)はどこの国の首都?

解答 2 [-2,6]の中間2に着目. f (-2)>0, f (2)>0, f (6)<0 なので解は[2,6] [2,6]の中間4に着目. f (2)>0, f (4)<0, f (6)<0 なので解は[2,4] [2,4]の中間3に着目. f (2)>0, f (3)>0, f (4)<0 なので解は[3,4] 解の範囲の長さが1になったので終了.

はさみうち法 Regula Falsi Method

はさみうち法 反復法の一種. 初期値の区間内に解が存在すれば必ず収束し,必ず近似解が求まる. 収束速度は2分法より速いと期待される 区間の長さはゼロに収束しない (2分法と異なる) 収束速度は2分法より速いと期待される 必ずしも速いとは限らない 2分法と似ているが,次の候補に1次近似を用いる

はさみうち法の前に 点(x0 , y0)を通り,傾きaの直線の式は y - y0 = a ( x - x0) 2点(x0 , y0)と(x1 , y1) を通る直線の傾きと式は 傾き 直線の式

はさみうち法 方程式を f (x) = 0 とする (1) 解が存在する区間[a,b]を定める. (2) 2点 ( a , f (a) ) と ( b , f (b) ) を通る直線を  求め,これを y = f (x) の近似直線とする.   近似直線がx軸と交わる点(m,0)を求める. 近似直線と y = f (x) が近ければ, mは解と近いことが期待される.

はさみうち法 2点( a , f (a) )と( b , f (b) ) を通る近似直線は 一次方程式 を解く 結果 となる 近似直線がx軸と交わる点(m,0)を求めるには 一次方程式 を解く 結果 となる

はさみうち法 (3) 解がmより小さいか大きいか調べる. ・ mより小さい→解は区間[a,m]に存在. (b-m) が十分に小さければ終了  ・ mより大きい→解は区間[m,b]に存在. (m-a) が十分に小さければ終了 (4) 新しい区間を[a,b]として,   これを用いて (2) に戻る

はさみうち法の例 f (x) = 0.1x3+x-50 とし f (x) = 0 の解を探す

はさみうち法の例 f (x) = 0.1x3+x-50 (1) 初期の区間を[0,8]に定める. 解は[0,8]に存在する. ただし,以下は既知であると仮定する. f (x)は単調増加であり実数解は1個 解は0~8の間に存在する (1) 初期の区間を[0,8]に定める. 解は[0,8]に存在する.

解はこの区間に存在する f (0) より f (8) の方が 0 に近いので, x=0 より x=8 の方が,解に近いと期待される.

はさみうち法の例 (2) 2点(0, f (0) ) と (8, f (8) ) を通る近似直線を引く. これがx軸と交わる点を(m0,0)とし,m0に着目する.

はさみうち法の例 f (0)= -50 ,f (8)=9.2 であり, (0, -50) と (8, 9.2) を通る直線は x軸と交わる点を(m0,0)のm0を求めるには を解く 結果,m0 ≒ 6.76

はさみうち法の例 (3) 解がm0より小さいか,大きいかを調べる. f (m0) ≒ -12.40 なので, m0は解としては小さすぎた.

解はこの区間に 存在する 2分法では, [0,8]の中央の4を 用いて調査する. はさみうち法では, 近似直線の x切片(m0)を

はさみうち法の例 (4) 解は [m0,8]に存在する. (m0, f (m0)) と (8, f (8)) を通る近似曲線の x切片(m1,0)を求める. m1 ≒ 7.47 , f (m1) ≒ -12.40 なので, m1は解としては小さすぎた. 解はm1より大きく,[m1, 8]に存在する.

解はこの区間に 存在する

はさみうち法が2分法より効率が悪い例 はさみうち法では この点が解に近いと 期待して調査する 2分法では, 中央の4を 調査する

はさみうち法の特徴 初期値が指定できれば必ず解に収束する. 区間の長さはゼロに収束しない 2分法より速い収束が期待できるが,必ず速いわけではない. 「f (m)が十分に小さいこと」を収束条件とすることもある. 厳密には「(b-m),(m-a) や| f (m)|が十分に小さいこと」は,解の精度を保証していない.

Newton-Raphson法 Newton-Raphson Method

Newton-Raphson法 反復法の一種. 必ず収束するとは限らない. 初期値が解に近ければ高速に収束する. n回目の調査で使った点から1次近似直線を引き,そのx切片をn+1回目の候補とする 初期値は1個の値. 2分法やはさみうち法の様に区間ではない.

Newton-Raphson法 方程式を f (x) = 0 とする (1) 解に近い値 a0 を定める. (2) y = f (x) に対して,( an , f (an) ) で接する   接線(1次近似直線)を引く.   接線は y – f (an) = f '(an) (x–an)

Newton-Raphson法 (3) 近似直線がx軸と交わる点(an+1,0)を求める.   すなわち,折線 y – f (an) = f ’(an) (x–an) が   y=0となる x を求め,その x がan+1である. 近似直線と y = f (x) が近ければ, an+1は解に近いことが期待される.

Newton-Raphson法 (4) |an-an+1| が十分に小さければ,終了.   小さく無ければ,(2)に戻る

Newton-Raphson法の例 f (x) = 0.1x3+x-5 とし f (x) = 0 の解を探す

Newton-Raphson法の例 f '(x) = 0.3x2+1 初期値a0=7とする. y = f (x) と ( 7, f (7) )で接する接線を引き,接線がx軸と交わる点(a1, 0)を求め, このa1に着目する.

Newton-Raphson法の例 接線のx切片は ただし,( 7, f (7) )における接線は y – f (7) = f ’(7)(x – 7) 接線のx切片は ≒ 4.69

近似直線 と y= f (x) が 近ければ, 近似直線のx切片は 解に近いと期待される. ( 7, f (7) ) ( 7, f (7) )で 接する接線 次に着目する点

Newton-Raphson法の例 y = f (x) と (a1, f (a1) )で接する接線を引き,接線がx軸と交わる点(a2, 0)を求め, 次は,このa2に着目する.

Neton-Raphson法で収束しない例 接点 接線 次の候補 次の候補 接線 接点

Newton-Raphson法の特徴 接線(1次近似直線)が,方程式と近ければ,高速に収束していく. 初期値が解に近くないと,収束しない. 傾きがゼロの箇所においても使えない. 「 | f (an)|が十分に小さいこと」を収束条件することもある. 厳密には「|an-an+1|や f (m)が十分に小さいこと」は,解の精度を保証していない.