南京大学：《计算方法 Numerical method》课程教学资源（课件讲稿）解线性方程组的直接和迭代方法、条件数、算子范数（operator norm）

回顾 上节课： ·离散傅里叶变换 ·三角级数近似 2

回顾 上节课： • 离散傅里叶变换 • 三角级数近似 2

傅里叶变换的矩阵表达形式 给定{aj},求{p(ω)} pa)=∑e ωj p(x)= ax! j=0 i=0 ao p(ω) wo @1 … wn p(w1) wn an p(on) 注意：对复数向量的内积，通常需要取共轭复数后再做内积 单位根的共轭复数w→w-1,这对应于Hermitian 对复数矩阵A,“正交”的正确定义是指Unitary:AHA=I 3

傅里叶变换的矩阵表达形式 3 �(�! ) = & "#$ % �"�!" � � = $ !"# $ �!�! �# �# �# �% ⋯ ⋯ �# �$ ⋮ ⋮ ⋱ ⋮ �# �$ ⋯ �$! �# �% ⋮ �$ = �(�#) �(�%) ⋮ �(�$) 注意：对复数向量的内积，通常需要取共轭复数后再做内积 单位根的共轭复数� → �&%，这对应于Hermitian 对复数矩阵 � ，“正交”的正确定义是指Unitary：�'� = � 给定 {�!}，求 � �(

傅里叶逆变换的矩阵表达形式 给定{p(w)},求{a} 1 ∑p(u)aw-i p(x)= n+1 j=0 i=0 0 wO QO p(ω) ao w1 wo 0… w-n p(ω2) a1 n+1 )0 w-n w-n2 p(wn) 注意：对复数向量的内积，通常需要取共轭复数后再做内积 单位根的共轭复数w→w-1,这对应于Hermitian 对复数矩阵A,“正交”的正确定义是指Unitary:AHA=I 4

傅里叶逆变换的矩阵表达形式 4 �! = 1 � + 1& "#$ % � �" �&!" � � = $ !"# $ �!�! % $)% �# �# �# �&% ⋯ ⋯ �# �&$ ⋮ ⋮ ⋱ ⋮ �# �&$ ⋯ �&$! �(�#) �(�%) ⋮ �(�$) = �# �% ⋮ �$ 注意：对复数向量的内积，通常需要取共轭复数后再做内积 单位根的共轭复数� → �&%，这对应于Hermitian 对复数矩阵 � ，“正交”的正确定义是指Unitary：�'� = � 给定 � �( ，求{�!}

傅里叶变换的矩阵表达形式 为什么这是一个逆变换？ wO wo O 0 -1 w-n w1 . an =(n+1)1 w-n w-n2 0 wn … 2 考虑乘积的(i,)位置上的元素 1-o(n+1)0-i) n+1 n+1 j≠i ωk0-0= 1-wj-i, n+1, j=i 注意：对复数向量的内积，通常需要取共轭复数后再做内积 单位根的共轭复数w→w-1,这对应于Hermitian 对复数矩阵A,“正交”的正确定义是指Unitary:AHA=I 5

傅里叶变换的矩阵表达形式 5 �# �# �# �&% ⋯ ⋯ �# �&$ ⋮ ⋮ ⋱ ⋮ �# �&$ ⋯ �&$! �# �# �# �% ⋯ ⋯ �# �$ ⋮ ⋮ ⋱ ⋮ �# �$ ⋯ �$! = � + 1 � 注意：对复数向量的内积，通常需要取共轭复数后再做内积 单位根的共轭复数� → �&%，这对应于Hermitian 对复数矩阵 � ，“正交”的正确定义是指Unitary：�'� = � 为什么这是一个逆变换？ 考虑乘积的(�,�)位置上的元素: $ *"# $)% �&+*�*! = $ *"# $)% �* !&+ = 1 − � $)% !&+ 1 − �!&+ , � ≠ � � + 1, � = �

回到离散三角级数的正交性 设整数r不能整除2m,则 cos(rx)=0,1 sin(rxj)=0. 并且，∑号61cos2(ry)=m,200-1sin2(rx）=m 证明：设整数r不能整除2m x1=-π+m,j=0,1,,2m-1 m eiz cosz+isinz 2m-1 2m-1 2m-1 cos(rxj)+i sin(rxj)= i=0 j=0 j=0 2m-1 1-ei2nr =e-irπ eirin/m =e-irn_ 1-eirn/m =0 =0 实部和虚部都必须为零！ 值得注意的是，erx=e-irπwj,其中ω为2m次单位根之一 6

回到离散三角级数的正交性 设整数 �不能整除2�，则 ∑ ! " # ,- & % cos ( � �! ) = 0, ∑ ! " # $% & ' sin ( � �! ) = 0 . 并且 ， ∑ ! " # $% & ' cos $ ( � �! ) = �, ∑ # $ % &' ( ) sin & ( � �# ) = � . 证明：设整数 �不能整除2��! = − � + �� � , � = 0 , 1 , … , 2� − 1 �"# = cos � + � sin � $!"# ,- & % cos ( � �! ) + � 4!"# $% & ' sin ( � �! ) = )"#$ %& ' ( � ) * + ! = � & + ./ $!"# ,- & % � + .! / / - = � & + ./ 1 − � + ,/ . 1 − � + ./ / - = 0 实部和虚部都必须为零 ！ 值得注意的是， � + . 1 , = � & + ./ �.!，其中 � 为2�次单位根之一 6

傅里叶变换与离散三角插值的对比（选讲） 离散三角插值：给定数据点化，y。,其中=-π+名=01,2m-1 能否找到系数{a,b使得，j n-1 2 +an cos nxj+ (ax coskx;+bg sinkxj) 最小二乘法解得 2m-1 1 2m-1 1 ak= m yi cos kxj, bk= m yi sin kxj j=0 =0 离散傅里叶变换相当于直接找到复平面上的系数{ck}使得，j 2m-1 *而品 由逆变换可得ck=”。y,e产，进而由Euler公式可得 1 251 ak +ibk m (cosk与+isinx)=-1 傅里叶变换的unitary性质：三角级数的正交性 7

傅里叶变换与离散三角插值的对比（选讲） 7 离散三角插值：给定数据点 �", �" "#$ %&'( ，其中�! = −� + ! " �,� = 0,1, … , 2� − 1 能否找到系数{�), �)}使得，∀� �" ≈ �$ 2 + �* cos ��" + @ +#( *'( �+ cos ��" + �+ sin ��" 最小二乘法解得 �+ = 1 � @ "#$ %&'( �" cos ��" , �+ = 1 � @ "#$ %&'( �" sin ��" 离散傅里叶变换相当于直接找到复平面上的系数{�+} 使得，∀� �! ≈ 1 � < #$% &"'( �#�)#*! 由逆变换可得 �+ = ∑+#$ %&'( �"� +,-. / ，进而由Euler公式可得 �# + ��# = 1 � < !$% &"'( �! cos ��! + � sin ��! = −1 # � �#. 傅里叶变换的unitary性质 ↔ 三角级数的正交性

求解线性方程 给定矩阵A∈Rmxn，,向量b∈Rm,，求x∈Rn使得Ax=b 只有三种情况 ·对任意的向量b,存在唯一解 不可解，或方程不一致(inconsistent,over-determined) ·存在无穷多组解(under-determined) 性质：只要存在两个不同的解，则一定存在无穷多组解。 性质：如果m>n则存在b使得方程不可解。 性质：如果m<n则存在b使得方程存在无穷多组解。 注：解线性方程组，与矩阵求逆是两回事 以下我们假设m=n 8

求解线性方程 给定矩阵� ∈ ℝ$×&，向量� ∈ ℝ$ ，求� ∈ ℝ&使得�� = � 只有三种情况 • 对任意的向量�，存在唯一解 • 不可解，或方程不一致 (inconsistent, over-determined) • 存在无穷多组解 (under-determined) 性质：只要存在两个不同的解，则一定存在无穷多组解。 性质：如果� > � 则存在�使得方程不可解。 性质：如果� < � 则存在�使得方程存在无穷多组解。 注：解线性方程组，与矩阵求逆是两回事 以下我们假设� = � 8

回顾高斯消元法 a11 a12 aln b1 a21 a22 a2n b2 a11 a12 aln 0 a21 a22 a12 ..a2n- c2以n 1b2 c2以b1 a11 a11 a11 可以一行一行地消，也可以一列一列地消 这里以行为例，主要涉及三种操作 ·交换行（交换两组方程） 。 给一行乘上一个数 在一行上减去另一行的一个倍数 9

回顾高斯消元法 可以一行一行地消，也可以一列一列地消 这里以行为例，主要涉及三种操作 • 交换行（交换两组方程） • 给一行乘上一个数 • 在一行上减去另一行的一个倍数 9

回顾高斯消元法：交换行 令o∈Sn为[n]上的一个置换 eo(1) eo(n) 其中向量e;是只有在第j个分量上为1的单位向量 10

回顾高斯消元法：交换行 令 � ∈ �+为 � 上的一个置换 �, = ⋯ �, - . ⋯ ⋮ ⋯ �, + . ⋯ 其中向量�/是只有在第�个分量上为1的单位向量 10

回顾高斯消元法：给一行乘上一个数 考虑对角矩阵 C 0 2 D 00 0 00 。。 11

回顾高斯消元法：给一行乘上一个数 考虑对角矩阵 � = �- 0 ⋯ 0 0 0 �0 ⋯ 0 ⋱ 0 0 0 0 ⋯ �+ 11