计算函数零点和极值点的迭代法初步.PPTVIP

数值计算方法 第四章 计算函数零点和极值点的迭代法 本章讨论非线性方程（组）的求解问题 4.1 不动点迭代法及其收敛性 1．不动点 设非线性方程组 f(x) = 0 (4.1-1) 4.1 不动点迭代法及其收敛性 非线性方程组 f(x) = 0 (4.1-1) 等价： x = ?(x) (4.1-2) 则有迭代格式：x(k+1) = ?(x(k))，k = 0, 1, 2, … 若?连续，且迭代序列{x(k)}收敛到x*，则两边取极限得 x* = ?(x*)， 即x*满足(4.1-2)，从而满足(4.1-1)，即x*为f 的零点。称x*为?(x)的不动点。 4.1 不动点迭代法及其收敛性 x(k+1) = ?(x(k))，k = 0, 1, 2, … 注： (1) 求零点?求不动点 (2) ?(.)称为迭代函数，{x(k)}称为迭代序列 (3) 不同方法构造迭代函数，得不同的迭代序列 4.1 不动点迭代法及其收敛性 2．迭代法的基本问题 (1) 如何构造适当的迭代函数?(.)使迭代序列{x(k)}收敛 (2) 收敛的速度和误差 (3) 如何加速 4.1 不动点迭代法及其收敛性 4.1.1 解一元方程的迭代法 1. 根的隔离 设一元方程f(x) = 0，f 连续，其实根可能有很多，需将各根隔离，即f在某区间[a，b]内有且仅有一根。 方法：设f ?C[a，b]，f(a)f(b) 0，且f在[a，b]上单调，则f在[a，b]内有且仅有一根。 4.1 不动点迭代法及其收敛性 4.1.1 解一元方程的迭代法 2. 迭代序列的收敛性 因为可以有多种迭代函数，所产生的迭代序列{x(k)}有可能： (1) 收敛快 (2) 收敛慢 (3) 不收敛 4.1 不动点迭代法及其收敛性 4.1.1 解一元方程的迭代法 例1 f(x) = x3 – x – 1 = 0，求f在x = 1.5附近的根，初值取x(0) = 1.5。(p328) 取 —— 收敛 k=1, x0=1.5 x1=(1+x0)^(1/3) while abs(x1-x0)0.00001 k=k+1, x0=x1; x1=(1+x0)^(1/3) end 4.1 不动点迭代法及其收敛性 4.1.1 解一元方程的迭代法 例1 f(x) = x3 – x – 1 = 0，求f在x = 1.5附近的根，初值取x(0) = 1.5。(p328) 取?(x) = x3 – 1 —— 不收敛 k=1, x0=1.5 x1=x0^3-1 while abs(x1-x0)0.00001 k5 k=k+1, x0=x1; x1=x0^3-1 end 4.1 不动点迭代法及其收敛性 4.1.1 解一元方程的迭代法 定理4.1-1 (1)设?(x)?C[a，b], 且对于任意x ? [a, b] 有? (x) ? [a，b]，则?在[a，b]上必有不动点。 (2) 进一步，若?(x)?C1[a，b]，且存在L1，使对于任意的x ? [a，b]有 |? (x)| ? L 1 (4.1-4) 则对于任意的x(0) ? [a，b]，x(k+1) = ?(x(k))收敛于唯一不动点x* ? [a，b]。 4.1 不动点迭代法及其收敛性 4.1.1 解一元方程的迭代法 定理4.1-1 (2) 进一步，若?(x)?C1[a，b]，且存在L1，使对于任意的x ? [a，b]有 |? (x)| ? L 1 (4.1-4) 则对于任意的x(0) ? [a，b]，x(k+1) = ?(x(k))收敛于唯一不动点x* ? [a，b]。且有 (4.1-5) 4.1 不动点迭代法及其收敛性 4.1.1 解一元方程的迭代法 定理4.1-1 (1)设?(x)?C[a，b], 且对于任意x ? [a, b] 有? (x) ? [a，b]，则?在[a，b]上必有不动点。 证明：(1) 若?(a) = a或?(b) = b，则结论显然成立 现设a ?(a)，?(b) b，令?(x)= ?(x) – x，则 ?(x) ? C[a，b]，且