前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >#数值分析读书笔记（4）求非线性方程的数值求解

#数值分析读书笔记（4）求非线性方程的数值求解

作者头像
Mezereon
发布于 2018-09-13 13:38:42
9910
发布于 2018-09-13 13:38:42
举报
文章被收录于专栏：MyBlogMyBlogMyBlog

数值分析读书笔记（4）求非线性方程的数值求解

1.关于非线性方程的根的定位以及二分法

我们直接介绍二分法

将有根区间

[a,b]
[a,b]

用中点

x_{0}=\frac{a+b}{2}
x_{0}=\frac{a+b}{2}

将它平分, 如果

x_{0}
x_{0}

不是

f(x)
f(x)

的零点, 则再做搜索, 检查

f(x_{0})
f(x_{0})

和

f(a)
f(a)

是否同号, 然后即可知根落在左侧还是右侧, 用这个中点来代替掉原来的端点, 然后得到一个新的区间, 如此反复迭代下去之后, 我们会发现区间收敛到接近一个数

二分法简单易懂,我们只要不断去计算中点,然后判断符号,从而来判断根的位置 但是二分法有着收敛速度慢的缺点,我们一般是用二分法来找到一个合适的初始值,然后再用其他收敛速度比较快的算法进行计算

我们可以用代码来实现一下二分法

public class NumericalTest {
    public static void main(String[] args){
        double a=0,b=2,mid=(a+b)/2,fa,fb,fmid;
        for(int i=0;i<100;i++){
            System.out.println(mid);
            fa=function(a);
            fb=function(b);
            fmid=function(mid);
            if(fa*fmid>0){
                a=mid;
            }else{
                b=mid;
            }
            mid=(a+b)/2;
        }
    }
    public static double function(double x){
        return Math.pow(x,3)+2*Math.pow(x,2)-4;
    }
}

给出最后的输出结果

1.1303954347672787 1.1303954347672787 1.1303954347672787 1.1303954347672787 1.1303954347672787 1.1303954347672787 1.1303954347672787

2.基于不动点原理的迭代法

类似于之前关于迭代法求解线性方程组时所讲过的Gauss-Seidel迭代以及Jacobi迭代等迭代的方法,我们对于非线性方程也可以使用这种基于不动点原理的迭代法,这时我们的目的即是构造出一个等价的非线性方程

x=\varphi(x)
x=\varphi(x)

我们用简单的代码来模拟一下

public class NumericalTest {
        public static void main(String[] args){
            double x=0;
            for(int i=0;i<100;i++){
                x=function(x);
                System.out.println(x);
            }
        }
        public static double function(double x){
            return Math.sqrt((4-Math.pow(x,3))/2);
        }
}

上面的代码是对

f(x)=x^{3}+2x^{2}-4=0
f(x)=x^{3}+2x^{2}-4=0

进行转换, 并且建立迭代格式

x^{(k+1)}=\left(\frac{4-(x^{(k)})^{3}}{2} \right)^{\frac{1}{2}}
x^{(k+1)}=\left(\frac{4-(x^{(k)})^{3}}{2} \right)^{\frac{1}{2}}

最后可以看出来应该是收敛的,给出最后的几个输出

1.1303954901953999 1.1303953877755042 1.130395474606742 1.1303954009915165 1.1303954634022533 1.1303954104906446

这里给出不动点迭代的三个基本要求

  • 适定性: 要保证序列
\{x_{k}\}
\{x_{k}\}

始终在

\phi(x)
\phi(x)

的定义域中,才能使迭代不中断

  • 收敛性: 要求迭代收敛
  • 收敛率: 要求收敛速度尽可能高

接下来我们来研究一下不动点的存在性以及迭代法的全局收敛性

关于不动点的存在性,给出一个Lipschitz条件,且给出不动点存在与唯一性定理

设迭代函数

\varphi (x)\in C[a,b]
\varphi (x)\in C[a,b]

, 且同时满足 1. 定义域条件:

\varphi(x) \in [a,b]
\varphi(x) \in [a,b]

,

\forall x \in [a,b]
\forall x \in [a,b]

**2. Lipschitz条件:存在Lipschitz常数

0<L<1
0<L<1

,使得对任意

t,s \in [a,b]
t,s \in [a,b]

有

\begin{vmatrix}\varphi(t)-\varphi(s)\end{vmatrix}\leq L\begin{vmatrix} t-s\end{vmatrix}
\begin{vmatrix}\varphi(t)-\varphi(s)\end{vmatrix}\leq L\begin{vmatrix} t-s\end{vmatrix}

** 则不动点迭代函数

\varphi(x)
\varphi(x)

在

[a,b]
[a,b]

上存在唯一的不动点

x^{*}
x^{*}

需要注意的是,这是不动点存在且唯一的一个充分条件,却不是必要的, 也就是说如果不满足这两个条件或不满足其中一个条件者,可能存在不动点

下面给出不动点迭代收敛与误差估计的定理

设迭代函数

\varphi (x) \in C[a,b]
\varphi (x) \in C[a,b]

满足上述的定义域条件以及Lipschitz条件,则对任意的

x_{0} \in [a,b]
x_{0} \in [a,b]

, 由不动点迭代格式产生的序列

\{ x_{k}\}^{\infty}_{k=0}
\{ x_{k}\}^{\infty}_{k=0}

必收敛于

\varphi(x)
\varphi(x)

的不动点

x^{*}
x^{*}

,并有误差估计

\begin{vmatrix} x^{*}-x_{k}\end{vmatrix}\leq \frac{L^{k}}{1-L}\begin{vmatrix}x_{1}-x_{0}\end{vmatrix}
\begin{vmatrix} x^{*}-x_{k}\end{vmatrix}\leq \frac{L^{k}}{1-L}\begin{vmatrix}x_{1}-x_{0}\end{vmatrix}
\begin{vmatrix} x^{*}-x_{k}\end{vmatrix}\leq \frac{L}{1-L}\begin{vmatrix}x_{k}-x_{k-1}\end{vmatrix}
\begin{vmatrix} x^{*}-x_{k}\end{vmatrix}\leq \frac{L}{1-L}\begin{vmatrix}x_{k}-x_{k-1}\end{vmatrix}

上述两个不等式,有时称前者为先验估计,后者为后验估计

利用上面的不等式,我们可以计算出给定误差界限所需要迭代的步数

n \geq \frac{ln(\frac{\epsilon (1-L)}{\begin{vmatrix} x_1-x_0\end{vmatrix}})}{lnL}
n \geq \frac{ln(\frac{\epsilon (1-L)}{\begin{vmatrix} x_1-x_0\end{vmatrix}})}{lnL}

其中

\epsilon
\epsilon

为给定的误差界限

给出一个推论

设迭代函数

\varphi(x) \in C[a,b]
\varphi(x) \in C[a,b]

,

\frac{d\varphi}{dx}
\frac{d\varphi}{dx}

在

[a,b]
[a,b]

上有界,且

\begin{vmatrix} \frac{d \varphi}{dx} \end{vmatrix} \leq L < 1 , \forall x\in [a,b]
\begin{vmatrix} \frac{d \varphi}{dx} \end{vmatrix} \leq L < 1 , \forall x\in [a,b]

则之前给出的不动点唯一定理以及后续的收敛定理均成立

以上给出的条件可能是基于全局收敛的,如果满足的条件只是限制在某个领域之中的话,那么就是局部收敛,对于局部收敛,也只需证明局部满足上述条件,需要提一下的是,不动点的迭代方案,在全局的情况下属于线性收敛

3.Newton切线法

解非线性方程组,除了我们之前讲述的迭代法以及二分法,还有Newton切线法,这一种方法是解非线性方程组常用的有效方法,特别的,当初始值充分接近方程的根的时候,收敛的很快,基本思想是以直代曲,近似成线性方程来求解,下面给出迭代的格式

x_{k+1}=x_{k}-\frac{f(x_{k})}{f'(x_{k})}, k=0,1,2,\dots
x_{k+1}=x_{k}-\frac{f(x_{k})}{f'(x_{k})}, k=0,1,2,\dots

这里直接给出代码来进行模拟

public class NumericalTest {
    public static void main(String[] args){
        double x=1;
        for(int i=0;i<20;i++){
            System.out.println(x);
            x=x-(function(x)/function2(x));
        }
    }
    public static double function(double x){
        return Math.pow(x,3)+2*Math.pow(x,2)-4;
    }

    //求导后的函数
    public static double function2(double x){
        return 3*Math.pow(x,2)+4*Math.pow(x,2);
    }

}

比起二分法或者迭代法,它的收敛速度还是较为快速的,特别是当初始值接近根的情况,更加明确的说,Newton切线在充分接近单根的情况下二次收敛,其他情况下线性收敛,充分接近重根的情况下线性收敛

下面针对Newton切线需要计算导数的这一缺点,给出另外一种类似的方法,即割线法

这里直接给出迭代的格式

x_{k+1}=x_{k}-\frac{f(x_{k})}{f(x_{k})-f(x_{k-1})}(x_k-x_{k-1}), k=1, 2 ,\dots
x_{k+1}=x_{k}-\frac{f(x_{k})}{f(x_{k})-f(x_{k-1})}(x_k-x_{k-1}), k=1, 2 ,\dots

给出代码的实现

public class NumericalTest {

    public static void main(String[] args){
        double x1=1,x2=0,temp;
        for(int i=0;i<20;i++){
            System.out.println(x2);
            temp=x2;
            x2=x2-(x2-x1)*(function(x2)/(function(x2)-function(x1)));
            x1=temp;
        }
    }
    
    public static double function(double x){
        return Math.pow(x,3)+2*Math.pow(x,2)-4;
    }
}

割线法的速度也是十分快,而且避免了导数的运算

对于非线性方程求根还有同伦算法,拟牛顿法等,待补充

本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.08.13 ，如有侵权请联系 cloudcommunity@tencent.com 删除
其他

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ，欢迎热爱写作的你一起参与！

其他
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 数值分析读书笔记（4）求非线性方程的数值求解
    • 1.关于非线性方程的根的定位以及二分法
      • 2.基于不动点原理的迭代法
        • 3.Newton切线法
        领券

        腾讯云开发者

        扫码关注腾讯云开发者

        扫码关注腾讯云开发者

        领取腾讯云代金券

        热门产品

        热门推荐

        更多推荐

        Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

        深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

        腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

        Copyright © 2013 - 2024 Tencent Cloud.

        All Rights Reserved. 腾讯云 版权所有

        登录 后参与评论