关于牛顿迭代法求多项式方程根及其算法实现
本帖最后由 Lifetimer 于 2020-7-19 18:53 编辑# 前言
这是我和我的一个朋友讲牛顿迭代法求解方程的根时写的文字，想了想还是发出来给大家看看。
因为我快要期末考试了，没时间作图了，现在只写一个文字描述，那天有时间再补图。
也有可能补不了，因为我是高中生，学业繁忙。
---
# 注意事项
好像吾爱破解论坛的markdown编辑器不支持latex公式语法呀，我的公式显示不出来，如果真是这样的话，你可以凑合着来看，结合源码应该很容易看懂，我也没时间处理这个了。
如果版主看到觉得不妥，可以直接删帖，不必通知我
---
# 基本步骤
1.给定一个函数
2.求导
3.给定一个点
4.求该点切线方程
5.求解切线方程y=0时x的取值
6.将x对应于原函数生成一个点
7.重复第4步
---
## 1.给定一个函数
在生成程序时就直接定义（计算器高级一些所以可能有正则表达式搜索自动识别函数
## 2.求导
我只展示多项式求导
## 3.给定一个点
用户自行输入，不必多说
定义为$x_{a}$
## 4.求该点切线方程
由微积分知识易得，(运用点斜式方程)
$$y-f(x_{0})=f^{'}(x_{0})(x-x_{0})$$
## 5.求解y=0时x的取值
易解得：
$$x=\frac{0-f(x_{0})}{f^{'}(x_{0})}+x_{0}$$
即为
$$x=x_{0}-\frac{f(x)}{f^{'}(x)}$$
## 6.将x对应于原函数生成一个点
该点为$(x,f^{'}(x))$
## 7.回到第四步
------
# 开始写算法
可见，牛顿迭代法的核心是给定一个点后不断地：
4.求该点切线方程
5.求解y=0时x的取值
6.将x对应于原函数生成一个点
所以我们可以编写一个函数double newton(double x);
## 原始函数定义（此处以二次方程为例）
```
double a,b,c;
//表示方程为 ax^2+b^x+c=0
```
## 导函数定义（此处以二次方程为例）
```
double k,b;
//表示方程为 y=kx+b
```
其中，k=a*2,b=b
## newton函数编写
```
double newton(double x){
double yuanf = a*x*x+b*x+c; // 原函数
double daof = k * x + b; //导函数
double chu = yuanf/daof; //原函数/导函数
x = x - chu;
return newton(x);
}
```
结合实际情况，我们可以对Newton函数进行优化。
## newton函数优化
```
double newton(double x){
if(tip == goal){
double yuanf = a*x*x+b*x+c; // 原函数
double daof = k * x + b; //导函数
double chu = yuanf/daof; //原函数/导函数
x = x - chu;
tip++;
return newton(x);
}
return x;
}
```
## 全局变量的声明
```
double a=0,b=0,c=0;//原函数
double k=0;//导函数斜率
int tip = 0,goal;//当前迭代次数、预期迭代总数
```
## main函数的编写
```
int main(){
cout << "请输入a，b，c";
cin >> a >> b >> c;
cout << "请输入目标迭代总数";
cin >> goal;
int x;
cout << "请先给出一个x：";
cin >> x;
k = a * 2;
double result = newton(x);
cout << "迭代次数为：" << tip << "结果为" << result;
return 0;
}
```
---
# 最终整理出我们需要的牛顿法
```
#include<iostream>
#include<cstdio>
using namespace std;
double a = 0, b = 0, c = 0;//原函数
double k = 0;//导函数斜率
int tip = 0, goal;//当前迭代次数、预期迭代总数
double newton(double x) {
if (tip == goal) {
return x;
}
double yuanf = a * x * x + b * x + c; // 原函数
double daof = k * x + b; //导函数
double chu = yuanf / daof; //原函数/导函数
x = x - chu;
tip++;
return newton(x);
}
int main() {
cout << "请输入a，b，c";
cin >> a >> b >> c;
cout << "请输入目标迭代总数";
cin >> goal;
int x;
cout << "请先给出一个x：";
cin >> x;
k = a * 2; //由微积分知识易得
double result = newton(x);
cout << "迭代次数为：" << tip << "结果为" << result;
return 0;
}
```
emm 大概就是这样了吧。
## 新增部分
还是去VScode截了一张图将那个latex公式没识别出来的地方展示一下：
从0开始的小小怪 发表于 2020-7-19 18:58
这倒是，我反正就学了点皮毛，实在不怎么感兴趣，你喜欢的话欢迎报考数学系，数值分析研究这个比较深入
其实没有
只是我朋友在用计算器的时候看到有个牛顿法，就来问我是什么东西，因为知道我是学算法的。
当时不好演示，就回家录了个视频，用GeoGebra和Visual Studio Code和Visual Studio演示了一下。
这个是我当时打的字，相当于老师上课的PPT，
讲完了后想了想觉得可能你们有用，
就发到了这里 依稀记得牛顿上山下山法，还有高斯公式，知识果然还是不用忘得快 现在高中生业余时间就玩这些了吗，不能好好去网吧开黑吗。越来越不懂00后了{:301_973:} 布点丶君 发表于 2020-7-19 17:44
现在高中生业余时间就玩这些了吗，不能好好去网吧开黑吗。越来越不懂00后了
学信息学竞赛玩算法其实挺正常的 好强好强，哈哈哈，独孤求败都自愧不如 看起来非常的厉害 我记得二分法用的比较多吧？复杂函数求导不好整 本帖最后由 Lifetimer 于 2020-7-19 18:35 编辑
从0开始的小小怪 发表于 2020-7-19 18:18
我记得二分法用的比较多吧？复杂函数求导不好整
二分法实现简单，编程速度快，但是执行效率低，要达到较高精确度不容易，
牛顿法实现复杂，但是达到较高精度极快，且不需要知道方程的根的大概位置。
一般二分法即可，但是牛顿法也未尝不可，
算法这东西多了解一些还是好的
页:
[1]
2