4 求代数方程的根1.ppt

求代数方程的根 方程求根的迭代法 线性方程组的解法 4 方程求根的迭代法 迭代法的基本概念 二分法 不动点理论 Newton-Raphson方法 割线法 多项式求根 讨论求实函数方程f(x)=0的解的数值方法 方程f(x)=0的解，通常称为方程的根或函数f(x)的零点。 迭代法是求解f(x)=0的常用方法。 4.1 迭代法的基本概念 迭代法： 从给定的一个或几个初始近似值(初始值)x0、x1、x2、…、xr出发，按某种方法产生的一个序列x0，x1，x2，…，xr， xr+1，…，xk ，…称为迭代序列，使得此序列收敛于方程f(x)=0的一个根p。  当k足够大时，取xk作为p的近似值。 需要讨论的问题 迭代法的构造(迭代格式)； 迭代序列的收敛性和收敛速度； 误差估计。 收敛性 解的收敛与初值选取范围有关。 大范围收敛：从任何可取的初始值出发都能保证收敛； 局部收敛：初始值充分接近于所要求的根，如果存在邻域Δ： ，使迭代过程对于任何初值x0 ∈δ均收敛。 收敛速度——收敛阶数 令 若存在实数λ和非零常数C，使得 则称该迭代法为λ阶收敛，或者说收敛阶数为λ。 若λ=1——线性收敛； 若λ1——超线性收敛； 通常局部收敛方法比大范围收敛方法收敛更快； 好的算法是用大范围收敛方法求得接近于根的近似值，再以其为初始值使用局部收敛方法。 4.2 二分法(区间分半法) 建立在中值定理上 设函数f(x)在[a，b]上连续，且f(a)f(b)0。 二分法示意图 迭代格式 a1=a，b1=b；x1=(a1+b1)/2. 若f(x1)δ,则x1为所求根的近似值。 若|f(x1)|δ,则： xk+1=(ak+1+bk+1)/2 特点： 大范围收敛。 误差估计： 迭代终止原则： 迭代步数的初步估计 可能出现的情况 f(xn)接近于0，但xn与p差别很大。 例：f(x)=(x-1)10的根为1，令xn=1+1/n。对n的要求？ 建议： 例题： 设f(x)=x3-x-1，采用二分法求方程的近似根。 解： (1) 确定[a，b]区间：[1，2]； (2) 由精度10-4确定步数：14。 (3) 二分法求根的近似解。 二分法的特点： 收敛速度不快，简单，可靠； 可用于确定根的初始近似值。 4.3 不动点迭代 将非线性方程f(x)=0化为等价方程 x=g(x)该方程的根称为函数g(x)的不动点。 为了求g(x)的不动点，选取一个初始近似值x0，令xk=g(xk-1)，k=1,2,…。以产生序列{xk}，这一类迭代法称为不动点迭代法，或Picard法。 g(x)称为迭代函数。 若g(x)连续， ，则p是g(x)的一个不动点，p为方程f(x)=0的解。 将隐式方程x=g(x)的求根问题归结为计算一组显式公式xk+1=g(xk)——逐步显式化的过程。 图例 确定y=g(x)与y=x的交点。 如何构造迭代格式？ 例题 方程f(x)=x3+2x2-4=0在区间[1，2]中有一个根。 取x0=1.5。 选取迭代格式的基本原则： picard迭代产生的迭代序列{xk}在g(x)的定义域中； 迭代序列{xk}收敛，且收敛速度尽可能快。 关于最简单函数g(x)=ax+b的讨论 定理1  假设g(x)为定义在有限区间[a，b]上的一个实函数，满足下列条件： (1) (2) Lipschitz条件，且Lipschitz常数L1，即存在正常数L1，使得则对任意的初始值x0 ∈[a，b] ，由Picard迭代产生的序列都收敛于g(x)的唯一不动点p，并有误差估计式 证明 (1) 不动点存在且唯一； (2) 收敛； (3) 误差。 推论 条件(2)改为g(x)的导数g’(x)在[a，b