• 2021-04-19 08:39:54

不动点迭代

function xc = fpi( g, x0, tol )

x(1) = x0;

i = 1;

while 1

x(i + 1) = g(x(i));

if(abs(x(i+1) - x(i)) < tol)

break

end

i = i + 1;

end

xc = x(i+1);

end

牛顿法找根：

$$f( x ) = ( 1 - \frac{3}{4x} ) ^ {\frac{1}{3} }$$

封装函数计算：

x_right = solve('(1 - 3 / (4 * x)) ^ (1 / 3)')

牛顿法实现：

function [y, dirv_y] = funNewton(x)

y = (1 - 3 / (4 * x)) ^ (1 / 3);

dirv_y = (1 - 3 / (4 * x)) ^ (- 2 / 3) / (4 * x ^ 2);

% dirv_y is y's diff

end

clear all

clc

Error = 1e-6;

format long

x_right = solve('(1 - 3 / (4 * x)) ^ (1 / 3)')

x = 0.7;

for k = 1:50

[y, dirv_y] = funNewton(x);

%call the function to get the f(x) and it's diff

xk = x;

disp(['the ', num2str(k), ' time is ', num2str(x)])

%xk to save the last time value of x

x = x - y / dirv_y;

%newton solve

if(abs(xk - x) < Error)

%decide whether to break out

break;

end

end

xk

%output the value of x

割线法：

function xc = CutLine( f, x0, x1, tol )

x(1) = x0;

x(2) = x1;

i = 2;

while 1

x(i + 1) = x(i) - (f(x(i)) * (x(i) - x(i - 1))) / (f(x(i)) - f(x(i - 1)));

if(abs(x(i + 1) - x(i)) < tol)

break;

end

i = i + 1;

end

xc = x(i + 1);

end

Stewart平台运动学问题求解：

function out = Stewart( theta )

% set the parameter

x1 = 4;

x2 = 0;

y2 = 4;

L1 = 2;

L2 = sqrt(2);

L3 = sqrt(2);

gamma = pi / 2;

p1 = sqrt(5);

p2 = sqrt(5);

p3 = sqrt(5);

A2 = L3 * cos(theta) - x1;

B2 = L3 * sin(theta);

A3 = L2 * cos(theta + gamma) - x2;

B3 = L2 * sin(theta + gamma) - y2;

N1 = B3 * (p2 ^ 2 - p1 ^ 2 - A2 ^ 2 - B2 ^ 2) - B2 * (p3 ^ 2 - p1 ^ 2 - A3 ^ 2 - B3 ^ 2);

N2 = -A3 * (p2 ^ 2 - p1 ^ 2 - A2 ^ 2 - B2 ^ 2) + A2 * (p3 ^ 2 - p1 ^ 2 - A3 ^ 2 - B3 ^ 2);

D = 2 * (A2 * B3 - B2 * A3);

out = N1 ^ 2 + N2 ^ 2 - p1 ^ 2 * D ^ 2;

end

test our function at theta = - pi / 4 and theta = pi / 4

clear all

clc

format short

disp('f(- pi / 4) is ')

out1 = Stewart(- pi / 4)

disp('--------------')

disp('f(pi / 4) is ')

out2 = Stewart(pi / 4)

更多相关内容
• 【问题描述】在[a,b]区间内寻找方程x**5-2*x-1=0的根的初始近似值位置，确定不动点迭代的初始点（可能有多个），然后使用不动点迭代法求方程的根（可能有多个根）。前后两次迭代的差的绝对值小于delta后停止迭代。 ...
• 1.领域：matlab，梯度下降,不动点迭代法,牛顿迭代法 2.内容：分别通过梯度下降,不动点迭代法,牛顿迭代法对方程进行求解+代码操作视频 3.用处：用于梯度下降,不动点迭代法,牛顿迭代法编程学习 4.指向人群：...
• 在[a,b]区间内寻找方程x**5-2*x-1=0的根的初始近似值位置，确定不动点迭代的初始点（可能有多个），然后使用不动点迭代法求方程的根（可能有多个根）。前后两次迭代的差的绝对值小于delta后停止迭代。 输入形式 在...

## 问题描述

在[a,b]区间内寻找方程x**5-2*x-1=0的根的初始近似值位置，确定不动点迭代的初始点（可能有多个），然后使用不动点迭代法求方程的根（可能有多个根）。前后两次迭代的差的绝对值小于delta后停止迭代。

## 输入形式

在屏幕上输入3个数，依次为区间左端点值a、右端点值b和所求根的精度值。各数间都以一个空格分隔。根据输入的所求根的精度值可求得delta.

## 输出形式

每一行输出一个根（精确到小数点后3位）

-1.2 1.5 3

-1.000
-0.519
1.291

## 样例1说明

输入：左端点a值为-1.2，右端点b值为1.5，前后两次迭代的差的绝对值小于delta=10**(-3)后停止迭代。输出：从小到大顺序输出三个根的值。

## 代码

import numpy as np

def f(x):
return x ** 5 - 2 * x - 1

def g1(x):
return (x**5-1)/2

def g2(x):
result = (abs(2 * x + 1))**(1 / 5)
if (2 * x - 1) < 0:
return -result
return result

def getEpsilon(x, epsilon):
maxY = minY = x[0]
for each in x:
maxY = max(f(each), maxY)
minY = min((f(each), minY))
epsilon = (maxY - minY) * epsilon
return epsilon

def getInitialVal(x, N, step, epsilon):
initalVal = []
for i in range(N + 1):
y1, y2, y3 = f(x - step), f(x), f(x + step)
if (y1 * y2 < 0) and (i != 0):
initalVal.append((x + x - step) / 2)
if ((y2 - y1) * (y3 - y2) < 0) and (abs(y2) < epsilon):
initalVal.append(x)
x += step

return initalVal

def findFixedPoint(initalVal, delta,epsilon):
points = []
for each in initalVal:
if (abs(g1(each)) < 1):
points.append(iteration(each, g1, delta,epsilon))
else:
points.append(iteration(each, g2, delta,epsilon))
return points

def iteration(p1, g, delta,epsilon):
while True:
p2 = g(p1)
err =abs(p2-p1)
relerr = err/(abs(p2)+epsilon)
if err<delta or relerr<delta:
return p2
p1 = p2

def main():
a, b, c = input().split(' ')
a = float(a)
b = float(b)
c = int(c)
delta = 10 ** (-c)
N = 8
epsilon = 0.01
step = (b - a) / N
x = np.arange(a, b + epsilon, epsilon)

epsilon2 = getEpsilon(x,epsilon)
initalVal = getInitialVal(a, N, step, epsilon2)
ans = findFixedPoint(initalVal, delta,epsilon)

for each in ans:
print('%.3f' % each)

if __name__ == '__main__':
main()

展开全文
• 方程根的常用迭代法有：二分法、不动点迭代、牛顿、弦截 不动点迭代法 简单迭代法或基本迭代法又称不动点迭代法 1、不动点（FixedPoint） 首先来看一下什么是不动点： 换句话说，函数φ的不动点是y=φ(x)与y

## 迭代法的作用

许多复杂的求解问题，都可以转换成方程f(x)=0的求解问题。这一系列的解叫做方程的根。对于非线性方程的求解，在自变量范围内往往有多个解，我们将此变化区域分为多个小的子区间，对每个区间进行分别求解。我们在求解过程中，选取一个近似值或者近似区间，然后运用迭代方法逐步逼近真实解。
方程求根的常用迭代法有：二分法不动点迭代牛顿法弦截法

## 不动点迭代法

简单迭代法或基本迭代法又称不动点迭代法
1、不动点（FixedPoint）
首先来看一下什么是不动点：

换句话说，函数φ的不动点是y=φ(x)与y=x的交点，下图画出了函数y=cos(x)与y=x在区间[0,π/2]的交点，即cos(x)的不动点：

2、不动点迭代（Fixed Point Iteration）
不动点迭代的基本思想：

也就是说，为了求解方程f(x)=0，首先将方程转换为x=g(x)，然后初始化x0，循环迭代xi+1=g(xi)，直到满足收敛收件。
这里将方程f(x)=0转换为x=g(x)是很容易的，比如对于f(x)=x-cos(x)，求解f(x)=0即为求解x-cos(x)=0，即x=cos(x)，因此g(x)=cos(x)。
再例如对于方程：

可以等价为

还可以等价为

也就是说，将方程f(x)=0转换为x=g(x)有不同的方式，因此对方程f(x)=0来说，g(x)也不是唯一的。
3、不动点迭代的收敛性
这个迭代过程是很简单的，但这里有个关键性的问题：迭代收敛么？即经过N次迭代后是否会收敛于不动点？

通俗点讲，若要使不动点迭代收敛，则要求φ(x)在区间[a,b]上的函数值也在此区间内，另外还要求φ(x)的斜率绝对值不大于1。其证明过程比较复杂，有兴趣的可以查阅一些相关文献。

## 例题

求方程式：x3 - 0.165 × x2 + 3.993 × 10-4 = 0在（0，0.11）上的根

## 先看看不用迭代法计算的结果

from sympy import *
from sympy.abc import x

def func(x):
return x**3 - 0.165*x**2 + 3.993*10**(-4)
result = solveset(func(x), x, Interval(0, 0.11))
print(result)


结果：

FiniteSet(0.0623775815137495)



## 约定一个误差，当误差小于某个数值的时候，迭代停止

代码：

xl = 0  #区间下限
xu = 0.11  #区间上限
x = (xl+xu)/2  #迭代初始值
x_list = [x]
i = 0

while True:
x = x ** 3 - 0.165 * x ** 2 + 3.993 * 10 ** (-4) + x
x_list.append(x)
if len(x_list) > 1:
i += 1
error = abs((x_list[-1] - x_list[-2]) / x_list[-1])
if error < 10**(-6):
print(f'迭代第{i}次后，误差小于10^-6')
break
else:
pass


结果：

迭代第777次后，误差小于10^-6
所求方程式的根为0.062370654088088


## 迭代至电脑默认误差为0

xl = 0  #区间下限
xu = 0.11  #区间上限
x = (xl+xu)/2  #迭代初始值
x_list = [x]
i = 0

while True:
x = x ** 3 - 0.165 * x ** 2 + 3.993 * 10 ** (-4) + x
x_list.append(x)
if len(x_list) > 1:
i += 1
error = abs((x_list[-1] - x_list[-2]) / x_list[-1])
if error == 0:
print(f'迭代第{i}次后，误差为0')
break
else:
pass

print(f'所求方程式的根为{x_list[-1]}')


结果：

迭代第3402次后，误差为0
所求方程式的根为0.062377581513749114


## 画迭代法

import matplotlib.pyplot as plt
xl = 0  #区间下限
xu = 0.11  #区间上限
x = (xl+xu)/2  #迭代初始值
x_list = [x]
i = 0

x_values = []
y_values = []
while True:
x = x ** 3 - 0.165 * x ** 2 + 3.993 * 10 ** (-4) + x
x_list.append(x)
if len(x_list) > 1:
i += 1
error = abs((x_list[-1] - x_list[-2]) / x_list[-1])
x_values.append(i)
y_values.append(error)
if error == 0:
print(f'迭代第{i}次后，误差为0')
break
else:
pass

print(f'所求方程式的根为{x_list[-1]}')

#设置绘图风格
plt.style.use('ggplot')
#处理中文乱码
plt.rcParams['font.sans-serif'] = ['Microsoft YaHei']
#坐标轴负号的处理
plt.rcParams['axes.unicode_minus']=False
#横坐标是迭代次数
#纵坐标是误差值
plt.plot(x_values,
y_values,
color = 'steelblue', # 折线颜色
marker = 'o', # 折线图中添加圆点
markersize = 1, # 点的大小
)
# 修改x轴和y轴标签
plt.xlabel('迭代次数')
plt.ylabel('误差值')
# 显示图形
plt.show()


结果：

迭代第3402次后，误差为0
所求方程式的根为0.062377581513749114


对比牛顿迭代法，牛顿迭代法要快很多，而且准确率也高
牛顿迭代法（Newton’s Method）迭代求根的Python程序

展开全文
• Matlab 根代码 包括Newton、Secant、Steffenson、Aitken's不动点迭代法，以及包括这些方法求同一个函数时候初始猜测值和迭代次数的比较，并用图像呈现。
• 不动点迭代和牛顿迭代法不动点迭代feval函数简单迭代法 不动点迭代 不动点可看成 y=φ(x)与y=xy=φ(x)与y=xy=φ(x)与y=x 的交点 feval函数 功能是函数值 基本使用格式：y=feval(fhandle, x) %fhandle——函数...

## MATLAB基础

### feval函数

用于求函数值

基本使用格式：y=feval(fhandle, x)
%fhandle——函数表达式，x——变量值[y1, y2, ...] = feval(fhandle, x1,..., xn)


### format long

设置输出格式，表示高精度输出

### syms x

定义符号变量，用于占位符占位！

## 简单迭代法【不动点迭代】

大致讲解：

不动点可看成 y = φ ( x ) 与 y = x y=φ(x)与y=x 的交点

MATLAB实现：

function [x,count]=Simple_iterative_method(x0,tol)
format long    %High precision output
error=1;    %The value of the initialization error
count=0;    %Initialization counter
while error>tol  %Shutdown criteria
x=f(x0);   %Function to be solved
error=abs(x-x0);  %Update the error of each step
x0=x;  %Update iteration point
count=count+1;
end
end

%%Definition of function to be solved
function f=f(x)
f=(10/(4+x))^(1/2);
end


测试文件：

clear;  %Empty variable
clc;   %Clear screen
tol=1e-9;  %Set the required precision
x0=1.5;  %Exact solution of the point near
[x,count]=Simple_iterative_method(x0,tol);  %Use simple iterative algorithm
disp('The exact solution is as follows:')
disp(x);
disp('Number of iterations required:')
disp(count);


结果展示：

## Newton 迭代法

matlab算法实现

function [x,count]=Newton_it(x0,tol)
format long
error=1;
count=0;
while error>tol
x=x0-f(x0)/df(x0);  %Newton iteration scheme
error=abs(x-x0);
x0=x;
count=count+1;
end
end

%%Enter the function test below
function f=f(x0)
syms x;                %Defining symbolic variables
m(x)=x^2-115;
f=vpa(m(x0));      %Calculate the value of the symbolic variable
end

function df=df(x0)  %Calculating the first derivative of a function
syms x;                %Defining symbolic variables
m(x)=x^2-115;
df(x)=diff(m(x));
df=vpa(df(x0));
end


测试文件

clear;  %Empty variable
clc;   %Clear screen
x0=10;
tol=1e-6;
[x,count]=Newton_it(x0,tol);
disp('The exact solution is as follows:')
disp(x);
disp('Number of iterations required:')
disp(count);


结果展示：

## 作业

1. 用两种迭代方式求解一个多项式的根，多项式满足下面两个条件：
（1）7次多项式
（2）系数在(0,7] 之间
要求：写出收敛阶、收敛速度、初值
2. 求出下面方程的根并作图 x 2 + ( 5 4 y − ∣ x ∣ ) 2 − 4 = 0 x^{2}+\left ( \frac{5}{4}y-\sqrt{|x|} \right )^{2}-4=0
初值（这个方程的初值不好找！）

尝试解答：

1.如何生成一个随机整数向量（满足第二个条件叭）

round(rand(1,5)*6+1)


2.构造随机多项式

function f=ex6_1(x0,p0)     %Constructing polynomials
syms x;                %Defining symbolic variables
y(x)=poly2sym(p0);
disp(y(x));
f=vpa(y(x0));      %Calculate the value of the symbolic variable
end

p0=round(rand(1,8)*6+1);
%If you put it in a function, every time you call the function, a polynomial will be generated randomly
x0=2;
f=ex6_1(x0,p0);
disp(f);
x0=0;
f=ex6_1(x0,p0);
disp(f);


输出结果：

3.尝试使用简单迭代法

function [x,count]=Simple_iterative_method(x0,tol)
format long    %High precision output
error=1;    %The value of the initialization error
count=0;    %Initialization counter
while error>tol  %Shutdown criteria
x=f(x0);   %Function to be solved
error=abs(x-x0);  %Update the error of each step
x0=x;  %Update iteration point
count=count+1;
end
end

%%Definition of function to be solved
function f=f(x0)
syms x;                %Defining symbolic variables
p0=round(rand(1,8)*6+1);  %Each time the function is called, a random polynomial is constructed
y(x)=poly2sym(p0);
f=vpa(y(x0));      %Calculate the value of the symbolic variable
end

clear;  %Empty variable
clc;   %Clear screen
tol=1e-9;  %Set the required precision
x0=0;  %Exact solution of the point near
[x,count]=Simple_iterative_method(x0,tol);  %Use simple iterative algorithm
disp('The exact solution is as follows:')
disp(x);
disp('Number of iterations required:')
disp(count);


输出结果（这是什么东西…）：

构造多项式并改写成 x = ϕ ( x ) x=\phi(x) 的形式

function [f,df]=ex6_1(x0,p0)
syms x;                %Defining symbolic variablesS
y(x)=poly2sym(p0);
% disp('This is a randomly generated equation of degree 7')
% disp(y(x));
q(x)=((y(x)-p0(6)*x^2)/(-p0(6)))^(1/2);
% disp('This is phi(x)');
% disp(q(x));
f=vpa(q(x0));      %Calculate the value of the symbolic variable
df(x)=diff(q(x));
df=vpa(df(x0));
end

function [x,count]=Newton_it(x0,tol)
format long
error=1;
count=0;
p0=round(rand(1,8)*6+1);
while error>tol && count <50
[f,df]=ex6_1(x0,p0);
x=x0-f/df;  %Newton iteration scheme
error=abs(x-x0);
disp('error:')
disp(error);
x0=x;
count=count+1;
end
end

clear;  %Empty variable
clc;   %Clear screen
x0=10;
tol=1e-3;
[x,count]=Newton_it(x0,tol);
disp('The exact solution is as follows:')
disp(x);
disp('Number of iterations required:')
disp(count);

function [x,count]=Simple_iterative_method(x0,tol)
format long    %High precision output
error=1;    %The value of the initialization error
count=0;    %Initialization counter
p0=round(rand(1,8)*6+1);
disp(p0);
while error>tol && count<20 %Shutdown criteria
x=ex6_1(x0,p0);   %Function to be solved
disp(x0);
count=count+1;
error=abs(x-x0);
disp('it is error');
disp(error);
x0=x;
end
end

clear;  %Empty variable
clc;   %Clear screen
tol=1e-5;  %Set the required precision
x0=0;  %Exact solution of the point near
[x,count]=Simple_iterative_method(x0,tol);  %Use simple iterative algorithm
disp('The exact solution is as follows:')
disp(x);
disp('Number of iterations required:')
disp(count);

close all;
clear all;
clc;
ezplot('x^2+((5/4)*y-sqrt(abs(x)))^2-4=0',[-3,3])
grid on

展开全文
• 不动点迭代法求方程的根（Python实现）不动点迭代法求方程的根：是迭代法解方程的根当中经典的方法。将求解f(x) = 0的问题变成x = h(x)这样的问题。转变的方程很简单，一般是移项，平方，开根号什么的。难点： 问题...
• 不动点是什么？...不动点迭代法，是方程的迭代方法。为什么要迭代，直接不好吗？直接显然比较好，但是存在弊端，比如函数形式较复杂时，求解器不容易直接求得。利用不动点的性质，可以...
• 1）在区间[0,1]内用二分法方程ex+10∗x−2e^x+10*x-2ex+10∗x−2的近似根，要求误差超过0.5×10−30.5\times10^{-3}0.5×10−3。 2）取初值x0=0x_0=0x0​=0，用迭代公式xk+1=2−exk10,(k=0,1,2,...)x_{...
• 不动点迭代法 一元非线性方程根 C语言实现
• 不动点迭代法的 MATLAB 程序代码如下: Function [root,n]=StablePoint(f,x0,eps) %用不动点迭代法求函数的一个零点 %初始迭代向量:x0 %根的精度:eps %......流程图:输入参数 f,x0,eps 迭代算根 否 比较精度是否符合...
• 1 概述 在工程和科学技术中,许多问题常归结为求解函数方程: f(x)=0 ...五次以上的代数方程和超越方程一般没有根公式，很难或者无法求得其精确解，而实际应用中要得到满足一定精度的近似解就...
• 反之亦然，我们称为函数的一个不动点f(x)的零点就等价于g（x）的不动点，选择一个初始近似值，将其带入右端，即,反复迭代之后得到,g(x)称为迭代函数，而且当k-&gt;∞, 例题： 方程在附近的根 x=1.5;...
• 方程根：二分法--不动点迭代--牛顿--弦截1.问题概述 许多复杂的求解问题，都可以转换成方程f(x)=0的求解问题。这一系列的解叫做方程的根。对于非线性方程的求解，在自变量范围内往往有多个解，我们将此变化...
• 使用定点迭代计算单变量函数不动点。 句法 c = fixed_point_iteration(f,x0) c = fixed_point_iteration(f,x0,TOL) c = fixed_point_iteration(f,x0,[],imax) c = fixed_point_iteration(f,x0,TOL,imax) c = ...
• 不动点迭代以及其收敛性对于迭代的理解不动点迭代迭代的收敛性区间收敛局部收敛 对于迭代的理解   所谓迭代就是反复使用执行某一个过程，并且用本次执行该过程的结果作为下一次执行的起点，不断推进，直到得到满足...
• Python实现二分法、不动点迭代法、牛顿 数值分析：Python实现二分法、不动点迭代法、牛顿 一、问题定义 二、相关概念 三、方程根的几种常用方法 1、二分法 2、不动点迭代法 3、牛顿 题目：编写实现...
• 这一节则主要是针对算法的收敛性进行分析，试图从一个更加抽象的层面，利用不动点迭代的思想，把上面的算法综合起来，给一个比较 general 的收敛性分析方法。 1. 什么是不动点？ 对于希尔伯特空间(Hilbert space) H\...
• 1.1.1.不动点不动点迭代法 对于方程 f(x)=0(1.1)(1.1)f(x)=0f(x) = 0\tag{1.1} 改写成 x=φ(x)(1.2)(1.2)x=φ(x) x = \varphi(x)\tag{1.2} 若要求x∗x∗x^*满足f(x∗)=0f(x∗)=0f(x^*) = 0，则x∗=φ(x∗)x∗...
• 不动点迭代法（Fixed Point Iteration）又叫简单迭代法，对于一个非线性方程 f(x)=0f(x)=0f(x)=0 将其转换成以下形式： x=φ(x)x=\varphi (x)x=φ(x) 假设 φ(x)\varphi (x)φ(x) 是一个连续函数（φ(x)\varphi (x)...
• 首先最简单的方法莫过于画一个函数图像看一看。 其次，我们可以使用如下两个原则去确定初始根 <1>、y(k-1)y(k)<0，该的左右两边y值正负号相反，由中值定理知道必有一根。 <2>、|y(k)|<一个小数&...
• 不动点迭代法求方程f(x)=x^3-2*x-1=0的根，按以下两种方案实现，分析迭代函数对收敛性的影响。要求输出每次的迭代结果并统计所用的迭代次数,取精度c=0.5*10^(-5)，x0=2. 方案一：化方程为等价方程x=pow(2*x+1,...
• 7BenvliMIN 贝努利法求按模最小实根HalfInterval 用二分法方程的一个根hj 用黄金分割法求方程的一个根StablePoint 用不动点迭代法求方程的一个根AtkenStablePoint 用艾肯特加速的不动点迭代法求方程的一个根...
• 分别用二分法、试位不动点迭代、Newton-Raphson和割线求解并比较各方法的收敛速度
• 关于不动点迭代和二分法、试值的本质区别，在[上一篇介绍二分法、试值]的博客中提到了(https://blog.csdn.net/weixin_42572826/article/details/104934857)，理论上不动点迭代，只能对给定的一个近似解迭代找到...
• %不动点迭代 function [xc,k] = fpi(g,x0,tol,N) x1=g(x0); k=1; while abs(x1-x0) > tol x0 =x1; x1=g(x0); if k==N fprintf('Fixed-point iteration failed!') break end k=k+1; end xc = x1;
• 1. 不动点不动点迭代法设 f 是连续函数，为了解方程 把方程变换为等价的方程 其中φ 是连续函数。若x* 是f 的零点，即f(x*)=0 则有 x*称为函数φ 的一个不动点.构造的迭代法 这称为一种...
• 非线性方程求解 不动点迭代法 Solution Knowledge 收敛定理一 可以尝试证明一下 1、不动点的存在性 2、不动点的唯一性 3、序列收敛 收敛定理二 这个的条件2更加简洁 可以尝试证明 1、不动点的存在性（其实同定理...

...