当前课程知识点：Numerical Analysis > [Week 3] Error Analysis > 3. [Lecture] Fixed Point Iteration > video
返回《Numerical Analysis》慕课在线视频课程列表
返回《Numerical Analysis》慕课在线视频列表
现在是不动点迭代
如果Pn是通过不动点迭代得到的
则Pn和准确解的差的绝对值小于
k的n次方乘以
p0-a或者b-p0两个值中的最大值
这里还有另外一个结果
pn-p的绝对值小于等于k^n/(1-k)再乘以p1-p0的绝对值
我们从数学上来证明一下这两个不等式。显然，P属于区间[a,b]
我们从数学上来证明一下这两个不等式。显然，P属于区间[a,b]
我们考虑一下pn-p的绝对值
根据学习过的不动点的内容
pn的值等于
g(pn-1), p的值等于
g(pn), 因为pn是不动点
注意，我们不动点迭代求解的算法是pn=g(pn-1)
所以这里我们可以反复使用这个迭代公式
在这里我们可以怎样处理呢
通常，在大多数这种类型的问题的证明中
关键点是中值定理的使用
我们在这里应用中值定理
我们先来回顾一下中值定理
中值定理是什么呢
如果存在这样一条曲线
考虑连接函数图像上对应a和b两点的直线
这时我们可以得到这条直线的斜率
那么存在a和b之间的一点，该点处切线的斜率和直线的斜率相同
即，存在c属于区间[a,b]， 使得
(f(b)-f(a))/(b-a)
这个值就是连接a和b两点的直线的斜率
等于c点的切线的斜率
这就是中值定理
我们现在应用这个定理
则有某一点 ζn处 的导数g’(ζn)的绝对值
乘以|pn-1 -p|. 由中值定理我们可以很容易得到这个结果
我们用k表示这一项的最大值
可以得到k乘以|pn-1 -P|
我们可以重复上述过程
重复一次后可以得到k的平方乘以|pn-2 -P|
所以，pn中,这里n变为n-1, 出来一个k
变成pn-2后, 又出来一个k
所以，如果继续重复这个方法，最后我们得到k的n次方乘以p0-p的绝对值
在这个不等式中，我们并不知道p的值
这时我们可以用我们已知的值来代替p的值
K的n次方乘以我们前面提到的p0-a和 b-p0这两个值中的最大值
如果我们用这两个值中的最大值来替代，
则这个最大值必须要大于|p0-p|
这一点很容易解释
如果这里是a, 这里是b, 则p和p0位于这两点之间
显然，可以看到，上述不等式成立
下面，我们来证明第二个不等式
我们用相似的方法来证明
同样的，先给定迭代方法和迭代序列
这里，我们考虑pn+1 -pn的绝对值
因为这是由不动点迭代得到的序列
于是我们得到 |g(pn)-g(pn-1)|
和我们在上一个证明中用的方法一样，我们可以得到k乘以|pn- pn-1|
这是应用中值定理得到的结果
重复利用这个关系式，则最后会得到k的n次方
以及p1-p0的绝对值
现在我们来这样考虑一下
假设n是大于1小于m的自然数
我们计算pm-pn的绝对值是多少
这个值等于pm- pm-1,这里减去了pm-1
所以需要再加上pm-1
再减去pm-2，不断加下去
一直加到哪个值为止呢
因为是在m和n之间的自然数，所以要到n为止
所以前面加上pn+1, 最后减去pn
现在我们分别考虑这些值
根据绝对值的性质
各项取绝对值再相加
得到三角不等式
所以，右边的值更大
于是有，pm - pm-1的绝对值加上pm-1 - pm-2的绝对值
把各个绝对值分别相加
最后是加上pn-1 - pn的绝对值
现在每项里面的序列下标只相差1，根据我们前面推导出的不等式
可以得到
从这里可以看到，如果是n,那么会有k的n次方乘以|p1 - p0|
由此，对每一项我们都可以得到一个不等式
所以，对第一项，因为下标是n的时候有n次方，这里下标是m-1，所以会出现m-1次方
乘以p1 - p0的绝对值
现在考虑第二项，我们得到加上k的(m-2)次方
乘以p1 - p0的绝对值
以此类推，最后我们得到k的n次方乘以p1 - p0的绝对值
这里每一项都包含了p1 - p0
利用分配律，我们可以求从k的(n-1)次方到k的n次方的和
于是我们得到
k的n次方乘以p1 - p0的绝对值
再乘以k的(m-n-1)次方
一直加到k的平方,加k,加1
很容易验证 把这个式子展开就是上面的式子，
我们还有哪些已知的条件呢
因为我们是在假设解存在的条件下使用的不动点迭代
所以，如果m趋于无穷，则Pm收敛到不动点
由此可以得到
|p -pn|的值等于m趋于无穷时 |pm - pn|的值
|p -pn|的值等于m趋于无穷时 |pm - pn|的值
因为我们前面求得的这个值小于等于右边的值
于是，我们可以得到不等式，令m趋于无穷
K的n次方乘以|p1 - p0|，再乘以这一项
这里，m趋于无穷
于是我们得到等比级数
这里等比级数的和为1/(1-k)
于是，我们得到了1/(1-k)，这里，等式右边还有k的n次方
以及我们得到的||p1 - p0||项
所以，我们证明了第二个不等式
那么，像我们前面讲的，
我们说不动点迭代的误差在这个范围内
我们用一个例子来验证一下
不动点迭代需要满足几个条件
所以，给定一个函数，我们首先应该验证什么呢
首先要确认不动点是否存在
所以，在这个例题中，我们分几种情况来考虑
首先，给定函数g1(x)
那么，要是不动点存在的话
如果我把这个区间的所有值代入到函数中，那么函数值的取值范围是什么呢
所有函数值也都要属于区间[1,2]
我们来检验一下
g1(1)等于6
g1(2)等于-12
这两个值不属于区间[1,2]
所以不动点迭代无法使用
还有什么呢
还需要检验导数
求导后得到导函数
由此可得，导函数的绝对值大于1
所以，还是不能保证不动点迭代的使用
所以，这个情况下我们不能使用不动点迭代
现在，在可以使用不动点迭代的情形
我们来验证一下其误差
考虑函数g2(x)
令g2(x)为这样的函数
x的3次方的平方根
好，这个函数满足我们刚刚验证过的所有条件吗
同学们可以自己来验证一下
如果所有的条件都满足， 导数值的条件也满足
那么我们就可以直接使用之前学过的不动点迭代
在使用不动点迭代的时候，大家分析一下每一个函数的不同之处
我把这个留作课后作业
大家来做一下试试
-1. [Warming up]
-2. [Lecture] 前言（들어가는 말）
--Guide
--video
-3. [Lecture] What is Mathematics?
--Guide
--video
-4. [Lecture] What is Numerical Analysis?
--Guide
--video
-5. [Lecture] 数值分析的领域（수치해석의 영역）
--Guide
--video
-6. [Activity] QUIZ
-1. [Warming up]
-2. [Lecture] Introduction & Bisection Method
--Guide
--video
-3. [Lecture] Fixed Point Iteration
--Guide
--video
-4. [Lecture] Newton's Method
--Guide
--video
-5. [Activity] QUIZ
-1. [Warming up]
-2. [Lecture] Introduction & Bisection Method
--Guide
--video
-3. [Lecture] Fixed Point Iteration
--Guide
--video
-4. [Lecture] Newton's Method
--Guide
--video
-5. [Activity] QUIZ
-1. [Warming up]
-2. [Lecture] Introduction & Lagrange Polynomial
--Guide
--video
-3. [Lecture] Divided Difference
--Guide
--video
-4. [Lecture] Binomial Theorem
--Guide
--video
-5. [Lecture] Spline
--Guide
--video
-6. [Activity] QUIZ
-1. [Warming up]
-2. [Lecture] 积分，微分简介（적분, 미분 소개）
--Guide
--video
-3. [Lecture] Newton Cotes Formula
--Guide
--video
-4. [Lecture] Simpson's Rule
--Guide
--video
-5. [Activity] QUIZ
-1. [Warming up]
-2. [Lecture] Polynomial Version
--Guide
--video
-3. [Lecture] Matrix Version (Gauss Elimination)
--Guide
--video
-4. [Lecture] Numerical Version
--Guide
--video
-5. [Lecture] Determinant
--Guide
--video
-6. [Lecture] Example
--Guide
--video
-7. [Activity] QUIZ
-1. [Warming up]
-2. [Lecture] LU Factorization
--Guide
--video
-3. [Lecture] 计算方法（계산법）
--Guide
--video
-4. [Lecture] Existence and Uniqueness
--Guide
--video
-5. [Lecture] Cholesky Factorization
--Guide
--video
-6. [Activity] QUIZ
-期中考试（중간고사）
-1. [Warming up]
-2. [Lecture] Proof
--Guide
--video
-3. [Lecture] Gram-Schmidt Process
--Guide
--video
-4. [Lecture] Example
--Guide
--video
-5. [Lecture] Matrix Norms
--Guide
--video
-6. [Activity] QUIZ
-1. [Warming up]
-2. [Lecture] Jacobi Iterative Method
--Guide
--video
-3. [Lecture] Gauss Seidel Iterative Method
--Guide
--video
-4. [Lecture] Convergence Theorem
--Guide
--video
-5. [Lecture] Example
--Guide
--video
-6. [Activity] QUIZ
-1. [Warming up]
-2. [Lecture] Definition
--Guide
--video
-3. [Lecture] Theorem & Example 1
--Guide
--video
-4. [Lecture] Theorem & Example 2
--Guide
--video
-5. [Lecture] Theorem & Example 3
--Guide
--video
-6. [Lecture] Theorem & Example 4
--Guide
--video
-7. [Activity] QUIZ
-1. [Warming up]
-2. [Lecture] First Order Equation
--Guide
--video
-3. [Lecture] Euler's Method
--Guide
--video
-4. [Lecture] Error Analysis
--Guide
--video
-5. [Lecture] Euler Method
--Guide
--video
-6. [Activity] QUIZ
-1. [Warming up]
-1. [Lecture] Introduction
--Guide
--video
-2. [Lecture] n-th Runge-Kutta Methods
--Guide
--video
-3. [Lecture] Multi Step Method
--Guide
--video
-4. [Lecture] Explicit
--Guide
--video
-5. [Lecture] Example
--Guide
--video
-QUIZ
-1. [Warming up]
-2. [Lecture] Boundary Value Problem With O.D.E.
--Guide
--video
-3. [Lecture] Partial Differential Equations
--Guide
--video
-4. [Activity] QUIZ
-期末考试（기말고사)