import matplotlib.pyplot as plt
import numpy as np
x1 = np.linspace(-32, 32, 256)
fx = 2 * x1 # 函数定义
y1 = 0 * x1 # x轴
# f(x) = f(xi) + f'(xi)(x - xi) 其实f'为导函数
f2 = (x1 * x1)-16
xi = 7.8 #第一次迭代随机7.8位置
t1 = ((xi * xi) - 16) + 2 * xi * (x1 - xi)
xi=4.9 #第二次迭代为前一次切线与x轴交点
t2 = ((xi * xi) - 16) + 2 * xi * (x1 - xi)
xi=4.1 #第三次迭代为第二次切线与x轴交点
t3 = ((xi * xi) - 16) + 2 * xi * (x1 - xi)
xi=4 #第四次迭代为第三次切线与x轴承交点
t4 = ((xi * xi) - 16) + 2 * xi * (x1 - xi)
plt.figure()
plt.title('y=pow(x,2)')
plt.xlabel('x')
x_ticks = np.arange(-16, 16, 2)
x_label_ticks = [('{}'.format(x)) for x in x_ticks]
plt.xticks(x_ticks, x_label_ticks)
y_ticks = np.arange(-16, 16, 2)
y_label_ticks = [('{}'.format(y)) for y in y_ticks]
plt.yticks(y_ticks, y_label_ticks)
plt.ylabel('y')
plt.plot(x1, fx, label="line f'(x)")
plt.plot(x1, t1, label="line 7.8")
plt.plot(x1, t2, label="line 4.9")
plt.plot(x1, t3, label="line 4.1")
plt.plot(x1, t4, label="line 4.0")
plt.plot(x1, y1, label="y=0")
plt.plot(x1, f2, label="f(x)")
plt.grid(True)
plt.legend(loc="upper left")
plt.axis([-16, 16, -16, 16])
plt.show()
image.png
https://leetcode-cn.com/problems/sqrtx/submissions/
二分查找实现大于平方根的最小值
public int mySqrt(int x) {
//为提高性能特殊判断 x/2
if(x==1){
return 1;
}
int l = 0, r = x/2,mid=-1;
//int 相乖可能溢出
long sqrt=0;
while (l <= r) {
//mid 计算逻辑一致
mid = l + (r - l) / 2;
sqrt=(long)mid*mid;
if(sqrt==x){
//如果找到直接返回
return mid;
}
if (sqrt < x) {
//这里是mid -1
l = mid + 1;
} else {
r = mid - 1;
}
}
//取比当前值小的最大平方根
return sqrt<x?mid:mid-1;
}
牛顿迭代法
- 原函数为f(x)=pow(x,2)
- 导函数为f'(x)=2x
- 在原函数随机采点(x0,y0) ，在该点求导，即过该点斜率，并导出该点的切线方程
- 已知切线为一条直线，根据切线定义与原函数曲线有且只有一个交点，即（x0,y0), 由导数定义可知，过该点的切线斜率为导数
5.在直接线任取一点（x,y) ，由(4)导出切线方程为
6.求出切线方程与x轴交点，即y=0时
- 求出切线与x轴交点后，代入原函数求y 生成新的(x0,y0),过该点求新的切线方程，反复迭代直至收敛，即
class Solution {
public int mySqrt(int n) {
if(n==0){
return 0;
}
double x0 = n / 2F;
double x;
while (true) {
x = x0;
//x0= (x0*x0+n)/(2*x0) //注意 (x0*x0+n)/2*x0 一定要加()
x0 = 0.5 * (x0 + n / x0);
//x0 = -(x0 * x0 - n) / (2 * x0) + x0;
if (x - x0 <1e-7) {
break;
}
}
return (int)x0;
}
}
