长沙学院毕业设计(论文)
的解只要存在则必是唯一的。
2.3几种常见的有理逼近
2.3.1 Padé逼近
Padé逼近法[3]是从幂级数出发获得有理逼近的一种十分简洁而且非常有效的方法。其基本思想是对于一个给定形式的幂级数，构造一个有理函数，使得该有理函数的Taylor展开尽可能多的项与原来的幂级数吻合。这种方法克服了用多项式逼近大扰度函数效果不理想以及用幂级数（如Taylor级数）逼近函数收敛性太差等缺点。Padé逼近的基本定义如下：
设函数f(x)?cN (-a,a),N=n+m+1,如果有理函数Rnm(x)可展开为式（2-7）
1na?ax?????axPn(x) （2-7） 01n R(x)??nm1?b1x1?????bmxmQm(x)其中Pn(x)、Qm(x)互质，且满足条件式（2-8）
(k) Rnm(0)?f(k)(0) k?0,1,???,n?m (2-8)
(k)其中Rnm(0)、f(k)(0)分别是有理函数和f(x)的Taylor展开式中的导数，则称Rnm(x)为函数f(x)在x=0处的(n,m)阶Padé逼近，记为R(n,m)。
2.3.2 Müntz有理逼近
Müntz有理逼近[4]是逼近论中一个比较有趣的问题，同时也是一个比较新的课题，在这个领域仍有许多问题有待解决。其相关记号及定义如下：
设C[0,1]是区间[0,1]上连续函数的全体，对非负递增实数序列??{?n}?n?1，以
?n?1?2表示n阶Müntz多项式空间，即{x,x,???,x}的线性组合的全体，以??nRn(?)表示n阶Müntz有理函数空间，即
P(x) Rn(?)?{|P(x),Q(x)??n(?),Q(x)?0,x?[0,1]} （2-9）
Q(x)P(x)/Q(x)存在并且有限。对f?C[0,1]，定义 此处，我们总认为P(0)/Q(0)?lim?x?0 w(f,t)?supmax|f(x?h)?f(x)| （2-10）
0?h?tx,x?h?[0,1]2.3.3 最佳有理分式逼近
今考虑有理型逼近函数如式（2-11）。
a0?a1x?????anxn R(A,x)? （2-11） mb0?b1x?????bmx为使表达式形式唯一，我们假定有理分式R(A,x)是最简有理分式，即其分子、分母是不可约的，并假定
P?{(a0,a1,???,an,b0,b1,???,bm)|?bi2?1;b0?b1x?????bmxm?0,x?[0,1]}
i?0m （2-12） 对于给定的在[0,1]上连续的函数f(x)，定义有理分式逼近R(A,x)与f(x)的偏差为 HA?max|f(x)?R(A,x)|?||f(x)?R(A,x)|| （2-13）
0?x?1 8
长沙学院毕业设计(论文)
而最佳有理分式逼近问题，乃是寻求A0?P，使得
HA0?||f(x)?R(A0,x)||?inf||f(x)?R(a,x)|| （2-14）
A?p如此的有理分式R(A0,x)称为f(x)的最佳逼近有理分式。
9
长沙学院毕业设计(论文)
第三章 有理函数逼近的实际应用
3.1 有理逼近在数值优化中的应用
本文已经介绍了有理函数的相关理论。对于有理逼近的应用，我们可以利用上文中的“倒差商”和“有理插值的唯一”性来求解数值优化问题，建立直线搜索方法。
3.1.1 直线搜索方法
直线搜索的数学模型是
minf(x)
x?[a,b]其中目标函数f(x)为定义在单峰区间[a,b]上的一元函数。显然为求最优解，可转化为求f(x)的稳定点，即使得f'(x)?0的x?x*。设z?f*(x)的反函数x?g(z)，我们用连分式x??(z)来逼近g(z)。假设已知x?xi时f'(xi)?zi其中（i?0,1,???,k）。利用有理插值，注意到?（zi）?g(zi)有
z?z0z?zk?1z?z1 (3-1)??????1?1?1[z0,z1]?[z0,z1,z2]?[z0,z1,???,zk]?为计算(3-1)的倒差商。可做倒插商表。倒插商表的推算公式是
x??(z)??(z0)??（z0）?x0 ?(zi)?xi（i?1,2,???k）
[z0,z1,???,zi,zj]???1zi?zj[z0,???,zi?2,zi]?1??[z0,???,zi?2,zj]?1? （3-2）
（j?0,1,2?,k?1;i?j?1,j?2,?,k）
式中[z0,z1,?,zi]?1?（其中i?1,2,???k）正是(3-1)中的各阶倒插商。因为f(x)的最优解x?x*对应z?0，所以x*?g(0)可用x??(0)近似x*，将z?0代入(3-1)式，得 x??(0)?z0zk?1z1 （3-3） ????[z0,z1]?1?[z0,z1,z2]?1?[z0,z1,?,zk]?1?由于是的逼近函数，一般不会有，所以可以把作为一个新的迭代点，即取，
有了新的连分式便增加了一层，因此在公式中再增加两式：
?（zk?1）?xk?1[z0,z1,?,zj,zk?1]?1??zk?1?zj[z0,?,zj?1,zk?1]?1??[z0,?,zj?1,zj]?1? （3-4）
其中为新增了一层连分式中最后一层所含的倒插商。此时增加了一层的函数连分式为
x??(z)??(z0)?z?z0z?zk?1z?zk???? （3-5）
[z0,z1]?1?[z0,?,zk]?1?[z0,?,zk?1]?1?10
长沙学院毕业设计(论文)
在此基础上，如果xk?1还不满足精度要求，与上述做法类似，再求出xk?2,xk?3,?等等。这是用有理函数差值解一维最优化问题的方法。
3.1.2 计算方法
a，对于给定的x0，由x0出发，取适当步长h按下式计算
xi?x0?ih， zk?f'(xi) （i?1,2,?,k） 其中k为预先给定的值，通常取k?3；
b，按公式计算（3-2）计算倒差值；
c，按公式（3-3）求出x?xk?1；
d，如果满足精度要求xk?1?xk??1或f'(xk?1)?zk?1??2（其中?1,?1为预先给定的充分正小数），则停止计算；否则作下述e； e，按公式（3-4）进行计算。这个计算相当于在倒插商表后面，再计算一行，以求得zk?1,[z0,?,zk,zk?1]?1f，因此连分式增加一层。然后，令k?1?k，转上述c。
3.1.3计算实例
为说明有理函数的逼近在数值优化中的应用，现给出线性搜索算例：
3 minf(x)?sinx?co3sx x?[0,?/2]
显然 f'(x)?3coxssinx(sixn?coxs) （3-6） 现取k?3,h?0.1,x0?0.3计算过程和结果如下表所示。 从下表可以看出：
最优解 x*??/4=0.785 398 163
最优值为 f(x*)?2/2=0.707 106 781
我们看到，最优解x*=0.785 398 达到6位有效数字，最优值f(x*)=0.707 106 8达到7位有效数字，倒数值f(x*)=-0.000 000 983准确到小数点后第六位，结果令人满意。
3.2 基于有理逼近的Halley迭代公式
3.2.1 预备知识
对于求解非线性方程时，很容易想到构造迭代函数的方法。通常情况下，迭代公式的构造有不同的方法，从而构造的迭代公式形式不完全相同，迭代效果一部一样。而本文中利用Thiele连分式逼近的表达式，重新构造出Halley迭代公式[7]。，同时为了避免求导数运算，利用差商近似代替倒数的办法，将Halley迭代公式离散化为多初始点迭代公式。
定义1 将下述形式如（4-1）的连分式称为Thiele型连分式。
11
长沙学院毕业设计(论文)
b0?x?x0|?x?x1|?????x?xn?1|???? （4-1）
|b1|b2|bn算法1 （Viscovatov算法） 假设函数f(x)在点x=xk处任意阶可微，若f(x)
x?xk|x?xk|x?xk|可展开成如下Thiele连分式f(x)?b0???????????。而f(x)
|b1|b2|b3的Taylor展开式为f(x)??Ci(0)(x?xk)i，于是可得如下Viscovatov算法：
i?0?0)(0)l(l?2)(l?1) b0?c；b1?1/c；ci(1)??ci(?/c，i?1；b??c/c，l?2；1111(0)0(0)1c??c(l)i(l?2)i?1?bc(l?1)li?1其中c，i?1，l?2。(0)if(i)(xk)?，i?0，1，2??? 'i3.2.2 Halley迭代公式
一般情况下，截取Taylor展开式的二次多项式部分近似代替f(x)，得到f(x)=0
(x?xk)2'\的近似方程f(x)?f(xk)?f(xk)(x?xk)?f(xk)，将此方程的根记作
2!f(x)f\(x)。 xk?1，并记Lf(x)?f2(x)，则得到Euler迭代公式如式（4-2）
2f(xk) xk?1?xk?，k?0 （4-2） '1?1?2LF(xk)f(xk)类似的方法，取Thiele展开式的第2项截断连分式近似代替f(x)，得到f(x)=0
x?xk|x?xk|的近似方程为f(x)?b0???0，将此方程的根记作xk?1，于是得到
|b1|b2bbb1xk?1?xk?012。然后由Viscovatov算法，得到b0?f(xk)，b1?'，
b0?b2f(xk)2(f'(xk))2b2??。将b0，b1，b2代入上式，得到 \f(xk)2f(xk)f'(xk) xk?1?xk? （4-3）
2[f'(xk)]2?f(xk)f\(xk)式（4-3）就是利用Thiele连分式逼近建立的Halley迭代公式。
12