两个基本定理
方程求根问题一般分为三步进行：
确定跟的分布范围可以采用如下方法：
- 作图法
- 搜索法
不断用定理2（根的存在性定理），不断逼近根的范围
5.2 二分法
实际计算中，不可能完成这种无穷过程；
对这种无穷过程的截断会产生截断误差；只要在精度范围之内就可以
误差估计与分析
也就是二分法的误差不会超过：
一般情况下：由这种方法计算出来的k值往往偏大；但是在不知道真值的情况下，这是确保精度所必须的
检验横坐标精度是否满足要求
检验y值
但是这种方法并不好，因为f(x)未知，这种方法无法保证x的精度
二分法的计算步骤
二分法的特点
优点
缺点
5.3 简单迭代法
用同一个迭代格式，逐次迭代逼近
迭代法的基本思路
由此，构造一个迭代的序列：
- 从一个初值 出发
- 迭代，直到误差足够小
- 选取不同的迭代函数，数学上不完全等价
改变了定义域
- 选取不同的迭代函数，收敛的速度（甚至是否收敛）结果是不同的
问题：这些迭代函数是如何设计出来的？
考察后面的收敛定理
迭代法的几何意义
迭代公式的收敛性与误差估计
问题
- 如何选取迭代函数使得迭代过程收敛？
- 收敛较慢时，如何加速收敛？
定理5.1 迭代法全局收敛定理
第一个要求：要求迭代函数 在平面上的位置在一个正方形区域内
第二个要求：要求迭代函数 的导数绝对值严格小于1
进行误差估计时，尽可能用到最新、最全的数据
例如，进行误差估计判断何时停止迭代时，用①估计的k值可能比②要小
但是定理5.1有如下局限性，即它给出了[a,b]上全局收敛的条件，此时x0在[a,b]上任取即可；但是定理的条件有时难以满足；（也就是，只在真值x*的某一个领域内收敛）
局部收敛的定义
定理5.2 迭代法局部收敛定理
全局收敛定理与局部收敛定理的主要区别在于：
- 全局收敛定理要求迭代函数在整个区间上都满足条件（导数绝对值小于1），此时无论初值选在的哪里都能保证收敛
- 局部收敛定理只要求，迭代格式在某一个领域内收敛；
- 也就是说，局部收敛定理只保证了这个收敛区间的存在性
换句话说：
- 全局收敛定理条件更严格，但使用更方便（初值随便选）
- 局部收敛定理条件相对宽松，但对初值选取有要求（必须足够接近真实解）
根据局部收敛定理，前两种迭代收敛，并且第二种迭代收敛更快；第三种迭代发散
也由此可以看出第二种迭代的设计思路：在真值点附近一阶导数值尽可能小。
实际应用中，我们不知道真值是多少，可以采取如下策略：
5.4 收敛速度与迭代公式加速
收敛速度
一种迭代法具有使用价值，不但需要它是收敛的，还要求它收敛的比较快
收敛速度的定义：描述迭代序列{}收敛到的快慢程度
如果存在常数p>0, C>0，使得：
则称此迭代法具有p阶收敛速度，p称为收敛阶数。其中：
- 当p=1时，称为线性收敛
- 当p=2时，称为二阶收敛（平方收敛）
- 当p=3时，称为三阶收敛
收敛阶数p越大，收敛速度越快。
定理5.3 收敛速度定理
使用求导方式计算收敛速度的步骤：
- 根据迭代函数的性质有：
- 分析误差表达式中最低次项：
- 若，则为线性收敛(p=1)
- 若，则为二阶收敛(p=2)
- 若，则为三阶收敛(p=3)
因此，设计迭代格式时，应尽可能使迭代函数在根处的低阶导数为0，以获得更高的收敛阶数。
5.4 牛顿迭代法
原理：将非线性方程逐步化为线性方程来求解
由x1向上做垂线和曲线交于一点；过这个点再做切线，重复上述过程
牛顿迭代法是用切线和x轴的交点来近似代替曲线和x轴交点的横坐标
牛顿法的收敛性
定理5.4 牛顿法全局收敛的充分条件
和定理5.1都是充分条件；5.1对所有迭代格式都成立；5.4仅针对牛顿法
牛顿迭代法至少是二阶收敛的
牛顿法的局部收敛定理
1.牛顿法的收敛域的存在性定理：
同样的，可以用此前一般迭代法的局部收敛定理来考察牛顿法的收敛性
2.收敛域的判定定理：
对于牛顿法而言，1、2两条是完全等价的；但是这两条其实都只能判定收敛域的存在性
由此很容易说明，只要牛顿法收敛，就至少具有二阶的收敛速度
因此，可以先用二分法进行预处理，得到一个足够精确的 后再用牛顿法进行求解
牛顿迭代法计算步骤
- 确定初值：选取一个适当的初始值，要求尽可能接近方程的根（验证收敛条件）
- 构造迭代公式：根据牛顿迭代公式进行计算
- 迭代计算：
- 计算当前点处的函数值和导数值
- 代入迭代公式计算下一个迭代点
- 重复此过程直到满足收敛条件
- 收敛判断：设定精度要求，当时停止迭代
注意事项：
- 初值选取对收敛性有重要影响，可以先用二分法获得较好的初值
- 需要确保迭代过程中，否则迭代公式无意义
- 牛顿法具有局部二阶收敛性，收敛速度较快
5.5弦截法
5.5.1 （单点）弦截公式及其收敛性
- 用弦截法计算，需要选取两个初值
- 弦截法的收敛速度比牛顿法慢；从图中也可以看出来
- 此外，这种方法是单点弦截法，也就是初始的 是始终没变的，这和牛顿法也不同
找切线的是牛顿迭代；用割线的是弦截法
5.5.2 快速（双点）弦截法
- 这条割线的起点和终点都是不断在往前推的
- 用到了更多的信息，收敛的速度更快
- 同样需要两个初值
- 只要是弦截法，都需要两个初值（因为要计算初始的割线）
快速弦截法计算步骤：
- 选取初值：选择两个初始值和
- 构造迭代公式：使用公式
其中k=1,2,...
- 迭代计算：
- 计算当前两个点和处的函数值
- 代入迭代公式计算下一个迭代点
- 更新迭代点，继续计算直到满足收敛条件
- 收敛判断：设定精度要求，当时停止迭代
注意事项：
- 需要两个初值来开始迭代过程
- 每次迭代都会更新两个计算点，这使得收敛速度比单点弦截法更快
- 要注意分母不能为0
- 收敛速度介于单点弦截法和牛顿法之间
