ぼんさい塾

ぼんさいノートと補遺に関する素材や注釈です.ミスが多いので初稿から1週間を経た重要な修正のみ最終更新日を残しています.

逆行列

2010-08-18 17:23:52 | 暮らし
記事一覧

math.pdf [#57] に関する「逆行列 計算量」の Google で

[1] 【文献調査】ガウスの消去法とLU分解
     http://mikilab.doshisha.ac.jp/dia/research/report/2005/0706/005/report20050706005.html
[2] 岩井の実験室
     http://www.tagen.tohoku.ac.jp/labo/kawamura/each_member/iwai/excelmania3.html
[3] 行列式 - Wikipedia
    http://ja.wikipedia.org/wiki/%E8%A1%8C%E5%88%97%E5%BC%8F

等が見つかりました.基本的な性質は[3]の

  逆行列 =(1/行列式)余因子行列

で理解することが重要ですが,計算が面倒なので LU分解の方が実用的です.
[1][2]のLU分解の説明には数値例がありません.「LU分解」で検索した

[4] LU分解の並列化について
     http://mikilab.doshisha.ac.jp/dia/research/report/2002/0612/018/report20020612018.html

の前半がお薦めです(余力があれば後半も).

発展: 単に「逆行列 計算量」で検索しても,一般化逆行列(一般逆行列,擬似逆行列)の資料が
予想以上に混じっていました.「一般化逆行列」で検索すると
[5] 正方行列の逆行列と一般化逆行列の違い - 数学 - 教えて!goo
    http://oshiete.goo.ne.jp/qa/3979862.html
[6] 擬似逆行列 - Wikipedia
    http://ja.wikipedia.org/wiki/%E6%93%AC%E4%BC%BC%E9%80%86%E8%A1%8C%E5%88%97
[蛇足] 応用例


Cの文法 (6)

2010-08-16 15:58:25 | 暮らし
「まず覚えるCの文法」
(ミス多し.校正中)

Ex2-1A: 擬似コード(#11)
//-------------------------------------
#include <stdio.h>
int main(void){
  int x, y;
  $[総和の計算]$
  $[総和の表示]$
  return 0;
}

$[総和の計算]$=${
  y=0; $[x に整数を入力する]$
  while(x!=0){
    $[y に x の絶対値を加える]$
    $[x に整数を入力する]$
  }
}$

$[y に x の絶対値を加える]$=${
  if(x>0){y=y+x;}else{y=y-x;}
}$
//-------------------------------------

Ex2-1B: 解答例
//-------------------------------------
#include <stdio.h>
int main(void){
  int x, y;
  y=0; printf("x="); scanf("%d", &x);
  while(x!=0){
    if(x>0){y=y+x;}else{y=y-x;}
    printf("x="); scanf("%d", &x);
  }
  printf("y=%d\n", y);
  return 0;
}
//-------------------------------------

問2-1. つぎの処理をするプログラムを示せ.
(1) 0 が入力されるまでキーボードから整数の
    データを読み続ける.
(2) 入力された整数の絶対値の総和を計算して
    画面に表示する.
(3) 入力データが整数でないときや,総和が
    オーバーフローするときのの対策は考え
    なくてよい.

・構造化プログラミングでは所望の処理をトップ
  ダウン的に連接,選択,反復の組み合わせに分解
  していきます(stepwise refinement).
    (1) 連接:  → {文1 文2}
    (2) 選択:  → if(式0){文1}else{文2}
    (3) 反復:  → while(式0){文0}
・(#11)の擬似コード表現によるトップダウン的
  設計例を Ex2-1A に示します.
    x: 入力データの記憶用
    y: 絶対値の総和の記憶用
・解答例を Ex2-1B に示します.Cでは y=y+x を
  y+=x,y=y-x を y-=x と書くことができるので,
    //-------------------------------------
    #include <stdio.h>
    int main(void){
      int x, y=0;
      while(1){
        printf("x="); scanf("%d", &x);
        if(x>0){y+=x;}
        else if(x<0){y-=x;}
        else{break;}
      }
      printf("y=%d\n", y);
      return 0;
    }
    //-------------------------------------
  と変形できます.


Cの文法 (5)

2010-08-14 19:11:31 | 暮らし
「まず覚えるCの文法」

P25: for文
//-------------------------------------
#include <stdio.h>
int main(void){
   int i, k=1;
   for(i=1; i<10; i++){k=k*i;}
   printf("k=%d\n", k);
   return 0;
}
//-------------------------------------

P26: break文
//-------------------------------------
#include <stdio.h>
int main(void){
  int k,a,b,c,d,m,n;
  a=b=c=d=m=n=0;
  while(1){
    printf("k="); scanf("%d", &k);
    if(k<0){break;}
    if(k>=80){
      a++; if(k==m){n++;}
      if(k>m){m=k; n=1;}
    }
    else if(k>=70){b++;}
    else if(k>=60){c++;}
    else{d++;}
  }
  printf("%d,%d,%d,%d;", a, b, c, d);
  printf("%d,%d\n", m, n);
  return 0;
}
//-------------------------------------

P27: switch文
//-------------------------------------
#include <stdio.h>
int main(void){
  int k,a,b,c,d,m,n;
  a=b=c=d=m=n=0;
  while(1){
    printf("k="); scanf("%d", &k);
    if(k<0){break;}
    switch(k/10){
      case 10:
      case  9:
      case  8: a++; if(k==m){n++;}
               if(k>m){m=k; n=1;}
               break;
      case  7: b++; break;
      case  6: c++; break;
      default: d++;
    }
  }
  printf("%d,%d,%d,%d;", a, b, c, d);
  printf("%d,%d\n", m, n);
  return 0;
}
//-------------------------------------

P25 のプログラムの 
  for(i=1; i<10; i++){k=k*i;}
の部分は
  i=1; while(i<10){k=k*i; i++;}
と同じ処理を行います.一般に
  式1; while(式2){ 式3;}
は,つねに
  for(式1; 式2; 式3){}
と書き換えることができます.ただし「文」は実行文
を意味します(宣言文は不可)(#11&).

・プログラムを実行すると,1 から 9 までの積が
    k=362880
  と表示されます.
・「i=1」は式,「i=1;」は文です(#15).
・「i=1,k=1」も式で,「k=i=1」と等価です.また,
  文「i=1,k=1;」は「i=1; k=1;」と等価です(@37).
・単純な while 文「while(k>0){k--;}」でも for 文
  で「for(; k>0;){k--;}」と表現できます.

P26 のプログラムでは break文を使って P24 のプロ
グラム中の
  printf("k="); scanf("%d", &k);
の重複を避けています.

・break文は(最も内側の)while文,for文,switch文
  の直後にジャンプします(#26).
・break文ほど使用頻度は高くありませんが,continue
  文で(最も内側の)while文の直前にジャンプさせる
  ことができます.
    for(式1; 式2; 式3){}
  の{}中で continue 文を実行したときは等価な
  while 文の先頭の処理である 式2 の真偽の判定に
  戻ります(#26).

P27 のプログラムでは 0≦k≦100 を前提に P24 のプロ
グラム中の if-else 文による分岐を switch文を使って
書き換えています.

・k/10 の値は小数部を切り捨てます(#12).
.switch文の部分での処理内容は
    if(k/10==10 || k/10==9 || k/10==8){
      a++; if(k==m){n++;} if(k>m){m=k; n=1;}
    }else if(k/10==7){
      b++;
    }else if(k/10==6){
      c++;
    }else{
      d++;
    }
  と等価です.
・k/10==7 のときはジャンプテーブルによって goto文
  と同様に,直接「case 7:」の位置にジャンプします.
  したがって,先頭から条件式の真偽を調べる if-else
  文に比べて高速に分岐できます.
・「case :」のは相異なる整数値の定数式です.
  式の値からジャンプテーブル内の相対アドレスを計算
  します.


Cの文法 (4)

2010-08-13 19:02:12 | 暮らし
「まず覚えるCの文法」

P22: 条件付ジャンプ
//-------------------------------------
#include <stdio.h>
int main(void){ char c; int k=0; loop:    scanf("%c", &c);    if(c==' '){goto next;}    k++; next:    if(c!='.'){goto loop;}    printf("k=%d\n", k);    return 0; } //------------------------------------- P23: if-else文 //------------------------------------- #include <stdio.h> int main(void){    int k,a,b,c,d,m,n;    a=b=c=d=m=n=0; loop:    printf("k="); scanf("%d", &k);    if(k>=80){      a++; if(k==m){n++;}      if(k>m){m=k; n=1;}    }    else if(k>=70){b++;}    else if(k>=60){c++;}    else{d++;}    if(k>=0){goto loop;}else{d--;}    printf("%d,%d,%d,%d;", a, b, c, d);    printf("%d,%d\n", m, n);    return 0; } //------------------------------------- P24: while文 //------------------------------------- #include <stdio.h> int main(void){    int k,a,b,c,d,m,n;    a=b=c=d=m=n=0;    printf("k="); scanf("%d", &k);    while(k>=0){      if(k>=80){        a++; if(k==m){n++;}        if(k>m){m=k; n=1;}      }      else if(k>=70){b++;}      else if(k>=60){c++;}      else{d++;}      printf("k="); scanf("%d", &k);    }    printf("%d,%d,%d,%d;", a, b, c, d);    printf("%d,%d\n", m, n);    return 0; } //------------------------------------- P24A: do-while文 //------------------------------------- #include <stdio.h> int main(void){    int k,a,b,c,d,m,n;    a=b=c=d=m=n=0;    do{      printf("k="); scanf("%d", &k);      if(k>=80){        a++; if(k==m){n++;}        if(k>m){m=k; n=1;}      }      else if(k>=70){b++;}      else if(k>=60){c++;}      else if(k>=0){d++;}    }while(k>=0);    printf("%d,%d,%d,%d;", a, b, c, d);    printf("%d,%d\n", m, n);    return 0; } //-------------------------------------
P22 のプログラムをコピーして実行し,キーボードから
    Hello, world.
と入力すると,画面に
    k=12
と表示されることを確かめてください.

・P22 は[#20]の処理を行うプログラムです.
・if(c==' '){goto next;} という文は式「c==' '」の値が
  0 でなければ「next:」の直後にジャンプします.この文
  は機械語の条件付きジャンプ命令に近い表現です.
・「c==' '」の値は 0 か 1 ですが,数式の 0 でない値は
  真偽の判定では 1 と同等に扱われます[#21].
・「loop:」や「next:」はアドレスを指定するだけで何も 計算しません. ・goto文を使うと制御の流れが分かりにくいプログラムも 作れるので,構造化プログラミングではgoto文の使用を 禁止しています(ジャンプ先を制限したif文やwhile文を 使ってプログラムを作ります). P23 は試験の点数 k を入力して 80点以上,70~79点,60~ 69点,60点未満の人数と,表彰者数を調べるプログラムです (#23). ・「a=b=0;」は「b=0; a=b;」と同じ(@37).「a=b=c=d=m=n =0;」も同様. ・最高得点が 80 点以上のとき最高得点者を表彰. ・得点として負の数を入力すると処理を終了します. ・if-else 文の else の部分に別の if-else 文があります. 構文に忠実な表現は if(k>=80){ a++; if(k==m){n++;} if(k>m){m=k; n=1;} }else{ if(k>=70){ b++; }else{ if(k>=60){ c++; }else{ d++; } } } ですが,通常は P23 のように表現します. if(k>=60){c++;}else{d++;} の部分は「if(k>=60) c++; else d++;」でもいいのですが { } で囲むように習慣付けておく方が無難です. while文を用いて P23 のプログラムを P24 のように変更する ことにより,goto文を除去できます(#24). ・反復終了の判定に必要な k の値を知るために while文の外 にも「printf("k="); scanf("%d", &k);」が必要になります. この部分が大きいときには次のような方法が使えます.    int k,a,b,c,d,m,n,end=0;    a=b=c=d=m=n=0;    while(end==0){      printf("k="); scanf("%d", &k);      if(k>=80){        a++; if(k==m){n++;}        if(k>m){m=k; n=1;}      }      else if(k>=70){b++;}      else if(k>=60){c++;}      else if(k>=0){d++;}      else end=1;    } ・後述の break文を使うと end は不要です(#26).また,P24A のように do-while文を使う方法もあります(#24&).

有効数字

2010-08-13 13:01:38 | 暮らし
記事一覧

「定数の分数近似」(8/9) の補足です.有効数字が 2 桁の数を小数第2位を四捨五入した値と考えると,相対誤差の上界は

  1.1×103 のときは 0.04545
  5.0×103 のときは 0.01
  9.9×103 のときは 0.00505

で,1.1 と 9.9 では1桁近い精度の差があります.したがって

 「1.1 の有効数字は log10 1.1/0.05 = 1.34 桁以上」
 「9.9 の有効数字は log10 9.9/0.05 = 2.29 桁以上」

という方が正確です.定数の分数近似の場合は誤差の上界でなく誤差そのもので評価でき,

  1/9 × 10-9 = 4πε0 × (1 - 0.0014)

の 1/9 を 4πε0 の近似値としてみたときの有効数字は「約 log10 0.0014 = 2.85 桁」です.したがって,例えば

  E = q /4πε0r2

の計算で q / r2 の精度を 2.3 桁以上とすると,(q / r2) × 9 × 109 で E を近似したときの精度は約 2.2 桁以上になります.

蛇足:(1 ± 0.0050) × (1 - 0.0014) ≒ 1 ± 0.0064