回顾与补充 Richardson iteration 一两个视角：矩阵多项式、梯度最速下降 一思考：如果换作其它范数下面的最速下降？ - 收敛性：当且仅当p(I-aA)=max{1-a元1l,|1-anl}<1 -记xk=pk(A)b∈Span{b,Ab,A2b,,Ak-1b}:Krylov子空间 -x.-xk=(I-pk(A)A)x.=qk(A)x. 一收敛所需迭代次数正比于条件数 Conjugate gradients(共轭梯度方法) -记Krylov-子空间K0={0,K:=span{b,Ab,.Ai-1b} -xi=arg minx∈K,lx-x*l☑，其中x满足Ax*=b C6的收敛所需选代次数正比于层依然取决于条件数 - 精确数值：最多迭代+1次；有限精度：也需要选择合适的停止条件 对稀疏矩阵，或者有好的初始猜测时，迭代比高斯消元更加适合 2 回顾与补充 • Richardson iteration – 两个视角：矩阵多项式、梯度最速下降 – 思考：如果换作其它范数下面的最速下降？ – 收敛性：当且仅当� � − �� = max{ 1 − ��! , 1 − ��" } < � – 记�� = �� � � ∈ ���� �,��,���, … ,��#�� ；Krylov子空间 – �∗ − �� = � − �� � � �∗ = �� � �∗ – 收敛所需迭代次数正比于条件数�� �� • Conjugate gradients （共轭梯度方法） – 记Krylov子空间�� = � , �� = ���� �, ��, … ��#�� – �� = ��� ����∈�� � − �∗ � � ，其中�∗满足��∗ = � – CG的收敛所需迭代次数正比于 �� �� ，依然取决于条件数 – 精确数值：最多迭代n+1次；有限精度：也需要选择合适的停止条件 • 对稀疏矩阵，或者有好的初始猜测时，迭代比高斯消元更加适合 2