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

数值分析读书笔记(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;
    }
}

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

教程 | 从字符级的语言建模开始,了解语言模型与序列建模的基本概念

选自imaddabbura 机器之心编译 你有没有想过 Gmail 自动回复是如何进行的?或者手机在你输入文本时如何对下一个词提出建议?生成文本序列的通常方式是...

4065
来自专栏信数据得永生

《Scikit-Learn与TensorFlow机器学习实用指南》第15章 自编码器

4107
来自专栏轮子工厂

神经网络的相关概念

感知机是由科学家Frank Rosenblatt发明于1950至1960年代,它受到了Warren McCulloch 和Walter Pitts的更早工作的启...

963
来自专栏专知

【NAACL 2018】Self-attention考虑相对位置,谷歌Vaswani团队最新工作

2545
来自专栏SeanCheney的专栏

《Scikit-Learn与TensorFlow机器学习实用指南》 第15章 自编码器

自编码器是能够在无监督的情况下学习输入数据的有效表示(叫做编码)的人工神经网络(即,训练集是未标记)。这些编码通常具有比输入数据低得多的维度,使得自编码器对降维...

1433
来自专栏AI研习社

完全图解RNN、RNN变体、Seq2Seq、Attention机制

本文主要是利用图片的形式,详细地介绍了经典的RNN、RNN几个重要变体,以及Seq2Seq模型、Attention机制。希望这篇文章能够提供一个全新的视角,帮助...

4525
来自专栏绿巨人专栏

机器学习中的基本数学知识

7907
来自专栏AI科技评论

干货 | 完全图解RNN、RNN变体、Seq2Seq、Attention机制

AI科技评论按:本文作者何之源,原文载于知乎专栏AI Insight,AI科技评论获其授权发布。 本文主要是利用图片的形式,详细地介绍了经典的RNN、RNN几个...

5004
来自专栏机器之心

学界 | 谷歌大脑提出对抗正则化方法,显著改善自编码器的泛化和表征学习能力

无监督学习的目标之一是不依靠显式的标注得到数据集的内在结构。自编码器是一种用于达成该目标的常见结构,它学习如何将数据点映射到隐编码中——利用它以最小的信息损失来...

942
来自专栏数值分析与有限元编程

有限元类型

从变分原理角度来看,按照所选取的独立自变函数的类型,可以分为如下几种类型: 1 协调类型 以位移作为独立自变函数,使用的变分原理是最小势能原理。作为独立自变函...

2884

扫码关注云+社区

领取腾讯云代金券