数値計算

このページでは、二分法とニュートン法による近似根の求め方、台形公式、情報落ち・桁落ちなどの誤差、逆行列や掃き出し法で連立方程式を解く方法がわかります。

  • 記号の書き方(このメモのルール):

    • 本来は上に線を引いて表す「否定」「補集合」は、論理なら ¬A、集合なら Aᶜ と書く
    • 2乗などのべき乗は 2³、σ² のように書く。log の底は log₂ のように書く
  • 一言で言うと:

    • 式を変形しても答えが出せない問題を、コンピュータの繰り返し計算で「だいたいの答え(近似値)」にする方法と、そのときに出る誤差の話。

方程式の根を求める(二分法・ニュートン法)→ 面積を求める(数値積分・台形公式)→ 誤差(丸め・情報落ち・桁落ち・打切り)→ 連立方程式を解く(逆行列・掃き出し法)

覚え方の軸

  • 根の求め方は「半分に切る」か「接線で近づく」:
    • 二分法(確実だが遅い)、ニュートン法(速い)。どちらも差がε未満になったら止める
  • ニュートン法の式は1本:
    • x₁=x₀−f(x₀)÷f’(x₀)
  • 誤差は「どこで起きるか」で4つ:
    • 端数(丸め)、大+小(情報落ち)、近い数の引き算(桁落ち)、途中でやめる(打切り)
  • 連立方程式は「Aα=b → α=A⁻¹b」:
    • 掃き出し法は(A|b)を(E|c)に変形する。cが答え

数値的解法:近似値を繰り返し計算で求める

  • 二分法:
    • f(x)=0 の近似根を求める方法。f(a)とf(b)の符号が逆なら、aとbの間に根がある。その範囲を半分に切る操作を繰り返して、範囲を狭めていく
    • 前提:
      • f(x)が区間[a,b]で単調に増加する連続関数で、f(a)<0 かつ f(b)>0
    • 手順:
      • ①c←(a+b)÷2
      • ②|a−b|<ε なら、cを近似根として終わる
      • ③f(c)<0 なら a←c、そうでなければ b←c
      • ④①に戻る
    • 閉区間[a,b]:
      • aとbの両端を含む区間
    • ε(イプシロン):
      • 収束判定に使う、十分に小さい正の値
  • 例(f(x)=x²−2、根は√2≒1.414):
    • [1,2]:c=1.5、f(1.5)=0.25>0 → b=1.5
    • [1,1.5]:c=1.25、f(1.25)=−0.4375<0 → a=1.25
    • [1.25,1.5]:c=1.375、f<0 → a=1.375
    • [1.375,1.5]:c=1.4375 …と、1.414に近づいていく
  • ニュートン法(★):
    • y=f(x)の接線を使って近似根を求める方法。「x₀での接線とx軸の交点x₁は、x₀より真の根に近い」という考えで繰り返す。二分法より速く収束する
    • 手順:
      • 予想できる近似値を初期値x₀にする → 点(x₀,f(x₀))の接線とx軸の交点x₁を求める → x₁を新しいx₀にして繰り返す → |x₁−x₀|<ε になったら止め、x₁を近似根にする
    • 接線の式:
      • y−f(x₀)=f’(x₀)(x−x₀)
    • y=0、x=x₁ を入れて変形すると(★試験で問われる):
      • x₁=x₀−f(x₀)÷f’(x₀)
    • f’(x):
      • f(x)を微分した導関数(接線の傾き)
  • 例(f(x)=x²−2、f’(x)=2x、x₀=2):
    • x₁=2−(4−2)÷4=1.5
    • x₂=1.5−(2.25−2)÷3=1.5−0.0833…=1.4167
    • x₃ ≒ 1.4142(3回でほぼ√2。二分法よりずっと速い)
  • はさみうち法(線形逆補間法):
    • 根を含む区間[a,b]で、点(a,f(a))と点(b,f(b))を結ぶ直線とx軸の交点を求め、それを新しい区間の端にして繰り返す
  • 数値積分:
    • 積分公式を使わずに、曲線で囲まれた面積の近似値を求める方法
  • 台形公式(台形則):
    • 区間[a,b]でf(x)を一次関数(直線)で近似し、できた台形の面積で定積分を近似する
    • 1つの台形:
      • ∫f(x)dx ≒(b−a)÷2 ×(f(a)+f(b))
    • 台形の面積:
      • (上底+下底)×高さ÷2
    • 区間をn等分(幅 h=(b−a)/n、端点 x₀,x₁,…,xₙ)すると、よりよい近似になる:
      • ∫f(x)dx ≒ h/2 ×(f(x₀)+2f(x₁)+2f(x₂)+…+2f(xₙ₋₁)+f(xₙ))
      • 両端は1回、間の点は2回(隣どうしの台形で共有するため)
    • 区間を n=2ᵏ(k=1,2,…)等分していき、|Sₖ−Sₖ₋₁|<ε になったら止めて、Sₖ を積分値とする
  • シンプソン法:
    • 誤差をさらに小さくするため、微小区間を一次関数ではなく二次関数で近似する方法
  • 例(∫₀² x² dx、真の値は8/3≒2.667):
    • 2等分(h=1、x=0,1,2、f=0,1,4):
      • 1/2 ×(0+2×1+4)=3
  • 誤差の種類(★)
誤差 どこで起きるか
丸め誤差 数値を有限のビット数で表すため、最下位桁より小さい部分を四捨五入・切上げ・切捨てしたときに出る
情報落ち 絶対値がとても大きな数ととても小さな数を足し引きしたとき、小さいほうの数の仮数部の下位が結果に反映されない
桁落ち 絶対値がほぼ等しい2つの数の差を求めたとき、有効桁数が大きく減る
打切り誤差 計算を途中で打ち切ったために出る(εが大きいと真の値に近づく前に止まる)
  • 情報落ちの仕組み:
    • 指数部が違う2つの数を足し引きするときは、指数部を大きいほうにそろえる。そのため小さいほうの仮数部が右にずれて、下位の桁がはみ出す
  • 絶対誤差=
    • |近似値−真値|
  • 相対誤差=
    • |絶対誤差÷真値|=|(近似値−真値)÷真値|
  • 誤差限界:
    • 誤差がこれを超えない、という範囲(|近似値−真値|≦ε なら、εが誤差限界)
  • 相対誤差の限界=
    • 誤差限界÷真値
  • 積の相対誤差の限界:
    • A、Bの近似値をa、b、それぞれの絶対誤差(誤差限界)をda、dbとすると、積の相対誤差の限界は |da/A|+|db/B|(掛け算では相対誤差が足し算になる)
  • 例(上の台形公式の例):
    • 絶対誤差=|3−2.667|≒0.333、相対誤差=0.333÷2.667≒0.125(12.5%)

連立一次方程式の解法:行列で解く

  • 多元連立一次方程式:
    • 未知数がいくつもある連立一次方程式。最小二乗法などで、データから情報を得るときに解く必要がある
  • 行列による表現:
    • x+2y=5、3x+4y=11 は、係数の行列 A=(1 2 / 3 4)、解の列ベクトル α=(x / y)、定数項の列ベクトル b=(5 / 11)を使って Aα=b と書ける
  • 単位行列 E:
    • 対角要素が1で、他がすべて0の行列。2×2なら(1 0 / 0 1)。E 又は I と書く
  • 逆行列 A⁻¹:
    • AB=BA=E を満たす行列B
  • 正則行列:
    • 逆行列をもつ行列
  • Aα=b の解き方:
    • 両辺に A⁻¹ を掛けると、A⁻¹Aα=A⁻¹b → Eα=A⁻¹b → α=A⁻¹b(Eα=α)
    • Aに逆行列があれば、解は一意に決まる
  • 2×2の逆行列の求め方:
    • A=(a b / c d)なら、A⁻¹=1/(ad−bc)×(d −b / −c a)
    • 行列式:
      • ad−bc のこと。|A| 又は detA と書く
  • 例:
    • A=(1 2 / 3 4)の行列式=1×4−2×3=−2
    • A⁻¹=−1/2 ×(4 −2 / −3 1)
    • α=A⁻¹b=−1/2 ×(4×5−2×11 / −3×5+1×11)=−1/2 ×(−2 / −4)=(1 / 2)→ x=1、y=2
    • 検算:
      • 1+2×2=5、3×1+4×2=11 で合う
  • 行列式を使う解き方(クラメルの公式):
    • ax+by=p、cx+dy=q で D=ad−bc≠0 なら
    • x=(pd−bq)÷D、y=(aq−pc)÷D
    • 例:
      • x=(5×4−2×11)÷(−2)=1、y=(1×11−5×3)÷(−2)=2
  • 掃き出し法(★):
    • Aα=b の左辺の A を単位行列に変える、という考え方の解き方
    • 手順:
      • ①係数の行列Aと定数項のベクトルbをまとめて、(A|b)という行列を作る
      • ②基本変形をくり返して、(E|c)の形にする。このとき c が解
    • 拡大係数行列(拡大行列):
      • 行列と列ベクトルを「|」で区切ってまとめた行列
    • 基本変形(この3つだけ使ってよい):
      • (1)ある行を k倍する(k≠0)
      • (2)ある行の k倍を、他の行に足す
      • (3)ある行と他の行を入れかえる
  • 例((1 2 | 5 / 3 4 | 11)から始める):
    • ①1行目を−3倍して2行目に足す → 2行目が(0 −2 | −4)
    • ②2行目を−1/2倍する → 2行目が(0 1 | 2)
    • ③2行目を−2倍して1行目に足す → 1行目が(1 0 | 1)
    • 結果は(1 0 | 1 / 0 1 | 2)。答えは x=1、y=2
  • 変形しても(E|c)の形にならないときは、解がない(不能)か、解が無数にある(不定)
  • ガウス・ジョルダン法:
    • 上の掃き出し法の別名
  • ガウスの消去法:
    • 拡大係数行列のAの部分を、対角より左下が全部0の三角行列にしてから(前進消去)、下から順に代入して(後退代入)解を求める方法

AIとGPU

  • GPU(Graphics Processing Unit):
    • 3Dグラフィックスなどの画像描画計算を高速に行うプロセッサ。「単純な演算を、多数のデータに、並列に、繰り返し」行うのが得意
  • GPGPU(General-Purpose computing on Graphics Processing Units):
    • GPUの高い演算性能を、画像処理以外の用途に使うこと。「GPUコンピューティング」「GPUによる汎用計算」ともいう
    • 代表例がディープラーニング。大量のデータで膨大な計算をし、その大部分が行列計算なので、CPUの代わりにGPUを積んだGPUサーバが使われる

混同しやすいペア

  • 二分法(区間を半分に。確実だが遅い)/ニュートン法(接線を使う。速い)/はさみうち法(2点を結ぶ直線を使う)
  • 台形公式(一次関数で近似)/シンプソン法(二次関数で近似。より正確)
  • 情報落ち(大きい数+小さい数)/桁落ち(ほぼ同じ数どうしの引き算)
  • 丸め誤差(端数処理)/打切り誤差(計算を途中で止める)
  • 絶対誤差(差そのもの)/相対誤差(差÷真値)
  • 単位行列(対角が1)/逆行列(掛けると単位行列になる)
  • ガウス・ジョルダン法(掃き出し法。Aを単位行列にする)/ガウスの消去法(三角行列にして後退代入)
  • 前進消去(左下を0にする)/後退代入(下から代入する)

← 01 基礎理論の目次に戻る

タイトルとURLをコピーしました