方程求根 - 二分法¶
选取$[a, b]$使根$x_0 \in [a, b]$，进行迭代
$$\sqrt{2} = 1.4142135623730951$$
In [8]:
def binary_get_root(f, left, right, n):
for i in range(1, n + 1):
mid = left + (right - left) / 2
left_value = f(left)
right_value = f(right)
mid_value = f(mid)
if mid_value == 0:
print(f'第{i}次迭代找到根为{mid_value}')
break
print(f'第{i}次迭代, left={left} left_value={left_value} right={right} right_value={right_value} mid={mid} mid_value={mid_value}')
if left_value * mid_value > 0:
left = mid
else:
right = mid
In [9]:
def f1(x):
return x * x - 2
binary_get_root(f=f1, left=1, right=2, n=10)
第1次迭代, left=1 left_value=-1 right=2 right_value=2 mid=1.5 mid_value=0.25 第2次迭代, left=1 left_value=-1 right=1.5 right_value=0.25 mid=1.25 mid_value=-0.4375 第3次迭代, left=1.25 left_value=-0.4375 right=1.5 right_value=0.25 mid=1.375 mid_value=-0.109375 第4次迭代, left=1.375 left_value=-0.109375 right=1.5 right_value=0.25 mid=1.4375 mid_value=0.06640625 第5次迭代, left=1.375 left_value=-0.109375 right=1.4375 right_value=0.06640625 mid=1.40625 mid_value=-0.0224609375 第6次迭代, left=1.40625 left_value=-0.0224609375 right=1.4375 right_value=0.06640625 mid=1.421875 mid_value=0.021728515625 第7次迭代, left=1.40625 left_value=-0.0224609375 right=1.421875 right_value=0.021728515625 mid=1.4140625 mid_value=-0.00042724609375 第8次迭代, left=1.4140625 left_value=-0.00042724609375 right=1.421875 right_value=0.021728515625 mid=1.41796875 mid_value=0.0106353759765625 第9次迭代, left=1.4140625 left_value=-0.00042724609375 right=1.41796875 right_value=0.0106353759765625 mid=1.416015625 mid_value=0.005100250244140625 第10次迭代, left=1.4140625 left_value=-0.00042724609375 right=1.416015625 right_value=0.005100250244140625 mid=1.4150390625 mid_value=0.0023355484008789062
In [10]:
def f1(x):
return x * x - 2
binary_get_root(f=f1, left=1.41, right=1.5, n=10)
第1次迭代, left=1.41 left_value=-0.011900000000000244 right=1.5 right_value=0.25 mid=1.455 mid_value=0.11702500000000038 第2次迭代, left=1.41 left_value=-0.011900000000000244 right=1.455 right_value=0.11702500000000038 mid=1.4325 mid_value=0.05205625000000014 第3次迭代, left=1.41 left_value=-0.011900000000000244 right=1.4325 right_value=0.05205625000000014 mid=1.4212500000000001 mid_value=0.019951562500000186 第4次迭代, left=1.41 left_value=-0.011900000000000244 right=1.4212500000000001 right_value=0.019951562500000186 mid=1.415625 mid_value=0.003994140624999698 第5次迭代, left=1.41 left_value=-0.011900000000000244 right=1.415625 right_value=0.003994140624999698 mid=1.4128124999999998 mid_value=-0.003960839843750508 第6次迭代, left=1.4128124999999998 left_value=-0.003960839843750508 right=1.415625 right_value=0.003994140624999698 mid=1.4142187499999999 mid_value=1.4672851562202993e-05 第7次迭代, left=1.4128124999999998 left_value=-0.003960839843750508 right=1.4142187499999999 right_value=1.4672851562202993e-05 mid=1.4135156249999998 mid_value=-0.0019735778808598337 第8次迭代, left=1.4135156249999998 left_value=-0.0019735778808598337 right=1.4142187499999999 right_value=1.4672851562202993e-05 mid=1.4138671874999997 mid_value=-0.000979576110840652 第9次迭代, left=1.4138671874999997 left_value=-0.000979576110840652 right=1.4142187499999999 right_value=1.4672851562202993e-05 mid=1.4140429687499998 mid_value=-0.0004824825286871004 第10次迭代, left=1.4140429687499998 left_value=-0.0004824825286871004 right=1.4142187499999999 right_value=1.4672851562202993e-05 mid=1.4141308593749997 mid_value=-0.000233912563324834