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 有对应同样一组特征向量。
11
111
…nn
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
31?2?3
2?3?4
3?4?5
0.0000000001?1000
1
–0.6?1?1?1
2
0?1
1?00.0000000001?10
1
1.0?1?1–1
Sample Output
–0.62347538
1.000000000.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 有对应同样一组特征向量。
11
111
…nn
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
31?2?3
2?3?4
3?4?5
0.0000000001?1000
1
–0.6?1?1?1
2
0?1
1?00.0000000001?10
1
1.0?1?1–1
Sample Output
–0.62347538
1.000000000.17206558–0.65586885?
1.00000000?is?an?eigenvalue.
