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

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

我们直接介绍二分法

将有根区间 用中点 将它平分, 如果不是的零点, 则再做搜索, 检查和是否同号, 然后即可知根落在左侧还是右侧, 用这个中点来代替掉原来的端点, 然后得到一个新的区间, 如此反复迭代下去之后, 我们会发现区间收敛到接近一个数

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

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

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迭代等迭代的方法,我们对于非线性方程也可以使用这种基于不动点原理的迭代法,这时我们的目的即是构造出一个等价的非线性方程

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

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);
        }
}

上面的代码是对进行转换, 并且建立迭代格式

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

1.1303954901953999
1.1303953877755042
1.130395474606742
1.1303954009915165
1.1303954634022533
1.1303954104906446

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

• 适定性: 要保证序列始终在的定义域中,才能使迭代不中断
• 收敛性: 要求迭代收敛
• 收敛率: 要求收敛速度尽可能高

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

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

设迭代函数 , 且同时满足
1. 定义域条件: ,
**2. Lipschitz条件:存在Lipschitz常数 ,使得对任意有 **
则不动点迭代函数在上存在唯一的不动点

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

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

设迭代函数满足上述的定义域条件以及Lipschitz条件,则对任意的, 由不动点迭代格式产生的序列必收敛于的不动点,并有误差估计

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

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

其中 为给定的误差界限

给出一个推论

设迭代函数, 在上有界,且

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

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

3.Newton切线法

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

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

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切线需要计算导数的这一缺点,给出另外一种类似的方法,即割线法

这里直接给出迭代的格式

给出代码的实现

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;
    }
}

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

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