多項式の零点同時決定のための反復法について

概要

論文の詳細を見る
多項式P(z)=z^n+a_1z^<n-1>+…+a_nの全ての零点を同時に求めるDurand-Kerner(D-K)法はz^<k+1>_i=z^k_i-σ^k_i,σ^k_i=<P(z^k_i)>/<Π__<j≠i>(z^k_i-z^k_j)>,(1)1≤i≥n,k≥0 により定義される.この方法は連立方程式f_i=(-1)^iΣz_j_1・・・z_j_2-a_i=0,(2)1≤i≥n に適用されたNewton法であり,n個の零点が相異なるとき,収束速度は局所的に2次である.また,D-K法の改良として,次の3次収束法はよく知られている.(I)Borsch-Supan 1963,Aberth 1973,他:z^<k+1>_i=z^k_i-<1>/<<P'(z^k_i)>/<P(z^k_i)>-Σ__<j≠i><1>/<z^k_i-z^k_j>>,(3)=z^k_i-<σ^k_i>/<1+Σ__<j≠i><σ^k_j>/<z^k_i-z^k_j>>,(4)1≤i≥n,k≥0(II)田辺1983:z^<k+1>_i=z^k_i-σ^k_i(1+Σ__<j≠i><σ^k_j>/<z^k_i-z^k_j>,(5)1≤i≥n,k≥0(III)Nourein 1977:z^<k+1>_i=z^k_i-<P(z^k_i)>/<Π__<j≠i>(z^k_i-z^<k+1,DK>_j)>,1≤i≥n,k≥0z^<k+1,DK>_j=z^k_j-σ^k_jこれらは,D-K法の加速と見倣される.また,SOR型加速として次の反復が考えられる.(IV)SOR型加速:z^<k+1>_i=z^k_i-ω<P(z^k_i)>/<Π__<j<i>(z^k_i-z^<k+1>_j)Π__<j>i>(z^k_i-z^k_j)>,(6)1≤i≥n,k≥0(V)SOR型加速:z^<k+1>_i=z^k_i-ω<P(z^k_i)>/<Π__<j<i>(z^k_i-z^<k+1,DK>_j)Π__<j>i>(z^k_i-z^k_j)>,1≤i≥n,k≥0 (7)ただし,ωは加速パラメータ.ここでは,これらの反復法について考察し,その収束の様子・反復列の挙動等について数値例を交えて論じる.
一般社団法人情報処理学会の論文
1995-03-15