回顾 。 插值：给定数据点，找出多项式经过所有点 -对于n个数据点，有且仅有一个 -存在性：拉格朗日插值方法 - 唯一性：代数基本定理 一龙格现象：等距采样 -插值的不可预测性的应用：分享秘密、自纠错码(Reed-Solomon code) 函数逼近/拟合：给定函数，找出与之相近的函数（多项式） - Neierstrass定理：对于连续函数，多项式可以任意地逼近（即使是等 距采样) 这节课： · Chebyshev:多项式 ·最小二乘法 4
回顾 • 插值：给定数据点，找出多项式经过所有点 – 对于 �个数据点，有且仅有一个 – 存在性：拉格朗日插值方法 – 唯一性：代数基本定理 – 龙格现象：等距采样 – 插值的不可预测性的应用：分享秘密、自纠错码（Reed-Solomon code） • 函数逼近/拟合：给定函数，找出与之相近的函数（多项式） – Weierstrass定理：对于连续函数，多项式可以任意地逼近（即使是等 距采样） 这节课： • Chebyshev多项式 • 最小二乘法 4
补充：自纠错码需要多大？(Hamming bound) 考虑自纠错码C:Fm→F.要处理k个字符的erasure,那么需 要n≥m+k C(x),C(x') 七，x'∈fgm x,x'∈Em Bx(C(x)) B&(C(x))
补充：自纠错码需要多大？(Hamming bound) 考虑自纠错码�: �! " → �! #. 要处理k个字符的erasure，那么需 要� ≥ � + � 5 �, �! ∈ �" # � � , � �! ∈ �" $ �, �! ∈ �" # �% � � �% � �!
补充：自纠错码需要多大？(Hamming bound) 考虑自纠错码C:Fgm→Fg.要处理k个字符的erasure,那么需要n≥ m+k 反证法：假设n≤m+k-1 考虑所有的codewordi的集合：{C(x):x∈Fm 去掉这些codeword的后面k位（投影到前面m-1位） ·剩下每个codeword的长度最多为m-1 由Pigeon-hole principle,一定存在两个codeword在前m一1位是相同 的，记为x,x 。 这意味着，存在x,x'∈Fgm,x≠x,使得C(x)和C(x)在去掉了最后 的k位后相等 这与能处理k个字符的erasurel的假设矛盾。 6
补充：自纠错码需要多大？(Hamming bound) 考虑自纠错码�: �" # → �" $. 要处理k个字符的erasure，那么需要� ≥ � + � 反证法：假设� ≤ � + � − 1 • 考虑所有的codeword的集合: � � : � ∈ �" # • 去掉这些codeword的后面 � 位 （投影到前面� − 1位） • 剩下每个codeword的长度最多为� − 1 • 由Pigeon-hole principle，一定存在两个codeword在前� − 1位是相同 的，记为�, �′ • 这意味着，存在�, �% ∈ �" # , � ≠ �′，使得� � 和 � �′ 在去掉了最后 的 � 位后相等 • 这与能处理k个字符的erasure的假设矛盾。 6
补充：自纠错码需要多大？(Hamming bound) 考虑自纠错码C:Fm→F.要处理k个字符的corruption,那么需要n≥m+2k 反证法：假设n≤m+2k-1 ·考虑所有的codeword的集合：{C(x):x∈Fgm} ·去掉这些codeword的后面2k位（投影到前面m-1位） ·剩下每个codeword的长度最多为m-1 由Pigeon-hole principle,.一定存在两个codeword在前m-1位是相同的，记为x,x' ·这意味着，存在x,x'∈Fm,x≠x',使得C(x)和C(x)在去掉了最后的2k位后相等 因此，可以从C(x)修改最多k个字符，再从C(x)修改最多k个字符，将得到一样的 信息 ,将无法区分这是由C(x)修改最多k个字符得到的，还是从C(x) 这与能处理k个字符的corruption矛盾 ● 7
补充：自纠错码需要多大？ (Hamming bound) 考虑自纠错码�: �! " → �! #. 要处理k个字符的corruption，那么需要� ≥ � + 2� 反证法：假设� ≤ � + 2� − 1 • 考虑所有的codeword的集合: � � : � ∈ �! " • 去掉这些codeword的后面 2� 位 （投影到前面� − 1位） • 剩下每个codeword的长度最多为� − 1 • 由Pigeon-hole principle，一定存在两个codeword在前� − 1位是相同的，记为�, �′ • 这意味着，存在�, �$ ∈ �! " , � ≠ �′，使得� � 和 � �′ 在去掉了最后的 2� 位后相等 • 因此，可以从� � 修改最多�个字符，再从� �′ 修改最多�个字符，将得到一样的 信息 • 从接收者的角度看，将无法区分这是由� � 修改最多�个字符得到的，还是从� �′ 修改最多�个字符得到的 • 这与能处理k个字符的corruption矛盾 7
回顾插值中的龙格现象 对连续n次可导函数f,在x1,…,xn上拉格朗日插值的误差 f)-P)=区-)6x-2…x-x) f(n)(c), n! 0.02 证明：令q(t)为x1,…,x,x上插值的多项式 则q()=P(t)+Π=1(t-x),其中入=)-P 0.01 Π=1(x-x) 考虑φ(t)=f(t)-q(t),则φ(t)在n+1个点处为零 由Rolle定理，中'(t)在n个点处为零 反复应用Rolle定理，中m)(t)在区间上某个点为零 -0.01 在该点中m)(c)=0→f(c)=qm)(c)=l 整理即得误差公式 -0.02 使用等距采样插值时的误差函数 如何选点x1,,xn,才能最小化误差？插值的表现可否媲美函数逼近？ ，采用更多靠近边界的点 12
回顾插值中的龙格现象 12 对连续n次可导函数�，在�!, … , �"上拉格朗日插值的误差 • 证明：令� � 为�!, … , �", �上插值的多项式 • 则� � = � � + � ∏#$! " � − �# , 其中� = % & '( & ∏!"# $ &'&! • 考虑� � ≔ � � − � � ，则� � 在� + 1个点处为零 • 由Rolle定理， �′(�)在�个点处为零 • 反复应用Rolle定理， �(") (�)在区间上某个点为零 • 在该点� " � = 0 ⇒ � " � = � " � = ��! • 整理即得误差公式 • 如何选点�!, … , �" ，才能最小化误差？插值的表现可否媲美函数逼近？ • 采用更多靠近边界的点 使用等距采样插值时的误差函数