数值计算方法 扩充教程 童伟华编 中国科学技术大学
数值计算方法 扩充教程 童伟华 编 中国科学技术大学
目录 第九章函数逼近 9.1逼近问题的描述.. 9.2内积空间的最佳逼近 > 9.3最小二乘法.。.， 12 9.4最佳平方逼近与正交多项式 18 9.5周期函数的最佳平方逼近与快速傅立叶变换 25 9.6最佳一致逼近多项式 34 9.7切比雪夫多项式.... 。。。，。,，。。。。。 9.8函数逼近的若干重要定理 48 第十章最优化方法 59 10.1线性规划问题 60 10.2线性规划问题的几何意义 63 103单纯形法，，··。 71 10.4非线性优化问题 10.5一维搜索，. 89 10.6无约束非线性优化 95
目录 第九章 函数逼近 1 9.1 逼近问题的描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 9.2 内积空间的最佳逼近 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 9.3 最小二乘法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 9.4 最佳平方逼近与正交多项式 . . . . . . . . . . . . . . . . . . . . . . . . . 18 9.5 周期函数的最佳平方逼近与快速傅立叶变换 . . . . . . . . . . . . . . . . 25 9.6 最佳一致逼近多项式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 9.7 切比雪夫多项式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 9.8 函数逼近的若干重要定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 第十章 最优化方法 59 10.1 线性规划问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 10.2 线性规划问题的几何意义 . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 10.3 单纯形法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 10.4 非线性优化问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 10.5 一维搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 10.6 无约束非线性优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 iii
第九章函数逼近 在理论和工程领域，经常会遇到函数逼近问题，即如何寻找简单的函数(x)去近 似地代替一个复杂的函数∫(x),其中近似代替又称为逼近，函数f(x)和(x)分别称 为被逼近和逼近函数.利用简单函数去逼近复杂函数的一个常用目的：使得一些常用 的操作，譬如函数求值、微分甚至积分，可以变得更容易执行.另一个常用目的：利用 函数的部分信息，譬如函数值表，重建或恢复一个函数.常用于构造逼近函数的类包括 多项式，三角多项式，分片多项式等.下面是函数逼近的典型例子 (1)在区间[-1,1刂上，确定具有最低次数的多项式p(x)使得|p(x)-arccos(x川≤10-7 成立.更一般地，给定函数f(x)和正数e,确定多项式p(x),使在区间[a,上有 lp(x)-f(x川≤e (2)通过观察或测量函数∫(x)得到一组离散数据：{(x,)1i=1,2,,n,在函数 $=span{9(j=1,2,m}中选择p(y=∑S()回使得逼近 最小，即 9.1逼近问题的描述 在逼近问题中几乎都涉及到从一个集合中选择一个元素，使它在某种意义上接近 该集合外的一个预先给定的元素.因此，若要确切的描述逼近问题，需要明确两个元素 之间的距离是如何度量的.为了在统一的框架下描述逼近问题，下面引入赋范线性空 间
第九章 函数逼近 在理论和工程领域, 经常会遇到函数逼近问题, 即如何寻找简单的函数 φ(x) 去近 似地代替一个复杂的函数 f(x), 其中近似代替又称为逼近, 函数 f(x) 和 φ(x) 分别称 为被逼近和逼近函数. 利用简单函数去逼近复杂函数的一个常用目的: 使得一些常用 的操作, 譬如函数求值、微分甚至积分, 可以变得更容易执行. 另一个常用目的: 利用 函数的部分信息, 譬如函数值表, 重建或恢复一个函数. 常用于构造逼近函数的类包括: 多项式, 三角多项式, 分片多项式等. 下面是函数逼近的典型例子: (1) 在区间 [−1, 1] 上, 确定具有最低次数的多项式 p(x) 使得 |p(x)−arccos(x)| 6 10−7 成立. 更一般地, 给定函数 f(x) 和正数 ε, 确定多项式 p(x), 使在区间 [a, b] 上有 |p(x) − f(x)| 6 ε; (2) 通过观察或测量函数 f(x) 得到一组离散数据: {(xi , yi) | i = 1, 2, . . . , n}, 在函数 空间 Φ = span{φi(x) | j = 1, 2, . . . , m} 中选择 φ(x) = ∑m j=1 cjφj (x) 使得逼近误差 最小, 即 min φ∈Φ ∑n i=1 yi − φ(xi) 2 = min c1,c2,··· ,cm∈R ∑n i=1 yi − ∑m j=1 cjφj (xi) 2 . 9.1 逼近问题的描述 在逼近问题中几乎都涉及到从一个集合中选择一个元素, 使它在某种意义上接近 该集合外的一个预先给定的元素. 因此, 若要确切的描述逼近问题, 需要明确两个元素 之间的距离是如何度量的. 为了在统一的框架下描述逼近问题, 下面引入赋范线性空 间. 1
2 第九章函数逼近 定义9.1设集合V是实数域R上的线性空间，如果V中任意一个元素∫都按某 一法则对应一个实数，记作儿，并且它满足下列条件： (1)正定性：f川≥0，f∈V:f川=0当且仅当f=0成立： (2)齐次性：lcf川=lclf川，ceR,f∈V; (3)三角不等式：If+gl≤If川+lgl,f,g∈V 上述对应关系可视为V→R的映射，称为线性空间V的范数，并简记为"，‖.定义了 范数的线性空间称为赋范线性空间. 下面对常用的有限维线性空间R”和无穷维线性空间C[a,)分别引入范数 例9.1记R”为n维线性空间，在Rn中定义 x2=(+号++2)/，收=(e1,2,…,rn)T ER". 易验证‖·2满足条件(1)~(3).因此，R”按1,2构成一赋范线性空间.事实上，若n 维线性空间R”按常用的内积(，)构成欧氏空间，则范数k2可视为向量x自己与自 己内积的平方根，即x2=√G,x,称x2为向量的2范数或欧几里得范数.另外，不 难验证Rn还可按如下范数 lk1=z+z2+…+znl,次=(e1,x2,…,xn)T∈R”, lxle=maxz1l,z2l,…,znl,i=(x1,x2,·,xn)T∈R”, 分别构成不同的赋范线性空间.更一般地，在Rn中定义 xp=(0zP+lz2P+…+znP)p,次=(c1,x2,…,xn)T∈R", 构成向量x的p范数，前面的范数分别对应p=1,2,∞的情形. 例9.2记Ca,)为区间a,)上连续函数的全体，按通常的函数加法与数乘运算 构成线性空间.在C[a,)中定义 lfl()l v e Cla. 易验证‖·川x满足条件(1)~(3).因此，Ca,)按1·‖✉构成一赋范线性空间，范数 ‖·‖le称为一致范数或Chebyshev范数
2 第九章 函数逼近 定义 9.1 设集合 V 是实数域 R 上的线性空间, 如果 V 中任意一个元素 f 都按某 一法则对应一个实数, 记作 ∥f∥, 并且它满足下列条件: (1) 正定性: ∥f∥ > 0, ∀f ∈ V ; ∥f∥ = 0 当且仅当 f = 0 成立; (2) 齐次性: ∥cf∥ = |c|∥f∥, ∀c ∈ R, ∀f ∈ V ; (3) 三角不等式: ∥f + g∥ 6 ∥f∥ + ∥g∥, ∀f, g ∈ V . 上述对应关系可视为 V → R 的映射, 称为线性空间 V 的范数, 并简记为 ∥ · ∥. 定义了 范数的线性空间称为赋范线性空间. 下面对常用的有限维线性空间 R n 和无穷维线性空间 C[a, b] 分别引入范数. 例 9.1 记 R n 为 n 维线性空间, 在 R n 中定义 ∥x∥2 = ( x 2 1 + x 2 2 + · · · + x 2 n )1/2 , ∀x = (x1, x2, · · · , xn) T ∈ R n . 易验证 ∥ · ∥2 满足条件 (1) ∼ (3). 因此, R n 按 ∥ · ∥2 构成一赋范线性空间. 事实上, 若 n 维线性空间 R n 按常用的内积 (·, ·) 构成欧氏空间, 则范数 ∥x∥2 可视为向量 x 自己与自 己内积的平方根, 即 ∥x∥2 = √ (x, x), 称 ∥x∥2 为向量的2-范数或欧几里得范数. 另外, 不 难验证 R n 还可按如下范数 ∥x∥1 = |x1| + |x2| + · · · + |xn|, ∀x = (x1, x2, · · · , xn) T ∈ R n , ∥x∥∞ = max{|x1|, |x2|, · · · , |xn|}, ∀x = (x1, x2, · · · , xn) T ∈ R n , 分别构成不同的赋范线性空间. 更一般地, 在 R n 中定义 ∥x∥p = (|x1| p + |x2| p + · · · + |xn| p ) 1/p , ∀x = (x1, x2, · · · , xn) T ∈ R n , 构成向量 x 的p-范数, 前面的范数分别对应 p = 1, 2, ∞ 的情形. 例 9.2 记 C[a, b] 为区间 [a, b] 上连续函数的全体, 按通常的函数加法与数乘运算 构成线性空间. 在 C[a, b] 中定义 ∥f∥∞ = max a6x6b |f(x)|, ∀f ∈ C[a, b]. 易验证 ∥ · ∥∞ 满足条件 (1) ∼ (3). 因此, C[a, b] 按 ∥ · ∥∞ 构成一赋范线性空间, 范数 ∥ · ∥∞ 称为一致范数或 Chebyshev 范数
9.1逼近问题的描述 例9.3记Cr[a,)为区间[a,)上r次连续可微函数的全体.定义Cr[a,b的范数 fs=ma{f(lf'(…,lf川，feCa,. 显然，Ca,b是Cra,b的一个特殊情形. 例9.4记LP[a,b为区间[a,b上所有满足 [eard<te,p≥l 的Lebesgue可积函数f构成的函数类(Lebesgue积分是Riemann积分的推广)，.因区间 [a,b)上所有的连续函数都是Riemann可积的，故C[a,)cL[a,.在LP[a,)中定义 1/p -（I)Pd）,fera, (9.1) Ja 可以证明‖·p是P[a,的一个范数.注意，在[a,)中约定：将几乎处处相等的两 个可测函数∫，9视为同一函数。 在赋范线性空间中，可以按照下面的方式引入向量之间的距离 定义9.2在赋范线性空间V中，定义函数 df,g)=f-gll,f,9∈V, 称为∫与g之间的距离.不难验证d(∫，9)满足距离定义所要求的条件： (1)正定性：d(f,g)≥0，f∈V,d(,9)=0当且仅当∫=9成立， (2)对称性：d(f,g)=dg,f),f,9∈V, (3)三角不等式：df,g)≤d(f,h)+d(h,g,f,g,h∈V 有了距离的定义，便可讨论函数的连续性。 引理9.1在赋范线性空间V中，加法，数乘和范数都是距离d(∫，g)下的连续函 数 证明设V中有收敛的序列，ma=∫及m9m=9,则有 d(f*+g",fn +gn)=lf*+g"-(fn +gn)ll ≤lf'-fnll+lg°-gl =d(f',fn)+dg',9n)
9.1 逼近问题的描述 3 例 9.3 记 C r [a, b] 为区间 [a, b] 上 r 次连续可微函数的全体. 定义 C r [a, b] 的范数 ∥f∥∞ = max x∈[a,b] { |f(x)|, |f ′ (x)|, · · · , |f (r) (x)| } , ∀f ∈ C r [a, b]. 显然, C[a, b] 是 C r [a, b] 的一个特殊情形. 例 9.4 记 L p [a, b] 为区间 [a, b] 上所有满足 ∫ b a |f(x)| p dx < +∞, p > 1, 的 Lebesgue 可积函数 f 构成的函数类 (Lebesgue 积分是 Riemann 积分的推广). 因区间 [a, b] 上所有的连续函数都是 Riemann 可积的, 故 C[a, b] ⊂ L[a, b]. 在 L p [a, b] 中定义 ∥f∥p = (∫ b a |f(x)| p dx )1/p , ∀f ∈ L p [a, b], (9.1) 可以证明 ∥ · ∥p 是 L p [a, b] 的一个范数. 注意, 在 L p [a, b] 中约定: 将几乎处处相等的两 个可测函数 f, g 视为同一函数. 在赋范线性空间中, 可以按照下面的方式引入向量之间的距离. 定义 9.2 在赋范线性空间 V 中, 定义函数 d(f, g) = ∥f − g∥, ∀f, g ∈ V, 称为 f 与 g 之间的距离. 不难验证 d(f, g) 满足距离定义所要求的条件: (1) 正定性: d(f, g) > 0, ∀f ∈ V ; d(f, g) = 0 当且仅当 f = g 成立; (2) 对称性: d(f, g) = d(g, f), ∀f, g ∈ V ; (3) 三角不等式: d(f, g) 6 d(f, h) + d(h, g), ∀f, g, h ∈ V . 有了距离的定义, 便可讨论函数的连续性. 引理 9.1 在赋范线性空间 V 中, 加法, 数乘和范数都是距离 d(f, g) 下的连续函 数. 证明 设 V 中有收敛的序列 lim n→∞ fn = f ∗ 及 lim n→∞ gn = g ∗ , 则有 d(f ∗ + g ∗ , fn + gn) = ∥f ∗ + g ∗ − (fn + gn)∥ 6 ∥f ∗ − fn∥ + ∥g ∗ − gn∥ = d(f ∗ , fn) + d(g ∗ , gn)