Chebyshev迭代和共軛梯度方法的收斂速度（后者或稱誤差分析）都與Chebyshev多項式有著緊密聯系，因此做一些整理，以期把其中的邏輯理清，推導理順，只覆寫關鍵要點，不求面面俱到，

Chebyshev 多項式

標準Chebyshev多項式

與權函式 ρ ( y ) = 1 1 ? y 2 \rho(y)=\frac{1}{\sqrt{1-y^2}} ρ(y)=1?y2 ?1?對應的正交多項式為Chebyshev多項式，標準的Chebyshev多項式分兩段定義：
T n ( y ) = { c o s ( n arccos ? ( y ) ) , y ∈ [ ? 1 , 1 ] 1 2 [ ( y + y 2 ? 1 ) n + ( y ? y 2 ? 1 ) n ] , y ∈ R ? [ ? 1 , 1 ] T_n(y)=\left\{ \begin{aligned} &\mathrm{cos}(n\space\arccos(y)) &\space, y\in [-1,1]\\ &\frac{1}{2}\left[\left(y+\sqrt{y^2-1}\right)^n+\left(y-\sqrt{y^2-1}\right)^n\right] &\space, y \in \mathbf{R} \setminus [-1,1] \end{aligned} \right. Tn?(y)=?????cos(n arccos(y))21?[(y+y2?1 ?)n+(y?y2?1 ?)n]? ,y∈[?1,1] ,y∈R?[?1,1]?

概述一些基本性質， n n n次的Chebyshev多項式在開區間 ( ? 1 , 1 ) (-1,1) (?1,1)內有 n n n個零點，在 [ ? 1 , 1 ] [-1,1] [?1,1]內有 n + 1 n+1 n+1個符號交錯的極值點（ ? 1 -1 ?1和 + 1 +1 +1交替），Chebyshev多項式不是奇函式就是偶函式，且隨 n n n交替變化，

對于任意位置區間 [ a , b ] [a,b] [a,b]的Chebyshev多項式，都可以通過平移和縮放來化為標準區間 [ ? 1 , 1 ] [-1,1] [?1,1]上的標準Chebyshev多項式，對于 x ∈ [ a , b ] x\in[a,b] x∈[a,b]，做變換 y = x ? 1 2 ( b + a ) 1 2 ( b ? a ) y=\frac{x-\frac{1}{2}(b+a)}{\frac{1}{2}(b-a)} y=21?(b?a)x?21?(b+a)?，即有 y ∈ [ ? 1 , 1 ] y\in[-1,1] y∈[?1,1]：
T n ~ ( x ) = T n ( y = x ? 1 2 ( b + a ) 1 2 ( b ? a ) ) \widetilde{T_n}(x)=T_n\left(y=\frac{x-\frac{1}{2}(b+a)}{\frac{1}{2}(b-a)}\right) Tn? ?(x)=Tn?(y=21?(b?a)x?21?(b+a)?)
相應地，權函式也做變換：
ρ ~ ( x ) = ρ ( y = x ? 1 2 ( b + a ) 1 2 ( b ? a ) ) = 1 1 ? ( x ? 1 2 ( b + a ) 1 2 ( b ? a ) ) 2 \widetilde{\rho}(x)=\rho\left(y=\frac{x-\frac{1}{2}(b+a)}{\frac{1}{2}(b-a)}\right)= \frac{1}{\sqrt{1-\left( \frac{x-\frac{1}{2}(b+a)}{\frac{1}{2}(b-a)} \right)^2}} ρ ?(x)=ρ(y=21?(b?a)x?21?(b+a)?)=1?(21?(b?a)x?21?(b+a)?)2 ?1?

三項遞推關系

記 θ = a r c c o s y \theta=\mathrm{arccos}y θ=arccosy，利用和差化積公式有
cos ? ( ( n + 1 ) θ ) + cos ? ( ( n ? 1 ) θ ) = 2 cos ? ( n θ ) cos ? ( θ ) \cos((n+1)\theta)+\cos((n-1)\theta)=2\cos(n\theta)\cos(\theta) cos((n+1)θ)+cos((n?1)θ)=2cos(nθ)cos(θ)
故有
T n + 1 ( y ) = 2 y T n ( y ) ? T n ? 1 ( y ) T_{n+1}(y)=2yT_n(y)-T_{n-1}(y) Tn+1?(y)=2yTn?(y)?Tn?1?(y)

逼近性質

對之前提到的定義在 x ∈ [ a , b ] x\in[a,b] x∈[a,b]上的Chebyshev多項式，按照區間外一點 c ? [ a , b ] c\notin[a,b] c∈/?[a,b]來做歸一化：
T n ^ ( x ) = T n ~ ( x ) T n ~ ( c ) \widehat{T_n}(x)=\frac{\widetilde{T_n}(x)}{\widetilde{T_n}(c)} Tn? ?(x)=Tn? ?(c)Tn? ?(x)?
顯然有 T n ^ ( x ) ∈ Φ n , c = { f ∈ P ∣ f ( c ) = 1 } \widehat{T_n}(x)\in\Phi_{n,c}=\{f\in\mathbf{P}\space|\space f(c)=1 \} Tn? ?(x)∈Φn,c?={f∈P ∣ f(c)=1}，后者表示所有在 c c c這一點值為1的 n n n次多項式的集合，Chebyshev多項式具有如下的逼近性質，
∣ ∣ T n ^ ( x ) ∣ ∣ C [ a , b ] = inf ? f ∈ Φ n , c ∣ ∣ f ∣ ∣ C [ a , b ] ||\widehat{T_n}(x)||_{C[a,b]}={\underset {f\in\Phi_{n,c}}{\operatorname {inf} }} ||f||_{C[a,b]} ∣∣Tn? ?(x)∣∣C[a,b]?=f∈Φn,c?inf?∣∣f∣∣C[a,b]?
即所有在 c c c這一點值為1的多項式里，Chebyshev多項式是取到最小范數的那一個，由有限維空間內范數的等價性，從無窮范數入手證明，

首先說明 T n ^ ( x ) \widehat{T_n}(x) Tn? ?(x)是well-defined的，因為 T n ( y ) T_n(y) Tn?(y)的零點都在開區間 ( ? 1 , 1 ) (-1,1) (?1,1)內，因此平移和縮放后 T n ~ ( x ) \widetilde{T_n}(x) Tn? ?(x)的零點都在 [ a , b ] [a,b] [a,b]內， T n ~ ( c ) ≠ 0 \widetilde{T_n}(c)\neq0 Tn? ?(c)?=0，

反證法，假設 Y n ∈ Φ n , c Y_n\in\Phi_{n,c} Yn?∈Φn,c?，且滿足 ∣ ∣ Y n ∣ ∣ C [ a , b ] < ∣ ∣ T n ^ ∣ ∣ C [ a , b ] ||Y_n||_{C[a,b]}<||\widehat{T_n}||_{C[a,b]} ∣∣Yn?∣∣C[a,b]?<∣∣Tn? ?∣∣C[a,b]?，則對于 z n ( x ) = T n ^ ( x ) ? Y n ( x ) z_n(x)=\widehat{T_n}(x)-Y_n(x) zn?(x)=Tn? ?(x)?Yn?(x)，它有一個零點是 c c c，

對于標準Chebyshev多項式 T n y T_n{y} Tn?y，在 [ ? 1 , 1 ] [-1,1] [?1,1]上的（交錯）極值點為 cos ? ( k π n ) , k = 0 , 1 , . . . , n \cos(\frac{k\pi}{n}), k=0,1,...,n cos(nkπ?),k=0,1,...,n，所以 T n ~ ( x ) \widetilde{T_n}(x) Tn? ?(x)在 [ a , b ] [a,b] [a,b]上的（交錯）極值點為 x k = b + a 2 + b ? a 2 cos ? ( k π n ) , k = 0 , 1 , . . . , n x_k=\frac{b+a}{2}+\frac{b-a}{2}\cos(\frac{k\pi}{n}), k=0,1,...,n xk?=2b+a?+2b?a?cos(nkπ?),k=0,1,...,n，因為 ∣ ∣ Y n ( x ) ∣ ∣ C [ a , b ] < ∣ ∣ T n ^ ( x ) ∣ ∣ C [ a , b ] ||Y_n(x)||_{C[a,b]}<||\widehat{T_n}(x)||_{C[a,b]} ∣∣Yn?(x)∣∣C[a,b]?<∣∣Tn? ?(x)∣∣C[a,b]?，那么自然有
∣ Y n ( x k ) ∣ ≤ ∣ ∣ Y n ( x ) ∣ ∣ C [ a , b ] < ∣ ∣ T n ^ ( x ) ∣ ∣ C [ a , b ] = ∣ T n ^ ( x k ) ∣ , k = 0 , 1 , . . . , n |Y_n(x_k)|\leq||Y_n(x)||_{C[a,b]}<||\widehat{T_n}(x)||_{C[a,b]}=|\widehat{T_n}(x_k)|\space, k=0,1,...,n ∣Yn?(xk?)∣≤∣∣Yn?(x)∣∣C[a,b]?<∣∣Tn? ?(x)∣∣C[a,b]?=∣Tn? ?(xk?)∣ ,k=0,1,...,n
所以 T n ^ ( x k ) \widehat{T_n}(x_k) Tn? ?(xk?)與 T n ^ ( x k ) ? Y n ( x k ) \widehat{T_n}(x_k)-Y_n(x_k) Tn? ?(xk?)?Yn?(xk?)同號！而 { x k } \{x_k\} {xk?}是 T n ^ ( x ) \widehat{T_n}(x) Tn? ?(x)的一組符號交錯點，那么也是 T n ^ ( x ) ? Y n ( x ) \widehat{T_n}(x)-Y_n(x) Tn? ?(x)?Yn?(x)的一組符號交錯點，所以在開區間 ( x k , x k + 1 ) (x_k,x_{k+1}) (xk?,xk+1?)中必至少有 z n ( x ) z_n(x) zn?(x)的一個零點，則 ( a , b ) (a,b) (a,b)內至少有 z n ( x ) z_n(x) zn?(x)的 n n n個不同零點，

加上前述的 c ? [ a , b ] c\notin[a,b] c∈/?[a,b]也是 z n ( x ) z_n(x) zn?(x)的一個零點，故它至少有 n + 1 n+1 n+1個零點，這與它是 n n n次多項式矛盾，證畢，

再來估計 ∣ ∣ T n ^ ( x ) ∣ ∣ C [ a , b ] = inf ? f ∈ Φ n , c ∣ ∣ f ∣ ∣ C [ a , b ] ||\widehat{T_n}(x)||_{C[a,b]}={\underset {f\in\Phi_{n,c}}{\operatorname {inf} }} ||f||_{C[a,b]} ∣∣Tn? ?(x)∣∣C[a,b]?=f∈Φn,c?inf?∣∣f∣∣C[a,b]?的大小，
∣ ∣ T n ^ ( x ) ∣ ∣ C [ a , b ] = ∣ ∣ T n ~ ( x ) T n ~ ( c ) ∣ ∣ C [ a , b ] = ∣ ∣ T n ~ ( x ) ∣ ∣ C [ a , b ] ∣ T n ~ ( c ) ∣ = 1 ∣ T n ~ ( c ) ∣ ||\widehat{T_n}(x)||_{C[a,b]}=\left|\left|\frac{\widetilde{T_n}(x)}{\widetilde{T_n}(c)}\right|\right|_{C[a,b]}= \frac{||\widetilde{T_n}(x)||_{C[a,b]}}{|\widetilde{T_n}(c)|}= \frac{1}{|\widetilde{T_n}(c)|} ∣∣Tn? ?(x)∣∣C[a,b]?=∣∣∣∣∣?∣∣∣∣∣?Tn? ?(c)Tn? ?(x)?∣∣∣∣∣?∣∣∣∣∣?C[a,b]?=∣Tn? ?(c)∣∣∣Tn? ?(x)∣∣C[a,b]??=∣Tn? ?(c)∣1?
而
T n ~ ( c ) = T n ( c ? b + a 2 b ? a 2 ) = T n ( ? ( b ? c ) + ( a ? c ) 2 ( b ? c ) ? ( a ? c ) 2 ) = ( ? 1 ) n T n ( ( b ? c ) + ( a ? c ) ( b ? c ) ? ( a ? c ) ) \widetilde{T_n}(c)= T_n\left(\frac{c-\frac{b+a}{2}}{\frac{b-a}{2}} \right)= T_n\left(\frac{-\frac{(b-c)+(a-c)}{2}}{\frac{(b-c)-(a-c)}{2}} \right)= (-1)^nT_n\left( \frac{(b-c)+(a-c)}{(b-c)-(a-c)} \right) Tn? ?(c)=Tn?(2b?a?c?2b+a??)=Tn?(2(b?c)?(a?c)??2(b?c)+(a?c)??)=(?1)nTn?((b?c)?(a?c)(b?c)+(a?c)?)
所以
∣ T n ~ ( c ) ∣ = T n ( ∣ ( b ? c ) + ( a ? c ) ( b ? c ) ? ( a ? c ) ∣ ) = T n ( λ + 1 λ ? 1 ) |\widetilde{T_n}(c)|= T_n\left(\left| \frac{(b-c)+(a-c)}{(b-c)-(a-c)} \right|\right)= T_n\left(\frac{\lambda+1}{\lambda-1} \right) ∣Tn? ?(c)∣=Tn?(∣∣∣∣?(b?c)?(a?c)(b?c)+(a?c)?∣∣∣∣?)=Tn?(λ?1λ+1?)
其中 λ = max ? ( ∣ a ? c ∣ ∣ b ? c ∣ , ∣ b ? c ∣ ∣ a ? c ∣ ) > 1 \lambda=\max(\frac{|a-c|}{|b-c|},\frac{|b-c|}{|a-c|})>1 λ=max(∣b?c∣∣a?c∣?,∣a?c∣∣b?c∣?)>1，所以根據標準Chebyshev多項式在 [ ? 1 , 1 ] [-1,1] [?1,1]區間外的運算式，有
T n ( λ + 1 λ ? 1 ) ≥ 1 2 [ λ + 1 λ ? 1 + ( λ + 1 λ ? 1 ) 2 ? 1 ] n = 1 2 ( λ + 1 λ ? 1 ) n T_n\left(\frac{\lambda+1}{\lambda-1} \right)\geq \frac{1}{2}\left[ \frac{\lambda+1}{\lambda-1}+\sqrt{ \left(\frac{\lambda+1}{\lambda-1}\right)^2-1 } \right]^n= \frac{1}{2}\left(\frac{\sqrt{\lambda}+1}{\sqrt{\lambda}-1}\right)^n Tn?(λ?1λ+1?)≥21????λ?1λ+1?+(λ?1λ+1?)2?1 ????n=21?(λ ??1λ ?+1?)n
所以最后得到的估計是
∣ ∣ T n ^ ( x ) ∣ ∣ C [ a , b ] = 1 ∣ T n ~ ( c ) ∣ = 1 T n ( λ + 1 λ ? 1 ) ≤ 2 ( λ ? 1 λ + 1 ) n ||\widehat{T_n}(x)||_{C[a,b]}= \frac{1}{|\widetilde{T_n}(c)|}= \frac{1}{T_n\left(\frac{\lambda+1}{\lambda-1} \right)}\leq 2\left(\frac{\sqrt{\lambda}-1}{\sqrt{\lambda}+1}\right)^n ∣∣Tn? ?(x)∣∣C[a,b]?=∣Tn? ?(c)∣1?=Tn?(λ?1λ+1?)1?≤2(λ ?+1λ ??1?)n
并且這個估計是較緊湊的，將會在Chebyshev迭代和共軛梯度的收斂速度分析中用到這個結論，

Chebyshev迭代

Chebyshev迭代是線性非定常迭代，其迭代使用的矩陣/系數在每個迭代步都會發生變化，而任意的單步線性定常迭代都可以表述為最簡單的Richardson迭代+預處理的組合，因此從Richardson迭代出發，引入Krylov子空間的概念，然后加以適當改造得到Chebyshev迭代，

Richardson迭代和Krylov子空間

Richardson迭代是最簡單的迭代格式，它在每一步都加上一個修正量，此修正量就簡單地取為當前迭代結果的殘差：
x ( i + 1 ) = x ( i ) + r ( i ) = x ( i ) + b ? A x ( i ) = ( I ? A ) x ( i ) + b \bm{x}^{(i+1)}=\bm{x}^{(i)}+\bm{r}^{(i)}=\bm{x}^{(i)}+\bm{b}-\bm{A}\bm{x}^{(i)}=(\bm{I}-\bm{A})\bm{x}^{(i)}+\bm{b} x(i+1)=x(i)+r(i)=x(i)+b?Ax(i)=(I?A)x(i)+b
r ( i + 1 ) = b ? A x ( i + 1 ) = b ? A x ( i ) ? A r ( i ) = ( I ? A ) r ( i ) = . . . = ( I ? A ) i + 1 r ( 0 ) \bm{r}^{(i+1)}=\bm{b}-\bm{A}\bm{x}^{(i+1)}=\bm{b}-\bm{A}\bm{x}^{(i)}-\bm{A}\bm{r}^{(i)} =(\bm{I}-\bm{A})\bm{r}^{(i)}=...=(\bm{I}-\bm{A})^{i+1}\bm{r}^{(0)} r(i+1)=b?Ax(i+1)=b?Ax(i)?Ar(i)=(I?A)r(i)=...=(I?A)i+1r(0)
由殘差與誤差的關系有 e ( i ) = A ? 1 r ( i ) \bm{e}^{(i)}=\bm{A}^{-1}\bm{r}^{(i)} e(i)=A?1r(i)，可知相應有 e ( i + 1 ) = ( I ? A ) e ( i ) \bm{e}^{(i+1)}=(\bm{I}-\bm{A})\bm{e}^{(i)} e(i+1)=(I?A)e(i)，于是在第 m m m步得到的迭代結果為
x ( m ) = x ( 0 ) + ∑ i = 0 m ? 1 r ( i ) = x ( 0 ) + ∑ i = 0 m ? 1 ( I ? A ) i r ( 0 ) ∈ x ( 0 ) + K m ( r ( 0 ) ) \bm{x}^{(m)}=\bm{x}^{(0)}+\sum_{i=0}^{m-1}\bm{r}^{(i)}=\bm{x}^{(0)}+\sum_{i=0}^{m-1}(\bm{I}-\bm{A})^{i}\bm{r}^{(0)}\in\bm{x}^{(0)}+\bm{K_m}(\bm{r}^{(0)}) x(m)=x(0)+i=0∑m?1?r(i)=x(0)+i=0∑m?1?(I?A)ir(0)∈x(0)+Km?(r(0))
其中 K m ( r ( 0 ) ) \bm{K_m}(\bm{r}^{(0)}) Km?(r(0))是由 r ( 0 ) \bm{r}^{(0)} r(0)生成的Krylov子空間，其中的元素是用 A \bm{A} A反復作用于 r ( 0 ) \bm{r}^{(0)} r(0)得到的 r ( 0 ) , A r ( 0 ) , A 2 r ( 0 ) , . . . \bm{r}^{(0)},\bm{Ar}^{(0)},\bm{A^2r}^{(0)},... r(0),Ar(0),A2r(0),...等的線性組合，

任何的單步定常迭代格式，比如給定 A = M ? N \bm{A}=\bm{M}-\bm{N} A=M?N，其中 M \bm{M} M為預處理矩陣，則迭代可以寫成
x ( i + 1 ) = M ? 1 N x ( i ) + M ? 1 b = M ? 1 ( M ? A ) x ( i ) + M ? 1 b \bm{x}^{(i+1)}=\bm{M}^{-1}\bm{N}\bm{x}^{(i)}+\bm{M}^{-1}\bm{b}=\bm{M}^{-1}(\bm{M}-\bm{A})\bm{x}^{(i)}+\bm{M}^{-1}\bm{b} x(i+1)=M?1Nx(i)+M?1b=M?1(M?A)x(i)+M?1b
而對 A x = b \bm{Ax}=\bm{b} Ax=b做預處理后得到的 M ? 1 A x = M ? 1 b \bm{M^{-1}Ax}=\bm{M^{-1}b} M?1Ax=M?1b，再進行Richardson迭代，可以得到
x ( i + 1 ) = x ( i ) + r ( i ) = x ( i ) + M ? 1 b ? M ? 1 A x ( i ) \bm{x}^{(i+1)}=\bm{x}^{(i)}+\bm{r}^{(i)}=\bm{x}^{(i)}+\bm{M^{-1}b}-\bm{M^{-1}}\bm{A}\bm{x}^{(i)} x(i+1)=x(i)+r(i)=x(i)+M?1b?M?1Ax(i)
可見是等價的，所以任何的單步定常迭代形式都可以寫成預處理后的Richardson迭代（即當前迭代值+修正量）的形式，

單步迭代格式

原始的Richardson迭代是最簡單地取了 M = I \bm{M}=\bm{I} M=I（最好計算，但最不好近似）來做預處理，現在采用非定常，即考慮每步迭代不那么naive，而是選用一個與當前步 i i i有關地矩陣 M i \bm{M_i} Mi?做預處理，假設 M i = τ i M \bm{M_i}=\tau_i\bm{M} Mi?=τi?M由同一個矩陣 M \bm{M} M生成，同樣類似Richardson迭代的好計算的想法，取 M = I \bm{M}=\bm{I} M=I，故有 M i = τ i I \bm{M_i}=\tau_i\bm{I} Mi?=τi?I，所以殘量的遞推關系成為
r ( i + 1 ) = ( I ? τ i A ) r ( i ) = ( I ? τ i A ) ( I ? τ i ? 1 A ) . . . ( I ? τ 0 A ) r ( 0 ) \bm{r}^{(i+1)}=(\bm{I}-\tau_i\bm{A})\bm{r}^{(i)}=(\bm{I}-\tau_i\bm{A})(\bm{I}-\tau_{i-1}\bm{A})...(\bm{I}-\tau_0\bm{A})\bm{r}^{(0)} r(i+1)=(I?τi?A)r(i)=(I?τi?A)(I?τi?1?A)...(I?τ0?A)r(0)
對于誤差 e ( i ) \bm{e}^{(i)} e(i)也同樣有此關系，所以有
∣ ∣ e ( i ) ∣ ∣ ∣ ∣ e ( 0 ) ∣ ∣ ≤ ∣ ∣ ( I ? τ i ? 1 A ) . . . ( I ? τ 0 A ) ∣ ∣ \frac{||\bm{e}^{(i)}||}{||\bm{e}^{(0)}||}\leq|| (\bm{I}-\tau_{i-1}\bm{A})...(\bm{I}-\tau_0\bm{A}) || ∣∣e(0)∣∣∣∣e(i)∣∣?≤∣∣(I?τi?1?A)...(I?τ0?A)∣∣
我們希望構造出來的結果（即 τ 0 , τ 1 , . . . \tau_0,\tau_1,... τ0?,τ1?,...等的取值）能使殘量（誤差）收縮得最小，即求解如下的優化問題：
inf ? τ 0 , . . . , τ i ? 1 ∣ ∣ ( I ? τ i ? 1 A ) . . . ( I ? τ 0 A ) ∣ ∣ {\underset {\tau_0,...,\tau_{i-1}} {\operatorname {inf} }} || (\bm{I}-\tau_{i-1}\bm{A})...(\bm{I}-\tau_0\bm{A}) || τ0?,...,τi?1?inf?∣∣(I?τi?1?A)...(I?τ0?A)∣∣
假設 A \bm{A} A是對稱陣（這些強加的適用條件后面匯總來看），那么存在正交陣 P \bm{P} P（如果 A \bm{A} A是Hermite矩陣，則 P \bm{P} P為酉矩陣）使得 A \bm{A} A能相似對角化，且取2-范數時有 ∣ ∣ P ∣ ∣ 2 = 1 ||\bm{P}||_2=1 ∣∣P∣∣2?=1，
A = P d i a g ( λ 1 , λ 2 , . . . , λ n ) P T = P Λ P T \bm{A}=\bm{P} \mathrm{diag}(\lambda_1,\lambda_2,...,\lambda_n)\bm{P}^T=\bm{P}\bm{\Lambda} \bm{P}^T A=Pdiag(λ1?,λ2?,...,λn?)PT=PΛPT
那么有
∣ ∣ ( I ? τ i ? 1 A ) . . . ( I ? τ 0 A ) ∣ ∣ 2 = ∣ ∣ P ( I ? τ i ? 1 Λ ) . . . ( I ? τ 0 Λ ) P T ∣ ∣ 2 = ∣ ∣ ( I ? τ i ? 1 Λ ) . . . ( I ? τ 0 Λ ) ∣ ∣ 2 = max ? λ ∈ σ ( A ) ∣ ( 1 ? τ i ? 1 λ ) . . . ( 1 ? τ 0 λ ) ∣ \begin{aligned} || (\bm{I}-\tau_{i-1}\bm{A})...(\bm{I}-\tau_0\bm{A}) ||_2=& ||\bm{P}(\bm{I}-\tau_{i-1}\bm{\Lambda})...(\bm{I}-\tau_0\bm{\Lambda})\bm{P}^T||_2\\ =&||(\bm{I}-\tau_{i-1}\bm{\Lambda})...(\bm{I}-\tau_0\bm{\Lambda})||_2\\ =&{\underset {\lambda\in\sigma(\bm{A})} {\operatorname {max} }} | (1-\tau_{i-1}\lambda)...(1-\tau_0\lambda)| \\ \end{aligned} ∣∣(I?τi?1?A)...(I?τ0?A)∣∣2?===?∣∣P(I?τi?1?Λ)...(I?τ0?Λ)PT∣∣2?∣∣(I?τi?1?Λ)...(I?τ0?Λ)∣∣2?λ∈σ(A)max?∣(1?τi?1?λ)...(1?τ0?λ)∣?
而 A \bm{A} A的譜是可以估計的，假設已算出 σ ( A ) ∈ [ λ ￣ , λ ˉ ] \sigma(\bm{A})\in[\underline{\lambda},\bar{\lambda}] σ(A)∈[λ?,λˉ]，那么上式可以寫成：
max ? λ ∈ σ ( A ) ∣ ( 1 ? τ i ? 1 λ ) . . . ( 1 ? τ 0 λ ) ∣ ≤ ∣ ∣ ( 1 ? τ i ? 1 λ ) . . . ( 1 ? τ 0 λ ) ∣ ∣ ∞ , [ λ ￣ , λ ˉ ] = ∣ ∣ f ( λ ) ∣ ∣ ∞ , [ λ ￣ , λ ˉ ] \begin{aligned} {\underset {\lambda\in\sigma(\bm{A})} {\operatorname {max} }} | (1-\tau_{i-1}\lambda)...(1-\tau_0\lambda)|&\leq& ||(1-\tau_{i-1}\lambda)...(1-\tau_0\lambda)||_{\infty,[\underline{\lambda},\bar{\lambda}]}\\ &=&||f(\lambda)||_{\infty,[\underline{\lambda},\bar{\lambda}]}\\ \end{aligned} λ∈σ(A)max?∣(1?τi?1?λ)...(1?τ0?λ)∣?≤=?∣∣(1?τi?1?λ)...(1?τ0?λ)∣∣∞,[λ?,λˉ]?∣∣f(λ)∣∣∞,[λ?,λˉ]??
左邊的原式是一個絕對值，現在右邊看成是一個關于 λ \lambda λ的多項式函式 f ( λ ) = ( 1 ? τ i ? 1 λ ) . . . ( 1 ? τ 0 λ ) f(\lambda)=(1-\tau_{i-1}\lambda)...(1-\tau_0\lambda) f(λ)=(1?τi?1?λ)...(1?τ0?λ)的無窮范數，該多項式函式有 i i i個實單根： 1 τ 0 , . . . , 1 τ i ? 1 \frac{1}{\tau_0},...,\frac{1}{\tau_{i-1}} τ0?1?,...,τi?1?1?，

而由之前的結論，定義在 [ λ ￣ , λ ˉ ] [\underline{\lambda},\bar{\lambda}] [λ?,λˉ]上的Chebyshev多項式 T i ^ ( λ ) \widehat{T_i}(\lambda) Ti? ?(λ)在開區間 ( λ ￣ , λ ˉ ) (\underline{\lambda},\bar{\lambda}) (λ?,λˉ)內有 i i i個實單根，且 T i ^ ( λ ) = inf ? P i ∈ P i , P i ( 0 ) = 1 ∣ ∣ P i ∣ ∣ ∞ , [ λ ￣ , λ ˉ ] \widehat{T_i}(\lambda)={\underset {P_i\in\mathbf{P_i},P_i(0)=1}{\operatorname {inf} }} ||P_i||_{\infty,[\underline{\lambda},\bar{\lambda}]} Ti? ?(λ)=Pi?∈Pi?,Pi?(0)=1inf?∣∣Pi?∣∣∞,[λ?,λˉ]?.

注意當 A \bm{A} A為對稱正定陣時， 0 ? [ λ ￣ , λ ˉ ] 0\notin[\underline{\lambda},\bar{\lambda}] 0∈/?[λ?,λˉ]，所以 inf ? P i ∈ P i , P i ( 0 ) = 1 ∣ ∣ P i ∣ ∣ ∞ , [ λ ￣ , λ ˉ ] {\underset {P_i\in\mathbf{P_i},P_i(0)=1}{\operatorname {inf} }} ||P_i||_{\infty,[\underline{\lambda},\bar{\lambda}]} Pi?∈Pi?,Pi?(0)=1inf?∣∣Pi?∣∣∞,[λ?,λˉ]?的下界恰好能被原問題的 f ( λ ) f(\lambda) f(λ)取到，此時
P i ? ( λ ) = T i ^ ( λ ) = T i ~ ( λ ) T i ~ ( 0 ) = T i ( λ ? 1 2 ( λ ˉ + λ ￣ ) 1 2 ( λ ˉ ? λ ￣ ) ) T i ( 0 ? 1 2 ( λ ˉ + λ ￣ ) 1 2 ( λ ˉ ? λ ￣ ) ) = ( 1 ? τ i ? 1 ( i ) λ ) . . . ( 1 ? τ 0 ( i ) λ ) P_i^*(\lambda)=\widehat{T_i}(\lambda)=\frac{\widetilde{T_i}(\lambda)}{\widetilde{T_i}(0)} =\frac{T_i\left( \frac{\lambda-\frac{1}{2}(\bar{\lambda}+\underline{\lambda})} {\frac{1}{2} (\bar{\lambda}-\underline{\lambda})} \right)}{T_i\left( \frac{0-\frac{1}{2}(\bar{\lambda}+\underline{\lambda})} {\frac{1}{2} (\bar{\lambda}-\underline{\lambda})} \right)}= (1-\tau_{i-1}^{(i)}\lambda)...(1-\tau_{0}^{(i)}\lambda) Pi??(λ)=Ti? ?(λ)=Ti? ?(0)Ti? ?(λ)?=Ti?(21?(λˉ?λ?)0?21?(λˉ+λ?)?)Ti?(21?(λˉ?λ?)λ?21?(λˉ+λ?)?)?=(1?τi?1(i)?λ)...(1?τ0(i)?λ)
其中 τ j ( i ) \tau_j^{(i)} τj(i)?的上標表示與迭代次數 i i i有關，所以原問題的 i i i個實單根就是定義在 [ λ ￣ , λ ˉ ] [\underline{\lambda},\bar{\lambda}] [λ?,λˉ]上的Chebyshev多項式的根，單步的迭代格式寫成
x ( 1 ) = x ( 0 ) + τ 0 ( i ) r ( 0 ) . . . x ( j ) = x ( j ? 1 ) + τ j ? 1 ( i ) r ( j ? 1 ) . . . x ( i ) = x ( i ? 1 ) + τ i ? 1 ( i ) r ( i ? 1 ) \begin{aligned} \bm{x}^{(1)}&=&\bm{x}^{(0)}+\tau_0^{(i)}\bm{r}^{(0)}\\ &...&\\ \bm{x}^{(j)}&=&\bm{x}^{(j-1)}+\tau_{j-1}^{(i)}\bm{r}^{(j-1)}\\ &...&\\ \bm{x}^{(i)}&=&\bm{x}^{(i-1)}+\tau_{i-1}^{(i)}\bm{r}^{(i-1)}\\ \end{aligned} x(1)x(j)x(i)?=...=...=?x(0)+τ0(i)?r(0)x(j?1)+τj?1(i)?r(j?1)x(i?1)+τi?1(i)?r(i?1)?

收斂速度

Chebyshev迭代的收斂速度優勢，應當通過進行一次 i i i步的Chebyshev迭代，和進行 i i i次的單步定常迭代來比較，

由Chebyshev的逼近性質，可以得到Chebyshev的迭代收斂速度為
∣ ∣ e ( i ) ∣ ∣ ∣ ∣ e ( 0 ) ∣ ∣ ≤ ∣ ∣ ( 1 ? τ i ? 1 λ ) . . . ( 1 ? τ 0 λ ) ∣ ∣ ∞ , [ λ ￣ , λ ˉ ] = 1 ∣ T i ~ ( 0 ) ∣ = 1 ∣ T i ( 0 ? λ ˉ + λ ￣ 2 λ ˉ ? λ ￣ 2 ) ∣ = 1 ∣ T i ( λ ˉ λ ￣ + 1 λ ˉ λ ￣ ? 1 ) ∣ = 1 ∣ T i ( α + 1 α ? 1 ) ∣ ≤ ≈ 2 ( α ? 1 α + 1 ) i \begin{aligned} \frac{||\bm{e}^{(i)}||}{||\bm{e}^{(0)||}}&\leq&||(1-\tau_{i-1}\lambda)...(1-\tau_0\lambda)||_{\infty,[\underline{\lambda},\bar{\lambda}]}\\ &=&\frac{1}{|\widetilde{T_i}(0)|}=\frac{1}{\left|T_i\left(\frac{0-\frac{\bar{\lambda}+\underline{\lambda}}{2}}{\frac{\bar{\lambda}-\underline{\lambda}}{2}}\right)\right|}\\ &=&\frac{1}{\left| T_i\left( \frac{\frac{\bar{\lambda}}{\underline{\lambda}}+1}{\frac{\bar{\lambda}}{\underline{\lambda}}-1} \right) \right|}=\frac{1}{\left| T_i\left( \frac{\alpha+1}{\alpha-1} \right) \right|}\\ &&\leq\approx2\left( \frac{\sqrt{\alpha}-1}{\sqrt{\alpha}+1} \right)^i \end{aligned} ∣∣e(0)∣∣∣∣e(i)∣∣??≤==?∣∣(1?τi?1?λ)...(1?τ0?λ)∣∣∞,[λ?,λˉ]?∣Ti? ?(0)∣1?=∣∣∣∣?Ti?(2λˉ?λ??0?2λˉ+λ???)∣∣∣∣?1?∣∣∣∣?Ti?(λ?λˉ??1λ?λˉ?+1?)∣∣∣∣?1?=∣∣?Ti?(α?1α+1?)∣∣?1?≤≈2(α ?+1α ??1?)i?
其中 α = λ ˉ λ ￣ > 1 \alpha=\frac{\bar{\lambda}}{\underline{\lambda}}>1 α=λ?λˉ?>1，

而如果做 i i i次單步的定常迭代，每次單步的收斂速度為
P 1 ? ( λ ) = 1 ∣ T 1 ( α + 1 α ? 1 ) ∣ = 1 ∣ α + 1 α ? 1 ∣ = α ? 1 α + 1 P_1^*(\lambda)=\frac{1}{\left| T_1\left( \frac{\alpha+1}{\alpha-1} \right) \right|} = \frac{1}{\left| \frac{\alpha+1}{\alpha-1} \right|} = \frac{\alpha-1}{\alpha+1} P1??(λ)=∣∣?T1?(α?1α+1?)∣∣?1?=∣∣?α?1α+1?∣∣?1?=α+1α?1?
連續做 i i i次以后的收斂速度為 ∣ ∣ e ( i ) ∣ ∣ ∣ ∣ e ( 0 ) ∣ ∣ ≤ ( α ? 1 α + 1 ) i \frac{||\bm{e}^{(i)}||}{||\bm{e}^{(0)||}}\leq\left( \frac{\alpha-1}{\alpha+1}\right)^i ∣∣e(0)∣∣∣∣e(i)∣∣?≤(α+1α?1?)i，這顯然要比Chebyshev迭代的收斂速度慢，

兩步迭代格式

單步的Chebyshev迭代格式的缺點是 τ j ( i ) \tau_j^{(i)} τj(i)?依賴于迭代次數 i i i的取值，自然地想，能不能不依賴于后者的確定？這就可以用上Chebyshev多項式的三項遞推關系來解決！

對標準的Chebyshev多項式， T n + 1 ( y ) = 2 y T n ( y ) ? T n ? 1 ( y ) , . . . , T 1 ( y ) = y , T 0 ( y ) = 1 T_{n+1}(y)=2yT_n(y)-T_{n-1}(y),...,T_1(y)=y,T_0(y)=1 Tn+1?(y)=2yTn?(y)?Tn?1?(y),...,T1?(y)=y,T0?(y)=1，但需要的是定義在 [ λ ￣ , λ ˉ ] [\underline{\lambda}, \bar{\lambda}] [λ?,λˉ]上的Chebyshev多項式，做變換：
T i ~ ( x ) = T i ( y = x ? 1 2 ( λ ˉ + λ ￣ ) 1 2 ( λ ˉ ? λ ￣ ) ) = T i ( y = a x ? y 0 ) \widetilde{T_i}(x)=T_i\left(y=\frac{x-\frac{1}{2}(\bar{\lambda}+\underline{\lambda})}{\frac{1}{2}(\bar{\lambda}-\underline{\lambda})}\right)=T_i(y=ax-y_0) Ti? ?(x)=Ti?(y=21?(λˉ?λ?)x?21?(λˉ+λ?)?)=Ti?(y=ax?y0?)
其中記 y 0 = λ ˉ + λ ￣ λ ˉ ? λ ￣ , a = 2 λ ˉ ? λ ￣ y_0=\frac{\bar{\lambda}+\underline{\lambda}}{\bar{\lambda}-\underline{\lambda}}, a=\frac{2}{\bar{\lambda}-\underline{\lambda}} y0?=λˉ?λ?λˉ+λ??,a=λˉ?λ?2?，按照 x = 0 x=0 x=0這一點的 T i ~ \widetilde{T_i} Ti? ?值做歸一化： T i ^ ( x ) = T i ~ ( x ) T i ~ ( 0 ) = T i ( a x ? y 0 ) T i ( ? y 0 ) = T i ( y 0 ? a x ) T i ( y 0 ) \widehat{T_i}(x)=\frac{\widetilde{T_i}(x)}{\widetilde{T_i}(0)}=\frac{T_i(ax-y_0)}{T_i(-y_0)}=\frac{T_i(y_0-ax)}{T_i(y_0)} Ti? ?(x)=Ti? ?(0)Ti? ?(x)?=Ti?(?y0?)Ti?(ax?y0?)?=Ti?(y0?)Ti?(y0??ax)?，因此三項遞推關系為
T 0 ^ ( x ) = T 0 ( y 0 ? a x ) T 0 ( y 0 ) = 1 T 1 ^ ( x ) = T 1 ( y 0 ? a x ) T 1 ( y 0 ) = y 0 ? a x y 0 = T 0 ^ ( x ) ? a y 0 x T 0 ^ ( x ) . . . . . . T i + 1 ^ ( x ) = T i + 1 ( y 0 ? a x ) T i + 1 ( y 0 ) = 2 ( y 0 ? a x ) T i ( y 0 ? a x ) ? T i ? 1 ( y 0 ? a x ) T i + 1 ( y 0 ) = 2 ( y 0 ? a x ) T i ( y 0 ) T i + 1 ( y 0 ) T i ( y 0 ? a x ) T i ( y 0 ) ? T i ? 1 ( y 0 ) T i + 1 ( y 0 ) T i ? 1 ( y 0 ? a x ) T i ? 1 ( y 0 ) = 2 ( y 0 ? a x ) T i ( y 0 ) T i + 1 ( y 0 ) T i ^ ( x ) ? T i ? 1 ( y 0 ) T i + 1 ( y 0 ) T i ? 1 ^ ( x ) = 2 y 0 T i ( y 0 ) T i + 1 ( y 0 ) T i ^ ( x ) ? T i ? 1 ( y 0 ) T i + 1 ( y 0 ) T i ? 1 ^ ( x ) ? 2 a T i ( y 0 ) T i + 1 ( y 0 ) x T i ^ ( x ) = ( 1 + T i ? 1 ( y 0 ) T i + 1 ( y 0 ) ) T i ^ ( x ) ? T i ? 1 ( y 0 ) T i + 1 ( y 0 ) T i ? 1 ^ ( x ) ? 2 a T i ( y 0 ) T i + 1 ( y 0 ) x T i ^ ( x ) = α i T i ^ ( x ) + ( 1 ? α i ) T i ? 1 ^ ( x ) ? β i x T i ^ ( x ) \widehat{T_0}(x)=\frac{T_0(y_0-ax)}{T_0(y_0)}=1\\ \widehat{T_1}(x)=\frac{T_1(y_0-ax)}{T_1(y_0)}=\frac{y_0-ax}{y_0}=\widehat{T_0}(x)-\frac{a}{y_0}x\widehat{T_0}(x)\\ ... ...\\ \begin{aligned} \widehat{T_{i+1}}(x)&=\frac{T_{i+1}(y_0-ax)}{T_{i+1}(y_0)}=\frac{2(y_0-ax)T_i(y_0-ax)-T_{i-1}(y_0-ax)}{T_{i+1}(y_0)}\\ &=\frac{2(y_0-ax)T_i(y_0)}{T_{i+1}(y_0)} \frac{T_i(y_0-ax)}{T_i(y_0)}-\frac{T_{i-1}(y_0)}{T_{i+1}(y_0)} \frac{T_{i-1}(y_0-ax)}{T_{i-1}(y_0)}\\ &=\frac{2(y_0-ax)T_i(y_0)}{T_{i+1}(y_0)} \widehat{T_i}(x) -\frac{T_{i-1}(y_0)}{T_{i+1}(y_0)} \widehat{T_{i-1}}(x)\\ &=\frac{2y_0T_i(y_0)}{T_{i+1}(y_0)} \widehat{T_i}(x) -\frac{T_{i-1}(y_0)}{T_{i+1}(y_0)} \widehat{T_{i-1}}(x)-2a\frac{T_i(y_0)}{T_{i+1}(y_0)}x\widehat{T_i}(x)\\ &=\left( 1+\frac{T_{i-1}(y_0)}{T_{i+1}(y_0)} \right) \widehat{T_i}(x) - \frac{T_{i-1}(y_0)}{T_{i+1}(y_0)}\widehat{T_{i-1}}(x) -2a\frac{T_i(y_0)}{T_{i+1}(y_0)}x\widehat{T_i}(x)\\ &=\alpha_i\widehat{T_i}(x) + (1-\alpha_i)\widehat{T_{i-1}}(x) - \beta_ix\widehat{T_i}(x) \end{aligned} T0? ?(x)=T0?(y0?)T0?(y0??ax)?=1T1? ?(x)=T1?(y0?)T1?(y0??ax)?=y0?y0??ax?=T0? ?(x)?y0?a?xT0? ?(x)......Ti+1? ?(x)?=

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/402466.html

標籤：其他

上一篇：第五章：排序演算法

下一篇：個人黑名單 抄襲恥辱墻