Ch 5 Power Method -Deflation Technique >原点平移法/ deflation technique k)=AV(k-l) (@希望2/1越小越好 不妨设41>2≥…≥n,且 块定收敛的速度,特别 是|m =(2+xn) 4-4|=|a-(B+pD)|=|(-p)-B How are we supposed to know where p is? 所以求B特征根收 As far as the laws of mathematics refer to reality, they are not certain, and as far as they are certain, they do not refer to reality. Albert Einstein(1879-1955)
Ch.5 Power Method – Deflation Technique ➢ 原点平移法 /* deflation technique */ = − = = n i i k i i k k k A x 1 1 1 ( ) ( 1) 决定收敛的速度，特别 是 | 2 / 1 | 希望 | 2 / 1 | 越小越好。 不妨设 1 > 2 … n，且 | 2 | > | n |。 n 2 1 O p = ( 2 + n ) / 2 思 路 令 B = A − pI ，则有 | I−A | = | I−(B+pI) | = | (−p)I−B | A − p = B。而 ，所以求B的特征根收 敛快。 | | | | | | | | 1 2 1 2 − − p p As far as the laws of mathematics refer to reality, they are not certain, and as far as they are certain, they do not refer to reality. -- Albert Einstein (1879-1955) How are we supposed to know where p is?
Ch5 Power method -Inverse Power method >反幂法/ Inverse Power method* 若A有41|2|A2|2…>14n1|,则A1有元 λ1 对应同样一组特征向量。 A1的主特征根<A的绝对值最小的特征根 Q: How must we compute v(+)=A-v()in every step? A: Solve a linear system ay(ktD=v(k) with a factorized 若知道某一特征根λ的大致位置p,即对任意j≠i 思有4-p|<|4-P|,并且如果(-p)存在,则 路可以用反幂法求A-p)的主特征根1(x-p),收 敛将非常快
➢ 反幂法 /* Inverse Power Method */ Ch.5 Power Method –Inverse Power Method 若 A 有| 1 | | 2 | … > | n |，则 A−1 有 对应同样一组特征向量。 1 1 1 1 1 > … n n− A−1 的主特征根 A的绝对值最小的特征根 Q: How must we compute in every step? (k 1) 1 (k ) A + − = A: Solve a linear system with A factorized. (k 1) (k ) A = + 若知道某一特征根 i 的大致位置 p ，即对任意 j i 有| i − p | << | j − p | ，并且如果 (A − pI) −1存在，则 可以用反幂法求(A − pI) −1的主特征根 1/(i − p ) ，收 敛将非常快。 思 路
Ch 5 Power method -Inverse power method Lab 09. Approximating Eigenvalues Approximate an eigenvalue and an associated eigenvector of a given nxn matrix A near a given value p and a nonzero vector=(x,,,n) put There are several sets of inputs. For each set: aIn The 1st line contains an integer100≥n≥0 which21、0n is the size of a matrix. n=-l signals the end of file The following n lines contain the matrix entries in the format shown: The next line contains a real number Tol. which is the tolerance for eigenvalues, and an integer N20 which is the maximum number of iterations. The next line contains an integer n2 m>0 which is the number of eigenvalues to be approximated. Each of the following m lines contains a real number p which is an initial approximation of the eigenvalue, followed by n real number entries of the nonzero vector x=(x1,…,xn The numbers are separated by spaces and new lines. The inputs guarantee that the shifted matrix can be factorized by doolittle method
Ch.5 Power Method –Inverse Power Method Lab 09. Approximating Eigenvalues Approximate an eigenvalue and an associated eigenvector of a given nn matrix A near a given value p and a nonzero vector . Input There are several sets of inputs. For each set: The 1 st line contains an integer 100 n 0 which is the size of a matrix. n = −1 signals the end of file. The following n lines contain the matrix entries in the format shown: The next line contains a real number TOL, which is the tolerance for eigenvalues, and an integer N 0 which is the maximum number of iterations. The next line contains an integer n m > 0 which is the number of eigenvalues to be approximated. Each of the following m lines contains a real number p which is an initial approximation of the eigenvalue, followed by n real number entries of the nonzero vector . The numbers are separated by spaces and new lines. The inputs guarantee that the shifted matrix can be factorized by Doolittle method. n nn n n a a a a a a ... ... ... ... ... ... 1 21 2 11 1 T x x xn ( , ..., ) = 1 T x x xn ( , ..., ) = 1
Ch5 Power Method -Inverse Power Method Output( represents a space) For each p, there must be a set of outputs in the following format The ist line contains the approximation of an eigenvalue printed as in the c printe: fprintf(outfile, %128f\n", lambda ) The 2nd line contains the n entries of the associated eigenvector each entry is printed as in the c fprintf: fprintf(outfile %12. 8f",x); If the method fails to give a solution after N iterations, print the message “ Maximun■ number■of■ iterations■ exceeded.lni If p is just the accurate eigenvalue, print the message printf(outfile,“%12.8f■is■an■ eigenvalue.n”,p); The outputs of two test cases must be seperated by a blank line. Sample Input Sample output 1■2■ 0.62347538 2■3■4 ■1.00000000■■■0.17206558■■-0.65586885■ 3■4■5 0.0000000001■1000 ■■1.0000000is■an■ eigenvalue 0.6■1■1■1 0■1 1■0 0.0000000001■10 1.0■1■1
Ch.5 Power Method –Inverse Power Method Output ( represents a space) For each p, there must be a set of outputs in the following format: • The 1 st line contains the approximation of an eigenvalue printed as in the C printf: fprintf(outfile, "%12.8f\n", lambda ); • The 2 nd line contains the n entries of the associated eigenvector. Each entry is printed as in the C fprintf: fprintf(outfile, "%12.8f", x ); • If the method fails to give a solution after N iterations, print the message “Maximumnumberof iterationsexceeded.\n”. • If p is just the accurate eigenvalue, print the message fprintf(outfile, “%12.8fisaneigenvalue.\n” , p ); The outputs of two test cases must be seperated by a blank line. Sample Input 3 123 234 345 0.00000000011000 1 –0.6111 2 01 10 0.000000000110 1 1.011 –1 Sample Output –0.62347538 1.000000000.17206558–0.65586885 1.00000000isaneigenvalue