第4回

数値解析

ニュートン法

方程式の反復法による解法のひとつ
以下の漸化式を解く（ホワイトボードには斬化式と書いてある…）
x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})}

例題 f(x)=(x-1)(x-2)(x-3)について解く
f'(x)=3x^2-12x+11

やったことにした

計算量

P次収束（1次収束、2次収束）
誤差：εn=xn-α について

  • | \varepsilon_{n+1} | = C | \varepsilon_{n} | …1次収束
  • | \varepsilon_{n+1} | = C | \varepsilon_{n}^2 | …2次収束

というようになる

２分法の場合
区間を半分ずつにするので| \varepsilon_{n+1} | = \frac{1}{2} | \varepsilon_{n} |
　…1次収束

ニュートン法の場合
\begin{matrix} \varepsilon_{n+1} &=& x_{n+1}-\alpha \\ & =& x_{n} - \frac{f(x_{n})}{f'(x_{n})} -\alpha \\ & =& \varepsilon_{n} - \frac{f(x_{n})}{f'(x_{n})} \end{matrix}
ここで、テーラー展開により
\left\{\begin{matrix} f(x_{n})=f(\alpha)+ \varepsilon_{n}f'(\alpha) + \frac{\varepsilon_{n}^2}{2} f^{(2)}(\alpha) +\frac{\varepsilon_{n}^3}{6}f^{(3)}(\xi_{1})\\ f'(x_{n})=f'(\alpha)+ \varepsilon_{n}f^{(2)}(\alpha) + \frac{\varepsilon_{n}^2}{2} f^{(3)}(\xi_{2}) \end{matrix}\right
したがって（f(α)=0を考慮すると）
\begin{matrix} \varepsilon_{n+1} &=& \varepsilon_{n} - \frac{f(x_{n})}{f'(x_{n})} \\& =& \frac{\varepsilon_{n}^2}{2} \times ... \\ & \simeq & C \varepsilon_{n}^2\end{matrix}
したがって2次収束
ちなみにαが2重根の場合は、f'(α)=0も考慮して1次収束になる。

3章 曲線の推定

点から曲線を補間する

  • タイプ1：点の値が正しい場合・・・点を通る曲線
  • タイプ2：点に誤差を含む場合・・・点の近傍を通る曲線

自由度が大きい（沢山の曲線がある）
→シンプルな曲線が良い（スムーズで次数が少ない曲線）

  • ラグランジュ補間（タイプ１）
  • スプライン補間（タイプ１）
  • 最小2乗法（タイプ２）
ラグランジュ補間

N+1個の点を通る曲線はN次の多項式で表すことができる。
一般にN+1個の(x,y)値が与えられたとき（ただしxはすべて異なる）
P_{N}=y_{0}l_{0}(x)+y_{1}l_{1}(x)+ ... +y_{N}l_{N}(x)
ただし
l_{i}=\frac{(x-x_{0})...(x-x_{i-1})(x-x_{i+1})...(x-x_{N})}{(x_{i}-x_{0})...(x_{i}-x_{i-1})(x_{i}-x_{i+1})...(x_{i}-x_{N})}