Ch.5 Power Method – Deflation Technique
? 原点平移法 /* deflation technique */
?
?
? ?
?
??
?
??? n
i
i
k
iikkk xA
1 1
1
)1()( ??? ??????
决定收敛的速度，特别
是 | ?2 / ?1 |
希望 | ?2 / ?1 | 越小越好。
不妨设 ?1 > ?2 ? … ? ?n,且 | ?2 | > | ?n |。
?1 ?2 ?n
O p = ( ?2 + ?n ) / 2
思
路
令 B = A ? pI,则有 | ?I?A | = | ?I?(B+pI) | = | (??p)I?B |
? ?A ? p = ?B 。 而,所以求 B的特征根收
敛快。 ||
|||| ||
1
2
1
2 ???? ??? pp
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?
? 反幂法 /* 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? )(1)1( kk A ?? ?? ?? ?
A,Solve a linear system with A factorized,)()1( kkA ?? ?? ??
若知道某一特征根 ?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
n?n matrix A near a given value p and a nonzero vector,
Input
There are several sets of inputs,For each set,
The 1st 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,
nnn
n
n
aa
aa
aa
.,,
.,,.,,.,,
.,,
.,,
1
221
111
Tnxxx )...,,( 1??
Tnxxx )...,,( 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 1st line contains the approximation of an eigenvalue printed as in the C
printf,fprintf(outfile,"%12.8f\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
,Maximum?number?of? iterations?exceeded.\n”,
? If p is just the accurate eigenvalue,print the message
fprintf(outfile,,%12.8f?is?an?eigenvalue.\n”,p );
The outputs of two test cases must be seperated by a blank line,
Sample Input
3 1?2?3
2?3?4
3?4?5
0.0000000001?1000
1
–0.6?1?1?1
2
0?1
1?0 0.0000000001?10
1
1.0?1?1 –1
Sample Output
?–0.62347538
??1.00000000???0.17206558??–0.65586885?
??1.00000000?is?an?eigenvalue,
? 原点平移法 /* deflation technique */
?
?
? ?
?
??
?
??? n
i
i
k
iikkk xA
1 1
1
)1()( ??? ??????
决定收敛的速度，特别
是 | ?2 / ?1 |
希望 | ?2 / ?1 | 越小越好。
不妨设 ?1 > ?2 ? … ? ?n,且 | ?2 | > | ?n |。
?1 ?2 ?n
O p = ( ?2 + ?n ) / 2
思
路
令 B = A ? pI,则有 | ?I?A | = | ?I?(B+pI) | = | (??p)I?B |
? ?A ? p = ?B 。 而,所以求 B的特征根收
敛快。 ||
|||| ||
1
2
1
2 ???? ??? pp
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?
? 反幂法 /* 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? )(1)1( kk A ?? ?? ?? ?
A,Solve a linear system with A factorized,)()1( kkA ?? ?? ??
若知道某一特征根 ?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
n?n matrix A near a given value p and a nonzero vector,
Input
There are several sets of inputs,For each set,
The 1st 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,
nnn
n
n
aa
aa
aa
.,,
.,,.,,.,,
.,,
.,,
1
221
111
Tnxxx )...,,( 1??
Tnxxx )...,,( 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 1st line contains the approximation of an eigenvalue printed as in the C
printf,fprintf(outfile,"%12.8f\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
,Maximum?number?of? iterations?exceeded.\n”,
? If p is just the accurate eigenvalue,print the message
fprintf(outfile,,%12.8f?is?an?eigenvalue.\n”,p );
The outputs of two test cases must be seperated by a blank line,
Sample Input
3 1?2?3
2?3?4
3?4?5
0.0000000001?1000
1
–0.6?1?1?1
2
0?1
1?0 0.0000000001?10
1
1.0?1?1 –1
Sample Output
?–0.62347538
??1.00000000???0.17206558??–0.65586885?
??1.00000000?is?an?eigenvalue,
