动算方没 第六章逐次逼近法 S63非线性方程的迭代法
第六章 逐次逼近法 §6.3 非线性方程的迭代法
§63非线性方程的迭代法 方程是在科学研究中不可缺少的工具 方程求解是科学计算中一个重要的研究对象 几百年前就已经找到但是,对于更高次数 了代数方程中二次至的代数方程目前仍 五次方程的求解公式无有效的精确解法 对于无规律的非代数方程的求解也无精确解法 因此研究非线性方程的数值解法成为必然
§6.3 非线性方程的迭代法 方程是在科学研究中不可缺少的工具 方程求解是科学计算中一个重要的研究对象 几百年前就已经找到 了代数方程中二次至 五次方程的求解公式 但是,对于更高次数 的代数方程目前仍 无有效的精确解法 对于无规律的非代数方程的求解也无精确解法 因此,研究非线性方程的数值解法成为必然
设非线性方程f(x)=0 如果存在一点x*,使得f(x)=0 则称x*为方程(1)的根或零点 如果方程(1)在区间[a,b上只有一个根, 则称[a,b为单根区间 如果方程(1)在区间[a,b]上有多个根, 则称[a,b为多根区间 本节主要研究单根区间上的求解方法
设非线性方程 f ( x) = 0 --------(1) 如果存在一点 x*, 使得 f ( x*) = 0 则称 x * 为方程 (1)的根或零点 如果方程 (1)在区间 [a ,b]上只有一个根， 则称 [a ,b ]为单根区间 如果方程 (1)在区间 [a ,b]上有多个根， 则称 [a ,b]为多根区间 本节主要研究单根区间上的求解方法
、简单迭代法(基本迭代法) 将非线性方程(1)化为一个同解方程 X 并且假设(x)为连续函数 任取一个初值x,代入(2)的右端,得 q(x0) 继续 2=9(x1 xk+1=9(xk)(k=0,1,2灬…) -(3) 称(3)式为求解非线性方程(2)的简单迭代法
一、简单迭代法(基本迭代法) --------(2) 将非线性方程(1)化为一个同解方程 x = j ( x) 并且假设 j ( x)为连续函数 任取一个初值 x0 ,代入 (2 )的右端 ,得 ( ) 1 0 x = j x ( ) 2 1 x = j x ( ) k 1 k x = j x + 继续 KKK --------(3) (k = 0 ,1,2 ,L) 称(3)式为求解非线性方程(2)的简单迭代法
称φ(x)为迭代函数,称xA为第k步迭代值 如果存在一点x*使得迭代序列{xk满足 lim x,=x (4) 则称迭代法(3)收敛否则称为发散 如果将(2)式表示为 y=x 与方程(2)同解 y=p(x) y y=x y y=(x) 收敛 11 11x3 q(x)在x*附近较平缓
称j( x)为迭代函数 ,称xk为第 k步迭代值 如果存在一点 x*,使得迭代序列 { xk } ¥ 0 满足 lim x x * k k = ® ¥ 则称迭代法(3)收敛,否则称为发散 --------(4) 2 1 0 O x * x x x y = j( x) y = x 1 3 2 0 O x x x * x x y = j( x) y = x 如果将(2)式表示为 y = j ( x) y = x î í ì 与方程(2)同解 收敛 j ( x )在x * 附近较平缓
y=(x) y=x 发散 y=p(x) Mo x x3 x1 x"xo x2 q(x)在x*附近较陡峭 例1.用迭代法求解方程2x3-x-1=0 解:(1)将原方程化为等价方程 x=2x3-1 如果取初值x。=0,由迭代法(3),得
例1. 2 1 0 3 用迭代法求解方程 x - x - = 解: 2 1 3 x = x - (1) 将原方程化为等价方程 如果取初值 x0 = 0,由迭代法 (3), 得 * 2 1 0 O x x x x y = j( x) y = x 3 1 0 2 O x x x * x x y = j( x) y = x 发散 j ( x )在x * 附近较陡峭
x1=2x0-1=-1 x2=2x3-1=-3 1=-55 显然迭代法发散 (2)如果将原方程化为等价方程 x+1 2
2 1 3 x1 = x0 - = -1 2 1 3 x2 = x1 - = -3 2 1 3 x 3 = x2 - = -55 0 x0 = KKK 显然迭代法发散 3 2 + 1 = x x (2) 如果将原方程化为等价方程
仍取初值x=0 xo+1 ≈0.7937 2 x1+1,/1.7937 0.9644 2 依此类推得x2=0944 同样的方程 X3=0.9940 不同的迭代格式 X4=09990 X5=0.9998 有不同的结果 X6=1.0000 迭代函数的构造有关 X7=1.0000 已经收敛,故原方程的解为 什么形式的迭代法 能够收敛呢? x=1.0000
0 x0 = 3 0 1 2 + 1 = x x 仍取初值 3 2 1 = » 0.7937 3 1 2 2 + 1 = x x 3 2 1.7937 = » 0.9644 x2 = 0.9644 x3 = 0.9940 x4 = 0.9990 x5 = 0.9998 x6 = 1.0000 x7 = 1.0000 依此类推,得 已经收敛,故原方程的解为 x = 1.0000 同样的方程 不同的迭代格式 有不同的结果 什么形式的迭代法 能够收敛呢? 迭代函数的构造有关
定理1.设迭代函数(x)在[a,b]连续,且满足 (1)当x∈[a,b时,a≤q(x)≤b; (2)存在一正数L,满足0<L<1,且x∈[a,b]有 Io(xsL (5) 则10.方程x=q(x)在[a,b内有唯一解x* 2对于任意初值x0∈[a,b迭代法xk+1=0(xk)均收敛于x* L (局部收敛性) 3 k WX x 1-L -(6) k 4° k-x≤ (7) 1-L
定理1. 设迭代函数j(x)在[a,b]上连续,且满足 (1) 当x Î [a ,b ]时, a £ j ( x) £ b; (2 ) 存在一正数 L,满足 0 < L < 1,且"x Î [a ,b],有 |j ¢( x)|£ L 1 . x (x) [a,b] x * 则 o 方程 = j 在 内有唯一解 2 . [ , ], ( ) * 0 1 x a b x x x k k o 对于任意初值 Î 迭代法 + = j 均收敛于 1 1 3 . * - - - k - £ k k o x x L L x x 1 0 1 4 . * x x L L x x k k o - - - £ --------(5) --------(6) --------(7) (局部收敛性)
证:设f(x)=x-(x)则f(x)在[a,b上连续可导 由条件(1)f(a)=a-(a)≤0 f(b)=b-q(b)≥0 由根的存在定理,方程f(x)=0在[a,bl上至少有一个根 由 lφ'(x)|L0 则f(x)在[a,b]上单调递增,f(x)=0在[a,b上仅有一个根 所以10.方程x=(x)在[a,b]有唯一解x*
证: 由条件(1) 设f ( x) = x - j( x), f (a) = a - j (a ) £ 0 f (b ) = b - j (b) ³ 0 则f ( x)在[a ,b]上连续可导 由根的存在定理, 方程f (x) = 0在[a,b]上至少有一个根 由 |j ¢( x)|£ L 0 则f (x)在[a,b]上单调递增 , f (x) = 0在[a,b]上仅有一个根 1 . x ( x ) [a ,b] x * 所以 o 方程 = j 在 内有唯一解