数值分析-引论

任务

整理引论中提到的一些算法

秦九韶算法

多项式计算f(x)

计算多项式，形式如：

a0x^n+a1x^n-1+a2x^n-2+…+an-1x+an

通过合并多项式，降低运算次数

根本源于：

a0*x^n+a1*x^n-1=(a0x+a1)*x^n-1

由此可得：

b0=a0

bi=bi-1*x+ai

最终，bn为所求

求导f'(x*)

f(x)=(x-x*)(b0x^n-1+b1x^n-2+…+bn-1)+bn

解释上式——通过迭代：

(x-x*)(b0x^n-1）=b0x^n-b0x^n-1x*

(x-x*)(b1x^n-2）=b1x^n-1-b1x^n-2x*=(b0x*+a1)x^n-1-b1x^n-2x*=b0x^n-1x*+a1x^n-1-b1x^n-2x*

则递推公式，可消去末项，得到

a0x^n+a1x^n-1+a2x^n-2+…+an-1x+an

得到证明，故可通过求上述导，即令

q(x)=(b0x^n-1+b1x^n-2+…+bn-1)

p'(x)=q(x)+(x-x*)q'(x)

p'(x*)=q(x*)

利用上一部分的多项式计算法则可得结果

迭代法

开方转化为四则运算，计算√a

可以取：xk+1=1/2(xk+a/xk)

import math
a=500
x=math.sqrt(a)
print('inside function: '+str(x))
print('*********iterative method*********')
s=2 # initial value
for i in range(10):
    s=1/2*(s+a/s)
    print('time: '+str(i)+' | result: '+str(s))

结果：

inside function: 22.360679774997898
*********iterative method*********
time: 1 | result: 126.0
time: 2 | result: 64.98412698412699
time: 3 | result: 36.33915679934244
time: 4 | result: 25.049209685021346
time: 5 | result: 22.504959637875427
time: 6 | result: 22.361142265914722
time: 7 | result: 22.3606797797807
time: 8 | result: 22.360679774997898
time: 9 | result: 22.360679774997898
time: 10 | result: 22.360679774997898

可见收敛的速度很快，但当a取500000时，10次迭代与内置结果有一定出入，将初值取值改为自适应

思考，当数目较大时，开方结果的位数与数字的一半位数接近，则取初值为一半位数

import math
a=5000000
x=math.sqrt(a)
print('inside function: '+str(x))
print('*********iterative method*********')
def digitNum(num):
    tens=1
    for i in range(10):
        if(num//tens==0):
            return i
        tens=tens*10
m=digitNum(a)
print('digit num of number: '+str(m))
s=10**(m//2) # initial value
print('choose initial value: '+str(s))
for i in range(10):
    s=1/2*(s+a/s)
    print('time: '+str(i+1)+' | result: '+str(s))

这样对于较大数字，选取的初值接近最终结果，更快收敛效果

inside function: 2236.06797749979
*********iterative method*********
digit num of number: 7
choose initial value: 1000
time: 1 | result: 3000.0
time: 2 | result: 2333.3333333333335
time: 3 | result: 2238.095238095238
time: 4 | result: 2236.0688956433637
time: 5 | result: 2236.067977499978
time: 6 | result: 2236.06797749979
time: 7 | result: 2236.06797749979
time: 8 | result: 2236.06797749979
time: 9 | result: 2236.06797749979
time: 10 | result: 2236.06797749979

以直代曲和化整为零

• 非线性问题线性化
• 直线近似曲线
  • 方程求根 牛顿迭代法
  • 微积分 梯形公式
  • 圆周率 割圆法

加权平均的松弛技术

这是最没有认知的一部分，是计算方法提高收敛速度的一种有效方法。

x0于x1为x*的两个近似值，

x=x1+w(x1-x0)=(1+w)x1-wx0

w选取适当可逼近真值，但选取困难。