如何判断一个数值算法的局部和全局收敛性？

Question

如题所述

Answer 1

总的来说局部收敛性指的是初值取在根的局部时算法(一般)具有二阶收敛速度, 全局收敛性是指初值在定义域内任取时算法是否收敛, 若收敛其速度如何, 收敛到哪个根.

具体来说
局部收敛性有如下定理
设已知 f(x) = 0 有根 a, f(x) 充分光滑(各阶导数存在且连续).
若 f'(a) != 0(单重零点), 则初值取在 a 的某个邻域内时, 迭代法 x[n+1] = x[n] - f(x[n])/f'(x[n]) 得到的序列 x[n] 总收敛到 a, 且收敛速度至少是二阶的.
若 f'(a) == 0(多重零点), 则初值取在 a 的某个邻域内时, 收敛速度是一阶的.
记 g(x)=x-f(x)/f'(x), 其中"某个邻域"可由 |g'(x)|<1 的区间确定, 但是 g'(a)==0, 所以这样的邻域总是能取到的.
说收敛速度是 r 阶指的是: 存在 r 及常数 c 使 lim_{n->\inf} |x[n+1]-a|/|x[n]-a|^r = c

至于牛顿迭代法的全局收敛性, 一般的数值分析书都没有详细叙述, 而只是举一些例子.
因为牛迭是否收敛依赖于函数是否"单调", 一些"曲折"大的函数就可能使迭代法不收敛了.
经常举的例子是三次函数, 比如 x^3 - x == 0. 有 -1,0,1 三个根.
迭代的时候如果取初值 x[1] = sqrt(0.2) = 0.4472.., 则得到 x[2] = sqrt(0.2), x[3] = sqrt(0.2) ... 收敛到 sqrt(0.2), 而这不是原方程根.
另外也可能不收敛, 或者不是收敛到离初值最近的根. 当然, 对于三次函数, 除了个别点, 牛迭总是收敛到某个根的, 因为初值远离原点时由于函数的单调性, 总会被拉回"局部".
事实上在复平面上三次函数的根的牛迭收敛行为是个著名的分形...足见全局收敛性的复杂.