牛顿迭代法

 

目录

一、牛顿迭代公式

二、利用牛顿迭代公式求平方根

C 语言实现

Python 语言实现 

三、利用牛顿迭代公式求立方根

C 语言实现

Python 语言实现

 

一、牛顿迭代公式

多数方程不存在求根公式,因此求精确根非常困难,甚至不可解,从而寻求方程的近似根就显得尤为重要。牛顿就提出了一种用迭代求方程近似根的方法,思路是不断取切线,用线性方程的根逼近非线性方程 f(x) = 0 的根

具体过程

设 x* 是 f(x) = 0 的根,选取 x0 作为 x* 的初始近似值,过点 (x0,f(x0)) 作曲线 y = f(x) 的切线 L,L:y = f(x0) + f'(x0)(x – x0),则 L 与 x 轴交点的横坐标为:gif.latex?x_1%20%3D%20x_0%20-%20%5Cfrac%7Bf%28x_0%29%7D%7Bf%27%28x_0%29%7D,称 x1 为 x* 的一次近似值。过点 (x1, f(x1)) 作曲线 y = f(x) 的切线,切线与 x 轴的交点横坐标为:gif.latex?x_2%20%3D%20x_1%20-%20%5Cfrac%7Bf%28x_1%29%7D%7Bf%27%28x_1%29%7D,称 x2 为 x* 的二次近似值。重复上述过程,得 x* 的近似值序列,其中:gif.latex?x_%7Bn+1%7D%20%3D%20x_n%20-%20%5Cfrac%7Bf%28x_n%29%7D%7Bf%27%28x_n%29%7D 称为 x* 的 n + 1 次近似值,上式称为牛顿迭代公式

概述图

fca93d38ec264b41a788103e8cc48660.png

 

 

二、利用牛顿迭代公式求平方根

求数 a 的平方根,即求二次方程 f(x) = x^2 – a = 0(a >= 0)的根,f'(x) = 2x,利用牛顿迭代公式,则有: gif.latex?x_%7Bn+1%7D%20%3D%20x_n%20-%20%5Cfrac%7Bx_n%5E2%20-%20a%7D%7B2x_n%7D%20%3D%20%5Cfrac%7B1%7D%7B2%7D%28x_n%20+%20%5Cfrac%7Ba%7D%7Bx_n%7D%29

C 语言实现

#include <stdio.h>
#include <math.h>

double square_root(double a)
{
	if (a < 0)
	{
		return -1;
	}
	double t = a;  // t 为近似值
	while (fabs(t * t - a) > 1e-10)
	{
		t = (t + a / t) / 2.0;
	}
	return t;
}

int main()
{
	double a = 0.0;
	scanf("%lf", &a);
	double ret = square_root(a);
	printf("%lf\n", ret);
	return 0;
}

fabs(t * t – a) > 1e-10:是将方程的近似值 t 代入方程 f(x) = x^2 – a 中,判断绝对误差是否小于等于 1e – 10。  

Python 语言实现 

def square_root(a):
    if a < 0:
        return -1
    t = a
    while abs(t * t - a) > 1e-10:
        t = (t + a / t) / 2.0
    return t


print(square_root(3))  # 1.7320508075688772
print(square_root(5))  # 2.236067977499978
print(square_root(10))  # 3.162277660168379
print(square_root(-10))  # -1

 

 

三、利用牛顿迭代公式求立方根

同理,求数 a 的立方根,即求三次方程 f(x) = x^3 – a = 0 的根,f'(x) = 3×2,利用牛顿迭代公式,则有: gif.latex?x_%7Bn+1%7D%20%3D%20x_%7Bn%7D%20-%20%5Cfrac%7Bx_n%5E3-a%7D%7B3x_n%5E2%7D%20%3D%20%5Cfrac%7B1%7D%7B3%7D%282x_n%20+%20%5Cfrac%7Ba%7D%7Bx_n%5E2%7D%29

C 语言实现

#include <stdio.h>
#include <math.h>

double cube_root(double a)
{
	double t = a;
	while (fabs(t * t * t - a) > 1e-10)
	{
		t = (2 * t + a / (t * t)) / 3.0;
	}
	return t;
}

int main()
{
	double a = 0.0;
	scanf("%lf", &a);
	double ret = cube_root(a);
	printf("%lf\n", ret);
	return 0;
}

Python 语言实现

def cube_root(a):
    t = a
    while abs(t * t * t - a) > 1e-10:
        t = (2 * t + a / (t * t)) / 3.0
    return t


print(cube_root(3))  # 1.4422495703074112
print(cube_root(5))  # 1.7099759466766973
print(cube_root(10))  # 2.154434690031893
print(cube_root(-10))  # -2.154434690031893

 

 

 

 

 

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
扎眼的阳光的头像扎眼的阳光普通用户
上一篇 2023年3月5日 下午10:45
下一篇 2023年3月5日 下午10:47

相关推荐