2008年6月12日 非線形方程式の近似解 Newton-Raphson法

Slides:



Advertisements
Similar presentations
1 高速フーリエ変換 (fast Fourier transform). 2 高速フーリエ変換とは? – 簡単に言うとフーリエ変換を効率よく計算 する方法 – アルゴリズムの設計技法は分割統治法に基 づいている 今回の目的は? – 多項式の積を求める問題を取り上げ、高速 フーリエ変換のアルゴリズムを用いた解法.
Advertisements

Absolute Orientation. Absolute Orientation の問題 二つの座標系の間における剛体 (rigid body) 変換を復元す る問題である。 例えば: 2 台のステレオカメラから得られた3次元情報の間の関 係を推定する問題。 2 台のステレオカメラから得られた3次元情報の間の関.
計測工学 10 データの補間 スプライン補間 1. . 復習 階差 近似多項式の次数 の決定法 等間隔階差 – 関数 y=f(x) で、 x の値 が等間隔の場合 等間隔: x 0, x 0 +h, x 0 +2h ・・・ y の値: y 0, y 1, y 2 ・・・ これらの階差は – 第1階差:
3 一次関数 1章 一次関数とグラフ § 5 一次関数の利用 (4時間) §5 §5 一次関数の利用 サイクリングで京都から神戸まで行くことにした。 朝出発して、 9 時にはあと 90km の地点を通過した。 さらに進んでいくと、 13 時にはあと 30km の地点を 通過した。 このペースで進み続けると、神戸には何.
中学数学2年 3 章 一次関数 3 一次関数の利用 § 1 一次関数の利用 (4時間) §1 §1 一次関数の利用 サイクリングで京都から神戸まで行くことにした。 朝出発して、 9 時にはあと 90km の地点を通過した。 さらに進んでいくと、 13 時にはあと 30km の地点を 通過した。 このペースで進み続けると、神戸には何.
1 線形代数学. 2 履修にあたって 電子情報システム学科 必修 2005 年度1セメスタ開講 担当 草苅良至 (電子情報システム学科) 教官室: G I 511 内線: 2095 質問等は上記のいずれかに行なうこと。 注意計算用のノートを準備すること。
2. 数値微分法. 数値微分が必要になる場合として、次の 2 つが考えられる。 関数が与えられていて、その微分を近似的に計算する。 (数値微分の精度が十分で、かつ、計算速度が数値微分の方が 早い場合など。) 離散的な点の上で離散的なデータしかわかっていない関数の微 分を近似的に計算する。(偏微分方程式の数値解を求めたい時.
数値解析シラバス C言語環境と数値解析の概要(1 回) C言語環境と数値解析の概要(1 回) 方程式の根(1回) 方程式の根(1回) 連立一次方程式(2回) 連立一次方程式(2回) 補間と近似(2回) 補間と近似(2回) 数値積分(1回) 数値積分(1回) 中間試験(1回) 中間試験(1回) 常微分方程式(1回)
1. 補間多項式 n 次の多項式 とは、単項式 の 線形結合の事である。 Definitions: ( 区間, 連続関数, abscissas (データ点、格子点、差分点), 多項 式 ) Theorem. (補間多項式の存在と一意性) 各 i = 0, …, n について、 をみたす、次数が高々 n.
第1回 確率変数、確率分布 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
確率・統計Ⅰ 第12回 統計学の基礎1 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
電子情報工学科5年(前期) 7回目(21/5/2015) 担当:古山彰一
確率・統計Ⅰ 第11回 i.i.d.の和と大数の法則 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
プログラミング論 数値積分
プログラミング論 I 補間
4.3 連立1次方程式   Ax = b   (23) と書くことができる。
数個、数十個のデータ点から その特徴をつかむ
演習00-0 “Hello,world![改行]”を表示するプログラムを作成せよ. 1 1.
解析的には解が得られない 方程式を数値的に求める。 例:3次方程式
一次関数のグラフ(式を求めること) 本時の流れ ねらい「グラフや座標など与えられた条件をもとに一次 関数の式を求める。」 ↓
一次関数のグラフ(式を求めること) 本時の流れ ねらい「グラフや座標など与えられた条件をもとに一次 関数の式を求める。」 ↓
プログラミング演習I
3 一次関数 1章 一次関数とグラフ §3 一次関数の式を求めること          (3時間).
スペクトル法による数値計算の原理 -一次元線形・非線形移流問題の場合-
1 次方程式 直線   と 軸が交わる点 解ける! 解析的に解ける(解析解)   または 厳密に解ける (厳密解)
Scilab で学ぶ  わかりやすい数値計算法 舞鶴高専 電子制御工学科 川田 昌克.
シミュレーション論Ⅰ 第4回 基礎的なシミュレーション手法.
IT入門B2 ー 連立一次方程式 ー.
第二回 連立1次方程式の解法 内容 目標 連立1次方程式の掃出し法 初期基底を求める 連立1次方程式を掃出し法を用いてExcelで解析する
第 七 回 双対問題とその解法 山梨大学.
応用統計学の内容 推測統計学(inferential statistics)   連続型の確率分布   標本分布   統計推定   統計的検定.
4.2 連立非線形方程式 (1)繰返し法による方法
方程式と不等式 1次方程式 1次不等式.
数値解析シラバス C言語環境と数値解析の概要(1回) 方程式の根(1回) 連立一次方程式(2回) 補間と近似(2回) 数値積分(1回)
非線形方程式の近似解 (2分法,はさみうち法,Newton-Raphson法)
(ラプラス変換の復習) 教科書には相当する章はない
電気回路Ⅱ 演習 特別編(数学) 三角関数 オイラーの公式 微分積分 微分方程式 付録 三角関数関連の公式
誤差の二乗和の一次導関数 偏微分.
計算アルゴリズム 計算理工学専攻 張研究室 山本有作.
情報科学 第6回 数値解析(1).
© Yukiko Abe 2014 All rights reserved
スペクトル法の一部の基礎の初歩への はじめの一歩
数値積分.
プログラミング論 II 2008年吉日 主成分分析 数値積分
応用統計学の内容 推測統計学(inferential statistics)   連続型の確率分布   標本分布   統計推定   統計的検定.
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
6. ラプラス変換.
12.数値微分と数値積分.
システム制御基礎論 システム工学科2年後期.
ルンゲクッタ法 となる微分方程式の解を数値的に解く方法.
電気回路学Ⅱ コミュニケーションネットワークコース 5セメ 山田 博仁.
原子動力工学特論 レポート1 交通電子機械工学専攻 齋藤 泰治.
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
4章 開水路における不等流(2) 漸変流 4-1漸変流とは ① 断面形状や底面形状が緩やかに変わる流れ。
計算機プログラミングI 第6回 2002年11月14日(木) アルゴリズムと計算量 第1回課題の説明 平方根を計算するアルゴリズム 計算量
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
行列式 方程式の解 Cramerの公式 余因数展開.
回帰分析(Regression Analysis)
解析学 ー第9〜10回ー 2019/5/12.
情報科学 第6回 数値解析(1).
1.基本概念 2.母集団比率の区間推定 3.小標本の区間推定 4.標本の大きさの決定
13.ニュートン法.
2008年6月5日 非線形方程式の近似解 2分法,はさみうち法,Newton-Raphson法)
ニュートン法による 非線型方程式の解.
モデルの微分による非線形モデルの解釈 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
Cプログラミング演習 ニュートン法による方程式の求解.
3 一次関数 1章 一次関数とグラフ §4 方程式とグラフ         (3時間).
コンピュータの高速化により, 即座に計算できるようになってきたが, 手法的にはコンピュータ出現以前に考え出された 方法が数多く使われている。
プログラミング言語によっては,複素数が使えない。
プログラミング論 バイナリーサーチ 1.
Presentation transcript:

2008年6月12日 非線形方程式の近似解 Newton-Raphson法 プログラミング論 I 2008年6月12日 非線形方程式の近似解 Newton-Raphson法 http://www.ns.kogakuin.ac.jp/~ct13140/Prog.2008

for文復習 回数が決まっている繰り返し処理(n回とする)は, 必ず for(i=0; i<n; i++) とするのが分かりやすい(ことが多い).

for文復習 100, 102, 104, 106...198 の50個を表示 例 A for(i=100; i<200; i+=2){ printf("%d\n", i); }

for文復習 100, 102, 104, 106...198 の50個を表示 例 B for(i=0; i<50; i++){ x = 100 + i*2; printf("%d\n", x); }

練習 0 右の様に表示されるプログラムを 記述せよ. 倍精度浮動小数点の表示は, double x; printf("%lf\n", x); 6.000000 6.300000 6.600000 6.900000 7.200000 7.500000 7.800000 8.100000 8.400000 8.700000 右の様に表示されるプログラムを 記述せよ. 倍精度浮動小数点の表示は, double x; printf("%lf\n", x);

解答 0 int i; double x; for(i=0; i<10; i++){ x = 6.0 + 0.3*i; printf("%lf\n", x); }

概要 非線形方程式の近似解 Newton-Raphson法 補間 n次多項式での近似 テイラー展開 関数の補間 ラグランジュの補間法

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)が十分に小さいこと」は,解の精度を保証していない.

復習:2分法 2分法 f (x)=ーx3ーx2+5x+20 として f (x)=0 の解を探す (注意:f (x) は単調増加ではない) ただし解が[-4,4]に存在は既知

復習:2分法 解は[-4,4]で,f (-4)>0, f (4)<0 中間値0に着目. f (-4)>0, f (0)>0, f (4)<0 なので,解は[0,4]に 解は[0,4]で,f (0)>0, f (4)<0 中間値2に着目. f (0)>0, f (2)>0, f (4)<0 なので,解は[2,4]に 解は[2,4]で,f (2)>0, f (4)<0 中間値3に着目. f (2)>0, f (3)<0, f (4)<0 なので,解は[2,3]に

復習:2分法 min=??, max=??; (max-min)が大きいなら繰り返す mid=(min+max)/2; f(min)*f(mid)>0 同符号なら 解は[mid,max] min = mid; f(min)*f(mid)<0 異符号なら 解は[min,mid] max = mid; 繰り返しの先頭に戻る

補間

補間 (1) n次多項式での近似 テイラー展開 (2) 関数の補間 ラグランジュの補間法

補間とは (x0, f (x0)), (x1, f (x1),…(xn, f (xn))が既知のとき, それ(x0, x1,… xn)以外の点における関数の値を求める(予測する)

補間の例 x=6 (10, 6.6) f (5), f (10)が既知. f (6)が必要になったら? 8 (10, 6.6) f(x) 6 4 f (5), f (10)が既知. f (6)が必要になったら? 近くの f (5)=2.4で代用する? (5, 2.4) 2 5 10 15 20 25 30 x

f (5)と f (10)からf (6)を補間する おそらく f (5)より, 一次近似の方が正確. (10,6.6) さらに正確な補間方法は? (10,6.6) 直線を引いて(一次近似), x=6 における値を予想. (5,2.4) f (5)=2.4 で代用

・近似は補間と密接な関係. ・関数をn次多項式で近似する. 関数の式が既知であることが前提 ・テイラー展開

一次式で近似 接線 y =f (a)+f '(a)(x-a)=g(x) y = f (x) 近似に 用いた点 1.5 y =f (a)+f '(a)(x-a)=g(x) 1 y = f (x) 0.5 近似に 用いた点 y x y = f (x) の接線 y = g(x)は,y =f (x)の一次近似線. f (a) = g(a) かつ f '(a) = g'(a) となっている. つまり,x=a において, 「yの値」と「傾き(一階微分)」が一致している. -0.5 -1

二次式で近似 y =f (a)+f '(a)(x-a)=g(x) 近似に x=aに近いほど 用いた点 y = f (x) 近似は正確 1.5 y =f (a)+f '(a)(x-a)=g(x) 1 0.5 近似に 用いた点 x=aに近いほど 近似は正確 y = f (x) y x y = h(x)は,y =f (x)の二次近似曲線. (y=f (x)を近似した二次曲線) f (a) = h(a) かつ f '(a) = h'(a) かつ f ''(a) = h''(a). x=a において 「y」と「一階微分」と「二階微分」が が一致している.一次近似よりより正確な近似. -0.5 -1

三次式で近似 y = i(x)は,y =f (x)の三次近似曲線. ここは xの式 ここは 定数である y = i(x)は,y =f (x)の三次近似曲線. f (a)=i (a),f '(a)= i (a), f ''(a)= i ''(a),f '''(a)=i '''(a) よって,x=a において,yの値,1~3階微分が一致.

テイラー展開 Taylor expansion f (x) を以下の級数に展開する a=0の場合, マクローリン展開

テイラー展開 テイラー展開を有限個の級数で打ち切る Rnはラグランジュの剰余項 =0のとき, 換言すると =0のとき,展開の次数を上げていくと より正確な近似になっていく.

テイラー展開 近似線 1次 2次 0次 5次 6次 y=sin(x) 4次 3次

n次多項式による近似 基本的に近似点の近傍では次数を上げるほど,正確な近似になる

単語の説明 この区間を 補うことを 補外,外挿 という この区間を補うことを 補間,内挿という

(2) 関数の補間 関数の式が未知の場合も使える

補間 既知の f (xi)から,f (6)を補間する例を考える.

0次補間 x=6に一番近い,x=5を採用する. 既知の点 既知の点 f (6)を補間 f (6) = f (5)

1次補間 (5, f (5)), (10, f (10)) を通る1次関数(直線)で補間する. 近似直線を用いて f (6)を補間 既知の点

1次補間 2点(a , f (a))と(b , f (b))より,x=mにおける yの値 f (m)を予測する

2次補間 3点を通る2次関数を求め,その2次関数(放物線)で補間する. (5, f (5)), (10, f (10)), これを近似曲線とする 近似曲線を用いて f (6)を補間

2次補間 3点(x0, y0), (x1, y1), (x2, y2) を通る2次曲線の求め方(の例) 2次曲線は y=ax2+bx+c で表せる. (3個の未知数が決まれば,2次曲線が決まる) (x, y)=(x0, y0), (x, y)=(x1, y1), (x, y)=(x2, y2)を代入すれば,方程式が3本立つ. よって,3元1次連立方程式を解けば2次曲線は求まる. 後で,別の方法(ラグランジュの補間法)を紹介する

2次補間 求めた2次近似曲線 y=g (x) に, x=m を代入し,g(m)を補間値として用いる. 1次補間(直線による予測)より,正確であることが期待できる.

練習 1 y=f (x)は,2点 (1, 1), (2,4) を通る. f (1.5) と f (3) を,一次補間(補外) により予測せよ

解答 1 両点を通る直線 傾き (1, 1)を通り,傾き3の式は x = 1.5 のとき,y = 2.5 x = 3 のとき,y = 7

ラグランジュの補間法 既知の点n+1個を全て通る n次式を求める

ラグランジュの補間法 n+1個の点を通る,n次方程式P(x)で補間 通る点を(x0, f (x0)), (x1, f (x1)),…, (xn, f (xn)) として 以下の方法により,P(x)が求まる ただし

ラグランジュの補間法 (xーxk)以外 (xkーxk)以外 Lk(x)の分子は x の n次多項式.分母は定数. f (xk) は定数.よって, f (xk)Lk(x)は x の n次多項式. よって,             は x の n次多項式.

ラグランジュの補間法の例 4点(x0, f (x0)), (x1, f (x1)), (x2, f (x2)), (x3, f (x3))を通る,3次曲線の方程式 y = P(x) は, (xーx2) 以外 (x2ーx2) 以外

ラグランジュの補間法の例 y = P(x) は,(x2, f (x2))を通るか確認 ゼロ ゼロ y=P(x)は (x2 , f (x2)) を通る 3次曲線 1 (x=x2なら 分子と分母 が一致) ゼロ = f (x0)×0 + f (x1)×0 + f (x2)×1 + f (x3)×0 = f (x2)

ラグランジュの補間法の例 4次曲線で 近似し,補間

ラグランジュ補間法の問題点 を11点を用いて ラグランジュ補間法で補間 端の方は 全く近く いない 補間曲線は, 確かに 全ての点を 通過している を11点を用いて ラグランジュ補間法で補間 端の方は 全く近く いない y=1/(x2+1) ラグランジュ補間法 による予想 正解

ラグランジュの補間法の問題点 補間の点数が増えると,激しく振動する 点数が増えると, (全ての補間点を通過しているのは事実だが) 補間のn多項式の次数が大きくなり振動する. 次数が高いほど好ましいのではない.

(3次)スプライン補間 区間ごとに,別々の 3次多項式を用意し 補間する この区間を 3次関数 で補間 この区間を 3次関数 で補間 y=1/(x2+1) この区間を 3次関数 で補間 補間点

練習 2 3点 (x0, y0), (x1, y1), (x2, y2) を通る,2次方程式を書け. ただし,  記号と, 記号は使用しないこと

解答 2