下载文档原格式
第4章 非线性方程与非线性方程组的迭代解法--------学习小结一、本章学习体会本章我们主要学习了非线性方程的几种解法，主要有对分法、简单迭代法、steffensen 迭代法、Newton 法、割线法等。
这几种方法都有其思想，并且它们的思想彼此之间有一定的联系。
本章的思路大致可以理解为：1.如何选取迭代公式；2.如何判断迭代公式的收敛速度；3.如何进行迭代公式的修正，以加速收敛；4.如何选取最适合的迭代方法 。
二、本章知识梳理具体求根通常分为两步走，第一步判断根是否存在，若存在，确定根的某个初始近似值；第二步，将初始近似值逐步加工成满足精度要求的结果。
求初始近似值，即确定根的大致区间（a, b ），使（a, b ）内恰有方程的一个根。
本章的学习思路：针对一种迭代方法，找出迭代公式，并判断其收敛性，一般选取收敛速度最快的迭代公式，所以自然的提出了如何使收敛加速的问题。
4.1非线性方程的迭代解法非线性方程的迭代解法有：对分法、简单迭代法、steffensen 迭代法、Newton 法、割线法等。
4.1.1对分法设()[]()()0,<∈b f a f b a C x f 且，根据连续函数的介值定理，在区间()b a ,内至少存在有一个实数s ，使()0=s f 。
现假设在()b a ,内只有一个实数s ，使()0=s f 并要把s 求出来，用对分法的过程： 令b b a a ==00, 对于M k ,....,2,1,0=执行计算2kk k b a x +=若()ηε≤≤-k f a b k k 或，则停止计算取k x s ≈否则转（3）()()k k k k k k b b a a a f x f ==<++11,,0则令()()k k k k k k b b x a a f x f ==>++11,,0则令 若M k =则输出M 次迭代不成功的信息；否则继续。
对分法的局限：对分法只能求实根，而且只能求单根和奇数重根，不能求偶数根和复数根4.1.2简单迭代法及其收敛性迭代法是一种逐次逼近法,用某个固定公式反复校正根的近似值,使之逐步精确化,最后得到满足精度要求的解。
非线性方程组的求解方法及其应用非线性方程组是数学中一类非常重要的问题，其中每个方程都不是线性的。
与线性方程组不同，非线性方程组的求解通常需要借助于数值方法。
本文将讨论一些常见的非线性方程组求解方法，并介绍它们在实际应用中的一些应用。
1. 牛顿法牛顿法是一种非常常见的非线性方程组求解方法。
该方法基于牛顿迭代法原理，将非线性方程组转化为一系列的线性问题。
牛顿法的基本思想是：通过不断地使用一阶导数和二阶导数的信息来逼近方程组的解。
具体地说，在每一轮迭代中，求解一个方程组：$$F(x^{k})+J(x^{k})\Delta x^{k} =0$$其中$F(x)$表示非线性方程组，$x^k$表示第$k$轮迭代的解，$J(x^k)$表示$F(x)$在$x^k$处的雅可比矩阵，$\Delta x^k$表示下降方向，满足$\|\Delta x^k\|\rightarrow 0$。
值得注意的是，牛顿法在每轮迭代中都需要求解一次雅可比矩阵，这需要大量的计算资源。
因此，在实际应用中，牛顿法通常只适用于相对较小的方程组。
2. 信赖域方法相比于牛顿法，信赖域方法更具有通用性。
信赖域方法的基本思想是：在每轮迭代中，通过构造二次模型来逼近目标函数，并在一个信赖域内搜索下降方向。
具体地说，我们在每轮迭代中将非线性方程组$F(x)$在$x^k$处转化为二次模型：$$m_k(\Delta x)=F(x^k)+\nabla F(x^k)^\top \Deltax+\frac{1}{2}\Delta x^\top B_k\Delta x$$其中，$\nabla F(x^k)$是$F(x)$在$x^k$处的梯度，$B_k$是二阶导数信息。
在这里我们假设$B_k$为正定矩阵。
显然，我们希望在$m_k(\Delta x)$的取值范围内找到一个适当的$\Delta x$，使得$m_k(\Delta x)$最小。
因此，我们需要设定一个信赖域半径$\Delta_k$，并在$B_k$所定义的椭圆范围内查找最优的$\Delta x$。
数值分析知识点总结说明：本文只提供部分较好的例题，更多例题参考老师布置的作业题和课件相关例题。
一、第1章 数值分析与科学计算引论1. 什么是绝对误差与相对误差？什么是近似数的有效数字？它与绝对误差和相对误差有何关系？相对误差限：**r re ε=的一个上界。
有效数字：如果近似值*x 的误差限是某一位的半个单位，该位到*x 的第一位非零数字共有n 位，就说x *共有n 位有效数字。
即x *=±10m ×(a 1+a 2×10-1+…+a n ×10-(n-1))，其中a 1≠0，并且*11102m n x x -+-≤⨯。
其中m 位该数字在科学计数法时的次方数。
例如9.80的m 值为0，n 值为3，绝对误差限*211102ε-=⨯。
2. 一个比较好用的公式：f(x)的误差限：()***()'()()f x f x x εε≈ 例题：二、第2章插值法例题：5. 给出插值多项式的余项表达式，如何用其估计截断误差？6. 三次样条插值与三次分段埃尔米特插值有何区别？哪一个更优越？7. 确定n+1个节点的三次样条插值函数需要多少个参数？为确定这些参数，需加上什么条件？8. 三弯矩法：为了得到三次样条表达式，我们需要求一些参数：对于第一种边界条件，可导出两个方程：，那么写成矩阵形式：公式 1对于第二种边界条件，直接得端点方程：，则在这个条件下也可以写成如上公式1的形式。
对于第三种边界条件，可得：也可以写成如下矩阵形式：公式 2求解以上的矩阵可以使用追赶法求解。
（追赶法详见第五章）例题：数值分析第5版清华大学出版社第44页例7三、第3章函数逼近与快速傅里叶变换的正交多项式？什么是[-1,1]上的勒让德多项式？它有3.什么是[a,b]上带权()x什么重要性质？4.什么是切比雪夫多项式？它有什么重要性质？5.用切比雪夫多项式零点做插值点得到的插值多项式与拉格朗日插值有何不同?6.什么是最小二乘拟合的法方程？用多项式做拟合曲线时，当次数n较大时，为什么不直接求解法方程？例题请参考第3章书上的作业题和课件上的例题。
实验报告一题目：非线性方程求解摘要：非线性方程的解析解通常很难给出，因此线性方程的数值解法就尤为重要。
本实验采用两种常见的求解方法二分法和Newton法及改进的Newton法。
前言：（目的和意义）掌握二分法与Newton法的基本原理和应用。
数学原理：对于一个非线性方程的数值解法很多。
在此介绍两种最常见的方法：二分法和Newton 法。
对于二分法，其数学实质就是说对于给定的待求解的方程f(x)，其在[a,b]上连续，f(a)f(b)<0，且f(x)在[a,b]内仅有一个实根x*，取区间中点c，若，则c恰为其根，否则根据f(a)f(c)<0是否成立判断根在区间[a,c]和[c,b]中的哪一个，从而得出新区间，仍称为[a,b]。
重复运行计算，直至满足精度为止。
这就是二分法的计算思想。
Newton法通常预先要给出一个猜测初值x0，然后根据其迭代公式产生逼近解x*的迭代数列{x k}，这就是Newton法的思想。
当x0接近x*时收敛很快，但是当x0选择不好时，可能会发散，因此初值的选取很重要。
另外，若将该迭代公式改进为其中r为要求的方程的根的重数，这就是改进的Newton法，当求解已知重数的方程的根时，在同种条件下其收敛速度要比Newton法快的多。
程序设计：本实验采用Matlab的M文件编写。
其中待求解的方程写成function的方式，如下function y=f(x);y=-x*x-sin(x);写成如上形式即可，下面给出主程序。
二分法源程序：clear%%%给定求解区间b=1.5;a=0;%%%误差R=1;k=0;%迭代次数初值while (R>5e-6) ;c=(a+b)/2;if f12(a)*f12(c)>0;a=c;elseb=c;endR=b-a;%求出误差k=k+1;endx=c%给出解Newton法及改进的Newton法源程序：clear%%%% 输入函数f=input('请输入需要求解函数>>','s')%%%求解f(x)的导数df=diff(f);%%%改进常数或重根数miu=2;%%%初始值x0x0=input('input initial value x0>>');k=0;%迭代次数max=100;%最大迭代次数R=eval(subs(f,'x0','x'));%求解f(x0)，以确定初值x0时否就是解while (abs(R)>1e-8)x1=x0-miu*eval(subs(f,'x0','x'))/eval(subs(df,'x0','x'));R=x1-x0;x0=x1;k=k+1;if (eval(subs(f,'x0','x'))<1e-10);breakendif k>max;%如果迭代次数大于给定值，认为迭代不收敛，重新输入初值ss=input('maybe result is error,choose a new x0,y/n?>>','s');if strcmp(ss,'y')x0=input('input initial value x0>>');k=0;elsebreakendendendk;%给出迭代次数x=x0；%给出解结果分析和讨论：1.用二分法计算方程在[1，2]内的根。
数值分析总结数值分析是研究用计算机和数学方法解决数学问题的一门学科，其核心是通过数值计算方法求解数学问题。
数值分析广泛应用于科学计算、工程计算以及实际问题的数值模拟和优化等领域。
本文将从数值方法的基本原理、数值线性代数、非线性方程求解、插值和曲线拟合、数值微分和数值积分、数值常微分方程等方面对数值分析进行总结。
数值方法的基本原理是将需要求解的数学问题转化为离散的数值计算问题。
数值方法主要包括近似计算、误差分析和收敛性研究。
近似计算通过选择适当的数值计算方法和算法，对原始问题进行精确程度有限的近似计算。
误差分析是研究数值计算和解析解之间的差别，包括截断误差和舍入误差。
收敛性研究是研究离散数值计算方法的收敛性，即当步长趋于零时，数值计算结果趋于解析解。
数值线性代数是数值分析的重要内容之一、数值线性代数主要研究线性代数方程组的数值解法。
常见的数值解法包括高斯消元法、LU分解法、Cholesky分解法等。
解线性代数方程组的数值方法可以分为直接法和迭代法两类。
直接法通过有限次数的计算求得方程组的解，而迭代法是通过求解逐步逼近方程组的解。
非线性方程求解是数值分析的另一个重要内容。
非线性方程求解的目标是找到方程的根，即方程的解。
常见的非线性方程求解方法包括二分法、牛顿法、割线法和迭代法。
这些方法根据不同的原理和特点，对非线性方程根的进行逐步逼近，最终得到根的近似值。
插值和曲线拟合是利用已知数据点确定未知数据点的数值计算方法。
插值方法通过已知数据点之间的连线来估计未知数据点的值。
常见的插值方法有拉格朗日插值法和牛顿插值法。
曲线拟合是通过已知数据点拟合出一条曲线，使得该曲线在已知数据点上与原始数据最接近。
最小二乘法是常用的曲线拟合方法，通过最小化数据点到拟合曲线的垂直距离来得到最佳拟合曲线。
数值微分和数值积分是数值分析的基础性内容。
数值微分是通过差商的定义计算函数在特定点的导数值。
常见的数值微分方法有前向差分法和中心差分法。
非线性方程的数值解法《计算方法》期末论文论文题目非线性方程的数值解法学院专业班级姓名学号指导教师日期目录摘要第1 章绪论1.1 问题的提出和研究目的和意义1.2 国内外相关研究综述1.3 论文的结构与研究方法第2 章非线性方程的数值解法2.1 二分法2.2 迭代法2.3 迭代法的局部收敛性及收敛的阶2.4 牛顿迭代法2.5 牛顿法的改进2.6 插值摘要数值计算方法，是一种研究解决数学问题的数值近似解方法，它的计算对象是那些。
在理论上有解而又无法用手工计算的数学问题。
在科学研究和工程技术中都要用到各种计算方法。
例如 在地质勘探、汽车制造、桥梁设计、天气预报和汉字设计中都有计算方法的踪影。
本文讨论了非线性方程的数值解法：非线性方程的二分法、迭代法原理、牛顿迭代法，迭代法的收敛性条件及适合非线性方程的插值法等等。
第1 章绪论可以证明插值多项式L (x) n 存在并唯一。
拉格朗日插值多项式的算法 step1.输入 插值节点控制数n 插值点序列 i i x , yi=0,1,…,n 要计算的函数点x。
step2. FOR i =0,1,…,n i 制拉格朗日基函数序列问题的提出和研究目的和意义非线性方程的问题在工程实践中有很多用途 研究其数值解法是当前一个研究方向。
目前已有相当一部分算法在广泛使用于工程实践中。
非线性方程组和无约束最优化的数值解法 一直是数值优化领域中热门的研究课题。
本文对传统的方法进行改进和提出新的算法 该算法不仅有重要的论价值，而且有很高的实用价值。
例如在天体力学中，有如下Kepler 开普勒方程 x-t- sin x=0,0< <1,其中t 表示时间 x 表示弧度，行星运动的轨道x 是t 的函数。
也就是说，对每个时刻i t 上述方程有唯一解i x ，运动轨道位置。
国内外相关研究综述随着科学技术的高速发展和计算机的广泛应用 求解形如F(x)=0 的非线性方程组问题越来越多的被提出来了 其中F 是的连续可微函数。
可编辑修改精选全文完整版
非线性方程组的解法
非线性方程组的解法包括：
（1）近似法。
近似法是根据所给非线性方程组，使用一定的数值方法，建立非线性方程组结果的拟合曲线，以此求解非线性方程组的常用方法，目前有贝塔、拉格朗日近似法和微分近似法等。
（2）多元分割法。
多元分割法根据非线性方程组的参数和变量空间，
将整个运算范围分割成多余小区间，利用各区间中只含有一个未知变
量的简单方程组，将非线性方程组转换成多个一元方程组，再用一次法、弦截法和二分法等算法求解，最终得出整个非线性方程组的解。
（3）迭代映射法。
迭代映射法是通过给定一个初始值，然后利用迭代，反复运算，最终达到收敛点的一种方法，主要包括牛顿法、收敛法、
弦截法、松弛法和隐函数法等。
（4）最小二乘法。
最小二乘法是将非线性方程组表示为残差函数，然
后求解残差函数最小值，获得未知变量的最优解，常用于数值分析中。
（5）特征法。
特征法是采用将非线性方程组表示为线性方程组特征值
和它们关于某一特征量的关系式，利用梯度下降法，最小化残差函数，求解非线性方程组的方法。
以上是非线性方程组的解法的简单综述，它们在一定程度上增加了解
决非线性方程组的效率，但并非所有情况都能使用以上求解方法。
正
确使用相应的求解方法就可以有效的求解非线性方程组，以便更好的
解决实际问题。
第四章 非线性方程和方程组的数值解法教学目标：1.了解并掌握非线性方程的根的相关概念，如m 重根、有根区间等概念；2.掌握逐步搜索法和二分法（区间对分法）的基本思想及步骤，了解这两种方法的适用性及缺点，能应用其求解简单的非线性方程；3.了解迭代法的分类，理解并掌握不动点迭代法的概念及相关收敛性定理，掌握全局收敛性及局部收敛性联系及区别，理解收敛阶和计算效率的相关概念的来历及含义；4.了解迭代加速的思想，掌握加权法（松弛法）、Aitken 以及Steffensen 加速方法的思想及相关理论、计算公式；5.理解并掌握Newton 迭代法及求重根的修正Newton 迭代法的思想、实现步骤以及相关理论；6.理解Newton 迭代法的相关变形方法的提出及实现步骤，如简化Newton 法（平行弦法）、Newton 下山法、拟Newton 法和Steffensen 方法；7、理解割线法和Muller 法提出的背景及实现步骤，掌握相关的理论。
教学重点：1.逐步搜索法和二分法（区间对分法）的基本思想及步骤；2.不动点迭代法的概念及相关收敛性定理；3.迭代加速的思想及三种实现方式；4. Newton 迭代法及相关变形或改进的迭代法的思想及步骤。
教学难点：1..不动点迭代法的概念及相关收敛性定理；2.迭代加速的思想及三种实现方式；3. Newton 迭代法及相关变形或改进的迭代法的思想及步骤。
教学方法：教具：§4.1 问题的提出非线性科学是当今科学发展的一个重要研究方向，而非线性方程的求根也成了一个不可缺的内容。
但是，非线性方程的求根非常复杂。
本章重点讨论单个方程的求根方法，对于非线性方程组的解法仅作一些简单的介绍。
这是因为单个方程的求根问题比非线性方程组更普遍。
另外非线性方程组的求解是个难度比较大的问题，许多近代研究集中在这个问题上。
非线性方程和方程组的数值解法主要是迭代法。
一般的非线性方程组可以写成()0F x =，其中F 和x 都是n 维向量。
当1n =时就是单个的方程()0f x =。
为了叙述方便，首先引入下述定义：定义4.1 对于一元非线性方程()0f x =，若()f x 为代数多项式，即01()n n f x a a x a x =+++则称()0f x =为代数（多项式）方程，否则称为超越方程。
例如，2510x x -+=为代数方程，而2520xx -+=则为超越方程。
定义4.2 （1）若存在*x 使*()0f x =，则称*x 是方程()0f x =的解或根，也称*x 是函数()f x 的零点。
（2）若函数()f x 可分解为*()()()m f x x x g x =-⋅，*()0g x ≠其中m 为正整数，则称*x 是方程()0f x =的m 重根，或称*x 是函数()f x 的m 重零点。
当1m =时，称*x 是()0f x =的单根或()f x 的单重零点。
零点*x 可能是实数，也可能是复数。
定理4.1 对于充分可微的函数()f x ，*x 是函数()f x 的m 重零点的充分必要条件是： *'*(1)*()()()0m f x f x f x -====，()*()0m f x ≠定义4.3 若方程()0f x =在区间[,]a b 内至少有一个根，则称[,]a b 为方程()0f x =的有根区间。
通常可用逐步（次）搜索法求方程的有根区间。
定理4.2 若函数()f x 在区间[,]a b 上连续（即[,]f C a b ∈），且()()0f a f b <，则方程()0f x =在(,)a b 内至少有一个根。
定义4.4 若在区间[,]a b 上只有方程()0f x =的一个根，则称[,]a b 为方程()0f x =的隔根区间。
定理4.3 若函数()f x 在区间[,]a b 上单调连续，且()()0f a f b <，则方程()0f x =在(,)a b 内有且仅有一个根。
关于根的个数，由代数学基本定理知，高次代数方程的根（包括实根和复根）的个数与代数方程的次数相同；对于超越方程，可能没有根，也可能有一个或若干个根，甚至无穷多个根。
理论上已经证明，对于次数4≤的代数方程，它的根可以用根式表示，而次数5≥的代数方程，它的根一般不能用根式表示，亦即不能用解析表达式来表示。
因此对于一般的函数方程()0f x =，一般来说，更不存在根的解析表达式，而在实际应用中，也不一定需要得到求根的解析表达式，只要得到满足精度要求的根的近似值就可以了。
求解非线性方程的根的问题大致可分为下面三个方面：（1）根的存在性。
即方程有没有根？如果有根，有几个根？（2）根的分布，即求出有根区间。
（3）根的精确化。
即在已知一个根的近似值后，设法逐步把根精确化，直到满足精度为止。
§4.2 逐步搜索法和二分法4.2.1 逐步搜索法假设()f x 是定义在某区域内的连续函数，在区间[,]a b 有且仅有一个单根*x ，则逐步搜索法的步骤如下：（1）判断()f a 的符号：若()0f a =，则*x a =；若()0f a ≠，则不妨设()0f a >。
（2）选择适当的步长b a h n-=，搜索一步，看()f a h +的符号，若()0f a h +=，则*x a h =+已找到。
若()0f a h +<则可知*(,)x a a h ∈+，这时可取a 或a h +作为*x 的近似值。
若()0f a h +>，则继续往前搜索一步，看(2)f a h +的符号，直到()f a kh +与((1))f a k h +-异号，则可知*1(,)k k x x x -∈，其中1(1)k x a k h -=+-，k x a kh =+，这时可取k x 或1k x -作为*x 的近似值。
逐步搜索法的步长h 的选择很难恰到好处，若h 取得较大，则精度较差；若h 取得足够小，精度提高了，但计算量增加了许多。
因此，如果精度要求较高的话，该方法不太经济。
例4.1 求方程32()11.138.841.77f x x x x =-+-的有根区间。
解：根据有根区间的定义，对方程的根进行搜索计算，结果如下表从上表可以得出方程的三个有根区间为[2,3]，[3,4]和[5,6]。
4.2.2 二分法二分法（对分法）是逐步搜索法的改进。
它的基本思想是逐步将非线性方程()0f x =的有根区间（或隔根区间）二分，通过判断函数值的符号，逐步对半缩小有根区间（或隔根区间），直到区间缩小到容许误差范围之内，然后取区间的中点为根*x 的近似值。
（基本思想：通过计算隔根区间的中点，逐步缩小隔根区间，从而得到方程的近似根） 设()[,]f x C a b ∈，且()()0f a f b ⋅<，则()0f x =在(,)a b 内有根*x 。
为明确起见，再设()0f x =在(,)a b 内仅有一个根。
令0a a =，0b b =，计算000()/2x a b =+和0()f x 。
若0()0f x =，则*0x x =，结束计算。
若00()()0f a f x <，则令10a a =，10b x =，否则令10a x =，10b b =，这样得到新的隔根区间11[,]a b 。
11[,][,]a b a b ⊂，00112b a b a --=。
再令1112a b x +=，若1()0f x =，则*1x x =，否则类似可得新的隔根区间22[,]a b 。
这个过程可一直进行下去，仅当出现()0k f x =时过程中断（其中2k k k a b x +=）。
记第n 次过程得到的隔根区间为[,]n n a b ，则 001122[,][,][,][,]n n a b a b a b a b ⊃⊃⊃⊃⊃*n n a x b <<，0,1,2,n =110022n n n n nb a b a b a -----=== （4.1） 故有 lim()0n n n b a →∞-=，*lim lim 2n n n n n a b x x →∞→∞+== 因此当n 充分大时，2n n n a b x +=可作为方程()0f x =的根*x 的近似值，且有误差估计式 *1||22n n n n b a b a x x +---≤= 对于预先给定的精度0ε>，只要12n b a ε+-<，即 2ln()ln 2log ln 22b a b a n εε--->= （4.2） 便有*||n x x ε-<，这时n x 就是满足精度要求的近似值。
（实际中常用0|()|f x δ<来代替0()0f x =，其中δ为预先给定的小量）分析以上过程不难发现，二分法的收敛速度与公比为1/2的等比级数相同。
由于1021024=，可知大约二分10次，近似根的精度可提高三位小数位。
二分法的思想方法还可以用于搜索一个较大区间[,]a b 内实根的分布情况（不包括偶重实根），实际做法是：取适当的步长b a h m -=，逐一检验小区间[,(1)]a kh a k h +++（0,1,,1k m =-）两端的函数值是否异号，若异号，则按以上二分法求出其中的根；若同号则不作求根运算而转入检查下一个区间，只要h 选得适当小，则可求出[,]a b 内的所有奇重实根（包括单实根）。
h 选得过大，可能漏掉某些根；h 选得过小，则计算量增大。
二分法的优点是程序简单、方法可靠、易于在计算机上实现，事先估计计算次数容易，收敛速度恒定，对函数的性质要求低，只要连续就可以了；它的局限性是不能求偶数重根，也不能求复根和虚根。
另外，二分法在求根过程中，只用到了函数的符号，而未用到计算出的函数值，这总有点浪费。
实际应用中这个方法可用于求根的初始近似值，以便使用其它的求根高速迭代法，有时也用来试探实根的分布区间。
例4.2 用二分法求方程3()10f x x x =--=在区间[1.0,1.5]内的一个实根，要求精确到小数点后第二位（即误差不超过0.005）。
解：这里 1.0a =， 1.5b =，而()0f a <，()0f b >，故在区间[1.0,1.5]内有根。
由（4.2）式可得 ln(1.5 1.0)ln 0.01 5.644ln 2n -->≈ 故只要二分6故6 1.3242x =为方程的近似根，误差不超过0.005。
§4.3 迭代法4.3.1 迭代法分类迭代法是一种逐步逼近根的方法，已知方程()0f x =的一个近似根后，通常使用某个固定公式反复校正根的近似值，使之逐步精确化，一直到满足给定的精度要求为止。
迭代法可分为单点迭代法和多点迭代法。
